Instytut Automatyki Politechniki Łódzkiej - Metody Numeryczne w Inżynierii wykład 6
W7-1
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 w Inżynierii wykład 6
W7-2
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
+
+
+
+
=
−
−
"
n
n
n
n
*
a
z
a
z
a
z
a
)
z
(
f
+
+
+
+
=
−
−
1
1
1
0
"
,
)
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
−
=
=
"
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
"
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łą)
Instytut Automatyki Politechniki Łódzkiej - Metody Numeryczne w Inżynierii wykład 6
W7-3
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).
-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 w Inżynierii wykład 6
W7-4
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
+
+
+
+
+
−
=
=
+
+
+
+
=
−
−
−
−
−
−
"
"
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
"
"
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 w Inżynierii wykład 6
W7-5
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 w Inżynierii wykład 6
W7-6
Przykład Wilkinsona
!
x
a
x
)
x
(
)
x
)(
x
(
)
x
(
f
20
20
2
1
19
19
20
+
+
+
=
−
−
−
=
"
"
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 w Inżynierii wykład 6
W7-7
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
)
(
)
(
!
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
=
δ
ε