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

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

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

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

General Iterative Method.png

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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