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

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

Розв'язок СЛАР методом найшвидшого спуску

або в матрично-векторній формі Розв'язок СЛАР методом найшвидшого спуску, де metod_najshvudshogo_spysky_slar4 — матриця коефіцієнтів при невідомих системи (1); Розв'язок СЛАР методом найшвидшого спуску — вектор-стовпець вільних члені; metod_najshvudshogo_spysky_slar6 — вектор-стовпець невідомих.

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

metod_najshvudshogo_spysky_slar7

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

metod_najshvudshogo_spysky_slar13

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

metod_najshvudshogo_spysky_slar16

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

metod_najshvudshogo_spysky_slar17

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

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

metod_najshvudshogo_spysky_slar191

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

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

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

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

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

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

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

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

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

Матеріал був корисним, поділись в соціальних мережах:

Коментарі

4 коментаря по темі “Метод найшвидшого спуску (градієнтний метод) для випадку системи лінійних рівнянь”
  1. Олександр пише:

    Що таке differense(X, X0, eps, n) ?!?!?!

  2. admin пише:

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

  3. Олександр пише:

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

  4. admin пише:

    Виходячи з того, що по даних блок-схемах було реалізовано delphi-проект Використання методу найшвидшого спуску при знаходженні розв'язку СЛАР, який працює безпомилково, то алгоритм можна вважати працездатним.

Якщо тобі сподобалась дана тема, залиш свій коментар