बहुपद मूल्यांकन

गणित और कंप्यूटर विज्ञान में, बहुपद मूल्यांकन एक बहुपद के मूल्य की गणना को संदर्भित करता है तथा इसके अनिश्चित चर को कुछ मूल्यों के लिए प्रतिस्थापित किया जाता है। दूसरे शब्दों में, बहुपद के मूल्यांकन $P(x_{1},x_{2})=2x_{1}x_{2}+x_{1}^{3}+4$ पर $x_{1}=2,x_{2}=3$ को $P(2,3)=2\cdot 2\cdot 3+2^{3}+4=24.$ को कंप्यूटिंग में समिम्लित किया जाता है,तथा बहुपद वलय § बहुपद मूल्यांकन भी दर्शाया गया है

अविभाज्य बहुपद के मूल्यांकन के लिए $a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots +a_{0},$ सबसे सरल विधि का उपयोग करेंगे $n$ गुणन की गणना करने के लिए $a_{n}x^{n}$, का,तथा $n-1$ गुणन की गणना करने के लिए $a_{n-1}x^{n-1}$ उपयोग करेंगे और इसी तरह कुल मिलाकर ${\tfrac {n(n+1)}{2}}$ से गुणन करेंगेऔर $n$ को जोड़ देंगे।हॉर्नर के नियम जैसे बेहतर विधियों का उपयोग करके $n$ गुणन और $n$ जोड़ को न्यूनतम किया जा सकता है। यदि कुछ प्रीप्रोसेसिंग की अनुमति दी जाती है, तो और भी बचत संभव है।

पृष्ठभूमि

अभ्यास में यह समस्या सामान्यतःः उत्पन्न होती है। न्यूनतम्प्यूटेशनल ज्यामिति में, टेलर बहुपदों का उपयोग करके फ़ंक्शन सन्निकटन की गणना करने के लिए बहुपदों का उपयोग किया जाता है। क्रिप्टोग्राफी और हैश तालिका में, k-स्वतंत्र हैशिंग की गणना करने के लिए बहुपद का उपयोग किया जाता है।

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

सामान्य विधि

हॉर्नर का नियम

See also: हॉर्नर की विधि

हॉर्नर विधि बार-बार ब्रैकेटिंग का उपयोग करके बहुपद का मूल्यांकन करती है:

$${\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$ कर देती है ,

हॉर्नर विधि इतनी सामान्य है,कि कई कंप्यूटर प्रोसेसर में एक कंप्यूटर निर्देश गुणा-संचय ऑपरेशन जोड़ा गया है, जो एक संयुक्त चरण में जोड़ और गुणा ऑपरेशन करने की अनुमति देता है।

बहुभिन्नरूपी

यदि बहुपद बहुभिन्नरूपी है, तो हॉर्नर के नियम को चर के कुछ क्रम पर पुनरावर्ती रूप से प्रारंभ किया जा सकता है।

उदाहरण.

$P(x,y)=4+x+2xy+2x^{2}y+x^{2}y^{2}$

के रूप में लिखा जा सकता है

${\begin{aligned}P(x,y)&=4+x(1+y(2)+x(y(2+y)))\quad {\text{or}}\\P(x,y)&=4+x+y(x(2+x(2))+y(x^{2})).\end{aligned}}$

इस दृष्टिकोण का एक कुशल संस्करण कार्निसर और गैस्का द्वारा वर्णित किया गया था।

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

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

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

$${\begin{aligned}P(x)=(a_{0}+a_{1}x)+(a_{2}+a_{3}x)x^{2}+((a_{4}+a_{5}x)+(a_{6}+a_{7}x)x^{2})x^{4}.\end{aligned}}$$

वर्ग और घातांक द्वारा संयुक्त संगणना को समानांतर करने की अनुमति देता है।

प्रीप्रोसेसिंग के सापेक्ष मूल्यांकन

मनमाने बहुपदों का मूल्यांकन न्यूनतम के सापेक्ष किया जा सकता है अगर हम पहले प्रीप्रोसेस करते हैं तो हॉर्नर के नियम की सापेक्ष में संचालन की आवश्यकता होती है गुणांक $a_{n},\dots ,a_{0}$.

एक उदाहरण सबसे पहले मोट्ज़किन ने दिया था जिन्होंने यह नोट किया था

$P(x)=x^{4}+a_{3}x^{3}+a_{2}x^{2}+a_{1}x+a_{0}$

के रूप में लिखा जा सकता है

$y=(x+\beta _{0})x+\beta _{1},\quad P(x)=(y+x+\beta _{2})y+\beta _{3},$

जहां मान $\beta _{0},\dots ,\beta _{3}$ के आधार पर अग्रिम गणना की जाती है $a_{0},\dots ,a_{3}$.हॉर्नर के 4 के सापेक्ष में मोट्ज़किन की विधि केवल 3 गुणन का उपयोग करती है।

प्रत्येक के लिए मान $\beta _{i}$ विस्तार करके आसानी से परिकलित किया जा सकता है $P(x)$ और गुणांकों की समान करना:

${\begin{aligned}\beta _{0}&={\tfrac {1}{2}}(a_{3}-1),\quad &z&=a_{2}-\beta _{0}(\beta _{0}+1),\quad &\beta _{1}&=a_{1}-\beta _{0}z,\\\beta _{2}&=z-2\beta _{1},\quad &\beta _{3}&=a_{0}-\beta _{1}(\beta _{1}+\beta _{2}).\end{aligned}}$

उदाहरण

टेलर विस्तार की गणना करने के लिए $\exp(x)\approx 1+x+x^{2}/2+x^{3}/6+x^{4}/24$, हम एक कारक को 24 तक बढ़ा सकते हैं, उपरोक्त चरणों को प्रारंभ कर सकते हैं, और स्केल वापस कर सकते हैं।यह हमें तीन बार गुणन संगणना देता है

$y=(x+1.5)x+11.625,\quad P(x)=(y+x-15)y/24+2.63477.$

समतुल्य हॉर्नर फॉर्म में सुधार (यानी $P(x)=1+x(1+x(1/2+x(1/6+x/24)))$) 1 गुणन द्वारा।

कुछ सामान्य विधियों में नुथ-ईव एल्गोरिथम और राबिन-विनोग्राद एल्गोरिथम समिम्लित हैं।

बहु बिंदु मूल्यांकन

एक $n$-डिग्री बहुपद और $P(x)$ तथा कई बिंदुओं का मूल्यांकन $x_{1},\dots ,x_{m}$ से किया जा सकता है हॉर्नर विधि का उपयोग करके $mn$ का गुणन $m$ बार किया जाता हैं। प्रीप्रोसेसिंग दृष्टिकोण का उपरोक्त उपयोग करके, इसे दो के कारक से न्यूनतम, अर्थात $mn/2$ गुणन किया जा सकता है। यद्यपि , इससे बेहतर करना संभव है।

समय की आवश्यकता को $O{\big (}(n+m)\log ^{2}(n+m){\big )}$ न्यूनतम करना संभव है .वो सिद्धांत जो दो बहुपदों को परिभाषित करता है तथा जो क्रमशः पहले और दूसरे भाग में शून्य हैं:तथा$m_{0}(x)=(x-x_{1})\cdots (x-x_{n/2})$ और $m_{1}(x)=(x-x_{n/2+1})\cdots (x-x_{n})$.हम पुनः गणना करते हैं $R_{0}=P{\bmod {m}}_{0}$ और $R_{1}=P{\bmod {m}}_{1}$ बहुपद विभाजन का उपयोग करके, जो में किया जा सकता है $O(n\log n)$ एक तीव्र फूरियर रूपांतरण का उपयोग करते समय हुए था। इसका मतलब यह है $P(x)=Q(x)m_{0}(x)+R_{0}(x)$ और $P(x)=Q(x)m_{1}(x)+R_{1}(x)$ निर्माण द्वारा, जहाँ $R_{0}$ और $R_{1}$ अधिकतम डिग्री के बहुपद हैं $n/2$.जिसके कारण $m_{0}$ और $m_{1}$ परिभाषित किया गया था, और हमारे पास है

${\begin{aligned}R_{0}(x_{i})&=P(x_{i})\quad {\text{for }}i\leq n/2\quad {\text{and}}\\R_{1}(x_{i})&=P(x_{i})\quad {\text{for }}i>n/2.\end{aligned}}$

इस प्रकार गणना करने के लिए $P$ सब पर $n$ की $x_{i}$, यह छोटे बहुपदों की गणना करने के लिए पर्याप्त है $R_{0}$ और $R_{1}$ प्रत्येक आधे अंक पर। यह हमें एक फूट डालो और जीतो एल्गोरिथम देता है $T(n)=2T(n/2)+n\log n$, जो ये दर्शाता हे $T(n)=O(n(\log n)^{2})$ मास्टर प्रमेय (एल्गोरिदम का विश्लेषण) द्वारा।

ऐसे इस्थिति में जहां जिन बिंदुओं पर हम बहुपदों का मूल्यांकन करना चाहते हैं, उनकी कुछ संरचना है, सरल विधिया उपस्थित हैं। उदाहरण के लिए, नुथ खंड 4.6.4 प्रकार के बहुपद मानों को सारणीबद्ध करने के लिए एक विधि देता है

$P(x_{0}+h),P(x_{0}+2h),\dots .$

गतिशील मूल्यांकन

जहां स्थिति में $x_{1},\dots ,x_{m}$ पहले से ज्ञात नहीं हैं,केडलया और उमंस ने आकार में $F_{q}$ समय के अन्दर $(\log n)^{O(1)}(\log _{2}q)^{1+o(1)}$ कुछ प्रारंभिक प्रीप्रोसेसिंग के उपरांत प्रति मूल्यांकन के सीमित क्षेत्र में बहुपदों के मूल्यांकन के लिए एक डेटा संरचना प्रदान की ।यह कैस्पर ग्रीन लार्सन द्वारा अनिवार्य रूप से इष्टतम होना दर्शाया गया था ।

विचार रूपांतरित हो गया था $P(x)$ डिग्री $n$ के एक बहुभिन्नरूपी बहुपद में $f(x_{1},x_{2},\dots ,x_{m})$, ऐसा है कि $P(x)=f(x,x^{d},x^{d^{2}},\dots ,x^{d^{m}})$ और व्यक्तिगत डिग्री $f$ से $d$. अधिकतम है क्योंकी यह समाप्त हो गया है और ${\bmod {q}}$, सबसे बड़ा मूल्य $f$ ले (ओवर $\mathbb {Z} )$ ,${\displaystyle M=d^{m}(q-1)^{dm}}$ सकता है । चीनी शेष प्रमेय का उपयोग करना, यह मूल्यांकन करने के लिए पर्याप्त है $f$ मॉड्यूलो विभिन्न प्राइम्स $p_{1},\dots ,p_{\ell }$ एक उत्पाद के सापेक्ष न्यूनतम से न्यूनतम $M$. प्रत्येक अभाज्य को $\log M=O(dm\log q)$ मोटे तौर पर लिया जा सकता है , और आवश्यक अभाज्य संख्याओं की संख्या, $\ell$, लगभग समान है। इस प्रक्रिया को पुनरावर्ती रूप से करते हुए, हम अभाज्य संख्या जितनी छोटी संख्या $\log \log q$. प्राप्त कर सकते हैं इसका अर्थ है कि हम $f$ में सभी संभावित मूल्यों पर $T=(\log \log q)^{m}$ समय और स्थान के सापेक्ष गणना और स्टोर कर सकते हैं।अगर हम लेते हैं $d=\log q$, हम पाते हैं $m={\tfrac {\log n}{\log \log q}}$, इसलिए समय/स्थान की आवश्यकता $n^{\frac {\log \log q}{\log \log \log q}}.$ उचित है।

केदलया और उमंस आगे दिखाते हैं कि इस तीव्र प्रीप्रोसेसिंग को मल्टीपॉइंट मूल्यांकन के सापेक्ष कैसे जोड़ा जाए। यह बहुपद मॉड्यूलर रचना जैसे कई महत्वपूर्ण बीजगणितीय समस्याओं के लिए इष्टतम एल्गोरिदम की अनुमति देता है।

विशिष्ट बहुपद

जब सामान्य बहुपदों की आवश्यकता $\Omega (n)$ संचालन के मूल्यांकन करने के लिए होती है, कुछ बहुपदों की गणना बहुत तीव्रता से की जा सकती है।उदाहरण के लिए, बहुपद $P(x)=x^{2}+2x+1$ केवल एक गुणन और एक जोड़ का उपयोग करके गणना की जा सकती है क्योंकी $P(x)=(x+1)^{2}$ होता है

शक्तियों का मूल्यांकन

Main articles: वर्ग करके घातांक and जोड़-श्रृंखला घातांक

एक विशेष रूप से दिलचस्प प्रकार का बहुपद घात $x^{n}$ है .ऐसे बहुपदों की सदैव गणना $O(\log n)$ संचालन की जा सकती है।मान लीजिए, उदाहरण के लिए, हमें $x^{16}$ गणना करने की आवश्यकता है ; हम बस $x$ और गुणा करें $x$ प्राप्त करने $x^{2}$. के सापेक्ष प्रारंभ कर सकते हैं इसके उपरांत हम $x^{4}$से केवल चार गुणा में $x^{8}$ और $x^{16}$ को प्राप्त करने के लिए उसी से गुणा कर सकते हैं ।अन्य घातांक जैसे $x^{5}$ इसी तरह पहली कंप्यूटिंग द्वारा $x^{4}$ 2 गुणा करके और पुनः गुणा करके $x$. कुशलतापूर्वक गणना की जा सकती है।

किसी दी गई घातांक की गणना करने का सबसे कुशल विधि $x^{n}$ अतिरिक्त-श्रृंखला घातांक द्वारा प्रदान किया जाता है। यद्यपि , इसके लिए प्रत्येक प्रतिपादक के लिए एक विशिष्ट एल्गोरिदम प्रारूपित करने की आवश्यकता होती है, और इन एल्गोरिदम को प्रारूपित करने के लिए आवश्यक गणना कठिन होती है, इसलिए प्रभावी संगणनाओं के लिए सामान्यतःः पर वर्ग द्वारा घातांक को प्राथमिकता दी जाती है।

बहुपद परिवार

सामान्यतः बहुपद प्रसिद्ध रूप से $a_{n}x^{n}+\dots +a_{1}x+a_{0}$ भिन्न रूप में दिखाई देते हैं .चेबिशेव रूप में बहुपदों के लिए हम क्लेंशॉ एल्गोरिथम का उपयोग कर सकते हैं।बेजियर रूप में बहुपदों के लिए हम डी कास्टलजौ के एल्गोरिदम का उपयोग कर सकते हैं,और बी-स्प्लिंस के लिए डी बूर का एल्गोरिदम है।

कठिन बहुपद

तथ्य यह है कि कुछ बहुपदों की गणना सामान्य बहुपदों की सापेक्ष में काफी तीव्रता से की जा सकती है, यह प्रश्न सुझाता है: क्या हम एक साधारण बहुपद का उदाहरण दे सकते हैं जिसकी गणना इसकी डिग्री से बहुत न्यूनतम समय में नहीं की जा सकती है? वोल्कर स्ट्रास ने दर्शाया है कि बहुपद

$P(x)=\sum _{k=0}^{n}2^{2^{kn^{3}}}x^{k}$

से न्यूनतम के द्वारा ${\tfrac {1}{2}}n-2$ गुणन और $n-4$ जोड़ का मूल्यांकन नहीं किया जा सकता है ।न्यूनतम से न्यूनतम यह बाध्यता धारण करती है यदि केवल $<n^{2}/\log n$. प्रकार के संचालन की अनुमति दी जाती है, जो लंबाई की तथाकथित बहुपद श्रृंखला को जन्म देती है

स्ट्रैसन द्वारा दिए गए बहुपद में बहुत बड़े गुणांक हैं, परंतु संभाव्य विधियों से कि केवल 0 और 1 के गुणांक वाले बहुपदों का अस्तित्व होना चाहिए, जो कोई भी दर्शा सकता है जैसे कि मूल्यांकन के लिए न्यूनतम से न्यूनतम आवश्यकता होती है $\Omega (n/\log n)$ गुणन की।

अन्य साधारण बहुपदों के लिए, जटिलता अज्ञात है।बहुपद $(x+1)(x+2)\cdots (x+n)$ समय $(\log n)^{c}$ किसी के लिए $c$. पर गणना करने योग्य नहीं होने का अनुमान है यह इस तथ्य से समर्थित है, कि यदि इसकी तीव्रता से गणना की जा सकती है, तो RSA (क्रिप्टोसिस्टम) को तोड़ते हुए बहुपद समय में पूर्णांक गुणनखंड की गणना की जा सकती है।

मैट्रिक्स बहुपद

कभी-कभी अदिश गुणन की न्यूनतम कम्प्यूटेशनल लागत (जैसे $ax$)गैर अदिश गुणन की न्यूनतम कम्प्यूटेशनल लागत से न्यूनतम है (जैसे $x^{2}$).इसका विशिष्ट उदाहरण मैट्रिसेस है। $M$ एक $m\times m$ मैट्रिक्स में, एक अदिश गुणन लगभग $aM$ और $m^{2}$ गणना करते समय $M^{2}$ अंकगणितीय संचालन लगभग $m^{3}$लगते हैं

उदाहरण के लिए मैट्रिक्स घातांक की गणना के लिए मैट्रिक्स बहुपद महत्वपूर्ण हैं।

पैटर्सन और स्टॉन्यूनतमेयर ने दर्शाया की डिग्री की गणना कैसे की जाती हैं $O({\sqrt {n}})$ गैर अदिश गुणन और $O(n)$ अदिश गुणन केवल $n$ बहुपद का उपयोग करती हैं।इस प्रकार डिग्री n के एक मैट्रिक्स बहुपद $O(m^{2.3}{\sqrt {n}}+m^{2}n)$ का समय मूल्यांकन किया जा सकता है। अगर $m=n$ से $O(n^{3})$ न्यूनतम है ,तो मानक एल्गोरिथम के सापेक्ष एकल मैट्रिक्स गुणन से तीव्र हैं।

यह विधि इस प्रकार काम करती है: एक बहुपद के लिए

$P(M)=a_{n-1}M^{n-1}+\dots +a_{1}M+a_{0}I,$

मान लीजिए k सबसे छोटा पूर्णांक है जो इससे ${\sqrt {n}}.$ छोटा नही है ,$M,M^{2},\dots ,M^{k}$ घातांक के सापेक्ष गणना की जाती है $k$ मैट्रिक्स गुणन, और $M^{k}.$ द्वारा $M^{2k},M^{3k},\dots ,M^{k^{2}-k}$ की बार-बार गुणा करके गणना की जाती है अब,

${\begin{aligned}P(M)=&\,(a_{0}I+a_{1}M+\dots +a_{k-1}M^{k-1})\\+&\,(a_{k}I+a_{k+1}M+\dots +a_{2k-1}M^{k-1})M^{k}\\+&\,\dots \\+&\,(a_{n-k}I+a_{n-k+1}M+\dots +a_{n-1}M^{k-1})M^{k^{2}-k},\end{aligned}}$,

जहाँ $a_{i}=0$ के लिए i ≥ n है.इसके लिए बस $k$ अधिक गैर-अदिश गुणन की आवश्यकता है।

क्रोनकर उत्पाद का उपयोग करके हम इसे संक्षेप में लिख सकते हैं:

$P(M)={\begin{bmatrix}I\\M\\\vdots \\M^{k-1}\end{bmatrix}}^{T}\left({\begin{bmatrix}a_{0}&a_{1}&a_{2}&\dots \\a_{k}&a_{k+1}&\ddots \\a_{2k}&\ddots \\\vdots \end{bmatrix}}\otimes I\right){\begin{bmatrix}I\\M^{k}\\M^{2k}\\\vdots \end{bmatrix}}$.

इस पद्धति का प्रत्यक्ष अनुप्रयोग का उपयोग $2{\sqrt {n}}$ गैर-अदिश गुणन करता है , परंतु इसे बहुपद मूल्यांकन के सापेक्ष जोड़कर, पैटर्सन और स्टॉन्यूनतमेयर को दर्शाते हैं कि आप ${\sqrt {2n}}$ को न्यूनतम कर सकते हैं

यह भी देखें

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