הוכחות מתמטיות/חשבון אינפיניטסימלי/גזירות/שיטת ניוטון-רפסון

משפט

שיטת ניוטון־רפסון משתמשת בסדרה $x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}$ כדי למצוא שורש של הפונקציה. עבור פונקציות מסוימות, ניתן להוכיח ששיטת ניוטון-רפסון תתכנס לפתרון המבוקש, בהתחשב בנגזרת הראשונה והשניה:

תהי $f$ גזירה פעמיים ברציפות בקטע $[a,b]$ , יש לה שורש יחיד בקטע $c$ ונבחר $x_{0}\in [a,b]$ . אז האיטרציה תתכנס לפתרון במקרים הבאים:

${\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}}$

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

$|x_{n+1}-c|\leq {\frac {M}{2m}}(x_{n+1}-x_{n})^{2}$

כאשר

$M=\sup _{a<x<b}{\bigl |}f''(x){\bigr |},m=\inf _{a<x<b}{\bigl |}f'(x){\bigr |}$

הוכחה

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

חלק א: הוכחת התכנסות

תהי $\{x_{n}\}_{n=0}^{\infty }$ הסדרה המתקבלת מאיטרציית ניוטון. נניח כי $x_{n}>c$ . כעת נפתח את טור טיילור של $f(c)$ מסדר שני סביב $x_{n}$ :

$0=f(c)=f(x_{n})+f'(x_{n})(c-x_{n})+{\frac {f''(\xi )}{2}}(c-x_{n})^{2}=$

$=f'(x_{n})\left(c-x_{n}+{\frac {f(x_{n})}{f'(x_{n})}}\right)+{\frac {f''(\xi )}{2}}(c-x_{n})^{2}=$

כעת נשתמש בהגדרת הסדרה $\{x_{n}\}_{n=0}^{\infty }$ ונקבל:

$=f'(x_{n})(c-x_{n+1})+{\frac {f''(\xi )}{2}}(c-x_{n})^{2}=0$

נעביר אגפים:

$f'(x_{n})(x_{n+1}-c)={\frac {f''(\xi )}{2}}(c-x_{n})^{2}$

כעת נזכור כי על-פי הנתון $f''(x)>0$ ולכן הביטוי באגף ימין חיובי. מכאן כי גם הביטוי באגף שמאל חייב להיות חיובי. על-פי הנתון, $\!\,f'(x)>0$ ולכן בהכרח מתקיים:

$x_{n+1}-c>0$ כלומר $x_{n+1}>c$

הראינו שהסדרה חסומה מלרע על-ידי $c$ . כעת נראה שזו סדרה יורדת: על-פי הנוסחה ידוע כי $x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}$ . הנגזרת חיובית, כלומר הפונקציה עולה בקטע, ומאחר ש- $x_{n}>c$ הרי ש- $f(x_{n})>f(c)=0$ ולכן ${\frac {f(x_{n})}{f'(x_{n})}}>0$ ומכאן שמתקיים $x_{n+1}<x_{n}$ . הראינו שהסדרה יורדת.

כידוע, כל סדרה יורדת וחסומה מלרע מתכנסת לגבול. נסמן $\lim _{n\to \infty }x_{n}=L$ . אז מתקיים: $\lim _{n\to \infty }x_{n}=\lim _{n\to \infty }x_{n+1}$ ולכן $L=L-{\frac {f(L)}{f'(L)}}$ ונקבל מיידית $f(L)=0$ . מכיון ש- $c$ הוא השורש היחיד בקטע, $L=c$ . הראנו שהסדרה מתכנסת אל השורש המבוקש. מ.ש.ל.

חלק ב': הוכחת הערכת השגיאה

נפתח הפעם את טור טיילור של $x_{n+1}$ סביב הנקודה $x_{n}$:

$f(x_{n+1})=f(x_{n})+f'(x_{n})(x_{n+1}-x_{n})+{\frac {f''(\xi )}{2}}(x_{n+1}-x_{n})^{2}=$

$=f'(x_{n})\left(x_{n+1}-x_{n}+{\frac {f(x_{n})}{f'(x_{n})}}\right)+{\frac {f''(\xi )}{2}}(x_{n+1}-x_{n})^{2}=$

$=f'(x_{n})(x_{n+1}-x_{n+1})+{\frac {f''(\xi )}{2}}(x_{n+1}-x_{n})^{2}={\frac {f''(\xi )}{2}}(x_{n+1}-x_{n})^{2}$

כעת, לפי משפט הערך הממוצע של לגראנז' קיימת $\eta \in (c,x_{n+1})$ המקיימת:

${\frac {f(x_{n+1})-f(c)}{x_{n+1}-c}}=f'(\eta )$ וקיבלנו:

$x_{n+1}-c={\frac {f(x_{n+1})}{f'(\eta )}}$ . כעת נציב את $f(x_{n+1})$ :

$x_{n+1}-c={\frac {f''(\xi )}{2f'(\eta )}}(x_{n+1}-x_{n})^{2}<{\frac {M}{2m}}(x_{n+1}-x_{n})^{2}$ .

מ.ש.ל.