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

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

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

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

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

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

  1.  
  2.   - בדיקה מוחלטת (השגיאה בעלת ממד).
  3.   - בדיקה יחסית (השגיאה חסרת ממד - ניתנת באחוזים).
  4.  
  5.  

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

נסמן את השיטה ב-   . על פי המודל של השיטה האיטרטיבית נובע:   . ננסה להעריך את מידת ההתכנסות של השיטה (order of convergence). נסמן את השגיאה באיטרציה ה-  -ית על-ידי ההפרש:   . זהו המרחק בין השורש לבין המקום בו אנו נמצאים, באיטרציה ה-  -ית. על-ידי הצבה במודל האיטרטיבי: אם   אז   ואז נקבל:   . כעת נפתח את   לטור טיילור סביב   :

 

נשתמש בעובדה שהשיטה האיטרטיבית צריכה להחזיר את השורש של הפונקציה, במידה והיא מקבלת אותו:   , כלומר:   . במילים אחרות:   הוא פתרון המשוואה   (ראו גם: שיטת החיתוך עם y=x). נציב קשר זה בטור ונקבל:

 

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

  • אם   אז בקירוב:   , כלומר מקבלים קשר לינארי בין שתי שגיאות (איטרציות) עוקבות.
  • אם   אבל   אז בקירוב:   , כלומר מקבלים קשר ריבועי בין שתי שגיאות (איטרציות) עוקבות.
  • כללית, אם:   , אבל   , אז בקירוב:   .

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

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

אם קיימים מספרים   כך ש-   אז   הוא סדר ההתכנסות (האיטרציה) ו-   הוא קבוע השגיאה האסימפטוטי ( ). ניתן להוכיח זאת על-ידי פיתוח לטור טיילור ושימוש במשפט לגראנז'.

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

  • אם   רציפה בתחום   וגם   (כלומר: התחום והטווח שניהם באותו מרווח [אינטרוול] והפונקציה היא על), אז למשוואה   קיים פתרון בתחום זה.
  • אם בנוסף   אז   הוא שורש יחיד בתחום זה.
  • אם מתקיימים שני התנאים הנ"ל, אז הפוקנציה האיטרטיבית   מתכנסת ל-   לכל   בתחום הנ"ל.

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


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