Метод прогонки. Розв’язок систем лінійних алгебраїчних рівнянь методом прогонки

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

Нехай дано систему лінійних рівнянь з тридіагональною матрицею:

Запишемо систему (1) у матрично-векторній формі , де

При цьому, як правило, всі елементи відмінні від нуля.

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

З першого рівняння системи (1)  знайдемо:

З іншої строни, використовуючи формулу (3) бачимо, що .  Прирівнюючи коефіцієнти в обох виразах для отримаємо:

Підставимо в друге рівняння системи замість  значення , отримаємо:

і звідси знаходимо :

або , де

Аналогічно можна знайти коефіцієнти для будь-якого :

Обернена прогонка полягає у послідовному обчисленні невідомих . Для цього спочатку, з останнього рівняння системи, знаходимо :

Підставимо в останній вираз замість значення отримаємо:

Далі, використовуючи формулу (1) і вирази для прогоночних коефіцієнтів (4) і (5), послідовно знаходимо всі невідомі .

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

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

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

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

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