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 - z1 )2
(x
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:
ri +1 ri d-1 d0 -1 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