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

Сентябрь 14, 2022

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

Содержание

2. МЕТОД ПРОСТОЇ ІТЕРАЦІЇ Припустимо, що і перетворимо систему до вигляду
3. x(k+1) = αx(k) + β, k=0,1,2… або у розгорнутому вигляді
7. ЗБІЖНІСТЬ МЕТОДУ ПРОСТОЇ ІТЕРАЦІЇ Для збіжності процесу обчислень необхідно, щоб виконувалась умова ||α|| Відповідно для різних
8. Теорема Якщо матриця α системи рівнянь x(k+1) = αx(k) + β задовольняє одну із умов то
9. ПОХИБКИ МЕТОДУ ПРОСТОЇ ІТЕРАЦІЇ Глобальна похибка розв’язку на двох сусідніх ітераціях ||x(k+1) – x*|| = ||α||
10. МЕТОД ЯКОБІ Запишемо метод Якобі в матричній формі. Для цього запишемо матрицю A як: A =
11. МЕТОД ЯКОБІ Запишемо СЛАР як: (L + D + U)x = b або Dx = b
12. МЕТОД ЯКОБІ При цьому Для збіжності методу Якобі достатньо, щоб матриця α мала домінуючу головну діагональ:
13. МЕТОД ЯКОБІ
14. МЕТОД ГАУССА-ЗЕЙДЕЛЯ Маємо (L + D)x = b - Ux У матричній формі метод Гаусса-Зейделя записується
17. ПОХИБКИ МЕТОДУ ГАУССА-ЗЕЙДЕЛЯ Локальна похибка за наближеннями, що отримані на двох сусідніх ітераціях Метод Гаусса-Зейделя слід
18. x* = 0.4; y* = 1.2
19. x=0,4; y=1,2
20. КАНОНІЧНА ФОРМА ІТЕРАЦІЙНИХ МЕТОДІВ Канонічною формою однокрокових ітераційних методів розв’язування СЛАР називається їх запис у вигляді:
21. МЕТОД РЕЛАКСАЦІЇ Умови збіжності можна покращити, якщо ввести коефіцієнт демпфірування для врахування нев’язки Тоді метод простої
25. Метод релаксації
26. РОЗВ’ЯЗАННЯ СИСТЕМ НЕЛІНІЙНИХ РІВНЯНЬ У загальному випадку системa нелінійних рівнянь записується у вигляді де − функції
27. Для методу простої ітерації можна записати: де На першій ітерації на основі початкового наближення наступне знаходять
28. де – матриця Якобі, Одним із серйозних недоліків методу простих ітерацій є складність вибору функцій які
29. Узагальнений метод Ньютона:
34. Скачать презентацию

Слайд 2

МЕТОД ПРОСТОЇ ІТЕРАЦІЇ
Припустимо, що і перетворимо систему
до вигляду

Слайд 3

x(k+1) = αx(k) + β, k=0,1,2…
або у розгорнутому вигляді

Слайд 4

Слайд 5

Слайд 6

Слайд 7

ЗБІЖНІСТЬ МЕТОДУ ПРОСТОЇ ІТЕРАЦІЇ
Для збіжності процесу обчислень необхідно, щоб виконувалась
умова
||α||

< 1.
Відповідно для різних матричних норм:

Слайд 8

Теорема
Якщо матриця α системи рівнянь x(k+1) = αx(k) + β
задовольняє

одну із умов
то ця система рівнянь має єдиний розв’язок x* = (x*1, x*2…, x*n), який можна обчислити як границю послідовності {x (k+1)}, починаючи з довільного початкового вектора x(0) = (x(0)1, x(0)2…, x(0)n)

Слайд 9

ПОХИБКИ МЕТОДУ ПРОСТОЇ ІТЕРАЦІЇ
Глобальна похибка розв’язку на двох сусідніх ітераціях
||x(k+1) –

x*|| = ||α|| ||x(k) – x*||
Локальні похибки, що отримані на двох сусідніх ітераціях

Метод простої ітерації слід завершити, якщо стане справедливою нерівність:
де ε – наперед задана точність обчислень.
Аналогічні умови дійсні і для інших матричних норм.

Слайд 10

МЕТОД ЯКОБІ
Запишемо метод Якобі в матричній формі. Для цього запишемо матрицю

A як:
A = L + D + U.

Слайд 11

МЕТОД ЯКОБІ
Запишемо СЛАР як:
(L + D + U)x = b
або
Dx

= b - (L + U)x.
Тоді у матричній формі метод Якобі має вид:
Dx(k+1) = b - (L + U)x(k)
З x(k+1) = - D-1(L + U)x(k) + D-1b
видно, що матриця перетворення ітераційного методу x(k+1) = αx(k) + β має вид:
α = - D-1(L + U).

Слайд 12

МЕТОД ЯКОБІ
При цьому
Для збіжності методу Якобі достатньо, щоб матриця α мала

домінуючу головну діагональ:
тобто

Слайд 13

МЕТОД ЯКОБІ

Слайд 14

МЕТОД ГАУССА-ЗЕЙДЕЛЯ
Маємо (L + D)x = b - Ux
У матричній формі

метод Гаусса-Зейделя записується як:
(L + D) х(k+ 1) = b - Uх(k).
де матриця перетворення має вигляд
α = - (D + L)-1U
Умови збіжності методів Якобі і Гаусса-Зейделя ідентичні.

Слайд 15

Слайд 16

Слайд 17

ПОХИБКИ МЕТОДУ ГАУССА-ЗЕЙДЕЛЯ
Локальна похибка за наближеннями, що отримані на двох сусідніх

ітераціях

Метод Гаусса-Зейделя слід завершити, якщо стане справедливою нерівність:
де ε – наперед задана точність обчислень.
Аналогічні умови дійсні і для інших матричних норм.

Слайд 18

x* = 0.4; y* = 1.2

Слайд 19

x=0,4; y=1,2

Слайд 20

КАНОНІЧНА ФОРМА ІТЕРАЦІЙНИХ МЕТОДІВ
Канонічною формою однокрокових ітераційних методів розв’язування СЛАР називається

їх запис у вигляді:
де Bk+1 − матриця, яка задає ітераційний метод; τk+1− ітераційний параметр, що задає швидкість збіжності методу.
Якщо Bk+1 = E метод називається явним (інакше неявним).
Якщо Bk+1= B та τk+1 = τ, метод називається стаціонарним (нестаціонарним в іншому випадку).
Канонічна форма методів Якобі та Зейделя

Слайд 21

МЕТОД РЕЛАКСАЦІЇ
Умови збіжності можна покращити, якщо ввести коефіцієнт демпфірування для врахування

нев’язки

Тоді метод простої ітерації перетворюється на метод верхньої релаксації (якщо вибрати для прискорення збіжності ), який застосовується для розв’язання систем лінійних рівнянь великої розмірності , або метод нижньої релаксації ( ) .

Слайд 22

Слайд 23

Слайд 24

Слайд 25

Метод релаксації

Слайд 26

РОЗВ’ЯЗАННЯ СИСТЕМ НЕЛІНІЙНИХ РІВНЯНЬ
У загальному випадку системa нелінійних рівнянь записується у вигляді
де − функції

дійсних змінних
Систему можна записати у вигляді
де

Слайд 27

Для методу простої ітерації можна записати:
де
На першій ітерації на основі початкового

наближення наступне знаходять за формулами:
У загальному вигляді, якщо знайдене k-е наближення то k +1 знаходять за формулами:
Збіжність забезпечується, якщо:

Слайд 28

де – матриця Якобі,
Одним із серйозних недоліків методу простих ітерацій

є складність вибору функцій які б задовольняли достатню умову збіжності.

Слайд 29

Узагальнений метод Ньютона:

Слайд 30

Слайд 31

Слайд 32

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

Содержание

МЕТОД ПРОСТОЇ ІТЕРАЦІЇПрипустимо, що і перетворимо систему до вигляду

x(k+1) = αx(k) + β, k=0,1,2…або у розгорнутому вигляді

ЗБІЖНІСТЬ МЕТОДУ ПРОСТОЇ ІТЕРАЦІЇДля збіжності процесу обчислень необхідно, щоб виконувалась умова||α||

ТеоремаЯкщо матриця α системи рівнянь x(k+1) = αx(k) + β задовольняє

ПОХИБКИ МЕТОДУ ПРОСТОЇ ІТЕРАЦІЇГлобальна похибка розв’язку на двох сусідніх ітераціях||x(k+1) –

МЕТОД ЯКОБІЗапишемо метод Якобі в матричній формі. Для цього запишемо матрицю

МЕТОД ЯКОБІЗапишемо СЛАР як: (L + D + U)x = bабоDx

МЕТОД ЯКОБІПри цьомуДля збіжності методу Якобі достатньо, щоб матриця α мала