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

מתוך testwiki
קפיצה לניווט קפיצה לחיפוש
משפט

שיטת ניוטון־רפסון משתמשת בסדרה xn+1=xn−f(xn)f′(xn) כדי למצוא שורש של הפונקציה. עבור פונקציות מסוימות, ניתן להוכיח ששיטת ניוטון-רפסון תתכנס לפתרון המבוקש, בהתחשב בנגזרת הראשונה והשניה:

תהי f גזירה פעמיים ברציפות בקטע [a,b] , יש לה שורש יחיד בקטע c ונבחר x0∈[a,b] . אז האיטרציה תתכנס לפתרון במקרים הבאים:

∀x∈[a,b] f′(x)>0 , f″(x)>0, x0>c∀x∈[a,b] f′(x)<0 , f″(x)<0, x0>c∀x∈[a,b] f′(x)<0 , f″(x)>0, x0<c∀x∈[a,b] f′(x)>0 , f″(x)<0, x0<c

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

|xn+1−c|≤M2m(xn+1−xn)2

כאשר

M=supa<x<b|f″(x)|,m=infa<x<b|f′(x)|

הוכחה

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

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

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

0=f(c)=f(xn)+f′(xn)(c−xn)+f″(ξ)2(c−xn)2=

=f′(xn)(c−xn+f(xn)f′(xn))+f″(ξ)2(c−xn)2=

כעת נשתמש בהגדרת הסדרה {xn}n=0∞ ונקבל:

=f′(xn)(c−xn+1)+f″(ξ)2(c−xn)2=0

נעביר אגפים:

f′(xn)(xn+1−c)=f″(ξ)2(c−xn)2

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

xn+1−c>0 כלומר xn+1>c

הראינו שהסדרה חסומה מלרע על-ידי c . כעת נראה שזו סדרה יורדת: על-פי הנוסחה ידוע כי xn+1=xn−f(xn)f′(xn) . הנגזרת חיובית, כלומר הפונקציה עולה בקטע, ומאחר ש- xn>c הרי ש- f(xn)>f(c)=0 ולכן f(xn)f′(xn)>0 ומכאן שמתקיים xn+1<xn . הראינו שהסדרה יורדת.

כידוע, כל סדרה יורדת וחסומה מלרע מתכנסת לגבול. נסמן limn→∞xn=L . אז מתקיים: limn→∞xn=limn→∞xn+1 ולכן L=L−f(L)f′(L) ונקבל מיידית f(L)=0 . מכיון ש- c הוא השורש היחיד בקטע, L=c . הראנו שהסדרה מתכנסת אל השורש המבוקש. מ.ש.ל.

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

נפתח הפעם את טור טיילור של xn+1 סביב הנקודה xn:

f(xn+1)=f(xn)+f′(xn)(xn+1−xn)+f″(ξ)2(xn+1−xn)2=

=f′(xn)(xn+1−xn+f(xn)f′(xn))+f″(ξ)2(xn+1−xn)2=

=f′(xn)(xn+1−xn+1)+f″(ξ)2(xn+1−xn)2=f″(ξ)2(xn+1−xn)2

כעת, לפי [[../../גזירות/משפט הערך הממוצע של לגראנז'|משפט הערך הממוצע של לגראנז']] קיימת η∈(c,xn+1) המקיימת:

f(xn+1)−f(c)xn+1−c=f′(η) וקיבלנו:

xn+1−c=f(xn+1)f′(η) . כעת נציב את f(xn+1) :

xn+1−c=f″(ξ)2f′(η)(xn+1−xn)2<M2m(xn+1−xn)2 .

מ.ש.ל.

אוחזר מתוך "https://he.wikibooks.beta.math.wmflabs.org/w/index.php?title=הוכחות_מתמטיות/חשבון_אינפיניטסימלי/גזירות/שיטת_ניוטון-רפסון&oldid=295"