Метод найшвидшого спуску (градієнтний метод) для випадку системи лінійних рівнянь
Нехай потрібно знайти чисельний розв'язок системи лінійниз рівнянь використовуючи метод найшвидшого спуску (градієнтний метод). Для цього, систему (1) перепишемо у наступному вигляді:
або в матрично-векторній формі , де
— матриця коефіцієнтів при невідомих системи (1);
— вектор-стовпець вільних члені;
— вектор-стовпець невідомих.
Згідно методу найшвидшого спуску кожне наступне наближення до рішення системи рівнянь будемо шукати у наступному вигляді:
де — наближення отримане на k-й ітерації градієнтного методу;
— транспонована матриця Якобі;
— вектор нев'язок, який на кожній ітерації обчислюється за насутпною формулою
і параметр
визначаємо наступним чином:
Нагадаємо, що матриця Якобі вектор-функції — це матриця, яка склажається з частинних похідних цих функцій, тобто матриця насутпного виду:
Неважко переконатися, що для системи (3) матриця Якобі рівна:
Як і для методу простої ітерації, достатньою умовою збіжності методу градієнта є переважання діагональних елементів. В якості нульового наближення можна взяти .
Також відмітимо, що в формулі (6) використовується скалярний добуток двох векторів, який визначається за наступною формулою:
Зауваження: у методі найшвидшого спуску ітераційний процес, зазвичай, продовжується до тих пір, поки на деякому кроці модуль вектора нев'язок не стане меншим або рівним від деякого як завгодно малого додатного числа (
).
Знаходження розв'язку системи лінійних алгебраїчних рівнянь використовуючи метод найшвидшого спуску — приклад:
Використовуючи розглянутий алгоритм методу найшвидшого спуску, знайти, з точністю , розв'язок наступної системи лінійних алгебраїчних рівнянь:
Для цього, перепишемо задану систему у зручному для ітерації вигляду та виберемо вектор нульового (початкового) наближення:
На наступному кроці, обчисливши матрицю Якобі (збігається з матрицею коефіцієнтів заданої системи) і транспоновану до неї
, вектор нев'язок
та параметр
, переходимо до обчислення наступного наближення до шуканого розв'язку:
Далі, обчисливши елементи вектора нев'язок , провіримо виконання умови зупинки.
Виходячи з того, що для отриманого на першій ітерації наближення, умова зупинки не виконується, продовжуємо ітераційний процес далі і на п'ятій ітерації методу найшвидшого спуску отримуємо значення, для яких задану точність досягнуто і які приймаємо в якості шуканих коренів заданої системи.
Що таке differense(X, X0, eps, n) ?!?!?!
difference(X, X0, eps, n) — функція, яка відповідає за зупинку ітераційного процесу методу найшвидшого спуску.
Чи помилки точно ніде нема? Запрограмував цей алгоритм по блок-схемам, проте алгоритм не працює.
Виходячи з того, що по даних блок-схемах було реалізовано delphi-проект Використання методу найшвидшого спуску при знаходженні розв'язку СЛАР, який працює безпомилково, то алгоритм можна вважати працездатним.