אנליזה נומרית/שיטות איטרטיביות רב צעדיות

שיטת Aitken

נעשה שימוש בשיטת איטקן כאשר רוצים להאיץ התכנסות לינארית. למשל כאשר ישנו שורש כפול, שיטת ניוטון-רפסון מתנוונת לסדר ראשון, ולכן נעדיף להשתמש בשיטה זו.

משפט: האצת איטקן נניח כי הסדרה $\ \{x_{n}\}_{n=0}^{\infty }$ מתכנסת לינארית לשורש α וגם $\ x_{n}\neq \alpha ,\ \forall n\in \mathbb {N}$. אז אם קיים קבוע ממשי $\ A,\ |A|<1$ כך ש- $\ \lim _{n\to \infty }{\frac {\alpha -x_{n+1}}{\alpha -x_{n}}}=A$ אז הסדרה $\ \{{\hat {x}}_{n}\}_{n=0}^{\infty },\ {\hat {x}}_{n}=x_{n}-{\frac {(\Delta x_{n})^{2}}{\Delta ^{2}x_{n}}}$ מתכנסת לשורש α מהר יותר מהסדרה המקורית, כאשר Δ הוא אופרטור הפרשים קדמיים.

ניתן להראות כי כאשר השיטה האיטרטיבית $\ x_{n+1}=g(x_{n})$ הינה מסדר ראשון (כלומר: $\ g'(\alpha )\neq 0$) אז עבור שתי האיטרציות הראשונות מתקיים בקירוב:

$\ \alpha \approx {\frac {x_{n}x_{n+2}-x_{n+1}^{2}}{x_{n+2}-2x_{n+1}+x_{n}}}$

הוכחה

נשתמש בקשר $\ x_{n}\approx \alpha +\epsilon _{0}[g'(\alpha )]^{n}$:

$\ {\frac {(\alpha +\epsilon _{0}[g'(\alpha )]^{n})(\alpha +\epsilon _{0}[g'(\alpha )]^{n+2})-(\alpha +\epsilon _{0}[g'(\alpha )]^{n+1})^{2}}{\alpha +\epsilon _{0}[g'(\alpha )]^{n+2}-2(\alpha +\epsilon _{0}[g'(\alpha )]^{n+1})+\alpha +\epsilon _{0}[g'(\alpha )]^{n}}}={\frac {\alpha [g'(\alpha )]^{n}(1-2g'(\alpha )+[g'(\alpha )]^{2})}{[g'(\alpha )]^{n}(1-2g'(\alpha )+[g'(\alpha )]^{2})}}=\alpha$

יישום

שיטת איטקן:

$\ x_{n+3}={\frac {x_{n}x_{n+2}-x_{n+1}^{2}}{x_{n+2}-2x_{n+1}+x_{n}}}$

נהוג לכתוב שיטה זו גם בצורת הפרשים קדמיים:

$\ x_{n+3}=x_{n}-{\frac {(\Delta x_{n})^{2}}{\Delta ^{2}x_{n}}}\quad ;\quad \left\{{\begin{aligned}\Delta x_{n}&=x_{n+1}-x_{n}\\\Delta ^{2}x_{n}&=x_{n+2}-2x_{n+1}+x_{n}\\\end{aligned}}\right.$

כאשר את שלושת הנקודות הראשונות יש לקבל באמצעות שיטה חד צעדית כלשהי.

קישורים חיצוניים

ערך בוויקיפדיה: שיטת איטקן (אנגלית)

• אתר MathWorld
• מאתר אוניברסיטת CSUF, הכולל דוגמאות קוד עבור תוכנת מתמטיקה.
• פיתוח גרפי של שיטת איטקן באתר אוניברסיטת Lancaster

הפרק הקודם: שיטות איטרטיביות עם מיתרים

שיטות איטרטיביות רב צעדיות

הפרק הבא: אופרטורים של הפרשים סופיים