Cvičení z Numerických metod I - 8.týden
Mějme polynom stupně n s reálnými koeficienty ve tvaru
P (x) = a0xn H-----h an-ix + an
s reálnými kořeny £j, i = 1,..., n, přičemž platí
£l > 6 > • • • > £n-
Naším úkolem nyní bude najít všechny kořeny polynomu P (x).
Zdvojená Newtonova metoda
Hledáme nej větší kořen polynomu P{x). Je možné použít klasickou Newtonovu metodu, ale jak víme, konvergence závisí na volbě počáteční aproximace. Dá se ukázat, že posloupnost {xk}'j*L0 určená Newtonovou metodou je konvergentní klesající posloupnost pro každou počáteční aproximaci x° > £1 a £1 = limk^oo xk. Ale tato konvergence nemusí být vždy dostatečně rychlá. Zavedeme proto zdvojenou Newtonovu metodu, která má tvar
Tk+1 _   k _ nP{xk) P'(xk)
Geometrický význam je trochu odlišný od klasické Newtonovy metody. Další člen iterační posloupnosti není průsečíkem tečny a osy x, ale průsečíkem sečny se směrnicí P ^ ^ a osy x. Zdvojená Newtonova metoda konverguje rychleji než klasická Newtonova metoda, ale můžeme kořen £1 „přestřelit", tj. pro některý člen iterační posloupnosti platí xk° < £1. V takovém případě pokračujeme klasickou Newtonovou metodou s počáteční aproximací x° = xk°.
Postup pro nalezení největšího kořene polynomu:
1. Zvolíme počáteční aproximaci x° tak, že x° > ^. Můžeme použít horní hranici kořenů. Tedy x° = 1 +     , kde A = max (| a\ \,..., | an \).
2. Použijeme zdvojenou Newtonovu metodu, ale musíme kontrolovat, zda jsme nepřestřelili.
3. V případě, že P(xk°)P(x°) > 0, pokračujeme zdvojenou Newtonovou metodou, tedy
P'(xk°)
4. V případě, že P(xk°)P(x°) < 0, přestřelili jsme a pokračujeme klasickou Newtonovou metodou, tedy
xk0+l _ xk0 _ °) P'(xko)'
Pozn. jako počáteční aproximace pro klasickou Newtonovu metodu je brána přestřelená aproximace.
Dále pokračujeme už pouze klasickou metodou.
5. Pokračujeme tak dlouho, dokud nedosáhneme požadované přesnosti.
Pozn. Pro výpočet funkčních hodnot polynomu P{x) a derivace polynomu P'{x) je výhodné využít Hornerovo schéma.
1
Příklad Najděte největší kořen polynomu P(x) = x4 — 5x2 + 4. Spočítáme hranice kořenů:
A = max{0,5,0,4} = 5
B = max{l, 0, 5, 0} = 5
TT| <l6l<l + f
|<J6c|<6
Spočítáme derivaci polynomu: P'(x) = Ax3 — lOx. Zdvojená Newtonova metoda má tvar :
xk+i = xk_ o(^)4-5(xfc)2 + 4 A(xk)3 - 10xk
x°
P(x1)P(x°) > 0 =^ pokračujeme zdvojenou metodou x2 = 2.0406 P(x2)P(x°) > 0 =^ pokračujeme zdvojenou metodou
x3 = 1.9642 P(x3)P(x°) < 0 =^ pokračujeme klasickou metodou
1.96424 - 5 • 1.96422 + 4 4- 1.96423 - 10- 1.9642
x4 = 1.9642 - -" -— = 2.0022
x5 = 2.0000
Newtonova-Maehlyova metoda
Po aproximaci £i největšího kořene £i polynomu P budeme hledat další kořeny. Mohli bychom využít metodu snižování stupně a zdvojenou Newtonovu metodu aplikovat na polynom
Pi(x)        1 '
Takto bychom mohli postupně najít všechny kořeny polynomu. V průběhu však dochází k zaokrouh-lovacím chybám. Největší kořen neznáme přesně a ani polynom P\(x) nebude znám přesně, budeme tedy hledat aproximaci kořene přibližného polynomu. Tyto chyby by se postupně kumulovaly. Řešením je spočítat derivaci polynomu P\ jako
x - £i     (x- £i)2 Newtonova metoda pro polynom Px má tedy tvar
xk+l = xk
P(xk)
Stejným způsobem můžeme najít i další kořeny. Předpokládejme, že jsme už aproximovali £].,...£} a hledáme        Newton-Maehlyova metoda má tvar
xk+l = xk P(X )
•\j P(xk)
Ji = l xk_^.
Samozřejmě můžeme použít i zdvojenou verzi, ale musíme si dát pozor, abychom nepřestřelili.
2
Příklad Najděte všechny kořeny polynomu P(x) = x3 + 3x2 - 1. Spočítáme hranice kořenů:
A = max{3,0,1} = 3
B = max{l, 3, 0} = 3
TÍr<|^l<l + f
i<l6l<4
Spočítáme derivaci polynomu: P'(x) = 3x2 + 6x.
Pozn. Pro lepší informaci o kořenech, bychom pomocí Sturmovy věty mohli určit intervaly, v kterých jednotlivé kořeny leží. li:
x° = A
P(x°)
x1 = x° — 2—-—- = 0.9167 P(x1)P(x ) > 0 =>• pokračujeme zdvojenou metodou
P'(x°)
x2 = x1__-—- = 0.3454 P(x2)P(x ) < 0 =>- pokračujeme klasickou metodou
P^x1)
x3 = 0.5927
x4 = 0.5328
z5 = 0.5321
6 = x° = 0.5
P(r°)
x1 = x° - 2--—-—7T- = -1.2351 P(xL)P(x°) < 0 =>■ pokračujeme klasickou metodou
x°-£i
•2 - P<^-- -0.3332
a;3 = -0.6171 XA = -0.6522 a:5 = -0.6527
6:
x° = -0.7
x
xu-2-
P'(x°)
P(x°) _ P(x°) x° — §1       a:0—§2
. 1 -P
X   = X
—i—l-— = —5.0744    P(x1)P(x ) < 0 =>• pokračujeme klasickou metodou
P(xl)
2 _ „i ^ lJ J-_ _2.8794
= -2.8794 x4 = -2.8794 x5 = -2.8794
X1-^!        x1-(2
3