طريقة الخطوات المتعددة الخطية

تُعد طريقة أويلر طريقة عددية بسيطة: $${\displaystyle y_{n+1}=y_{n}+hf(t_{n},y_{n}).}$$ يمكن اعتبار طريقة أويلر طريقة متعددة الخطوات صريحة للحالة المنحلة المكونة من خطوة واحدة.

تُطبق هذه الطريقة مع حجم الخطوة${\displaystyle h={\tfrac {1}{2}}}$حول المشكلة${\displaystyle y'=y}$، يعطي النتائج التالية: $${\displaystyle {\begin{aligned}y_{1}&=y_{0}+hf(t_{0},y_{0})=1+{\tfrac {1}{2}}\cdot 1=1.5,\\y_{2}&=y_{1}+hf(t_{1},y_{1})=1.5+{\tfrac {1}{2}}\cdot 1.5=2.25,\\y_{3}&=y_{2}+hf(t_{2},y_{2})=2.25+{\tfrac {1}{2}}\cdot 2.25=3.375,\\y_{4}&=y_{3}+hf(t_{3},y_{3})=3.375+{\tfrac {1}{2}}\cdot 3.375=5.0625.\end{aligned}}}$$

طريقة أويلر هي طريقة من خطوة واحدة . أما طريقة آدمز-باشفورث فهي طريقة بسيطة متعددة الخطوات من خطوتين. $${\displaystyle y_{n+2}=y_{n+1}+{\tfrac {3}{2}}hf(t_{n+1},y_{n+1})-{\tfrac {1}{2}}hf(t_{n},y_{n}).}$$ تتطلب هذه الطريقة قيمتين،${\displaystyle y_{n+1}}$و${\displaystyle y_{n}}$لحساب القيمة التالية،${\displaystyle y_{n+2}}$ومع ذلك، فإن مسألة القيمة الابتدائية لا توفر سوى قيمة واحدة.${\displaystyle y_{0}=1}$إحدى الطرق الممكنة لحل هذه المشكلة هي استخدام${\displaystyle y_{1}}$يتم حسابها باستخدام طريقة أويلر كقيمة ثانية. وبهذا الاختيار، تعطي طريقة آدمز-باشفورث (مقربة إلى أربعة أرقام): $${\displaystyle {\begin{aligned}y_{2}&=y_{1}+{\tfrac {3}{2}}hf(t_{1},y_{1})-{\tfrac {1}{2}}hf(t_{0},y_{0})=1.5+{\tfrac {3}{2}}\cdot {\tfrac {1}{2}}\cdot 1.5-{\tfrac {1}{2}}\cdot {\tfrac {1}{2}}\cdot 1=2.375,\\y_{3}&=y_{2}+{\tfrac {3}{2}}hf(t_{2},y_{2})-{\tfrac {1}{2}}hf(t_{1},y_{1})=2.375+{\tfrac {3}{2}}\cdot {\tfrac {1}{2}}\cdot 2.375-{\tfrac {1}{2}}\cdot {\tfrac {1}{2}}\cdot 1.5=3.7812,\\y_{4}&=y_{3}+{\tfrac {3}{2}}hf(t_{3},y_{3})-{\tfrac {1}{2}}hf(t_{2},y_{2})=3.7812+{\tfrac {3}{2}}\cdot {\tfrac {1}{2}}\cdot 3.7812-{\tfrac {1}{2}}\cdot {\tfrac {1}{2}}\cdot 2.375=6.0234.\end{aligned}}}$$ الحل الدقيق في${\displaystyle t=t_{4}=2}$يكون${\displaystyle e^{2}=7.3891\ldots }$لذا، فإن طريقة آدمز-باشفورث ذات الخطوتين أكثر دقة من طريقة أويلر. ويتحقق ذلك دائمًا إذا كانت خطوة الحساب صغيرة بما يكفي.

تُعدّ طرق آدمز-باشفورث طرقًا صريحة. المعاملات هي${\displaystyle a_{s-1}=-1}$و${\displaystyle a_{s-2}=\cdots =a_{0}=0}$بينما${\displaystyle b_{j}}$يتم اختيارها بحيث يكون للطرق ترتيب s (وهذا يحدد الطرق بشكل فريد).

طرق Adams–Bashforth مع s = 1، 2، 3، 4، 5 هي ( Hairer، Nørsett & Wanner 1993 ، §III.1 ؛ Butcher 2003 ، ص 103 ):  $${\displaystyle {\begin{aligned}y_{n+1}&=y_{n}+hf(t_{n},y_{n}),\qquad {\text{(This is the Euler method)}}\\y_{n+2}&=y_{n+1}+h\left({\frac {3}{2}}f(t_{n+1},y_{n+1})-{\frac {1}{2}}f(t_{n},y_{n})\right),\\y_{n+3}&=y_{n+2}+h\left({\frac {23}{12}}f(t_{n+2},y_{n+2})-{\frac {16}{12}}f(t_{n+1},y_{n+1})+{\frac {5}{12}}f(t_{n},y_{n})\right),\\y_{n+4}&=y_{n+3}+h\left({\frac {55}{24}}f(t_{n+3},y_{n+3})-{\frac {59}{24}}f(t_{n+2},y_{n+2})+{\frac {37}{24}}f(t_{n+1},y_{n+1})-{\frac {9}{24}}f(t_{n},y_{n})\right),\\y_{n+5}&=y_{n+4}+h\left({\frac {1901}{720}}f(t_{n+4},y_{n+4})-{\frac {2774}{720}}f(t_{n+3},y_{n+3})+{\frac {2616}{720}}f(t_{n+2},y_{n+2})-{\frac {1274}{720}}f(t_{n+1},y_{n+1})+{\frac {251}{720}}f(t_{n},y_{n})\right).\end{aligned}}}$$

المعاملات${\displaystyle b_{j}}$يمكن تحديدها كما يلي. استخدم الاستيفاء متعدد الحدود لإيجاد متعددة الحدود p من الدرجة p${\displaystyle s-1}$بحيث $${\displaystyle p(t_{n+i})=f(t_{n+i},y_{n+i}),\qquad {\text{for }}i=0,\ldots ,s-1.}$$ صيغة لاغرانج للاستيفاء متعدد الحدود تعطي $${\displaystyle p(t)=\sum _{j=0}^{s-1}{\frac {(-1)^{s-j-1}f(t_{n+j},y_{n+j})}{j!(s-j-1)!h^{s-1}}}\prod _{i=0 \atop i\neq j}^{s-1}(t-t_{n+i}).}$$ تُعتبر كثيرة الحدود p تقريبًا جيدًا محليًا للطرف الأيمن من المعادلة التفاضلية${\displaystyle y'=f(t,y)}$هذا ما يجب حله، لذا ضع في اعتبارك المعادلة${\displaystyle y'=p(t)}$بدلاً من ذلك، يمكن حل هذه المعادلة بدقة؛ الحل هو ببساطة تكامل p . وهذا يشير إلى أخذ $${\displaystyle y_{n+s}=y_{n+s-1}+\int _{t_{n+s-1}}^{t_{n+s}}p(t)\,\mathrm {d} t.}$$ تظهر طريقة آدمز-باشفورث عند استبدال الصيغة الخاصة بـ p . المعاملات${\displaystyle b_{j}}$اتضح أنه مُقدم من قبل $${\displaystyle b_{s-j-1}={\frac {(-1)^{j}}{j!(s-j-1)!}}\int _{0}^{1}\prod _{i=0 \atop i\neq j}^{s-1}(u+i)\,\mathrm {d} u,\qquad {\text{for }}j=0,\ldots ,s-1.}$$ استبدال${\displaystyle f(t,y)}$يؤدي الاستيفاء p إلى حدوث خطأ من الرتبة h ^s ، وبالتالي فإن طريقة Adams–Bashforth ذات الخطوة s لها بالفعل الرتبة s ( Iserles 1996 ، §2.1).

صُممت طرق آدمز-باشفورث بواسطة جون كوتش آدمز لحل معادلة تفاضلية تُحاكي الخاصية الشعرية ، وذلك استنادًا إلى نظرية فرانسيس باشفورث . وقد نشر باشفورث (1883) نظريته وطريقة آدمز العددية ( جولدستين 1977 ) .

تتشابه طرق آدمز-مولتون مع طرق آدمز-باشفورث في أنها تحتوي أيضًا على${\displaystyle a_{s-1}=-1}$و${\displaystyle a_{s-2}=\cdots =a_{0}=0}$مرة أخرى، يتم اختيار معاملات b للحصول على أعلى رتبة ممكنة. ومع ذلك، فإن طرق آدمز-مولتون هي طرق ضمنية. بإزالة القيد الذي${\displaystyle b_{s}=0}$يمكن لطريقة آدمز-مولتون ذات الخطوات s أن تصل إلى رتبة${\displaystyle s+1}$، بينما طرق Adams–Bashforth ذات الخطوة s لها رتبة s فقط .

تم إدراج طرق Adams–Moulton مع s = 0، 1، 2، 3، 4 ( Hairer، Nørsett & Wanner 1993 ، §III.1 ؛ Quarteroni، Sacco & Saleri 2000 )، حيث أن الطريقتين الأوليين هما طريقة أويلر العكسية وقاعدة شبه المنحرف (المعروفة أيضًا باسم طريقة Crank-Nicolson ) على التوالي: $${\displaystyle {\begin{aligned}y_{n}&=&y_{n-1}&+hf(t_{n},y_{n}),\\y_{n+1}&=&y_{n}&+h\left({\frac {1}{2}}f(t_{n+1},y_{n+1})+{\frac {1}{2}}f(t_{n},y_{n})\right),\\y_{n+2}&=&y_{n+1}&+h\left({\frac {5}{12}}f(t_{n+2},y_{n+2})+{\frac {8}{12}}f(t_{n+1},y_{n+1})-{\frac {1}{12}}f(t_{n},y_{n})\right),\\y_{n+3}&=&y_{n+2}&+h\left({\frac {9}{24}}f(t_{n+3},y_{n+3})+{\frac {19}{24}}f(t_{n+2},y_{n+2})-{\frac {5}{24}}f(t_{n+1},y_{n+1})+{\frac {1}{24}}f(t_{n},y_{n})\right),\\y_{n+4}&=&y_{n+3}&+h\left({\frac {251}{720}}f(t_{n+4},y_{n+4})+{\frac {646}{720}}f(t_{n+3},y_{n+3})-{\frac {264}{720}}f(t_{n+2},y_{n+2})+{\frac {106}{720}}f(t_{n+1},y_{n+1})-{\frac {19}{720}}f(t_{n},y_{n})\right).\end{aligned}}}$$

إن اشتقاق طرق آدمز-مولتون مشابه لاشتقاق طريقة آدمز-باشفورث؛ ومع ذلك، فإن متعدد الحدود الاستيفائي لا يستخدم النقاط فقط${\displaystyle t_{n-1},\dots ,t_{n-s}}$كما سبق، ولكن أيضاً${\displaystyle t_{n}}$المعاملات معطاة بواسطة $${\displaystyle b_{s-j}={\frac {(-1)^{j}}{j!(s-j)!}}\int _{0}^{1}\prod _{i=0 \atop i\neq j}^{s}(u+i-1)\,\mathrm {d} u,\qquad {\text{for }}j=0,\ldots ,s.}$$

تُعزى طرق آدامز-مولتون بالكامل إلى جون كوتش آدامز ، مثل طرق آدامز-باشفورث. ارتبط اسم فورست راي مولتون بهذه الطرق لأنه أدرك إمكانية استخدامها بالتزامن مع طرق آدامز-باشفورث كزوج تنبؤي-مصحح ( مولتون، 1926 ) ؛ وقد تبنى ميلن (1926) الفكرة نفسها. استخدم آدامز طريقة نيوتن لحل المعادلة الضمنية ( هايرر، نورست، ووانر ، 1993 ، القسم الثالث، الفقرة 1) .

تُعدّ طرق BDF طرقًا ضمنية ذات${\displaystyle b_{s-1}=\cdots =b_{0}=0}$والمعاملات الأخرى المختارة بحيث تصل الطريقة إلى الرتبة s (الأعلى الممكنة). تُستخدم هذه الطرق بشكل خاص لحل المعادلات التفاضلية الصلبة .

السؤال الأول هو ما إذا كانت الطريقة متسقة: هل معادلة الفرق $${\displaystyle {\begin{aligned}&a_{s}y_{n+s}+a_{s-1}y_{n+s-1}+a_{s-2}y_{n+s-2}+\cdots +a_{0}y_{n}\\&\qquad {}=h{\bigl (}b_{s}f(t_{n+s},y_{n+s})+b_{s-1}f(t_{n+s-1},y_{n+s-1})+\cdots +b_{0}f(t_{n},y_{n}){\bigr )},\end{aligned}}}$$ تقريب جيد للمعادلة التفاضلية${\displaystyle y'=f(t,y)}$بتعبير أدق، تكون الطريقة متعددة الخطوات متسقة إذا كان خطأ الاقتطاع المحلي يؤول إلى الصفر أسرع من حجم الخطوة h عندما يؤول h إلى الصفر، حيث يُعرَّف خطأ الاقتطاع المحلي بأنه الفرق بين النتيجة${\displaystyle y_{n+s}}$من الطريقة، بافتراض أن جميع القيم السابقة${\displaystyle y_{n+s-1},\ldots ,y_{n}}$وهي دقيقة، والحل الدقيق للمعادلة عند الزمن${\displaystyle t_{n+s}}$تُظهر عملية حسابية باستخدام متسلسلة تايلور أن طريقة الخطوات المتعددة الخطية تكون متسقة إذا وفقط إذا $${\displaystyle \sum _{k=0}^{s-1}a_{k}=-1\quad {\text{and}}\quad \sum _{k=0}^{s}b_{k}=s+\sum _{k=0}^{s-1}ka_{k}.}$$ جميع الطرق المذكورة أعلاه متسقة ( Hairer, Nørsett & Wanner 1993 ، §III.2) .

إذا كانت الطريقة متسقة، فإن السؤال التالي هو مدى دقة معادلة الفرق التي تحدد الطريقة العددية في تقريب المعادلة التفاضلية. يُقال إن طريقة الخطوات المتعددة من الرتبة p إذا كان الخطأ المحلي من الرتبة p.${\displaystyle O(h^{p+1})}$عندما تقترب قيمة h من الصفر. وهذا يكافئ الشرط التالي على معاملات الطرق: $${\displaystyle \sum _{k=0}^{s-1}a_{k}=-1\quad {\text{and}}\quad q\sum _{k=0}^{s}k^{q-1}b_{k}=s^{q}+\sum _{k=0}^{s-1}k^{q}a_{k}{\text{ for }}q=1,\ldots ,p.}$$ تتميز طريقة Adams–Bashforth ذات الخطوات s بالرتبة s ، بينما تتميز طريقة Adams–Moulton ذات الخطوات s بالرتبة s.${\displaystyle s+1}$( هيرر، نورسيت ووانر 1993 ، §III.2) .

غالباً ما تُصاغ هذه الشروط باستخدام كثيرات الحدود المميزة$${\displaystyle \rho (z)=z^{s}+\sum _{k=0}^{s-1}a_{k}z^{k}\quad {\text{and}}\quad \sigma (z)=\sum _{k=0}^{s}b_{k}z^{k}.}$$ بالنسبة لهذه كثيرات الحدود، يصبح الشرط المذكور أعلاه لكي تكون رتبة الطريقة p كما يلي$${\displaystyle \rho (e^{h})-h\sigma (e^{h})=O(h^{p+1})\quad {\text{as }}h\to 0.}$$ وبالتحديد، تكون الطريقة متسقة إذا كان ترتيبها واحدًا على الأقل، وهو ما ينطبق إذا${\displaystyle \rho (1)=0}$و${\displaystyle \rho '(1)=\sigma (1)}$.

يعتمد الحل العددي لطريقة الخطوة الواحدة على الشرط الأولي${\displaystyle y_{0}}$لكن الحل العددي لطريقة الخطوات s يعتمد على جميع قيم البداية s .${\displaystyle y_{0},y_{1},\ldots ,y_{s-1}}$لذا، من المهم معرفة ما إذا كان الحل العددي مستقرًا في مواجهة التغيرات في القيم الابتدائية. تُعتبر طريقة الخطوات المتعددة الخطية مستقرةً عند الصفر لمعادلة تفاضلية معينة على فترة زمنية محددة، إذا تسبب تغير في القيم الابتدائية بمقدار ε في تغيير الحل العددي خلال تلك الفترة الزمنية بما لا يزيد عن Kε ، وذلك لقيمة معينة لـ K لا تعتمد على حجم الخطوة h . يُطلق على هذا "الاستقرار عند الصفر" لأنه يكفي التحقق من شرط المعادلة التفاضلية.${\displaystyle y'=0}$( سولي ومايرز 2003 ، ص 332) . 

إذا كانت جميع جذور متعددة الحدود المميزة ρ ذات معيار أقل من أو يساوي 1، وكانت الجذور ذات المعيار 1 من الرتبة 1، نقول إن شرط الجذر مُحقق. وتكون طريقة الخطوات المتعددة الخطية مستقرة عند الصفر إذا وفقط إذا تحقق شرط الجذر ( سولي ومايرز 2003 ، ص 335) . 

لنفترض الآن أنه يتم تطبيق طريقة خطية متسقة متعددة الخطوات على معادلة تفاضلية سلسة بدرجة كافية، وأن القيم الابتدائية${\displaystyle y_{1},\ldots ,y_{s-1}}$جميعها تتقارب إلى القيمة الأولية${\displaystyle y_{0}}$مثل${\displaystyle h\to 0}$ثم، يتقارب الحل العددي مع الحل الدقيق عندما${\displaystyle h\to 0}$إذا وفقط إذا كانت الطريقة مستقرة عند الصفر. تُعرف هذه النتيجة بنظرية دالكويست للتكافؤ ، نسبةً إلى جيرموند دالكويست ؛ وتتشابه هذه النظرية في جوهرها مع نظرية لاكس للتكافؤ لطرق الفروق المحدودة . علاوة على ذلك، إذا كانت الطريقة من الرتبة p ، فإن الخطأ الكلي (الفرق بين الحل العددي والحل الدقيق عند زمن ثابت) هو${\displaystyle O(h^{p})}$( سولي ومايرز 2003 ، ص 340) . 

علاوة على ذلك، إذا كانت الطريقة متقاربة، يُقال إن الطريقة مستقرة بقوة إذا${\displaystyle z=1}$هو الجذر الوحيد للقيمة المطلقة 1. إذا كانت الطريقة متقاربة، ولم تتكرر جميع جذور القيمة المطلقة 1، ولكن يوجد أكثر من جذر واحد من هذا النوع، يُقال إنها مستقرة نسبيًا . لاحظ أن 1 يجب أن يكون جذرًا لكي تكون الطريقة متقاربة؛ وبالتالي، فإن الطرق المتقاربة تكون دائمًا إحدى هاتين الحالتين.

لتقييم أداء طرق الخطوات المتعددة الخطية على المعادلات الصلبة ، نأخذ في الاعتبار معادلة الاختبار الخطية y' = λ y . عند تطبيق طريقة الخطوات المتعددة على هذه المعادلة التفاضلية بخطوة مقدارها h، نحصل على علاقة تكرارية خطية ذات متعددة حدود مميزة. $${\displaystyle \pi (z;h\lambda )=(1-h\lambda \beta _{s})z^{s}+\sum _{k=0}^{s-1}(\alpha _{k}-h\lambda \beta _{k})z^{k}=\rho (z)-h\lambda \sigma (z).}$$ تُسمى هذه المعادلة متعددة الحدود بمعادلة استقرار طريقة الخطوات المتعددة. إذا كانت جميع جذورها ذات معيار أقل من واحد، فإن الحل العددي لطريقة الخطوات المتعددة سيتقارب إلى الصفر، وتُسمى هذه الطريقة مستقرة استقرارًا مطلقًا لتلك القيمة من hλ . تُسمى الطريقة مستقرة من النوع A إذا كانت مستقرة استقرارًا مطلقًا لجميع قيم hλ ذات الجزء الحقيقي السالب. منطقة الاستقرار المطلق هي مجموعة جميع قيم hλ التي تكون عندها طريقة الخطوات المتعددة مستقرة استقرارًا مطلقًا ( سولي ومايرز ، 2003 ، ص 347 و348) . لمزيد من التفاصيل، راجع قسم المعادلات الصلبة وطرق الخطوات المتعددة . 

ضع في اعتبارك طريقة آدمز-باشفورث المكونة من ثلاث خطوات $${\displaystyle y_{n+3}=y_{n+2}+h\left({23 \over 12}f(t_{n+2},y_{n+2})-{4 \over 3}f(t_{n+1},y_{n+1})+{5 \over 12}f(t_{n},y_{n})\right).}$$ ومن بين كثيرات الحدود المميزة ما يلي: $${\displaystyle \rho (z)=z^{3}-z^{2}=z^{2}(z-1)}$$ والتي لها جذور${\displaystyle z=0,1}$وتتحقق الشروط المذكورة أعلاه.${\displaystyle z=1}$بما أن الجذر الوحيد ذو المعامل 1، فإن الطريقة مستقرة للغاية.

متعددة الحدود المميزة الأخرى هي $${\displaystyle \sigma (z)={\frac {23}{12}}z^{2}-{\frac {4}{3}}z+{\frac {5}{12}}}$$

ينص حاجز دالكوست الأول على أن طريقة الخطوات المتعددة الخطية ذات q خطوة والمستقرة عند الصفر لا يمكنها الوصول إلى رتبة تقارب أكبر من q + 1 إذا كان q فرديًا، وأكبر من q + 2 إذا كان q زوجيًا. وإذا كانت الطريقة صريحة أيضًا، فلا يمكنها الوصول إلى رتبة أكبر من q ( هاير، نورست، ووانر 1993 ، النظرية III.3.5) .

ينص حاجز دالكوست الثاني على أنه لا توجد طرق خطية متعددة الخطوات صريحة مستقرة من النوع A. علاوة على ذلك، فإن الرتبة القصوى لطريقة خطية متعددة الخطوات مستقرة من النوع A (ضمنياً) هي 2. ومن بين الطرق الخطية متعددة الخطوات المستقرة من النوع A من الرتبة 2، فإن قاعدة شبه المنحرف لها أصغر ثابت خطأ ( دالكويست 1963 ، النظرية 2.1 و2.2) .