Opakování
Polynomy
P(x) = anxn + an_ixn_1... + aix + a0. 6)^2, •••,£/» kořeny (reálné i komplexní) polynomu P.
• dělení polynomů se zbytkem
• Hornerovo schéma
a 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, 1. dubna 2015 2/19
Newtonova metoda a její modifikace
Problém - volba počáteční aproximace Věta
Nechť P E nn je polynom stupně n > 2. Nechť všechny kořeny
jsou reálné. Pak posloupnost {xk}^=0 určená Newtonovou metodou je konvergentní klesající posloupnost pro každou počáteční aproximaci x0 > £1 a platí lim xk = £i-
Jiří Zelinka        Numerické metody 7. přednáška, 1. dubna 2015 3/19
Příklad
P(x)   =  (x - l)(x - 2)(x - 3)(x - 4)(x - 5)(x - 6)
=  x6 - 21x5 + 175x4 - 735x3 + 1624x2 - 1764x + 720
|£; | < 1765
xo =	1765
*L =	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, 1. dubna 2015 4/19
Zdvojená Newtonova metoda
Pro velké x^.
k+i__k        (x*)" + ■ ■ ■    ^ „k {■, 1
X        = X
n(xk)n
-i
Veta
Nechť P e nn, n > 2, a nechť všechny kořeny    /' = 1,..., n polynomu P jsou reálné a £i > £2 > • • • > £n- Nechť «1 je největší kořen P'\
£1 > ai > &■
Pro n = 2 předpokládejme £1 > £2- Pak pro každé z > £1 jsou čísla
P'(zY      y P(z)'      r    r P'{y)
definována a platí
"i < y, íi<y<z.
Algoritmus
Začneme s počáteční aproximací x0 > £1 a zdvojenou metodou:
*k+l = *k
Mohou nastat dva případy: O P(x0)P(xk) > 0 pro všechna k. Pak
x0 > xi > ... > xk > ... > £1,
k = 0,1,...
lim Xk
k^řOO
6
O Existuje xk tak, že P(xk)P(x0) < 0, P(xk-i)P(x0) > 0. V tomto případě tedy došlo k „přestřelení" bodu £i a platí
x0 > xi > ... > xk i > £i > xk > ai > 5.
Položme yo = xk a pokračujme dále klasickou Newtonovou metodou s touto počáteční aproximací:
yk+i = yk
P'W
0,1,2,...
1 -00,0
Jiří Zelinka        Numerické metody 7. přednáška, 1. dubna 2015 6/19
Snižování stupně
Pi(x) = -^f- - numerické nepřesnosti v koeficientech. Příklad
P - polynom s kořeny £1 = 10, ..., £10 = 1 Aproximace kořenů:
£1  = 10.000000040624446 |2  = 8.999999654991576 |3  = 8.000001300611824
|7  = 4.000018865503898
£10  = 0.99999962963847448
<n>4ď> ■= -O^O-
Jin Zelinka        Numerické metody 7. přednáška, 1. dubna 2015 7/19
Maehlyova metoda
(x-íi)2
Dosazením tohoto vyjádření do vzorce pro Newtonovu metodu pro polynom P\ dostaneme:
X       = x   —___, , = X
xk
Jiří Zelinka        Numerické metody 7. přednáška, 1. dubna 2015 8/19
Obecně, jestliže jsme již nalezli aproximace kořenů £1,..., £y, postupujeme obdobně a sestrojíme polynom
PM P{X)
(x-a)...(x-0)
P'(x) P(x) £ _1_
(x-6)...(x-0)   (x-6)...(x-0) £í*-6
Newtonova metoda pro nalezení kořene      je tvaru
Xfc+1 = <S>j{xk), <Dy(x) = X
x - e-
Jiří Zelinka        Numerické metody 7. přednáška, 1. dubna 2015 9/19
Normy vektoru a matic
Vektory - prvky M." nebo C", sloupcové. Normy vektorů
Vektorová norma na C" je funkce || • || (z C" do IR) s následujícími vlastnostmi:
O ||x|| > 0,   Vx G C"
Q \\x\\ = 0 ^ x = o,   o = (0,...,0)T
O ||ax|| = \a\ \\x\\,   VaGC,   Vx G C"
O ||x+ y|| < ||x|| + ||y||, Vx,yGC".
Jiří Zelinka        Numerické metody 7. přednáška, 1. dubna 2015   10 / 19
Príklady vektorových norem:
O ||x||2 = (     lx''|2 ) (eukleidovská norma)
i=l
O ||x||i = ^2 \xi\       (oktaedrická norma)
i=l
Q ||x||oo = max |x,-|       (krychlová norma)
K; <n
i
n \ p
O ||x||p =       \xi\P (P norma)
i=l
Každá vektorová norma indukuje metriku danou vztahem
p(*,y) = II* -y||-
Konvergence v normě: xn —> x <^ ||x„ — x|| —> 0.
Jiří Zelinka        Numerické metody 7. přednáška, 1. dubna 2015   11 / 19
Matice
Nechť A je čtvercová matice řádu n s reálnými resp. komplexními prvky:
/ 3ll 3\n \
321 Sin
\ a„i
)
Mn: 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:
JiřT Zelinka        Numerické metody 7. přednáška, 1. dubna 2015   12 / 19
Vlastní čísla a vlastní vektory
A - x = Xx
x - vlastní vektor matice AA, X - příslušné vlastní číslo
Vlastní čísla jsou kořeny charakteristického polynomu
■i/u(A) = det(A ■ E — A), E - jednotková matice
Spektrální poloměr matice: p(A) = max{\Xk\; Xk je vlastní číslo matice A}
n
Stopa matice: tr(A) = akk
Jiří Zelinka        Numerické metody 7. přednáška, 1. dubna 2015   13 / 19
Normy matic
Maticová norma na množině M.n je reálná funkce s těmito vlastnostmi:
o \\a\\ > o, y A g Mn
O \\A\\ = 0    A je nulová matice O \\aA\\ = \a\ \\A\\,   VaGC,   W\ e Mn O \\A + fi|| < \\A\\ + ||fi||,   A, B e Mn Q \\AB\\ < \\A\\ \\B\\,   A, B e Mn Vlastnost 5) se nazývá multiplikativnost.
Jiří Zelinka        Numerické metody 7. přednáška, 1. dubna 2015   14 / 19
Souhlasnost maticové a vektorové normy
Řekneme, že maticová norma || • || je souhlasná s danou vektorovou normou II
l^^llip — \\A\\ ll-^llip)
Lp, jestliže
VxeC",   VA eMn.
Pridružená norma
Nechť
je vektorová norma na C". Pak číslo
\A\\íp = max HAxIlp
je maticová norma souhlasná s danou vektorovou normou
Pro jednotkovou matici E platí
\E\\íp = max HExIlp = 1
a pro souhlasnou maticovou normu platí >„^.
• < 1 ►     l -00.0 Numerické metody 7. přednáška, 1. dubna 2015 15/19
Veta
Přidružená maticová norma je nejvýše rovna libovolné maticové normě souhlasné s danou vektorovou normou.
Věta
Nechť maticová norma || • || je souhlasná s danou vektorovou normou || • H^. Pak pro všechna vlastní čísla A matice A platí:
|A| < \\A\\ .
Jiří Zelinka        Numerické metody 7. přednáška, 1. dubna 2015   16 / 19
Pridružené maticové normy
Nechť A E M.n. Přidružené maticové normy k vektorovým normám || • ||i, || • ||oo, || • ||2 jsou dány vztahy
n
O \\A\\i = max Y, \3ij\, 1</<";=1
n
O \\A\loo = max Y, \au\>
1<; <n
O M>4H2 = y/p(A*A), p{A*A) je spektrální poloměr A*A, kde A* = AT, pro reálné matice je A* = AT. \\A\\2 - spektrálni norma matice
JiŕT Zelinka        Numerické metody 7. přednáška, 1. dubna 2015   17 / 19
Frobeniova norma
• \\A\\2F = tr(A*A)
• ||£||F = y/ň.
• ^\\A\\oo < \\A\\2 < V^\\A\\oo
• ||>A||2 < \\A\\F < Vň\\A\\2
• ^||^||i< ||^||2 <>||^||i ■
Jin Zelinka        Numerické metody 7. přednáška, 1. dubna 2015   18 / 19
Veta
Nechť ||61| < 1, || • || je souhlasná s danou vektorovou normou. Pak matice E — B je regulární a platí
Jiří Zelinka        Numerické metody 7. přednáška, 1. dubna 2015   19 / 19