2 системи на линеарни равенки - PDF бесплатно преземање

Повисоки деривати Услови на интерполација d k Φ dx k (x j) = y (k) j, (j =. N; k =. C j) го одредуваат полиномот за интерполација на хермитите Φ Π r со r + = n (+ c j). j = 2 системи на линеарни равенки 2. Гаусов алгоритам Коментар 2. (Задача) дадена: A R n n, b R n, n =. Вкупно 7: Решение x од линеарниот систем на равенки Ax = b формално x = A b, нумерички несоодветен (пресметковен напор да се оцени А) Растворливоста x R n е уникатно одредена ако и само ако Редовно n = 2, n = 3 решение со употреба на правилото на Крамер Коментар 2.2 (линеарни мрежни модели) Моделирање на комплексни системи (технологија, околина) Основни градежни блокови, поврзани со влезни/излезни односи и конзерваторски променливи Пример на електрични кола, дизајн на чипови Основен градежен блок: Отпорност Ом закон U i = R i I i, (i =, 2. 6) 8

равенки

. Правило на Кирхоф Во секој јазол: Збир на влезните струи еднакви на збирот на излеаните струи 2. Правило на Кирхоф Во секоја мрежа: Збир на падови на напон еднаков на збирот на изворите на напон Резултат Линеарен равенски систем 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 Еден ги брише редундантните равенки 4 = 2 3 и [, 2, 3] = [, 4, 3] + [2, 3, 4] + [, 2, 4], потоа Ax = b со AR 6 6, x = (I, I 2. I 6) R 6, b = (. U,) R 6. Забележете го пропорцијата на не-нула елементи во A малку ретко населени матрици Позицијата на не-нула елементи a ij во A произлегува од т.н. топологија на колото Rx = z со редовна горна триаголна матрица R = (r ij) R nn, т.е. т.е., 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

Пример 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 = (,). Замена наназад генерално xn = znr nn, xi = zinj = i + r ij xjr ii, (i = n, n 2.) Алгоритам за i = n: s: = zi за j = (i +): ns: = sr ij xjxi: = s/r ii Код на матлаб x = нули (големина (z)); x (n) = z (n)/r (n, n); за i = n -: -:, x (i) = (z (i) - r (i, i +: n) x (i +: n))/r (i, i); крај; аналогно на Lx = z со редовна долна триаголна матрица L = (l ij) R n n, d. т.е., l ii, l ij =, (i =. n; j = i +. n) замена за напред. Забелешка 2.4 (Гаусов алгоритам) Идеја на системот за равенки Ax = b во еквивалентен систем на скалести равенки со множење на една равенка со друг број освен нула, додавање на множеството на една равенка на друга равенка и/или разменување на равенки. 2

Пример x 7x 2 = 7 3x + 2x 2 + 6x 3 = 4 5x x 2 + 5x 3 = 6 Чекор k Додадете множители на k-та равенка на равенките k +. n, така што не-нула елементите се елиминираат во колоната kth под главната дијагонала, англиски: Гаусова елиминација 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 = 7х 2 + 6х 3 = 6. III = +25 II + III: 55x 3 = 55 замена назад x = (,). Проблем на главниот дијагонален елемент a (k) kk = во чекорот на елиминација на kth Решение Размена на равенката kth со една од равенките k +. n таков што стожерниот елемент a (k) kk (секогаш возможен ако A е редовен). Стратегија Определи p во чекорот на елиминација k < k, k +. n >таква што a (k) pk = макс < a(k): l = k, k +. n >и разменување k-та и p-та равенки (колони) Пивотирањето е исто така поволно за намалување на влијанието на грешките во заокружување lk Пример k = 2, равенки на размена II III x 7x 2 = 7 ĨI = III: 2,5х 2 + 5х 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

Алгоритам за k =: n p: = k; s: = kk за i = k +: n ако a ik> s тогаш p: = i; s: = a ik за j = k: n s: = a kj; a kj: = pj; a pj: = s s: = b k; b k: = b p; b p: = s за i = k +: n l ik: = a ik/a kk; b i: = b i l ik b k за j = k +: n a ij: = a ij l ik a kj Забелешка 2,5 (LU распаѓање) k-ти чекор на елиминација A (k) A (k +) со k n k + A (k) = со. L (k) =. A (k +) = во ознака на матрицата (без пивотирање) k l k +, k. l n, k n k +, A (k +) = l k +, k. л, к nknk A (k) = (IL (k)) A (k), A (): = A, A (n) =: U (горната триаголна матрица), (IL (n)) (IL ()) A = U 22

Забелешка 2.6 (Матрици на симетрични коефициенти, распаѓање на Холески) Важен посебен случај: Ax = b со A = A, особено исто така симетрични, позитивно определени матрици со коефициент A, т.е. Х. A = A x Axe>, (x R n \ <>). Гаусов алгоритам без свртување A = L U Нека D: = дијаг u ii D U е горната триаголна матрица со главни дијагонални елементи =. i n A = (L D D U) = (D U) DL Од единственоста на распаѓањето на LU (!) следи D U = L, т.е. A = LDL. Пресметка со n3 6 + O (n2) можни аритметички операции. Пивотизација: истовремена размена на редови и колони за одржување на симетријата. Симетрична, позитивна дефинитивна покажува дека Гаусовиот алгоритам секогаш може да се спроведе без да се сврти. Поради . i Cholesky распаѓање на A A = ˆLˆL со ˆL: = L D/2, D/2 = дијаг i i a a 2 a n a 2 a 22 a 2n. a n a n2 a nn = ˆl ˆl2. ˆL22. NLn ˆln2 ˆlnn ˆl ˆl2 ln ˆl22 ˆln2. AlLnn алгоритам за k =: n (k)/2 klkk: = a kk ˆl2 kj j = за i = (k +): n ˆl (k) ik: = a ik ˆlijˆlkj/ˆl kk j = напред/назад замена како во општ случај, но имајте предвид дека е зачувано само ˆL, не ˆL. Пресметувачки напор n3 6 + O (n2) аритметички операции, n квадратни корени 24

2.2 Дадена пресметка на линеарно изедначување Забелешка 2.7 (метод на најмали квадрати) дадена: вкупно: AR mn, m> n, ранг (A) = n, b R m решение x Rn на Ax = b метод на најмали квадрати (Гаус) Da i . Општо, нема класично решение x R n со Ax b = постои, се бара генерализирано решение x R n така што Ax b 2 min. () Еве v 2: = (m)/2 vv = vi 2 го означува евклидот Векторска норма на векторот v = (vi) mi = R m, видете Дел 3.2. Својство: За вектори y = (yi) R n, z = (zi) R mn, () y 2 2 = zi = n yi 2 + i = mni = Проблемот со најмали квадрати () е еквивалентен на z 2 i = y 2 2 + z 2 2. Секира b 2 2 = m (n) 2 a ij xjbi мин. I = j = неопходен услов за минимум! = xk Axe 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 = Гаусови нормални равенки A Ax = A b и рангот (A) = n е АА симетрична и позитивна заради AA = (AA) R nn конечно: ξ R n \ <> ξ (АА) ξ = (ξ А) (Aξ) = (Aξ) (Aξ) = Aξ 2 2>, затоа што Aξ поради ξ и ранг (A) = н. Решение на нормалните равенки со користење на распаѓање на Cholesky 25

Проблем Кога се користат Гаусовите равенки, нумеричкото решение е честопати многу чувствително на грешките во заокружувањето. Алтернативен метод на ортогонализација, видете забелешка 2 . Даден е примерот 2.8 (линеарна регресија): вкупно: податоци за мерење (xi, yi), (i =. М), со грешки во мерењето права линија y = ax + b, што вредностите на мерењето се што е можно подобри приближно: yia + bx i, (i =. m) пристап m (a + bx iyi) 2 мин i = ознака на матрицата A () a = y со y = (y b. ym) R m, A = xx 2 . xm Rm 2, n = 2 нормални равенки AA mmj = xjmj = mx 2 jj = () a = A ybxj () a = bmyjj = mxjya, b R jj = Забелешка 2.9 (Ортогонални трансформации) Идеја Користете ортогонални трансформации за да пронајдете линеарни системи на равенки и ги трансформираме линеарните проблеми на изедначување во еквивалентни проблеми од поедноставна форма. 26-ти

n = 2 ротации, рефлексии овде ротациони матрици (cos θ sin θ Q = sin θ cos θ) Литература за матрици на рефлексија: Стоер, Дофлхард/Хоман генерално Гивенови ротации, Рефлексии на домаќинства овде Гиванови ротации. G kl = c s. S c. l k R m m l k со c = cos θ, s = sin θ, c 2 + s 2 =. Одреди θ така што (G kl A) kl =: a kl sa ll + ca kl! = и 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 τ Забелешка 2. (QR распаѓање) дадено: AR mn, mn, ранг (A) = n Чекор-по-чекор елиминација на не-нула елементи a ij, (j