- משפט
שיטת ניוטון־רפסון משתמשת בסדרה
כדי למצוא שורש של הפונקציה. עבור פונקציות מסוימות, ניתן להוכיח ששיטת ניוטון-רפסון תתכנס לפתרון המבוקש, בהתחשב בנגזרת הראשונה והשניה:
תהי
גזירה פעמיים ברציפות בקטע
, יש לה שורש יחיד בקטע
ונבחר
. אז האיטרציה תתכנס לפתרון במקרים הבאים:
![{\displaystyle {\begin{aligned}\forall x\in [a,b]\ f'(x)>0\ ,\ f''(x)>0,\ x_{0}>c\\\forall x\in [a,b]\ f'(x)<0\ ,\ f''(x)<0,\ x_{0}>c\\\forall x\in [a,b]\ f'(x)<0\ ,\ f''(x)>0,\ x_{0}<c\\\forall x\in [a,b]\ f'(x)>0\ ,\ f''(x)<0,\ x_{0}<c\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bad1ea2fb06ad2beeffb6839a4fafbd88520da70)
במקרים אלו ניתן לתחום את גודל השגיאה, על־ידי אי־השוויון הבא:
![{\displaystyle |x_{n+1}-c|\leq {\frac {M}{2m}}(x_{n+1}-x_{n})^{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e32922e601bdca0e3a46271ff7f0a9a988e48cca)
כאשר
![{\displaystyle M=\sup _{a<x<b}{\bigl |}f''(x){\bigr |},m=\inf _{a<x<b}{\bigl |}f'(x){\bigr |}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/71a690b5e2c3a4ed39924f0f5e3279eae769fd33)
ההוכחה מתבססת על שימוש בטור טיילור מסדר שני. נראה אותה עבור המקרה הראשון – עבור שאר המקרים הרעיון זהה.
חלק א: הוכחת התכנסות
[עריכה]
תהי
הסדרה המתקבלת מאיטרציית ניוטון. נניח כי
. כעת נפתח את טור טיילור של
מסדר שני סביב
:
כעת נשתמש בהגדרת הסדרה
ונקבל:
נעביר אגפים:
כעת נזכור כי על-פי הנתון
ולכן הביטוי באגף ימין חיובי. מכאן כי גם הביטוי באגף שמאל חייב להיות חיובי. על-פי הנתון,
ולכן בהכרח מתקיים:
כלומר
הראינו שהסדרה חסומה מלרע על-ידי
. כעת נראה שזו סדרה יורדת: על-פי הנוסחה ידוע כי
. הנגזרת חיובית, כלומר הפונקציה עולה בקטע, ומאחר ש-
הרי ש-
ולכן
ומכאן שמתקיים
. הראינו שהסדרה יורדת.
כידוע, כל סדרה יורדת וחסומה מלרע מתכנסת לגבול. נסמן
. אז מתקיים:
ולכן
ונקבל מיידית
. מכיון ש-
הוא השורש היחיד בקטע,
. הראנו שהסדרה מתכנסת אל השורש המבוקש. מ.ש.ל.
חלק ב': הוכחת הערכת השגיאה
[עריכה]
נפתח הפעם את טור טיילור של
סביב הנקודה
:
כעת, לפי משפט הערך הממוצע של לגראנז' קיימת
המקיימת:
וקיבלנו:
. כעת נציב את
:
.
מ.ש.ל.