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

שיטת Aitken

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

ניתן להראות כי כאשר השיטה האיטרטיבית $x_{n+1}=g(x_n)$ הינה מסדר ראשון (כלומר: $g^{\prime }(\alpha )\ne 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 +{ϵ}_0[g^{\prime }(\alpha ){]}^n$:

$\frac{(\alpha +{ϵ}_0[g^{\prime }(\alpha ){]}^n)(\alpha +{ϵ}_0[g^{\prime }(\alpha ){]}^{n+2})-(\alpha +{ϵ}_0[g^{\prime }(\alpha ){]}^{n+1}{)}^2}{\alpha +{ϵ}_0[g^{\prime }(\alpha ){]}^{n+2}-2(\alpha +{ϵ}_0[g^{\prime }(\alpha ){]}^{n+1})+\alpha +{ϵ}_0[g^{\prime }(\alpha ){]}^n}=\frac{\alpha [g^{\prime }(\alpha ){]}^n(1-2g^{\prime }(\alpha )+[g^{\prime }(\alpha ){]}^2)}{[g^{\prime }(\alpha ){]}^n(1-2g^{\prime }(\alpha )+[g^{\prime }(\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{(\mathrm{\Delta }{x}_n{)}^2}{{\mathrm{\Delta }}^2{x}_n};\{\begin{array}{cc}\mathrm{\Delta }{x}_n& =x_{n+1}-x_n\\ {\mathrm{\Delta }}^2{x}_n& =x_{n+2}-2x_{n+1}+x_n\\ \end{array}$

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

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

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