אנליזה נומרית/שיטות איטרטיביות פשוטות מסדר ראשון

שיטת החיתוך עם

עריכה

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

סדרת הקירובים שלנו, אם כן, תתקבל על-ידי:   .

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

בדיקת סדר האיטרציה

עריכה

כזכור, השגיאה באיטרציה ה- -ית היא   . נציב לשיטה ונקבל:

 

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

תקפות השיטה

עריכה
  השגיאה באיטרציה ה- -ית (סדר 1):
 

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

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

נבצע הזזת אינדקסים אחרונה ( ) כדי לקבל:   .

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

 
שיפוע הפונקציה חיובי וקטן מאחד
 
שיפוע הפונקציה שלילי וקטן מאחד

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

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

 

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

 

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

 

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

דוגמאות

עריכה

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


 

x0=1.9 x0=2.1

x1=0.759
x2=-6.803
x3=-329.651
התבדרות!

x1=3.361
x2=33.327
x3=37,041.25
התבדרות!


 

x0=1.9 x0=2.1

x1=2.042
x2=1.977
x3=2.011
התכנסות!

x1=1.942
x2=2.026
x3=1.986
התכנסות!


קיבלנו, אם כן, שעבור g1 אין התכנסות, ואילו עבור g2 יש התכנסות. יכולנו לחזות זאת מבעוד מועד אילו חישבנו את ערכי הנגזרות שלהן.


נבדוק כעת את הפונקציה  . קל לראות ש-  . נבחר את הפונקציות הבאות:

 
 

נחסוך את הצגת האיטרציות ונציג את התוצאות הסופיות:

x0    
9.9 α2 α1
0.10001 α2 α1
10.1 α2 התבדרות!

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

מסקנות

עריכה
  1. שיטה איטרטיבית עלולה להתכנס לשורש אחד בלבד.
  2. השורש אליו שיטה איטרטיבית מתכנסת עלול להיות תלוי בניחוש ההתחלתי.
  3. שיטה איטרטיבית תתכנס או תתבדר, בהתאם לבחירת  .

שיטת קירובים עוקבים משופרת

עריכה

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

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

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

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

 

נשים לב כי α הוא פתרון עבור g(x)=x לכן שיטה זו תתכנס בתנאים הבאים:

  1. x0 קרוב ל-α, כדי שיתקיים  .
  2.   לא גדול, על מנת שהמונה לא יגרום לחריגה מ-1.
  3.   מספיק רחוק מ-1 כדי שהמכנה ילך לאינסוף.

שיטת המשיק הקבוע

עריכה
 
שיטת המשיק הקבוע

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

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

 

נשים לב ששיטה זו כושלת כאשר  .


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