Метод прогону .
Більшість технічних задач зводиться до розв’язування систем ЛАР, в яких матриці містять багато нульових елементів, а ненульові елементи розміщені за спеціальною структурою (стрічкові квазітрикутні матриці).
Задачі побудови інтерполяційних сплайнів, різницевих методів розв’язування крайових задач для диференціальних рівнянь зводяться до розв’язування систем ЛАР з трьохдіагональною матрицею А. В матриці А всі елементи, що не лежать на головній діагоналі і двох сусідніх паралельних діагоналях, дорівнюють нулю.
В загальному вигляді такі системи записують так:
аіхі-1 + bixi + cixi+1 = di (1)
1 ? i ? n ; a1 = 0 ; cn = 0
або в розгорнутому вигляді:
b1x1 + c1x2 = d1
a2x1 + b2x2 + c2x3 = d2
a3x2 + b3x3 + c3x4 = d3
• • • • • • • • • • • • • • • • • • • • (2)
aixi-1 + bixi + cixi+1 = di
an-1xn-2 + bn-1xn-1 + cn-1xn = dn-1
anxn-1 + bnxn = dn
Вибір найбільшого елемента при виключенні невідомих за методом Гауса в таких системах робити не можна, оскільки перестановка рядків руйнує структуру матриці. Найчастіше для розв’язку системи з трьохдіагональною матрицею використовують метод прогону, який є частковим випадком методу Гауса.
Прямий хід прогону (алгоритм прямого ходу методу Гауса).
Кожне невідоме хі виражається через хі+1 з допомогою прогоночних коефіцієнтів Аі та Ві
хі = Аіхі+1 + Ві ; EMBED Equation.3 (3)
Наприклад, з першого рівняння системи (2) знайдемо
EMBED Equation.3 , звідки EMBED Equation.3 (4)
З другого рівняння системи (3) виразимо х2 через х3, замінюючи х1 формулою (3) або (4)
a2х1 + b2x2 + c2x3 = a2(A1x2 + B1) + b2x2 = d2
Звідси знайдемо
EMBED Equation.3 або х2 = А2х3 + В2
EMBED Equation.3 EMBED Equation.3 , беручи за е2 = а2А1 + b2
Запишемо:
EMBED Equation.3 EMBED Equation.3
Аналогічно для кожного і прогоночні коефіцієнти з рівняння хі = Аіхі+1 + Ві мають вигляд:
EMBED Equation.3 EMBED Equation.3 (5)
еі = аіАі-1 + bі ; EMBED Equation.3
При цьому враховуючи, що а1 = сn = 0 приймаємо
Ао = 0 ; Во = 0. (6)
В розгорнутому вигляді формула (5) буде мати вигляд формули (7). Значення прогоночних коефіцієнтів можна одержати і таким шляхом. В рівнянні (3) понизимо індекс на одиницю та підставимо значення хі-1 в і-е рівняння системи (1)
хі-1 = Аі-1хі + Ві-1
аіхі-1 + bixi + cixi+1 = di EMBED Equation.3 ai(Ai-1xi + Bi-1) + bixi + cixi+1 = di
EMBED Equation.3 (7)
Обернений хід прогонки (аналог оберненого ходу методу Гауса).
Він полягає в послідовному обчисленні невідомих хі. Спочатку знаходять хn. Для цього формулу (7) запишемо при і = n (враховуючи, що Сп = 0)
EMBED Equation.3
Долі використовуючи формулу (3) знаходимо послідовно всі невідомі xn-1, xn-2, … , x1.
Майже у всіх задачах, що приводять до розв’язку системи (2) з трьохдіаго-нальною матрицею, забезпечується умова переважання діагональних коефіцієнтів
EMBED Equation.3
Це забезпечує існування єдиного розв’язку та достатню стійкість методу прогону відносно похибок заокруглення.
Для запису коефіцієнтів ai, bi, та прогоночних коефіцієнтів Аi-1, Ві-1 використати один і той же масив.