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

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

תוכן עניינים

1 שיטת החיתוך עם y=x
2 שיטת המשיק הקבוע

[עריכה] שיטת החיתוך עם y=x

שיטה זו ידועה גם בשם "שיטת הקירובים העוקבים". אנו מחפשים את ערכי x עבורם $\ f(x)=0$ . נשנה מעט את צורת הפונקציה f כדי לקבל את המשוואה: $\ x=g(x)$ , כך שאם α הוא שורש של 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_ng'(\alpha)+ ...\quad\Rightarrow\quad \epsilon_{n+1}= \epsilon_ng'(\alpha)+ ...$

כלומר, בקירוב $\ \epsilon_{n+1}\approx \epsilon_n g'(\alpha)$ ולכן זאת שיטה מסדר ראשון (במידה והשיטה מתכנסת ו- $\ g'(\alpha)\ne 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=...= \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|\le m|x_n-\alpha|\ ,\ |x_n-\alpha|\le m|x_{n-1}-\alpha|\ \Rightarrow\ |x_{n+1}-\alpha|\le m^2|x_{n-1}-\alpha|$

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

$\ |x_{n+1}-\alpha|\le m^{n+1}|x_0-\alpha|$

שוב, נבצע הזזת אינדקסים לקבלת: $\ |x_n-\alpha|\le 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$

x₀=1.9	x₀=2.1
x₁=0.759 x₂=-6.803 x₃=-329.651 התבדרות!	x₁=3.361 x₂=33.327 x₃=37,041.25 התבדרות!

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

x₀=1.9	x₀=2.1
x₁=2.042 x₂=1.977 x₃=2.011 התכנסות!	x₁=1.942 x₂=2.026 x₃=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}$

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

x₀	$\ g_1(x)$	$\ g_2(x)$
9.9	α₂	α₁
0.10001	α₂	α₁
10.1	α₂	התבדרות!

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

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

שיטה איטרטיבית עלולה להתכנס לשורש אחד בלבד.
השורש אליו שיטה איטרטיבית מתכנסת עלול להיות תלוי בניחוש ההתחלתי.
שיטה איטרטיבית תתכנס או תתבדר, בהתאם לבחירת $\ 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 לכן שיטה זו תתכנס בתנאים הבאים:

x₀ קרוב ל-α, כדי שיתקיים $\ g(x)-x\to 0$ .
$\ g''(x)$ לא גדול, על מנת שהמונה לא יגרום לחריגה מ-1.
$\ 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$ .

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

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

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

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

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

תוכן עניינים

[עריכה] שיטת החיתוך עם y=x

[עריכה] בדיקת סדר האיטרציה

[עריכה] תקפות השיטה

[עריכה] דוגמאות

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

[עריכה] שיטת קירובים עוקבים משופרת

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

צפיות

כלים אישיים

ניווט

קהילה

חיפוש

תיבת כלים

הדפסה/ייצוא