Numerické metody 7. prednáška, 5. dubna 2019 Jiří Zelinka Jiří Zelinka Numerické metody 7. přednáška, 5. dubna 2019 1/23 Opakování Polynomy P (x) = anxn + an-ixn 1... + aľx + a0. £i?£2? • • • >£n 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 veta □ Jiří Zelinka Numerické metody 7. přednáška, 5. dubna 2019 2/23 Hranice kořenů Věta Nechť P(x) A B anxn + an_ix" 1... + aix + a0, = max(|a„_i|,..., |a0|) = max(|an • • • ai\), kde aoa„ ^ 0. Pak pro všechny kořeny /c = polynomu P platí 0,1, • • •, n, 1 1 + < & < 1 + A a0 Jiří Zelinka Numerické metody 7. přednáška, 5. dubna 2019 3/23 Další kriteria n-l I- & < < 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, 5. dubna 2019 5/23 Sturmova věta Počet reálných kořenů polynomu P v intervalu a < x < b je roven 1/1/(6) — l/l/(a), kde W(x) je počet znaménkových změn ve Sturmově posloupnosti Po(x)? • • • ? Pm{x) v bodě x (z níž jsou vyškrtnuty nuly). Konec opakování Jiří Zelinka Numerické metody 7. přednáška, 5. dubna 2019 6/23 Newtonova metoda a její modifikace Problém - volba počáteční aproximace Věta Nechť P e Un je polynom stupně n > 2. Nechť všechny kořeny jsou reálné. Pak posloupnost {x^}^ určená Newtonovou metodou je konvergentní klesající posloupnost pro každou počáteční aproximaci xq > £1 a platí lim x^ = £1. Jiří Zelinka Numerické metody 7. přednáška, 5. dubna 2019 7/23 l)(x - 2)(x - 3)(x - 4)(x - 5)(x - 6) 21x5 + 175x4 - 735x3 + 1624x2 - 1764x + 720 161 < 1765 x0 = 1765 Xi = 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, 5. dubna 2019 8/23 Zdvojená Newtonova metoda Pro velké Xk+l = *k {xk)n +... "(x/c)""1 + . . . n Věta Nechť P e nn, n > 2, a nechť všechny kořeny £/, / = 1,..., n polynomu P jsou reálné a £1 > £2 > • • • > 6?- Nechť «1 je největší kořen P;: Pro n = 2 předpokládejme £1 > £2- Pak pro každé z > £1 jsou čísla P(z) .. _ .. P(y) z = z — P(z)' definována a platí «i < y, £1 < y' < y =y P(y) Jiří Zelinka Numerické metody 7. přednáška, 5. dubna 2019 9/23 Algoritmus Začneme s počáteční aproximací x0 >^a zdvojenou metodou: xfc+i = xk - 2— Mohou nastat dva případy: O P(x0)P(x/c) > 0 pro všechna k. Pak x0 > xi > ... > xk > ... > £1? k = 0,1,... lim xk = O Existuje xk tak, že P(x/c)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 > ... > x/r_i > £i > x/c > ai > £2- Položme yo = xk a pokračujme dále klasickou Newtonovou metodou s touto počáteční aproximací: Yk+i = Yk P'iYk) k = 0,1,2,... Jiří Zelinka Numerické metody 7. přednáška, 5. dubna 2019 10/23 Snižování stupně Pi(x) — ~ numerické nepřesnosti v koeficientech Příklad P - polynom s kořeny £1 = 10, ..., £10 = 1 Aproximace kořenů: rsJ 6 = 10.000000040624446 = 8.999999654991576 = 8.000001300611824 £7 = 4.000018865503898 £10 = 0.99999962963847448 Jiří Zelinka Numerické metody 7. přednáška, 5. dubna 2019 11/23 Maehlyova metoda PlM=m, rl{x)=m--m-, Dosazením tohoto vyjádření do vzorce pro Newtonovu metodu pro polynom Pi dostaneme: xk+1 = xk P'M - PM Vhodná počáteční iterace pro Maehlyovu metodu: iterace x^, u níž došlo k „přestřelení" kořene pro zdvojenou Newtonovou metodou. Jiří Zelinka Numerické metody 7. přednáška, 5. dubna 2019 12/23 /N/ /N/ Obecně, jestliže jsme již nalezli aproximace kořenů £1?..., postupujeme obdobně a sestrojíme polynom Pj(x) = P(x) /N/ /N/ ^ (x -&)... (x - 0) (*) = P'(x) P(x) J 1 E— (X - ^) ... (X - Cj) (X - ^) ... (X - £y) ^ X - £; Newtonova metoda pro nalezení kořene je tvaru Xk+l = QjM, ;(x) = X - P(x) 7 /"M - E P(x) /=! * " & Jiří Zelinka Numerické metody 7. přednáška, 5. dubna 2019 13/23 Normy vektoru a matic Vektory - prvky IRn nebo C7, sloupcové, Normy vektorů Vektorová norma na Cn je funkce s následujícími vlastnostmi: O llxll > 0, Vx e Cn (z Cn do R) O O x ax = 0^x = o. o = (0,... ,0) T a x x Va eC, Vx g Cn O \\x + y < x + \\y\l VxjgP. □ ► < s Příklady vektorových norem: n 1 2 O ||x O ||x O llx El*/ /=1 r? 1 — oo El*/ /=1 max 1 x <^> xn - x *0. Jiří Zelinka Numerické metody 7. přednáška, 5. dubna 2019 15/23 Matice Nechť A je čtvercová matice řádu n s reálnými resp. komplexními prvky: A = í au 321 3l 32 n ]nn Á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: Jiří Zelinka Numerické metody 7. přednáška, 5. dubna 2019 16/23 Vlastní čísla a vlastní vektory A-x = \x x - vlastní vektor matice AA, A - příslušné vlastní číslo Vlastní čísla jsou kořeny charakteristického polynomu ^/\(A) = det(A • E — A), E - jednotková matice Spektrální poloměr matice: p(A) = maxUA/J; A/< je vlastní číslo matice A} n Stopa matice: tr(A) = akk k=l Jiří Zelinka Numerické metody 7. přednáška, 5. dubna 2019 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/4 g M„ A\ = 0 A je nulová matice aA a A , VaeC, V/4 g /4 + B < A + B AB\\<\A B A, B e Mn A, B G Mn Vlastnost 5) se nazývá multiplikativnost. Jiří Zelinka Numerické metody 7. přednáška, 5. dubna 2019 18/23 Souhlasnost maticové a vektorové normy Řekneme, že maticová norma je souhlasná s danou vektorovou normou , jestliže >4x x VxeC", Wl eMn. Přidružená norma Nechť je vektorová norma na Cn. 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í ||fj| > 1. Jiří Zelinka Numerické metody 7. přednáška, 5. dubna 2019 19/23 Věta 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 . Pak pro všechna vlastní čísla A matice A platí: A < A Jiří Zelinka Numerické metody 7. přednáška, 5. dubna 2019 20/23 Pridružené maticové normy Nechť A g Ain. Pridružené maticové normy k vektorovým normám OO J 2 jsou dány vztahy n O = max Yl \an l4M), p(A*A) je spektrální poloměr ZIM, — t kde /A* = /4' , pro reálné matice je A* = >4T. >4 2 _ spektrálni norma matice Jiří Zelinka Numerické metody 7. přednáška, 5. dubna 2019 21/23 Frobeniova norma Věta 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, 5. dubna 2019 23/23