हॉर्नर की विधि

गणित और कंप्यूटर विज्ञान में, हॉर्नर की विधि या हॉर्नर की योजना बहुपद मूल्यांकन के लिए एक कलन विधि के रूप में होती है। यद्यपि विलियम जॉर्ज हॉर्नर के नाम पर इसका नाम रखा गया, यह बहुत पुरानी विधि के रूप में है और इसका श्रेय हॉर्नर द्वारा जोसेफ-लुई लाग्रेंज को दिया गया है तथा चीनी और फ़ारसी गणितज्ञों को कई सैकड़ों वर्षों में खोजा गया है। कंप्यूटरों के आगमन के बाद, यह कलन विधि बहुपदों के साथ कुशलतापूर्वक गणना करने के लिए मूलभूत रूप में बन गया।

कलन विधि हॉर्नर के नियम पर आधारित है, जिसमें एक बहुपद को 'नेस्टेड फॉर्म' में लिखा गया है

${\begin{aligned}a_{0}&+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\cdots +a_{n}x^{n}\\&=a_{0}+x{\bigg (}a_{1}+x{\Big (}a_{2}+x{\big (}a_{3}+\cdots +x(a_{n-1}+x\,a_{n})\cdots {\big )}{\Big )}{\bigg )}.\end{aligned}}$

यह केवल n गुणन और n जोड़ के साथ घात n के बहुपद के मूल्यांकन की अनुमति देता है। यह इष्टतम है, क्योंकि घात n के बहुपद हैं जिनका मूल्यांकन कम अंकगणितीय परिचालनों के साथ नहीं किया जा सकता है

वैकल्पिक रूप से, हॉर्नर की विधि 1819 में हॉर्नर द्वारा वर्णित बहुपदों की रूट्स का अनुमान लगाने के लिए एक विधि को संदर्भित करती है। यह न्यूटन रैप्सन विधि का एक प्रकार है, जो हॉर्नर के नियम के अनुप्रयोग द्वारा हाथ की गणना के लिए अधिक कुशल रूप में होती है। 1970 के आसपास कंप्यूटर के सामान्य उपयोग में आने तक इसका व्यापक रूप से उपयोग किया जाता था।

बहुपद मूल्यांकन और दीर्घ विभाजन

बहुपद दिया है

$p(x)=\sum _{i=0}^{n}a_{i}x^{i}=a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\cdots +a_{n}x^{n},$

जहाँ $a_{0},\ldots ,a_{n}$ निरंतर गुणांक के रूप में होता है, समस्या $x_{0}$ के एक विशिष्ट मान $x.$पर बहुपद का मूल्यांकन करना है।

इसके लिए, अचरों के एक नए अनुक्रम का पुनरावर्तन संबंध इस प्रकार परिभाषित किया जाता है।

${\begin{aligned}b_{n}&:=a_{n}\\b_{n-1}&:=a_{n-1}+b_{n}x_{0}\\(1)\quad \quad \quad &~~~\vdots \\b_{1}&:=a_{1}+b_{2}x_{0}\\b_{0}&:=a_{0}+b_{1}x_{0}.\end{aligned}}$

तब $b_{0}$ का मूल्य $p(x_{0})$.है

यह देखने के लिए कि यह क्यों काम करता है, बहुपद के रूप में लिखा जा सकता है

$p(x)=a_{0}+x{\bigg (}a_{1}+x{\Big (}a_{2}+x{\big (}a_{3}+\cdots +x(a_{n-1}+x\,a_{n})\cdots {\big )}{\Big )}{\bigg )}\ .$

इस प्रकार, पुनरावृत्त रूप से $b_{i}$को प्रतिस्थापित करके अभिव्यक्ति इस प्रकार किया है,

${\begin{aligned}p(x_{0})&=a_{0}+x_{0}{\Big (}a_{1}+x_{0}{\big (}a_{2}+\cdots +x_{0}(a_{n-1}+b_{n}x_{0})\cdots {\big )}{\Big )}\\&=a_{0}+x_{0}{\Big (}a_{1}+x_{0}{\big (}a_{2}+\cdots +x_{0}b_{n-1}{\big )}{\Big )}\\&~~\vdots \\&=a_{0}+x_{0}b_{1}\\&=b_{0}.\end{aligned}}$

अब, यह सिद्ध किया जा सकता है कि

$(2)\quad \quad \quad p(x)=(b_{1}+b_{2}x+b_{3}x^{2}+b_{4}x^{3}+\cdots +b_{n-1}x^{n-2}+b_{n}x^{n-1})(x-x_{0})+b_{0}$

यह अभिव्यक्ति हॉर्नर के व्यावहारिक अनुप्रयोग का गठन करती है, क्योंकि यह परिणाम का निर्धारण करने का एक बहुत तेज़ विधि प्रदान करती है;

$p(x)/(x-x_{0})$

$b_{0}$ के साथ जो $p(x_{0})$ के बराबर है, जो कि विभाजन का शेषफल है, जैसा कि नीचे दिए गए उदाहरणों द्वारा प्रदर्शित होता है। यदि $x_{0}$ की रूट् $p(x)$ है, तब $b_{0}=0$ का मतलब शेष $0$ है, जिसका अर्थ है कि आप $p(x)$ को $x-x_{0}$.के रूप में गुणनखंडित कर सकते हैं।

लगातार $b$-मूल्य खोजने के लिए, आप $b_{n}$ निर्धारण के साथ प्रारंभ करते हैं, जो कि एक $a_{n}$के बराबर होता है। फिर आप सूत्र का उपयोग करके पुनरावर्ती रूप से कार्य करते हैं।

$b_{n-1}=a_{n-1}+b_{n}x_{0}$

जब तक आप $b_{0}$ पर नहीं पहुंच जाते हैं।

उदाहरण

मूल्यांकन करना $f(x)=2x^{3}-6x^{2}+2x-1$ के लिए $x=3$.

हम निम्नानुसार सिंथेटिक विभाजन का उपयोग करते हैं,

$x_{0}$│$x^{3}$ $x^{2}$ $x^{1}$ $x^{0}$3 │ 2 −6 2 −1

   │ 6 0 6
   └────────────────────────
       2 0 2 5

तीसरी पंक्ति की प्रविष्टियाँ पहले दो की प्रविष्टियों का योग हैं। दूसरी पंक्ति में प्रत्येक प्रविष्टि का उत्पाद $x$-मान है, इस उदाहरण में 3 तीसरी-पंक्ति प्रविष्टि के साथ तुरंत बाईं ओर होती है। पहली पंक्ति में प्रविष्टियाँ मूल्यांकन किए जाने वाले बहुपद के गुणांक हैं। तब $x-3$ से भाग देने पर $f(x)$ का शेषफल 5 होता है।

लेकिन बहुपद शेष प्रमेय द्वारा हम जानते हैं कि शेषफल $f(3)$ इस प्रकार $f(3)=5$ है

इस उदाहरण में, यदि $a_{3}=2,a_{2}=-6,a_{1}=2,a_{0}=-1$ हम देख सकते हैं कि $b_{3}=2,b_{2}=0,b_{1}=2,b_{0}=5$, तीसरी पंक्ति में प्रविष्टियाँ के रूप में होते है। अतः संश्लेषित विभाजन हॉर्नर विधि पर आधारित होती है।

बहुपद शेष प्रमेय के परिणाम के रूप में, तीसरी पंक्ति में प्रविष्टियां दूसरी घात बहुपद के गुणांक के रूप में होते है, और इसका भागफल $f(x)$ विभाजन $x-3$.पर शेष $5$ है यह हॉर्नर की विधि को बहुपद लंबे विभाजन के लिए उपयोगी बनाता है।

$x^{3}-6x^{2}+11x-6$ को $x-2$ से विभाजित करें

 2 │ 1 −6 11 −6
   │ 2 −8 6
   └────────────────────────
       1 −4 3 0

भागफल $x^{2}-4x+3$ है

माना $f_{1}(x)=4x^{4}-6x^{3}+3x-5$ और $f_{2}(x)=2x-1$, $f_{1}(x)$ को $f_{2}\,(x)$ से विभाजित करना है हॉर्नर की विधि का उपयोग करके।

  0.5 │ 4 -6 0 3 -5
      │ 2 -2 -1 1
      └───────────────────────
        2 -2 -1 1 -4

तीसरी पंक्ति पहली दो पंक्तियों का योग है, जिसे 2 से विभाजित किया गया है। दूसरी पंक्ति में प्रत्येक प्रविष्टि 1 का गुणनफल है और बाईं ओर तीसरी पंक्ति की प्रविष्टि उत्तर है

${\frac {f_{1}(x)}{f_{2}(x)}}=2x^{3}-2x^{2}-x+1-{\frac {4}{2x-1}}.$

दक्षता

घात के एकपद रूप का उपयोग करके मूल्यांकन $n$ बहुपद की अधिकतम आवश्यकता होती है $n$ अतिरिक्त और $(n^{2}+n)/2$ गुणन, यदि बार-बार गुणन द्वारा शक्तियों की गणना की जाती है और प्रत्येक एकपद का व्यक्तिगत रूप से मूल्यांकन किया जाता है। पुनरावृत्ति द्वारा $x$ की शक्तियों का मूल्यांकन करके लागत को $n$ जोड़ और $2n-1$ गुणा तक कम किया जा सकता है।

यदि संख्यात्मक डेटा अंकों या बिट्स के संदर्भ में प्रस्तुत किया जाता है, तो सहज कलन विधि भी $x$ के बिट्स की संख्या का लगभग $2n$ गुना स्टोर करने पर जोर देता है, मूल्यांकित बहुपद का परिमाण $x^{n}$अनुमानित है और किसी $x^{n}$को अपने आप में स्टोर करना चाहिए। इसके विपरीत, हॉर्नर की विधि को केवल $n$ जोड़ और $n$ गुणन की आवश्यकता होती है,और इसकी भंडारण आवश्यकताएं केवल $n$ के बिट्स की संख्या का केवल $x$ गुना होती हैं। वैकल्पिक रूप से, हॉर्नर की विधि की गणना $n$ फ़्यूज्ड गुणा-जोड़ों के साथ की जा सकती है। हॉर्नर की विधि को $kn$ योग और गुणन के साथ बहुपद के पहले $k$ डेरिवेटिव का मूल्यांकन करने के लिए भी बढ़ाया जा सकता है।

हॉर्नर की विधि इष्टतम रूप में होती है, इस अर्थ में किसी भी कलन विधि को यादृच्छिक ढंग से बहुपद का मूल्यांकन करने के लिए कम से कम कई परिचालनों का उपयोग करना चाहिए। अलेक्जेंडर ओस्ट्रोव्स्की ने 1954 में सिद्ध किया कि आवश्यक परिवर्धन की संख्या न्यूनतम रूप में होती है। विक्टर पैन ने 1966 में सिद्ध किया कि गुणन की संख्या न्यूनतम होती है। चूँकि, कब $x$ एक मैट्रिक्स के रूप में होता है, बहुपद मूल्यांकन हॉर्नर की विधि इष्टतम रूप में नहीं होती है।

यह मानता है कि बहुपद का मूल्यांकन एकपद रूप में किया जाता है और प्रतिनिधित्व की कोई पूर्व शर्त की अनुमति नहीं होती है, जो समझ में आता है कि बहुपद का मूल्यांकन केवल एक बार किया जाता है। चूंकि, यदि पूर्व शर्त की अनुमति होती है और बहुपद का कई बार मूल्यांकन किया जाता है, तो तेज़ कलन विधि संभव हैं। उनमें बहुपद के प्रतिनिधित्व का परिवर्तन सम्मलित है। सामान्यतः, एक घात -$n$ बहुपद का मूल्यांकन केवल ⌊n/2⌋+2 गुणा और $n$ जोड़ का उपयोग करके किया जा सकता है।

समानांतर मूल्यांकन

See also: एस्ट्रिन की योजना

हॉर्नर के नियम का एक नुकसान यह है कि सभी ऑपरेशन डेटा पर निर्भर होते है, इसलिए आधुनिक कंप्यूटरों पर निर्देश स्तर की समानता का लाभ उठाना संभव नहीं होता है। अधिकांश अनुप्रयोगों में जहां बहुपद मूल्यांकन की दक्षता मायने रखती है, कई निम्न-क्रम वाले बहुपदों का एक साथ मूल्यांकन किया जाता है, कंप्यूटर ग्राफिक्स में प्रत्येक पिक्सेल या बहुभुज के लिए या प्रत्येक ग्रिड वर्ग के लिए एक संख्यात्मक सिमुलेशन के रूप में होता है, इसलिए एकल बहुपद मूल्यांकन के भीतर समानता खोजना आवश्यक नहीं है।

चूंकि, यदि कोई बहुत उच्च क्रम के एकल बहुपद का मूल्यांकन कर रहा है, तो इसे निम्न प्रकार से विभाजित किया सकता है,

${\begin{aligned}p(x)&=\sum _{i=0}^{n}a_{i}x^{i}\\&=a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\cdots +a_{n}x^{n}\\&=\left(a_{0}+a_{2}x^{2}+a_{4}x^{4}+\cdots \right)+\left(a_{1}x+a_{3}x^{3}+a_{5}x^{5}+\cdots \right)\\&=\left(a_{0}+a_{2}x^{2}+a_{4}x^{4}+\cdots \right)+x\left(a_{1}+a_{3}x^{2}+a_{5}x^{4}+\cdots \right)\\&=\sum _{i=0}^{\lfloor n/2\rfloor }a_{2i}x^{2i}+x\sum _{i=0}^{\lfloor n/2\rfloor }a_{2i+1}x^{2i}\\&=p_{0}(x^{2})+xp_{1}(x^{2}).\\\end{aligned}}$

अधिक सामान्यतः, योग को k भागों में विभाजित किया जा सकता है

${\begin{aligned}p(x)&=\sum _{i=0}^{n}a_{i}x^{i}\\&=\sum _{j=0}^{k-1}x^{j}\sum _{i=0}^{\lfloor n/k\rfloor }a_{ki+j}x^{ki}\\&=\sum _{j=0}^{k-1}x^{j}p_{j}(x^{k})\\\end{aligned}}$

जहां हॉर्नर की विधि के अलग-अलग समानांतर उदाहरणों का उपयोग करके आंतरिक योग का मूल्यांकन किया जा सकता है। इसके लिए मूल हॉर्नर विधि की तुलना में थोड़े अधिक संचालन की आवश्यकता होती है, लेकिन उनमें से अधिकांश के के-वे सिमड निष्पादन की अनुमति देता है। आधुनिक संकलक सामान्यतः इस तरह से बहुपदों का मूल्यांकन करते हैं, जब फायदेमंद होता है, चूंकि फ्लोटिंग-पॉइंट गणनाओं के लिए इसके लिए असुरक्षित पुनर्संरचनात्मक गणित को सक्षम करने की आवश्यकता होती है।.

फ़्लोटिंग-पॉइंट गुणा और भाग के लिए आवेदन

Main article: गुणन कलन विधि शिफ्ट और जोड़ें

हॉर्नर की विधि बिना किसी बाइनरी गुणक वाले माइक्रोकंट्रोलर पर बाइनरी संख्याओं के गुणन और विभाजन के लिए एक तेज़, कोड-कुशल विधि के रूप में होती है। गुणा की जाने वाली द्विआधारी संख्याओं में से एक को तुच्छ बहुपद के रूप में दर्शाया गया है, जहाँ उपरोक्त संकेतन का उपयोग करके $a_{i}=1$, और $x=2$. फिर, x या x से कुछ शक्ति को बार-बार फैक्टर आउट किया जाता है। इस बाइनरी अंक प्रणाली आधार 2 में, $x=2$, इसलिए 2 की घातें बार-बार फ़ैक्टर आउट की जाती हैं।

उदाहरण

उदाहरण के लिए, दो संख्याओं (0.15625) और m का गुणनफल ज्ञात करने के लिए हैं

${\begin{aligned}(0.15625)m&=(0.00101_{b})m=(2^{-3}+2^{-5})m=(2^{-3})m+(2^{-5})m\\&=2^{-3}(m+(2^{-2})m)=2^{-3}(m+2^{-2}(m)).\end{aligned}}$

तरीका

दो बाइनरी नंबरों d और m का गुणनफल ज्ञात करने के लिए इस प्रकार किया है

1. इंटरमीडिएट परिणाम रखने वाले एक रजिस्टर को डी में प्रारंभ किया जाता है।

2. मीटर में कम से कम महत्वपूर्ण दाहिनी ओर गैर-शून्य बिट से प्रारंभ करते है।

2बी। गिनती बाईं ओर अगले सबसे महत्वपूर्ण गैर-शून्य बिट के लिए बिट पदों की संख्या के रूप में होती है। यदि अधिक महत्वपूर्ण बिट नहीं होती है, तो वर्तमान बिट स्थिति का मान लेते है।

2सी। उस मान का उपयोग करते हुए, इंटरमीडिएट परिणाम रखने वाले रजिस्टर पर बिट्स की संख्या से बाएं-शिफ्ट ऑपरेशन प्रारंभ करते है।

3. यदि सभी गैर-शून्य बिट्स गिने जाते हैं, तो मध्यवर्ती परिणाम रजिस्टर अब अंतिम परिणाम रखता है। अन्यथा, मध्यवर्ती परिणाम में d जोड़ें और m में अगले सबसे महत्वपूर्ण बिट के साथ चरण 2 में जारी रखते है।

व्युत्पत्ति

सामान्यतः , बिट वैल्यू वाले बाइनरी नंबर के लिए ($d_{3}d_{2}d_{1}d_{0}$) उत्पाद है

$(d_{3}2^{3}+d_{2}2^{2}+d_{1}2^{1}+d_{0}2^{0})m=d_{3}2^{3}m+d_{2}2^{2}m+d_{1}2^{1}m+d_{0}2^{0}m.$

कलन विधि में इस स्तर पर, यह आवश्यक है कि शून्य-मूल्य वाले गुणांक वाले पदों को हटा दिया जाए, जिससे कि केवल एक के बराबर द्विआधारी गुणांक की गणना की जा सके, इस प्रकार शून्य से गुणा या विभाजन की समस्या कोई समस्या नहीं है, इस निहितार्थ के बावजूद कारक समीकरण के रूप में होते है

$=d_{0}\left(m+2{\frac {d_{1}}{d_{0}}}\left(m+2{\frac {d_{2}}{d_{1}}}\left(m+2{\frac {d_{3}}{d_{2}}}(m)\right)\right)\right).$

हर सभी बराबर एक या शब्द अनुपस्थित है, तो यह कम हो जाता है

$=d_{0}(m+2{d_{1}}(m+2{d_{2}}(m+2{d_{3}}(m)))),$

या समकक्ष ऊपर वर्णित विधि के अनुरूप होते है

$=d_{3}(m+2^{-1}{d_{2}}(m+2^{-1}{d_{1}}(m+{d_{0}}(m)))).$

बाइनरी बेस -2 गणित में, 2 की शक्ति से गुणा केवल एक अंकगणितीय शिफ्ट ऑपरेशन के रूप में होते है। इस प्रकार, 2 से गुणा करने पर आधार-2 में एक अंकगणितीय शिफ्ट द्वारा गणना की जाती है। कारक (2⁻¹) एक सही अंकगणितीय बदलाव है, a (0) के परिणामस्वरूप कोई संक्रिया नहीं होती 2⁰ = 1 के बाद से गुणात्मक पहचान तत्व है और एक (2¹) का परिणाम बाएं अंकगणितीय बदलाव में होता है। गुणन गुणनफल अब केवल अंकगणितीय पारी संचालन जोड़ और घटाव का उपयोग करके जल्दी से गणना की जा सकती है।

एकल-निर्देश शिफ्ट-एंड-एडिशन-संचय का समर्थन करने वाले प्रोसेसर पर विधि विशेष रूप से तेज़ है, सी फ्लोटिंग-पॉइंट लाइब्रेरी की तुलना में,

हॉर्नर की विधि कुछ यथार्थ ता का त्याग करती है, चूंकि यह नाममात्र रूप से 13 गुना तेज है, 16 गुना तेज जब कैनोनिकल हस्ताक्षरित अंक सीएसडी फॉर्म का उपयोग किया जाता है और कोड स्थान का केवल 20% उपयोग करता है।

अन्य अनुप्रयोग

हॉर्नर की विधि का उपयोग विभिन्न स्थितीय अंक प्रणालियों के बीच रूपांतरण के लिए किया जा सकता है, इस स्थिति में x संख्या प्रणाली का आधार है और a_i गुणांक किसी दिए गए नंबर के बेस-एक्स प्रतिनिधित्व के अंक हैं और इसका उपयोग तब भी किया जा सकता है जब एक्स एक मैट्रिक्स (गणित) के रूप में होता है, इस स्थिति में कम्प्यूटेशनल दक्षता में लाभ और भी अधिक है। चूँकि, ऐसे स्थितियों के लिए बहुपद मूल्यांकन के लिए तेज़ तरीके ज्ञात हैं।।

बहुपद रूट् ढूँढना

न्यूटन की विधि के संयोजन में दीर्घ विभाजन कलन विधि का उपयोग करके, बहुपद की वास्तविक रूट्स का अनुमान लगाना संभव होता है। यह कलन विधि इस प्रकार काम करता है। एक बहुपद $p_{n}(x)$दिया घात का $n$ शून्य के साथ $z_{n}<z_{n-1}<\cdots <z_{1},$ कुछ प्रारंभिक अनुमान लगाएं $x_{0}$ ऐसा है कि $z_{1}<x_{0}$. अब निम्नलिखित दो चरणों को दोहराता है,.

1. न्यूटन की विधि का उपयोग करते हुए, अनुमान $x_{0}$ का उपयोग करके $p_{n}(x)$ का सबसे बड़ा शून्य $z_{1}$ ज्ञात करते है
2. हॉर्नर की विधि का उपयोग करके $p_{n-1}$ प्राप्त करने के लिए $(x-z_{1})$ को विभाजित करते है, चरण 1 पर लौटते है लेकिन बहुपद $p_{n-1}$ और प्रारंभिक अनुमान $z_{1}$.का उपयोग करते है

इन दो चरणों को तब तक दोहराया जाता है जब तक कि बहुपद के लिए सभी वास्तविक शून्य नहीं मिल जाते। यदि अनुमानित शून्य पर्याप्त यथार्थ रूप में नहीं होते है, तो प्राप्त मूल्यों को न्यूटन की विधि के लिए प्रारंभिक अनुमानों के रूप में उपयोग किया जा सकता है, लेकिन कम बहुपदों के अतिरिक्त पूर्ण बहुपद का उपयोग किया जा सकता है।

उदाहरण

File:HornerandNewton.gif

हॉर्नर की विधि का उपयोग करते हुए बहुपद मूल खोज

बहुपद पर विचार करें

$p_{6}(x)=(x+8)(x+5)(x+3)(x-2)(x-3)(x-7)$

जिसे बढ़ाया जा सकता है

$p_{6}(x)=x^{6}+4x^{5}-72x^{4}-214x^{3}+1127x^{2}+1602x-5040.$

ऊपर से हम जानते हैं कि इस बहुपद का सबसे बड़ा मूल 7 है इसलिए हम 8 का प्रारंभिक अनुमान लगाने में सक्षम हैं। न्यूटन की विधि का उपयोग करके 7 का पहला शून्य पाया जाता है जैसा कि दाईं ओर की आकृति में काले रंग में दिखाया गया है। अगला $p(x)$ से विभाजित है $(x-7)$ प्राप्त करने के लिए

$p_{5}(x)=x^{5}+11x^{4}+5x^{3}-179x^{2}-126x+720$

जो दाईं ओर की आकृति में लाल रंग से खींचा गया है। 7 के प्रारंभिक अनुमान के साथ इस बहुपद का सबसे बड़ा शून्य खोजने के लिए न्यूटन की विधि का उपयोग किया जाता है। इस बहुपद का सबसे बड़ा शून्य जो मूल बहुपद के दूसरे सबसे बड़े शून्य से मेल खाता है, 3 पर पाया जाता है और लाल रंग में घेरा जाता है। घात 5 बहुपद अब से विभाजित है $(x-3)$ प्राप्त करने के लिए

$p_{4}(x)=x^{4}+14x^{3}+47x^{2}-38x-240$

जो पीले रंग में दिखाया गया है। न्यूटन की विधि का उपयोग करके इस बहुपद के लिए शून्य फिर से 2 पर पाया जाता है और पीले रंग में घेरा जाता है। प्राप्त करने के लिए हॉर्नर विधि का उपयोग किया जाता है

$p_{3}(x)=x^{3}+16x^{2}+79x+120$

जो हरे रंग में दिखाया गया है और -3 पर शून्य पाया गया है। इस बहुपद को और घटाया जाता है

$p_{2}(x)=x^{2}+13x+40$

जो नीले रंग में दिखाया गया है और -5 का शून्य देता है। न्यूटन की विधि के प्रारंभिक अनुमान के रूप में अंतिम शून्य का उपयोग करके या घटाकर मूल बहुपद का अंतिम मूल पाया जा सकता है $p_{2}(x)$ और रैखिक समीकरण को हल करना। जैसा कि देखा जा सकता है, -8, -5, -3, 2, 3 और 7 की अपेक्षित जड़ें पाई गईं।

एक बहुपद का विभाजित अंतर

विभाजित अंतर की गणना करने के लिए हॉर्नर की विधि को संशोधित किया जा सकता है $(p(y)-p(x))/(y-x).$ बहुपद को देखते हुए (पहले की तरह)

$p(x)=\sum _{i=0}^{n}a_{i}x^{i}=a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\cdots +a_{n}x^{n},$

निम्नलिखित के रूप में आगे बढ़ें

${\begin{aligned}b_{n}&=a_{n},&\quad d_{n}&=b_{n},\\b_{n-1}&=a_{n-1}+b_{n}x,&\quad d_{n-1}&=b_{n-1}+d_{n}y,\\&{}\ \ \vdots &\quad &{}\ \ \vdots \\b_{1}&=a_{1}+b_{2}x,&\quad d_{1}&=b_{1}+d_{2}y,\\b_{0}&=a_{0}+b_{1}x.\end{aligned}}$

पूरा होने पर, हमारे पास है

${\begin{aligned}p(x)&=b_{0},\\{\frac {p(y)-p(x)}{y-x}}&=d_{1},\\p(y)&=b_{0}+(y-x)d_{1}.\end{aligned}}$

विभाजित अंतर की यह गणना कम के अधीन है मूल्यांकन की तुलना में राउंड-ऑफ़ त्रुटि $p(x)$ और $p(y)$ अलग से, विशेष रूप से जब $x\approx y$. स्थानापन्न $y=x$ इस विधि में देता है $d_{1}=p'(x)$, का व्युत्पन्न $p(x)$.

इतिहास

File:Qingjiushaoquad1.GIF

द्विघात बहुपद समीकरण को हल करने के लिए जे आईयू में क्यू कम का एल्गोरिथ्म$-x^{4}+763200x^{2}-40642560000=0$
नतीजा: x=840

निरंतर सन्निकटन द्वारा सभी आदेशों के संख्यात्मक समीकरणों को हल करने की एक नई विधि शीर्षक वाला हॉर्नर का पेपर, 1 जुलाई 1819 को रॉयल सोसाइटी ऑफ लंदन की बैठक में 1823 में अगली कड़ी के साथ पढ़ा गया था। 1819 के लिए लंदन की रॉयल सोसाइटी के दार्शनिक लेनदेन के भाग II में हॉर्नर के पेपर का अप्रैल, 1820 के द मंथली रिव्यू या लिटरेरी जर्नल के अंक में एक समीक्षक स्थायी डेड लिंक द्वारा गर्मजोशी और विस्तार से स्वागत किया गया था; इसकी तुलना में चार्ल्स बैबेज के एक तकनीकी पेपर को इस समीक्षा में स्पष्ट रूप से खारिज कर दिया गया है। सितंबर, 1821 के लिए द मंथली रिव्यू में समीक्षाओं का क्रम यह निष्कर्ष निकालता है कि होल्डर संख्यात्मक समीकरणों के प्रत्यक्ष और सामान्य व्यावहारिक समाधान की खोज करने वाले पहले व्यक्ति थे। फुलर दिखाया कि हॉर्नर के 1819 के पेपर की विधि बाद की विधि" के रूप में जानी जाने वाली पेपर विधि से भिन्न है और इसके परिणामस्वरूप इस पद्धति की प्राथमिकता होल्ड्रेड (1820) को मिलनी चाहिए थी।

अपने अंग्रेजी समकालीनों के विपरीत, हॉर्नर ने महाद्वीपीय साहित्य पर विशेष रूप से लुइस फ्रांकोइस एंटोनी अर्बोगैस्ट के काम को आकर्षित किया। हॉर्नर को बीजगणित पर जॉन बोनीकैसल की पुस्तक का गहन अध्ययन करने के लिए भी जाना जाता है, चूंकि उन्होंने पाओलो रफिनी (गणितज्ञ) के काम की उपेक्षा की थी।

चूँकि, हॉर्नर को इस विधि को सुलभ और व्यावहारिक बनाने का श्रेय दिया जाता है, लेकिन यह हॉर्नर से बहुत पहले से जाना जाता था। रिवर्स कालानुक्रमिक क्रम में हॉर्नर की विधि पहले से ही ज्ञात थी

• 1809 में पाओलो रफ़िनी (गणितज्ञ) रुफ़िनी का नियम देखें
• आइजैक न्यूटन ने 1669 में
• 14वीं शताब्दी में चीनी गणित मिस जेड टाइगर के रूप में थे
• 13वीं शताब्दी में चीनी गणित किन जियुशाओ ने अपने गणितीय ग्रंथ नौ खंडों में प्रस्तुत किया था
• फारसी लोग मध्यकालीन इस्लाम में गणित शराफ अल-दीन अल-यूसी 12वीं शताब्दी में घन समीकरण के सामान्य स्थिति में उस पद्धति का उपयोग करने वाले पहले व्यक्ति के रूप में थे
• 11वीं शताब्दी में चीनी गणितज्ञ जे आइए एक्स इयान सांग राजवंश के रूप में थे
• गणितीय कला पर नौ अध्याय, हान राजवंश की एक चीनी कृति 202 ईसा पूर्व - 220 ईस्वी, तीसरी शताब्दी में लियू हुई फ़्ल द्वारा संपादित हुई है।किन जिउशाओ, अपने शू शू जिउ झांग मैथमेटिकल ट्रीटिस इन नाइन सेक्शन्स, 1247 में बहुपद समीकरणों को हल करने के लिए हॉर्नर प्रकार के विधि का एक पोर्टफोलियो प्रस्तुत करता है, जो 11 वीं शताब्दी के सांग वंश के गणितज्ञ जिया जियान के पहले के कार्यों पर आधारित था, उदाहरण के लिए एक विधि बाय-क्विंटिक्स के अनुकूल विशेष रूप से है, जिसमें से केस स्टडीज के तत्कालीन चीनी रिवाज को ध्यान में रखते हुए किन एक उदाहरण देता है। चीन और जापान में गणित के विकास में योशियो मिकामी लीपज़िग 1913 ने लिखा गया है।

  यूरोप की तुलना में कम से कम छह लंबी शताब्दियों पहले चीन में हॉर्नर की शानदार प्रक्रिया का उपयोग करने के तथ्य से कौन इंकार कर सकता है, हम निश्चित रूप से किसी भी तरह से हॉर्नर के आविष्कार को चीनी मूल के रूप में वर्णित करने का इरादा नहीं रखते हैं, लेकिन समय की कमी पर्याप्त रूप से बनाती है यह पूरी तरह से असंभव नहीं था कि यूरोपीय लोग प्रत्यक्ष या अप्रत्यक्ष रूप से चीनी पद्धति के बारे में जान सकते थे

उलरिच लिब्रेब्रेच ने निष्कर्ष निकाला यह स्पष्ट है कि यह प्रक्रिया एक चीनी आविष्कार के रूप में है, यह विधि भारत में ज्ञात नहीं थी। उन्होंने कहा, फिबोनाची ने संभवतः इसके बारे में अरबों से सीखा, जिन्होंने संभवतः चीनियों से उधार लिया था। जिउ झांग सुआन शू में समस्या IV.16 और 22 के संबंध में समान रेखाओं के साथ वर्ग और घन रूट्स की निकासी पर पहले से ही लियू हुई द्वारा चर्चा की गई है, जबकि 7 वीं शताब्दी में वांग शियाओतोंग का मानना ​​​​है कि उनके पाठक क्यूबिक्स को उनके द्वारा वर्णित एक सन्निकटन विधि द्वारा हल कर सकते हैं। उनकी किताब जिगू सुंजिंग में दिखाया गया है

यह भी देखें

• चेबिशेव रूप में बहुपदों का मूल्यांकन करने के लिए क्लेंशॉ कलन विधि का प्रयोग करते है
• बी-पट्टी फॉर्म में तख़्ता वक्र का मूल्यांकन करने के लिए डी बूर का कलन विधि का प्रयोग करते है
• बेज़ियर रूप में बहुपदों का मूल्यांकन करने के लिए डी कैस्टेलजौ का कलन विधि का प्रयोग करते है
• एस्ट्रिन की योजना आधुनिक कंप्यूटर आर्किटेक्चर पर समानांतरकरण की सुविधा के रूप में होता है
• लील की विधि से रूट्स का रेखांकन किया जा सकता है
• रफ़िनी का नियम और सिंथेटिक विभाजन एक बहुपद को x - r के रूप में एक द्विपद से विभाजित करने के लिए करते है

संदर्भ

• Berggren, J. L. (1990). "Innovation and Tradition in Sharaf al-Din al-Tusi's Muadalat". Journal of the American Oriental Society. 110 (2): 304–309. doi:10.2307/604533. JSTOR 604533.
• Cajori, Florian (1911). "Horner's method of approximation anticipated by Ruffini". Bulletin of the American Mathematical Society. 17 (8): 409–414. doi:10.1090/s0002-9904-1911-02072-9. Read before the Southwestern Section of the American Mathematical Society on November 26, 1910.
• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein10.1016/0315-0860(81)90069-0, Clifford (2009). "Introduction to Algorithms". Historia Mathematica (3rd ed.). MIT Press. 8 (3): 277–318. doi:10.1016/0315-0860(81)90069-0.
• Fateman, R. J.; Kahan, W. (2000). Improving exact integrals from symbolic algebra systems (PDF) (Report). PAM. University of California, Berkeley: Center for Pure and Applied Mathematics. Archived from the original (PDF) on 2017-08-14. Retrieved 2018-05-17.
• Fuller, A. T. (1999). "Horner versus Holdred: An Episode in the History of Root Computation". Historia Mathematica. 26: 29–51. doi:10.1006/hmat.1998.2214.
• Higham, Nicholas (2002). Accuracy and Stability of Numerical Algorithms. SIAM. ISBN 978-0-89871-521-7.
• Holdred, T. (1820). A New Method of Solving Equations with Ease and Expedition; by which the True Value of the Unknown Quantity is Found Without Previous Reduction. With a Supplement, Containing Two Other Methods of Solving Equations, Derived from the Same Principle (PDF). Richard Watts. Archived from the original (PDF) on 2014-01-06. Retrieved 2012-12-10.

  Holdred's method is in the supplement following page numbered 45 (which is the 52nd page of the pdf version).

• Horner, William George (July 1819). "A new method of solving numerical equations of all orders, by continuous approximation". Philosophical Transactions. Royal Society of London. 109: 308–335. doi:10.1098/rstl.1819.0023. JSTOR 107508. S2CID 186210512.

  Directly available online via the link, but also reprinted with appraisal in D.E. Smith: A Source Book in Mathematics, McGraw-Hill, 1929; Dover reprint, 2 vols, 1959.

• Knuth, Donald (1997). The Art of Computer Programming. Vol. 2: Seminumerical Algorithms (3rd ed.). Addison-Wesley. pp. 486–488 in section 4.6.4. ISBN 978-0-201-89684-8.
• Kress, Rainer (1991). Numerical Analysis. Springer.
• Kripasagar, Venkat (March 2008). "Efficient Micro Mathematics – Multiplication and Division Techniques for MCUs". Circuit Cellar Magazine (212).
• Libbrecht, Ulrich (2005). "Chapter 13". Chinese Mathematics in the Thirteenth Century (2nd ed.). Dover. ISBN 978-0-486-44619-6. Archived from the original on 2017-06-06. Retrieved 2016-08-23.
• Mikami, Yoshio (1913). "Chapter 11. Ch'in Chiu-Shao". The Development of Mathematics in China and Japan (1st ed.). Chelsea Publishing Co reprint. pp. 74–77.
• Ostrowski, Alexander M. (1954). "On two problems in abstract algebra connected with Horner's rule". Studies in Mathematics and Mechanics presented to Richard von Mises. Academic Press. pp. 40–48. ISBN 978-1-4832-3272-0.
• Pan, Y. Ja (1966). "On means of calculating values of polynomials". Russian Math. Surveys. 21: 105–136. doi:10.1070/rm1966v021n01abeh004147. S2CID 250869179.
• Pankiewicz, W. (1968). "Algorithm 337: calculation of a polynomial and its derivative values by Horner scheme". Communications of the ACM. ACM. 11 (9): 633. doi:10.1145/364063.364089. S2CID 52859619.
• Spiegel, Murray R. (1956). Schaum's Outline of Theory and Problems of College Algebra. McGraw-Hill.
• Temple, Robert (1986). The Genius of China: 3,000 Years of Science, Discovery, and Invention. Simon and Schuster. ISBN 978-0-671-62028-8.
• Whittaker, E.T.; Robinson, G. (1924). The Calculus of Observations. London: Blackie.
• Wylie, Alexander (1897). "Jottings on the Science of Chinese Arithmetic". Chinese Researches. Shanghai. pp. 159–194.{{cite book}}: CS1 maint: location missing publisher (link)

  Reprinted from issues of The North China Herald (1852).

बाहरी संबंध

• "Horner scheme", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
• Qiu Jin-Shao, Shu Shu Jiu Zhang (Cong Shu Ji Cheng ed.)
• For more on the root-finding application see [1]