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, чисельно непридатне (обчислювальне зусилля для оцінки A) Розчинність 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 ij в A випливає з так званої топології схеми Коментар 2.3 (систематичні системи рівнянь) Особливий випадок 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 Код Matlab 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, так що ненульові елементи усуваються в k-му стовпці нижче основної діагоналі, англійська: Гаусова елімінація 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.x 2 + 6x 3 = 6. III = +25 II + III: 55x 3 = 55 зворотна підстановка x = (,). Основний діагональний елемент задачі a (k) kk = на k-му етапі усунення Розв’язання Заміна k-го рівняння з одним із рівнянь 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,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
Алгоритм для k =: n p: = k; s: = a kk для i = k +: n, якщо a ik> s, то p: = i; s: = a ik для j = k: n s: = a kj; a kj: = a 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. l n, 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, тобто H. A = A x Ax>, (x R n \ <>). Гауссов алгоритм без повороту A = L U Нехай D: = diag 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 n Холесківське розкладання A A = ˆLˆL з ˆ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. ˆL22. ˆLn ˆln2 ˆlnn ˆl ˆl2 ˆln ˆl22 ˆln2. Алгоритм ˆLnn для k =: n (k)/2 ˆlkk: = 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 хв. () Тут 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. Ax b 2 2 = m (n) 2 a ij xjbi хв. I = j = необхідна умова для мінімуму! = 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 = гауссові нормальні рівняння A Ax = A b і rank (A) = n AA симетричний і додатний через AA = (AA) R nn скінченний: ξ R n \ <> ξ (AA) ξ = (ξ A) (Aξ) = (Aξ) (Aξ) = Aξ 2 2>, оскільки Aξ через ξ і ранг (A) = n. Розв’язання нормальних рівнянь за допомогою розкладання Холеського 25
Проблема При використанні рівнянь Гауса числове рішення часто дуже чутливе до помилок округлення. Альтернативний метод ортогоналізації, див. Зауваження 2 . Наведено приклад 2.8 (лінійна регресія): загальна: дані вимірювань (xi, yi), (i =. M), з похибками вимірювання пряма лінія 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 θ) Література про матриці відбиття: Stoer, Deuflhard/Hohmann взагалі обертання Givens, відбиття домогосподарів тут Givens обертання. 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, rank (A) = n Поетапна елімінація ненульових елементів a ij, (j