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

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

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

${\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) तीसरी-पंक्ति प्रविष्टि के साथ तुरंत बाईं ओर। पहली पंक्ति में प्रविष्टियाँ मूल्यांकन किए जाने वाले बहुपद के गुणांक हैं। फिर शेष $f(x)$ विभाजन पर $x-3$ 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$ गुणा, शक्तियों की गणना बार-बार गुणा करके की जाती है और प्रत्येक मोनोमियल का व्यक्तिगत रूप से मूल्यांकन किया जाता है। लागत को कम किया जा सकता है $n$ अतिरिक्त और $2n-1$ की शक्तियों का मूल्यांकन करके गुणा $x$ पुनरावृत्ति द्वारा। अंकों (या बिट्स) के संदर्भ में संख्यात्मक डेटा का प्रतिनिधित्व किया जाता है, फिर भोली कलन विधि भी लगभग भंडारण पर जोर देता है $2n$ के बिट्स की संख्या का गुना $x$: मूल्यांकित बहुपद का परिमाण अनुमानित है $x^{n}$, और एक को स्टोर भी करना चाहिए $x^{n}$ अपने आप। इसके विपरीत, हॉर्नर की विधि को केवल आवश्यकता होती है $n$ अतिरिक्त और $n$ गुणन, और इसकी भंडारण आवश्यकताएं केवल हैं $n$ के बिट्स की संख्या का गुना $x$. वैकल्पिक रूप से, हॉर्नर की विधि की गणना की जा सकती है $n$ फ़्यूज्ड मल्टीप्लाई-जोड़ता है। पहले का मूल्यांकन करने के लिए हॉर्नर की विधि को भी बढ़ाया जा सकता है $k$ के साथ बहुपद के डेरिवेटिव $kn$ जोड़ और गुणा। हॉर्नर की विधि इष्टतम है, इस अर्थ में कि किसी भी एल्गोरिदम को मनमाने ढंग से बहुपद का मूल्यांकन करने के लिए कम से कम कई परिचालनों का उपयोग करना चाहिए। अलेक्जेंडर ओस्ट्रोव्स्की ने 1954 में सिद्ध किया कि आवश्यक परिवर्धन की संख्या न्यूनतम है। विक्टर पैन ने 1966 में सिद्ध किया कि गुणन की संख्या न्यूनतम है। चूँकि , कब $x$ एक मैट्रिक्स है, बहुपद मूल्यांकन#मैट्रिक्स बहुपद|हॉर्नर की विधि इष्टतम नहीं है।

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

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

See also: Estrin's scheme

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

चूंकि , यदि कोई बहुत उच्च क्रम के एकल बहुपद का मूल्यांकन कर रहा है, तो इसे निम्न प्रकार से तोड़ना उपयोगी हो सकता है:

${\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}}$

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

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

Main article: multiplication algorithm § Shift and add

हॉर्नर की विधि बिना किसी बाइनरी गुणक वाले microcontroller पर बाइनरी संख्याओं के गुणन और विभाजन के लिए एक तेज़, कोड-कुशल विधि है। गुणा की जाने वाली द्विआधारी संख्याओं में से एक को तुच्छ बहुपद के रूप में दर्शाया गया है, जहाँ (उपरोक्त संकेतन का उपयोग करके) $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. न्यूटन की विधि का उपयोग करते हुए, सबसे बड़ा शून्य ज्ञात कीजिए $z_{1}$ का $p_{n}(x)$ अनुमान का उपयोग करना $x_{0}$.
2. हॉर्नर की विधि का उपयोग करके विभाजित करें $(x-z_{1})$ प्राप्त करने के लिए $p_{n-1}$. चरण 1 पर लौटें लेकिन बहुपद का प्रयोग करें $p_{n-1}$ और प्रारंभिक अनुमान $z_{1}$.

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

उदाहरण

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

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

$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)$.

इतिहास

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

हॉर्नर का पेपर, निरंतर सन्निकटन द्वारा, सभी आदेशों के संख्यात्मक समीकरणों को हल करने की एक नई विधि शीर्षक, 1 जुलाई, 1819 को लंदन की रॉयल सोसाइटी की बैठक में, 1823 में अगली कड़ी के साथ, पढ़ा गया था।1819 के लिए लंदन की रॉयल सोसाइटी के दार्शनिक लेन-देन के भाग II में हॉर्नर के पेपर का एक समीक्षक ने गर्मजोशी और विस्तार से स्वागत किया।{{Dead link|date=January 2020|bot=InternetArchiveBot|fix-attempted=yes}द मंथली रिव्यू: या, लिटरेरी जर्नल फॉर अप्रैल, 1820 के अंक में; इसकी तुलना में, चार्ल्स बैबेज के एक तकनीकी पेपर को इस समीक्षा में स्पष्ट रूप से खारिज कर दिया गया है। सितंबर, 1821 के लिए द मंथली रिव्यू में समीक्षाओं का क्रम यह निष्कर्ष निकालता है कि होल्डर संख्यात्मक समीकरणों के प्रत्यक्ष और सामान्य व्यावहारिक समाधान की खोज करने वाले पहले व्यक्ति थे। कपड़ा साफ करनेवाला दिखाया कि हॉर्नर के 1819 के पेपर में विधि बाद में हॉर्नर की विधि के रूप में जानी जाने वाली विधि से भिन्न है और इसके परिणामस्वरूप इस पद्धति की प्राथमिकता होल्ड्रेड (1820) को मिलनी चाहिए।

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

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

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

किन जिउशाओ, अपने शू शू जिउ झांग (नौ वर्गों में गणितीय ग्रंथ; 1247) में, बहुपद समीकरणों को हल करने के लिए हॉर्नर-प्रकार के तरीकों का एक पोर्टफोलियो प्रस्तुत करता है, जो 11 वीं शताब्दी के सांग वंश के गणितज्ञ जिया जियान के पहले के कार्यों पर आधारित था; उदाहरण के लिए, एक विधि विशेष रूप से बाय-क्विंटिक्स के अनुकूल है, जिसमें से केस स्टडीज के तत्कालीन चीनी रिवाज को ध्यान में रखते हुए किन एक उदाहरण देता है। चीन और जापान में गणित के विकास में योशियो मिकामी (लीपज़िग 1913) ने लिखा:

"... who can deny the fact of Horner's illustrious process being used in China at least nearly six long centuries earlier than in Europe ... We of course don't intend in any way to ascribe Horner's invention to a Chinese origin, but the lapse of time sufficiently makes it not altogether impossible that the Europeans could have known of the Chinese method in a direct or indirect way."

उलरिच लिब्रेब्रेच ने निष्कर्ष निकाला: यह स्पष्ट है कि यह प्रक्रिया एक चीनी आविष्कार है ... यह विधि भारत में ज्ञात नहीं थी। उन्होंने कहा, फिबोनाची ने संभवतः इसके बारे में अरबों से सीखा, जिन्होंने संभवतः चीनियों से उधार लिया था। जिउ झांग सुआन शू में समस्या 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]