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

गणित और कंप्यूटर विज्ञान में, बहुपद मूल्यांकन एक बहुपद के मूल्य की गणना को संदर्भित करता है तथा इसके अनिश्चित चर को कुछ मूल्यों के लिए प्रतिस्थापित किया जाता है। दूसरे शब्दों में, बहुपद के मूल्यांकन $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{array}{rl}P(x,y)& =4+x(1+y(2)+x(y(2+y)))\text{or}\\ P(x,y)& =4+x+y(x(2+x(\end{array}$