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

שיטת החיתוך עם $y=x$

שיטה זו ידועה גם בשם "שיטת הקירובים העוקבים". אנו מחפשים את ערכי $x$ עבורם $f(x)=0$ . נשנה מעט את צורת הפונקציה $f$ כדי לקבל את המשוואה: $x=g(x)$ , כך שאם $\alpha$ הוא שורש של $f$ אז בהכרח מתקיים $\alpha =g(\alpha )$ . כלומר $g(x)=\Phi (x)$ היא השיטה האיטרטיבית.

סדרת הקירובים שלנו, אם כן, תתקבל על-ידי: $x_{n+1}=g(x_{n})$ .

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

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

כזכור, השגיאה באיטרציה ה-$n$-ית היא $\epsilon _{n}=x_{n}-\alpha$ . נציב לשיטה ונקבל:

$\epsilon _{n+1}+\alpha =g(\alpha +\epsilon _{n})=g(\alpha )+\epsilon _{n}g'(\alpha )+\cdots \quad \Rightarrow \quad \epsilon _{n+1}=\epsilon _{n}g'(\alpha )+\cdots$

כלומר, בקירוב $\epsilon _{n+1}\approx \epsilon _{n}g'(\alpha )$ ולכן זאת שיטה מסדר ראשון (במידה והשיטה מתכנסת ו- $g'(\alpha )\neq 0$). במידה והנגזרת הראשונה בשורש מתאפסת, סדר השיטה יקבע לפי סדר הנגזרת הראשונה שאינה מתאפסת (ראו סדר התכנסות).

תקפות השיטה

השגיאה באיטרציה ה-$n$-ית (סדר 1): $\epsilon _{n}=\epsilon _{0}[g'(\alpha )]^{n}$

על-פי התוצאה הנ"ל, נאמר ש- $\epsilon _{n+1}=\epsilon _{n}g'(\alpha )$ . כעת, נבצע הזזת אינדקסים עד שנגיע לקשר בין $\epsilon _{n},\epsilon _{0}$ :

$\epsilon _{n+1}=\epsilon _{n}g'(\alpha )=[\epsilon _{n-1}g'(\alpha )]g'(\alpha )=\epsilon _{n-1}[g'(\alpha )]^{2}=$

$=\epsilon _{n-2}[g'(\alpha )]^{3}=\epsilon _{n-3}[g'(\alpha )]^{4}=\cdots =\epsilon _{0}[g'(\alpha )]^{n+1}$

שיטה איטרטיבית מסדר ראשון: $0\neq |g'(\alpha )|<1$

נבצע הזזת אינדקסים אחרונה ($n+1\to n$) כדי לקבל: $\epsilon _{n}=\epsilon _{0}[g'(\alpha )]^{n}$ .

על-מנת שתהיה התכנסות, השגיאה אמורה לקטון בכל איטרציה, ולכן נסיק שתנאי הכרחי להתכנסות הוא $|g'(\alpha )|<1$ . לכן כאשר נבחר פונקציה $g(x)$ , נדאג שהשיפוע שלה (בערך מוחלט) בתחום החיפוש יהיה קטן מ-1.

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

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

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

דרך אחרת לבדיקת תקפות השיטה:
אנו יודעים כי$\ \alpha =g(\alpha )$ וכי $\ x_{n+1}=g(x_{n})$. נחסיר את המשוואות זו מזו ונקבל: $\ x_{n+1}-\alpha =g(x_{n})-g(\alpha )$. כעת נכפול ונחלק את אגף ימין ב- $\ (x_{n}-\alpha )$ ונשתמש במשפט לגראנז':

$\ x_{n+1}-\alpha ={\frac {g(x_{n})-g(\alpha )}{x_{n}-\alpha }}(x_{n}-\alpha )=g'(c)(x_{n}-\alpha )$

כאשר c נמצאת בין $\ x_{n},\alpha$. נניח כי m הוא הערך המקסימלי של $\ |g'(x)|$ בתחום החיפוש. אזי מתקיים:

$\ |x_{n+1}-\alpha |\leq m|x_{n}-\alpha |\ ,\ |x_{n}-\alpha |\leq m|x_{n-1}-\alpha |\ \Rightarrow \ |x_{n+1}-\alpha |\leq m^{2}|x_{n-1}-\alpha |$

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

$\ |x_{n+1}-\alpha |\leq m^{n+1}|x_{0}-\alpha |$

שוב, נבצע הזזת אינדקסים לקבלת: $\ |x_{n}-\alpha |\leq m^{n}|x_{0}-\alpha |$ ואז אם $\ m<1$ בכל תחום החיפוש, אז לכל בחירה של x₀, כאשר n ילך ויגדל, המרחק בין x_n ל-α ילך ויקטן.

דוגמאות

לשם הפשטות, ננתח את הפונקציה $\ f(x)=x^{3}-8$. קל לראות כי α=2. נזכור כי סדרת הקירובים מתקבלת על ידי: $\ x_{n+1}=g(x_{n})$. ניתן למצוא אינסוף שיטות איטרטיביות כאלו, אנו נתבונן בשתיים מהן:

$\ g_{1}(x)=f(x)+x=x^{3}-8+x$

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 התבדרות!

$\ g_{2}(x)={\frac {f(x)-8x}{-8}}={\frac {x^{3}-8-8x}{-8}}$

x0=1.9	x0=2.1
x1=2.042 x2=1.977 x3=2.011 התכנסות!	x1=1.942 x2=2.026 x3=1.986 התכנסות!

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

נבדוק כעת את הפונקציה $\ x^{2}-10.1x+1$. קל לראות ש- $\ \alpha _{1}=0.1,\alpha _{2}=10$. נבחר את הפונקציות הבאות:

$\ g_{1}(x)={\sqrt {10.1x-1}}\quad ,\quad x_{n+1}={\sqrt {10.1x_{n}-1}}$

$\ g_{2}(x)={\frac {x^{2}+1}{10.1}}\quad ,\quad x_{n+1}={\frac {x^{2}+1}{10.1}}$

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

x0	$\ g_{1}(x)$	$\ g_{2}(x)$
9.9	α2	α1
0.10001	α2	α1
10.1	α2	התבדרות!

נשים לב כי $\ g_{1}(x)$ מתכנס לשורש אחד בלבד, אבל זה לא מפתיע כי בבניית $\ g_{1}(x)$ הוצאנו שורש ובחרנו רק את הפתרון החיובי.

מסקנות

1. שיטה איטרטיבית עלולה להתכנס לשורש אחד בלבד.
2. השורש אליו שיטה איטרטיבית מתכנסת עלול להיות תלוי בניחוש ההתחלתי.
3. שיטה איטרטיבית תתכנס או תתבדר, בהתאם לבחירת $\ g(x)$.

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

כזכור, סדרת הקירובים התקבלה על ידי $\ x_{n+1}=g(x_{n})$. ניתן להסתכל על קשר זה באופן אחר: כל נקודה מתקבלת על ידי הנקודה הקודמת x_n, בתוספת $\ g(x_{n})-x_{n}$, כלומר: $\ x_{n+1}=x_{n}+\Delta x_{n}$, כאשר $\ \Delta x_{n}=g(x_{n})-x_{n}$. עד כאן השיטה המוכרת. כעת, על מנת לשפר את קצב ההתכנסות, נוכל לנסות לקחת "תוספת" גדולה יותר לנקודה הקודמת, כך: $\ x_{n+1}=x_{n}+\theta \Delta x_{n}$, כאשר θ>1. אנו לא יודעים איזה θ לקחת, אך אנו יודעים כי הערך הטוב ביותר עבור θ יניב: $\ x_{n+1}=x_{n}+\theta _{\alpha }\Delta x_{n}=\alpha$.

נניח ואנו עומדים על נקודה x_n, ורוצים לחשב את θ האופטימלי. נסמן: $\ \Delta x_{n-1}=g(x_{n-1})-x_{n-1}$. ניתן להראות משיקולים גיאומטריים ש-θ האופטימלי הוא $\ \theta ={\Delta x_{n-1} \over \Delta x_{n-1}-\Delta x}$.

יתרה מזאת: אם נבחר $\ \theta ={1 \over 1-g'(x)}$, נקבל $\ x_{n+1}={g(x)-xg'(x) \over 1-g'(x)}$, או $\ x_{n+1}={\tilde {g}}(x)$, כאשר $\ {\tilde {g}}(x)={g(x)-xg'(x) \over 1-g'(x)}$. זוהי בדיוק שיטת ניוטון-רפסון אשר תכוסה בפרק הבא.

על מנת שהשיטה תתכנס נדרוש $\ |{\tilde {g}}'(x)|<1$. כאן עלולים לתהות מדוע בודקים את התנאי על $\ {\tilde {g}}(x)$ ולא על $\ g(x)$. הסיבה היא שכעת הפונקציה שמקשרת בין x לבין f היא $\ {\tilde {g}}(x)$. אם כן, נמשיך:

$\ {\tilde {g}}'(x)={g''(x)[g(x)-x] \over [1-g'(x)]^{2}}$

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

1. x₀ קרוב ל-α, כדי שיתקיים $\ g(x)-x\to 0$.
2. $\ g''(x)$ לא גדול, על מנת שהמונה לא יגרום לחריגה מ-1.
3. $\ g'(x)$ מספיק רחוק מ-1 כדי שהמכנה ילך לאינסוף.

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

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

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

אם הניחוש ההתחלתי הוא $\ x_{0}$, שיפוע המשיק לפונקציה בנקודה זו הוא $\ f'(x_{0})$, ועל ידי חישוב השיפוע באמצעות שיקולים גאומטריים נמצא את סדרת הקירובים:

$\ f'(x_{0})={\frac {f(x_{n})-0}{x_{n}-x_{n+1}}}\quad \Rightarrow \quad x_{n+1}=x_{n}-{f(x_{n}) \over f'(x_{0})}$

נשים לב ששיטה זו כושלת כאשר $\ f'(x_{0})\approx 0$.

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

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

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