Opakování Normy matic Souhlasnost maticové a vektorové normy Řekneme, že maticová norma || • || je souhlasná s danou vektorovou normou || • H^, jestliže \\Ax\\v < \\A\\ \\x\\v, WxeC", VA eMn- Pridružená norma Nechť je vektorová norma na C". Pak číslo II/4IL = max IIAxIL 11X^=1 je maticová norma souhlasná s danou vektorovou normou Jiří Zelinka Numerické metody 8. přednáška, 8. dubna 2015 2/18 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 8. přednáška, 8. dubna 2015 3/18 Veta Nechť ||61| < 1, || • || je souhlasná s danou vektorovou normou. Pak matice E — B je regulární a platí (E-B)-1 < IBI Konec opakování Jiří Zelinka Numerické metody 8. přednáška, 8. dubna 2015 4/18 Iterační metody řešení systémů lineárních rovnic Systém Ax = b převedeme na x = Tx + g x* - řešení x* = (E — Ty1 g za předpokladu, že E — T je regulární. x° G IR" - libovolná počáteční aproximace. Posloupnost {xk^_Q určená rekurentně vztahem xk+1 = Txk+g, k = 0,1,... se nazývá iterační posloupnost a matice T se nazývá iterační matice « □ ► < S ► I -O0.O Jiří Zelinka Numerické metody 8. přednáška, 8. dubna 2015 5/18 Problémy: O Jak zvolit iterační matici T, tj. jakým způsobem převést systém Ax = b na systém x = T x + gl O Za jakých předpokladů posloupnost {xk}^_Q konverguje pro libovolnou počáteční aproximaci k přesnému řešení r*? Tx° + g, Tx1 + g = T(Tx° + g) + g = T2x° + (T + E)g, Tx2+g= T3x° + {T2+T + E)g, ,k+l {Tk+T k-i x— = Tk+1x° + ^jk + Tk-i + ... + E}g Definice Řekneme, že matice H je konvergentní, jestliže lim Hk = O, kde O je nulová matice, konvergence je bodová^ Jiří Zelinka Numerické metody 8. přednáška, 8. dubna 2015 6/18 Veta Následující tvrzení jsou ekvivalentní: O H je konvergentní matice. O lim \\Hk\\ = 0 pro nějakou přidruženou maticovou normu. O p(H) < 1 (p{H) je spektrální poloměr H). O lim Hkx = o pro libovolný vektor x G W. Lemma Nechť p(T) < 1. Pak E — T je regulární a platí {E-T)-1 = E+T+T2 + ... Jiří Zelinka Numerické metody 8. přednáška, 8. dubna 2015 7/18 Hlavní veta o konvergenci iteracního procesu Posloupnost {■**}^10 určená iteračním procesem x = Tx + g konverguje pro každou počáteční aproximaci x° G M" právě tehdy, když p(T) < 1, přičemž lim xk = x*, x* = Tx* + g Důsledek Nechť pro nějakou přidruženou maticovou normu platí ||7~|| < 1. Pak posloupnost {xk}^_Q generovaná iteračním procesem x = Tx + g konverguje k řešení x* = (E — T)_1g pro každou počáteční aproximaci x° G IR". Dále platí Jiří Zelinka Numerické metody 8. přednáška, 8. dubna 2015 8/18 Kriteria pro zastavení výpočtu O \\xk+1 — xk\\/\\xk\\ < e O \\rk+1\\ < e{\\A\\ \\xk+1\\ + ||b||), kde rk+1 = Axk+1 - b maticová norma je přidružená dané vektorové normě, e > 0 je požadovaná přesnost. Jiří Zelinka Numerické metody 8. přednáška, 8. dubna 2015 9/18 Jacobiova iterační metoda Ax = b, / 3n 321 V a„i D V 0 3ln \ Sin Matici A zapišme ve tvaru A = D - L - U kde / 3ii 0 \ »n#i / Jiří Zelinka Numerické metody 8. přednáška, 8. dubna 2015 10 / 18 u í o — 321 V -a„i ■■ í O -3i2 Vo -a„,„-i O / -au \ ~an—\n 0 / D je diagonálni matice, /. je dolní trojúhelníková matice s nulami na diagonále a U je horní trojúhelníková matice s nulami na diagonále. JiŕT Zelinka Numerické metody 8. přednáška, 8. dubna 2015 11 / 18 Ax = (D - L - U)x = b Dx = {L+ U)x + b. Pokud a,-, 7^ 0, / = 1,...,/?, je matice D regulární a z předchozí rovnice lze vypočítat x = D-\L+U)x + D xb. D 1 (h \ 0 0 \ -i- / 3nn / Jiří Zelinka Numerické metody 8. přednáška, 8. dubna 2015 12 / 18 Maticový tvar Jacobiovy iteracní metody Jacobiova iterační matice: Tj = D'1 (L + U) Tj = (t;j), ty í Tj &nn .k+1 Tjxk + D ^b, ^ pro i ^ j, ts = 0 pro / = 1, 0 3l2 3in \ 311 3ll 321 0 32n 322 322 3n2 3nn D b í h_ \ 3ll 322 bn JiŕT Zelinka Numerické metody 8. přednáška, 8. dubna 2015 13 / 18 Realizace výpočtu: Z první rovnice vypočteme xi: 3iiXi+3i2X2H-----\-alnxn = bi^xi 1 aii .k+l aii (fel - 3i2X2 (/)i-ai2x2-.. .-3inxn) z druhé rovnice vypočteme x2: -(fe2 - 321X* - 323x| 322 obecně z /-té rovnice vypočteme x,-: .k+l až z n-té rovnice vypočteme xn, a na pravé straně takto získaného systému jsou prvky matice Ty. , n „ / = 1,... ,n. Pak Jacobiova iterační metoda konverguje pro každou počáteční aproximaci x° G IR". Silné sloupcové sumační kriterium: Nechť matice A je ryze sloupcově diagonálně dominantní, tj. \akk\ > /V = 1,..., n. 7 = 1 Pak Jacobiova iterační metoda konverguje pro každou počáteční aproximaci x° G IR". Jiří Zelinka Numerické metody 8. přednáška, 8. dubna 2015 16 / 18 Gaussova-Seidelova iterační metoda Z první rovnice vypočteme xi: a11x1+a12x2-\-----hainxn = bi xi = —(/>i-3i2x2-. • -3inxn) 3ll 311 (fel - 212X3 ainXn), z druhé rovnice vypočteme x2, pro xx použijme novou iteraci: 1 Jc+l 322 (62 - 32ix*+1 - a23x3A 3lnXn), ze třetí rovnice vypočteme x3, pro xx a x2 použijme novou iteraci: Jc+l 333 (63 - 331XÍ+1 - 332X2 - 334X4 ... - ainX*), -«flP> 1 -o^O- Jin Zelinka Numerické metody 8. přednáška, 8. dubna 2015 17 / 18 Obecně ;-l 3// 3// Maticový zápis: Ax = b => (D-L-U)x (D - L)x / = 1, b Ux + b. n. a,-, 0, / = 1,..., n, =>• matice D — L je regulární a x = (D - L) xUx + (D - Z.)-1^ Položme TG = (D — Gaussova-Seidelova iterační metoda je tvaru 7"6x*+g, g = (D-Z.)-1b. Jiří Zelinka Numerické metody 8. přednáška, 8. dubna 2015 18 / 18