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

כלומר, בקירוב
ולכן זאת שיטה מסדר ראשון (במידה והשיטה מתכנסת ו-
). במידה והנגזרת הראשונה בשורש מתאפסת, סדר השיטה יקבע לפי סדר הנגזרת הראשונה שאינה מתאפסת (ראו סדר התכנסות).
תקפות השיטה[עריכה]
|
השגיאה באיטרציה ה- -ית (סדר 1):
|
על-פי התוצאה הנ"ל, נאמר ש-
. כעת, נבצע הזזת אינדקסים עד שנגיע לקשר בין
:
![{\displaystyle \epsilon _{n+1}=\epsilon _{n}g'(\alpha )=[\epsilon _{n-1}g'(\alpha )]g'(\alpha )=\epsilon _{n-1}[g'(\alpha )]^{2}=}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e8c5005998a7c39b1307e26dfca6a8db9e0c3a3a)
![{\displaystyle =\epsilon _{n-2}[g'(\alpha )]^{3}=\epsilon _{n-3}[g'(\alpha )]^{4}=\cdots =\epsilon _{0}[g'(\alpha )]^{n+1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/76308245e48939aabbd01aee399db4523ff6df21)
|
שיטה איטרטיבית מסדר ראשון:
|
נבצע הזזת אינדקסים אחרונה (
) כדי לקבל:
.
על-מנת שתהיה התכנסות, השגיאה אמורה לקטון בכל איטרציה, ולכן נסיק שתנאי הכרחי להתכנסות הוא
. לכן כאשר נבחר פונקציה
, נדאג שהשיפוע שלה (בערך מוחלט) בתחום החיפוש יהיה קטן מ-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 |
התבדרות!
|
נשים לב כי
מתכנס לשורש אחד בלבד, אבל זה לא מפתיע כי בבניית
הוצאנו שורש ובחרנו רק את הפתרון החיובי.
- שיטה איטרטיבית עלולה להתכנס לשורש אחד בלבד.
- השורש אליו שיטה איטרטיבית מתכנסת עלול להיות תלוי בניחוש ההתחלתי.
- שיטה איטרטיבית תתכנס או תתבדר, בהתאם לבחירת
.
שיטת קירובים עוקבים משופרת[עריכה]
כזכור, סדרת הקירובים התקבלה על ידי
. ניתן להסתכל על קשר זה באופן אחר: כל נקודה מתקבלת על ידי הנקודה הקודמת xn, בתוספת
, כלומר:
, כאשר
. עד כאן השיטה המוכרת. כעת, על מנת לשפר את קצב ההתכנסות, נוכל לנסות לקחת "תוספת" גדולה יותר לנקודה הקודמת, כך:
, כאשר θ>1. אנו לא יודעים איזה θ לקחת, אך אנו יודעים כי הערך הטוב ביותר עבור θ יניב:
.
נניח ואנו עומדים על נקודה xn, ורוצים לחשב את θ האופטימלי. נסמן:
. ניתן להראות משיקולים גיאומטריים ש-θ האופטימלי הוא
.
יתרה מזאת: אם נבחר
, נקבל
, או
, כאשר
. זוהי בדיוק שיטת ניוטון-רפסון אשר תכוסה בפרק הבא.
על מנת שהשיטה תתכנס נדרוש
. כאן עלולים לתהות מדוע בודקים את התנאי על
ולא על
. הסיבה היא שכעת הפונקציה שמקשרת בין x לבין f היא
. אם כן, נמשיך:
![{\displaystyle \ {\tilde {g}}'(x)={g''(x)[g(x)-x] \over [1-g'(x)]^{2}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/45ca730fa9cf3b01010d4a3231dd46e252438f1f)
נשים לב כי α הוא פתרון עבור g(x)=x לכן שיטה זו תתכנס בתנאים הבאים:
- x0 קרוב ל-α, כדי שיתקיים
.
לא גדול, על מנת שהמונה לא יגרום לחריגה מ-1.
מספיק רחוק מ-1 כדי שהמכנה ילך לאינסוף.
שיטת המשיק הקבוע[עריכה]
בשיטת המשיק הקבוע מוצאים את את המשיק לפונקציה בנקודת הניחוש ההתחלתי, מחשבים את חיתוכו עם ציר x ואת ערך הפונקציה בנקודה זו, ודרך הנקודה הזאת מעבירים שוב את אותו משיק, עד אשר מגיעים לשורש.
אם הניחוש ההתחלתי הוא
, שיפוע המשיק לפונקציה בנקודה זו הוא
, ועל ידי חישוב השיפוע באמצעות שיקולים גאומטריים נמצא את סדרת הקירובים:

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