متعددة حدود لاغرانج

في التحليل العددي ، تعد متعددة الحدود لاغرانج الاستيفائية هي متعددة الحدود الفريدة ذات الدرجة الأدنى التي تستوفي مجموعة معينة من البيانات.

بافتراض وجود مجموعة بيانات من أزواج الإحداثيات${\displaystyle \textstyle (x_{j},y_{j})}$، الـ​${\displaystyle \textstyle x_{j}}$تُسمى هذه العقد ، و${\displaystyle \textstyle y_{j}}$تُسمى هذه القيم . متعددة حدود لاغرانج${\displaystyle L(x)}$والتي تقوم باستيفاء البيانات تفترض كل قيمة عند العقدة المقابلة ،${\displaystyle \textstyle L(x_{j})=y_{j}}$إذا كان هناك${\displaystyle k+1}$بالنسبة لأزواج البيانات، فإن متعددة حدود لاغرانج لها درجة${\displaystyle \leq k}$⁠ .

على الرغم من تسميتها نسبةً إلى جوزيف لويس لاغرانج ، الذي نشرها عام 1795، ^{[ 1 ]} إلا أن الطريقة اكتُشفت لأول مرة عام 1779 على يد إدوارد وارينغ . ^{[ 2 ]} وهي أيضاً نتيجة مباشرة لصيغة نشرها ليونارد أويلر عام 1783. ^{[ 3 ]}

تشمل استخدامات كثيرات حدود لاغرانج طريقة نيوتن-كوتس للتكامل العددي ، ونظام مشاركة الأسرار لشامير في علم التشفير ، وتصحيح الأخطاء ريد-سولومون في نظرية الترميز .

بالنسبة للعقد متساوية المسافات، فإن استيفاء لاغرانج عرضة لظاهرة رونج للتذبذب الكبير.

بالنظر إلى مجموعة من${\displaystyle k+1}$العقد​${\displaystyle \{x_{0},x_{1},\ldots ,x_{k}\}}$والتي يجب أن تكون جميعها متميزة ،${\displaystyle \textstyle x_{j}\neq x_{m}}$للمؤشرات​​${\displaystyle j\neq m}$، أساس لاغرانج لكثيراتالحدود من الدرجة${\displaystyle \leq k}$بالنسبة لتلك العقد ، تكون مجموعة كثيرات الحدود${\displaystyle \textstyle \{\ell _{0}(x),\ell _{1}(x),\ldots ,\ell _{k}(x)\}}$كل درجة${\displaystyle k}$والتي تأخذ قيمًا${\displaystyle \textstyle \ell _{j}(x_{m})=0}$إذا​​${\displaystyle m\neq j}$و​​${\displaystyle \textstyle \ell _{j}(x_{j})=1}$باستخدام دالة كرونكر دلتا ، يمكن كتابة ذلك على النحو التالي :${\displaystyle \textstyle \ell _{j}(x_{m})=\delta _{jm}}$. يمكن وصف كل متعددة حدود أساسية بشكل صريح من خلال حاصل ضرب:

$${\displaystyle {\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})}}\\[8mu]&=\prod _{\begin{smallmatrix}0\leq m\leq k\\m\neq j\end{smallmatrix}}{\frac {x-x_{m}}{x_{j}-x_{m}}}{\vphantom {\Bigg |}}.\end{aligned}}}$$

لاحظ أن البسط ⁠${\displaystyle \textstyle \prod _{m\neq j}(x-x_{m})}$لديه​​${\displaystyle k}$الجذور عند العقد${\displaystyle \textstyle \{x_{m}\}_{m\neq j}}$بينما المقام ⁠${\displaystyle \textstyle \prod _{m\neq j}(x_{j}-x_{m})}$⁠ يقوم بتوسيع نطاق متعدد الحدود الناتج بحيث ⁠${\displaystyle \textstyle \ell _{j}(x_{j})=1}$⁠ .

متعددة حدود لاغرانج الاستيفائية لتلك العقد من خلال القيم المقابلة${\displaystyle \{y_{0},y_{1},\ldots ,y_{k}\}}$التركيبة الخطية :

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

لكل متعددة حدود أساسية درجة${\displaystyle k}$إذن المجموع​${\displaystyle L(x)}$حاصل على درجة علمية${\displaystyle \leq k}$ويقوم هذا البرنامج باستيفاء البيانات لأن${\displaystyle \textstyle L(x_{m})=\sum _{j=0}^{k}y_{j}\ell _{j}(x_{m})=\sum _{j=0}^{k}y_{j}\delta _{mj}=y_{m}}$⁠ .

كثير الحدود المُستكمِل فريد. البرهان: لنفترض وجود كثير حدود ما .${\displaystyle M(x)}$درجة​​${\displaystyle \leq k}$يقوم هذا الأسلوب باستيفاء البيانات. ثم يتم حساب الفرق .${\displaystyle M(x)-L(x)}$يساوي صفرًا عند${\displaystyle k+1}$عقد مميزة${\textstyle \{x_{0},x_{1},\ldots ,x_{k}\}}$لكن متعددة الحدود الوحيدة من الدرجة ⁠${\displaystyle \leq k}$مع أكثر من${\displaystyle k}$الجذر هو دالة ثابتة تساوي صفرًا، لذا${\displaystyle M(x)-L(x)=0}$أو​​${\displaystyle M(x)=L(x)}$⁠ .

كل متعددة حدود أساس لاغرانج${\displaystyle \textstyle \ell _{j}(x)}$يمكن إعادة كتابة ⁠ كحاصل ضرب ثلاثة أجزاء، وهي دالة ⁠${\displaystyle \textstyle \ell (x)=\prod _{m}(x-x_{m})}$ثابت خاص بكل عقدة، وهو ثابت مشترك بين جميع كثيرات الحدود الأساسية .${\displaystyle \textstyle w_{j}=\prod _{m\neq j}(x_{j}-x_{m})^{-1}}$( يُسمى الوزن الباريسنتري )، وجزء يمثل الإزاحة من${\displaystyle \textstyle x_{j}}$إلى​​${\displaystyle x}$⁠ : ^{[ 4 ]}

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

عن طريق التحليل إلى عوامل${\displaystyle \ell (x)}$من خلال المجموع، يمكننا كتابة متعددة حدود لاغرانج في ما يسمى بالشكل الباري سنترال الأول :

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

إذا كانت الأوزان${\displaystyle \textstyle w_{j}}$تم حسابها مسبقًا، وهذا يتطلب فقط${\displaystyle {\mathcal {O}}(k)}$العمليات مقارنة بـ${\displaystyle \textstyle {\mathcal {O}}(k^{2})}$لتقييم كل متعددة حدود أساس لاغرانج${\displaystyle \textstyle \ell _{j}(x)}$بشكل فردي. (انظر ترميز Big O. )

يمكن أيضًا تحديث صيغة الاستيفاء الباريسنترية بسهولة لتضمين عقدة جديدة .${\displaystyle \textstyle x_{k+1}}$بتقسيم كل من${\displaystyle \textstyle w_{j}}$،​​${\displaystyle j=0\dots k}$بواسطة​​${\displaystyle \textstyle (x_{j}-x_{k+1})}$وبناء الجديد​${\displaystyle \textstyle w_{k+1}}$كما سبق.

لأي قيمة لـ x ،${\textstyle \sum _{j=0}^{k}\ell _{j}(x)=1}$لأن الدالة الثابتة${\textstyle g(x)=1}$هي متعددة الحدود الفريدة من الدرجة${\displaystyle \leq k}$استيفاء البيانات${\textstyle \{(x_{0},1),(x_{1},1),\ldots ,(x_{k},1)\}}$وبالتالي ، يمكننا تبسيط صيغة مركز الكتلة بشكل أكبر عن طريق القسمة على {${\displaystyle L(x)=L(x)/g(x)}$:

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

يُطلق على هذا الشكل الثاني أو الشكل الحقيقي لصيغة الاستيفاء الباريسنترية.

يتميز هذا الشكل الثاني بمزايا في تكلفة الحساب والدقة: فهو يتجنب تقييم${\displaystyle \ell (x)}$؛ العمل اللازم لحساب كل حد في المقام${\displaystyle w_{j}/(x-x_{j})}$تم إنجاز ذلك بالفعل في مجال الحوسبة${\displaystyle {\bigl (}w_{j}/(x-x_{j}){\bigr )}y_{j}}$وبالتالي فإن حساب المجموع في المقام لا يكلف سوى${\textstyle k}$عمليات الجمع؛ لنقاط التقييم${\textstyle x}$والتي تقع بالقرب من إحدى العقد${\textstyle x_{j}}$عادةً ما يمثل الإلغاء الكارثي مشكلة بالنسبة للقيمة${\textstyle (x-x_{j})}$ومع ذلك، تظهر هذه الكمية في كل من البسط والمقام، ويتم إلغاء كليهما مما يترك دقة نسبية جيدة في النتيجة النهائية.

استخدام هذه الصيغة للتقييم${\displaystyle L(x)}$في إحدى العقد${\displaystyle x_{j}}$سيؤدي ذلك إلى نتيجة غير محددة${\displaystyle \infty y_{j}/\infty }$يجب أن تستبدل تطبيقات الحاسوب هذه النتائج بـ${\displaystyle L(x_{j})=y_{j}.}$

يمكن أيضًا كتابة كل متعددة حدود أساسية من لاغرانج في شكل مركزي:

$${\displaystyle \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}}$، يجب علينا عكس مصفوفة فاندرموند${\displaystyle (x_{i})^{j}}$لحل${\displaystyle L(x_{i})=y_{i}}$بالنسبة للمعاملات${\displaystyle m_{j}}$ل${\displaystyle L(x)}$باختيار أساس أفضل، وهو أساس لاغرانج،${\textstyle L(x)=\sum _{j=0}^{k}l_{j}(x)y_{j}}$نحصل ببساطة على مصفوفة الوحدة .${\displaystyle \delta _{ij}}$، وهو معكوسها الخاص: أساس لاغرانج يعكس تلقائيًا نظير مصفوفة فانديرموند.

هذا البناء مشابه لنظرية الباقي الصينية . فبدلاً من التحقق من بواقي الأعداد الصحيحة بتردد الأعداد الأولية، فإننا نتحقق من بواقي كثيرات الحدود عند قسمتها على دوال خطية.

علاوة على ذلك، عندما يكون الترتيب كبيرًا، يمكن استخدام تحويل فورييه السريع لحل معاملات كثير الحدود المستوفى.

نرغب في الاستيفاء${\displaystyle f(x)=x^{2}}$على النطاق${\displaystyle 1\leq x\leq 3}$عند العقد الثلاث${\displaystyle \{1,\,2,\,3\}}$:

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

متعدد الحدود العقدي${\displaystyle \ell }$يكون $${\displaystyle \ell (x)=(x-1)(x-2)(x-3)=x^{3}-6x^{2}+11x-6.}$$

الأوزان الباريسنترية هي $${\displaystyle {\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}}}$$

كثيرات حدود أساس لاغرانج هي

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

متعددة الحدود لاغرانج الاستيفائية هي: $${\displaystyle {\begin{aligned}L(x)&=y_{0}\cdot \ell _{0}(x)+y_{1}\cdot \ell _{1}(x)+y_{2}\cdot \ell _{2}(x)=x^{2}.\end{aligned}}}$$

في الشكل (الثاني) المركزي،

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

تُظهر صيغة لاغرانج لكثيرة الحدود الاستيفائية الطابع الخطي للاستيفاء متعدد الحدود ووحدانية هذه كثيرة الحدود. لذا، يُفضّل استخدامها في البراهين والحجج النظرية. ويمكن إثبات الوحدانية أيضًا من خلال قابلية عكس مصفوفة فاندرموند، نظرًا لعدم انعدام محدد فاندرموند .

لكن، كما يتضح من البنية، في كل مرة يتغير فيها موضع العقدة x _k ، يجب إعادة حساب جميع كثيرات حدود أساس لاغرانج. يُعد الشكل الباري مركزي لاستيفاء لاغرانج (انظر أدناه) أو كثيرات حدود نيوتن شكلاً أفضل لكثيرة حدود الاستيفاء لأغراض عملية (أو حسابية) .

تؤدي طرق لاغرانج وغيرها من طرق الاستيفاء عند نقاط متساوية التباعد، كما في المثال أعلاه، إلى معادلة متعددة الحدود تتذبذب أعلى وأسفل الدالة الحقيقية. ويميل هذا السلوك إلى التزايد مع عدد النقاط، مما يؤدي إلى تباعد يُعرف بظاهرة رونج ؛ ويمكن التغلب على هذه المشكلة باختيار نقاط الاستيفاء عند عقد تشيبيشيف . ^{[ 5 ]}

يمكن استخدام كثيرات حدود أساس لاغرانج في التكامل العددي لاستنتاج صيغ نيوتن-كوتس .

عند استيفاء دالة معينة f بواسطة متعددة حدود من الدرجة k عند العقد${\displaystyle x_{0},\dots ,x_{k}}$نحصل على الباقي${\displaystyle R(x)=f(x)-L(x)}$والتي يمكن التعبير عنها على النحو التالي ^{[ 6 ]}

$${\displaystyle {\begin{aligned}R(x)&=f[x_{0},\ldots ,x_{k},x]\ell (x)\\[1ex]&=\ell (x){\frac {f^{(k+1)}(\xi )}{(k+1)!}},&x_{0}<\xi <x_{k},\end{aligned}}}$$

أين${\displaystyle f[x_{0},\ldots ,x_{k},x]}$يُستخدم الرمز للدلالة على الفروق المقسمة . ويمكن التعبير عن الباقي كتكامل كفافي في المجال المركب كما يلي:

$${\displaystyle {\begin{aligned}R(x)&={\frac {\ell (x)}{2\pi i}}\int _{C}{\frac {f(t)}{(t-x)(t-x_{0})\cdots (t-x_{k})}}dt\\[1ex]&={\frac {\ell (x)}{2\pi i}}\int _{C}{\frac {f(t)}{(t-x)\ell (t)}}dt.\end{aligned}}}$$

ويمكن ربط الباقي على النحو التالي

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

يمكن كتابة المشتقة من الرتبة d لكثير الحدود لاغرانج الاستيفائي بدلالة مشتقات كثيرات الحدود الأساسية.

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

تذكر (انظر §  التعريف أعلاه) أن كل متعددة حدود أساسية من لاغرانج هي

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

يمكن إيجاد المشتقة الأولى باستخدام قاعدة الضرب :

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

المشتقة الثانية هي

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

المشتق الثالث هو

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

وينطبق الأمر نفسه على المشتقات الأعلى.

لاحظ أن جميع هذه الصيغ للمشتقات غير صالحة عند العقدة أو بالقرب منها. تتمثل إحدى طرق حساب جميع رتب مشتقات متعددة حدود لاغرانج بكفاءة عند جميع نقاط المجال، بما في ذلك العقد، في تحويل متعددة حدود لاغرانج إلى صيغة أساس القوى ثم حساب المشتقات.

يمكن أيضًا حساب متعددة حدود لاغرانج في الحقول المنتهية . ولهذا تطبيقات في علم التشفير ، كما هو الحال في مخطط مشاركة الأسرار لشامير .

• "صيغة لاغرانج للاستيفاء" ، موسوعة الرياضيات ، دار نشر EMS، 2001 [1994]
• يحتوي ALGLIB على تطبيقات بلغات C++ / C# / VBA / Pascal.
• تحتوي مكتبة GSL على كود استيفاء متعدد الحدود مكتوب بلغة C
• يحتوي موقع SO على مثال MATLAB يوضح الخوارزمية ويعيد إنشاء الصورة الأولى في هذه المقالة
• طريقة لاغرانج للاستيفاء - ملاحظات، عرض تقديمي، ماثكاد، ماثيماتيكا، ماتلاب، مابل
• كثير الحدود لاغرانج للاستيفاء على الموقع www.math-linux.com
• وايسشتاين، إريك دبليو. "متعددة الحدود لاغرانج الاستيفائية" . عالم الرياضيات .
• دالة ورقة عمل إكسل للاستيفاء التكعيبي لاغرانج
• كثيرات حدود لاغرانج في بايثون