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

Сентябрь 14, 2022

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

Содержание

2. МЕТОДИ РОЗВ’ЯЗУВАННЯ СЛАР Методи чисельного розв’язування СЛАР діляться на дві групи: прямі та ітераційні. В прямих
4. ПРЯМІ МЕТОДИ РОЗВ’ЯЗУВАННЯ СЛАР МЕТОД ГАУССА Прямий хід методу Гаусса полягає в послідовному виключенні невідомих x1,x2,…,xn
5. МЕТОД ГАУССА Коефіцієнти системи обчислюються за формулами: Обчислення правих частин системи здійснюється за формулами:
6. МЕТОД ГАУССА Виключаючи послідовно невідомі із початкової системи отримуємо систему рівнянь Cx = y: Зворотній хід
7. МЕТОД ГАУССА Метод Гаусса має сигнальну функцію виду (поліноміальний): Елемент називається ведучим елементом на k-му кроці
8. Матрицею перестановок P називається квадратна матриця, у якої в кожному рядку і в кожному стовпці наявний
9. З системи Ax = b маємо Cx = y Можна показати b та y пов’язані між
10. Метод Гаусса відповідає розкладанню матриці A на добуток двох трикутних матриць: A = LU (L =
11. LU-розкладання матриці А
12. Приклад
13. Схема Холецького Самостійно: розглянути метод Холецького. Метод Холецького використовується для розв’язування СЛАР з симетричними матрицями (
14. Обчислення det(A) на основі LU-розкладу матриці det(A)= det(LU)= det(L) det(U) = Розв’язування СЛАР на основі LU-розкладу
15. Для обчислення оберненої матриці необхідно розв’язати n систем лінійних алгебраїчних рівнянь виду: A Z(j)= δ(j), j=1,n
16. Обчислення A-1 Знаючи розклад обернену матрицю легко обчислити як
17. РОЗВ’ЯЗУВАННЯ ПЕРЕВИЗНАЧЕНИХ СИСТЕМ РІВНЯНЬ Припустимо, що система Ax = b має матрицю A розмірністю m× n
18. ТОЧНІСТЬ РОЗВ’ЯЗКУ СЛАР 6,1 x 1 + 3,4 x 2 = 6,1 14,7 x 1 +
19. Графічна ілюстрація для систем рівнянь з погано обумовленою матрицею
20. Норми векторів Норма lp ||x||p = (|x1|p + |x2|p +…+|xn|p)1/p Евклидова норма ||x||2 = (|x1|2 +
21. Норми матриць Норма lp Евклидова норма Норма l1 Норма l∞
22. ВЛАСТИВОСТІ НОРМ векторів: ||x|| ≥ 0 ||x|| = 0 лише для x = 0 || c
23. ЧИСЛО ОБУМОВЛЕНОСТІ Нехай x* − точний розв’язок, xн − обчислене (наближене) значення розв’язку, δx = (x*
24. ЧИСЛО ОБУМОВЛЕНОСТІ Припустимо, що (A + δA)(x* + δx) = b. Маємо A δx + δA(x*
25. ОЦІНКА ПОХИБОК Похибка обчислення оберненої матриці ||A-1 – (A + δA)-1|| ||A -1|| ≤ cond (A)
27. Скачать презентацию

Слайд 2

МЕТОДИ РОЗВ’ЯЗУВАННЯ СЛАР
Методи чисельного розв’язування СЛАР діляться на дві групи:
прямі та

ітераційні.
В прямих (або точних) методах розв’язок x системи знаходиться за скінчену кількість арифметичних дій (методи Гаусса, LU-розкладання, прогонки, Халецького и т.д). Якщо матриця неособлива, тобто
то x = A-1b, де A-1 − обернена матриця.
A A-1 = A-1 A = E
Ітераційні методи полягають в тому, що розв’язок x системи знаходиться як границя послідовних наближень x(k) при k→∞, де k − номер ітерації (Якобі, Зейделя, варіаційного типу).

Слайд 3

Слайд 4

ПРЯМІ МЕТОДИ РОЗВ’ЯЗУВАННЯ СЛАР МЕТОД ГАУССА
Прямий хід методу Гаусса полягає в послідовному

виключенні невідомих x1,x2,…,xn з системи. Якщо то поділивши перше рівняння системи на отримаємо:
де
Помножимо це рівняння на і відніматимемо отримане рівняння від i-го рівняння системи. Після виключення x1 з решти рівнянь отримаємо:

Слайд 5

МЕТОД ГАУССА
Коефіцієнти системи обчислюються за формулами:
Обчислення правих частин системи здійснюється за

формулами:

Слайд 6

МЕТОД ГАУССА
Виключаючи послідовно невідомі із початкової системи отримуємо систему рівнянь Cx

= y:
Зворотній хід полягає в знаходженні невідомих :

Слайд 7

МЕТОД ГАУССА
Метод Гаусса має сигнальну функцію виду (поліноміальний):
Елемент називається ведучим елементом

на k-му кроці виключення. Основним обмеженням методу є припущення, що всі елементи відмінні від нуля. Щоб зменшити похибку ведучим необхідно вибирати найбільшим за модулем елемент.

Слайд 8

Матрицею перестановок P називається квадратна матриця, у якої в кожному рядку

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

Слайд 9

З системи Ax = b маємо Cx = y
Можна показати b

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

Слайд 10

Метод Гаусса відповідає розкладанню матриці A на добуток двох трикутних матриць:
A

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

Слайд 11

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

Слайд 12

Приклад

Слайд 13

Схема Холецького
Самостійно: розглянути метод Холецького.
Метод Холецького використовується для розв’язування СЛАР з

симетричними матрицями ( )

Слайд 14

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

на основі LU-розкладу матриці
Розкладання матриці A = LU
Розв’язування системи Ly = b
Розв’язування системи Ux = y

Обчислення det(A) та розв’язування СЛАР

Слайд 15

Для обчислення оберненої матриці необхідно розв’язати n систем лінійних алгебраїчних рівнянь

виду:
A Z(j)= δ(j), j=1,n
де
Z(j) − j-й стовпчик оберненої матриці,
δ(j) − j-й стовпчик одиничної матриці.

Обернена матриця − це матриця, для якої
AA-1 = E

Слайд 16

Обчислення A-1

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

Слайд 17

РОЗВ’ЯЗУВАННЯ ПЕРЕВИЗНАЧЕНИХ СИСТЕМ РІВНЯНЬ
Припустимо, що система
Ax = b
має матрицю A розмірністю

m× n (m > n).
Така система має безліч розв’язків, але можна вибрати серед них таке, що мінімізує нев’язку розв’язку ε = b – Ax.
Початкова перевизначена система зводиться до так званої нормальної форми
(ATA)x = Cx = ATb
Звідки
x = (ATA)-1ATb
Матриця С = ATA розмірністю (n × n) неособлива,
якщо стовпці матриці A незалежні.

Слайд 18

ТОЧНІСТЬ РОЗВ’ЯЗКУ СЛАР
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.

Слайд 19

Графічна ілюстрація для систем рівнянь
з погано обумовленою матрицею

Слайд 20

Норми векторів
Норма 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

Слайд 21

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

Слайд 22

ВЛАСТИВОСТІ НОРМ
векторів:
||x|| ≥ 0
||x|| = 0 лише для x = 0
||

c x|| = |c| ||x|| для всіх комплексних чисел c
||x + y|| ≤ ||x|| + ||y||
матриць:
||A|| ≥ 0
||A|| = 0 лише для A=0
|| c A|| = | c | ||A|| для всіх комплексних чисел c
||A + B|| ≤ ||A|| + ||B||
||AB|| ≤ ||A|| ||B||

Слайд 23

ЧИСЛО ОБУМОВЛЕНОСТІ
Нехай x* − точний розв’язок,
xн − обчислене (наближене) значення розв’язку,
δx

= (x* − xн) − похибка розв’язку.
ε = b − A xн − нев’язка розв’язку системи A x* = b.
Розглянемо випадок, коли
A(x* + δx) = b + δb,
звідки
δx = A-1δb.
Користуючись нормами , запишемо:
||δx|| ≤ ||A-1|| ||δb||,
||b|| ≤ ||A|| || x* ||
||δx|| ||b|| ≤ ||A-1|| ||δb|| ||A|| || x* ||.

||δx||

|| x* ||

≤

||A|| ||A-1||

||δb||

||b||

Слайд 24

ЧИСЛО ОБУМОВЛЕНОСТІ
Припустимо, що (A + δA)(x* + δx) = b.
Маємо
A δx

+ δA(x* + δx) = 0
− δx = A-1δA(x* + δx), ||δx|| ≤ ||A-1|| ||δA|| ||(x* + δx)||.
Звідки

||δx||

|| x* + δx||

≤

||A|| ||A-1||

||δA||

||A||

Число обумовленості cond (A) =

||A|| ||A-1||

Слайд 25

ОЦІНКА ПОХИБОК
Похибка обчислення оберненої матриці
||A-1 – (A + δA)-1||
||A -1||
≤
cond (A)
1

– cond (A) (||δA|| ||A||)

якщо ||δA|| ||A-1|| < 1.

||δA||

||A||
Похибка розв’язку системи

|| x* ||

≤

cond (A)

1 – cond (A) (||δA|| ||A||)

||δA||

||δx||

||A||

якщо ||δA|| ||A-1|| < 1.

||δb||

(

)

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

Содержание

МЕТОДИ РОЗВ’ЯЗУВАННЯ СЛАРМетоди чисельного розв’язування СЛАР діляться на дві групи:прямі та

ПРЯМІ МЕТОДИ РОЗВ’ЯЗУВАННЯ СЛАР МЕТОД ГАУССАПрямий хід методу Гаусса полягає в послідовному

МЕТОД ГАУССАКоефіцієнти системи обчислюються за формулами:Обчислення правих частин системи здійснюється за

МЕТОД ГАУССАВиключаючи послідовно невідомі із початкової системи отримуємо систему рівнянь Cx

МЕТОД ГАУССА Метод Гаусса має сигнальну функцію виду (поліноміальний):Елемент називається ведучим елементом

Матрицею перестановок P називається квадратна матриця, у якої в кожному рядку

З системи Ax = b маємо Cx = y Можна показати b

Метод Гаусса відповідає розкладанню матриці A на добуток двох трикутних матриць:A

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

Приклад

Схема ХолецькогоСамостійно: розглянути метод Холецького.Метод Холецького використовується для розв’язування СЛАР з

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

Для обчислення оберненої матриці необхідно розв’язати n систем лінійних алгебраїчних рівнянь

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

РОЗВ’ЯЗУВАННЯ ПЕРЕВИЗНАЧЕНИХ СИСТЕМ РІВНЯНЬ Припустимо, що системаAx = b має матрицю A розмірністю

ТОЧНІСТЬ РОЗВ’ЯЗКУ СЛАР6,1 x 1 + 3,4 x 2 = 6,1 14,7

Графічна ілюстрація для систем рівнянь з погано обумовленою матрицею

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

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

ВЛАСТИВОСТІ НОРМ векторів:||x|| ≥ 0||x|| = 0 лише для x = 0||

ЧИСЛО ОБУМОВЛЕНОСТІНехай x* − точний розв’язок,xн − обчислене (наближене) значення розв’язку,δx

ЧИСЛО ОБУМОВЛЕНОСТІПрипустимо, що (A + δA)(x* + δx) = b.МаємоA δx

ОЦІНКА ПОХИБОКПохибка обчислення оберненої матриці||A-1 – (A + δA)-1||||A -1||≤cond (A)1

Похожие презентации

МЕТОДИ РОЗВ’ЯЗУВАННЯ СЛАР
Методи чисельного розв’язування СЛАР діляться на дві групи:
прямі та

ПРЯМІ МЕТОДИ РОЗВ’ЯЗУВАННЯ СЛАР МЕТОД ГАУССА
Прямий хід методу Гаусса полягає в послідовному

МЕТОД ГАУССА
Коефіцієнти системи обчислюються за формулами:
Обчислення правих частин системи здійснюється за

МЕТОД ГАУССА
Виключаючи послідовно невідомі із початкової системи отримуємо систему рівнянь Cx

МЕТОД ГАУССА
Метод Гаусса має сигнальну функцію виду (поліноміальний):
Елемент називається ведучим елементом

З системи Ax = b маємо Cx = y
Можна показати b

Метод Гаусса відповідає розкладанню матриці A на добуток двох трикутних матриць:
A

Схема Холецького
Самостійно: розглянути метод Холецького.
Метод Холецького використовується для розв’язування СЛАР з

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

Обчислення A-1

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

РОЗВ’ЯЗУВАННЯ ПЕРЕВИЗНАЧЕНИХ СИСТЕМ РІВНЯНЬ
Припустимо, що система
Ax = b
має матрицю A розмірністю

ТОЧНІСТЬ РОЗВ’ЯЗКУ СЛАР
6,1 x 1 + 3,4 x 2 = 6,1 14,7

Графічна ілюстрація для систем рівнянь
з погано обумовленою матрицею

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

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

ВЛАСТИВОСТІ НОРМ
векторів:
||x|| ≥ 0
||x|| = 0 лише для x = 0
||

ЧИСЛО ОБУМОВЛЕНОСТІ
Нехай x* − точний розв’язок,
xн − обчислене (наближене) значення розв’язку,
δx

ЧИСЛО ОБУМОВЛЕНОСТІ
Припустимо, що (A + δA)(x* + δx) = b.
Маємо
A δx

ОЦІНКА ПОХИБОК
Похибка обчислення оберненої матриці
||A-1 – (A + δA)-1||
||A -1||
≤
cond (A)
1