Opakování
• Choleského metoda - rozklad symetrických matic
• Croutova metoda - rozklad třídiagonálních matic
Příklad
	2	-1	0	0	0	\		f 5	4	3	2	1 \
	-1	2	-1	0	0		i	4	8	6	4	2
	0	-1	2	-1	0		A 1 - -	3	6	9	6	3
	0	0	-1	2	-1		0	2	4	6	8	4
v	0	0	0	-1	2	/		\ 1	2	3	4	5/
Jiří Zelinka        Numerické metody 12. přednáška, 13. května 2015 2/15
Stabilita, podmíněnost
Definice
Algoritmus pro řešení Ax = b se nazývá stabilní, jestliže vypočtené řešení x je takové, že
{A + S)x = b + 5b,
kde S a 6b jsou malé; S se nazývá chybová matice. Definice
Pro libovolnou přidruženou maticovou normu definujeme číslo podmíněnosti matice A vztahem
k(A) = \\A\\ H^T1!!.
Řekneme, že matice A je dobře podmíněna, jestliže k(A) 1 a špatně podmíněna, jestliže k(A) je podstatně větší než 1.
Jiří Zelinka        Numerické metody 12. přednáška, 13. května 2015 3/15
Příklad
( 101  10 \ „ ,„ 11t
A  = { 10  i J ^  =111
^ = (-io 7oi° )    -   ^ = 111
Tedy k(A) = lil2 = 12321, A je špatně podmíněna. Příklad - Hilbertova matice
(l    1      i    ...     1 \
■"■2 3 n
111 _J_ ^   _       2      3 4      " ' n+1
1     _J_    _1_    . _ _ 1
\ n    n+1     n+2    '''     2n-l /
Pro n = 10 vzhledem k normě || . ||i je k(A) = 3,5353.10
Veta
Jestliže řešíme systém Ax = b v pohyblivé řádové čárce se zaokrouhlováním na t desetinných míst a k(A) 10°, pak vypočtené řešení x je správné na (ŕ — a — 1) desetinných míst.
A - pozitivně definitní matice
\\A\\2 = y/ďMÄ) = q{A)
\\AW2 = max A;
Ki<n
lA-1^ = ( min A,-)"1.
Ki<n
k{A)
max A/ min A;
Jiří Zelinka        Numerické metody 12. přednáška, 13. května 2015 5/15
Komplexní kořeny reálných polynomů
nn: třída polynomů stupně nejvýše n s reálnými koeficienty.
Perv
P(x) = anxn + an_ixn_1... + aix + a0.
6)^2, • • •, £n kořeny (reálné i komplexní) polynomu P. Zobecněné Hornerovo schéma
Polynom P dělíme kvadratickým trojčlenem
D(x) = x2 + px + q:
P(x) = D(x) • Q(x) + Ax + B pro <?(x) = bn 2xn 2 + ■ ■ ■ + bxx + b0.
<n>4ď> š -o^o-
Jin Zelinka        Numerické metody 12. přednáška, 13. května 2015 6/15
Platí:
b n -2	= 3n			
bn 3	= an	-1 - P^n	-2	
	= an	-2 - P6n	3 —	qbn-2
	= ak	f2 - P^/c	f 1 _	^/c+2
	= ai	- pbo -	qbi	
e	= a0	- qbo		
	an	an-i	3n-2	an 3	31	
-P	0	-Pbn-2	-Pbn 3	-Pbn 4     ■ ■	-P^o	0
	0	0	-qbn-2	-qbn 3   ■ ■		-g^o
	bn 2	6n 3	bn-H	bn-3		e
<n>4ď> š -o^o-
Jin Zelinka        Numerické metody 12. přednáška, 13. května 2015 7/15
Hodnota polynomu v komplexním čísle:
z G C, polynom P dělíme
D(x) = (x - z)(x - ž) = x2 + px + q, p = -ZR(z), q = |z|2 Pak P(z) = Az + B.
Bairstowova metoda
Podstatou Bairstowovy metody je myšlenka nalezení kvadratického trojčlenu, který je dělitelem daného polynomu P.
Označme z, ž, z = u + / v, dvojici komplexně sdružených kořenů polynomu P. Čísla z, ž jsou kořeny kvadratického trojčlenu D(x) = x2 + px + q, p = —2u, q = u2 + i/2. Chceme najít čísla p, q tak, aby polynom D dělil polynom P beze zbytku.
Jiří Zelinka        Numerické metody 12. přednáška, 13. května 2015 8/15
kde
P(x) = D{x)Q{x) + Ax + B,
D (x) = x2 + px + q,
Q(x) = Q(x, p, q)      je polynom st. n - 2,
A = A{p,q),
B = B{p,q).
Je třeba určit p, q tak, aby
A{p, q) = O,       B{p, q) = 0.
Jedná se o systém nelineárních rovnic a budeme ho řešit Newtonovou metodou pro systémy nelineárních rovnic.
Jiří Zelinka        Numerické metody 12. přednáška, 13. května 2015 9/15
Považujeme-li kvadratický trojčlen Dk(x) = x2 + Pk* + Qk za aproximaci dělitele, dostaneme další aproximaci
Dk+1(x) = x2 + pk+1x + qk+1, pk+1 = pk + h, qk+1 = qk + g
/ dA dA \
<9p dq
dB dB
\ dp dq J
h g
B{p, q)
dA    A.  dA    A.  dB    n. dB n. Označme — = A'p, — = A'q, — = B'p, — = B'q, pak dp      H dq      4 dp      H dq 4
A{p, q) + A'p{p, q)h + A'q{p, q)g = 0, B{p,q) + Bp{p,q)h + Bq{p,q)g = 0.
,    Numerické metody 12. přednáška, 13. května 2015 Jiří Zelinka        10 / 15
Derivujme vztah P(x) = D(x)Q(x) + Ax + B podle p a q:
0 = xQ{x) + Q'p{x)D{x) + + 6; 0 =  Q{x) + <3£(x)D(x) + A'qx + 6;
Odtud
(a) x(?(x) = -Q'p(x)D(x) - A'px - B'p,
(b) Q{x) = -Q'q{x)D{x)-A'qx-B'q.
—A'p, —B'p resp. — A'q, —B'q jsou koeficienty lineárních zbytku při dělení polynomu xQ(x) polynomem D(x), resp. Q(x) polynomem D(x). Položme
a = -A'q,      b = -B'q.
Tato čísla lze opět získat zobecněným Homérovým algoritmem pro dělení polynomů Q(x)/D(x).
Numerické metody 12. přednáška, 13. května 2015 Jiří Zelinka 11/15
Vypočet A'p, B'p.
xQ(x) = -xQ'q(x)D(x) + ax2 + bx xQ(x) = a(x2 + px + q) + bx — xQ'q(x)D(x) — apx — aq, a tedy
xQ(x) = (a - xQ'q(x)) D(x) + (b - ap)x - aq.
xQ(x) = -xQ'q(x)D(x) + ax2 + bx a po úpravě můžeme tento vztah zapsat ve tvaru
xQ(x) = a(x2 + px + q) + bx - xQ'q{x)D{x) - apx - q, a tedy
xQ(x) = (a - xQ'q(x)) D(x) + (b - ap)x - aq. Porovnáním rovností dostaneme
A'p = ap- b,       B'p = aq.
Numerické metody 12. přednáška, 13. května 2015 JiřT Zelinka 12/15
Soustavu pro h a g můžeme nyní zapsat takto:
(ap - b)h - ag + A =0, aqh - bg + B = 0.
Vyřešením této soustavy získáme čísla h, g a kvadratický trojčlen Dk+1(x).
,    Numerické metody 12. přednáška, 13. května 2015 Jiří Zelinka        13 / 15
Fraktály - aplikace numerických metod
Madelbrodova množina
Položme z0 = 0, zn+i = z* + c, c E C. Madelbrodova množina je pak definována jako množina komplexních čísel c,
pro která je posloupnost z0, zi, z2,... omezená.
I 3 ►   < 1 ►   < 1 ►      I -O0.O ,    Numerické metody 12. přednáška, 13. května 2015 Jiří Zelinka 14/15
Fraktál Newton (autor John Hubbard)
Newtonova metoda pro funkci f(x) = x3 — 1 v komplexním oboru. Barevně označíme oblasti podle konvergence k jednomu z kořenů:_
•O0.O