Метод найшвидшого спуску (градієнтний метод) для випадку системи лінійних рівнянь

Нехай потрібно знайти чисельний розв’язок системи рівнянь використовуючи метод найшвидшого спуску (градієнтний метод). Для цього, систему (1) перепишемо у наступному вигляді:

або в матрично-векторній формі , де – матриця коефіцієнтів при невідомих системи (1); – вектор-стовпець вільних члені; – вектор-стовпець невідомих.

Тоді, згідно з методом найшвидшого спуску, кожне наступне наближення до рішення системи рівнянь будемо шукати у наступному вигляді:

де – наближення отримане на k-й ітерації градієнтного методу; – транспонована матриця Якобі;  – вектор нев’язок, який на кожній ітерації обчислюється за формулою і параметр визначається наступним чином:

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

Неважко переконатися, що для системи (3) матриця Якобі рівна:

Як і для методу простої ітерації, достатньою умовою збіжності градієнтного методу є переважання діагональних елементів. В якості нульового наближення можна взяти .

Також відмітимо, що у формулі (6) використовується скалярний добуток двох векторів, який визначається за наступною формулою:

Зауваження: у методі найшвидшого спуску ітераційний процес, зазвичай, продовжується до тих пір, поки на деякому кроці модуль вектора нев’язок не стане меншим або рівним від деякого як завгодно малого додатного числа ().

Розв’язок системи рівнянь використовуючи метод найшвидшого спуску – приклад:

Використовуючи розглянутий вище градієнтний метод, з точністю розв’язати систему рівнянь наступного вигляду:

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

На наступному кроці, обчисливши матрицю Якобі (збігається з матрицею коефіцієнтів заданої системи) і транспоновану до неї , вектор нев’язок та параметр , переходимо до обчислення наступного наближення до шуканого розв’язку:

Далі, обчисливши елементи вектора нев’язок , перевіримо виконання умови зупинки:

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

Блок-схема алгоритму знаходження розв’язку системи лінійних рівнянь використовуючи метод найшвидшого спуску

Метод шайшвидшого спуску блок-схема

4 коментаря

  1. difference(X, X0, eps, n) – функція, яка відповідає за зупинку ітераційного процесу методу найшвидшого спуску.

  2. Чи помилки точно ніде нема? Запрограмував цей алгоритм по блок-схемам, проте алгоритм не працює.

Залишити коментар

Your email address will not be published. Required fields are marked *

*