लैग्रेंज बहुपद

यह चित्र चार बिंदुओं के लिए दिखाता है ((−9, 5), (−4, 2), (−1, −2), (7, 9)), (घन) प्रक्षेप बहुपद < स्पैन स्टाइल = रंग: काला; >L(x) (धराशायी, काला), जो स्केल किए गए आधार बहुपदों का योग है य₀ℓ₀(x), य₁ℓ₁(x), य₂ℓ₂(x) और य₃ℓ₃(एक्स)। प्रक्षेप बहुपद सभी चार नियंत्रण बिंदुओं से होकर गुजरता है, और प्रत्येक स्केल्ड आधार बहुपद अपने संबंधित नियंत्रण बिंदु से गुजरता है और 0 है जहां x अन्य तीन नियंत्रण बिंदुओं से मेल खाता है।

संख्यात्मक विश्लेषण में, लैग्रेंज इंटरपोलेटिंग बहुपद एक बहुपद की निम्नतम डिग्री का अनूठा बहुपद है जो बहुपद डेटा के एक सेट को प्रक्षेपित करता है।

किसी फ़ंक्शन के ग्राफ़ के डेटा सेट को देखते हुए $(x_{j},y_{j})$ साथ $0\leq j\leq k,$ $x_{j}$ नोड कहलाते हैं और $y_{j}$ मान कहलाते हैं। लैग्रेंज बहुपद $L(x)$ डिग्री है ${\textstyle \leq k}$ और प्रत्येक मान को संबंधित नोड पर मानता है, $L(x_{j})=y_{j}.$ हालांकि इसका नाम जोसेफ-लुई लाग्रेंज के नाम पर रखा गया, जिन्होंने इसे 1795 में प्रकाशित किया था, विधि पहली बार 1779 में एडवर्ड वारिंग द्वारा खोजी गई थी। यह लियोनहार्ड यूलर द्वारा 1783 में प्रकाशित एक सूत्र का भी आसान परिणाम है। लैग्रेंज बहुपदों के उपयोग में न्यूटन-कोट्स सूत्र शामिल हैं। न्यूटन-कोट्स संख्यात्मक एकीकरण की विधि और शमीर की गुप्त साझाकरण। क्रिप्टोग्राफी में शमीर की गुप्त साझाकरण योजना।

समस्थानिक नोड्स के लिए, लैग्रेंज इंटरपोलेशन बड़े दोलन की रूंज की घटना के लिए अतिसंवेदनशील है।

परिभाषा

का एक सेट दिया ${\textstyle k+1}$ नोड्स $\{x_{0},x_{1},\ldots ,x_{k}\}$, जो सभी अलग-अलग होने चाहिए, $x_{j}\neq x_{m}$ सूचकांकों के लिए $j\neq m$, डिग्री के बहुपदों के लिए लैग्रेंज आधार ${\textstyle \leq k}$ उन नोड्स के लिए बहुपदों का समूह है ${\textstyle \{\ell _{0}(x),\ell _{1}(x),\ldots ,\ell _{k}(x)\}}$ प्रत्येक डिग्री ${\textstyle k}$ जो मान लेते हैं ${\textstyle \ell _{j}(x_{m})=0}$ अगर ${\textstyle m\neq j}$ और ${\textstyle \ell _{j}(x_{j})=1}$. क्रोनकर डेल्टा का उपयोग करके इसे लिखा जा सकता है ${\textstyle \ell _{j}(x_{m})=\delta _{jm}.}$ प्रत्येक आधार बहुपद को उत्पाद द्वारा स्पष्ट रूप से वर्णित किया जा सकता है:

$${\begin{aligned}\ell _{j}(x)&={\frac {(x-x_{0})}{(x_{j}-x_{0})}}\cdots {\frac {(x-x_{j-1})}{(x_{j}-x_{j-1})}}{\frac {(x-x_{j+1})}{(x_{j}-x_{j+1})}}\cdots {\frac {(x-x_{k})}{(x_{j}-x_{k})}}\\[10mu]&=\prod _{\begin{smallmatrix}0\leq m\leq k\\m\neq j\end{smallmatrix}}{\frac {x-x_{m}}{x_{j}-x_{m}}}.\end{aligned}}$$

ध्यान दें कि अंश ${\textstyle \prod _{m\neq j}(x-x_{m})}$ है ${\textstyle k}$ नोड्स पर जड़ें ${\textstyle \{x_{m}\}_{m\neq j}}$ जबकि भाजक ${\textstyle \prod _{m\neq j}(x_{j}-x_{m})}$ परिणामी बहुपद को स्केल करता है ताकि ${\textstyle \ell _{j}(x_{j})=1.}$ संबंधित मानों के माध्यम से उन नोड्स के लिए लैग्रेंज इंटरपोलेटिंग बहुपद $\{y_{0},y_{1},\ldots ,y_{k}\}$ रैखिक संयोजन है:

$$L(x)=\sum _{j=0}^{k}y_{j}\ell _{j}(x).$$

प्रत्येक आधार बहुपद की डिग्री होती है ${\textstyle k}$, तो योग ${\textstyle L(x)}$ डिग्री है ${\textstyle \leq k}$, और यह डेटा को प्रक्षेपित करता है क्योंकि ${\textstyle L(x_{m})=\sum _{j=0}^{k}y_{j}\ell _{j}(x_{m})=\sum _{j=0}^{k}y_{j}\delta _{mj}=y_{m}.}$ इंटरपोलेटिंग बहुपद अद्वितीय है। सबूत: बहुपद मान लें ${\textstyle M(x)}$ डिग्री का ${\textstyle \leq k}$ डेटा को इंटरपोलेट करता है। फिर फर्क ${\textstyle M(x)-L(x)}$ पर शून्य है ${\textstyle k+1}$ विशिष्ट नोड्स ${\textstyle \{x_{0},x_{1},\ldots ,x_{k}\}.}$ लेकिन डिग्री का एकमात्र बहुपद ${\textstyle \leq k}$ से अधिक के साथ ${\textstyle k}$ जड़ें निरंतर शून्य कार्य है, इसलिए ${\textstyle M(x)-L(x)=0,}$ या ${\textstyle M(x)=L(x).}$

बैरीसेंट्रिक रूप

प्रत्येक Lagrange आधार बहुपद ${\textstyle \ell _{j}(x)}$ तीन भागों, एक समारोह के उत्पाद के रूप में फिर से लिखा जा सकता है ${\textstyle \ell (x)=\prod _{m}(x-x_{m})}$ हर आधार बहुपद के लिए सामान्य, एक नोड-विशिष्ट स्थिरांक ${\textstyle w_{j}=\prod _{m\neq j}(x_{j}-x_{m})^{-1}}$ (बैरीसेंट्रिक वजन कहा जाता है), और विस्थापन का प्रतिनिधित्व करने वाला एक हिस्सा ${\textstyle x_{j}}$ को ${\textstyle x}$:

$$\ell _{j}(x)=\ell (x){\dfrac {w_{j}}{x-x_{j}}}$$

फैक्टरिंग करके ${\textstyle \ell (x)}$ योग से बाहर, हम लैग्रेंज बहुपद को तथाकथित प्रथम बेरिकेंट्रिक रूप में लिख सकते हैं:

$L(x)=\ell (x)\sum _{j=0}^{k}{\frac {w_{j}}{x-x_{j}}}y_{j}.$

अगर वजन $w_{j}$ पूर्व-गणना की गई है, इसके लिए केवल आवश्यकता है ${\mathcal {O}}(k)$ संचालन की तुलना में ${\mathcal {O}}(k^{2})$ प्रत्येक Lagrange आधार बहुपद का मूल्यांकन करने के लिए $\ell _{j}(x)$ व्यक्तिगत रूप से।

एक नया नोड शामिल करने के लिए बैरीसेंट्रिक इंटरपोलेशन फॉर्मूला को भी आसानी से अपडेट किया जा सकता है $x_{k+1}$ प्रत्येक को विभाजित करके $w_{j}$, $j=0\dots k$ द्वारा $(x_{j}-x_{k+1})$ और नया निर्माण $w_{k+1}$ ऊपरोक्त अनुसार।

किसी के लिए ${\textstyle x,}$ ${\textstyle \sum _{j=0}^{k}\ell _{j}(x)=1}$ क्योंकि निरंतर कार्य ${\textstyle g(x)=1}$ डिग्री का अद्वितीय बहुपद है $\leq k$ डेटा प्रक्षेपित करना ${\textstyle \{(x_{0},1),(x_{1},1),\ldots ,(x_{k},1)\}.}$ इस प्रकार हम विभाजित करके बैरेंट्रिक सूत्र को और सरल बना सकते हैं $L(x)=L(x)/g(x)\colon$

${\begin{aligned}L(x)&=\ell (x)\sum _{j=0}^{k}{\frac {w_{j}}{x-x_{j}}}y_{j}{\Bigg /}\ell (x)\sum _{j=0}^{k}{\frac {w_{j}}{x-x_{j}}}\\[10mu]&=\sum _{j=0}^{k}{\frac {w_{j}}{x-x_{j}}}y_{j}{\Bigg /}\sum _{j=0}^{k}{\frac {w_{j}}{x-x_{j}}}.\end{aligned}}$

इसे बेरसेंट्रिक इंटरपोलेशन फॉर्मूला का दूसरा रूप या सही रूप कहा जाता है।

गणना लागत और सटीकता में इस दूसरे रूप के फायदे हैं: यह मूल्यांकन से बचा जाता है $\ell (x)$; भाजक में प्रत्येक शब्द की गणना करने का कार्य $w_{j}/(x-x_{j})$ कंप्यूटिंग में किया जा चुका है ${\bigl (}w_{j}/(x-x_{j}){\bigr )}y_{j}$ और इसलिए हर में योग की गणना करने में केवल लागत आती है ${\textstyle k-1}$ अतिरिक्त संचालन; मूल्यांकन बिंदुओं के लिए ${\textstyle x}$ जो एक नोड के करीब हैं ${\textstyle x_{j}}$, भयावह रद्दीकरण आमतौर पर मूल्य के लिए एक समस्या होगी ${\textstyle (x-x_{j})}$, हालांकि यह मात्रा अंश और हर दोनों में दिखाई देती है और अंतिम परिणाम में अच्छी सापेक्ष सटीकता छोड़ते हुए दोनों रद्द हो जाते हैं।

मूल्यांकन करने के लिए इस सूत्र का उपयोग करना $L(x)$ नोड्स में से एक पर $x_{j}$ अनिश्चित रूप में परिणाम होगा $\infty y_{j}/\infty$; कंप्यूटर कार्यान्वयन को ऐसे परिणामों को प्रतिस्थापित करना चाहिए $L(x_{j})=y_{j}.$ प्रत्येक Lagrange आधार बहुपद को बेरिकेंट्रिक रूप में भी लिखा जा सकता है:

$\ell _{j}(x)={\frac {w_{j}}{x-x_{j}}}{\Bigg /}\sum _{m=0}^{k}{\frac {w_{m}}{x-x_{m}}}.$

== रैखिक बीजगणित == से एक परिप्रेक्ष्य

एक बहुपद इंटरपोलेशन को हल करना # इंटरपोलेशन पॉलीनोमियल का निर्माण रैखिक बीजगणित में मैट्रिक्स के व्युत्क्रम की समस्या की ओर ले जाता है। हमारे प्रक्षेप बहुपद के लिए एक मानक एकपदी आधार का उपयोग करना ${\textstyle L(x)=\sum _{j=0}^{k}x^{j}m_{j}}$, हमें वैंडरमोंड मैट्रिक्स को उल्टा करना चाहिए $(x_{i})^{j}$ समाधान करना $L(x_{i})=y_{i}$ गुणांक के लिए $m_{j}$ का $L(x)$. एक बेहतर आधार चुनकर, लैग्रेंज आधार, ${\textstyle L(x)=\sum _{j=0}^{k}l_{j}(x)y_{j}}$, हम केवल पहचान मैट्रिक्स, क्रोनकर डेल्टा प्राप्त करते हैं$\delta _{ij}$, जो इसका अपना प्रतिलोम है: लैग्रेंज आधार स्वचालित रूप से वैंडरमोंड मैट्रिक्स के एनालॉग को उलट देता है।

यह निर्माण चीनी शेष प्रमेय के अनुरूप है। पूर्णांक मॉडुलो अभाज्य संख्याओं के अवशेषों की जाँच करने के बजाय, हम रैखिकों द्वारा विभाजित किए जाने पर बहुपदों के अवशेषों की जाँच कर रहे हैं।

इसके अलावा, जब ऑर्डर बड़ा होता है, तो इंटरपोलेटेड बहुपद के गुणांकों को हल करने के लिए फास्ट फूरियर रूपांतरण का उपयोग किया जा सकता है।

उदाहरण

हम इंटरपोलेट करना चाहते हैं $f(x)=x^{2}$ डोमेन के ऊपर $1\leq x\leq 3$ तीन नोड्स पर $\{1,\,2,\,3\}$:

${\begin{aligned}x_{0}&=1,&&&y_{0}=f(x_{0})&=1,\\[3mu]x_{1}&=2,&&&y_{1}=f(x_{1})&=4,\\[3mu]x_{2}&=3,&&&y_{2}=f(x_{2})&=9.\end{aligned}}$

नोड बहुपद $\ell$ है

$\ell (x)=(x-1)(x-2)(x-3)=x^{3}-6x^{2}+11x-6.$

बैरीसेंट्रिक भार हैं

${\begin{aligned}w_{0}&=(1-2)^{-1}(1-3)^{-1}={\tfrac {1}{2}},\\[3mu]w_{1}&=(2-1)^{-1}(2-3)^{-1}=-1,\\[3mu]w_{2}&=(3-1)^{-1}(3-2)^{-1}={\tfrac {1}{2}}.\end{aligned}}$

Lagrange आधार बहुपद हैं

${\begin{aligned}\ell _{0}(x)&={\frac {x-2}{1-2}}\cdot {\frac {x-3}{1-3}}={\tfrac {1}{2}}x^{2}-{\tfrac {5}{2}}x+3,\\[5mu]\ell _{1}(x)&={\frac {x-1}{2-1}}\cdot {\frac {x-3}{2-3}}=-x^{2}+4x-3,\\[5mu]\ell _{2}(x)&={\frac {x-1}{3-1}}\cdot {\frac {x-2}{3-2}}={\tfrac {1}{2}}x^{2}-{\tfrac {3}{2}}x+1.\end{aligned}}$

लैग्रेंज इंटरपोलिंग बहुपद है:

${\begin{aligned}L(x)&=1\cdot {\frac {x-2}{1-2}}\cdot {\frac {x-3}{1-3}}+4\cdot {\frac {x-1}{2-1}}\cdot {\frac {x-3}{2-3}}+9\cdot {\frac {x-1}{3-1}}\cdot {\frac {x-2}{3-2}}\\[6mu]&=x^{2}.\end{aligned}}$

(द्वितीय) बेरसेंट्रिक रूप में,

$L(x)={\frac {\displaystyle \sum _{j=0}^{2}{\frac {w_{j}}{x-x_{j}}}y_{j}}{\displaystyle \sum _{j=0}^{2}{\frac {w_{j}}{x-x_{j}}}}}={\frac {\displaystyle {\frac {\tfrac {1}{2}}{x-1}}+{\frac {-4}{x-2}}+{\frac {\tfrac {9}{2}}{x-3}}}{\displaystyle {\frac {\tfrac {1}{2}}{x-1}}+{\frac {-1}{x-2}}+{\frac {\tfrac {1}{2}}{x-3}}}}.$

टिप्पणियाँ

Example of interpolation divergence for a set of Lagrange polynomials.

The Lagrange form of the interpolation polynomial shows the linear character of polynomial interpolation and the uniqueness of the interpolation polynomial. Therefore, it is preferred in proofs and theoretical arguments. Uniqueness can also be seen from the invertibility of the Vandermonde matrix, due to the non-vanishing of the Vandermonde determinant.

But, as can be seen from the construction, each time a node x_k changes, all Lagrange basis polynomials have to be recalculated. A better form of the interpolation polynomial for practical (or computational) purposes is the barycentric form of the Lagrange interpolation (see below) or Newton polynomials.

Lagrange and other interpolation at equally spaced points, as in the example above, yield a polynomial oscillating above and below the true function. This behaviour tends to grow with the number of points, leading to a divergence known as Runge's phenomenon; the problem may be eliminated by choosing interpolation points at Chebyshev nodes.

The Lagrange basis polynomials can be used in numerical integration to derive the Newton–Cotes formulas.

लैग्रेंज इंटरपोलेशन फॉर्मूला में अवशेष

किसी दिए गए फ़ंक्शन f को डिग्री के बहुपद द्वारा प्रक्षेपित करते समय k नोड्स पर $x_{0},...,x_{k}$ हमें शेष मिलता है $R(x)=f(x)-L(x)$ जिसे व्यक्त किया जा सकता है

$R(x)=f[x_{0},\ldots ,x_{k},x]\ell (x)=\ell (x){\frac {f^{(k+1)}(\xi )}{(k+1)!}},\quad \quad x_{0}<\xi <x_{k},$

कहाँ $f[x_{0},\ldots ,x_{k},x]$ विभाजित मतभेदों के लिए अंकन है। वैकल्पिक रूप से, शेष को जटिल डोमेन में समोच्च अभिन्न के रूप में व्यक्त किया जा सकता है

$R(x)={\frac {\ell (x)}{2\pi i}}\int _{C}{\frac {f(t)}{(t-x)(t-x_{0})\cdots (t-x_{k})}}dt={\frac {\ell (x)}{2\pi i}}\int _{C}{\frac {f(t)}{(t-x)\ell (t)}}dt.$

शेष के रूप में बाध्य किया जा सकता है

$|R(x)|\leq {\frac {(x_{k}-x_{0})^{k+1}}{(k+1)!}}\max _{x_{0}\leq \xi \leq x_{k}}|f^{(k+1)}(\xi )|.$

व्युत्पत्ति

स्पष्ट रूप से, $R(x)$ नोड्स पर शून्य है। ढूँढ़ने के लिए $R(x)$ एक बिंदु पर $x_{p}$, एक नया कार्य परिभाषित करें $F(x)=R(x)-{\tilde {R}}(x)=f(x)-L(x)-{\tilde {R}}(x)$ और चुनें ${\textstyle {\tilde {R}}(x)=C\cdot \prod _{i=0}^{k}(x-x_{i})}$ कहाँ $C$ वह स्थिरांक है जिसे हमें दिए गए के लिए निर्धारित करना है $x_{p}$. हम चुनते हैं $C$ ताकि $F(x)$ है $k+2$ शून्य (सभी नोड्स पर और $x_{p}$) बीच में $x_{0}$ और $x_{k}$ (अंतिम बिंदुओं सहित)। ये मानते हुए $f(x)$ है $k+1$-समय अलग-अलग, के बाद से $L(x)$ और ${\tilde {R}}(x)$ बहुपद हैं, और इसलिए, असीम रूप से भिन्न हैं, $F(x)$ होगा $k+1$-समय अलग करने योग्य। रोले के प्रमेय द्वारा, $F^{(1)}(x)$ है $k+1$ शून्य, $F^{(2)}(x)$ है $k$ शून्य... $F^{(k+1)}$ 1 शून्य है, कहते हैं $\xi ,\,x_{0}<\xi <x_{k}$. स्पष्ट रूप से लिख रहा हूँ $F^{(k+1)}(\xi )$:

$F^{(k+1)}(\xi )=f^{(k+1)}(\xi )-L^{(k+1)}(\xi )-{\tilde {R}}^{(k+1)}(\xi )$

$L^{(k+1)}=0,{\tilde {R}}^{(k+1)}=C\cdot (k+1)!$ (क्योंकि उच्चतम शक्ति $x$ में ${\tilde {R}}(x)$ है $k+1$)

$0=f^{(k+1)}(\xi )-C\cdot (k+1)!$

समीकरण के रूप में पुनर्व्यवस्थित किया जा सकता है

$C={\frac {f^{(k+1)}(\xi )}{(k+1)!}}$

तब से $F(x_{p})=0$ अपने पास $R(x_{p})={\tilde {R}}(x_{p})={\frac {f^{k+1}(\xi )}{(k+1)!}}\prod _{i=0}^{k}(x_{p}-x_{i})$

== डेरिवेटिव्स == d}एक Lagrange अंतर्वेशी बहुपद के वें व्युत्पन्न आधार बहुपद के डेरिवेटिव के संदर्भ में लिखा जा सकता है,

$L^{(d)}(x):=\sum _{j=0}^{k}y_{j}\ell _{j}^{(d)}(x).$

स्मरण (देखें § Definition ऊपर) कि प्रत्येक Lagrange आधार बहुपद है

$${\begin{aligned}\ell _{j}(x)&=\prod _{\begin{smallmatrix}m=0\\m\neq j\end{smallmatrix}}^{k}{\frac {x-x_{m}}{x_{j}-x_{m}}}.\end{aligned}}$$

उत्पाद नियम # दो से अधिक कारकों के उत्पाद का उपयोग करके पहला व्युत्पन्न पाया जा सकता है:

${\begin{aligned}\ell _{j}'(x)&=\sum _{\begin{smallmatrix}i=0\\i\not =j\end{smallmatrix}}^{k}{\Biggl [}{\frac {1}{x_{j}-x_{i}}}\prod _{\begin{smallmatrix}m=0\\m\not =(i,j)\end{smallmatrix}}^{k}{\frac {x-x_{m}}{x_{j}-x_{m}}}{\Biggr ]}\\[5mu]&=\ell _{j}(x)\sum _{\begin{smallmatrix}i=0\\i\not =j\end{smallmatrix}}^{k}{\frac {1}{x-x_{i}}}.\end{aligned}}$

दूसरा व्युत्पन्न है

${\begin{aligned}\ell _{j}''(x)&=\sum _{\begin{smallmatrix}i=0\\i\neq j\end{smallmatrix}}^{k}{\frac {1}{x_{j}-x_{i}}}{\Biggl [}\sum _{\begin{smallmatrix}m=0\\m\neq (i,j)\end{smallmatrix}}^{k}{\Biggl (}{\frac {1}{x_{j}-x_{m}}}\prod _{\begin{smallmatrix}n=0\\n\neq (i,j,m)\end{smallmatrix}}^{k}{\frac {x-x_{n}}{x_{j}-x_{n}}}{\Biggr )}{\Biggr ]}\\[10mu]&=\ell _{j}(x)\sum _{0\leq i<m\leq k}{\frac {2}{(x-x_{i})(x-x_{m})}}\\[10mu]&=\ell _{j}(x){\Biggl [}{\Biggl (}\sum _{\begin{smallmatrix}i=0\\i\not =j\end{smallmatrix}}^{k}{\frac {1}{x-x_{i}}}{\Biggr )}^{2}-\sum _{\begin{smallmatrix}i=0\\i\not =j\end{smallmatrix}}^{k}{\frac {1}{(x-x_{i})^{2}}}{\Biggr ]}.\end{aligned}}$

तीसरा व्युत्पन्न है

${\begin{aligned}\ell _{j}'''(x)&=\ell _{j}(x)\sum _{0\leq i<m<n\leq k}{\frac {3!}{(x-x_{i})(x-x_{m})(x-x_{n})}}\end{aligned}}$

और इसी तरह उच्च डेरिवेटिव के लिए।

परिमित क्षेत्र

Lagrange बहुपद की गणना परिमित क्षेत्रों में भी की जा सकती है। इसमें क्रिप्टोग्राफी में अनुप्रयोग हैं, जैसे शमीर की गुप्त साझाकरण योजना में।

यह भी देखें

• नेविल का एल्गोरिदम
• प्रक्षेप बहुपद का न्यूटन बहुपद
• बर्नस्टीन बहुपद
• कार्लसन की प्रमेय
• लेबेस्ग स्थिरांक (प्रक्षेप)
• चेबफन
• न्यूटोनियन श्रृंखला की तालिका
• फ्रोबेनियस सहसंयोजक
• सिल्वेस्टर का सूत्र
• परिमित अंतर गुणांक
• सन्यासी के बीच

बाहरी संबंध

• "Lagrange interpolation formula", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
• ALGLIB has an implementations in C++ / C# / VBA / Pascal.
• GSL has a polynomial interpolation code in C
• SO has a MATLAB example that demonstrates the algorithm and recreates the first image in this article
• Lagrange Method of Interpolation — Notes, PPT, Mathcad, Mathematica, MATLAB, Maple at Holistic Numerical Methods Institute
• Lagrange interpolation polynomial on www.math-linux.com
• Weisstein, Eric W. "Lagrange Interpolating Polynomial". MathWorld.
• लैग्रेंज बहुपद at ProofWiki
• Dynamic Lagrange interpolation with JSXGraph
• Numerical computing with functions: The Chebfun Project
• Excel Worksheet Function for Bicubic Lagrange Interpolation
• Lagrange polynomials in Python