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

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

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

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

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

נניח כי אנו בודקים סדרת מספרים $x_{n}$ וערכי הפונקציה $f(x_{n})$ סביב תחום שידוע שיש בו שורש. נגדיר את קריטריוני ההתכנסות הבאים, כאשר $\epsilon$ הוא קריטריון ההתכנסות:

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

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

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

$\epsilon _{n+1}+\alpha =\Phi (\alpha )+\epsilon _{n}\Phi '(\alpha )+{\frac {\epsilon _{n}^{2}}{2!}}\Phi ''(\alpha )+{\frac {\epsilon _{n}^{3}}{3!}}\Phi '''(\alpha )+\cdot$

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

$\epsilon _{n+1}=\epsilon _{n}\Phi '(\alpha )+{\frac {\epsilon _{n}^{2}}{2!}}\Phi ''(\alpha )+{\frac {\epsilon _{n}^{3}}{3!}}\Phi '''(\alpha )+\cdots$

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

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

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

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

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

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

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

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

ערך בוויקיפדיה: איטרציה

הפרק הקודם: שיטת חציית האינטרוולים

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

הפרק הבא: שיטות איטרטיביות פשוטות מסדר ראשון