Методи розв’язування СЛАР (Система лінійних алгебраїчних рівнянь) презентация

МЕТОДИ РОЗВ’ЯЗУВАННЯ СЛАР

МЕТОДИ РОЗВ’ЯЗУВАННЯ СЛАР

ПРЯМІ МЕТОДИ РОЗВ’ЯЗУВАННЯ СЛАР МЕТОД ГАУССА

МЕТОД ГАУССА

МЕТОД ГАУССА

МЕТОД ГАУССА Метод Гаусса має сигнальну функцію виду (поліноміальний): Елемент називається ведучим елементом на k-му кроці виключення. Основним обмеженням методу є припущення, що всі елементи відмінні від нуля. Щоб зменшити похибку ведучим необхідно вибирати найбільшим за модулем елемент.

Матрицею перестановок P називається квадратна матриця, у якої в кожному рядку і в кожному стовпці наявний лише один відмінний від нуля і рівний одиниці елемент. Елементарною матрицею перестановок Pki називається матриця, отримана з одиничної матриці перестановкою k-го і i-го рядків. Наприклад, елементарними матрицями перестановок третього порядку є матриці: Добуток двох (а отже, і будь-якої кількості) елементарних матриць перестановок є матрицею перестановок (не обов’язково елементарною). Матрицю PkiA отримують із матриці A перестановкою k-го і i-го рядків. Матрицю APki отримують із матриці A перестановкою k-го і i-го стовпців. Метод Гаусса з вибором головного елемента по стовпцю еквівалентний звичайному методу Гаусса, який застосовують до системи

З системи Ax = b маємо Cx = y З системи Ax = b маємо Cx = y Можна показати b та y пов’язані між собою як Dy = b, де матриця D має вигляд: З y = D-1b Маємо Cx = D-1b  DCx = b  A = DC

Метод Гаусса відповідає розкладанню матриці A на добуток двох трикутних матриць: Метод Гаусса відповідає розкладанню матриці A на добуток двох трикутних матриць: A = LU (L = D, U = C) тобто Якщо det A ≠ 0, то існує матриця перестановок P така, що справедливе розкладання

LU-розкладання матриці А

Приклад

Схема Холецького

Обчислення det(A) на основі LU-розкладу матриці Обчислення det(A) на основі LU-розкладу матриці det(A)= det(LU)= det(L) det(U) = Розв’язування СЛАР на основі LU-розкладу матриці Розкладання матриці A = LU Розв’язування системи Ly = b Розв’язування системи Ux = y

Обчислення A-1 Знаючи розклад обернену матрицю легко обчислити як

РОЗВ’ЯЗУВАННЯ ПЕРЕВИЗНАЧЕНИХ СИСТЕМ РІВНЯНЬ Припустимо, що система Ax = b має матрицю A розмірністю m n (m > n). Така система має безліч розв’язків, але можна вибрати серед них таке, що мінімізує нев’язку розв’язку  = b – Ax. Початкова перевизначена система зводиться до так званої нормальної форми (ATA)x = Cx = ATb Звідки x = (ATA)-1ATb Матриця С = ATA розмірністю (n  n) неособлива, якщо стовпці матриці A незалежні.

ТОЧНІСТЬ РОЗВ’ЯЗКУ СЛАР 6,1 x 1 + 3,4 x 2 = 6,1 14,7 x 1 + 8,2 x 2 = 14,7 x 1= 1; x 2 = 0. 6,1 x 1 + 3,4 x 2 = 6,101 14,7 x 1 + 8,2 x 2 = 14,7 x 1= 1,205; x 2 = -0,3675. 6,101 x 1 + 3,4 x 2 = 6,1 14,7 x 1 + 8,2 x 2 = 14,7 x 1= 0,829875; x 2 = 0,304979.

Норми векторів Норма lp ||x||p = (|x1|p + |x2|p +…+|xn|p)1/p Евклидова норма ||x||2 = (|x1|2 + |x2|2 +…+|xn|2)1/2 Норма l1 ||x||1 = (|x1| + |x2| +…+|xn|) Норма l ||x|| = max {|x1|,|x2|,…,|xn|) i

Норми матриць Норма lp Евклидова норма Норма l1 Норма l

ВЛАСТИВОСТІ НОРМ

ЧИСЛО ОБУМОВЛЕНОСТІ

ЧИСЛО ОБУМОВЛЕНОСТІ

ОЦІНКА ПОХИБОК

ТОЧНІСТЬ РОЗВ’ЯЗКУ СЛАР 6,1 x 1 + 3,4 x 2 = 6,1 14,7 x 1 + 8,2 x 2 = 14,7 x 1= 1; x 2 = 0. 6,1 x 1 + 3,4 x 2 = 6,101 14,7 x 1 + 8,2 x 2 = 14,7 x1= 1,205; x 2 = -0,3675. 6,101 x 1 + 3,4 x 2 = 6,1 14,7 x 1 + 8,2 x 2 = 14,7 x 1= 0,829875; x 2 = 0,304979. cond(A)=1.1908*104 |A| = 0.04