Релаксаційні методи

Матеріал із MachineLearning.

Релаксаційні методи- окремий випадок ітераційних методів рішення СЛАУ. Ітераційні методи є особливо ефективними при вирішенні систем з великою кількістю невідомих (близько 1000 і більше).

Зміст

У випадку спочатку задається деякий вектор x 0 , званий початковим наближенням. У випадку початкове наближення може бути будь-яким. Від нього будується послідовність x1, x2. x k тощо, де число k називають номером ітерації. Ітераційний метод називається однокроковим, якщо кожне наступне ітераційне наближення будується лише по одному попередньому:

Якщо – лінійна функція, то відповідний ітераційний метод називається лінійним. Відповідно до визначення, можна отримати канонічну форму запису однокрокового ітераційного методу:

Якщо , то відповідний метод називається явним, інакше – неявним.

Виклад методу

Релаксаційні методи є стаціонарними та неявними рішеннями СЛАУ. Нехай нам потрібно вирішити систему лінійних рівнянь алгебри:

Представимо матрицю як суми трьох матриць , і :

Де - нижньотрикутна, - верхньотрикутна, - діагональна

Канонічна форма релаксаційного методу записується так

Де - якийсь числовий параметр.

Метод Зейделя

Канонічний вид методу Зейделя:

Перетворивши ці уранення наведемо їх до наступного виду:

Звідси отримана система виглядатиме так:

Висловимо із цієї системи нове ітераційне наближення:

Таким чином, -я компонента -го наближення обчислюється за формулою:

Умова збіжності та оцінка похибки методу

Має місце така теорема. Нехай

де -симетрична позитивно визначена матриця та . Тоді метод релаксації є схожим на будь-яке початкове наближення.

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

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

Реалізація методів

Метод Зейделя

Функція мовою Сі, яка вважає наступну ітерацію методом Зейделя:

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

Функція мовою Сі, що вважає наступну ітерацію методом Релаксації:

Приклади роботи

Наприклад розглянемо систему:

Точне рішення очевидно: (1, 2).

Тестування проводилося за

, початкове наближення (0, 0). Умова зупинки - поелементна різниця елементів наступного наближення та попереднього не більше, ніж.

Метод Зейделя

Рішення: (1.00274, 1.99909) отримано за 6 ітерацій

Метод релаксації (ω=0.5)

Рішення: (1.002673, 1.98664) отримано за 14 ітерацій

Метод релаксації (ω=1.5)

Рішення: (0.995275, 1.99967) отримано за 9 ітерацій

---