Numerické metody 8. přednáška, 12. dubna 2018 Jiří Zelinka Jiří Zelinka Numerické metody 8. přednáška, 12. dubna 2018 1 / 21 Opakování Normy matic Souhlasnost maticové a vektorové normy Řekneme, že maticová norma · je souhlasná s danou vektorovou normou · ϕ, jestliže Ax ϕ ≤ A x ϕ, ∀x ∈ Cn , ∀A ∈ Mn. Přidružená norma Nechť · ϕ je vektorová norma na Cn . Pak číslo A ϕ = max x ϕ=1 Ax ϕ je maticová norma souhlasná s danou vektorovou normou · ϕ. Jiří Zelinka Numerické metody 8. přednáška, 12. dubna 2018 2 / 21 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 λ matice A platí: |λ| ≤ A . Jiří Zelinka Numerické metody 8. přednáška, 12. dubna 2018 3 / 21 Věta Nechť B < 1, · je souhlasná s danou vektorovou normou. Pak matice E − B je regulární a platí (E − B)−1 ≤ E 1 − B . Konec opakování Jiří Zelinka Numerické metody 8. přednáška, 12. dubna 2018 4 / 21 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 − T)−1 g za předpokladu, že E − T je regulární. x0 ∈ Rn – libovolná počáteční aproximace. Posloupnost xk ∞ k=0 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 Jiří Zelinka Numerické metody 8. přednáška, 12. dubna 2018 5 / 21 Problémy: 1 Jak zvolit iterační matici T, tj. jakým způsobem převést systém Ax = b na systém x = Tx + g? 2 Za jakých předpokladů posloupnost xk ∞ k=0 konverguje pro libovolnou počáteční aproximaci k přesnému řešení x∗ ? x1 = Tx0 + g, x2 = Tx1 + g = T(Tx0 + g) + g = T2 x0 + (T + E)g, x3 = Tx2 + g = T3 x0 + (T2 + T + E)g, ... xk+1 = Tk+1 x0 + (Tk + Tk−1 + . . . + E)g. Definice Řekneme, že matice H je konvergentní, jestliže lim k→∞ Hk = O, kde O je nulová matice, konvergence je bodová. Jiří Zelinka Numerické metody 8. přednáška, 12. dubna 2018 6 / 21 Věta Následující tvrzení jsou ekvivalentní: 1 H je konvergentní matice. 2 lim k→∞ Hk = 0 pro nějakou přidruženou maticovou normu. 3 ρ(H) < 1 (ρ(H) je spektrální poloměr H). 4 lim k→∞ Hk x = o pro libovolný vektor x ∈ Rn . Lemma Nechť ρ(T) < 1. Pak E − T je regulární a platí (E − T)−1 = E + T + T2 + . . . Jiří Zelinka Numerické metody 8. přednáška, 12. dubna 2018 7 / 21 Hlavní věta o konvergenci iteračního procesu Posloupnost xk ∞ k=0 určená iteračním procesem x = Tx + g konverguje pro každou počáteční aproximaci x0 ∈ Rn právě tehdy, když ρ(T) < 1, přičemž lim k→∞ xk = x∗ , x∗ = Tx∗ + g Důsledek Nechť pro nějakou přidruženou maticovou normu platí T < 1. Pak posloupnost xk ∞ k=0 generovaná iteračním procesem x = Tx + g konverguje k řešení x∗ = (E − T)−1 g pro každou počáteční aproximaci x0 ∈ Rn . Dále platí x∗ − xk ≤ T k x∗ − x0 , x∗ − xk ≤ T k 1 − T x1 − x0 . Jiří Zelinka Numerické metody 8. přednáška, 12. dubna 2018 8 / 21 Kriteria pro zastavení výpočtu 1 xk+1 − xk / xk < ε 2 rk+1 ≤ ε( A xk+1 + b ), kde rk+1 = Axk+1 − b maticová norma je přidružená dané vektorové normě, ε > 0 je požadovaná přesnost. Jiří Zelinka Numerické metody 8. přednáška, 12. dubna 2018 9 / 21 Jacobiova iterační metoda Ax = b, A =      a11 · · · · · · a1n a21 a2n ... ... an1 · · · · · · ann      Matici A zapišme ve tvaru A = D + L + U, kde D =    a11 0 ... 0 ann    , Jiří Zelinka Numerické metody 8. přednáška, 12. dubna 2018 10 / 21 L =      0 0 a21 ... ... ... ... an1 · · · an,n−1 0      , U =      0 a12 · · · a1n ... ... ... ... an−1,n 0 0      . D je diagonální matice, L 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ří Zelinka Numerické metody 8. přednáška, 12. dubna 2018 11 / 21 Ax = (D + L + U)x = b Dx = −(L + U)x + b. Pokud aii = 0, i = 1, . . . , n, je matice D regulární a z předchozí rovnice lze vypočítat x = −D−1 (L + U)x + D−1 b. D−1 =    1 a11 0 ... 0 1 ann    , Jiří Zelinka Numerické metody 8. přednáška, 12. dubna 2018 12 / 21 Maticový tvar Jacobiovy iterační metody Jacobiova iterační matice: TJ = −D−1 (L + U) xk+1 = TJxk + D−1 b, TJ = (tij ), tij = − aij aii pro i = j, tii = 0 pro i = 1, . . . , n. TJ =             0 − a12 a11 · · · − a1n a11 − a21 a22 0 − a2n a22 ... ... ... − an1 ann − an2 ann · · · 0             , D−1 b =             b1 a11 b2 a22 ... bn ann             . Jiří Zelinka Numerické metody 8. přednáška, 12. dubna 2018 13 / 21 Realizace výpočtu: Z první rovnice vypočteme x1: a11x1+a12x2+· · ·+a1nxn = b1 ⇒ x1 = 1 a11 (b1−a12x2−. . .−a1nxn) xk+1 1 = 1 a11 (b1 − a12xk 2 − . . . − a1nxk n ), z druhé rovnice vypočteme x2: xk+1 2 = 1 a22 (b2 − a21xk 1 − a23xk 3 − . . . − a1nxk n ), obecně z i-té rovnice vypočteme xi : xk+1 i = − n j=1 j=i aij aii xk j + bi aii , až z n-té rovnice vypočteme xn, a na pravé straně takto získaného systému jsou prvky matice TJ. Jiří Zelinka Numerické metody 8. přednáška, 12. dubna 2018 14 / 21 Věta o konvergenci Jacobiovy iterační metody: Posloupnost xk ∞ k=0 generovaná metodou xk+1 = TJxk + D−1 b konverguje pro každou počáteční aproximaci x0 ∈ Rn právě tehdy, když (TJ) < 1. Odhad chyby: x∗ − xk ∞ ≤ TJ k ∞ 1 − T ∞ x1 − x0 ∞. Příklad Geometrický význam Jiří Zelinka Numerické metody 8. přednáška, 12. dubna 2018 15 / 21 Silné řádkové sumační kriterium: Nechť matice A je ryze řádkově diagonálně dominantní, tj. |aii | > n j=1 j=i |aij |, i = 1, . . . , n. Pak Jacobiova iterační metoda konverguje pro každou počáteční aproximaci x0 ∈ Rn . Silné sloupcové sumační kriterium: Nechť matice A je ryze sloupcově diagonálně dominantní, tj. |akk| > n i=1 i =k |aik|, k = 1, . . . , n. Pak Jacobiova iterační metoda konverguje pro každou počáteční aproximaci x0 ∈ Rn . Jiří Zelinka Numerické metody 8. přednáška, 12. dubna 2018 16 / 21 Gaussova-Seidelova iterační metoda Z první rovnice vypočteme x1: a11x1+a12x2+· · ·+a1nxn = b1 ⇒ x1 = 1 a11 (b1−a12x2−. . .−a1nxn) xk+1 1 = 1 a11 (b1 − a12xk 2 − . . . − a1nxk n ), z druhé rovnice vypočteme x2, pro x1 použijme novou iteraci: xk+1 2 = 1 a22 (b2 − a21xk+1 1 − a23xk 3 − . . . − a1nxk n ), ze třetí rovnice vypočteme x3, pro x1 a x2 použijme novou iteraci: xk+1 3 = 1 a33 (b3 − a31xk+1 1 − a32xk+1 2 − a34xk 4 . . . − a1nxk n ), Jiří Zelinka Numerické metody 8. přednáška, 12. dubna 2018 17 / 21 Obecně xk+1 i = − i−1 j=1 aij aii xk+1 j − n j=i+1 aij aii xk j + bi aii , i = 1, . . . , n. Maticový zápis: Ax = b ⇒ (D + L + U)x = b (D + L)x = −Ux + b. aii = 0, i = 1, . . . , n, ⇒ matice D + L je regulární a x = −(D + L)−1 Ux + (D + L)−1 b. Položme TG = −(D + L)−1 U, Gaussova-Seidelova iterační metoda je tvaru xk+1 = TG xk + g, g = (D + L)−1 b. Jiří Zelinka Numerické metody 8. přednáška, 12. dubna 2018 18 / 21 Věta Posloupnost xk ∞ k=0 generovaná Gaussovou-Seidelovou iterační metodou xk+1 = −(D + L)−1 Uxk + (D + L)−1 b. konverguje pro každou počáteční aproximaci x0 ∈ Rn právě tehdy, když (TG ) < 1. Silné řádkové sumační kriterium: Nechť matice A je ryze řádkově diagonálně dominantní, tj. |aii | > n j=1 j=i |aij |, i = 1, . . . , n. Pak Gaussova-Seidelova iterační metoda konverguje pro každou počáteční aproximaci x0 ∈ Rn . Jiří Zelinka Numerické metody 8. přednáška, 12. dubna 2018 19 / 21 Silné sloupcové sumační kriterium: Nechť matice A je ryze sloupcově diagonálně dominantní, tj. |akk| > n i=1 i =k |aik|, k = 1, . . . , n. Pak Gaussova-Seidelova iterační metoda konverguje pro každou počáteční aproximaci x0 ∈ Rn . Příklad Geometrický význam Jiří Zelinka Numerické metody 8. přednáška, 12. dubna 2018 20 / 21 Věta (Stein-Rosenberg) Nechť pro prvky matice A platí aij ≤ 0 pro všechna i = j a aii > 0, i = 1, . . . , n. Pak platí právě jedno z následujících tvrzení: 0 < (TG ) < (TJ) < 1 1 < (TJ) < (TG ) (TJ) = (TG ) = 0 (TJ) = (TG ) = 1. To znamená, že konvergují-li obě metody, Gaussova-Seidelova metoda konverguje rychleji. Věta Nechť A je pozitivně definitní matice. Pak Gaussova-Seidelova metoda konverguje pro každou počáteční aproximaci. Jiří Zelinka Numerické metody 8. přednáška, 12. dubna 2018 21 / 21