Uniwersytet Kazimierza Wielkiego Wydziaª Matematyki, Fizyki i Techniki Instytut Matematyki Emilia Maria Jasi«ska 81336 Wybrane metody obliczania pierw...
17 downloads
29 Views
440KB Size
Uniwersytet Kazimierza Wielkiego Wydziaª Matematyki, Fizyki i Techniki Instytut Matematyki
Emilia Maria Jasi«ska 81336
Wybrane metody obliczania pierwiastków wielomianów Praca licencjacka wykonana pod kierunkiem dr in». K Mroczy«ska
Bydgoszcz 2016
2
Streszczenie pracy dyplomowej Temat pracy dyplomowej:
Wybrane metody obliczania pierwiastków wielomianów Imi¦ i nazwisko autora pracy: Emilia Maria Jasi«ska Nr albumu: 81336 Imi¦ i nazwisko promotora pracy: dr in». Karolina Mroczy«ska Sªowa kluczowe:
wielomian, pierwiastki wielomianów, lokalizacja pierwiastków, schemat Hornera, metoda Newtona, metoda Lagruerre'a, fraktal. Tre±¢ streszczenia
Tematem niniejszej pracy s¡ wybrane metody obliczania pierwiastków wielomianów. W pierwszym rozdziale przedstawione zostan¡ podstawowe zagadnienia zwi¡zane z wielomianami, pierwiastkami wielomianów wraz z przykªadami. Drugi rozdziaª to jedna z podstawowych metod obliczania pierwiastków wielomianów, czyli schemat Hornera. Za pomoc¡ schematu Hornera przedstawione zostanie rozwini¦cie Taylora wielomianu oraz poj¦cie de acji. W trzecim rozdziale przedstawione zostan¡ dwie popularne metody wyznaczania pierwiastków wielomianów. W rozdziale tym opisana zostanie ogólna metoda Newtona jak i metoda Newtona w dziedzinie zespolonej oraz metoda Laguerre'a.
3
Spis tre±ci Wst¦p
5
1 Wielomiany
6
2 Schemat Hornera
16
3 Inne metody wyznaczania pierwiastków wielomianów
22
Bibliogra a
30
4
Wst¦p Wielomiany s¡ u»ywane w wielu dziaªach matematyki, ze wzgl¦du na swoj¡ prostot¦ i dobrze poznane wªasno±ci. Istnieje kilkadziesi¡t metod szukania pierwiastków wielomianów; s¡ to gªównie metody iteracyjne, które wyznaczaj¡ przybli»enia pierwiastków lub pewien obszar w którym si¦ znajduj¡. Tematem pracy s¡ wybrane metody obliczania pierwiastków wielomianów. Praca skªada si¦ z trzech rozdziaªów. W pierwszym rozdziale zawarte s¡ podstawowe zagadnienia zwi¡zane z wielomianami, m.in. podstawowe dziaªania na wielomianach, twierdzenie Bézouta i zasadnicze twierdzenie algebry oraz twierdzenia o lokalizacji pierwiastków. Rozdziaª drugi opisuje schemat Hornera i jego zastosowanie. Ostatni rozdziaª zawiera opis dwóch metod numerycznych wyznaczania pierwiastków: metoda Newtona i metoda Laguerre'a. Opisane metody cz¦sto wykorzystywane s¡ w programach komputerowych. Wielomiany s¡ rozwa»ane zarówno nad zbiorem liczb rzeczywistych jak i zespolonych. Moim wkªadem w prac¦ jest uszczegóªowienie dowodów oraz samodzielne uªo»enie i obliczenie przykªadów.
5
Rozdziaª 1 Wielomiany Aby lepiej zrozumie¢ temat niniejszej pracy rozdziaª ten po±wi¦cony b¦dzie przypomnieniu najwa»niejszych poj¦¢ zwi¡zanych z wielomianami oraz pierwiastkami wielomianów. W rozdziale tym b¦dziemy opiera¢ si¦ o publikacje: [1], [3], [4], [5] i [7].
Standardowo w caªej pracy zbiór liczb naturalnych oznaczamy N, caªkowitych Z, wymiernych Q, rzeczywistych R i zespolonych C. Ponadto ±rodek okr¦gu (0, 0) b¦dziemy uto»samia¢ z 0.
De nicja 1.1. (Wielomian rzeczywisty) Wielomianem rzeczywistym stopnia n ∈ N∪ {0} nazywamy funkcj¦ W : R → R okre±lon¡ wzorem: W (x) = an xn + an−1 xn−1 + ... + a1 x + a0 ,
gdzie ak ∈ R dla 0 ¬ k ¬ n oraz an 6= 0. Liczby ak , gdzie 0 ¬ k ¬ n nazywamy wspóªczynnikami wielomianu W .
6
De nicja 1.2. (Wielomian zespolony) Wielomianem zespolonym stopnia n ∈ N∪ {0} nazywamy funkcj¦ W : C → C okre±lon¡ wzorem: W (x) = cn z n + cn−1 z n−1 + ... + c1 z + c0 ,
gdzie ck ∈ C dla 0 ¬ k ¬ n oraz cn 6= 0. Liczby ck , gdzie 0 ¬ k ¬ n nazywamy wspóªczynnikami wielomianu W .
Uwaga 1.3. 1. Najwy»sz¡ pot¦g¦ wielomianu W (x) nazywamy stopniem wielomianu. 2. Wielomiany postaci W (x) = a; a ∈ R (a ∈ C) maj¡ stopie« zerowy i nazywamy je wielomianami staªymi. 3. Przyjmujemy, »e funkcja W (x) ≡ 0 jest wielomianem zerowym.
De nicja 1.4. (Suma, ró»nica i iloczyn wielomianów) Niech P i Q b¦d¡ wielomianami o wspóªczynnikach rzeczywistych (zespolonych). Sum¦, ró»nic¦ i iloczyn wielomianów P i Q okre±lamy w sposób naturalny, tj. przyjmujemy: (P + Q)(x) = P (x) + Q(x), (P − Q)(x) = P (x) − Q(x), (P · Q)(x) = P (x) · Q(x).
Przykªady 1. Suma wielomianów: P (x) = 6 − 5x5 − 2x2 , Q(x) = 4x2 − 3x − x5 . P (x) + Q(x) = 6 − 5x5 − 2x2 + 4x2 − 3x − x5 = −6x5 + 2x2 − 3x + 6.
2. Ró»nica wielomianów: P (x) = −7x4 − 2x6 + 5, Q(x) = 5 − 8x + 3x6 . P (x) − Q(x) = −7x4 − 2x6 + 5 − 5 + 8x − 3x6 = −5x6 − 7x4 + 8x.
3. Iloczyn wielomianów: P (x) = 2 − 4x5 + x, Q(x) = −6x2 − x. P (x) · Q(x) = (2 − 4x5 + x)(−6x2 − x) = 24x7 + 4x6 − 6x3 − 13x2 − 2x.
7
De nicja 1.5. (Podzielno±¢ wielomianów) Mówimy, »e wielomian S jest ilorazem, a wielomian R reszt¡ z dzielenia wielomianu P przez wielomian Q, je»eli dla ka»dego x ∈ R (x ∈ C) speªniony jest warunek P (x) = Q(x) · S(x) + R(x)
oraz stopie« reszty R jest mniejszy od stopnia dzielnika Q. Je»eli R ≡ 0, to mówimy, »e wielomian P jest podzielny przez Q.
Przykªad Obliczymy iloraz oraz reszt¦ z dzielenia wielomianu P przez Q, gdzie: P (z) = iz 4 − 5z 3 + 2z 2 + 3 + i, Q(z) = z 2 − i.
Dzielenie wykonujemy pisemnie: (iz 4 − 5z 3 + 2z 2 + 3 + i)
: (z 2 − i) = iz 2 − 5z + 1
−iz 4 − z 2 −5z 3 + z 2 5z 3 − 5iz z 2 − 5iz −z 2 + i −5iz + i + 3 + i
Otrzymujemy zatem P (z) = (iz 2 − 5z + 1)(z 2 − 1) + (3 + 2i) − 5iz , gdzie ilorazem jest wielomian S(z) = iz 2 − 5z + 1, za± reszt¡ jest wielomian R(z) = −5iz + 3 + 2i.
De nicja 1.6. (Pierwiastek wielomianów) Liczb¦ rzeczywist¡ (zespolon¡) x0 nazywamy pierwiastkiem rzeczywistym (zespolonym) wielomianu W , je»eli W (x0 ) = 0.
8
Twierdzenie 1.7. (Twierdzenie Bézouta) Liczba x0 jest pierwiastkiem wielomianu W wtedy i tylko wtedy, gdy istnieje wielomian P taki, »e W (x) = (x − x0 )P (x).
Dowód. Zauwa»my, »e wielomian W (x) mo»na zapisa¢ w postaci: W (x) = (x − x0 )P (x) + R,
gdzie R jest reszt¡. Wobec tego: W (x0 ) = (x0 − x0 )P (x0 ) + R = 0 · P (x0 ) + R = R.
Otrzymali±my zatem równo±¢: W (x0 ) = R.
Korzystaj¡c z tej równo±ci, udowodnimy dwie implikacje: 1. Zaªó»my, »e liczba x0 jest pierwiastkiem wielomianu W (x), czyli, »e W (x0 ) = 0. Poniewa» W (x0 ) = R, zatem R = 0. Wynika st¡d, »e wielomian W (x) jest podzielny przez dwumian x − x0 . 2. Zaªó»my teraz, »e wielomian W (x) dzieli si¦ przez dwumian x − x0 , czyli, »e R = 0. Poniewa» W (x0 ) = R, zatem W (x0 ) = 0. Wynika st¡d, »e liczba x0 jest pierwiastkiem wielomianu W (x).
Wniosek 1.8. Reszta z dzielenia wielomianu W przez dwumian x − x0 jest równa W (x0 ).
9
Przykªady 1. Korzystaj¡c z twierdzenia Bézout, ustalimy przez jaki dwumian dzieli si¦ wielomian W (x) = x4 + x3 − 8x2 − x + 7. Poniewa» liczba 1 jest pierwiastkiem wielomianu W , wi¦c W (1) = 14 + 13 − 8 · 12 − 1 + 7 = 0. Zatem wielomian W (x) jest podzielny przez dwumian x − 1. 2. Ustalmy teraz reszt¦ z dzielenia wielomianu W (x) = x4 + x3 − 8x2 − x + 7 przez dwumian x − 2. Mamy: x0 = 2, W (x) = 24 + 23 − 8 · 22 − 2 + 7 = −3 6= 0.
Zatem reszta z dzielenia wielomianu wynosi −3, wi¦c wielomian nie jest podzielny przez dwumian x − 2, a st¡d 2 nie jest pierwiastkiem wielomianu.
De nicja 1.9. (Pierwiastek wielokrotny wielomianu) Liczba x0 jest pierwiastkiem k-krotnym wielomianu W , gdy istnieje taki wielomian P , »e W (x) = (x − x0 )k P (x)
oraz P (x0 ) 6= 0.
Uwaga 1.10. Je»eli x1 jest k1 -krotnym pierwiastkiem, x2 jest k2 -krotnym pierwiastkiem, ..., xm jest km -krotnym pierwiastkiem wielomianu, to wielomian ten podzielny jest przez iloczyn (x − x1 )k1 (x − x2 )k2 . . . (x − xm )km .
10
Zanim udowodnimy najwa»niejsze twierdzenie mówi¡ce o istnieniu pierwiastków wielomianu przypomnijmy de nicje zbioru ograniczonego, kresu dolnego zbioru oraz kresu górnego zbioru. Poj¦cia te b¦d¡ nam potrzebne w dowodzie twierdzenia.
De nicja 1.11. (Zbiór ograniczony) Zbiór A ⊂ R jest ograniczony je»eli jest ograniczony z doªu i z góry, to znaczy je»eli istniej¡ takie liczby rzeczywiste m, M , »e m¬a¬M
dla wszystkich a ∈ A.
De nicja 1.12. (kres dolny zbioru) Niech A ⊂ R b¦dzie zbiorem ograniczonym z doªu. Liczba m jest kresem dolnym zbioru A, co zapisujemy m = inf A, gdy speªnione s¡ nast¦puj¡ce warunki: a) dla dowolnego a ∈ A zachodzi nierówno±¢: m¬a
b) dla dowolnego ε > 0 istnieje taka liczba aε ∈ A, »e: aε < m + ε.
De nicja 1.13. (kres górny zbioru) Niech A ⊂ R b¦dzie zbiorem ograniczonym z góry. Liczba M jest kresem górnym zbioru A, co zapisujemy M = sup A, gdy speªnione s¡ nast¦puj¡ce warunki: a) dla dowolnego a ∈ A zachodzi nierówno±¢: a¬M
b) dla dowolnego ε > 0 istnieje aε ∈ A takie, »e M − ε < aε .
11
Przykªad 1. inf([0, ∞) ∧ Q) = 0 2. sup([0, ∞) ∧ Q) = ∞
Twierdzenie 1.14. (zasadnicze twierdzenie algebry, Gauss 1799) Ka»dy wielomian ró»ny od staªej ma co najmniej jeden pierwiastek w zbiorze liczb zespolonych.
Dowód. (Hardy, 1938) Niech W b¦dzie wielomianem ró»nym od wielomianu staªego. Chcemy wykaza¢, »e W (z0 ) = 0 dla pewnego z0 ∈ C. Z zaªo»enia o W wynika, »e |W (z)| → ∞, gdy |z| → ∞. Niech D b¦dzie takim koªem o ±rodku w 0, »e poza nim |W (z)| > |W (0)|. Niech z0 b¦dzie punktem, w którym jest osi¡gni¦te inf z∈D |W (z)|. Poniewa» 0 ∈ D, wi¦c |W (z0 )| ¬ |W (0)|. St¡d |W (z0 )| ¬ |W (z)| dla z ∈ C. Niech b¦dzie P (z) := W (z + z0 ). Chcemy wykaza¢, »e P (0) = 0, czyli P (0) = W (0 + z0 ) = W (z0 ) = 0. Wyra»amy P w postaci P (z) = c0 +cj z j +...+cn z n = c0 +cj z j +z j+1 R(z), gdzie cj 6= 0, a R jest wielomianem (by¢ mo»e równym 0). Aby udowodni¢, »e c0 = 0 zaªó»my przez sprzeczno±¢, »e c0 6= 0. Przypu±¢my, »e c0 6= 0. Niech v b¦dzie dowoln¡ liczb¡ zespolon¡, dla której cj v j = −c0 . De niujemy N := sup0<ε<1 |R(εv)|. Wybieramy ε ∈ (0, 1) tak maªe, aby byªo ε |v|j+1 N < |c0 |. Wtedy mamy ci¡g nierówno±ci |P (εv)| ¬ |c0 + cj εj v j | + εj+1 |v j+1 | |R(εv)| = = |c0 − c0 εj | + εj ε |v|j+1 N < |c0 | (1 − εj ) + εj |c0 | = = |c0 | − εj |c0 | + εj |c0 | = |c0 | = |P (0)| = |W (z0 )| ¬ ¬ |W (z0 + εv)| = |P (εv)| .
Zatem otrzymali±my sprzeczno±¢, st¡d c0 = 0.
Wniosek 1.15. Zasadnicze twierdzenie algebry nie zapewnia istnienia pierwiastków rzeczywistych. Wielomian W (x) = x2 + 1 jest wielomianem o wszystkich wspóªczynnikach rzeczywistych i nie ma pierwiastków rzeczywistych. Ma natomiast pierwiastki zespolone z0 = i, z1 = −i poniewa» W (i) = i2 + 1 = −1 + 1 = 0 oraz W (−i) = (−1)2 + 1 = −1 + 1 = 0.
12
Twierdzenie 1.16. Wielomian stopnia n ma dokªadnie n pierwiastków na pªaszczy¹nie zespolonej, gdy ka»dy z nich jest liczony tyle razy ile wynosi jego krotno±¢.
Twierdzenie 1.17. Wszystkie pierwiastki wielomianu W (z) = an z n + an−1 z n−1 + ... + a1 z + a0 le»¡ w kole otwartym o ±rodku w punkcie 0 pªaszczyzny zespolonej i promieniu r := 1 + |an |−1 max |ak | . 06k6n
Dowód. Niech b¦dzie α = max |ak | , 06k6n
sk¡d α |an |−1 = r − 1.
Je±li α = 0, to twierdzenie jest prawdziwe. W przeciwnym razie, je±li r > 1, |z| 6 r mamy nierówno±¢ n
|W (z)| > |an z | − |an−1 z
n−1
n
+ ... + a0 | > |an z | − α
n−1 X
|z|k >
k=0
> |an z n | − α |z|n (|z| − 1)−1 = |an z n | [1 − α |an |−1 (|z| − 1)−1 ] > > |an z n | [1 − α |an |−1 (r − 1)−1 ] = 0.
Przykªad Znajdziemy koªo o ±rodku w punkcie 0, zawieraj¡ce wszystkie pierwiastki wielomianu W (z) = z 5 − 4z 4 + z 3 + 8z 2 − z + 5.
Na mocy twierdzenia 1.17. to koªo ma promie« n
o
r = 1 + |a5 |−1 max |ak | = 1 + |1|−1 max |1| , |−4| , |1| , |8| , |−1| , |5| = 1 + 1 · 8 = 9. 06k65
13
Rozwa»my funkcj¦ 1 1 V (z) := z n W ( ) = z n [an ( )n + ... + a0 ] = an + an−1 z + an−2 z 2 + ... + a0 z n , z z
stopnia nie wi¦kszego od n, o wspóªczynnikach takich samych jak w wielomianie W (x), ale uporz¡dkowanych odwrotnie. Dla liczby zespolonej z0 ró»nej od zera nast¦puj¡ce warunki s¡ równowa»ne: V ( z10 ) = 0.
W (z0 ) = 0,
St¡d mamy kolejne twierdzenie o lokalizacji pierwiastków
Twierdzenie 1.18. Je±li wszystkie pierwiastki wielomianu V le»¡ w kole |z| 6 r, to wszystkie niezerowe pierwiastki wielomianu W le»¡ poza koªem |z| < r−1 .
Przykªad Znajdziemy koªo o ±rodku w punkcie 0, w którym wielomian W (z) = z 4 + z 3 + 6z 2 − 4z + 5 nie ma »adnego pierwiastka. Koªo zawieraj¡ce wszystkie pierwiastki wielomianu W ma promie«: r = 1 + |a4 |−1 max |ak | = 1 + |1|−1 max{1, 1, 6, |−4| , 5} = 1 + 1 · 6 = 7. 06k64
Wielomian V ma posta¢
1 1 1 1 1 V (z) = z 4 · W ( ) = z 4 · ( 4 + 3 + 6 2 − 4 + 5) = 1 + 6z 2 − 4z 3 + 5z 4 = z z z z z = 5z 4 − 4z 3 + 6z 2 + z + 1.
Na mocy twierdzenia 1.17. wszystkie pierwiastki tego wielomianu le»¡ w kole |x| < r, gdzie r = 1 + |a4 |−1 max |ak | = 1 + 06k64
1 1 11 · max{1, 1, 6, |−4| , 5} = 1 + · 6 = ; 5 5 5
wynika zatem, »e pierwiastki wielomianu W le»¡ poza koªem o promieniu 115 . Ostatecznie wnioskujemy, »e wszystkie te pierwiastki wielomianu W le»¡ w pier±cieniu 5 < |z| < 7 na pªaszczy¹nie zespolonej. 11
14
Przykªad Dla wielomianu W (z) = 2z 5 − 7z 4 − 5z 3 + 8z + 5 znale¹¢ koªa o ±rodku w punkcie 0: a) zawieraj¡ce wszystkie pierwiastki: r = 1 + |a5 |−1 max |ak | = 1 + |3|−1 · max{2, |−7| , |−5| , 8, 5} = 1 + 06k65
1 ·8=5 2
b) nie zawieraj¡ce »adnego pierwiastka:
1 1 1 1 1 V (z) = z 5 · W ( ) = z 5 · (2 5 − 7 4 − 5 3 + 8 + 5) = 2 − 7z − 5z 2 + 8z 4 + 5z 5 = z z z z z = 5z 5 + 8z 4 − 5z 2 − 7z + 2 r = 1 + |a5 |−1 max |ak | = 1 + |5|−1 · max{5, 8, |−5| , |−7| , 2} = 1 + 06k65
1 11 ·8= 5 3
Wszystkie pierwiastki le»¡ w nast¦puj¡cym pier±cieniu na pªaszczy¹nie zespolonej: 3 < |z| < 5. 11
15
Rozdziaª 2 Schemat Hornera Schemat Hornera to algorytm, który sªu»y do obliczania warto±ci wielomianu w punkcie oraz wyliczenia ilorazu i dzielenia z reszt¡ wielomianu W (x) przez dwumian x − a. Ze wzgl¦du na rekurencyjny charakter schematu oraz maª¡ liczb¦ wykonywanych mno»e« jest ten schemat cz¦sto u»ywany w programach komputerowych. W rozdziale tym b¦dziemy opiera¢ si¦ o nast¦puj¡ce publikacje: [2], [4], [5] i [6]. Przy dzieleniu wielomianu W = an xn + an−1 xn−1 + ... + a1 x + a0 stopnia n > 1 przez dwumian x − a tworzy si¦ tabelk¦ wspóªczynników:
a
an
an−1
an−2
...
ak+1
ak
...
a1
a0
an
bn−2
bn−3
...
bk
bk−1
...
b0
R
gdzie w drugim wierszu tabeli pojawiaj¡ si¦ wspóªczynniki ilorazu I(x) = an xn−1 + bn−2 xn−2 + ... + b1 x + b0
oraz reszta R z dzielenia, b¦d¡ca jednocze±nie warto±ci¡ wielomianu W w punkcie a. Z równo±ci W (x) = (x − a)I(x) + R dostajemy nast¦puj¡ce wzory rekurencyjne: bn−1 bn−2 bn−3 b0
= an = abn−1 + an−1 = abn−2 + an−2
.. .
= ab1 + a1
R = ab0 + a0
16
Przykªad Za pomoc¡ schematu Hornera obliczymy W (1), gdzie wielomian W okre±lony jest nast¦puj¡co: W (x) = x5 − 3x4 + 9x3 − 8x2 + 3x + 9. Obliczone warto±ci wpisujemy do tabelki:
1
1
−3
9
−8
3
9
1
−2
7
−1
2
11
Zatem R = 11 i mo»emy zapisa¢, »e W (x) = (x − 1)(x4 − 2x3 + 7x2 − x + 2) + 11.
Przykªad Obliczymy krotno±ci pierwiastków wielomianu W (x) = x5 +3x4 −7x3 −7x2 +18x−8 za pomoc¡ schematu Hornera, wiedz¡c, »e pierwiastki W (x) to 1, −4, −2.
1
3
−7
−7
18
−8
1
1
4
−3
−10
8
0
1
1
5
2
−8
0
1
1
6
8
0
−4
1
2
0
−2
1
0
Zatem krotno±¢ pierwiastka 1 wynosi 3, a pozostaªych 1. St¡d W (x) = (x − 1)3 (x + 4)(x + 2).
17
Bª¦dy numeryczne
Wykonuj¡c obliczenia na komputerze mog¡ pojawi¢ si¦ tzw. bª¦dy numeryczne. W schemacie Hornera bª¦dy numeryczne przy obliczaniu warto±ci danego wielomianu zale»¡ tylko i wyª¡cznie od bª¦dów zaokr¡gle«. Zatem zaªo»ymy, »e liczba ξ = x oraz wspóªczynniki wielomianu an , an−1 , ..., a0 s¡ dokªadnymi liczbami i wszystkie obliczenia przeprowadzane s¡ z dokªadno±ci¡ do m miejsc po przecinku. Wtedy oszacowanie bª¦du wyra»one jest wzorem: ∆W (ξ) =
|ξ|n − 1 · 0.5 · 10m . |ξ| − 1
Przykªad Obliczymy dla x = 1.7555 z jak¡ dokªadno±ci¡ nale»y przeprowadzi¢ obliczenia dla wielomianu W (x) = 2x4 − 6x3 + x2 + 3x − 1, aby uzyska¢ wynik z dokªadno±ci¡ do 0.001. |2|4 − 1 W (1.7555) 6 · 0.5 · 10k < 0.001 |2| − 1 k 6 −4.
Zatem wystarczy przeprowadzi¢ obliczenia z dokªadno±ci¡ do 4 miejsc po przecinku.
Dla wielomianu W (x) mo»na za pomoc¡ schematu Hornera okre±li¢ przedziaª w którym zawarte s¡ pierwiastki rzeczywiste. Metod¡ prób szukamy takie x = β > 0, aby wszystkie jego wspóªczynniki bk (k = 0, 1, ..., n − 1) ze schematu Hornera byªy nieujemne, tzn: bn−1 = an > 0,
bk > 0,
k = 0, 1, ..., n − 1.
(2.1)
Zatem wszystkie pierwiastki rzeczywiste xi (i = 1, 2, ..., m; m 6 n) wielomianu W (x) nie s¡ wi¦ksze od β to znaczy, »e xi 6 β , gdy» W (x) = (bn−1 xn−1 + bn−2 xn−2 + · · · + b0 )(x − β) + R > 0
dla dowolnego x > β . Wynika wi¦c, »e ka»da dowolna liczba, która jest wi¦ksza od β na pewno nie jest pierwiastkiem wielomianu W (x). 18
Aby uzyska¢ oszacowanie z doªu warto±ci pierwiastków xi rozpatrujemy nast¦puj¡cy wielomian (−1)n W (−x) = an xn − an−1 xn−1 + · · · + (−1)n a0 . (2.2) Nast¦pnie, aby speªniony byª warunek (2.1) dla wielomianu (2.2) znajdujemy liczb¦ x = α > 0. Wtedy dla wielomianu (2.2) pierwiastki rzeczywiste równe −xi (i = 1, 2, ..., m) speªniaj¡ nierówno±¢ −xi 6 α, zatem xi > −α. Otrzymujemy wi¦c, »e wszystkie pierwiastki rzeczywiste wielomianu W (x) le»¡ w przedziale domkni¦tym [−α, β].
Przykªad Znajdziemy przedziaª dla wielomianu W (x) = x4 − x3 + 4x2 − 2x − 3, w którym zawarte s¡ pierwiastki rzeczywiste. Dla a = 1.5, mamy:
1.5
1
−1
4
−2
−3
1
0.5
4.75
5.125
4.6875
Zatem warunek (2.1) jest speªniony, wi¦c xk 6 2. Przyjmuj¡c dla wielomianu (−1)4 W (−x) = (−1)4 ·[(−x)4 −(−x)3 +4·(−x)2 −2·(−x)−3] = x4 +x3 +4x2 +2x−3 a = 1 otrzymujemy
1
1
1
4
2
−3
1
2
6
8
5
Uzyskujemy zatem, »e wszystkie pierwiastki rzeczywiste le»¡ w przedziale domkni¦tym [−1, 1.5].
19
Rozwini¦cie Taylora wielomianu
Wyznaczaj¡c wielomian I i reszt¦ R wielomianu W (x) = (x − a)I(x) + R za pomoc¡ schematu Hornera, mo»na w taki sam sposób wyznaczy¢ iloraz i reszt¦ I(a) z dzielenia I przez dwumian x − a, itd. W (x) = (x − a)I(x) + R = = (x − a)[(x − a)I1 (x) + R1 ] + R = = (x − a)2 I1 (x) + (x − a)R1 + R = = (x − a)2 [(x − a)I2 (x) + R2 ] + (x − a)R1 + R = = (x − a)3 I2 (x) + (x − a)2 R2 + (x − a)R1 + R = ··· n
= (x − a) cn + (x − a)
gdzie
n−1
cn−1 + · · · + (x − a)2 c2 + (x − a)c1 + c0
c n = an
c2 = R2
cn−1 = Rn−1
.. .
c1 = R1 c0 = R
Zatem W (x) = an xn + an−1 xn−1 + · · · + a2 x2 + a1 x + a0 = = cn (x − a)n + cn−1 (x − a)n−1 + · · · + c2 (x − a)2 + c1 (x − a) + c0
W ten sposób uzyskali±my rozwini¦cie Taylora wielomianu w otoczeniu punktu a.
Przykªad Znajdziemy rozwini¦cie Taylora wielomianu W (x) = 2x4 − 8x3 + 16x2 − 10x + 5 w punkcie a = 2. Obliczamy wspóªczynniki ci za pomoc¡ nast¦puj¡cej tablicy:
20
2
−8
16
−10
5
2
2
−4
8
6
17
2
2
0
8
22
2
2
4
16
2
2
8
W (x) = (x − 2)(2x3 − 4x2 + 8x + 6) + 17 = (x − 2)[(x − 2)(2x2 + 8) + 22] + 17 = = (x − 2)[(x − 2) {(x − 2)(2x + 4) + 16} + 22] + 17 = = (x − 2)[(x − 2) {(x − 2)[(x − 2) · 2 + 8] + 16} + 22] + 17
Powstaje w ten sposób nowe wyra»enie wielomianu W : W (x) = 2(x − 2)4 + 8(x − 2)3 + 16(x − 2)2 + 22(x − 2) + 17.
Tak¡ posta¢ wielomianu nazywamy kompletnym schematem Hornera. Schemat Hornera ma zastosowanie w de acji, tzn. w procesie usuwania z wielomianu jego czynnika liniowego. Szukamy rozkªadu wielomianu na czynniki liniowe, tzn. wyznaczamy pierwiastki wielomianu W z równa« wielomianowych coraz ni»szych stopni, gdzie obni»amy stopie« wielomianu dziel¡c go przez odpowiedni czynnik liniowy. Stosuj¡c wielokrotnie de acj¦, obliczamy po jednym pierwiastku wielomianów coraz ni»szych stopni, co zmniejsza koszt oblicze«.
Przykªad Dla wielomianu W (x) = x4 + 3x3 − 19x2 − 4x + 21 wykonamy de acj¦ usuwaj¡c jego pierwiastek 3. Tworzymy tabelk¦:
3
1
3
−19
−4
21
1
6
−1
−7
0
Zatem otrzymujemy: x4 + 3x3 − 19x2 − 4x + 21 = (x − 3)(x3 + 6x2 − x − 7).
21
Rozdziaª 3 Inne metody wyznaczania pierwiastków wielomianów W rozdziale tym opisane zostan¡ dwie metody obliczania pierwiastków wielomianów: metoda Newtona oraz metoda Laguerre'a. Obie te metody s¡ iteracyjne, wi¦c podaj¡ przybli»one rozwi¡zanie. S¡ jednak powszechnie stosowane w obliczeniach na komputerach. Przedstawione w tym rozdziale twierdzenia b¦d¡ bez dowodów, poniewa» s¡ one skomplikowane, dªugie i wymagaªyby najpierw wprowadzenia wielu poj¦¢ z analizy matematycznej. Opiera¢ si¦ b¦dziemy o nast¦puj¡ce publikacje: [2], [5], [8] i [9]. Przypomnijmy wzór na pochodn¡ wielomianu: W (x) = an xn + an−1 xn−1 + · · · + a2 x2 + a1 x + a0 W 0 (x) = nan xn−1 + (n − 1)an−1 xn−2 + · · · + 2a2 x + a1 W ”(x) = n(n − 1)an xn−2 + (n − 1)(n − 2)an−1 xn−3 + · · · + 2a2 Metoda Newtona
Metoda Newtona, zwana równie» metod¡ stycznych jest metod¡ iteracyjn¡. Metoda ta sªu»y do wyznaczania przybli»onej warto±ci punktu xk+1 jako miejsca zerowe stycznych do wykresu w poprzednim punkcie xk . Omawiana metoda polega na obliczeniu przybli»onego rozwi¡zania równania f (x) = 0 wyrazami ci¡gu miejsc zerowych stycznych do f (x). Zatem wielomian stopnia stopnia pierwszego Wk okre±lony nast¦puj¡co (i)
Wk (xk ) = f (i) (xk ),
22
dla
i = 0, 1.
Wielomian Wk mo»na zapisa¢ w posta¢ w postaci W (xk ) = f 0 (xk )(x − xk ) + f (xk ).
Przyjmuj¡c za W (xk ) = 0 oraz x = xn+1 otrzymamy xk+1 = xk −
f (xk ) , f 0 (xk )
dla
k > 1.
Wzór ten tworzy de nicj¦ metody Newtona.
Interpretacja geometryczna metody Newtona (stycznych)
Rysunek 3.0.1: Metoda stycznych Geometrycznie metoda Newtona polega na przeprowadzeniu stycznej do wykresu funkcji y = f (x) w punkcie xk i przyj¦ciu punktu xk + 1 jako punkt przeci¦cia otrzymanej stycznej z osi¡ x (gdzie funkcja f jest wielomianem W ).
23
Przykªad Obliczymy wielomian W (x) = x3 − 4x2 + x + 6 metod¡ Newtona dla punktu pocz¡tkowego x0 = 0. Dla x0 = 0 otrzymujemy nast¦puj¡ce warto±ci: W (0) = 6, Pochodna W 0 (x) = 3x2 − 8x + 1, W 0 (0) = 1. Zatem dla x1 uzyskujemy now¡ warto±¢: x1 = x 0 −
W (0) 6 = 0 − = −6. 0 W (0) 1
Wykonuj¡c dalsze iteracje otrzymujemy: k
W (xk )
W 0 (xk )
xk
1
6, 0000
1, 0000
−6, 0000
2
−360, 0000
157, 0000
−3, 7070
3
−103, 6154
71, 8816
−2, 2655
4
−28, 4231
34, 5216
−1, 4422
5
−6, 7617
18, 7774
−1, 0821
6
−1, 0329
13, 1696
−1, 0037
7
−0, 0445
12, 0518
−1, 0000
8
0, 0000
12, 0000
−1, 0000
Zatem ci¡g xk jest szybko zbie»ny do pierwiastka −1, 0000.
Twierdzenie 3.1. (Bodewig) Niech xk i xk+1 b¦d¡ kolejnymi przybli»eniami pierwiastka otrzymanymi metod¡ Newtona dla wielomianu W stopnia n. Wtedy ten wielomian mam na pªaszczy¹nie zespolonej pierwiastek odlegªy od xk co najwy»ej o n |xk − xk+1 |.
24
Metoda Newtona w dziedzinie zespolonej
Opis tej metody podamy tylko w zarysie, poniewa» jest to temat trudny i obszerny. Zostaª jednak on tu zamieszczony ze wzgl¦du na zwi¡zek z fraktalami, które s¡ bardzo interesuj¡cym poj¦ciem matematycznym. Dla wielomianu W , który b¦dzie wielomianem stopnia co najmniej drugiego oraz dla ξ , czyli dla jednego z pierwiastków tego wielomianu, metoda Newtona startuj¡ca od punktu z pªaszczyzny zespolonej tworzy ci¡g okre±lony wzorami z0 := z, zk+1 := zk −
W (zk ) , W 0 (zk )
(n > 0).
Je±li limn→∞ zk = ξ , to punkt pocz¡tkowy z jest przyci¡gany przez ξ . Niech pocz¡tkowy wyraz z0 = z wyst¦puje w maªym otoczeniu jednego z pierwiastków okre±lonego wielomianu, to kolejne przybli»enia obliczone metod¡ Newtona b¦d¡ szybko zbie»ne do tego pierwiastka wielomianu. Zbiór wszystkich punktów z0 przyci¡ganych przez ξ , dla których ci¡g kolejnych przybli»e« Newtona b¦dzie zbie»ny do zk (gdzie zk to dowolny pierwiastek ci¡gu) nazywany jest zbiorem przyci¡gania dla tego pierwiastka. Ka»dy pierwiastek dowolnego wielomianu W ma swój zbiór przyci¡gania. Zbiory te s¡ parami rozª¡czne, poniewa» ci¡g zbie»ny do jednego pierwiastka nie mo»e by¢ zbie»ny do innego. Niech pewne liczby zespolone nie nale»¡ do »adnego zbioru przyci¡gania, wtedy mówimy, »e tymi liczbami s¡ punkty pocz¡tkowe, dla których metoda Newtona nie jest zbie»na. Te punkty tworz¡ zbiór Julii wielomianu W , nazwany tak na cze±¢ francuskiego matematyka Gatsona Julia. Dla zbioru Julii pªaszczyzna zespolona punktów pocz¡tkowych podzielona jest na dwa podzbiory. Pierwszy zbiór nazywany jest zbiorem uciekinierów, gdzie ci¡g dla pewnych punktów jest ograniczony, czyli nie d¡»y do niesko«czono±ci. Natomiast drugim zbiorem, gdzie dla innych punktów ci¡g ten jest nieograniczony, tzn. d¡»y do niesko«czono±ci nazywamy zbiorem wi¦¹niów. Zbiory uciekinierów i wi¦¹niów s¡ zbiorami niepustymi, dopeªniaj¡cymi si¦ oraz oba zbiory pokrywaj¡ pewn¡ cz¦±¢ pªaszczyzny zespolonej, dlatego posiadaj¡ wspóln¡ granic¦. Zatem granica zbioru uciekinierów jest jednocze±nie granic¡ zbioru wi¦¹niów i nazywamy j¡ wªa±nie zbiorem Julii. Zbiór ten na pªaszczy¹nie zespolonej skªada si¦ z brzegów otwartych zbiorów przyci¡gania, je±li wszystkie pierwiastki wielomianu W s¡ pojedyncze. 25
Przykªad zbioru Julii Dla wielomianu W (z) = z 3 − 1, obliczamy miejsca zerowe: z3 − 1 = 0 (z − 1)(z 2 + z + 1) = 0 z−1=0 z0 = 1 + i · 0
∧
z2 + z + 1 = 0 ∆ = b2 − 4ac = −3 = 3i2 √ ∆=i 3 √ 1 z1 = − (1 + i 3) ∨ 2
√ 1 z2 = (−1 + i 3) 2
Zatem wielomian ten ma trzy miejsca zerowe: √ √ 1 1 z0 = 1 + i · 0, z1 = − (1 + i 3) oraz z2 = (−1 + i 3). 2 2 Utworzymy ci¡g z0 , z1 , z2 , ... okre±lony zale»no±ci¡ rekurencyjn¡ zn+1 = zn −
W (zn ) zn3 − 1 3zn3 zn3 − 1 3zn3 − zn3 + 1 2zn3 + 1 = z − = − = = = n W 0 (zn ) 3zn2 3zn2 3zn2 3zn2 3zn2 2z 3 1 2zn 1 = n2 + 2 = + 2. 3zn 3zn 3 3zn
Je»eli punkt pocz¡tkowy jest dowolny to iteracje d¡»¡ odpowiednio do rozwi¡za« i i 1, e4π 3 , e2π 3 , gdzie regiony te s¡ basenami przyci¡gania pierwiastków wielomianu W , które oznaczone s¡ odpowiednio ró»nymi kolorami.
Rysunek 3.0.2: Przykªad zbioru Julii. Baseny przyci¡gania dla wielomianu W (z) = z 3 − 1 przy iterowaniu metod¡ Newtona. Po lewej stronie zaznaczony kolorem czarnym zbiór przyci¡gania rozwi¡zania z = 1, a po prawej stronie brzegi zbiorów.
26
Widoczne na rysunku zbiory maj¡ szczególn¡ struktur¦ fraktaln¡. Fraktale zostaªy wprowadzone przez Benoita Mandelbrota. Poj¦cie fraktali dotyczy obiektów geometrycznych, które maj¡ nietrywialn¡ struktur¦, bowiem s¡ samopodobne, tzn. niezale»nie od skali obserwacji jej struktura jest niezmienna. Polega ona równie» na tym, »e na powi¦kszonym fragmencie obiektu zawieraj¡cym dwa zbiory widzimy powtórzone ogólne wzorce, które powtarzaj¡ si¦ przy ponownym powi¦kszaniu. Przykªadami fraktali s¡ liczne przykªady obiektów geometrycznych takich jak zbiór Cantora, krzywa von Kocha, dywan Sierpi«skiego czy omówiony zbiór Julii.
Rysunek 3.0.3: Dywan Sierpi«skiego jako przykªad fraktala
27
Metoda Laguerre'a
Metoda Laguerre'a jest to metoda obliczania pierwiastków wielomianu W stopnia n. Jest to metoda iteracyjna, gdzie przej±cie od danego przybli»enia z pierwiastka do nowego pierwiastka okre±lone jest za pomoc¡ wzorów: A := −
W 0 (z) W (z)
B := A2 − C := n−1 [A ±
W ”(z) W (z)
q
(n − 1)(nB − A2 )]
znowe = z +
(3.1) (3.2) (3.3)
1 , C
gdzie W 0 i W ” to odpowiednio pierwsza i druga pochodna wielomianu W .
Uwaga 3.2. Znak C wybieramy tak, »eby |C| byªo jak najwi¦ksze.
Twierdzenie 3.3. (Kahan, 1967) Je±li W jest wielomianem stopnia n, z jest dowoln¡ liczb¡ zespolon¡, a C jest okreq ±lone nast¦puj¡co C := n−1 [A± (n − 1)(nB − A2 )], to W ma pierwiastek na pªasz√
czy¹nie zespolonej odlegªy od z co najwy»ej o
n . |C|
Twierdzenie 3.4. Je±li wielomian rzeczywisty W ma wszystkie pierwiastki rzeczywiste, to ci¡g generowany za pomoc¡ algorytmu Laguerre'a dla dowolnego punktu pocz¡tkowego jest zbie»ny monotonicznie do jednego z nich.
28
Przykªad Niech W (z) = z 4 + 2z 3 − 2z − 1. Obliczymy A, B i C ze wzorów odpowiednio (3.1), (3.2) i (3.3). Otrzymujemy nast¦puj¡ce pochodne wielomianu W (z): W 0 (z) = 4z 3 + 6z 2 − 2 W 00 (z) = 12z 2 + 12z . A=−
W 0 (z) 4z 3 + 6z 2 − 2 2(z + 1)2 (2z − 1) 4z − 2 =− 4 = − =− 2 3 3 W (z) z + 2z − 2z − 1 (z − 1)(z + 1) z −1
!2
W 00 (z) 4z − 2 12z 2 + 12z B = A2 − = − 2 − 4 = W (z) z −1 z + 2z 3 − 2z − 1 16z 2 − 16z + 4 12z(z + 1) 16z 2 − 16z + 4 − 12z(z − 1) = − = = (z 2 − 1)2 (z − 1)(z + 1)3 (z 2 − 1)2 4z 2 − 4z − 4 = (z 2 − 1)2
C = n−1 [A ± " −1
=4
4z − 2 − 2 z −1 "
v u u ± t(4 − 1)
q
(n − 1)(nB − A2 )] =
4z 2 − 4z − 4 16z 2 − 16z + 4 4· − (z 2 − 1)2 (z 2 − 1)2
v u
!#
=
!#
16z 2 − 16z + 16 − 16z 2 + 16z − 4 1 4z − 2 u = · − 2 ± t3 · = 4 z −1 (z 2 − 1)2 " # " # " # s 4z − 2 36 1 4z − 2 6 1 −4z + 8 1 ± = · − 2 + = · = = · − 2 4 z −1 (z 2 − 1)2 4 z − 1 z2 − 1 4 z2 − 1 −z + 2 = 2 z −1
znowe = z +
1 z2 − 1 z(−z + 2) + z 2 − 1 −2z − 1 2z + 1 =z+ = = = C −z + 2 −z + 2 −z + 2 z−2 2z + 1 =0 z−2 2z + 1 = 0 1 znowe = − 2 1 2
Zatem metod¡ Laguerre'a otrzymali±my znowe = − .
29
Bibliogra a [1] Dobrowolska M., Karpi«ski M., Lech J.,
Matematyka 2. Podr¦cznik. Zakres rozszerzony, Gda«skie Wydawnictwo O±wiatowe, Gda«sk 2014. [2] Dryja M., Jankowscy J. i M., Przegl¡d metod i algorytmów numerycznych, Wydawnictwo Naukowo-Techniczne, Warszawa 2012. [3] Gewert M., Skoczylas Z., Analiza matematyczna 1. De nicje, twierdzenia, wzory, O cyna Wydawnicza GiS, Wrocªaw 2001. [4] Jurlewicz T., Skoczylas Z., Algebra liniowa 1. De nicje, twierdzenia, wzory, O cyna Wydawnicza GiS, Wrocªaw 2001. [5] Kincaid D., Cheney W., Analiza numeryczna, Wydawnictwo Naukowo-Techniczne, Warszawa 2006. [6] Klamka J., Ogonowski Z., Janicki M., Stasik M., Metody numeryczne, Wydawnictwo Politechniki l¡skiej, Gliwice 1998. [7] Marcinkowska H., Analiza matematyczna (funkcje jednej zmiennej), 2008 praca dost¦pna pod adresem:
http://www.math.uni.wroc.pl/∼ jwr/anal2008/marcinkowska_analiza1.pdf [8] Peitgen H.-O., Ju¨rgens H., Saupe D., Granice chaosu. Fraktale. Cz¦±¢ 1, Wydawnictwo Naukowe PWN, Warszawa 1997. [9] Peitgen H.-O., Ju¨rgens H., Saupe D., Granice chaosu. Fraktale. Cz¦±¢ 2, Wydawnictwo Naukowe PWN, Warszawa 2002. [10] http://www.sta.amu.edu.pl/∼awoj/OLAT/miteracyjne.pdf
30
Emilia Maria Jasi«ska 81336 matematyka sp. nansowo-ubezpieczeniowa pierwszego stopnia stacjonarne
O±wiadczenie
autora pracy dyplomowej wiadomy odpowiedzialno±ci prawnej, o±wiadczam, »e praca dyplomowa: Wybrane metody obliczania pierwiastków wielomianów
zostaªa wykonana samodzielnie i nie zawiera tre±ci uzyskanych w sposób niezgodny z obowi¡zuj¡cymi przepisami. O±wiadczam równie», »e: 1) przedstawiona praca nie byªa wcze±niej przedmiotem procedur zwi¡zanych z uzyskaniem tytuªu zawodowego uczelni; 2) drukowana wersja pracy dyplomowej jest identyczna z wprowadzon¡ do programu APD elektroniczn¡ wersj¡.
Bydgoszcz, dnia .......................
.........................................
![#2- K. B. Winters - Plush #2 [revisado]](https://docer.tips/img/300x300/2-k-b-winters-plush-2-revisado_5a645525d64ab2085406cd9d.jpg)
