2 systémy lineárnych rovníc - PDF na stiahnutie zadarmo

Vyššie deriváty Interpolačné podmienky d k Φ dx k (x j) = y (k) j, (j =. N; k =. C j) určujú Hermitov interpolačný polynóm Φ Π r s r + = n (+ c j). j = 2 sústavy lineárnych rovníc 2. Gaussov algoritmus Komentár 2. (Zadanie úlohy): A R n n, b R n, n =. 7 celkom: Riešenie x lineárnej sústavy rovníc Ax = b formálne x = A b, numericky nevhodné (výpočtové úsilie na vyhodnotenie A) Rozpustnosť x R n je jednoznačne určená práve vtedy, ak a len vtedy, ak je bežné riešenie n = 2, n = 3 pomocou Cramerovho pravidla Komentár 2.2 (lineárne sieťové modely) Modelovanie zložitých systémov (technológia, prostredie) Základné stavebné bloky, prepojené vzťahmi vstup/výstup a konzervačnými premennými Príklad elektrických obvodov, návrh čipu Základný stavebný blok: Odpor Ohmov zákon U i = R i I i, (i =, 2. 6) 8

systémy

. Kirchhoffovo pravidlo V každom uzle: súčet prichádzajúcich prúdov rovný súčtu odchádzajúcich prúdov 2. Kirchhoffovo pravidlo V každej sieti: súčet poklesov napätia rovný súčtu zdrojových napätí Výsledok Systém lineárnych rovníc 2 3 4 [, 4, 3] [2, 3, 4] RR 4 R 6 [, 2, 4] R 2 R 5 R 6 [, 2, 3] R 3 R 4 R 5 RR 2 R 3 II 2 I 3 I 4 I 5 I 6 = UU Ak odstránime nadbytočné rovnice 4 = 2 3 a [, 2, 3] = [, 4, 3] + [2, 3, 4] + [, 2, 4], potom Ax = b s AR6 6, x = (I, I2. I 6) R 6, b = (. U,) R 6. Všimnite si podiel nenulových prvkov v A mierne riedko osídlených maticiach Poloha nenulových prvkov a ij v A vyplýva z takzvanej topológie obvodu Komentár 2.3 (rozložené systémy rovníc) Špeciálny prípad Rx = z s pravidelnou hornou trojuholníkovou maticou R = (r ij) R nn, t.j. t.j. r ii, r ij =, (i =. n; j =. i). r x + r 2 x 2 +. + r n x n = z r 22 x 2 +. + r 2n x n = z 2 Rx = z. =. r nn x n = z n 9

Príklad x 7x 2 + x 3 = 7 2,5x 2 + 5 x 3 = 2,5 6,2 x 3 = 6,2 x 3 = 6,2 6,2 =, x 2 = 2,5 5 2,5 =, x = 7 + 7 () = x = (,). Spätná substitúcia všeobecne xn = znr nn, xi = zinj = i + r ij xjr ii, (i = n, n 2.) Algoritmus pre i = n: s: = zi pre j = (i +): ns: = sr ij xjxi: = s/r ii Matlab Code x = nuly (veľkosť (z)); x (n) = z (n)/r (n, n); pre i = n -: -:, x (i) = (z (i) - r (i, i +: n) x (i +: n))/r (i, i); koniec; analogický k Lx = z s pravidelnou dolnou trojuholníkovou maticou L = (l ij) R n n, d. tj. l ii, l ij =, (i =. n; j = i +. n) dopredná substitúcia. Poznámka 2.4 (Gaussov algoritmus) Myšlienka systému rovníc Ax = b do ekvivalentného rozloženého systému rovníc vynásobením jednej rovnice číslom iným ako nula, pridaním násobku jednej rovnice k inej rovnici a/alebo zamenením rovníc. 2

Príklad x 7x 2 = 7 3x + 2x 2 + 6x 3 = 4 5x x 2 + 5x 3 = 6 Krok k Pridajte k rovniciam k + násobky k-tej rovnice. n, takže nenulové prvky sú eliminované v k-tom stĺpci pod hlavnou uhlopriečkou, anglicky: Gaussova eliminácia k = x 7x 2 = 7 II = + 3.x 2 + 6x 3 = 6. III = 5 2,5x 2 + 5x 3 = 2,5 k = 2 x 7x 2 = 7x 2 + 6x 3 = 6. III = +25 II + III: 55x 3 = 55 spätná substitúcia x = (,). Úloha hlavného diagonálneho prvku a (k) kk = v k-tom eliminačnom kroku Riešenie Výmena k-tej rovnice s jednou z rovníc k +. n taký, že otočný prvok a (k) kk (vždy možný, ak je A pravidelný). Stratégia Určte p v k-tom eliminačnom kroku < k, k +. n >také, že a (k) pk = max < a(k): l = k, k +. n >a zameniť k-tú a p-tú rovnicu (stĺpce) Otáčanie je tiež výhodné na zníženie vplyvu zaokrúhľovacích chýb lk Príklad k = 2, zameniť rovnice II III x 7x 2 = 7 ĨI = III: 2,5x 2 + 5x 3 = 2,5 ĨII = II: .x 2 + 6x 3 = 6. x 7x 2 = 7 2,5x 2 + 5x 3 = 2,5 ĨII = + 25 ĨI + ĨII: 6,2x 3 = 6,2 2

Algoritmus pre k =: n p: = k; s: = a kk pre i = k +: n ak a ik> s potom p: = i; s: = a ik pre j = k: n s: = a kj; a kj: = a pj; a pj: = s s: = b k; b k: = b p; b p: = s pre i = k +: n l ik: = a ik/a kk; b i: = b i l ik b k pre j = k +: n a ij: = a ij l ik a kj Poznámka 2.5 (rozklad LU) k-tý eliminačný krok A (k) A (k +) s k n k + A (k) = s. L (k) =. A (k +) = v maticovom zápise (bez otočenia) k l k +, k. l n, k n k +, A (k +) = l k +, k. l n, k. nknk A (k) = (IL (k)) A (k), A (): = A, A (n) =: U (horná trojuholníková matica), (IL (n)) (IL ()) A = U 22

Poznámka 2.6 (Matice symetrických koeficientov, Choleského rozklad) Dôležitý špeciálny prípad: Ax = b s A = A, najmä tiež symetrické, pozitívne určité matice koeficientov A, t.j. H. A = A x Ax>, (x R n \ <>). Gaussov algoritmus bez otáčania A = L U Nech D: = diag u ii D U je horná trojuholníková matica s hlavnými diagonálnymi prvkami =. i n A = (L D D U) = (D U) DL Z jedinečnosti rozkladu LU (!) vyplýva D U = L, teda A = LDL. Výpočet pomocou n3 6 + O (n2) aritmetických operácií je možný. Pivotizácia: súčasná výmena riadkov a stĺpcov na zachovanie symetrie. Symetrický, pozitívny určitý Jeden ukazuje, že Gaussov algoritmus je možné vždy vykonať bez otáčania. Kvôli . i n Choleský rozklad A A = ˆLˆL s ˆL: = L D/2, D/2 = diag i di a a 2 a n a 2 a 22 a 2n. a n a n2 a nn = ˆl ˆl2. 22L22. ˆLn ˆln2 ˆlnn ˆl ˆl2 ˆln ˆl22 ˆln2. ˆLnn algoritmus pre k =: n (k)/2 ˆlkk: = a kk ˆl2 kj j = pre i = (k +): n ˆl (k) ik: = a ik ˆlijˆlkj/ˆl kk j = substitúcia dopredu/dozadu ako vo všeobecnom prípade, ale nezabudnite, že sa uloží iba ˆL, nie ˆL. Výpočtové úsilie n3 6 + O (n2) aritmetické operácie, n druhá odmocnina 24

2.2 Výpočet lineárneho vyrovnania Poznámka 2.7 (metóda najmenších štvorcov) uvedená: súčet: AR mn, m> n, poradie (A) = n, b R m riešenie x Rn Ax = b metóda najmenších štvorcov (Gauss) Da i . Všeobecne neexistuje žiadne klasické riešenie x R n s Ax b =, treba hľadať všeobecné riešenie x R n také, že Ax b 2 min. () Tu v 2: = (m)/2 vv = vi 2 označuje euklidovské riešenie. Vektorová norma vektora v = (vi) mi = R m, pozri časť 3.2. Vlastnosť: Pre vektory y = (yi) R n, z = (zi) R mn, () y 2 2 = zi = n yi 2 + i = mni = Úloha najmenších štvorcov () je ekvivalentná z 2 i = y 2 2 + z 2 2. Sekera b 2 2 = m (n) 2 a ij xjbi min. I = j = nevyhnutná podmienka pre minimum! = xk Ax b 2 2 = 2 m (na ij xjbi) a ik, (k =. n), i = j = m (n) a ik a ij xj = i = j = ma ik bi, (k =. n), i = Gaussovské normálne rovnice A Ax = A b a poradie (A) = n je AA symetrické a pozitívne z dôvodu AA = (AA) R nn konečné: ξ R n \ <> ξ (AA) ξ = (ξ A) (Aξ) = (Aξ) (Aξ) = Aξ 2 2>, pretože Aξ kvôli ξ a poradie (A) = n. Riešenie normálnych rovníc pomocou Choleského rozkladu 25

Problém Pri použití Gaussových rovníc je numerické riešenie často veľmi citlivé na chyby zaokrúhľovania. Alternatívna metóda ortogonalizácie, pozri poznámku 2 . Uvedený príklad 2.8 (lineárna regresia): celkom: namerané údaje (xi, yi), (i =. M), s chybami merania priama čiara y = ax + b, ktoré sú namerané hodnoty čo najlepšie aproximované: yia + bx i, (i =. m) priblíženie m (a + bx iyi) 2 min i = maticový zápis A () a = y s y = (y b. ym) R m, A = xx 2 . xm Rm 2, n = 2 normálne rovnice AA mmj = xjmj = mx 2 jj = () a = A ybxj () a = bmyjj = mxjya, b R jj = Poznámka 2.9 (Ortogonálne transformácie) Nápad Použite ortogonálne transformácie na nájdenie lineárnych sústav rovníc a transformovať problémy lineárneho vyrovnávania na ekvivalentné problémy jednoduchšieho tvaru. 26

n = 2 rotácie, odrazy tu rotačné matice (cos θ sin θ Q = sin θ cos θ) Literatúra k reflexným maticiam: Stoer, Deuflhard/Hohmann vo všeobecnosti Givensove rotácie, Domáce odrazy tu Givensove rotácie. G kl = c s. S c. l k R m m l k s c = cos θ, s = sin θ, c 2 + s 2 =. Určte θ také, aby (G kl A) kl =: a kl sa ll + ca kl! = a c 2 + s 2 =. a kl> a ll: τ: = a ll a kl, s: = a kl a ll: τ: = a kl a ll, c: = + τ 2, + τ 2, c: = s τ s: = c τ Poznámka 2. (QR rozklad) dané: AR mn, mn, poradie (A) = n Postupná eliminácia nenulových prvkov a ij, (j