Numerické metody 7. přednáška, 6. dubna 2016
Jiří Zelinka
Jiří Zelinka        Numerické metody 7. přednáška, 6. dubna 2016
Opakování
Polynomy
P(x) = anxn + 3n-xxn~x... + aix + a0. £i>£2> •••>£#? kořeny (reálné i komplexní) polynomu P.
• dělení polynomů se zbytkem
• Hornerovo schéma
• zobecněné Hornerovo schéma
• hranice kořenů
• počet reálných kořenů polynomu na intervalu - Sturmova věta
Jiří Zelinka        Numerické metody 7. přednáška, 6. dubna 2016 2/19
Newtonova metoda a její modifikace
Problém - volba počáteční aproximace Věta
Nechť P G n„ je polynom stupně n > 2. Nechť všechny kořeny
jsou reálné. Pak posloupnost {x/c}^0 určená Newtonovou metodou je konvergentní klesající posloupnost pro každou počáteční aproximaci x0 > (i a platí lim     = £1.
k^oc
Jiří Zelinka        Numerické metody 7. přednáška, 6. dubna 2016 3/19
Príklad
P(x)  = (x-l)(x-2)(x-3)(x-4)(x-5)(x-6)
= x6 - 21x5 + 175x4 - 735x3 + 1624x2 - 1764x + 720
161 < 1765
*0	= 1765
Xl	= 1226.8
X2	= 1022.9
*3	= 859.99
X4	= 711.41
xio = 287.99 x20  = 49.48
Jiří Zelinka        Numerické metody 7. přednáška, 6. dubna 2016 4/19
Zdvojená Newtonova metoda
Pro velké x^.
xk+1 =
xk-
{xky +...
n(xfc)n-l + . . .
1  - ~
Věta
Nechť P e Un, n > 2, a nechť všechny kořeny £/, / = 1,..., n polynomu P jsou reálné a £i > £2 > • • • > £#?■ Nechť «i je největší kořen P'\
£1 > «1 > 6-
Pro /? = 2 předpokládejme £1 > £2. Pak pro každé z > £1 jsou čísla
z = z —
P (z)' definována a platí
y = y
P(y)
«i < y,
6 < / <
5     ^) c\ o
Jiří Zelinka        Numerické metody 7. prednáška, 6. dubna 2016 5/19
Algoritmus
Začneme s počáteční aproximací x0 > d a zdvojenou metodou:
Xk+i = *k - 2—
Mohou nastat dva případy: O P(xo)P(xk) > 0 pro všechna k. Pak
x0 > xi > ... > xk > ... > £1,
A- = 0,1,...
lim xk =
k^oc
O Existuje xk tak, že P{xk)P(x0) < 0, P(xk_1)P(x0) > 0. V tomto případě tedy došlo k „přestřelení" bodu £i a platí
x0 > xi > ... > xk_i >    > xk > ai > ^2-
Položme yo = xk a pokračujme dále klasickou Newtonovou metodou s touto počáteční aproximací:
P(Yk)
Yk+i = Yk
P'iYk)
k = 0,1,2,...
□      g ► < i i
Jiří Zelinka        Numerické metody 7. prednáška, 6. dubna 2016
6/19
Snižování stupně
Pí (x) = - numerické nepřesnosti v koeficientech. Příklad
P - polynom s kořeny ^ = 10, ..., £10 = 1 Aproximace kořenů:
|i  = 10.000000040624446 |2  = 8.999999654991576 |3  = 8.000001300611824
|7  = 4.000018865503898
|io  = 0.99999962963847448
Jiří Zelinka        Numerické metody 7. přednáška, 6. dubna 2016 7/19
Maehlyova metoda
P(x)
P'(x) P(x)
*-6     ^     *-6 (*-6)2
Dosazením tohoto vyjádření do vzorce pro Newtonovu metodu pro polynom P\ dostaneme:
k+i =xk_
Pi(xk) P[(xk)
xk-
P{xk)
P'(xk) -
P{xk)
xk - 6
Jiří Zelinka
Numerické metody 7. přednáška, 6. dubna 2016 8/19
SNS /N/
Obecně, jestliže jsme již nalezli aproximace kořenů £1,..., £/, postupujeme obdobně a sestrojíme polynom
Pj(x) =
P(x)
{x-i1)...{x-ijy
P'{x)
P(x)
J 1
E —
(x - 6)... (x - 0)    (x - 6)... (x - 0) tí x ~ &
Newtonova metoda pro nalezení kořene      je tvaru
x
= <t>Axl    H*) = x -
P(x)
P'(x) - > —
^ X - f-i=l X
Jiří Zelinka        Numerické metody 7. přednáška, 6. dubna 2016 9/19
Normy vektoru a matic
Vektory - prvky R" nebo C", sloupcové.
Normy vektorů
Vektorová norma na C" je funkce s následujícími vlastnostmi:
O llxll > 0,   Vx e C
(z C do R)
O O
o
x||=0<^>x = o,   o = (0, ...,0)T ojx|| = |a| ||x||,   VaGC,   Vx G C x + y < x|+|y|, Vx,yeC".
Príklady vektorových norem:
O x
Q \\x O \\x
oo
O x
n
1
2
E I*
J=l n
E kí
#=1
= max
1<# <A7
X;
(eukleidovská norma)
(oktaedrická norma) (krychlová norma)
i
n \ p
P
E |x/
7=1
(p norma)
Každá vektorová norma indukuje metriku danou vztahem
p(*,y) = II* - y
Konvergence v normě: x„ —>► x <^>
Xn -X
>0
Jiří Zelinka        Numerické metody 7. přednáška, 6. dubna 2016   11 / 19
Matice
Nechť A je čtvercová matice řádu n s reálnými resp. komplexními prvky:
A =
í 3n 321
3\
32 n
Á4n: třída všech matic tohoto typu.
Matici A lze považovat za vektor dimenze n2. Mohli bychom tedy definovat normu matice jako normu vektoru. Ale potřebujeme i další vlastnosti:
Jirí Zelinka
Numerické metody 7. přednáška, 6. dubna 2016   12 / 19
Vlastní čísla a vlastní vektory
A • x = Ax
x - vlastní vektor matice AA, A - příslušné vlastní číslo
Vlastní čísla jsou kořeny charakteristického polynomu ?/V\(A) = det(A • E — A), E - jednotková matice
Spektrální poloměr matice: p(Ä) = max{|A^|; A^ je vlastní číslo matice A}
n
Stopa matice: tr(A) = ^
k=i
Jirí Zelinka
Numerické metody 7. přednáška, 6. dubna 2016   13 / 19
Normy matic
Maticová norma na množině Mn je reálná funkce s těmito vlastnostmi:
O
o o o o
A\\ > 0,   V/A G Mn
A\ = 0 ^ A je nulová matice
aA
a
A ,   VaeC,   M A <G Mn
A + B < A + B
AB\\<\A B
A, B e Mn A, B e Mn
Vlastnost 5) se nazývá multiplikativnost.
Jiří Zelinka
Numerické metody 7. přednáška, 6. dubna 2016   14 / 19
Souhlasnost maticové a vektorové normy
Řekneme, že maticová norma
je souhlasná s danou
vektorovou normou
, jestliže
/A
x
Vx e C",   V/A e M,-
Pridružená norma
Nechť
je vektorová norma na O1. Pak číslo
A
= max
11X11^=1
Ax
je maticová norma souhlasná s danou vektorovou normou
Pro jednotkovou matici E platí
= max
11X11^=1
Ex ,„ = 1
a pro souhlasnou maticovou normu platí ||E|| > 1.
Jiří Zelinka        Numerické metody 7. prednáška, 6. dubna 2016   15 / 19
Veta
Přidružená maticová norma je nejvýše rovna libovolné maticové normě souhlasné s danou vektorovou normou
Veta
Nechť maticová norma
normou
je souhlasná s danou vektorovou . Pak pro všechna vlastní čísla A matice A platí:
A < A
Jiří Zelinka
Numerické metody 7. přednáška, 6. dubna 2016   16 / 19
Pridružené maticové normy
Nechť A G A4n. Přidružené maticové normy k vektorovým
normám
OOi
2 jsou dány vztahy
n
A i = max V] la/;
l<7<",tl
n
Q \\AWqo = max ^ \3ij
e \\a
2 = y/p(a*a), p{a*a) je spektrální poloměr /AM, kde a* = /AT, pro reálné matice je a* = at. >A 2 _ spektrálni norma matice
□ e
Frobeniova norma
Veta
Nechť ||6|| < 1, || • || je souhlasná s danou vektorovou normou. Pak matice E — B je regulární a platí
(E-B)
-i
<
	E	
1 -		B
Jiří Zelinka        Numerické metody 7. přednáška, 6. dubna 2016   19 / 19