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

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

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

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

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

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

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

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

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

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

Знаходження розв'язку системи лінійних алгебраїчних рівнянь використовуючи метод найшвидшого спуску — приклад:

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

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

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

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

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

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