UNIVERZITA PALACKÉHO V OLOMOUCI PŘÍRODOVĚDECKÁ FAKULTA KATEDRA MATEMATICKÉ ANALÝZY A APLIKACÍ MATEMATIKY
BAKALÁŘSKÁ PRÁCE Metody pro výpočet kořenů polynomů
Vedoucí diplomové práce: RNDr. Horymír Netuka, Ph.D. Rok odevzdání: 2013
Vypracovala: Zuzana Vranová III. ročník
Prohlášení Prohlašuji, že jsem tuto práci napsala samostatně za vedení RNDr. Horymíra Netuky, Ph.D. a že jsem v seznamu použité literatury uvedla všechny zdroje použité při zpracování práce. V Olomouci dne
Poděkování Ráda bych na tomto místě poděkovala mému vedoucímu práce RNDr. Horymíru Netukovi, Ph.D. za věnovaný čas a rady, bez kterých by tato práce nemohla vzniknout.
Obsah Úvod ...................................................................................................................................... 4 1 Řešení algebraických rovnic ............................................................................................... 5 1.1 Násobné kořeny ........................................................................................................... 5 1.2.1 Snížení stupně polynomu ......................................................................................... 7 2 Startovací metody .............................................................................................................. 8 2.1 Grafická metoda .......................................................................................................... 8 2.2 Metoda bisekce ............................................................................................................ 8 3 Müllerova metoda .............................................................................................................. 9 3.1 Algoritmus Müllerovy metody .................................................................................. 11 4 Laguerrova metoda ........................................................................................................... 13 4.1 Algoritmus Laguerrovy metody ................................................................................ 15 5 Bairstowova metoda ......................................................................................................... 17 5.1 Algoritmus Bairstowovy metody .............................................................................. 21 6 Příklady............................................................................................................................. 23 7 Problémy při hledání kořenů polynomů ........................................................................... 35 Závěr .................................................................................................................................... 36 Seznam příloh ...................................................................................................................... 37 Literatura ............................................................................................................................. 38
Úvod Tato práce se zabývá různými numerickými metodami sloužícími k výpočtu kořenů polynomů s reálnými koeficienty. Kořeny lineárního polynomu a polynomů druhého i třetího stupně můžeme vyřešit velmi jednoduše pomocí vzorců. Pro polynomy vyšších stupňů je však řešení složitější, jelikož žádné vzorce neexistují nebo jsou velmi komplikované, takže využíváme iteračních metod. K odhadu kořenů polynomu můžeme použít jakoukoliv metodu, která slouží k nalezení kořene nelineární rovnice, ale existují i metody, které jsou zvláště vhodné pro polynomy. V první kapitole si připomeneme základní vlastnosti algebraických rovnic. V druhé kapitole se budeme zabývat startovacími metodami, grafickou metodou a metodou bisekce, které nám sice neposkytnou příliš přesné výsledky, ale jsou vhodné k hrubému odhadu řešení. V dalších kapitolách se budeme postupně zabývat iteračními metodami pro výpočet kořenů polynomů, konkrétně metodou Müllerovou, Laguerrovou a Bairstowovou. Tyto metody konvergují k hledanému řešení poměrně rychle, ale potřebujeme znát alespoň přibližnou polohu kořenů. Metody uvedené v této práci jsou vhodné i pro určení komplexních kořenů polynomu. V této práci se také zaměříme na vytvoření programů uvedených metod v programovacím jazyce Fortran 77 a s jejich pomocí vyřešíme konkrétní příklady. Realizace uvedených metod ve Fortanu jsou přiloženy na CD.
4
1 Řešení algebraických rovnic Polynomy jsou zvláštní formou nelineárních rovnic. V následujících kapitolách se budeme zabývat různými numerickými metodami, kterými lze najít množinu řešení algebraické rovnice ve tvaru ( ) Polynomem stupně
rozumíme funkci ( )
kde
jsou reálné koeficienty polynomu ( ) a
je stupeň polynomu a
Číslo
je kořenem polynomu pokud platí rovnost ( )
Kořeny koeficienty
mohou být reálné i komplexní, jednoduché nebo násobné. Pokud jsou všechny reálné, pak komplexní kořeny jsou vždy komplexně sdružené .
Základní věta algebry nám říká, že polynom stupně
má právě
kořenů. Každý kořen
počítáme tolikrát, kolik je jeho násobnost. Polynom ( ) můžeme zapsat také ve tvaru ( )
(
)(
)
(
)
Descartovo pravidlo znamének nám říká, že počet kladných kořenů polynomu je roven počtu znaménkových změn nenulových koeficientů
nebo je menší o sudé číslo.
1.1 Násobné kořeny V praxi se často setkáváme s funkcemi, které nemají jednoduchý kořen a jeho výpočet je tedy obtížnější. Geometrická interpretace násobnosti kořenů je taková, že pokud má funkce násobné kořeny, pak má tečnu na ose . Nelineární rovnice ( ) ( )
má (
-násobný kořen )
( ),
jestliže pro
kde
5
( )
platí
Kořen
má násobnost
, právě tehdy, když platí ( )
( )
( )
(
)
( )
ale ( )
Pokud
, pak ( )
Například v rovnici
( )
( )
a rovnice má jednoduchý kořen. řešení
je dvojnásobným kořenem.
6
1.2.1 Snížení stupně polynomu Jedním z možných postupů, jak určit všechny kořeny polynomu, je postupně snižovat stupeň polynomu. To provádíme tak, že polynom
( ) vydělíme lineárním činitelem
je již známý kořen daného polynomu.
, kde
( )
(
) ( )
( ) je polynom stupně Stupeň polynomu
( ) také můžeme snížit dělením kvadratickým trojčlenem
( )
. ( ) kde
( ) je polynom stupně
( ) ( ) ,
( )
( )
a
( ) je
zbytek, ( ) Pokračujeme hledáním kořenů rovnice určíme všech
( )
. Postup opakujeme do té doby, než
kořenů polynomu.
Metody používané k hledání kořenů, můžeme rozdělit do dvou skupin a) startovací metody b) zpřesňující metody
7
2 Startovací metody V praxi je situace taková, že rychle konvergující metody většinou vyžadují dobrou počáteční aproximaci. Je tedy dobré začít nějakou méně přesnou, avšak spolehlivou metodou. Rychlost konvergence startovacích metod není příliš velká, ale zato konvergují vždy a jejich výhodou je, že není potřeba znát počáteční aproximaci.
2.1 Grafická metoda Představu o počtu a pozici kořenů rovnice si můžeme snadno udělat, pokud si vykreslíme ( ). Přibližné kořeny rovnice
graf funkce
( )
pak zjistíme jako x-ové
souřadnice průsečíků grafu funkce s osou x. Pomocí grafické metody také můžeme zjistit, zda má rovnice v daném intervalu nějaký kořen.
2.2 Metoda bisekce Metoda bisekce neboli metoda půlení intervalu je velmi jednoduchá a univerzální metoda založená na známé větě z matematické analýzy. Je to poměrně pomalá metoda, ale zato je jednou z nejspolehlivějších. Spočívá v tom, že se snažíme nalézt velmi malý interval, ve kterém funkce mění své znaménko. Předpokládáme, že
je reálná spojitá funkce na intervalu 〈
〉a〈
〉 je takový interval,
že znaménka čísel ( ) a ( ) v koncových bodech intervalu jsou opačná. Potom existuje kořen
( )
rovnice
znaménko v intervalu 〈
〈
a
〉. Existuje-li první derivace funkce
〉, pak má funkce
Sestrojíme posloupnost intervalů 〈 Položíme 〈
〉
〈
〉a
〉 (
1. Pokud ( )
je
2. Pokud ( )
potom interval 〈
a nemění-li
v tomto intervalu právě jeden kořen . 〈
),
〉
〈
〉
je středem intervalu 〈
〉,
kořenem rovnice. 〉 bude ten z intervalů 〈
který platí, že v jeho krajních bodech má funkce
8
různá znaménka.
〉, 〈
〉 pro
3 Müllerova metoda Müllerova metoda byla poprvé prezentována Davidem E. Müllerem roku 1956. Je vhodná k výpočtu kořenů jakékoliv funkce, ale je převážně využívána k určení kořenů polynomů. Tato metoda slouží i k nalezení násobných kořenů. V kombinaci s některou ze startovacích metod nám Müllerova metoda poskytuje velmi efektivní řešení. Tato metoda je založena na metodě sečen, která začíná se dvěma počátečními aproximacemi kořene body [
( )] , [
. Další aproximaci určíme jako průsečík přímky procházející ( )] a osy . Müllerova metoda využívá tři počáteční aproximace,
kterými proloží parabolu. Jako další aproximaci poté vezmeme průsečík sestrojené paraboly s osou .
V Müllerově metodě začínáme se třemi (dobrými) aproximacemi rovnice [
( )] [
( )
Sestrojíme
.
( )] [
polynom,
( )] ( )
(
)
(
)
kde ( ) (
(
) [ ( ) ( )[ ( ) (
( )] )( ( )] )(
( )( ( )(
) [ ( ) ) )[ ( ) )
9
( )]
( )]
procházející
kořene body
jsou určeny z podmínek
Konstanty ( )
(
)
(
)
( )
(
)
(
)
( )
(
)
(
)
Abychom určili
, kořen polynomu , položíme ( )
. Vzhledem k zaokrouhlovacím
chybám při odečítání téměř stejných čísel, kořen rovnice vyjádříme ve tvaru
√ Znaménko u odmocniny vybíráme tak, aby bylo shodné se znaménkem . Tedy tak, aby jmenovatel v absolutní hodnotě byl co největší.
( )√ Tato metoda je vhodná i k odhadu komplexních kořenů polynomů. Ze vztahu výše vidíme, že výraz pod odmocninou může nabývat i záporných hodnot a můžeme tedy určit komplexní kořeny i při reálné počáteční aproximaci. je komplexním kořenem polynomu
Pokud ̅
je také kořenem polynomu a
( ) s reálnými koeficienty, pak
( )
je dělitelem
polynomu ( ). Po určení
postup opakujeme a místo
následující aproximaci
použijeme
a tak určíme
. Pokračujeme tak dlouho, dokud nedostaneme uspokojivou
aproximaci kořene.
10
3.1 Algoritmus Müllerovy metody Vstup: , seřazeny od největšího,
( )
( )
( )
( )
maximální počet iterací,
For
( )
√ If |
|
|
|
else
(
If | |
)
a pak algoritmus končí
Příprava pro další iteraci
11
požadovaná přesnost
Příklad 3.1: Pomocí Müllerovy metody určete kořeny rovnice
.
Řešení: V tabulkách jsou uvedeny jednotlivé aproximace a funkční hodnoty v těchto bodech. Výpočet jsme zastavili podmínkou | | ( )
Z hodnot
v tabulkách
( )
vidíme,
že
( )
,
12
a
4 Laguerrova metoda Laguerrova metoda byla pojmenována po francouzském matematikovi Edmondu Laguerrovi. Hlavní výhodou Laguerrovy metody je to, že je vhodná pro jakékoliv typy kořenů: reálné, komplexní, jednoduché i násobné. Zvlášť vhodná je pro výpočet jednoduchých a reálných kořenů, u nichž je zaručena velmi rychlá konvergence k některému kořenu a to při jakékoliv počáteční aproximaci. Pro polynomy s komplexními kořeny toho o konvergenci není příliš mnoho známo, ale případy
kdy metoda není
konvergentní jsou velmi neobvyklé. V případě určování násobných kořenů se konvergence zpomalí v okolí násobného kořene. Předpokládáme, že
jsou dva kořeny daného polynomu. Zkonstruujeme parabolu,
a
která prochází bodem počáteční aproximace intervalu 〈
a jejíž kořeny leží v blízkosti krajních bodů
〉 Další aproximací pak bude ten kořen paraboly, který leží podstatně
blíže krajnímu bodu intervalu než původní aproximace Předpokládáme, že
( )
jsou kořeny rovnice
. Potom každý polynom může být
zapsán ve tvaru ( )
(
)(
)
(
)(
(
)
(4.1)
a ( )
(
)
(
)
)
(
( )(
) )
Obě strany rovnice (4.1) zlogaritmujeme a dostaneme | ( )|
|
|
|
|
|
|
Označíme | ( )|
( ) ( )
| ( )| (
)
(
)
13
(
)
(
( ) ) ( )
( ) ( )
Předpokládáme, že kořen
leží ve vzdálenosti
že ostatní kořeny leží ve vzdálenosti
od současné aproximace , . Potom můžeme
,
a a
vyjádřit ve tvaru
Vyřešíme-li tuto soustavu dostaneme
√(
)(
( ) ( ( )
)
( ) ( ) ) ( ( ))
√
Znaménko před odmocninou vybíráme tak, aby absolutní hodnota jmenovatele byla co největší. Následující aproximaci kořene vypočteme podle vzorce
Jelikož hodnota pod odmocninou může být záporná, kořen
může být komplexní číslo a tedy
může být komplexní i přestože předchozí odhad kořene
byl reálný. Pro
polynomy s komplexními kořeny metoda nemusí být konvergentní při jakékoliv počáteční aproximaci, jako tomu bylo u reálných kořenů, ale ze zkušeností víme, že případy kdy metoda není konvergentní, se vyskytují jen zřídka. Laguerrova metoda může využívat komplexní aritmetiku i při konvergenci k reálným kořenům. Počáteční aproximaci
si zvolíme libovolně. Postup opakujeme tak dlouho, dokud
neobdržíme dostatečně malou hodnotu . Jestliže jsou kořeny rovnice seřazeny tak, že
a
pak proces konverguje k jednomu z kořenů
. Pokud
pokud
pak konverguje k
(
), pro pak konverguje k
, ,
.
Hodnotu polynomu a jeho derivací v daném bodě vypočítáme pomocí Hornerova algoritmu, postup výpočtu je uveden například v [6]. 14
4.1 Algoritmus Laguerrovy metody Vstup:
For
For
√(
)(
)
Výstup:
Pokud |
Označili jsme
|
pak algoritmus končí
( )
( )
( )
15
Příklad 4.1: Pomocí Laguerrovy metody řešte rovnici
.
Řešení: V tabulce jsou uvedeny jednotlivé aproximace a funkční hodnoty v těchto bodech. Výpočet zastavíme podmínkou | |
.
( )
( )
Z hodnot v tabulce vidíme, že
,
16
( )
a
5 Bairstowova metoda Bairstowova metoda se poprvé objevila roku 1920 v knize Leonarda Bairstowa „Applied Aerodynamics“. Pokud reálný polynom má komplexně sdružené kořeny, běžnými metodami je nemůžeme určit, aniž bychom využívali komplexní aritmetiku. Bairstowova metoda nám umožňuje se komplexní aritmetice vyhnout. Tato metoda se snaží převést řešení algebraické rovnice na řešení rovnice kvadratické, a to tak, že najde kvadratický trojčlen, který je dělitelem daného polynomu. Bairstowova metoda konverguje poměrně rychle, ale je potřeba znát dobrou počáteční aproximaci. Předpokládáme reálný polynom -tého stupně, ( ) Polynom
vydělíme libovolným kvadratickým trojčlenem ( ) ( )
(5.1)
Kořeny rovnice (5.1) jsou i kořeny polynomu beze zbytku. Po vydělení polynomu
právě tehdy když
dostaneme polynom
( ) dělí polynom
stupně
( ) Polynom
nyní můžeme obecně zapsat ve tvaru ( )
kde
( ) je zbytek a
( )
( ) ( )
( )
, koeficienty zbytku závisí na parametrech
znamená (
)a
17
(
)
(5.2) , což
Zbytek bude nulový, pokud oba koeficienty (
)
budou nulové a tedy bude platit soustava
a (
,
)
Tuto soustavu nelineárních rovnic budeme řešit Newtonovou metodou. Předpokládáme-li, že kvadratický trojčlen
( )
bude další aproximace
( )
je aproximací dělitele, pak řešením soustavy , kde
( ) (
a
( (
(
.
) ) )
)
Označíme
a soustavu přepíšeme do tvaru (
)
(
)
(
) (5.3)
(
Čísla (
)a (
)
(
)
(
)
) získáme pomocí zobecněného Hornerova schématu.
Derivujeme rovnici (5.2) parciálně podle ( )
( )
( )
( ) ( )
( )
( ) ( )
Soustavu přepíšeme do tvaru ( )
( ) ( )
(5.4)
( )
( ) ( )
(5.5)
18
jsou koeficienty lineárních zbytků při dělení polynomu
Koeficienty trojčlenem
( ). Koeficienty
polynomu
( ) trojčlenem ( ).
Označíme
jsou koeficienty lineárních zbytků při dělení
a dopočítáme koeficienty
a
( )
a
.
Rovnici (5.5) upravíme tak, že ji vynásobíme činitelem ( )
( ) ( )
Po další úpravě dostaneme ( )
( ) ( )
(
)
( ) ( ) ( )
( )(
( ) ( ))
(
)
(
Porovnáme rovnice (5.4) a (5.6) a dostaneme
)
(5.6)
a
Vypočtené koeficienty dosadíme do původního vztahu (5.3) a získáme soustavu (
)
Vyřešením této soustavy získáme kvadratický dělitel
(
)
(
),
jehož kořeny jsou i aproximací kořenů polynomu . Bairstowova metoda bude konvergovat ke kořenům polynomu, pokud počáteční aproximace koeficientů určíme dostatečně blízko skutečným hodnotám koeficientů.
19
Zobecněné Hornerovo schéma Pro výpočet koeficientů zbytků použijeme zobecněný Hornerův algoritmus. Postup výpočtu je uveden například v [6]. … … … … … … …
20
5.1 Algoritmus Bairstowovy metody Vstup: (
)
For
For
Výstup:
Dále pokračujeme tak, že stanovíme
a
.
Proces opakujeme tak dlouho, dokud nedosáhneme předem stanovené podmínky, např. (| | | |)
21
Příklad 5.1:
Užitím Bairstowovy metody nalezněte komplexní kořeny polynomu
( )
Řešení: Jako počáteční aproximační trojčlen zvolíme
( )
jsou uvedeny v tabulce. Výpočet zastavíme podmínkou
Z hodnot v tabulce určíme opravený kvadratický trojčlen ( ) Kořeny tohoto trojčlenu jsou
22
. Koeficienty trojčlenu (| | | |)
6 Příklady Příklad 1: Pomocí uvedených metod najděte všechny kořeny polynomu ( )
Řešení: Do příkazového okna Fortranu zadáme koeficienty polynomu data a/1.0,0.0,2.0,-1.0,-3.0/ a) Nejdříve kořeny polynomu určíme pomocí Müllerovy metody. Do příkazového okna zadáme počáteční aproximace data x/-2.0,-1.0,-0.5/ a po spuštění dostaneme Roots of polynomial x^4+2x^2-x-3 Real
Complex
#iter
( -0.87605315 , 0.00000000 )
6
Spočítáme i druhý reálný kořen polynomu data x/0.0,1.0,2.0/ Roots of polynomial x^4+2x^2-x-3 Real (
1.1241230
Complex ,
0.0000000
#iter )
5
23
Našli jsme dva reálné kořeny polynomu
. Polynom
vydělíme kvadratickým trojčlenem ( ) příslušným kořenům
a získáme tak polynom
( )
. Kořeny tohoto polynomu jsou
.
b) Dále kořeny odhadneme pomocí Laguerrovy metody. x0=0 Roots of polynomial x^4+2x^2-x-3 Real
Complex
#iter
( -0.87605315 , 0.00000000 )
3
X0=2 Roots of polynomial x^4+2x^2-x-3 Real (
Complex
1.1241233
,
#iter
0.0000000
)
2
Laguerrovou metodou jsme určili dva reálné kořeny . Opět vydělíme příslušným kvadratickým trojčlenem a dostaneme polynom , jehož kořeny jsou c) Nakonec kořeny vypočítáme ještě Bairstowovou metodou. Jako počáteční aproximační trojčlen vezmeme ( )
.
p=1 q=1 Roots of polynomial x^4+2x^2-x-3 Root x1 ( 1.1241230 , 0.00000000 )
Root x2
#iter
(-0.87605304 , 0.0000000)
Vypočítali jsme kořeny
4
. Polynom opět vydělíme již
získanými kořeny a určíme komplexně sdružené kořeny
24
Příklad 2: Určete všechny kořeny polynomu ( )
Řešení: a) Müllerova metoda Počáteční aproximace
Kořeny polynomu
#iterací
Zbývá nám určit poslední kořeny kvadratické rovnice vzniklé po vydělení původního polynomu již určenými kořeny
.
b) Laguerrova metoda Počáteční aproximace Kořeny polynomu
#iterací
Z kvadratické rovnice dopočítáme poslední dvojici komplexních kořenů
c) Bairstowova metoda Koeficienty aproximačního trojčlenu Kořeny polynomu
#iterací
Bairstowovou metodou jsme určili první dvě komplexně sdružené dvojice kořenů. Zbývá z lineární rovnice dopočítat poslední kořen
. 25
Příklad 3: V intervalu 〈
〉 určete reálný kořen polynomu ( ) s přesností ( )
Řešení: a) Nejdříve k výpočtu použijeme Müllerovu metodu. Za počáteční aproximace vezmeme ,
,
. Výsledek
jsme obdrželi po pěti iteracích.
b) Následně kořen odhadneme pomocí Laguerrovy metody. Za počáteční aproximaci vezmeme krajní bod uvedeného intervalu
. Po třech iteracích získáme výsledek
. c) Nakonec použijeme ještě Bairstowovu metodu. Jako počáteční aproximační trojčlen vezmeme ( )
. Bairstowovou metodou dostaneme hledaný kořen
po 8 iteracích. Nejrychlejší metodou v tomto případě byla Laguerrova metoda, ale bylo potřeba určit dobrou počáteční aproximaci. Pokud bychom zvolili například komplexní kořeny
vypočítali bychom
, což není námi hledané řešení.
Stejně tak u metody Müllerovy jsme museli zvolit vhodné aproximace. Jako nejlepší metoda se zdá v tomto případě metoda Bairstowova, která nám kořen určila bez ohledu na zvolené počáteční koeficienty. Pokud bychom za počáteční aproximační trojčlen vzali ( )
získáme stejný výsledek.
26
Příklad 4: Určete reálné i komplexní kořeny polynomu ( )
Řešení: a) Müllerova metoda Počáteční aproximace
Kořeny polynomu
#iterací
b) Laguerrova metoda Počáteční aproximace Kořeny polynomu
#iterací
27
c) Bairstowova metoda Koeficienty aproximačního trojčlenu Kořeny polynomu
#iterací
Z tabulek vidíme, že rozdíly mezi řešeními podle různých metod jsou zanedbatelné, takže příliš nezáleží na tom, jakou metodu k vyřešení příkladu použijeme. Nejrychleji konverguje Laguerrova metoda, výsledek jsme získali již po dvou iteracích.
28
Příklad 5: Určete reálné kořeny polynomu ( )
Řešení: Z grafu funkce vidíme, že polynom má pouze 2 reálné kořeny. a) Müllerova metoda Počáteční aproximace
Kořeny polynomu
#iterací Hodnota ( )
,0
b) Laguerrova metoda Počáteční aproximace Kořeny polynomu
#iterací Hodnota ( )
29
c) Bairstowova metoda Koeficienty aproximačního trojčlenu
Kořeny polynomu
#iterací
Hodnota ( )
Pro hledání pouze reálných kořenů se zdá nejvhodnější metoda Laguerrova, která byla nejrychlejší a nejpřesnější z uvedených metod, a zároveň nebylo potřeba přemýšlet nad zvolením počáteční aproximace. Pokud bychom vzali za počáteční aproximaci pro
bychom získali stejný výsledek již po 7 iteracích. Bairstowova metoda pro
tento příklad nebyla příliš vhodná, jelikož při stanovení koeficientů
nebo
nám našla pouze komplexní kořeny. Nás však zajímala pouze reálná řešení rovnice.
30
Příklad 6: Najděte reálné i komplexní kořeny polynomu ( )
a) Müllerova metoda Počáteční aproximace
Kořeny polynomu
#iterací
Müllerovou metodou jsme příliš přesné výsledky nezískali a navíc při výpočtu překročili povolený počet iterací
jsme
. U tohoto příkladu je lepší pro výpočet zvolit jinou
metodu.
b) Laguerrova metoda Počáteční aproximace Kořeny polynomu
#iterací
0 0
Laguerrovou metodou jsme získali přesnější výsledky. Zvolíme-li pro počáteční aproximaci
o něco lepší
získáme pro daný kořen zcela přesný výsledek.
31
c) Bairstowova metoda Počáteční koeficienty trojčlenu Kořeny polynomu
Pomocí Bairstowovy metody jsme našli přesné kořeny rovnice.
32
#iterací
Příklad 7: Určete všechny kořeny polynomu ( )
.
Tento polynom má pouze reálné kořeny a to z grafu vidíme, že v okolí hodnoty
a dvojnásobný kořen . I
se pravděpodobně bude nacházet násobný kořen.
Řešení: a) Müllerova metoda Počáteční aproximace
Kořeny polynomu
#iterací
,0
Při určování kořenu komplexní část
jsme překročili povolený počet iterací
a daný kořen měl i
, tu jsme ale vzhledem k tomu, že zaokrouhlujeme na
sedm desetinných míst, v tabulce neuvedli. Násobný kořen můžeme také určit tak, že zadáme a získáme
. Poté bychom určili násobnost
kořene tak, že spočítáme -té derivace polynomu v bodě ( )
,
( )
a kořen je dvojnásobný.
je násobnost kořene. V našem případě
33
(viz kapitola 1.1). Pokud
( )
ale
( )
, tedy
b) Laguerrova metoda Počáteční aproximace Kořeny polynomu
#iterací
Konvergence Laguerrovy metody se v okolí násobného kořene velmi zpomalí. Vezmeme-li vypočítáme kořen
po
iteracích. Pokud
a počet iterací bude . c) Bairstowova metoda Počáteční koeficienty trojčlenu Kořeny polynomu
#iterací
Bairstowova metoda nám poskytla poměrně přesné řešení, i přesto si ale myslím, že je vhodnější pro násobné kořeny použít některou z ostatních metod.
34
7 Problémy při hledání kořenů polynomů Přestože metody uvedené v této práci jsou ve většině případů konvergentní, může při hledání kořenů polynomů nastat několik problému. Mezi hlavní problémy patří nedostatečná počáteční aproximace. Neznáme-li dobrou počáteční aproximaci, metoda může konvergovat ke špatnému kořeni nebo nemusí k hledanému řešení konvergovat vůbec. Tomuto problému se dá snadno vyhnout, pokud sestrojíme graf funkce nebo použijeme jinou startovací metodu. Další problém může nastat, pokud kořeny polynomu leží příliš blízko. Může být těžké určit, zda se v problémovém místě nachází jeden kořen, dva kořeny nebo dvojnásobný kořen. I tento problém můžeme snadno vyřešit tak, že si vykreslíme graf funkce a v problémovém místě jej zvětšíme. Násobné kořeny, pokud o nich víme, mohou být řešeny například Laguerrovou metodou. Jestliže ale nevíme, zda má polynom vůbec nějaké násobné kořeny, může se efektivnost uvedených metod zhoršit. Sestrojení grafu funkce nám může pomoci zjistit, zda je existence násobných kořenů možná. Největším problémem je špatná podmíněnost polynomu, která se většinou vyskytuje u polynomů vyššího stupně. Špatně podmíněný polynom je takový polynom, u kterého i malé změny v koeficientech způsobí větší změny v jeho kořenech. Většina polynomů v této práci se chovala dobře, ale vždy musíme počítat s tím, že se mohou objevit nečekané problémy a řešení rovnice se tím ztíží.
35
Závěr Cílem této práce bylo nastudovat metody vhodné pro řešení algebraických rovnic. Práce byla rozdělena na část teoretickou a praktickou. V první části jsem se seznámila s tím, jak postupovat při řešení dané problematiky a ve druhé části jsem se naučila jak vyřešit konkrétní příklady pomocí programu vytvořeného v programovacím jazyce Fortran 77. Startovací metody slouží k hrubému odhadu řešení algebraické rovnice, ale samy o sobě nám příliš dobrou aproximaci kořene neposkytnou. V této práci jsme dále uvedli tři metody, které jsou vhodné zvláště pro výpočet kořenů polynomů. Všechny metody vyžadovaly určení počáteční aproximace a poté vygenerovaly posloupnost, která konvergovala ke hledanému řešení rovnice. Pokud jsme již jeden či více kořenů polynomu určili, dále jsme pokračovali tak, že jsme polynom vydělili již určenými kořeny a pokračovali jsme v hledání kořenů redukovaného polynomu. Všechny zde uvedené metody jsou vhodné pro řešení algebraických rovnic jak s reálnými kořeny, tak s komplexními. Z příkladů vidíme, že nejrychleji konvergovala metoda Laguerrova. Počet iterací ale u žádné metody nebyl příliš vysoký a při výpočtu na počítači nehraje příliš velkou roli. Výhodou Bairstowovy metody je zase to, že nám spočítá hned dva kořeny daného polynomu najednou. Všechny metody většinou konvergovaly k velmi podobným výsledkům, rozdíl byl jen minimální, takže nejde jednoznačně určit, která z metod je pro výpočty nejlepší. K této práci je přiloženo CD s programy uvedených metod.
36
Seznam příloh Příloha A CD s programy metod pro určování kořenů polynomů
37
Literatura [1]
Burden, R. L., Faires, J. D., Numerical Analysis, 9th edition, Boston: Brooks Cole, 2010.
[2]
Hamming, R., W., Numerical methods for scientists and engineers, 2nd edition, Mineola : Dover Publications, 1986.
[3]
Horová, I., Zelinka, J., Numerické metody, 2. vydání, Brno: Masarykova univerzita, 2004.
[4]
Hřebíček, J., Programovací jazyk FORTRAN 77 a vědeckotechnické výpočty, Praha: Academia, 1989.
[5]
Kincaid, D, Numerical Analysis: Mathematics of Scientific Computing, 3rd edition, American Mathematical Society, 2002.
[6]
Μíka, S., Numerické metody algebry, 2. vydání, Praha: SNTL, 1985.
[7]
Nekvida, M, Šrubař, J, Vild, J, Úvod do numerické matematiky, Praha: SNTL, 1976.
[8]
Press, W. H., Numerical recipes in Fortran 77: The art of scientific computing, 2nd edition, Cambridge: Cambridge University Press, 1992.
[9]
Stoer, J., Bulirsch, R. Introduction to numerical analysis, 2nd edition, New York: Springer – Verlag, 1993.
[10] Vitásek, E., Numerické metody, Praha: SNTL, 1987.
38
