מתוך ויקיספר, אוסף הספרים והמדריכים החופשי
כפי שנראה בהמשך, קיימות שיטות איטרטיביות שונות. ניתן למיין אותן לפי מספר הנקודות בהן הן משתמשות על-מנת לייצר את הקירוב הבא. התאוריה לכשעצמה היא מסובכת, לכן אנו נעסוק בתאוריה של שיטות איטרטיביות חד-נקודתיות בלבד.
להלן מודל כללי של שיטה איטרטיבית חד-נקודתית כלשהי:
בעזרת השיטה האיטרטיבית נוכל לייצר סדרת מספרים אשר מהווים קירוב לשורש. נסמן את השורש של הפונקציה
f
(
x
)
{\displaystyle f(x)}
α
{\displaystyle \alpha }
f
(
α
)
≡
0
{\displaystyle f(\alpha )\equiv 0}
lim
n
→
∞
x
n
→
α
{\displaystyle \lim _{n\to \infty }x_{n}\to \alpha }
נניח כי אנו בודקים סדרת מספרים
x
n
{\displaystyle x_{n}}
f
(
x
n
)
{\displaystyle f(x_{n})}
ϵ
{\displaystyle \epsilon }
|
x
n
+
1
−
x
n
|
<
ϵ
{\displaystyle {\Big |}x_{n+1}-x_{n}{\Big |}<\epsilon }
|
f
(
x
n
)
|
<
ϵ
{\displaystyle {\Big |}f(x_{n}){\Big |}<\epsilon }
|
1
−
x
n
x
n
+
1
|
<
ϵ
{\displaystyle \left|1-{\frac {x_{n}}{x_{n+1}}}\right|<\epsilon }
|
f
(
x
n
+
1
)
−
f
(
x
n
)
|
<
ϵ
{\displaystyle {\Big |}f(x_{n+1})-f(x_{n}){\Big |}<\epsilon }
|
1
−
f
(
x
n
)
f
(
x
n
+
1
)
|
<
ϵ
{\displaystyle \left|1-{\frac {f(x_{n})}{f(x_{n+1})}}\right|<\epsilon }
[ עריכה ] נסמן את השיטה ב-
Φ
{\displaystyle \Phi }
x
n
+
1
=
Φ
(
x
n
)
{\displaystyle x_{n+1}=\Phi (x_{n})}
n
{\displaystyle n}
ϵ
n
=
x
n
−
α
{\displaystyle \epsilon _{n}=x_{n}-\alpha }
n
{\displaystyle n}
x
n
=
ϵ
n
+
α
{\displaystyle x_{n}=\epsilon _{n}+\alpha }
x
n
+
1
=
ϵ
n
+
1
+
α
{\displaystyle x_{n+1}=\epsilon _{n+1}+\alpha }
ϵ
n
+
1
+
α
=
Φ
(
α
+
ϵ
n
)
{\displaystyle \epsilon _{n+1}+\alpha =\Phi (\alpha +\epsilon _{n})}
Φ
(
ϵ
n
+
α
)
{\displaystyle \Phi (\epsilon _{n}+\alpha )}
α
{\displaystyle \alpha }
ϵ
n
+
1
+
α
=
Φ
(
α
)
+
ϵ
n
Φ
′
(
α
)
+
ϵ
n
2
2
!
Φ
″
(
α
)
+
ϵ
n
3
3
!
Φ
‴
(
α
)
+
⋅
{\displaystyle \epsilon _{n+1}+\alpha =\Phi (\alpha )+\epsilon _{n}\Phi '(\alpha )+{\frac {\epsilon _{n}^{2}}{2!}}\Phi ''(\alpha )+{\frac {\epsilon _{n}^{3}}{3!}}\Phi '''(\alpha )+\cdot }
נשתמש בעובדה שהשיטה האיטרטיבית צריכה להחזיר את השורש של הפונקציה, במידה והיא מקבלת אותו:
α
=
lim
n
→
∞
x
n
=
lim
n
→
∞
Φ
(
x
n
−
1
)
=
Φ
(
lim
n
→
∞
x
n
−
1
)
=
Φ
(
α
)
{\displaystyle \alpha =\lim _{n\to \infty }x_{n}=\lim _{n\to \infty }\Phi (x_{n-1})=\Phi (\lim _{n\to \infty }x_{n-1})=\Phi (\alpha )}
Φ
(
α
)
=
α
{\displaystyle \Phi (\alpha )=\alpha }
α
{\displaystyle \alpha }
x
=
Φ
(
x
)
{\displaystyle x=\Phi (x)}
שיטת החיתוך עם y=x ). נציב קשר זה בטור ונקבל:
ϵ
n
+
1
=
ϵ
n
Φ
′
(
α
)
+
ϵ
n
2
2
!
Φ
″
(
α
)
+
ϵ
n
3
3
!
Φ
‴
(
α
)
+
⋯
{\displaystyle \epsilon _{n+1}=\epsilon _{n}\Phi '(\alpha )+{\frac {\epsilon _{n}^{2}}{2!}}\Phi ''(\alpha )+{\frac {\epsilon _{n}^{3}}{3!}}\Phi '''(\alpha )+\cdots }
על-פי הגדרה, סדר האיטרציה נקבע לפי סדר הנגזרת הראשונה שאינה מתאפסת. לדוגמה:
אם
Φ
′
(
α
)
≠
0
{\displaystyle \Phi '(\alpha )\neq 0}
ϵ
n
+
1
≈
ϵ
n
Φ
′
(
α
)
{\displaystyle \epsilon _{n+1}\approx \epsilon _{n}\Phi '(\alpha )}
אם
Φ
′
(
α
)
=
0
{\displaystyle \Phi '(\alpha )=0}
Φ
″
(
α
)
≠
0
{\displaystyle \Phi ''(\alpha )\neq 0}
ϵ
n
+
1
≈
ϵ
n
2
2
!
Φ
″
(
α
)
{\displaystyle \epsilon _{n+1}\approx {\frac {\epsilon _{n}^{2}}{2!}}\Phi ''(\alpha )}
כללית, אם:
Φ
(
k
)
(
α
)
=
0
,
∀
0
≤
k
<
m
{\displaystyle \Phi ^{(k)}(\alpha )=0\ ,\ \forall \ 0\leq k<m}
Φ
(
m
)
(
α
)
≠
0
{\displaystyle \Phi ^{(m)}(\alpha )\neq 0}
ϵ
n
+
1
≈
ϵ
n
m
m
!
Φ
(
m
)
(
α
)
{\displaystyle \epsilon _{n+1}\approx {\frac {\epsilon _{n}^{m}}{m!}}\Phi ^{(m)}(\alpha )}
ככל שסדר האיטרציה גדול יותר, הקשר בין כל שתי שגיאות (איטרציות) עוקבות הוא "חזק" יותר, כלומר קצב ההתכנסות מהיר יותר.
[ עריכה ] אם קיימים מספרים
m
,
c
{\displaystyle m,c}
lim
n
→
∞
|
ϵ
n
+
1
ϵ
n
m
|
=
c
{\displaystyle \lim _{n\to \infty }\left|{\frac {\epsilon _{n+1}}{\epsilon _{n}^{m}}}\right|=c}
m
{\displaystyle m}
c
=
|
Φ
(
m
)
(
α
)
|
m
!
{\displaystyle c={\frac {{\Big |}\Phi ^{(m)}(\alpha ){\Big |}}{m!}}}
c
≠
0
{\displaystyle c\neq 0}
אם
Φ
(
x
)
{\displaystyle \Phi (x)}
[
a
,
b
]
{\displaystyle [a,b]}
a
≤
Φ
(
x
)
≤
b
,
∀
x
∈
[
a
,
b
]
{\displaystyle a\leq \Phi (x)\leq b\ ,\ \forall x\in [a,b]}
x
=
Φ
(
x
)
{\displaystyle x=\Phi (x)}
אם בנוסף
|
Φ
′
(
x
)
|
<
1
,
∀
x
∈
[
a
,
b
]
{\displaystyle {\Big |}\Phi '(x){\Big |}<1\ ,\ \forall x\in [a,b]}
α
{\displaystyle \alpha }
אם מתקיימים שני התנאים הנ"ל, אז הפוקנציה האיטרטיבית
Φ
(
x
)
{\displaystyle \Phi (x)}
α
{\displaystyle \alpha }
x
0
{\displaystyle x_{0}}
![{\displaystyle [a,b]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9c4b788fc5c637e26ee98b45f89a5c08c85f7935)
![{\displaystyle a\leq \Phi (x)\leq b\ ,\ \forall x\in [a,b]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2387086ded746e66a5f7eee20cf5ba3e87ef5f24)
![{\displaystyle {\Big |}\Phi '(x){\Big |}<1\ ,\ \forall x\in [a,b]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ed3e14f660d7ebd7711a6e1e9217f1641c69687a)
