Instytut Automatyki Politechniki A
ódzkiej - Metody Numeryczne wykład 7
Wyznaczanie zer wielomianów
1 Metoda Maehly ego
P(x) = 0
P(xi )
xi+1 = xi - wyznaczamy zero z1
P'(xi )
P(x)
Powinniśmy wyznaczyć współczynniki wielomianu P1(x) = i prowadzić iteracje
x - z1
P1(xi )
wg xi+1 = xi - . Zamiast tego:
P1'(xi )
P'( x) P(x)
P1'( x) = -
x - z1
( x - z1 )2
P1( xi ) P(xi )
xi+1 = xi - = xi -
P(xi )
P1'(xi )
P'(xi ) -
xi - z1
Po wyznaczeniu zer z1, z2, ...zj
P(xi )
xi+1 = xi -
j
P(xi )
P'(xi ) -
"
xi - zk
k=1
W7-1
Instytut Automatyki Politechniki A
ódzkiej - Metody Numeryczne wykład 7
2 Metoda Lehmera-Shura
Kryterium sprawdzające istnienie zera w kole jednostkowym:
f ( z ) = anzn + an-1zn-1 + L+ a1z + a0
*
f ( z ) = a0zn + a1zn-1 + L+ an-1z + an, a = Re( a ) - j Im( a )
*
T [�"] : T [ f ( z )] = a0 f ( z ) - an f ( z )
*
T [ f ( 0 )] = a0 f ( 0 ) - an f ( 0 ) = a0a0 - ana0 = a0 2 - an 2
2 j j -1
T [ f ( z )] = T [T [ f ( z )], L ,T [ f ( z )] = T [T [ f ( z )]
A) Czy f ( 0 ) = 0 ? TAK, to perwiastek=0, NIE to B)
B) Czy T [ f ( 0 )] < 0 TAK, pierwiastek w kole jednostkowym, NIE to C)
j
C) Obliczyć T [ f ( z )], j = 1,2,L,k aż do uzyskania
k
T [ f ( 0 )] < 0 (wtedy istnieje pierwiastek w kole jednostkowym)
k
lub T [ f ( 0 )] = 0 (wtedy żaden pierwiastek nie leży wewnątrz koła
k -1
jednostkowego, jeśli T [ f ( z )] jest stałą)
W7-2
Instytut Automatyki Politechniki A
ódzkiej - Metody Numeryczne wykład 7
Jeżeli wielomian f ( z ) ma zero wewnątrz koła z - c = r, to wielomian
g( z ) = f ( rz + c ) ma zero wewnątrz koła jednostkowego ( g( z ) może
mieć współczynniki zespolone).
R
2
..... 2R
1.5
oooooooo
1
3R
jĄk / 4
e ,
0.5
2cos(Ą / 8 )
0
k = 0,...,7
-0.5
.........4R 5
-1
-1.5 ........ 4R10
-2
-2 -1 0 1 2 3
W7-3
Instytut Automatyki Politechniki A
ódzkiej - Metody Numeryczne wykład 7
Dzielenie wielomianów
Czynnik liniowy:
f ( z ) = anzn + an-1zn-1 +L+ a1z + a0 =
= ( z - z0 )( bn-1zn-1 + bn-2zn-2 +L+ b1z + b0 )+ R( z0 )
bn = 0, bk = ak +1 + z0bk +1 , k = n - 1,n - 2,...,0
R( z0 ) = a0 + z0b0
Czynnik kwadratowy:
f ( z ) = anzn + an-1zn-1 + L+ a1z + a0 =
= ( z2 + rz + q )( bn-2zn-2 + bn-3zn-3 + L+ b1z + b0 ) + A( r ,q )z + B( r ,q )
bn = bn-1 = 0, bk = ak+2 - rbk+1 - qbk+2 , k = n - 2,n - 3,...,0
A( r ,q ) = a1 - rb0 - qb1 , B( r ,q ) = ao - qb0
W7-4
Instytut Automatyki Politechniki A
ódzkiej - Metody Numeryczne wykład 7
SCHEMAT i-tej ITERACJI METODY BAIRSTOW A
r = ri , q = qi
Obliczyć
bn = bn-1 = 0, bk = ak+2 - rbk+1 - qbk+2 , k = n - 2,n - 3,...,0
A( r ,q ) = a1 - rb0 - qb1 , B( r ,q ) = ao - qb0
Obliczyć
dn-1 = dn-2 = 0, dk = -bk+1 - rdk+1 - qdk+2 , k = n - 3,n - 4,...,0,-1
Wartości kolejnego przybliżenia:
-1
ri +1 ri d-1 d0 A( ri ,qi )
Ą# ń# Ą# ń# Ą# ń# Ą# ń#
= -
ó#q Ą# ó#q Ą# ó# Ą# ó#B( ri ,qi )Ą#
Ł# Ś# Ł# Ś# Ł#- qid0 d-1 + rid0 Ś# Ł# Ś#
i +1 i
W7-5
Instytut Automatyki Politechniki A
ódzkiej - Metody Numeryczne wykład 7
Przykład Wilkinsona
f ( x ) = ( x - 1 )( x - 2 )L( x - 20 ) = x20 + a19 x19 + L+ 20! a19 = -210
10
8
a19 = -210 ***
6
a19 = -210 + 10-9**
4
a19 = -210 + 10-6**
2
a19 = -210 + 10-3 **
0
-2
-4
-6
-8
-10
0 5 10 15 20 25 30
W7-6
Instytut Automatyki Politechniki A
ódzkiej - Metody Numeryczne wykład 7
Niech a będzie pojedynczym pierwiastkiem r-nia f(x)=0 i niech xna.
c "[xn,a]
Na mocy tw. o wartości średniej istnieje takie, że
f (xn )
xn - a =
.
f '(c)
Stąd
f (xn )
�
xn - a d" H" =: �
min f '(c) f '(a)
xn ,a
gdzie � jest dokładnością z jaką obliczamy f(x).
Dla pierwiastków o krotności p mamy:
1
p
�# ś#
�p!
ś# ź#
� =
( p)
ś# ź#
f (a)
�# #
W7-7