שיטת ניוטון-רפסון ("המשיק המשתנה") שיטת ניוטון-רפסון - אשר ידועה גם בתור "שיטת המשיק המשתנה" - היא שכלול של שיטת המשיק הקבוע.
מעבירים משיק לפונקציה בניחוש ההתחלתי. מיקום חיתוך המשיק עם ציר
x
{\displaystyle x}
f
′
(
x
n
)
=
f
(
x
n
)
−
0
x
n
−
x
n
+
1
{\displaystyle f'(x_{n})={\frac {f(x_{n})-0}{x_{n}-x_{n+1}}}}
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
′
(
x
n
)
≈
0
{\displaystyle f'(x_{n})\approx 0}
x
0
{\displaystyle x_{0}}
נשים לב כי בשיטה זו מניחים שהנגזרת הראשונה רציפה.
[ עריכה ] כזכור, השגיאה באיטרציה ה-
n
{\displaystyle n}
ε
n
=
x
n
−
α
{\displaystyle \varepsilon _{n}=x_{n}-\alpha }
ε
n
+
1
+
α
=
ε
n
+
α
−
f
(
ε
n
+
α
)
f
′
(
ε
n
+
α
)
⇒
ε
n
+
1
=
ε
n
f
′
(
ε
n
+
α
)
−
f
(
ε
n
+
α
)
f
′
(
ε
n
+
α
)
{\displaystyle \varepsilon _{n+1}+\alpha =\varepsilon _{n}+\alpha -{\frac {f(\varepsilon _{n}+\alpha )}{f'(\varepsilon _{n}+\alpha )}}\quad \Rightarrow \quad \varepsilon _{n+1}={\frac {\varepsilon _{n}f'(\varepsilon _{n}+\alpha )-f(\varepsilon _{n}+\alpha )}{f'(\varepsilon _{n}+\alpha )}}}
נפתח את המונה והמכנה לטור טיילור:
ε
n
+
1
=
ε
n
[
f
′
(
α
)
+
ε
n
f
″
(
α
)
+
ε
n
2
2
!
f
‴
(
α
)
+
⋯
]
−
[
f
(
α
)
+
ε
n
f
′
(
α
)
+
ε
n
2
2
!
f
″
(
α
)
+
⋯
]
f
′
(
α
)
+
ε
n
f
″
(
α
)
+
ε
n
2
2
!
f
‴
(
α
)
{\displaystyle \varepsilon _{n+1}={\frac {\varepsilon _{n}\left[f'(\alpha )+\varepsilon _{n}f''(\alpha )+{\dfrac {\varepsilon _{n}^{2}}{2!}}f'''(\alpha )+\cdots \right]-\left[f(\alpha )+\varepsilon _{n}f'(\alpha )+{\dfrac {\varepsilon _{n}^{2}}{2!}}f''(\alpha )+\cdots \right]}{f'(\alpha )+\varepsilon _{n}f''(\alpha )+{\dfrac {\varepsilon _{n}^{2}}{2!}}f'''(\alpha )}}}
לאחר שכמה אברים במונה מצטמצמים, נקבל שהאיברים המובילים של הטורים במונה ובמכנה נותנים את הביטוי הבא:
ε
n
+
1
=
ε
n
2
2
!
f
″
(
α
)
+
⋯
f
′
(
α
)
+
⋯
{\displaystyle \varepsilon _{n+1}={\frac {{\dfrac {\varepsilon _{n}^{2}}{2!}}f''(\alpha )+\cdots }{f'(\alpha )+\cdots }}}
אם השיטה מתכנסת, אז עבור
lim
n
→
∞
ε
n
=
0
{\displaystyle \lim _{n\to \infty }\varepsilon _{n}=0}
ε
n
+
1
≈
ε
n
2
f
″
(
α
)
2
f
′
(
α
)
⏞
A
⇒
ε
n
=
A
2
n
−
1
ε
0
2
n
{\displaystyle \varepsilon _{n+1}\approx \varepsilon _{n}^{2}\overbrace {\frac {f''(\alpha )}{2f'(\alpha )}} ^{A}\quad \Rightarrow \quad \varepsilon _{n}=A^{2^{n}-1}\varepsilon _{0}^{2^{n}}}
כלומר, סדר האיטרציה הוא 2.
מצד שני, אם
α
{\displaystyle \alpha }
f
{\displaystyle f}
f
(
α
)
=
f
′
(
α
)
=
0
{\displaystyle f(\alpha )=f'(\alpha )=0}
ε
n
+
1
=
ε
n
2
2
!
f
″
(
α
)
+
⋯
ε
n
f
″
(
α
)
+
⋯
{\displaystyle \varepsilon _{n+1}={\frac {{\dfrac {\varepsilon _{n}^{2}}{2!}}f''(\alpha )+\cdots }{\varepsilon _{n}f''(\alpha )+\cdots }}}
ואז הגבול הוא בקירוב:
ε
n
+
1
≈
ε
n
2
{\displaystyle \varepsilon _{n+1}\approx {\frac {\varepsilon _{n}}{2}}}
כלומר התכנסות לינארית. באופן זה, שיטת ניוטון-רפסון מהווה אינדיקציה לשורש כפול.
[ עריכה ] ניתן לקבל התכנסות ריבועית באמצעות סדרת הקירובים המתוקנת הבאה:
x
n
+
1
=
x
n
−
2
f
(
x
n
)
f
′
(
x
n
)
{\displaystyle x_{n+1}=x_{n}-{\frac {2f(x_{n})}{f'(x_{n})}}}
[ עריכה ] כזכור, השגיאה באיטרציה ה-
n
{\displaystyle n}
ε
n
=
x
n
−
α
{\displaystyle \varepsilon _{n}=x_{n}-\alpha }
ε
n
+
1
+
α
=
ε
n
+
α
−
2
f
(
ε
n
+
α
)
f
′
(
ε
n
+
α
)
=
ε
n
⋅
f
′
(
ε
n
+
α
)
−
2
f
(
ε
n
+
α
)
f
′
(
ε
n
+
α
)
{\displaystyle \varepsilon _{n+1}+\alpha =\varepsilon _{n}+\alpha -{\frac {2f(\varepsilon _{n}+\alpha )}{f'(\varepsilon _{n}+\alpha )}}={\frac {\varepsilon _{n}\cdot f'(\varepsilon _{n}+\alpha )-2f(\varepsilon _{n}+\alpha )}{f'(\varepsilon _{n}+\alpha )}}}
נפתח מונה ומכנה לטור טיילור:
ε
n
+
1
=
ε
n
[
f
′
(
α
)
+
ε
n
f
″
(
α
)
+
⋯
]
−
2
[
f
(
α
)
+
ε
n
f
′
(
α
)
+
ε
n
2
2
!
f
″
(
α
)
+
⋯
]
f
′
(
α
)
+
ε
n
f
″
(
α
)
+
⋯
{\displaystyle \varepsilon _{n+1}={\frac {\varepsilon _{n}{\Big [}f'(\alpha )+\varepsilon _{n}f''(\alpha )+\cdots {\Big ]}-2\left[f(\alpha )+\varepsilon _{n}f'(\alpha )+{\dfrac {\varepsilon _{n}^{2}}{2!}}f''(\alpha )+\cdots \right]}{f'(\alpha )+\varepsilon _{n}f''(\alpha )+\cdots }}}
כעת, שוב, נסתכל על האברים המובילים וניקח גבול כאשר
n
{\displaystyle n}
ε
n
+
1
=
ε
n
3
3
!
f
‴
(
α
)
−
2
ε
n
3
3
!
f
‴
(
α
)
+
⋯
ε
n
f
″
(
α
)
+
⋯
≈
ε
n
2
f
‴
(
α
)
6
f
″
(
α
)
{\displaystyle \varepsilon _{n+1}={\frac {{\dfrac {\varepsilon _{n}^{3}}{3!}}f'''(\alpha )-{\dfrac {2\varepsilon _{n}^{3}}{3!}}f'''(\alpha )+\cdots }{\varepsilon _{n}f''(\alpha )+\cdots }}\approx {\frac {\varepsilon _{n}^{2}f'''(\alpha )}{6f''(\alpha )}}}
בהינתן פונקציה f עם שורש α בריבוי s, ניתן להציג:
f
(
x
)
=
(
x
−
α
)
s
h
(
x
)
{\displaystyle f(x)=(x-\alpha )^{s}h(x)}
h
(
α
)
≠
0
{\displaystyle h(\alpha )\neq 0}
x
n
+
1
=
x
n
−
s
f
(
x
n
)
f
′
(
x
n
)
{\displaystyle \ x_{n+1}=x_{n}-s{\frac {f(x_{n})}{f'(x_{n})}}}
נראה שבמקרה זה ישנה התכנסות ריבועית:
ϵ
n
+
1
=
[
ϵ
n
s
(
s
−
1
)
!
f
(
s
)
(
α
)
+
ϵ
n
s
+
1
s
!
f
(
s
+
1
)
(
α
)
+
.
.
.
]
ϵ
n
s
−
1
(
s
−
1
)
!
f
(
s
)
(
α
)
+
.
.
.
+
{\displaystyle \ \epsilon _{n+1}={\frac {\left[{\frac {\epsilon _{n}^{s}}{(s-1)!}}f^{(s)}(\alpha )+{\frac {\epsilon _{n}^{s+1}}{s!}}f^{(s+1)}(\alpha )+...\right]}{{\frac {\epsilon _{n}^{s-1}}{(s-1)!}}f^{(s)}(\alpha )+...}}+}
−
s
[
ϵ
n
s
s
!
f
(
s
)
(
α
)
+
ϵ
n
s
+
1
(
s
+
1
)
!
f
(
s
+
1
)
(
α
)
+
.
.
.
]
ϵ
n
s
−
1
(
s
−
1
)
!
f
(
s
)
(
α
)
+
.
.
.
≈
{\displaystyle {\frac {-s\left[{\frac {\epsilon _{n}^{s}}{s!}}f^{(s)}(\alpha )+{\frac {\epsilon _{n}^{s+1}}{(s+1)!}}f^{(s+1)}(\alpha )+...\right]}{{\frac {\epsilon _{n}^{s-1}}{(s-1)!}}f^{(s)}(\alpha )+...}}\approx }
≈
f
(
s
+
1
)
(
α
)
f
(
s
)
(
α
)
ϵ
n
2
s
(
s
+
1
)
{\displaystyle \ \approx {\frac {f^{(s+1)}(\alpha )}{f^{(s)}(\alpha )}}{\frac {\epsilon _{n}^{2}}{s(s+1)}}}
[ עריכה ] שימו לב כי אם α הוא שורש כפול של f, אז הוא יהיה שורש בודד של
h
(
x
)
=
f
(
x
)
f
′
(
x
)
{\displaystyle \ h(x)={\tfrac {f(x)}{f'(x)}}}
x
n
+
1
=
x
n
−
f
(
x
n
)
f
′
(
x
n
)
[
f
′
(
x
n
)
]
2
−
f
(
x
n
)
f
″
(
x
n
)
{\displaystyle \ x_{n+1}=x_{n}-{\frac {f(x_{n})f'(x_{n})}{[f'(x_{n})]^{2}-f(x_{n})f''(x_{n})}}}
[ עריכה ] בשיטה זו יוצרים שתי סדרות איטרטיביות במקביל, כאשר שתיהן מתקבלות משיטת ניוטון-רפסון, אך באחת מהן מציבים את ערכי הסדרה האחרת עבור הנגזרת:
{
x
n
+
1
=
x
n
−
f
(
x
n
)
f
′
(
x
n
)
z
n
+
1
=
z
n
−
f
(
z
n
)
f
′
(
x
n
)
{\displaystyle \ \left\{{\begin{aligned}x_{n+1}&=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}\\z_{n+1}&=z_{n}-{\frac {f(z_{n})}{f'(x_{n})}}\\\end{aligned}}\right.}
כאשר הניחוש ההתחלתי הוא:
x
0
=
b
,
z
0
=
a
{\displaystyle \ x_{0}=b,\ z_{0}=a}
המרחק בין שתי הסדרות בכל איטרציה קטן ריבועית ונתון על ידי:
x
n
−
z
n
≈
(
x
n
−
1
−
z
n
−
1
)
2
f
″
(
α
)
2
f
′
(
α
)
{\displaystyle \ x_{n}-z_{n}\approx (x_{n-1}-z_{n-1})^{2}{\frac {f''(\alpha )}{2f'(\alpha )}}}
שיטת סטפנסון אף היא מודיפיקציה של שיטת ניוטון-רפסון:
x
n
+
1
=
x
n
−
f
(
x
n
)
z
(
x
n
)
,
z
(
x
n
)
=
f
[
x
n
+
f
(
x
n
)
]
−
f
(
x
n
)
f
(
x
n
)
{\displaystyle \ x_{n+1}=x_{n}-{\frac {f(x_{n})}{z(x_{n})}}\ ,\qquad z(x_{n})={\frac {f[x_{n}+f(x_{n})]-f(x_{n})}{f(x_{n})}}}
כך שכאשר α הוא שורש בודד של f, שיטת סטפנסון היא מסדר 2 לפחות.
![{\displaystyle \varepsilon _{n+1}={\frac {\varepsilon _{n}\left[f'(\alpha )+\varepsilon _{n}f''(\alpha )+{\dfrac {\varepsilon _{n}^{2}}{2!}}f'''(\alpha )+\cdots \right]-\left[f(\alpha )+\varepsilon _{n}f'(\alpha )+{\dfrac {\varepsilon _{n}^{2}}{2!}}f''(\alpha )+\cdots \right]}{f'(\alpha )+\varepsilon _{n}f''(\alpha )+{\dfrac {\varepsilon _{n}^{2}}{2!}}f'''(\alpha )}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2ace51886a12b274030e24e6773b51b4ca821b2c)
![{\displaystyle \varepsilon _{n+1}={\frac {\varepsilon _{n}{\Big [}f'(\alpha )+\varepsilon _{n}f''(\alpha )+\cdots {\Big ]}-2\left[f(\alpha )+\varepsilon _{n}f'(\alpha )+{\dfrac {\varepsilon _{n}^{2}}{2!}}f''(\alpha )+\cdots \right]}{f'(\alpha )+\varepsilon _{n}f''(\alpha )+\cdots }}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/09f7b9ec6f8f6cd9dba70972ed35700df47338a5)
![{\displaystyle \ \epsilon _{n+1}={\frac {\left[{\frac {\epsilon _{n}^{s}}{(s-1)!}}f^{(s)}(\alpha )+{\frac {\epsilon _{n}^{s+1}}{s!}}f^{(s+1)}(\alpha )+...\right]}{{\frac {\epsilon _{n}^{s-1}}{(s-1)!}}f^{(s)}(\alpha )+...}}+}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2675d37af3c030e70fe55291d98a7be7b0440112)
![{\displaystyle {\frac {-s\left[{\frac {\epsilon _{n}^{s}}{s!}}f^{(s)}(\alpha )+{\frac {\epsilon _{n}^{s+1}}{(s+1)!}}f^{(s+1)}(\alpha )+...\right]}{{\frac {\epsilon _{n}^{s-1}}{(s-1)!}}f^{(s)}(\alpha )+...}}\approx }](https://wikimedia.org/api/rest_v1/media/math/render/svg/b8c109fe11d1344e16a5e143c567ea6f279f7521)
![{\displaystyle \ x_{n+1}=x_{n}-{\frac {f(x_{n})f'(x_{n})}{[f'(x_{n})]^{2}-f(x_{n})f''(x_{n})}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dca4f81275a18c1b3e9e85211072691a26e1a618)
![{\displaystyle \ x_{n+1}=x_{n}-{\frac {f(x_{n})}{z(x_{n})}}\ ,\qquad z(x_{n})={\frac {f[x_{n}+f(x_{n})]-f(x_{n})}{f(x_{n})}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ddd799f4080a4a42dccd40a381816a83bde90d00)
