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

מתוך ויקיספר, אוסף ספרי הלימוד והמדריכים החופשי.

קפיצה אל: ניווט, חיפוש


תוכן עניינים

[עריכה] שיטת 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_nx_{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_nx_{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{align} \Delta x_n & = x_{n+1}-x_n \\ \Delta^2 x_n & = x_{n+2}-2x_{n+1}+x_n \\ \end{align}\right.

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

[עריכה] קישורים חיצוניים

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


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



מקור: http://he.wikibooks.org/wiki/%D7%90%D7%A0%D7%9C%D7%99%D7%96%D7%94_%D7%A0%D7%95%D7%9E%D7%A8%D7%99%D7%AA/%D7%A9%D7%99%D7%98%D7%95%D7%AA_%D7%90%D7%99%D7%98%D7%A8%D7%98%D7%99%D7%91%D7%99%D7%95%D7%AA_%D7%A8%D7%91_%D7%A6%D7%A2%D7%93%D7%99%D7%95%D7%AA