Instytut Automatyki Politechniki Łódzkiej - Metody Numeryczne ET3 wykład 4
W4 - 1
U
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
B
i
B
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 ET3 wykład 4
W4 - 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 ET3 wykład 4
W4 - 3
U
Metody iteracyjne rozwiązywania równań nieliniowych
Szukamy rzeczywistego pierwiastka równania
0
=
)
x
(
f
.
Metoda bisekcji.
Weźmy przedział
[a, b], na krańcach którego f(x) jest różnego znaku. Jeśli f(x)
jest ciągła, to osiąga wartość zero wewnątrz [a, b]. Połowiąc przedział [a, b] i
badając znak funkcji na krańcach przedziałów zawężamy przedział zawierający
pierwiastek równania f(x)=0. Ponieważ prowadzimy obliczenia w arytmetyce
zmiennopozycyjnej nie znajdziemy pewnie punktu, w którym f(x)=0. Naszym
celem będzie wić znalezienie przedziału o długości nie przekraczajacej zadanej
dokładności obliczeń (mogą to być dwie sąsiednie liczby zmiennoprzecinkowe), w
którym f(x) zmienia znak.
Złoty podział
Instytut Automatyki Politechniki Łódzkiej - Metody Numeryczne ET3 wykład 4
W4 - 4
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
U
Newtona-Raphsona stopnia I
U
):
)
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 ET3 wykład 4
W4 - 5
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 ET3 wykład 4
W4 - 6
Rząd zbieżności metody N-R I dla m-krotnego zera
(
0
≠
−
=
)
(
g
),
x
(
g
)
x
(
)
x
(
f
m
ξ
ξ
):
),
(
'
)
(
)
(
)
(
)
(
'
1
x
g
x
x
g
x
m
x
f
m
m
ξ
ξ
−
+
−
=
−
,
)
(
'
)
(
)
(
)
(
)
(
)
(
)
(
1
x
g
x
x
g
x
m
x
g
x
x
x
m
m
m
ξ
ξ
ξ
−
+
−
−
−
=
Φ
−
m
)
(
'
1
1
−
=
Φ
ξ
, czyli p=1
m
C
1
1
−
=
Instytut Automatyki Politechniki Łódzkiej - Metody Numeryczne ET3 wykład 4
W4 - 7
PRZYKŁAD 1:
m
a
a>0
a
x
m
=
,
0
=
− a
x
m
1
1
−
+
−
−
=
m
n
m
n
n
n
mx
a
x
x
x
1
1
)
1
(
−
+
−
+
=
m
n
m
n
n
mx
x
m
a
x
. ,
m=3, a=7
n x(n)
x(13)-x(n) err(n-1)^2
0 4
-2,087068817
1 2,8125
-0,899568817
2 2,169979424
-0,257048241
0,809224057
3 1,94217793
-0,029246748
0,066073798
4 1,913369391
-0,000438208
0,000855372
5 1,912931283
-1,00353E-07
1,92027E-07
6 1,912931183
-5,55112E-15
1,00707E-14
7 1,912931183
0
3,08149E-29
8 1,912931183
0
0
9 1,912931183
0
0
10 1,912931183
0
0
11 1,912931183
0
0
12 1,912931183
0
0
13 1,912931183
0
0
Instytut Automatyki Politechniki Łódzkiej - Metody Numeryczne ET3 wykład 4
W4 - 8
Instytut Automatyki Politechniki Łódzkiej - Metody Numeryczne ET3 wykład 4
W4 - 9
PRZYKŁAD 2:
?
=
2
π
:
0
1
)
sin(
=
−
x
.
0
=
)
x
cos(
.
)
cos(
1
)
sin(
1
n
n
n
n
x
x
x
x
−
−
=
+
)
sin(
)
cos(
1
n
n
n
n
x
x
x
x
−
−
=
+
n x(n)
x(23)-x(n)
0 1,0000000000
0,5707962609
1 1,2934079930
0,2773882679
2 1,4329983667
0,1377978942
3 1,5020065769
0,0687896840
4 1,5364150214
0,0343812395
5 1,5536073677
0,0171888932
6 1,5622020589
0,0085942021
7 1,5664992193
0,0042970416
8 1,5686477763
0,0021484846
9 1,5697220520
0,0010742089
10 1,5702591894
0,0005370715
11 1,5705277581
0,0002685028
12 1,5706620425
0,0001342185
13 1,5707291846
0,0000670763
14 1,5707627557
0,0000335052
15 1,5707795413
0,0000167197
16 1,5707879340
0,0000083269
17 1,5707921304
0,0000041305
18 1,5707942286
0,0000020323
19 1,5707952777
0,0000009832
20 1,5707958023
0,0000004587
21 1,5707960645
0,0000001964
22 1,5707961957
0,0000000652
23 1,5707962609
n x(n)
2
π
-x(n)
0 1,0000000000
0,5707963268
1 1,6420926159
-0,0712962891
2 1,5706752772
0,0001210496
3 1,5707963268
0,0000000000
4 1,5707963268
0,0000000000
5 1,5707963268
0,0000000000
6 1,5707963268
0,0000000000
7 1,5707963268
0,0000000000
Instytut Automatyki Politechniki Łódzkiej - Metody Numeryczne ET3 wykład 4
W4 - 10
U
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..
U
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 ET3 wykład 4
W4 - 11
U
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
U
Newtona-Raphsona stopnia I
U
):
)
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
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
L
L
L
L
M
M
M
M
L
L
L
L
L
L
L
L
1
1
1
1
1
2
1
2
1
1
2
1
1
1
1
1
1
1
Instytut Automatyki Politechniki Łódzkiej - Metody Numeryczne ET3 wykład 4
W4 - 12
Wyznaczanie zer wielomianów
1 Metoda Maehly’ego
0
)
(
=
x
P
)
(
'
)
(
1
i
i
i
i
x
P
x
P
x
x
−
=
+
wyznaczamy zero z
1
Powinniśmy wyznaczyć współczynniki wielomianu
1
1
)
(
)
(
z
x
x
P
x
P
−
=
i prowadzić iteracje
wg
)
(
'
)
(
1
1
1
i
i
i
i
x
P
x
P
x
x
−
=
+
. Zamiast tego:
2
1
1
1
)
(
)
(
)
(
'
)
(
'
z
x
x
P
z
x
x
P
x
P
−
−
−
=
1
1
1
1
)
(
)
(
'
)
(
)
(
'
)
(
z
x
x
P
x
P
x
P
x
x
P
x
P
x
x
i
i
i
i
i
i
i
i
i
−
−
−
=
−
=
+
Po wyznaczeniu zer z
1
, z
2
, ...z
j
∑
=
+
−
−
−
=
j
k
k
i
i
i
i
i
i
z
x
x
P
x
P
x
P
x
x
1
1
)
(
)
(
'
)
(
Instytut Automatyki Politechniki Łódzkiej - Metody Numeryczne ET3 wykład 4
W4 - 13
2 Metoda Lehmera-Shura
Kryterium sprawdzające istnienie zera w kole jednostkowym:
0
1
1
1
a
z
a
z
a
z
a
)
z
(
f
n
n
n
n
+
+
+
+
=
−
−
L
n
n
n
n
*
a
z
a
z
a
z
a
)
z
(
f
+
+
+
+
=
−
−
1
1
1
0
L
,
)
a
Im(
j
)
a
Re(
a
−
=
)
z
(
f
a
)
z
(
f
a
)]
z
(
f
[
T
:
]
[
T
*
n
−
=
⋅
0
2
2
0
0
0
0
0
0
0
0
n
n
*
n
a
a
a
a
a
a
)
(
f
a
)
(
f
a
)]
(
f
[
T
−
=
−
=
−
=
)]
z
(
f
[
T
[
T
)]
z
(
f
[
T
,
)],
z
(
f
[
T
[
T
)]
z
(
f
[
T
j
j
1
2
−
=
=
L
A) Czy
0
0
=
)
(
f
? TAK, to perwiastek=0, NIE to B)
B) Czy
0
0
<
)]
(
f
[
T
TAK, pierwiastek w kole jednostkowym, NIE to C)
C) Obliczyć
k
,
,
,
j
)],
z
(
f
[
T
j
L
2
1
=
aż do uzyskania
0
0
<
)]
(
f
[
T
k
(wtedy istnieje pierwiastek w kole jednostkowym)
lub
0
0
=
)]
(
f
[
T
k
(wtedy żaden pierwiastek nie leży wewnątrz koła
jednostkowego, jeśli
)]
z
(
f
[
T
k
1
−
jest stałą)
Jeżeli wielomian
)
z
(
f
ma zero wewnątrz koła
r
c
z
=
−
, to wielomian
)
c
rz
(
f
)
z
(
g
+
=
ma zero wewnątrz koła jednostkowego (
)
z
(
g
może
mieć współczynniki zespolone).
Instytut Automatyki Politechniki Łódzkiej - Metody Numeryczne ET3 wykład 4
W4 - 14
-2
-1
0
1
2
3
-2
-1.5
-1
-0.5
0
0.5
1
1.5
2
R
..... 2R
oooooooo
7
0
8
2
3
4
,...,
k
,
e
)
/
cos(
R
/
k
j
=
π
π
.........
5
4R
........
10
4R
Instytut Automatyki Politechniki Łódzkiej - Metody Numeryczne ET3 wykład 4
W4 - 15
Dzielenie wielomianów
Czynnik liniowy:
)
z
(
R
)
b
z
b
z
b
z
b
)(
z
z
(
a
z
a
z
a
z
a
)
z
(
f
n
n
n
n
n
n
n
n
0
0
1
2
2
1
1
0
0
1
1
1
+
+
+
+
+
−
=
=
+
+
+
+
=
−
−
−
−
−
−
L
L
0
0
0
0
1
0
1
0
2
1
0
b
z
a
)
z
(
R
,...,
n
,
n
k
,
b
z
a
b
,
b
k
k
k
n
+
=
−
−
=
+
=
=
+
+
Czynnik kwadratowy:
)
q
,
r
(
B
z
)
q
,
r
(
A
)
b
z
b
z
b
z
b
)(
q
rz
z
(
a
z
a
z
a
z
a
)
z
(
f
n
n
n
n
n
n
n
n
+
+
+
+
+
+
+
+
=
=
+
+
+
+
=
−
−
−
−
−
−
0
1
3
3
2
2
2
0
1
1
1
L
L
0
1
0
1
2
1
2
1
0
3
2
0
qb
a
)
q
,
r
(
B
,
qb
rb
a
)
q
,
r
(
A
,...,
n
,
n
k
,
qb
rb
a
b
,
b
b
o
k
k
k
k
n
n
−
=
−
−
=
−
−
=
−
−
=
=
=
+
+
+
−
Instytut Automatyki Politechniki Łódzkiej - Metody Numeryczne ET3 wykład 4
W4 - 16
SCHEMAT i-tej ITERACJI METODY BAIRSTOW’A
i
i
q
q
,
r
r
=
=
Obliczyć
0
1
0
1
2
1
2
1
0
3
2
0
qb
a
)
q
,
r
(
B
,
qb
rb
a
)
q
,
r
(
A
,...,
n
,
n
k
,
qb
rb
a
b
,
b
b
o
k
k
k
k
n
n
−
=
−
−
=
−
−
=
−
−
=
=
=
+
+
+
−
Obliczyć
1
0
4
3
0
2
1
1
2
1
−
−
−
=
−
−
−
=
=
=
+
+
+
−
−
,
,...,
n
,
n
k
,
qd
rd
b
d
,
d
d
k
k
k
k
n
n
Wartości kolejnego przybliżenia:
⎥
⎦
⎤
⎢
⎣
⎡
⎥
⎦
⎤
⎢
⎣
⎡
+
−
−
⎥
⎦
⎤
⎢
⎣
⎡
=
⎥
⎦
⎤
⎢
⎣
⎡
−
−
−
+
+
)
q
,
r
(
B
)
q
,
r
(
A
d
r
d
d
q
d
d
q
r
q
r
i
i
i
i
i
i
i
i
i
i
1
0
1
0
0
1
1
1
Instytut Automatyki Politechniki Łódzkiej - Metody Numeryczne ET3 wykład 4
W4 - 17
Przykład Wilkinsona
!
x
a
x
)
x
(
)
x
)(
x
(
)
x
(
f
20
20
2
1
19
19
20
+
+
+
=
−
−
−
=
L
L
210
19
−
=
a
0
5
10
15
20
25
30
-10
-8
-6
-4
-2
0
2
4
6
8
10
210
19
−
=
a
***
9
19
10
210
−
+
−
=
a
**
6
19
10
210
−
+
−
=
a
**
3
19
10
210
−
+
−
=
a
**
Instytut Automatyki Politechniki Łódzkiej - Metody Numeryczne ET3 wykład 4
W4 - 18
Niech a będzie pojedynczym pierwiastkiem r-nia f(x)=0 i niech x
n
<a zbiega
do a.
Na mocy tw. o wartości średniej istnieje
]
,
[
a
x
c
n
∈
takie, że
)
(
'
)
(
c
f
x
f
a
x
n
n
=
−
.
Stąd
ε
δ
:
)
(
'
)
(
'
min
)
(
,
=
≈
≤
−
a
f
c
f
x
f
a
x
a
x
n
n
n
gdzie δ jest dokładnością z jaką obliczamy f(x).
Dla pierwiastków o krotności p mamy:
p
p
a
f
p
1
)
(
)
(
!
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
=
δ
ε