Розв'язок систем з трьохдіагональною матрицею (реалізація в середовищі Delphi)

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

Для рішення систем з подібними матрицями існує модифікація алгоритму Гаусса, яку називають методом прогонки. Перевагою даного способу є той факт, що для знаходження коренів системи  рівняння він вимагає порядку операцій, на відміну від стандартного алгоритму. Спробуємо коротко розібрати основну суть методу прогонки після чого розглянемо відповідну delphi-програму, яка, напевно, виявиться корисною для читача, що зіткнувся з необхідністю рішення систем з трьохдіагональною матрицею.

Отже, будь-яке рішення, отримане методом прогонки, описується рівнянням:

де  — прогоночні коефіцієнти. Зазначимо, що дані коефіцієнти визначаються на першому етапі роботи алгоритму — називається прямим ходом прогонки. У класичному варіанті методу Гаусса, цьому етапу відповідає приведення матриці до трикутного вигляду. Звернемо увагу, що, відповідно до рівняння, попередній корінь обчислюється виходячи з наступного. Така послідовність називається зворотним ходом алгоритму прогонки, в процесі якого безпосередньо шукається вектор рішень. Описані дії представлені нижче у вигляді delphi-програми.

Читати повністю

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

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

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

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

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

Читати повністю