Numerické metody 7. přednáška, 4. dubna 2017 Jiří Zelinka Jiří Zelinka Numerické metody 7. přednáška, 4. dubna 2017 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, 4. dubna 2017 2/23 Hranice kořenů Veta Nechť P(x) A B anxn + an-ixn 1... + 3Xx + a0, = max(|a„-i|,..., |a0|) = max (\an i • ■ ■ i kde 3o3„ 0. Pak pro všechny kořeny /c = polynomu P platí 0,1,..., n, 1 + B 30 < & < 1 + A Jiří Zelinka Numerické metody 7. přednáška, 4. dubna 2017 3/23 Další kriteria n-l 1. < max St P/+i a konstanty q jsou kladné, ale jinak libovolné. Lze říci, že P/+i je záporně vzatý zbytek při dělení P/_i : P/. Protože stupně polynomů klesají, musí algoritmus končit po m < n krocích. Jiří Zelinka Numerické metody 7. přednáška, 4. dubna 2017 5/23 Počet reálných kořenů polynomu P v intervalu a < x < b je roven W(b) — W(a), kde W(x) je počet znaménkových změn ve Sturmově posloupnosti Pq(x), ..., Pm(x) v bodě x (z níž jsou vyškrtnuty nuly). Konec opakování Jiří Zelinka Numerické metody 7. přednáška, 4. dubna 2017 6/23 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, 4. dubna 2017 7/23 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, 4. dubna 2017 8/23 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 > • • • > Šn- Nechť a\ je největší kořen P'\ €i>oí!> 6- Pro n = 2 předpokládejme £1 > č;2- Pak pro každé z > £1 jsou čísla P(z) nP(z) P(y) z = z — P (z)' definována a platí y =y P(y) «i < y, 6 < / < Jiří Zelinka Numerické metody 7. prednáška, 4. dubna 2017 9/23 Algoritmus Začneme s počáteční aproximací x0 > d a zdvojenou metodou: xk+1 =xk- 2 p,^Xky /c = 0,1,... Mohou nastat dva případy: O P(xo)P(xk) > 0 pro všechna k. Pak x0 > xi > ... > Xk > ... > £i, lim Xk = £i O Existuje xk tak, že P(xk)P(x0) < 0, P(x/c_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 > č;2- Položme yo = Xk a pokračujme dále klasickou Newtonovou metodou s touto počáteční aproximací: y/c+i = y/c - p/, v /c = o, i, 2,... Jiří Zelinka Numerické metody 7. přednáška, 4. dubna 2017 10/23 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, 4. dubna 2017 11 /23 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, 4. dubna 2017 12/23 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 = Axl H*) = x - P(x) P'(x) - > — ^ x - f-i=l X Jiří Zelinka Numerické metody 7. přednáška, 4. dubna 2017 13/23 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 G C (z C do R) O O o x||=0<^>x = o, o = (0, ...,0)T ojx|| = |a| ||x||, Va G C, Vx G C x + y < x|+|y|, Vx,yGC. 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<# ► x <^> Xn -X >0 Jiří Zelinka Numerické metody 7. přednáška, 4. dubna 2017 15/23 Matice Nechť A je čtvercová matice řádu n s reálnými resp. komplexními prvky: A = í 3n 321 3\ 32 n \ 3nl Á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, 4. dubna 2017 16/23 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, 4. dubna 2017 17/23 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 1. Jiří Zelinka Numerické metody 7. prednáška, 4. dubna 2017 19/23 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, 4. dubna 2017 20/23 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, 4. dubna 2017 23/23