Numerické metody 10. přednáška, 25. dubna 2017
Jiří Zelinka
Jiří Zelinka        Numerické metody 10. přednáška, 25. dubna 2017
Opakování
Iteracní metody resení systémů lineárních rovnic
Systém
Ax = b
převedeme na
x = Tx + g
x
k+l
= TxK + g,      k = 0,1,...
Hlavní veta o konvergenci iteracního procesu
Posloupnost {xk}™   určená iteračním procesem x = Tx + g konverguje pro každou počáteční aproximaci x° G W právě tehdy, když p(T) < 1, přičemž
lim xk = x*, x* = Tx* + g
k^řoc
Jiří Zelinka        Numerické metody 10. přednáška, 25. dubna 2017 2/23
Jacobiova iterační metoda
Ax = b
A = D- L - U.
Ax = (D - L - U)x = b
x = D~X{L + U)x + D~Lb.
-i
xk+1 = D-\L+ U)xk + D-'b.
-i
Z /-té rovnice vypočteme x,-:
n
x'+1 = -
^-xk + —
' J o.. 7 o.. .   .        // //
7=1
Jiří Zelinka        Numerické metody 10. přednáška, 25. dubna 2017 3/23
Gaussova-Seidelova iterační metoda
i-l
xť+1 = -
j=l "
k+1
n i
fy xk + El
7=1+1
/ = 1.....n.
? • • • ?
Maticový zápis:
Jiří Zelinka        Numerické metody 10. přednáška, 25. dubna 2017 4/23
Konvergence
Silné řádkové (sloupcové) sumační kriterium:
Nechť matice A je ryze řádkově (sloupcově) diagonálně dominantní, tj.
Pak Jacobiova i Gaussova-Seidelova iterační metoda konverguje pro každou počáteční aproximaci x° e W. Věta
Nechť A je pozitivně definitní matice. Pak Gaussova-Seidelova metoda konverguje pro každou počáteční aproximaci.
n
/ = 1.....n.
7=1
Jiří Zelinka        Numerické metody 10. přednáška, 25. dubna 2017 5/23
Relaxační metody
Modifikace Gaussovy-Seidelovy metody, oj - relaxační parametr
xi
k+l _
= (1 - u)xf +
oj
au
bi-
i-i
7=1
n
k+1
j=i+l
SijXj
Relaxační metodu lze maticově zapsat takto
x^1 = (D - - u)D + ojU]xk + oj{D - ojL)~1b
TU = (D- ojL)-1^! - lo)D + loU]
Jiří Zelinka        Numerické metody 10. přednáška, 25. dubna 2017 6/23
Iterační metody pro systémy nelineárních rovnic
fi{xi,... ,xm) = o
F(x) = o,      xeMmo = (0,...,0)TeMm Systém převedeme na ekvivalentní rovnici
x = G(x), xeR
AT?
xi   = gi{xi,...,xm)
*m    = gm{xi,...,Xm)
Jiří Zelinka        Numerické metody 10. přednáška, 25. dubna 2017 7/23
Newtonova metoda pro systémy nelineárních rovnic
F(x) = o,      F G C2(0(|))
M*) =
( QJM.
dxi dfm{x)
dx,
m
dfm{x)
dx,
m
Taylorův rozvoj:
F(x + h) = F(x) + JF(x) • h + 0(\\h\\2) •(!,..., l)r
X = X , X
*+* =    + /)    h = xk+1 - xk
Zanedbáme chybový člen,
F(x + h) = o    JF(xk)(xk+i - xk) = -Fa(xk}
1= <\(y
Jiří Zelinka
Numerické metody 10. prednáška, 25. dubna 2017 8/23
xk+1=xk-Jř1(xk)F{xk)
Iterační funkce
G(x) = x - Jp1(x)F(x)
Veta
Nechť £ je kořenem rovnice F(x) = o. Nechť Jf{x) je regulární matice se spojitými prvky v okolí 0(£) bodu £, pricemz
pro všechna x z tohoto okolí. Nechť funkce fn i = 1,..., m, mají spojité druhé parciální derivace v 0(£). Posloupnost {x*}^_0 určená Newtonovou metodou konverguje ke kořenu £ za předpokladu, že počáteční aproximace x° leží dostatečně blízko £. Rád metody je roven dvěma.
Jiří Zelinka
Numerické metody 10. přednáška, 25. dubna 2017 9/23
Řešení systémů lin. rovnic - přímé metody
Základní pojmy
/ 3n
Ax = b, A =
X —
r/7/7
>A - matice soustavy, regulární. Řešení: x = A lb
Rozšířená matice soustavy:
(A\b) =
( 3U 321
3ln 32 n
\ 3nl
' nn
□ [5P
Jiří Zelinka        Numerické metody 10. prednáška, 25. dubna 2017 10/23
A A A
Bij
w =
- dolní trojúhelníková: a;j = 0 pro / < /
- horní trojúhelníková: a,y = 0 pro / > j.
- pásová, jestliže existují p, q, 1 < p, q < n taková, že = 0, jestliže i + p <j nebo j + q < i, šířka pásu
p + q-1.
A - trídiagonální pro p = q = 2.
>4 - ryze řádkově diagonálně dominantní
n
au
>
E
a/,-
/ = 1,..., n.
A - ryze sloupcové diagonálne dominantní - podobně Věta:
Ryze řádkově (sloupcově) diagonálně dominantní matice, je regulární. , n
Numerické metody 10. prednáška, 25. dubna 2017 11/23
Gaussova eliminační metoda
Úprava soustavy na soustavu s horní trojúhelníkovou maticí R:
{A | b) —> [R I b
Pak provádíme tzv. zpětný chod - počítáme řešení od poslední složky k první.
Elementární úpravy a matice úprav
Nemění řešení, každá úprava má inverzi.
1. násobení řádku nenulovou konstantou c
/ i   o ...
/Ol o
lc =
0 \
o \
/ 1 o /Ol o
\ o o
i/
1/c
\ o o
0 \
o \
i/
Jiří Zelinka
Numerické metody 10. přednáška, 25. dubna 2017 12/23
2. výměna řádků /, k
í 1 0 O 1
Vo
O
P; k - permutační matice
0\ 0
1	0	0 ••	• 0	0	0 ••	• 0
0	0	0 ••	• 0	1	0 ••	• 0
0	0	1		0	0 ••	• 0
0	0		1	0	0 ••	• 0
0	1	0 ••	• 0	0	0 ••	• 0
0	0	0 ••	• 0	0	1	
1/
Pi,k - Pi,k
<[fj]^ -š Q, O
Jiří Zelinka        Numerické metody 10. přednáška, 25. dubna 2017 13/23
přičtení c násobku /-tého řádku ke /r-tému, i < k
( 1 o
0 1
Gi,k,c -
0\ 0
V o
Jiří Zelinka        Numerické metody 10. přednáška, 25. dubna 2017 14/23
i,k,c
( 1 o
O 1
—c
o
Ve skutečnosti pro převod na trojúhelníkovou matici stačí 2. a 3. elementární úprava.
Jiří Zelinka
Numerické metody 10. přednáška, 25. dubna 2017 15/23
Postup pri Gaussove eliminaci
(1) výměna 1. a /c-tého řádku (v případě potřeby)
(ľ) vynulování prvního sloupce pod hlavní diagonálou
AM\bl1')) = G1-(AW\b<1)), G1
ki = -
f(1)
7c 1
f(1) '11
/   1 ••• hl 1
V U 0
Jiří Zelinka        Numerické metody 10. přednáška, 25. dubna 2017 16/23
(i) výměna /-tého. a /c-tého řádku (v případě potřeby) (i') vynulování /-tého sloupce pod hlavní diagonálou
/ = 2,..., n — 1
Jiří Zelinka        Numerické metody 10. přednáška, 25. dubna 2017 17/23
Gaussova eliminaca bez výmeny řádků:
/?|b) = G„_i •... G2 • Gi • (A | b) tedy
/? = Gn—i •... G2 • Gi • /A
odkud
G^ * G2 *. • • G^J^ R — A.
Matice G; jsou dolní trojúhelníková, tedy Gf' jsou také dolní trojúhelníkové, takže
A = /_ • R,      /_ = G^ G2 *... Gn_i. /_ - dolní trojúhelníková matice.
Jiří Zelinka        Numerické metody 10. přednáška, 25. dubna 2017 18/23
i
pak
V
o
/. — Gx G2  ... Gn\ —
-L;
( 1
-/-
21
V-í
A7l
/n,n-i   1 /
Jiří Zelinka        Numerické metody 10. přednáška, 25. dubna 2017 19/23
LR rozklad
A = L - R: LR (též LU) rozklad matice A
Použití při řešení soustavy: substituce Rx = y, řešíme soustavu Ly = b s dolní trojúhelníkovou maticí, pak Rx = y s horní trojúhelníkovou maticí.
LR rozklad s výměnou řádků
Provádíme LR rozklad matice P • A, kde P je vhodná permutační matice, která provádí výměnu řádků. Při praktickém výpočtu, pokud narazíme na potřebu vyměnit řádky, postupujeme takto:
Pokud bychom vyměnili řádky předem, v už vypočítané části matice L by tyto řádky byly vyměněny, zbytek by se nezměnil. Proto můžeme vyměnit řádky ve vypočítané části matice L. Dále v pomocném vektoru p na začátku nastaveném na (1,2,..., n)T zaznamenáme výměnu řádků, tedy vyměníme v něm stejné řádky.
Jiří Zelinka        Numerické metody 10. prednáška, 25. dubna 2017 20/23
Príklad
2x1 + 4x2 —  x3 = —5
xi +  x2 — 3x3 = —9
4xi + x2 + 2x3 = 9
Jiří Zelinka        Numerické metody 10. přednáška, 25. dubna 2017 21/23
Výběr vedoucího prvku (pivota) - částečný
Při úpravě i-tého sloupce najdeme mezi prvky aj;_1),..., a^_1)
(i   1 ^
prvek s maximální absoulutní hodnotou (např. a^- }), pak vyměníme /-tý a k-tý řádek.
Výběr vedoucího prvku (pivota) - úplný
(i   1 ^
Hledáme prvek s maximální absoultní hodnotou mezi , i <j < n, i < k < n, pak vyměníme příslušný řádek a spoupec, čímž se změní pořadí proměnných.
Příklad:
LR rozklad matice
A =
0,0001
1
se zaokrouhlováním na 3 platné číslice.
Jiří Zelinka        Numerické metody 10. přednáška, 25. dubna 2017 22/23
Veta
Nechť všechny hlavní minory matice A G A4„ jsou různé od nuly, tj.
311 Ž 0.
3ll 3i2 321 ^22
/o
au  ai2 ai3
321    ^22 ^23 332 333
^ 0, ... det/A ^ 0.
Pak matici >A lze rozložit na součin dolní a horní trojúhelníkové matice.
Důsledky
• Nechť matice A je pozitivně definitní. Pak GEM lze provést bez výměny řádků a sloupců.
• Nechť matice A je ryze řádkově diagonálně dominantní. Pak GEM lze provést bez výměny řádků a sloupců.
Jiří Zelinka        Numerické metody 10. přednáška, 25. dubna 2017 23/23