الاستيفاء متعدد الحدود

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

بافتراض مجموعة من $n + 1$ نقطة بيانات $(x_{0},y_{0}),\ldots ,(x_{n},y_{n})$ ، بدون اثنين $x_{j}$ وهي نفسها دالة متعددة الحدود $p(x)=a_{0}+a_{1}x+\cdots +a_{n}x^{n}$ يقال إنها تقوم باستيفاء البيانات إذا $p(x_{j})=y_{j}$ لكل $j\in \{0,1,\dotsc ,n\}$ .

يوجد دائمًا متعدد حدود فريد من نوعه، يُعطى عادةً بصيغتين صريحتين، وهما متعددات حدود لاغرانج ومتعددات حدود نيوتن .

التطبيقات

كان الاستخدام الأصلي لكثيرات الحدود الاستيفائية هو تقريب قيم الدوال المتسامية المهمة ، مثل اللوغاريتم الطبيعي والدوال المثلثية . وبالبدء ببضع نقاط بيانات محسوبة بدقة، تقوم كثيرة الحدود الاستيفائية المقابلة بتقريب الدالة عند أي نقطة قريبة. كما يشكل الاستيفاء بكثيرات الحدود أساسًا للخوارزميات في التكامل العددي ( قاعدة سيمبسون ) والمعادلات التفاضلية العادية العددية ( طرق الشبكة المتعددة ).

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

في التحليل العددي، يُعدّ استيفاء كثيرات الحدود أساسيًا لإجراء عمليات الضرب والتربيع شبه التربيعية، مثل ضرب كاراتسوبا وضرب توم-كوك ، حيث يُعطي الاستيفاء عبر نقاط على كثير حدود الضرب الناتج المطلوب. على سبيل المثال، إذا كان لدينا ^{a = f(x) = a₀x₀ + a₁x₁}+ ... و b = g ( ^x) = _b₀x₀ + b₁x₁ + ... ، فإن الناتج ab هو قيمة _محددة^لـ^W( x ) = f ( x ) g ( x ) . يمكن بسهولة إيجاد نقاط على طول _W( x ) عند قيم صغيرة لـ _x، وسيؤدي الاستيفاء بناءً على هذه النقاط إلى الحصول على حدود W ( x ) والناتج ab . وكما هو مُصاغ في ضرب كاراتسوبا، فإن هذه التقنية أسرع بكثير من الضرب التربيعي، حتى مع المدخلات ذات الأحجام المتوسطة، وخاصةً على الأجهزة المتوازية.

في علوم الحاسوب ، يؤدي الاستيفاء متعدد الحدود أيضًا إلى خوارزميات للحوسبة الآمنة متعددة الأطراف ومشاركة الأسرار .

نظرية الاستيفاء

لأي $n+1$ نقاط البيانات ثنائية المتغيرات $(x_{0},y_{0}),\dotsc ,(x_{n},y_{n})\in \mathbb {R} ^{2}$ حيث لا يوجد اثنان $x_{j}$ إذا كانت متطابقة، فهناك متعددة حدود فريدة $p(x)$ درجة علمية على الأكثر $n$ التي تقوم باستيفاء هذه النقاط، أي $p(x_{0})=y_{0},\ldots ,p(x_{n})=y_{n}$ [ ¹^]

وبصورة مكافئة، بالنسبة لاختيار ثابت لعقد الاستيفاء $x_{j}$ يُعرّف الاستيفاء متعدد الحدود تقابلًا خطيًا $L_{n}$ بين ( ن + 1) من القيم العددية الحقيقية $(y_{0},\ldots ,y_{n})\in \mathbb {R} ^{n+1}$ والفضاء المتجهي $P(n)$ من كثيرات الحدود الحقيقية من الدرجة n على الأكثر : $L_{n}:\mathbb {R} ^{n+1}{\stackrel {\sim }{\longrightarrow }}\,P(n).$

هذا نوع من نظريات الحل الأحادي . وتكون النظرية صالحة أيضًا على أي حقل لانهائي بدلاً من الأعداد الحقيقية. $\mathbb {R}$ على سبيل المثال، الأعداد النسبية أو المركبة.

الدليل الأول

ضع في اعتبارك دوال أساس لاغرانج $L_{0}(x),\ldots ,L_{n}(x)$ مقدم من: $L_{j}(x)=\prod _{i=0,i\neq j}^{n}{\frac {x-x_{i}}{x_{j}-x_{i}}}={\frac {(x-x_{0})\cdots (x-x_{j-1})(x-x_{j+1})\cdots (x-x_{n})}{(x_{j}-x_{0})\cdots (x_{j}-x_{j-1})(x_{j}-x_{j+1})\cdots (x_{j}-x_{n})}}.$

لاحظ أن $L_{j}(x)$ هي متعددة حدود من الدرجة $n$ ولدينا $L_{j}(x_{k})=0$ لكل $j\neq k$ ، بينما $L_{k}(x_{k})=1$ وبناءً على ذلك، فإن التركيبة الخطية هي: $p(x)=\sum _{j=0}^{n}y_{j}L_{j}(x)$ لديه $p(x_{k})=\sum _{j}y_{j}\,L_{j}(x_{k})=y_{k}$ ، لذا $p(x)$ هي متعددة حدود استيفاء من الدرجة $n$ .

لإثبات التفرد، افترض وجود متعددة حدود استيفائية أخرى $q(x)$ درجة علمية على الأكثر $n$ ، لهذا السبب $p(x_{k})=q(x_{k})$ للجميع $k=0,\dotsc ,n$ . ثم $p(x)-q(x)$ هي متعددة حدود من الدرجة على الأكثر $n$ والذي يحتوي $n+1$ الأصفار المميزة (الـ $x_{k}$ ). لكن متعددة حدود غير صفرية من الدرجة على الأكثر $n$ يمكن أن يكون لديه على الأكثر $n$ أصفار، ^{[ أ ]} لذلك $p(x)-q(x)$ يجب أن تكون كثيرة الحدود الصفرية، أي $p(x)=q(x)$ [ ²^]

الدليل الثاني

اكتب متعددة الحدود الاستيفائية على الصورة

p(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots +a_{2}x^{2}+a_{1}x+a_{0}.

1

بإدخال هذا في معادلات الاستيفاء $p(x_{j})=y_{j}$ ، فنحصل على نظام من المعادلات الخطية في المعاملات $a_{j}$ ، والتي تُقرأ في شكل مصفوفة-متجه على النحو التالي : ${\begin{bmatrix}x_{0}^{n}&x_{0}^{n-1}&x_{0}^{n-2}&\ldots &x_{0}&1\\x_{1}^{n}&x_{1}^{n-1}&x_{1}^{n-2}&\ldots &x_{1}&1\\\vdots &\vdots &\vdots &&\vdots &\vdots \\x_{n}^{n}&x_{n}^{n-1}&x_{n}^{n-2}&\ldots &x_{n}&1\end{bmatrix}}{\begin{bmatrix}a_{n}\\a_{n-1}\\\vdots \\a_{0}\end{bmatrix}}={\begin{bmatrix}y_{0}\\y_{1}\\\vdots \\y_{n}\end{bmatrix}}.$

وسيط $p(x)$ يتوافق مع الحل $A=(a_{n},\ldots ,a_{0})$ معادلة المصفوفة أعلاه $X\cdot A=Y$ المصفوفة X على اليسار هي مصفوفة فاندرموند ، ومحددها معروف بأنه $\textstyle \det(X)=\prod _{0\leq i<j\leq n}(x_{j}-x_{i}),$ وهو غير صفري لأن العقد $x_{j}$ جميعها متميزة. وهذا يضمن أن المصفوفة قابلة للعكس وأن المعادلة لها حل وحيد $A=X^{-1}\cdot Y$ ؛ إنه، $p(x)$ موجود وفريد من نوعه.

نتيجة

لو $f(x)$ هي متعددة حدود من الدرجة على الأكثر $n$ ثم متعددة الحدود الاستيفائية لـ $f(x)$ في $n+1$ النقاط المميزة هي $f(x)$ نفسها.

بناء متعددة الحدود الاستيفائية

استيفاء لاغرانج

يمكننا كتابة متعددة الحدود مباشرة بدلالة متعددات حدود لاغرانج على النحو التالي: ${\begin{aligned}p(x)&={\frac {(x-x_{1})(x-x_{2})\cdots (x-x_{n})}{(x_{0}-x_{1})(x_{0}-x_{2})\cdots (x_{0}-x_{n})}}y_{0}\\[4pt]&+{\frac {(x-x_{0})(x-x_{2})\cdots (x-x_{n})}{(x_{1}-x_{0})(x_{1}-x_{2})\cdots (x_{1}-x_{n})}}y_{1}\\[4pt]&+\cdots \\[4pt]&+{\frac {(x-x_{0})(x-x_{1})\cdots (x-x_{n-1})}{(x_{n}-x_{0})(x_{n}-x_{1})\cdots (x_{n}-x_{n-1})}}y_{n}\\[7pt]&=\sum _{i=0}^{n}{\Biggl (}\prod _{\stackrel {\!0\,\leq \,j\,\leq \,n}{j\,\neq \,i}}{\frac {x-x_{j}}{x_{i}-x_{j}}}{\Biggr )}y_{i}=\sum _{i=0}^{n}{\frac {p(x)}{p'(x_{i})(x-x_{i})}}\,y_{i}\end{aligned}}$ بالنسبة للوسائط المصفوفية، تسمى هذه الصيغة صيغة سيلفستر، وتكون كثيرات حدود لاغرانج ذات القيم المصفوفية هي المتغيرات المشتركة لفروبينيوس .

استيفاء نيوتن

نظرية

لكثير الحدود $p_{n}$ من درجة أقل من أو تساوي $n$ ، الذي يقوم بالإيجاز $f$ عند العقد $x_{i}$ أين $i=0,1,2,3,\cdots ,n$ . يترك $p_{n+1}$ ليكن كثير الحدود من الدرجة الأقل من أو تساوي $n+1$ ذلك الاستيفاء $f$ عند العقد $x_{i}$ أين $i=0,1,2,3,\cdots ,n,n+1$ . ثم $p_{n+1}$ يُعطى بواسطة: $p_{n+1}(x)=p_{n}(x)+a_{n+1}w_{n}(x)$ أين ${\textstyle w_{n}(x):=\prod _{i=0}^{n}(x-x_{i})}$ يُعرف أيضًا باسم أساس نيوتن و ${\textstyle a_{n+1}:={f(x_{n+1})-p_{n}(x_{n+1}) \over w_{n}(x_{n+1})}}$ .

دليل:

ويمكن إثبات ذلك في الحالة التي $i=0,1,2,3,\cdots ,n$ : $p_{n+1}(x_{i})=p_{n}(x_{i})+a_{n+1}\prod _{j=0}^{n}(x_{i}-x_{j})=p_{n}(x_{i})$ ومتى $i=n+1$ : $p_{n+1}(x_{n+1})=p_{n}(x_{n+1})+{f(x_{n+1})-p_{n}(x_{n+1}) \over w_{n}(x_{n+1})}w_{n}(x_{n+1})=f(x_{n+1})$ بفضل تفرد كثيرات الحدود المُستكملة من الدرجة الأقل من $n+1$ ، ${\textstyle p_{n+1}(x)=p_{n}(x)+a_{n+1}w_{n}(x)}$ وهي عملية الاستيفاء متعددة الحدود المطلوبة. وبالتالي، يمكن التعبير عن الدالة على النحو التالي:

${\textstyle p_{n}(x)=a_{0}+a_{1}(x-x_{0})+a_{2}(x-x_{0})(x-x_{1})+\cdots +a_{n}(x-x_{0})\cdots (x-x_{n-1}).}$

معاملات كثير الحدود

للعثور على $a_{i}$ علينا حل المصفوفة المثلثية السفلية المتكونة من ترتيب ${\textstyle p_{n}(x_{i})=f(x_{i})=y_{i}}$ من المعادلة أعلاه في شكل مصفوفة:

{\begin{bmatrix}1&&\ldots &&0\\1&x_{1}-x_{0}&&&\\1&x_{2}-x_{0}&(x_{2}-x_{0})(x_{2}-x_{1})&&\vdots \\\vdots &\vdots &&\ddots &\\1&x_{n}-x_{0}&\ldots &\ldots &\prod _{j=0}^{n-1}(x_{n}-x_{j})\end{bmatrix}}{\begin{bmatrix}a_{0}\\\\\vdots \\\\\\a_{n}\end{bmatrix}}={\begin{bmatrix}y_{0}\\\\\vdots \\\\\\y_{n}\end{bmatrix}}

تُشتق المعاملات على النحو التالي

a_{j}:=[y_{0},\ldots ,y_{j}]

أين

[y_{0},\ldots ,y_{j}]

يُستخدم الرمز للدلالة على الفروق المقسمة . وبالتالي، تُستخدم كثيرات حدود نيوتن لتقديم صيغة استيفاء متعددة الحدود لـ n نقطة. ^{[ 2 ]}

دليل

يمكن حساب المعاملات القليلة الأولى باستخدام نظام المعادلات. ويُفترض شكل المعامل النوني لغرض البرهان بالاستقراء الرياضي.

${\begin{aligned}a_{0}&=y_{0}=[y_{0}]\\a_{1}&={y_{1}-y_{0} \over x_{1}-x_{0}}=[y_{0},y_{1}]\\\vdots \\a_{n}&=[y_{0},\cdots ,y_{n}]\quad {\text{(let)}}\\\end{aligned}}$

ليكن Q استيفاء متعدد الحدود للنقاط $(x_{1},y_{1}),\ldots ,(x_{n},y_{n})$ إضافة $(x_{0},y_{0})$ إلى متعددة الحدود Q:

$Q(x)+a'_{n}(x-x_{1})\cdot \ldots \cdot (x-x_{n})=P_{n}(x),$

أين ${\textstyle a'_{n}(x_{0}-x_{1})\ldots (x_{0}-x_{n})=y_{0}-Q(x_{0})}$ . بفضل تفرد متعددة الحدود الاستيفائية للنقاط $(x_{0},y_{0}),\ldots ,(x_{n},y_{n})$ ، بمساواة معاملات $x^{n-1}$ نحصل على، ${\textstyle a'_{n}=[y_{0},\ldots ,y_{n}]}$ .

وبالتالي يمكن التعبير عن متعددة الحدود على النحو التالي: $P_{n}(x)=Q(x)+[y_{0},\ldots ,y_{n}](x-x_{1})\cdot \ldots \cdot (x-x_{n}).$

إضافة $(x_{n+1},y_{n+1})$ بالنسبة لكثير الحدود Q، يجب أن تحقق ما يلي: ${\textstyle [y_{1},\ldots ,y_{n+1}](x_{n+1}-x_{1})\cdot \ldots \cdot (x_{n+1}-x_{n})=y_{n+1}-Q(x_{n+1})}$ حيث الصيغة لـ ${\textstyle a_{n}}$ ويتم استخدام كثيرات الحدود الاستيفائية. ${\textstyle a_{n+1}}$ مصطلح متعدد الحدود ${\textstyle P_{n+1}}$ يمكن إيجادها عن طريق الحساب: ${\begin{aligned}&[y_{0},\ldots ,y_{n+1}](x_{n+1}-x_{0})\cdot \ldots \cdot (x_{n+1}-x_{n})\\&={\frac {[y_{1},\ldots ,y_{n+1}]-[y_{0},\ldots ,y_{n}]}{x_{n+1}-x_{0}}}(x_{n+1}-x_{0})\cdot \ldots \cdot (x_{n+1}-x_{n})\\&=\left([y_{1},\ldots ,y_{n+1}]-[y_{0},\ldots ,y_{n}]\right)(x_{n+1}-x_{1})\cdot \ldots \cdot (x_{n+1}-x_{n})\\&=[y_{1},\ldots ,y_{n+1}](x_{n+1}-x_{1})\cdot \ldots \cdot (x_{n+1}-x_{n})-[y_{0},\ldots ,y_{n}](x_{n+1}-x_{1})\cdot \ldots \cdot (x_{n+1}-x_{n})\\&=(y_{n+1}-Q(x_{n+1}))-[y_{0},\ldots ,y_{n}](x_{n+1}-x_{1})\cdot \ldots \cdot (x_{n+1}-x_{n})\\&=y_{n+1}-(Q(x_{n+1})+[y_{0},\ldots ,y_{n}](x_{n+1}-x_{1})\cdot \ldots \cdot (x_{n+1}-x_{n}))\\&=y_{n+1}-P(x_{n+1}).\end{aligned}}$ مما يعني أن $a_{n+1}={y_{n+1}-P_{n}(x_{n+1}) \over w_{n}(x_{n+1})}=[y_{0},\ldots ,y_{n+1}]$ .

وبالتالي، يتم إثبات ذلك بمبدأ الاستقراء الرياضي.

صيغة نيوتن الأمامية

يمكن التعبير عن متعددة حدود نيوتن بصيغة مبسطة عندما $x_{0},x_{1},\dots ,x_{k}$ يتم ترتيبها بشكل متتابع مع تباعد متساوٍ.

لو $x_{0},x_{1},\dots ,x_{k}$ مرتبة بشكل متتابع ومتباعدة بمسافات متساوية مع ${x}_{i}={x}_{0}+ih$ بالنسبة لـ i = 0، 1، ...، k ، ويتم التعبير عن متغير ما x على النحو التالي ${x}={x}_{0}+sh$ ثم الفرق $x-x_{i}$ يمكن كتابتها على النحو التالي $(s-i)h$ وبذلك تصبح متعددة حدود نيوتن

{\begin{aligned}N(x)&=[y_{0}]+[y_{0},y_{1}]sh+\cdots +[y_{0},\ldots ,y_{k}]s(s-1)\cdots (s-k+1){h}^{k}\\&=\sum _{i=0}^{k}s(s-1)\cdots (s-i+1){h}^{i}[y_{0},\ldots ,y_{i}]\\&=\sum _{i=0}^{k}{s \choose i}i!{h}^{i}[y_{0},\ldots ,y_{i}].\end{aligned}}

بما أن العلاقة بين الفروق المقسمة والفروق الأمامية معطاة على النحو التالي: ^{[ 3 ]} $[y_{j},y_{j+1},\ldots ,y_{j+n}]={\frac {1}{n!h^{n}}}\Delta ^{(n)}y_{j},$ أخذ $y_{i}=f(x_{i})$ ، إذا تم اعتبار تمثيل x في الأقسام السابقة بدلاً من ذلك $x=x_{j}+sh$ ، تُعبّر صيغة نيوتن للاستيفاء الأمامي على النحو التالي: $f(x)\approx N(x)=N(x_{j}+sh)=\sum _{i=0}^{k}{s \choose i}\Delta ^{(i)}f(x_{j})$ وهو استيفاء جميع النقاط بعد $x_{j}$ ويتم توسيعها على النحو التالي: $f(x_{j}+sh)=f(x_{j})+{\frac {s}{1!}}\Delta f(x_{j})+{\frac {s(s-1)}{2!}}\Delta ^{2}f(x_{j})+{\frac {s(s-1)(s-2)}{3!}}\Delta ^{3}f(x_{j})+{\frac {s(s-1)(s-2)(s-3)}{4!}}\Delta ^{4}f(x_{j})+\cdots$

صيغة نيوتن العكسية

إذا أعيد ترتيب العقد على النحو التالي ${x}_{k},{x}_{k-1},\dots ,{x}_{0}$ تصبح متعددة حدود نيوتن

N(x)=[y_{k}]+[{y}_{k},{y}_{k-1}](x-{x}_{k})+\cdots +[{y}_{k},\ldots ,{y}_{0}](x-{x}_{k})(x-{x}_{k-1})\cdots (x-{x}_{1}).

لو ${x}_{k},\;{x}_{k-1},\;\dots ,\;{x}_{0}$ متباعدة بالتساوي مع ${x}_{i}={x}_{k}-(k-i)h$ لـ i = 0، 1، ...، k و ${x}={x}_{k}+sh$ ، ثم،

{\begin{aligned}N(x)&=[{y}_{k}]+[{y}_{k},{y}_{k-1}]sh+\cdots +[{y}_{k},\ldots ,{y}_{0}]s(s+1)\cdots (s+k-1){h}^{k}\\&=\sum _{i=0}^{k}{(-1)}^{i}{-s \choose i}i!{h}^{i}[{y}_{k},\ldots ,{y}_{k-i}].\end{aligned}}

بما أن العلاقة بين الفروق المقسمة والفروق الخلفية معطاة على النحو التالي: $[{y}_{j},y_{j-1},\ldots ,{y}_{j-n}]={\frac {1}{n!h^{n}}}\nabla ^{(n)}y_{j},$ أخذ $y_{i}=f(x_{i})$ ، إذا تم اعتبار تمثيل x في الأقسام السابقة بدلاً من ذلك $x=x_{j}+sh$ ، تُعبّر صيغة نيوتن للاستيفاء العكسي على النحو التالي: $f(x)\approx N(x)=N(x_{j}+sh)=\sum _{i=0}^{k}{(-1)}^{i}{-s \choose i}\nabla ^{(i)}f(x_{j}).$ وهو استيفاء جميع النقاط قبل $x_{j}$ ويتم توسيعها على النحو التالي: $f(x_{j}+sh)=f(x_{j})+{\frac {s}{1!}}\nabla f(x_{j})+{\frac {s(s+1)}{2!}}\nabla ^{2}f(x_{j})+{\frac {s(s+1)(s+2)}{3!}}\nabla ^{3}f(x_{j})+{\frac {s(s+1)(s+2)(s+3)}{4!}}\nabla ^{4}f(x_{j})+\cdots$

رسم تخطيطي على شكل معين

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

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

يتم التعبير عن العوامل باستخدام الصيغة التالية: $C(u+k,n)={\frac {(u+k)(u+k-1)\cdots (u+k-n+1)}{n!}}$

إثبات التكافؤ

إذا كان المسار يبدأ من $\Delta ^{n-1}y_{s}$ ل $\Delta ^{n+1}y_{s-1}$ ويمكن أن يتم الاتصال من خلال ثلاث خطوات وسيطة، (أ) من خلال $\Delta ^{n}y_{s-1}$ (ب) من خلال ${\textstyle C(u-s,n)}$ أو (ج) من خلال $\Delta ^{n}y_{s}$ . إن إثبات تكافؤ هذه المسارات الثلاثة المكونة من خطوتين يجب أن يثبت أنه يمكن تحويل جميع المسارات (المكونة من n خطوة) بنفس البداية والنهاية، وكلها تمثل نفس الصيغة.

المسار (أ):

$C(u-s,n)\Delta ^{n}y_{s-1}+C(u-s+1,n+1)\Delta ^{n+1}y_{s-1}$

المسار (ب):

$C(u-s,n)\Delta ^{n}y_{s}+C(u-s,n+1)\Delta ^{n+1}y_{s-1}$

المسار (ج):

$C(u-s,n){\frac {\Delta ^{n}y_{s-1}+\Delta ^{n}y_{s}}{2}}\quad +{\frac {C(u-s+1,n+1)+C(u-s,n+1)}{2}}\Delta ^{n+1}y_{s-1}$

طرح المساهمات من المسارين أ و ب:

${\begin{aligned}{\text{Path a - Path b}}=&C(u-s,n)(\Delta ^{n}y_{s-1}-\Delta ^{n}y_{s})+(C(u-s+1,n+1)-C(u-s,n-1))\Delta ^{n+1}y_{s-1}\\=&-C(u-s,n)\Delta ^{n+1}y_{s-1}+C(u-s,n){\frac {(u-s+1)-(u-s-n)}{n+1}}\Delta ^{n+1}y_{s-1}\\=&C(u-s,n)(-\Delta ^{n+1}y_{s-1}+\Delta ^{n+1}y_{s-1})=0\\\end{aligned}}$

وبالتالي، فإن مساهمة كل من المسار (أ) والمسار (ب) متساوية. وبما أن المسار (ج) هو متوسط المسارين (أ) و(ب)، فإنه يُساهم أيضًا بنفس الدالة في كثير الحدود. ومن ثم، يتضح تكافؤ المسارات ذات نقاط البداية والنهاية نفسها. وللتحقق مما إذا كان بالإمكان تحريك المسارات إلى قيم مختلفة في الزاوية اليسرى، يكفي أخذ مسارين فقط: (أ) $y_{s+1}$ ل $y_{s}$ خلال $\Delta y_{s}$ أو (ب) عامل بين $y_{s+1}$ و $y_{s}$ ، ل $y_{s}$ خلال $\Delta y_{s}$ أو (ج) بدءاً من $y_{s}$ .

المسار (أ)

$y_{s+1}+C(u-s-1,1)\Delta y_{s}-C(u-s,1)\Delta y_{s}$

المسار (ب)

${\frac {y_{s+1}+y_{s}}{2}}+{\frac {C(u-s-1,1)+C(u-s,1)}{2}}\Delta y_{s}-C(u-s,1)\Delta y_{s}$

المسار (ج)

$y_{s}$

منذ $\Delta y_{s}=y_{s+1}-y_{s}$ وبتعويض المعادلات أعلاه، يتضح أن جميع الحدود المذكورة أعلاه تختزل إلى $y_{s}$ وبالتالي فهما متكافئان. ومن ثم يمكن تحويل هذه المسارات لتبدأ من الزاوية اليسرى وتنتهي عند نقطة مشتركة. ^{[ 4 ]}

صيغة نيوتن

بأخذ المقطع العرضي ذي الميل السالب من $y_{0}$ ل $\Delta ^{n}y_{0}$ تعطي صيغة الاستيفاء لجميع $n+1$ نقاط مرتبة بشكل متتابع، تعادل صيغة نيوتن للاستيفاء الأمامي:

${\begin{aligned}y(s)&=y_{0}+C(s,1)\Delta y_{0}+C(s,2)\Delta ^{2}y_{0}+C(s,3)\Delta ^{3}y_{0}+\cdots \\&=y_{0}+s\Delta y_{0}+{\frac {s(s-1)}{2}}\Delta ^{2}y_{0}+{\frac {s(s-1)(s-2)}{3!}}\Delta ^{3}y_{0}+{\frac {s(s-1)(s-2)(s-3)}{4!}}\Delta ^{4}y_{0}+\cdots \end{aligned}}$

بينما، بأخذ الميل الموجب المستعرض من $y_{n}$ ل $\nabla ^{n}y_{n}=\Delta ^{n}y_{0}$ ، تعطي صيغة الاستيفاء لجميع $n+1$ نقاط مرتبة بشكل متتابع، تعادل صيغة نيوتن للاستيفاء العكسي:

${\begin{aligned}y(u)&=y_{k}+C(u-k,1)\Delta y_{k-1}+C(u-k+1,2)\Delta ^{2}y_{k-2}+C(u-k+2,3)\Delta ^{3}y_{k-3}+\cdots \\&=y_{k}+(u-k)\Delta y_{k-1}+{\frac {(u-k+1)(u-k)}{2}}\Delta ^{2}y_{k-2}+{\frac {(u-k+2)(u-k+1)(u-k)}{3!}}\Delta ^{3}y_{k-3}+\cdots \\y(k+s)&=y_{k}+(s)\nabla y_{k}+{\frac {(s+1)s}{2}}\nabla ^{2}y_{k}+{\frac {(s+2)(s+1)s}{3!}}\nabla ^{3}y_{k}+{\frac {(s+3)(s+2)(s+1)s}{4!}}\nabla ^{4}y_{k}+\cdots \\\end{aligned}}$

أين $s=u-k$ هو الرقم المقابل للرقم المُدخل في استيفاء نيوتن.

صيغة جاوس

اتخاذ خط متعرج نحو اليمين بدءًا من $y_{0}$ مع ميل سالب، نحصل على صيغة جاوس الأمامية:

$y(u)=y_{0}+u\Delta y_{0}+{\frac {u(u-1)}{2}}\Delta ^{2}y_{-1}+{\frac {(u+1)u\left(u-1\right)}{3!}}\Delta ^{3}y_{-1}+{\frac {(u+1)u\left(u-1\right)(u-2)}{4!}}\Delta ^{4}y_{-2}+\cdots$

بينما يبدأ من $y_{0}$ وبميل موجب، نحصل على صيغة جاوس العكسية:

$y(u)=y_{0}+u\Delta y_{-1}+{\frac {(u+1)u}{2}}\Delta ^{2}y_{-1}+{\frac {(u+1)u\left(u-1\right)}{3!}}\Delta ^{3}y_{-2}+{\frac {(u+2)(u+1)u\left(u-1\right)}{4!}}\Delta ^{4}y_{-2}+\cdots$

تركيبة ستيرلينغ

باتباع مسار أفقي نحو اليمين بدءًا من $y_{0}$ ، فنحصل على صيغة ستيرلينغ:

${\begin{aligned}y(u)&=y_{0}+u{\frac {\Delta y_{0}+\Delta y_{-1}}{2}}+{\frac {C(u+1,2)+C(u,2)}{2}}\Delta ^{2}y_{-1}+C(u+1,3){\frac {\Delta ^{3}y_{-2}+\Delta ^{3}y_{-1}}{2}}+\cdots \\&=y_{0}+u{\frac {\Delta y_{0}+\Delta y_{-1}}{2}}+{\frac {u^{2}}{2}}\Delta ^{2}y_{-1}+{\frac {u(u^{2}-1)}{3!}}{\frac {\Delta ^{3}y_{-2}+\Delta ^{3}y_{-1}}{2}}+{\frac {u^{2}(u^{2}-1)}{4!}}\Delta ^{4}y_{-2}+\cdots \end{aligned}}$

صيغة ستيرلينغ هي متوسط صيغتي غاوس الأمامية والخلفية.

صيغة بيسل

باتباع مسار أفقي نحو اليمين بدءًا من العامل بين $y_{0}$ و $y_{1}$ ، فنحصل على صيغة بيسل:

${\begin{aligned}y(u)&=1{\frac {y_{0}+y_{1}}{2}}+{\frac {C(u,1)+C(u-1,1)}{2}}\Delta y_{0}+C(u,2){\frac {\Delta ^{2}y_{-1}+\Delta ^{2}y_{0}}{2}}+\cdots \\&={\frac {y_{0}+y_{1}}{2}}+\left(u-{\frac {1}{2}}\right)\Delta y_{0}+{\frac {u(u-1)}{2}}{\frac {\Delta ^{2}y_{-1}+\Delta ^{2}y_{0}}{2}}+{\frac {\left(u-{\frac {1}{2}}\right)u\left(u-1\right)}{3!}}\Delta ^{3}y_{0}+{\frac {(u+1)u(u-1)(u-2)}{4!}}{\frac {\Delta ^{4}y_{-1}+\Delta ^{4}y_{-2}}{2}}+\cdots \\\end{aligned}}$

خوارزميات فاندرموند

قد يكون لمصفوفة فاندرموند في البرهان الثاني أعلاه رقم حالة كبير ، ^{[ 5 ]} مما يتسبب في أخطاء كبيرة عند حساب المعاملات $a i$ إذا تم حل نظام المعادلات باستخدام طريقة الحذف الغاوسي .

^{لذلك ،} اقترح العديد من المؤلفين خوارزميات تستغل بنية مصفوفة فانديرموند لحساب حلول مستقرة عدديًا في O( n² ) عملية بدلًا من O( n³ ) المطلوبة في طريقة الحذف الغاوسي. ^[⁶^]^[⁷^]^[⁸^] تعتمد هذه الطرق على إنشاء استيفاء نيوتن لكثير الحدود أولًا ^، ثم تحويله إلى صيغة أحادية الحد .

خوارزميات غير فاندرموند

لإيجاد متعددة الحدود الاستيفائية p ( x ) في فضاء المتجهات P ( n ) لمتعددات الحدود من الدرجة $n$ ، يمكننا استخدام أساس أحادي الحد المعتاد لـ P ( n ) وعكس مصفوفة فانديرموند باستخدام طريقة الحذف الغاوسي، مما ينتج عنه تكلفة حسابية من ^رتبة O( n³ ) عملية. ولتحسين هذه الخوارزمية، يمكن لأساس أكثر ملاءمة لـ P ( n ) تبسيط حساب المعاملات، والتي يجب ترجمتها لاحقًا إلى أساس أحادي الحد .

إحدى الطرق هي كتابة متعددة الحدود للاستيفاء بصيغة نيوتن (أي باستخدام أساس نيوتن) واستخدام طريقة الفروق المقسمة لحساب المعاملات، مثل خوارزمية نيفيل . تبلغ تكلفة هذه ^{الطريقة} O( n² ) عملية حسابية. علاوة على ذلك، لا تحتاج إلا إلى O( n ) من العمليات الإضافية عند إضافة نقطة جديدة إلى مجموعة البيانات، بينما في الطرق الأخرى، يجب إعادة الحساب بالكامل.

يُفضّل استخدام طريقة أخرى عندما لا يكون الهدف هو حساب معاملات p ( x )، وإنما قيمة واحدة فقط p ( a ) عند نقطة x = a غير موجودة في مجموعة البيانات الأصلية. تحسب صيغة لاغرانج القيمة p ( a ) بتعقيد زمني O( ^n²) . ^[⁹^]

تم استخدام شكل برنشتاين في برهان بناء لنظرية تقريب فايرشتراس بواسطة برنشتاين واكتسب أهمية كبيرة في رسومات الحاسوب في شكل منحنيات بيزير .

الاستيفاءات كمجموعات خطية من القيم

بالنظر إلى مجموعة من نقاط البيانات (الموقع، القيمة) $(x_{0},y_{0}),\ldots ,(x_{j},y_{j}),\ldots ,(x_{n},y_{n})$ حيث لا يوجد موقفان $x_{j}$ هي نفسها، متعددة الحدود الاستيفائية $y(x)$ يمكن اعتبارها توليفة خطية من القيم $y_{j}$ باستخدام معاملات هي كثيرات حدود في $x$ بحسب $x_{j}$ على سبيل المثال، تعد كثيرة الحدود الاستيفائية في صيغة لاغرانج عبارة عن تركيبة خطية $y(x):=\sum _{j=0}^{k}y_{j}c_{j}(x)$ مع كل معامل $c_{j}(x)$ معطاة بواسطة متعددة حدود أساس لاغرانج المناظرة على المواضع المعطاة $x_{j}$ : $c_{j}(x)=L_{j}(x_{0},\ldots ,x_{n};x)=\prod _{0\leq i\leq n \atop i\neq j}{\frac {x-x_{i}}{x_{j}-x_{i}}}={\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_{n})}{(x_{j}-x_{n})}}.$

بما أن المعاملات تعتمد فقط على المواضع $x_{j}$ وليس القيم $y_{j}$ يمكننا استخدام نفس المعاملات لإيجاد متعددة الحدود الاستيفائية لمجموعة ثانية من نقاط البيانات $(x_{0},v_{0}),\ldots ,(x_{n},v_{n})$ في نفس المناصب: $v(x):=\sum _{j=0}^{k}v_{j}c_{j}(x).$

علاوة على ذلك، المعاملات $c_{j}(x)$ يعتمد فقط على المساحات النسبية $x_{i}-x_{j}$ بين المواضع. وبالتالي، بالنظر إلى مجموعة بيانات ثالثة تُعطى نقاطها بواسطة المتغير الجديد $t=ax+b$ ( تحويل أفيني لـ $x$ ، معكوسة بواسطة $x={\tfrac {t-b}{a}}$ ): $(t_{0},w_{0}),\ldots ,(t_{j},w_{j})\ldots ,(t_{n},w_{n})\qquad {\text{with}}\qquad t_{j}=ax_{j}+b,$

يمكننا استخدام نسخة مُحوَّلة من كثيرات الحدود ذات المعاملات السابقة:

${\tilde {c}}_{j}(t):=c_{j}({\tfrac {t-b}{a}})=c_{j}(x),$

واكتب متعددة الحدود الاستيفائية على النحو التالي:

${\textstyle w(t):=\sum _{j=0}^{k}w_{j}{\tilde {c}}_{j}(t).}$

نقاط البيانات $(x_{j},y_{j})$ غالبًا ما تكون مواقعها متساوية التباعد ، والتي يمكن تطبيعها عن طريق تحويل خطي إلى $x_{j}=j$ على سبيل المثال، انظر إلى نقاط البيانات

$(0,y_{0}),(1,y_{1}),(2,y_{2})$ .

تعد كثيرة الحدود الاستيفائية في صيغة لاغرانج عبارة عن تركيبة خطية

${\begin{aligned}y(x):=\sum _{j=0}^{2}y_{j}c_{j}(x)&=y_{0}{\frac {(x-1)(x-2)}{(0-1)(0-2)}}+y_{1}{\frac {(x-0)(x-2)}{(1-0)(1-2)}}+y_{2}{\frac {(x-0)(x-1)}{(2-0)(2-1)}}\\&={\tfrac {1}{2}}y_{0}(x-1)(x-2)-y_{1}(x-0)(x-2)+{\tfrac {1}{2}}y_{2}(x-0)(x-1).\end{aligned}}$

على سبيل المثال، $y(3)=y_{3}=y_{0}-3y_{1}+3y_{2}$ و $y(1.5)=y_{1.5}={\tfrac {1}{8}}(-y_{0}+6y_{1}+3y_{2})$ .

يمكن أيضًا معالجة حالة النقاط المتساوية التباعد باستخدام طريقة الفروق المحدودة . الفرق الأول لسلسلة من القيم $v=\{v_{j}\}_{j=0}^{\infty }$ التسلسل $\Delta v=u=\{u_{j}\}_{j=0}^{\infty }$ محدد بواسطة $u_{j}=v_{j+1}-v_{j}$ تكرار هذه العملية يعطي عملية الفرق ^رقمn $\Delta ^{n}v=u$ ، كما هو محدد صراحةً بواسطة $u_{j}=\sum _{k=0}^{n}(-1)^{n-k}{n \choose k}v_{j+k}.$

متعدد الحدود $y(x)$ تُعرّف الدرجة d سلسلة من القيم عند نقاط الأعداد الصحيحة الموجبة، $y_{j}=y(j)$ و $(d+1)^{\text{th}}$ الفرق بين عناصر هذه المتتالية يساوي صفرًا تمامًا:

$\Delta ^{d+1}y=0$ .

وبالتالي، القيم المعطاة $y_{0},\ldots ,y_{n}$ عند نقاط متباعدة بالتساوي، حيث $n=d+1$ لدينا: $(-1)^{n}y_{0}+(-1)^{n-1}{\binom {n}{1}}y_{1}+\cdots -{\binom {n}{n-1}}y_{n-1}+y_{n}=0.$ على سبيل المثال، 4 نقاط بيانات متباعدة بالتساوي $y_{0},y_{1},y_{2},y_{3}$ من الدرجة الثانية $y(x)$ يطيع $0=-y_{0}+3y_{1}-3y_{2}+y_{3}$ ، وحل المعادلة لـ $y_{3}$ يعطي نفس معادلة الاستيفاء التي تم الحصول عليها أعلاه باستخدام طريقة لاغرانج.

خطأ الاستيفاء: صيغة باقي لاغرانج

عند استيفاء دالة معينة f بواسطة متعددة الحدود $p_{n}$ عند العقد من الدرجة $n،$ _x0، ...، xn _، نحصل على الخطأ $f(x)-p_{n}(x)=f[x_{0},\ldots ,x_{n},x]\prod _{i=0}^{n}(x-x_{i})$

أين ${\textstyle f[x_{0},\ldots ,x_{n},x]}$ هو الفرق المقسم ⁽ن + 1) لنقاط البيانات

$(x_{0},f(x_{0})),\ldots ,(x_{n},f(x_{n})),(x,f(x))$ .

علاوة على ذلك، يوجد شكل باقي لاغرانج للخطأ، لدالة f قابلة للتفاضل بشكل مستمر $n + 1$ مرة على فترة مغلقة $I$ ، ومتعددة الحدود $p_{n}(x)$ من الدرجة التي لا تتجاوز $n$ والتي تقوم باستيفاء f عند $n + 1$ نقطة مميزة $x_{0},\ldots ,x_{n}\in I$ لكل $x\in I$ يوجد $\xi \in I$ بحيث

$f(x)-p_{n}(x)={\frac {f^{(n+1)}(\xi )}{(n+1)!}}\prod _{i=0}^{n}(x-x_{i}).$

$يشير$ حد الخطأ هذا إلى اختيار نقاط الاستيفاء $xᵢ$ لتقليل حاصل الضرب ${\textstyle \left|\prod (x-x_{i})\right|}$ ، وهو ما يتم تحقيقه بواسطة عقد تشيبيشيف .

إثبات باقي لاغرانج

حدد حد الخطأ على النحو التالي ${\textstyle R_{n}(x)=f(x)-p_{n}(x)}$ ، وتحديد دالة مساعدة : $Y(t)=R_{n}(t)-{\frac {R_{n}(x)}{W(x)}}W(t)\qquad {\text{where}}\qquad W(t)=\prod _{i=0}^{n}(t-x_{i}).$ هكذا: $Y^{(n+1)}(t)=R_{n}^{(n+1)}(t)-{\frac {R_{n}(x)}{W(x)}}\ (n+1)!$

لكن منذ $p_{n}(x)$ إذا كانت كثيرة حدود من الدرجة $n$ على الأكثر ، فلدينا ${\textstyle R_{n}^{(n+1)}(t)=f^{(n+1)}(t)}$ ، و: $Y^{(n+1)}(t)=f^{(n+1)}(t)-{\frac {R_{n}(x)}{W(x)}}\ (n+1)!$

الآن، بما أن $xᵢ هي$ جذور لـ $R_{n}(t)$ و $W(t)$ لدينا $Y(x)=Y(x_{j})=0$ وهذا يعني أن $Y$ لها على الأقل $n + 2$ جذرًا. من نظرية رول ، $Y^{\prime }(t)$ لها على الأقل $n + 1$ جذر، وبشكل تكراري $Y^{(n+1)}(t)$ للمعادلة جذر واحد على الأقل $ξ$ في الفترة $I.$ وبالتالي: $Y^{(n+1)}(\xi )=f^{(n+1)}(\xi )-{\frac {R_{n}(x)}{W(x)}}\ (n+1)!=0$

و: $R_{n}(x)=f(x)-p_{n}(x)={\frac {f^{(n+1)}(\xi )}{(n+1)!}}\prod _{i=0}^{n}(x-x_{i}).$

يوازي هذا المنطقَ الكامن وراء حدّ لاغرانج المتبقي في نظرية تايلور ؛ في الواقع، يُعدّ باقي تايلور حالةً خاصةً من خطأ الاستيفاء عندما تكون جميع نقاط الاستيفاء $xᵢ$ $متطابقة$ . ^{[ 10 ]} لاحظ أن الخطأ سيكون صفرًا عندما $x=x_{i}$ لأي قيمة لـ i . وبالتالي، سيحدث الحد الأقصى للخطأ عند نقطة ما في الفترة الفاصلة بين عقدتين متتاليتين.

فترات زمنية متساوية

في حالة عقد الاستيفاء المتباعدة بالتساوي حيث $x_{i}=a+ih$ ، ل $i=0,1,\ldots ,n,$ وأين $h=(b-a)/n,$ يمكن تحديد حد الضرب في صيغة خطأ الاستيفاء على النحو التالي ^{[ 11 ]} $\left|\prod _{i=0}^{n}(x-x_{i})\right|=\prod _{i=0}^{n}\left|x-x_{i}\right|\leq {\frac {n!}{4}}h^{n+1}.$

وبالتالي يمكن التعبير عن حد الخطأ على النحو التالي $\left|R_{n}(x)\right|\leq {\frac {h^{n+1}}{4(n+1)}}\max _{\xi \in [a,b]}\left|f^{(n+1)}(\xi )\right|$

لكن هذا يفترض أن $f^{(n+1)}(\xi )$ يهيمن عليها $h^{n+1}$ ، أي $f^{(n+1)}(\xi )h^{n+1}\ll 1$ في عدة حالات، لا يصح هذا، بل يزداد الخطأ فعلياً مع ازدياد قيمة $n إلى ما لا نهاية$ (انظر ظاهرة رونج ). وقد تم تناول هذه المسألة في قسم خصائص التقارب .

ثوابت ليبيغ

نُثبّت نقاط الاستيفاء x₀ _، ...، xₙ _، والفترة [ a , b ] التي تحتوي على جميع نقاط الاستيفاء. تُحوّل عملية الاستيفاء الدالة f إلى متعددة حدود p . يُعرّف هذا تحويلاً X من الفضاء C ([ a , b ]) لجميع الدوال المتصلة على [ a , b ] إلى نفسه. التحويل X خطي، وهو إسقاط على الفضاء الجزئي . $P(n)$ من كثيرات الحدود من الدرجة n أو أقل.

يُعرَّف ثابت ليبيغ L بأنه معيار المؤثر X. وهذا (حالة خاصة من مبرهنة ليبيغ ) : $\left\|f-X(f)\right\|\leq (L+1)\left\|f-p^{*}\right\|.$

بمعنى آخر، تكون قيمة متعددة الحدود للاستيفاء أسوأ من أفضل تقريب ممكن بمعامل ( L + 1) على الأكثر. وهذا يشير إلى ضرورة البحث عن مجموعة من نقاط الاستيفاء التي تجعل L صغيرة. وعلى وجه الخصوص، لدينا بالنسبة لنقاط تشيبيشيف : $L\leq {\frac {2}{\pi }}\log(n+1)+1.$

نستنتج مجدداً أن عقد تشيبيشيف خيارٌ جيدٌ جداً للاستيفاء متعدد الحدود، إذ أن نمو n يكون أُسّياً للعقد متساوية البعد. مع ذلك، فإن هذه العقد ليست مثالية.

خصائص التقارب

من الطبيعي أن نتساءل، ما هي فئات الدوال، وما هي نقاط الاستيفاء التي يتقارب عندها تسلسل كثيرات الحدود المستوفية إلى الدالة المستوفية عندما $n \to \infty$ ؟ يمكن فهم التقارب بطرق مختلفة، على سبيل المثال، نقطيًا، أو منتظمًا، أو في معيار تكاملي ما.

الوضع سيء للغاية بالنسبة للعقد متساوية البعد، إذ لا يُضمن التقارب المنتظم حتى للدوال القابلة للتفاضل بلا حدود. أحد الأمثلة الكلاسيكية، التي وضعها كارل رونج ، هي الدالة f ( x ) = 1/(1 + x² ) على الفترة $[-5, 5]$ ^. يزداد خطأ الاستيفاء $||$ $f$ $-$ $pn$ $||$ $بلا حدود عندما n$ $\to \infty$ $.$ $مثال$ آخر هو الدالة f ( x ) = | x | على الفترة $[-1, 1]$ ، حيث لا تتقارب كثيرات الحدود المستوفاة نقطيًا إلا عند النقاط الثلاث x = ±1, 0. ^[¹²^]

قد يظن المرء أنه يمكن الحصول على خصائص تقارب أفضل باختيار نقاط استيفاء مختلفة. ويبدو أن النتيجة التالية تقدم إجابة مشجعة إلى حد ما:

نظرية — لأي دالة f ( x ) متصلة على الفترة [ a , b ]، يوجد جدول للعقد التي يكون عندها تسلسل كثيرات الحدود الاستيفائية $p_{n}(x)$ يتقارب إلى f ( x ) بشكل منتظم على [ a , b ].

دليل

من الواضح أن متتالية كثيرات الحدود ذات أفضل تقريب $p_{n}^{*}(x)$ يتقارب إلى f ( x ) بانتظام (بسبب نظرية تقريب فايرشتراس ). الآن علينا فقط أن نثبت أن كل $p_{n}^{*}(x)$ يمكن الحصول على ذلك عن طريق الاستيفاء عند نقاط معينة. لكن هذا صحيح بسبب خاصية خاصة لكثيرات الحدود ذات أفضل تقريب، والمعروفة من نظرية التذبذب المتساوي . تحديدًا، نعلم أن هذه كثيرات الحدود يجب أن تتقاطع مع f ( x ) على الأقل $n + 1$ مرة. باختيار نقاط التقاطع كنقاط استيفاء، نحصل على كثيرة الحدود المستوفاة التي تتطابق مع كثيرة الحدود ذات أفضل تقريب.

لكنّ عيب هذه الطريقة يكمن في ضرورة حساب نقاط الاستيفاء من جديد لكل دالة جديدة f ( x )، إلا أن تطبيق الخوارزمية عدديًا أمرٌ صعب. هل يوجد جدول واحد للنقاط التي تتقارب عندها متتالية كثيرات الحدود المستوفية إلى أي دالة متصلة f ( x )؟ للأسف، الإجابة هي لا.

نظرية — لأي جدول من العقد، توجد دالة متصلة f ( x ) على الفترة [ a , b ] بحيث تتباعد متتالية كثيرات الحدود الاستيفائية على الفترة [ a , b ]. ^{[ 13 ]}

تعتمد البرهنة أساسًا على تقدير الحد الأدنى لثابت ليبيغ ، الذي عرّفناه أعلاه بأنه معيار المؤثر X _n (حيث X _n هو مؤثر الإسقاط على Π _n ). الآن نبحث عن جدول للعقد التي تحقق

$\lim _{n\to \infty }X_{n}f=f,{\text{ for every }}f\in C([a,b]).$

بسبب نظرية باناخ-شتاينهاوس ، لا يكون هذا ممكناً إلا عندما تكون معايير X _n محدودة بشكل منتظم، وهو أمر غير ممكن لأننا نعلم أن

$\|X_{n}\|\geq {\tfrac {2}{\pi }}\log(n+1)+C.$

على سبيل المثال، إذا تم اختيار نقاط متساوية البعد كعقد استيفاء، فإن الدالة الناتجة عن ظاهرة رونج تُظهر تباعد هذا الاستيفاء. تجدر الإشارة إلى أن هذه الدالة ليست متصلة فحسب، بل قابلة للتفاضل إلى ما لا نهاية على الفترة $[-1, 1] . مع ذلك، بالنسبة$ لعقد تشيبيشيف الأفضل ، يصعب إيجاد مثال كهذا بسبب النتيجة التالية:

نظرية — لكل دالة متصلة تمامًا على الفترة $[-1, 1]،$ فإن متتالية كثيرات الحدود الاستيفائية المبنية على عقد تشيبيشيف تتقارب إلى f ( x ) بانتظام. ^[¹⁴^]

مفاهيم ذات صلة

تُظهر ظاهرة رونج أنه عند القيم العالية لـ $n$ ، قد يتذبذب كثير الحدود المستخدم في الاستيفاء بشكل كبير بين نقاط البيانات. تُحل هذه المشكلة عادةً باستخدام استيفاء الدوال التكعيبية . في هذه الحالة، لا يكون المُستَوفى كثير حدود، بل دالة تكعيبية : وهي سلسلة من عدة كثيرات حدود من درجة أقل.

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

تُعرف مسائل استيفاء هيرميت بأنها تلك التي لا تُعطى فيها قيم متعددة الحدود p عند العقد فحسب، بل تُعطى فيها أيضًا جميع المشتقات حتى رتبة معينة. وهذا يُكافئ نظامًا من تطابقات متعددة الحدود المتزامنة، ويمكن حله باستخدام نظرية الباقي الصينية لمتعددات الحدود. أما استيفاء بيركوف فهو تعميم آخر حيث تُحدد فيه مشتقات بعض الرتب فقط، وليس بالضرورة جميع الرتب من 0 إلى k .

تعتمد طرق التجميع لحل المعادلات التفاضلية والتكاملية على الاستيفاء متعدد الحدود.

تُعد تقنية نمذجة الدوال الكسرية تعميماً يأخذ في الاعتبار نسب الدوال متعددة الحدود.

وأخيرًا، الاستيفاء متعدد المتغيرات للأبعاد الأعلى.

انظر أيضاً

ملحوظات

↑ هذا يتبع من نظرية العامل لقسمة كثيرات الحدود.

الاقتباسات

↑ همفريز، جيفري؛ جارفيس، تايلر جيه. (2020). "9.2 - الاستيفاء". أسس الرياضيات التطبيقية، المجلد 2: الخوارزميات، والتقريب، والتحسين . جمعية الرياضيات الصناعية والتطبيقية. ص 418. ISBN 978-1-611976-05-2.
1 2 إيبيرسون، جيمس ف. (2013). مقدمة في الأساليب والتحليل العددي ( الطبعة الثانية). هوبوكين، نيوجيرسي: وايلي. ISBN 978-1-118-36759-9.
↑ بيردن ، ريتشارد ل.؛ فيرز، ج. دوغلاس (2011). التحليل العددي ( الطبعة التاسعة). سينجايج ليرنينج. ص 129. ISBN 9780538733519.
1 2 هامينغ، ريتشارد و. (1986). الأساليب العددية للعلماء والمهندسين (إعادة نشر كاملة للطبعة الثانية (1973) ). نيويورك: دوفر. ISBN 978-0-486-65241-2.
^ جاوتشي ، والتر (1975). “التقديرات المعيارية لعكسات مصفوفات فاندرموند”. الرياضيات الرقمية . 23 (4): 337-347 . دوى : 10.1007 / BF01438260 . S2CID 122300795 .
↑ هايغام، ن. ج. (1988). "الحل السريع لأنظمة فاندرموند التي تتضمن كثيرات حدود متعامدة". مجلة IMA للتحليل العددي . 8 (4): 473-486 . doi : 10.1093/imanum/8.4.473 .
↑ بيورك، أ؛ ف. بيريرا (1970). "حل أنظمة معادلات فاندرموند". رياضيات الحساب . 24 (112). الجمعية الرياضية الأمريكية: 893-903 . doi : 10.2307/2004623 . JSTOR 2004623 .
↑ كالفيتي، د .؛ رايشل، ل. (1993). "الانعكاس السريع للمصفوفات الشبيهة بمصفوفات فانديرموند التي تتضمن كثيرات حدود متعامدة". BIT . 33 (3): 473–484 . doi : 10.1007/BF01990529 . S2CID 119360991 .
^ ر.بيفيلاكوا، د. بيني، م.كابوفاني و أو. مينشي (2003). Appunti di Calcolo Numerico . الفصل 5، ص. 89. خدمة التحرير Universitario Pisa - Azienda Regionale Diritto allo Studio Universitario.
↑ "أخطاء في الاستيفاء متعدد الحدود" (PDF) .
↑ "ملاحظات حول الاستيفاء متعدد الحدود" (PDF) .
↑ ينسب واتسون (1980 ، ص 21) المثال الأخير إلى بيرنشتاين (1912) .
↑ ينسب واتسون (1980 ، ص 21) هذه النظرية إلى فابر (1914) .
^ كريلوف السادس (1956). "إن الاستيطان الجبرى يشجع كثيرًا على الوظائف والوظائف غير المطلقة ограниченным изменением" [ تقارب الاستيفاء الجبري فيما يتعلق بجذور كثيرة حدود تشيبيشيف للوظائف المستمرة تمامًا ووظائف التباين المحدود ] . دوكلادي أكاديمي ناوك SSSR . سلسلة جديدة (بالروسية). 107 : 362– 365.MR 18-32.

مراجع

بيرنشتاين، سيرجي ن. (1912). "Sur l'ordre de la meilleure approximation des fonctions continue par les polynômes de degré donné" [ في ترتيب أفضل تقريب للدوال المستمرة بواسطة كثيرات الحدود بدرجة معينة ] . م. أكاد. روي. بلجيكا. (باللغة الفرنسية). 4 : 1 – 104.
فابر، جورج (1914). "Über die interpolatorische Darstellung stetiger Funktionen" [ حول استيفاء الدوال المستمرة ] . الرياضيات الألمانية. جهر. (باللغة الألمانية). 23 : 192 – 210.
واتسون، جي. أليستير (1980). نظرية التقريب والأساليب العددية . جون وايلي. ISBN 0-471-27706-1.

للمزيد من القراءة

أتكينسون، كينديل أ. (1988). "الفصل 3". مقدمة في التحليل العددي ( الطبعة الثانية). جون وايلي وأولاده. ISBN 0-471-50023-2.
بروتمان، ل. (1997). "دوال ليبيغ للاستيفاء متعدد الحدود - دراسة استقصائية". حوليات الرياضيات العددية 4 : 111-127 .
باول، إم جيه دي (1981). "الفصل 4". نظرية التقريب وأساليبه . مطبعة جامعة كامبريدج. ISBN 0-521-29514-9.
شاتزمان، ميشيل (2002). "الفصل 4". التحليل العددي: مقدمة رياضية . أكسفورد: مطبعة كلارندون. ISBN 0-19-850279-6.
سولي، إندري ؛ مايرز، ديفيد (2003). "الفصل 6". مقدمة في التحليل العددي . مطبعة جامعة كامبريدج. ISBN 0-521-00794-1.

جيه إل والش: الاستيفاء والتقريب باستخدام الدوال الكسرية في المجال المركب ، منشورات الجمعية الأمريكية للرياضيات (سلسلة منشورات كولكيوم، المجلد 20)، رقم ISBN 0-8218-1020-0 (1960). الفصل السابع: «الاستيفاء باستخدام كثيرات الحدود».

روابط خارجية

"عملية الاستيفاء" ، موسوعة الرياضيات ، دار نشر EMS ، 2001 [1994]
يحتوي ALGLIB على تطبيقات بلغة C++ / C#.
تحتوي مكتبة GSL على كود استيفاء متعدد الحدود مكتوب بلغة C
عرض توضيحي للاستيفاء متعدد الحدود .

[2] هذا يتبع من نظرية العامل لقسمة كثيرات الحدود.

[1] همفريز، جيفري؛ جارفيس، تايلر جيه. (2020). "9.2 - الاستيفاء". أسس الرياضيات التطبيقية، المجلد 2: الخوارزميات، والتقريب، والتحسين . جمعية الرياضيات الصناعية والتطبيقية. ص 418. ISBN 978-1-611976-05-2.

[Epperson_2013-3] 1 2 إيبيرسون، جيمس ف. (2013). مقدمة في الأساليب والتحليل العددي ( الطبعة الثانية). هوبوكين، نيوجيرسي: وايلي. ISBN 978-1-118-36759-9.

[4] بيردن ، ريتشارد ل.؛ فيرز، ج. دوغلاس (2011). التحليل العددي ( الطبعة التاسعة). سينجايج ليرنينج. ص 129. ISBN 9780538733519.

[:0-5] 1 2 هامينغ، ريتشارد و. (1986). الأساليب العددية للعلماء والمهندسين (إعادة نشر كاملة للطبعة الثانية (1973) ). نيويورك: دوفر. ISBN 978-0-486-65241-2.

[6] جاوتشي ، والتر (1975). “التقديرات المعيارية لعكسات مصفوفات فاندرموند”. الرياضيات الرقمية . 23 (4): 337-347 . دوى : 10.1007 / BF01438260 . S2CID 122300795 .

[7] هايغام، ن. ج. (1988). "الحل السريع لأنظمة فاندرموند التي تتضمن كثيرات حدود متعامدة". مجلة IMA للتحليل العددي . 8 (4): 473-486 . doi : 10.1093/imanum/8.4.473 .

[8] بيورك، أ؛ ف. بيريرا (1970). "حل أنظمة معادلات فاندرموند". رياضيات الحساب . 24 (112). الجمعية الرياضية الأمريكية: 893-903 . doi : 10.2307/2004623 . JSTOR 2004623 .

[9] كالفيتي، د .؛ رايشل، ل. (1993). "الانعكاس السريع للمصفوفات الشبيهة بمصفوفات فانديرموند التي تتضمن كثيرات حدود متعامدة". BIT . 33 (3): 473–484 . doi : 10.1007/BF01990529 . S2CID 119360991 .

[10] ر.بيفيلاكوا، د. بيني، م.كابوفاني و أو. مينشي (2003). Appunti di Calcolo Numerico . الفصل 5، ص. 89. خدمة التحرير Universitario Pisa - Azienda Regionale Diritto allo Studio Universitario.

[11] "أخطاء في الاستيفاء متعدد الحدود" (PDF) .

[12] "ملاحظات حول الاستيفاء متعدد الحدود" (PDF) .

[13] ينسب واتسون (1980 ، ص 21) المثال الأخير إلى بيرنشتاين (1912) .

[14] ينسب واتسون (1980 ، ص 21) هذه النظرية إلى فابر (1914) .

[15] كريلوف السادس (1956). "إن الاستيطان الجبرى يشجع كثيرًا على الوظائف والوظائف غير المطلقة ограниченным изменением" [ تقارب الاستيفاء الجبري فيما يتعلق بجذور كثيرة حدود تشيبيشيف للوظائف المستمرة تمامًا ووظائف التباين المحدود ] . دوكلادي أكاديمي ناوك SSSR . سلسلة جديدة (بالروسية). 107 : 362– 365.MR 18-32.

1

[ أ ]

2

[ 3 ]

[ 5 ]

[

[

[

[

[ 10 ]

[ 11 ]

[

[ 13 ]

[

اللغة	العربية (RTL)
روابط موسوعية	30 رابطاً
المصدر الأصلي	ويكيبيديا ↗