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 е ясно определена, ако и само ако A регулярно n = 2, n = 3 решение, използващо правилото на Cramer Коментар 2.2 (линейни мрежови модели) Моделиране на сложни системи (технология, околна среда) Основни градивни елементи, свързани чрез входно/изходни взаимоотношения и запазени величини Пример за електрически вериги, дизайн на чипа Основен градивен блок: Закон за съпротивлението на Um = R i I i, (i =, 2. 6) 8

уравнения

. Правило на Kirchhoff Във всеки възел: Сума на входящите токове, равна на сумата на изходящите токове 2. Правило на Kirchhoff Във всяка мрежа: Сума от спада на напрежението, равна на сумата от напреженията на източника Резултат Линейна система за уравнения 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 метод на най-малките квадрати (Gauss) Da i . Общ не съществува класическо решение x R n с Ax b =, търси се обобщено решение x R n такова, че Ax b 2 min. () Тук v 2: = (m)/2 v v = vi 2 означава евклидовата векторна норма на вектора v = (v i) m i = 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 и ранг (A) = n е AA симетричен и положителен поради AA = (AA) R nn краен: ξ R n \ <> ξ (AA) ξ = (ξ A) (Aξ) = (Aξ) (Aξ) = Aξ 2 2>, защото Aξ поради ξ и ранг (A) = n. Решение на нормалните уравнения с помощта на разлагане на Cholesky 25

Проблем Когато се използват уравнения на Гаус, численото решение често е много чувствително към грешки при закръгляване. Алтернативни методи за ортогонализация, вж. Коментар 2 . Даден пример 2.8 (линейна регресия): общо: данни за измерване (xi, yi), (i =. M), с грешки в измерването права линия y = ax + b, която максимално приближава стойностите на измерване: yia + bx i, (i =. m) Подход m (a + bx iyi) 2 min 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, ранг (A) = n Елиминиране стъпка по стъпка на ненулевите елементи a ij, (j