ерестановка рядків не впливає на рішення, тому що відповідає перестановці місцями рівнянь в системі, але перестановка стовпців означає зміну нумерації змінних. Тому інформація про всі переставляються стовпцях повинна зберігатися, щоб після завершення зворотного ходу можна було б відновити вихідну нумерацію змінних.
Існують дві більш прості модифікації методу Гаусса:
- з вибором головного елемента за стовпцем;
- з вибором головного елемента по рядку.
У першому випадку в як головний елемент вибирається найбільший за абсолютною величиною елемент k-го рядка (серед елементів, i =). У другому - найбільший за абсолютною величиною елемент k-го шпальти (серед елементів, i =). Найбільшого поширення отримала перший підхід, оскільки тут не змінюється нумерація змінних.
Слід зауважити, що зазначені модифікації стосуються тільки прямого ходу методу Гаусса. Зворотний хід виконується без змін, але після отримання рішення може знадобитися відновити вихідну нумерацію змінних.
LU-розкладання. У сучасному математичному забезпеченні ЕОМ метод Гауса реалізується з використанням LU-розкладання, під яким розуміють уявлення матриці коефіцієнтів A у вигляді добутку A = LU двох матриць L і U, де L - нижня трикутна матриця, U - верхня трикутна матриця
В
Якщо LU-розкладання отримано, то рішення вихідної системи рівнянь (2) зводиться до послідовного розв'язування двох наступних систем рівнянь з трикутними матрицями коефіцієнтів
LY = B; (6)
UX = Y (7)
лінійний алгебраїчний рівняння чисельний
де Y = - вектор допоміжних змінних.
Такий підхід дозволяє багаторазово розв'язувати системи лінійних рівнянь з різними правими частинами B. При цьому найбільш трудомістка частина (LU-розкладання матриці A) виконується тільки один раз. Ця процедура відповідає прямому ходу методу Гауса і має оцінку трудомісткості O (n 3 ). Подальше рішення систем рівнянь (6) і (7) може виконуватися багаторазово (для різних B), причому рішення кожної з них відповідає зворотному ходу методу Гауса і має оцінку обчислювальної складності O (n 2 ). p> Для отримання LU-розкладання можна скористатися наступним алгоритмом. p> 1. Для вихідної системи (1) виконати прямий хід методу Гауса і отримати систему рівнянь трикутного вигляду (5).
2. Визначити елементи матриці U за правилом
u ij = C ij (I =; j =)
3. Обчислити елементи матриці L за правилами
В
Розрахункові формули для рішення системи (6) мають наступний вигляд:
y 1 = b 1 /L 11 ;
В
Розрахункові формули для рішення системи (7)
x n = y n ;
(i = n - 1, n - 2, ..., 1).
3. Метод прогонки
Метод прогонки являє собою простий і ефективний алгоритм розв'язання систем лінійних алгебраїчних рівнянь з трехдіагональной матрицями коефіцієнтів наступного виду
(8)
Системи такого виду часто виникають при вирішенні різних інженерних завдань, наприклад, при інтерполяції функцій сплайнами.
Перетворимо першу рівняння системи (8) до виду x 1 = a 1 x 2 + b 1 , де
a 1 =-с 1 /B 1 і b 1 =-d 1 /B 1 . Підставимо отримане для x 1 вислів на друге рівняння системи (8)
a 2 (a 1 x 2 + B 1 ) + b 2 x 2 + C 2 x 3 = d 2 . br/>
Уявімо це рівняння у вигляді x 2 = a 2 x 3 + b 2 , де a 2 =-с 2 /(b 2 + a 2 a 1 ) і b 2 = (d 2 - a 2 b 1 )/(b 2 + A 2 a 1 ). Отримане для x 2 вираз підставимо в третє рівняння системи (8) і т.д.
На i-му кроці (1
x i = A i x i +1 + b i , (9)
де a i =-с i /(b i + a i a i -1 ) і b i = (d i - a i b i-1 ) /(b i + a i a i-1 ).
На останньому n-му кроці підстановка в останнє рівняння системи (8) вираження x n -1 = a n -1 x n + b n -1 дає рівняння a n (a n -1 x n + b n -1 ) + b n x n = d n , з якого можна визначи...
