משפט
שיטת ניוטון־רפסון משתמשת בסדרה
x
n
+
1
=
x
n
−
f
(
x
n
)
f
′
(
x
n
)
{\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}}
כדי למצוא שורש של הפונקציה. עבור פונקציות מסוימות, ניתן להוכיח ששיטת ניוטון-רפסון תתכנס לפתרון המבוקש, בהתחשב בנגזרת הראשונה והשניה:
תהי
f
{\displaystyle f}
גזירה פעמיים ברציפות בקטע
[
a
,
b
]
{\displaystyle [a,b]}
, יש לה שורש יחיד בקטע
c
{\displaystyle c}
ונבחר
x
0
∈
[
a
,
b
]
{\displaystyle x_{0}\in [a,b]}
. אז האיטרציה תתכנס לפתרון במקרים הבאים:
∀
x
∈
[
a
,
b
]
f
′
(
x
)
>
0
,
f
″
(
x
)
>
0
,
x
0
>
c
∀
x
∈
[
a
,
b
]
f
′
(
x
)
<
0
,
f
″
(
x
)
<
0
,
x
0
>
c
∀
x
∈
[
a
,
b
]
f
′
(
x
)
<
0
,
f
″
(
x
)
>
0
,
x
0
<
c
∀
x
∈
[
a
,
b
]
f
′
(
x
)
>
0
,
f
″
(
x
)
<
0
,
x
0
<
c
{\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}}}
במקרים אלו ניתן לתחום את גודל השגיאה, על־ידי אי־השוויון הבא:
|
x
n
+
1
−
c
|
≤
M
2
m
(
x
n
+
1
−
x
n
)
2
{\displaystyle |x_{n+1}-c|\leq {\frac {M}{2m}}(x_{n+1}-x_{n})^{2}}
כאשר
M
=
sup
a
<
x
<
b
|
f
″
(
x
)
|
,
m
=
inf
a
<
x
<
b
|
f
′
(
x
)
|
{\displaystyle M=\sup _{a<x<b}{\bigl |}f''(x){\bigr |},m=\inf _{a<x<b}{\bigl |}f'(x){\bigr |}}
ההוכחה מתבססת על שימוש בטור טיילור מסדר שני. נראה אותה עבור המקרה הראשון – עבור שאר המקרים הרעיון זהה.
חלק א: הוכחת התכנסות [ עריכה ]
תהי
{
x
n
}
n
=
0
∞
{\displaystyle \{x_{n}\}_{n=0}^{\infty }}
הסדרה המתקבלת מאיטרציית ניוטון. נניח כי
x
n
>
c
{\displaystyle x_{n}>c}
. כעת נפתח את טור טיילור של
f
(
c
)
{\displaystyle f(c)}
מסדר שני סביב
x
n
{\displaystyle x_{n}}
:
0
=
f
(
c
)
=
f
(
x
n
)
+
f
′
(
x
n
)
(
c
−
x
n
)
+
f
″
(
ξ
)
2
(
c
−
x
n
)
2
=
{\displaystyle 0=f(c)=f(x_{n})+f'(x_{n})(c-x_{n})+{\frac {f''(\xi )}{2}}(c-x_{n})^{2}=}
=
f
′
(
x
n
)
(
c
−
x
n
+
f
(
x
n
)
f
′
(
x
n
)
)
+
f
″
(
ξ
)
2
(
c
−
x
n
)
2
=
{\displaystyle =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
∞
{\displaystyle \{x_{n}\}_{n=0}^{\infty }}
ונקבל:
=
f
′
(
x
n
)
(
c
−
x
n
+
1
)
+
f
″
(
ξ
)
2
(
c
−
x
n
)
2
=
0
{\displaystyle =f'(x_{n})(c-x_{n+1})+{\frac {f''(\xi )}{2}}(c-x_{n})^{2}=0}
נעביר אגפים:
f
′
(
x
n
)
(
x
n
+
1
−
c
)
=
f
″
(
ξ
)
2
(
c
−
x
n
)
2
{\displaystyle f'(x_{n})(x_{n+1}-c)={\frac {f''(\xi )}{2}}(c-x_{n})^{2}}
כעת נזכור כי על-פי הנתון
f
″
(
x
)
>
0
{\displaystyle f''(x)>0}
ולכן הביטוי באגף ימין חיובי. מכאן כי גם הביטוי באגף שמאל חייב להיות חיובי. על-פי הנתון,
f
′
(
x
)
>
0
{\displaystyle \!\,f'(x)>0}
ולכן בהכרח מתקיים:
x
n
+
1
−
c
>
0
{\displaystyle x_{n+1}-c>0}
כלומר
x
n
+
1
>
c
{\displaystyle x_{n+1}>c}
הראינו שהסדרה חסומה מלרע על-ידי
c
{\displaystyle c}
. כעת נראה שזו סדרה יורדת: על-פי הנוסחה ידוע כי
x
n
+
1
=
x
n
−
f
(
x
n
)
f
′
(
x
n
)
{\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}}
. הנגזרת חיובית, כלומר הפונקציה עולה בקטע, ומאחר ש-
x
n
>
c
{\displaystyle x_{n}>c}
הרי ש-
f
(
x
n
)
>
f
(
c
)
=
0
{\displaystyle f(x_{n})>f(c)=0}
ולכן
f
(
x
n
)
f
′
(
x
n
)
>
0
{\displaystyle {\frac {f(x_{n})}{f'(x_{n})}}>0}
ומכאן שמתקיים
x
n
+
1
<
x
n
{\displaystyle x_{n+1}<x_{n}}
. הראינו שהסדרה יורדת.
כידוע, כל סדרה יורדת וחסומה מלרע מתכנסת לגבול . נסמן
lim
n
→
∞
x
n
=
L
{\displaystyle \lim _{n\to \infty }x_{n}=L}
. אז מתקיים:
lim
n
→
∞
x
n
=
lim
n
→
∞
x
n
+
1
{\displaystyle \lim _{n\to \infty }x_{n}=\lim _{n\to \infty }x_{n+1}}
ולכן
L
=
L
−
f
(
L
)
f
′
(
L
)
{\displaystyle L=L-{\frac {f(L)}{f'(L)}}}
ונקבל מיידית
f
(
L
)
=
0
{\displaystyle f(L)=0}
. מכיון ש-
c
{\displaystyle c}
הוא השורש היחיד בקטע,
L
=
c
{\displaystyle L=c}
. הראנו שהסדרה מתכנסת אל השורש המבוקש. מ.ש.ל.
חלק ב': הוכחת הערכת השגיאה [ עריכה ]
נפתח הפעם את טור טיילור של
x
n
+
1
{\displaystyle x_{n+1}}
סביב הנקודה
x
n
{\displaystyle x_{n}}
:
f
(
x
n
+
1
)
=
f
(
x
n
)
+
f
′
(
x
n
)
(
x
n
+
1
−
x
n
)
+
f
″
(
ξ
)
2
(
x
n
+
1
−
x
n
)
2
=
{\displaystyle 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
)
(
x
n
+
1
−
x
n
+
f
(
x
n
)
f
′
(
x
n
)
)
+
f
″
(
ξ
)
2
(
x
n
+
1
−
x
n
)
2
=
{\displaystyle =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
)
+
f
″
(
ξ
)
2
(
x
n
+
1
−
x
n
)
2
=
f
″
(
ξ
)
2
(
x
n
+
1
−
x
n
)
2
{\displaystyle =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}}
כעת, לפי משפט הערך הממוצע של לגראנז' קיימת
η
∈
(
c
,
x
n
+
1
)
{\displaystyle \eta \in (c,x_{n+1})}
המקיימת:
f
(
x
n
+
1
)
−
f
(
c
)
x
n
+
1
−
c
=
f
′
(
η
)
{\displaystyle {\frac {f(x_{n+1})-f(c)}{x_{n+1}-c}}=f'(\eta )}
וקיבלנו:
x
n
+
1
−
c
=
f
(
x
n
+
1
)
f
′
(
η
)
{\displaystyle x_{n+1}-c={\frac {f(x_{n+1})}{f'(\eta )}}}
. כעת נציב את
f
(
x
n
+
1
)
{\displaystyle f(x_{n+1})}
:
x
n
+
1
−
c
=
f
″
(
ξ
)
2
f
′
(
η
)
(
x
n
+
1
−
x
n
)
2
<
M
2
m
(
x
n
+
1
−
x
n
)
2
{\displaystyle x_{n+1}-c={\frac {f''(\xi )}{2f'(\eta )}}(x_{n+1}-x_{n})^{2}<{\frac {M}{2m}}(x_{n+1}-x_{n})^{2}}
.
מ.ש.ל.