Numerické metody 12. přednáška, 12. května 2016 Jiří Zelinka Jiří Zelinka Numerické metody 12. prednáška, 12. května 20161 /17 Opakování • Choleského metoda - rozklad symetrických matic • Croutova metoda - rozklad třídiagonálních matic Croutova metoda A = ( *11 312 0 321 322 323 0 V o 0 o \ 3n—l,n 0 a„,„_! a„„ Jiří Zelinka Numerické metody 12. přednáška, 12. května 2016 2/17 A = LU L = ( kí fei O o I22 I32 o ^33 o \ o o O /n,n-l Inn J 3n = In 3f,f-l — 3 3/f = A",/—1^/—1,/ + 'l/j í 1 O "12 1 O "23 1 o i' = 2,3,..., n i' = 2,3,..., /7 / = 1,2,..., n — 1. o o \ "n-l,n / Numerické metody 12. přednáška, 12. května 2016 3/17 Veta Nechť A G Á4n je třídiagonální matice s vlastnostmi 3/;+i 7^ 0 > 3l2 3,71 > 1 + la/\/+l / = 2,3,..., n — 1, / = 2, ... , 77 — 1, '/7/7 > A - řádkově diagon dominantní Pak matice A je regulární a hodnoty //,-, / = 1,..., n, vypočtené ze uvedených vztahů jsou různé od nuly. Důsledek Jsou-li splněny předpoklady věty, lze matici A rozložit na součin dolní a horní trojúhelníkové matice v uvedeném tvaru Jiří Zelinka Numerické metody 12. přednáška, 12. května 2016 4/17 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 + £)x = b + ô b, kde £ a Sb jsou malé; £ se nazývá chybová matice. Definice Pro libovolnou přidruženou maticovou normu definujeme číslo podmíněnosti matice A vztahem k (A) = ||4|| \\A -i Ř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. I—I LF Jiří Zelinka Numerické metody 12. prednáška, 12. května 2016 5/17 Príklad A = A-1 = 101 10 10 1 1 -10 -10 101 A = 111 A'1 ! = 111 Tedy k(A) = lll2 = 12321, A je špatně podmíněna Príklad - Hilbertova matice /i A = 1 2 1 2 1 3 1 3 1 4 i \ n A7+1 1 n A7+1 A7+2 2n-l Pro /? = 10 vzhledem k normě || . ||i je k(Ä) = 3,5353.10 il3 Jiří Zelinka Numerické metody 12. přednáška, 12. května 2016 6/17 Veta Jestliže řešíme systém Ax = b v pohyblivé řádové čárce se zaokrouhlováním na ř desetinných míst a k(A) « 10a, pak vypočtené řešení x je správné na (t — a — l) desetinných míst. A - pozitivně definitní matice A\\2 = y/e(ÄrÄ) = Q{A) A 2— max A; Ki4x + B pro Q(x) = bn_2xn~2 + ''' + t>xx + bQ. Jiří Zelinka Numerické metody 12. přednáška, 12. května 2016 8/17 Platí: bn-3 = an-\ - pbn_2 bn-A = 3n_2 - pbn-3 - qbn-2 bk = ak+2 - pbk+i - qbk+2 A = 3i - pb0 - qbi B = a0 - q60 3„ än-1 än-2 än-3 3\ 30 -p 0 -pb„-2 -Pbn-3 — pbn-4 -pbo 0 -g 0 0 —qbn-2 —qbn-3 ■ ■ ■ -qbi -q bo bn-2 bn-3 bn-4 bn-3 A B Jiří Zelinka Numerické metody 12. přednáška, 12. května 2016 9/17 Hodnota polynomu v komplexním čísle: z G C, polynom P dělíme D(x) = (x - z)(x - ž) = x2 + px + q, p = -2ft(z), q = 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 + i 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 + v2. Chceme najít čísla p, q tak, aby polynom D dělil polynom P beze zbytku. Jiří Zelinka Numerické metody 12. prednáška, 12. května 2016 10/17 P{x) = D{x)Q{x) + Ax+B, kde D (x) = x2 + px + g, 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, fí(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. Numerické metody 12. přednáška, 12. května 2016 Jiří Zelinka 11/17 Po važ uje m e-li kvadratický trojčlen Dk(x) = x2 + pkx + qk za aproximaci dělitele, dostaneme další aproximaci Dk+1(x) = x2 + pk+1x + qk+1, pk+1 = pk + h, qk+1 = qk + g í dp dB \ ~dp dq dB ~dq 1 h g A(p, q) B{p,q) dA A, dA A, dB Označme — = An, — — An, dp dq dp b'p- ^ =pak A{p, q) + A'p{p: q)h + A'q{p, q)g = 0, B(p,q) + B'p(p,q)h + B,q{p,q)g = 0. Jirí Zelinka Numerické metody 12. prednáška, 12. kvetná 2016 12/17 Derivujme vztah P(x) — D(x)Q(x) + Ax + B podle p a q: 0 = xQ{x) + Q'p{x)D{x) + A'px + B'p 0 = Q(x) + Q'q{x)D{x) + A'qx + B'q Odtud (a) xQ(x) = -Q'p(x)D(x)-A'px-B'p, (b) o(x) = -o;(x)D(x)->A;x-fi;. —Ařp, —Břp resp. — /A^, —Bfq jsou koeficienty lineárních zbytků při dělení polynomu xč?(x) polynomem D(x), resp. polynomem D(x). Položme a = -4,, 6 = -B'q. Tato čísla lze opět získat zobecněným Homérovým algoritmem pro dělení polynomů Q(x)/D(x). < e ► < i ► < i ► i Numerické metody 12. přednáška, 12. května 2016 Jiří Zelinka 13/17 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- xQq(x)D(x) - a tedy xQ{x) =(a- xQ'q(x)) D{x) + {b - ap) Porovnáním rovností dostaneme A'p = ap-b, B'p = aq. Numerické metody 12. přednáška, 12. května 2016 Jiří Zelinka 14/17 apx - q, x — aq. 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 D/c+i(x). Jiří Zelinka Numerické metody 12. prednáška, 12. května 2016 15/17 Fraktály - aplikace numerických metod Madelbrodova množina Položme z0 = 0, z„+1 = z* + c, c G C. Madelbrodova množina je pak definována jako množina komplexních čísel c, pro která je posloupnost zq, zi, z2,... omezená. Re[c] Jiří Zelinka Numerické metody 12. prednáška, 12. května 2016 16/17 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ů: Numerické metody 12. prednáška, 12. května 2016 Jiří Zelinka 17/17