Instytut Automatyki Politechniki Łódzkiej - Metody Numeryczne wykład 6
W6 - 1
Właściwości metod iteracyjnych
iteratio=powtarzanie (procesu numerycznego w celu ulepszenia
wcześniejszych wyników)=kolejne przybliżanie
metoda iteracji prostej:
x=F(x)
równanie iteracji
)
x
(
F
x
i
i
=
+1
dostateczny warunek zbieżności:
1
<
)
x
(
'
F
szybkość zbieżności tym większa im mniejszy
)
x
(
'
F
Def.:
Niech x
i
będzie ciągiem kolejnych przybliżeń zbieżnej metody iteracyjnej:
a
x
lim
i
i
=
∞
→
. Jeżeli istnieje liczba
1
≥
p
taka, że
1
1
0
1
=
<
≠
=
−
−
+
∞
→
p
gdy
C
,
C
a
x
a
x
lim
p
i
i
i
to mówimy, że metoda jest rzędu p w punkcie a. Liczba C jest nazywana
stałą asymptotyczną błędu.
Instytut Automatyki Politechniki Łódzkiej - Metody Numeryczne wykład 6
W6 - 2
Jeżeli z jedną iteracją związany jest koszt K to
K
p
E
1
=
nazywamy
wskaźnikiem efektywności metody.
Tw.
Jeżeli równaniem iteracji jest
)
x
(
x
i
i
Φ
=
+1
i dla k=1,..,p-1
0
=
Φ
)
a
(
)
k
(
,
to metoda jest rzędu p.
dow.
1
2
1
2
+
+
−
+
Φ
−
+
+
+
Φ
−
+
Φ
−
+
Φ
=
Φ
=
p
i
)
p
(
p
i
i
i
i
i
)
a
x
(
(
O
!
p
)
a
(
)
a
x
(
!
)
a
(
'
'
)
a
x
(
)
a
(
'
)
a
x
(
)
a
(
)
x
(
x
L
!
p
)
a
(
)
a
x
(
a
x
lim
)
p
(
p
i
i
i
Φ
=
−
−
+
∞
→
1
Instytut Automatyki Politechniki Łódzkiej - Metody Numeryczne wykład 6
W6 - 3
Metody iteracyjne rozwiązywania równań nieliniowych
Szukamy rzeczywistego pierwiastka równania
0
=
)
x
(
f
. Jeżeli jest nim
ξ
, a
i
x
jest przybliżeniem
ξ
(
i
x
leży w otoczeniu
ξ
), to
L
+
−
+
−
+
−
+
=
=
=
)
x
(
f
!
)
x
(
)
x
(
'
'
f
!
)
x
(
)
x
(
'
f
)
x
(
)
x
(
f
)
(
f
i
)
(
i
i
i
i
i
i
3
3
2
3
2
0
ξ
ξ
ξ
ξ
zaniedbując wyrazy rzędy większego niż
ν
otrzymujemy równanie do
wyznaczenia kolejnego przybliżenia
1
+
i
x
Dla
1
=
ν
(metoda Newtona-Raphsona stopnia I):
)
x
(
'
f
)
x
x
(
)
x
(
f
i
i
i
i
−
+
=
+1
0
)
x
(
'
f
)
x
(
f
x
x
i
i
i
i
−
=
+1
Instytut Automatyki Politechniki Łódzkiej - Metody Numeryczne wykład 6
W6 - 4
Dla
2
=
ν
(metoda Newtona-Raphsona stopnia II):
)
x
(
'
'
f
!
)
x
x
(
)
x
(
'
f
)
x
x
(
)
x
(
f
i
i
i
i
i
i
i
2
0
2
1
1
−
+
−
+
=
+
+
)
x
(
'
'
f
)
x
(
'
'
f
)
x
(
'
f
)
x
(
'
f
)
x
(
'
f
x
x
i
i
i
i
i
i
i
2
2
1
−
±
−
=
+
Zbieżność lokalna!
Rząd zbieżności metody N-R I dla jednokrotnego zera (
0
≠
)
(
'
f
ξ
):
)
x
(
'
f
)
x
(
f
x
)
x
(
),
x
(
x
i
i
−
=
Φ
Φ
=
+1
0
1
2
=
+
−
=
Φ
=
ξ
ξ
x
)
x
(
'
f
)
x
(
'
'
f
)
x
(
f
)
x
(
'
f
)
x
(
'
f
)
(
'
, czyli p=2
Instytut Automatyki Politechniki Łódzkiej - Metody Numeryczne wykład 6
W6 - 5
Rząd zbieżności metody N-R I dla m-krotnego zera
(
0
≠
−
=
)
(
g
),
x
(
g
)
x
(
)
x
(
f
m
ξ
ξ
):
),
x
(
'
g
)
x
(
)
x
(
g
)
x
(
m
)
x
(
'
f
m
m
1
1
−
−
−
+
−
=
ξ
ξ
,
)
x
(
'
g
)
x
(
)
x
(
g
)
x
(
m
)
x
(
g
)
x
(
x
)
x
(
m
m
m
1
1
−
−
−
+
−
−
−
=
Φ
ξ
ξ
ξ
m
)
(
'
1
1
−
=
Φ
ξ
, czyli p=1
m
C
1
1
−
=
Instytut Automatyki Politechniki Łódzkiej - Metody Numeryczne wykład 6
W6 - 6
Metoda siecznych
)
x
(
f
)
x
(
f
x
)
x
(
f
x
)
x
(
f
)
x
(
f
)
x
(
f
)
x
x
)(
x
(
f
x
)
x
(
'
f
)
x
(
f
x
x
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
1
1
1
1
1
1
−
−
−
−
−
+
−
−
=
−
−
−
≈
−
=
p=1.618..
Regula falsi
dane
0
<
)
a
(
f
)
x
(
f
,
a
,
x
i
i
i
i
obliczamy
,
)
a
(
f
)
x
(
f
)
a
(
f
x
)
x
(
f
a
i
i
i
i
i
i
i
−
−
=
µ
wybieramy
0
1
1
>
⇐
=
=
+
+
)
(
f
)
x
(
f
a
a
x
i
i
i
i
i
i
µ
µ
0
1
1
<
⇐
=
=
+
+
)
(
f
)
x
(
f
x
a
x
i
i
i
i
i
i
µ
µ
p=1
Instytut Automatyki Politechniki Łódzkiej - Metody Numeryczne wykład 6
W6 - 7
Układy równań nieliniowych
[
]
⋅
⋅
⋅
=
⋅
=
=
=
=
)
(
f
)
(
f
)
(
f
)
(
F
,
x
,
,
x
,
x
X
,
)
X
(
F
n
,...,
i
,
)
x
,
,
x
,
x
(
f
n
T
n
n
i
M
L
L
2
1
2
1
2
1
0
1
0
Dla
1
=
ν
(metoda Newtona-Raphsona stopnia I):
)
X
X
)(
X
(
'
F
)
X
(
F
i
i
i
i
−
+
=
+1
0
∂
∂
∂
∂
∂
∂
∂
∂
∂
∂
∂
∂
∂
∂
∂
∂
∂
∂
=
n
n
n
n
n
n
n
n
n
n
n
n
n
n
n
x
x
x
f
x
x
x
f
x
x
x
f
x
x
x
f
x
x
x
f
x
x
x
f
x
x
x
f
x
x
x
f
x
x
x
f
X
F
)
,
(
)
,
(
)
,
(
)
,
(
)
,
(
)
,
(
)
,
(
)
,
(
)
,
(
)
(
'
1
2
1
1
1
1
2
2
1
2
1
1
2
1
1
2
1
1
1
1
1
L
L
L
L
M
M
M
M
L
L
L
L
L
L
L
L