ти значення x n = b n = (d n - a n b n-1 )/(b n + A n a n-1 ). p> Значення інших невідомих x i (i = n-1, n-2, ..., 1) легко обчислюються за формулою (9).
Таким чином, алгоритм прогонки, подібно методом Гаусса, включає два етапи - прямий хід (Пряма прогін) і зворотний хід (зворотна прогін). p> Прямий хід методу прогонки полягає в обчисленні прогоночние коефіцієнтів
a i (i =) і b i (i =). br/>
При i = 1 ці коефіцієнти обчислюються за формулами:
a 1 =-с 1 /G 1 ; b 1 =-d 1 /G 1 ; g 1 = b 1 . br/>
Для i = використовуються наступні рекурентні формули:
a i =-с i /g i ; b i = (d i - a i b i-1 )/g i ; g i = b i + a i a i-1 .
Пряма прогін завершується при i = n:
b n = (d n - a n b n-1 )/g n ; g n = b n + a n a n-1 .
Зворотний хід методу прогонки дозволяє обчислити значення невідомих. Спочатку вважають x n = b n . Потім у зворотному порядку за формулою (9) визначають значення невідомих x n -1 , x n -2 , .. ., x 1 .
Властивості методу прогонки. Трудомісткість методу прогонки оцінюється приблизно як 8n арифметичних операцій, що істотно менше методу Гаусса. Існування рішення системи (8) і його єдиність гарантуються при виконанні достатніх умов, що задаються наступною теоремою. p> Теорема [2]. Нехай коефіцієнти системи (8) задовольняють наступним нерівностям
ГЇb k ГЇ Ві ГЇa k ГЇ + ГЇc k ГЇ; ГЇb < sub> k ГЇ> ГЇa k ГЇ; k =, де a 1 = 0; b n = 0. Тоді g i В№ 0 і ГЇa i ГЇ ВЈ
1 для всіх i =
Зауважимо, що при всіх g i В№ 0 обчислення за формулами прямої прогонки можуть бути доведені до кінця (жоден з знаменників не вернувся в нуль). Одночасно всі коефіцієнти a i , такі, що ГЇa i ГЇ ВЈ 1, забезпечують стійкість за вхідними даними етапу зворотного прогонки за формулою (9). br/>
4. Обчислення визначників
Ідея послідовного виключення змінних, реалізована в методі Гаусса, може бути використана при обчисленні визначників. При цьому використовуються такі властивості визначників:
1) перестановка двох рядків або стовпців визначника не змінює його абсолютної величини, але змінює знак на протилежний;
2) множення всіх елементів одного рядка або одного стовпця на будь-яке число рівносильно множенню визначника на це число;
3) якщо до елементів деякою рядки (шпальти) визначника додати відповідні елементи іншого рядка (стовпця), помножені на будь загальний множник, то величина визначника не зміниться.
Нехай заданий визначник
В
Виберемо головний елемент a 11 В№ 0. Якщо a 11 = 0, то виконаємо перестановку двох рядків або стовпців цього визначника, щоб отримати a 11 В№ 0. p> Винесемо головний елемент a 11 з першого рядка за знак визначника
В
Використовуючи процедуру прямого ходу методу Гаусса, перетворимо отриманий визначник таким чином, щоб у першому стовпці під одиницею були б всі нулі. При цьому величина визначника не зміниться.
В
Розкладемо отриманий визначник за елементами першого стовпця, що дасть зниження його порядку визначника на одиницю
В
Повторимо зазначену процедуру (n - 1) раз і остаточно отримаємо
В
Якщо при обчисленні визначника проводилася перестановка рядків або стовпців (для вибору головного елемента), то
В
де s - кількість виконаних перестановок.
Таким чином, обчислення визначника detA деякої матриці A зводиться до виконання прямого ходу методу Гаусса. Абсолютна величина цього визначника дорівнює добутку головних елементів, k =, використовуваних на кожному кроці прямого ходу. Знак визначника залежить від числа перестановок рядків і стовпців, виконаних при виборі головних елементів.
Якщо такі перестановки не вироблялися, то величина визначника також може бути обчислена як твір діагональних елементів матриці L, що формується у процесі LU-розкладання вихідної матриці А
В
5. Обчислення зворотних матриць
Зворотну матрицю А -1 має будь-яка квадратна матриця А, для якої detA В№ 0. Нехай дана матриця А = [a ij ] n '...
