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

כפי שנראה בהמשך, קיימות שיטות איטרטיביות שונות. ניתן למיין אותן לפי מספר הנקודות בהן הן משתמשות על-מנת לייצר את הקירוב הבא. התאוריה לכשעצמה היא מסובכת, לכן אנו נעסוק בתאוריה של שיטות איטרטיביות חד-נקודתיות בלבד.

להלן מודל כללי של שיטה איטרטיבית חד-נקודתית כלשהי:

קובץ:General Iterative Method.png

תבנית:אנליזה נומרית בעזרת השיטה האיטרטיבית נוכל לייצר סדרת מספרים אשר מהווים קירוב לשורש. נסמן את השורש של הפונקציה $f(x)$ בתור $\alpha$ , כך שמתקיים: $f(\alpha )\equiv 0$ . אם נבצע מספיק איטרציות, כך ש: $\underset{n\to \mathrm{\infty }}{\lim }{x}_n\to \alpha$ אז השיטה האיטרטיבית מתכנסת. בכל מקרה אחר היא מתבדרת.

קריטריוני התכנסות

נניח כי אנו בודקים סדרת מספרים $x_n$ וערכי הפונקציה $f(x_n)$ סביב תחום שידוע שיש בו שורש. נגדיר את קריטריוני ההתכנסות הבאים, כאשר $ϵ$ הוא קריטריון ההתכנסות:

1. $|x_{n+1}-x_n|<ϵ$
2. $|f(x_n)|<ϵ$ - בדיקה מוחלטת (השגיאה בעלת ממד).
3. $|1-\frac{x_n}{x_{n+1}}|<ϵ$ - בדיקה יחסית (השגיאה חסרת ממד - ניתנת באחוזים).
4. $|f(x_{n+1})-f(x_n)|<ϵ$
5. $|1-\frac{f(x_n)}{f(x_{n+1})}|<ϵ$

תיאור מתמטי של שיטה איטרטיבית כלשהי

נסמן את השיטה ב- $\mathrm{\Phi }$ . על פי המודל של השיטה האיטרטיבית נובע: $x_{n+1}=\mathrm{\Phi }(x_n)$ . ננסה להעריך את מידת ההתכנסות של השיטה (order of convergence). נסמן את השגיאה באיטרציה ה- $n$-ית על-ידי ההפרש: ${ϵ}_n=x_n-\alpha$ . זהו המרחק בין השורש לבין המקום בו אנו נמצאים, באיטרציה ה- $n$-ית. על-ידי הצבה במודל האיטרטיבי: אם $x_n={ϵ}_n+\alpha$ אז $x_{n+1}={ϵ}_{n+1}+\alpha$ ואז נקבל: ${ϵ}_{n+1}+\alpha =\mathrm{\Phi }(\alpha +{ϵ}_n)$ . כעת נפתח את $\mathrm{\Phi }({ϵ}_n+\alpha )$ לטור טיילור סביב $\alpha$ :

${ϵ}_{n+1}+\alpha =\mathrm{\Phi }(\alpha )+{ϵ}_n{\mathrm{\Phi }}^{\prime }(\alpha )+\frac{{ϵ}_n^2}{2!}{\mathrm{\Phi }}^{″}(\alpha )+\frac{{ϵ}_n^3}{3!}{\mathrm{\Phi }}^{‴}(\alpha )+\cdot$

נשתמש בעובדה שהשיטה האיטרטיבית צריכה להחזיר את השורש של הפונקציה, במידה והיא מקבלת אותו: $\alpha =\underset{n\to \mathrm{\infty }}{\lim }{x}_n=\underset{n\to \mathrm{\infty }}{\lim }\mathrm{\Phi }(x_{n-1})=\mathrm{\Phi }(\underset{n\to \mathrm{\infty }}{\lim }{x}_{n-1})=\mathrm{\Phi }(\alpha )$ , כלומר: $\mathrm{\Phi }(\alpha )=\alpha$ . במילים אחרות: $\alpha$ הוא פתרון המשוואה $x=\mathrm{\Phi }(x)$ (ראו גם: שיטת החיתוך עם y=x). נציב קשר זה בטור ונקבל:

${ϵ}_{n+1}={ϵ}_n{\mathrm{\Phi }}^{\prime }(\alpha )+\frac{{ϵ}_n^2}{2!}{\mathrm{\Phi }}^{″}(\alpha )+\frac{{ϵ}_n^3}{3!}{\mathrm{\Phi }}^{‴}(\alpha )+\cdots$

על-פי הגדרה, סדר האיטרציה נקבע לפי סדר הנגזרת הראשונה שאינה מתאפסת. לדוגמה:

• אם ${\mathrm{\Phi }}^{\prime }(\alpha )\ne 0$ אז בקירוב: ${ϵ}_{n+1}\approx {ϵ}_n{\mathrm{\Phi }}^{\prime }(\alpha )$ , כלומר מקבלים קשר לינארי בין שתי שגיאות (איטרציות) עוקבות.
• אם ${\mathrm{\Phi }}^{\prime }(\alpha )=0$ אבל ${\mathrm{\Phi }}^{″}(\alpha )\ne 0$ אז בקירוב: ${ϵ}_{n+1}\approx \frac{{ϵ}_n^2}{2!}{\mathrm{\Phi }}^{″}(\alpha )$ , כלומר מקבלים קשר ריבועי בין שתי שגיאות (איטרציות) עוקבות.
• כללית, אם: ${\mathrm{\Phi }}^{(k)}(\alpha )=0,\mathrm{\forall }0\le k<m$ , אבל ${\mathrm{\Phi }}^{(m)}(\alpha )\ne 0$ , אז בקירוב: ${ϵ}_{n+1}\approx \frac{{ϵ}_n^m}{m!}{\mathrm{\Phi }}^{(m)}(\alpha )$ .

ככל שסדר האיטרציה גדול יותר, הקשר בין כל שתי שגיאות (איטרציות) עוקבות הוא "חזק" יותר, כלומר קצב ההתכנסות מהיר יותר.

סדר התכנסות: הגדרה פורמלית

אם קיימים מספרים $m,c$ כך ש- $\underset{n\to \mathrm{\infty }}{\lim }\left|\frac{{ϵ}_{n+1}}{{ϵ}_n^m}\right|=c$ אז $m$ הוא סדר ההתכנסות (האיטרציה) ו- $c=\frac{|{\mathrm{\Phi }}^{(m)}(\alpha )|}{m!}$ הוא קבוע השגיאה האסימפטוטי ($c\ne 0$). ניתן להוכיח זאת על-ידי פיתוח לטור טיילור ושימוש במשפט לגראנז'.

משפטי התכנסות

• אם $\mathrm{\Phi }(x)$ רציפה בתחום $[a,b]$ וגם $a\le \mathrm{\Phi }(x)\le b,\mathrm{\forall }x\in [a,b]$ (כלומר: התחום והטווח שניהם באותו מרווח [אינטרוול] והפונקציה היא על), אז למשוואה $x=\mathrm{\Phi }(x)$ קיים פתרון בתחום זה.
• אם בנוסף $|{\mathrm{\Phi }}^{\prime }(x)|<1,\mathrm{\forall }x\in [a,b]$ אז $\alpha$ הוא שורש יחיד בתחום זה.
• אם מתקיימים שני התנאים הנ"ל, אז הפוקנציה האיטרטיבית $\mathrm{\Phi }(x)$ מתכנסת ל- $\alpha$ לכל $x_0$ בתחום הנ"ל.