Numerické metody 8. přednáška, 9. dubna 2014 Jiří Zelinka Jiří Zelinka Numerické metody 8. přednáška, 9. dubna 2014 1 / 19 Opakování 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, 9. dubna 2014 2 / 19 Konvergence iterační posloupnosti 1 T je konvergentní matice. 2 lim k→∞ Tk = 0 pro nějakou přidruženou maticovou normu. 3 ρ(T) < 1 (ρ(T) je spektrální poloměr T). 4 lim k→∞ Tk x = o pro libovolný vektor x ∈ Rn . Jiří Zelinka Numerické metody 8. přednáška, 9. dubna 2014 3 / 19 Hlavní věta o konvergenci iteračního procesu Posloupnost xk ∞ k=0 určená iteračním procesem xk+1 = Txk + g, konverguje k řešení x∗ = (E − T)−1 g 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 Odhad chyby Nechť pro nějakou přidruženou maticovou normu platí T < 1. Pak iterační posloupnost konverguje a x∗ − xk ≤ T k x∗ − x0 , x∗ − xk ≤ T k 1 − T x1 − x0 . Konec opakování Jiří Zelinka Numerické metody 8. přednáška, 9. dubna 2014 4 / 19 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, 9. dubna 2014 5 / 19 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, 9. dubna 2014 6 / 19 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, 9. dubna 2014 7 / 19 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, 9. dubna 2014 8 / 19 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+1 n ), z druhé rovnice vypočteme x2: xk+1 2 = 1 a22 (b2 − a21xk 1 − a23xk 3 − . . . − a1nxk+1 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, 9. dubna 2014 9 / 19 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, 9. dubna 2014 10 / 19 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, 9. dubna 2014 11 / 19 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+1 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+1 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+1 n ), Jiří Zelinka Numerické metody 8. přednáška, 9. dubna 2014 12 / 19 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, 9. dubna 2014 13 / 19 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, 9. dubna 2014 14 / 19 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, 9. dubna 2014 15 / 19 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, 9. dubna 2014 16 / 19 Relaxační metody Modifikace Gaussovy–Seidelovy metody, ω – relaxační parametr xk+1 i = (1 − ω)xk i + ω aii bi − i−1 j=1 aij xk+1 j − n j=i+1 aij xk j . Relaxační metodu lze maticově zapsat takto xk+1 = (D − ωL)−1 [(1 − ω)D + ωU]xk + ω(D − ωL)−1 b Tω = (D − ωL)−1 [(1 − ω)D + ωU] Jiří Zelinka Numerické metody 8. přednáška, 9. dubna 2014 17 / 19 Hodnoty parametru ω: Pro 0 < ω < 1 se iterační metody nazývají metodami dolní relaxace. Tyto metody jsou vhodné v případě, že Gaussova-Seidelova metoda nekonverguje. Pro ω = 1 je relaxační metoda totožná s GaussovouSeidelovou metodou. Pro 1 < ω se metody nazývají metodami horní relaxace, nebo častěji SOR metodami (SOR = Successive Over-Relaxation). Tyto metody lze užít ke zrychlení konvergence GaussovySeidelovy metody. Věta (Kahan). Nechť aii = 0, i = 1, . . . , n. Pak (Tω) ≥ |ω − 1|. Důsledek: Má smysl uvažovat jen ω ∈ (0, 2). Jiří Zelinka Numerické metody 8. přednáška, 9. dubna 2014 18 / 19 Věta (Ostrowski-Reich). Pro pozitivně definitní matici A platí (Tω) < 1 pro všechna ω ∈ (0, 2). Příklad Geometrický význam Jiří Zelinka Numerické metody 8. přednáška, 9. dubna 2014 19 / 19