Додаткові застосування методу Гауса

 

Виконання прямого ходу методу Гауса дозволяє також обчислити значення визначника матриці системи.

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

.

Метод Гауса може бути використаний для отримання оберненої матриці. Позначимо її елементи через a_jm. Тоді співвідношення AA^-1=E можна записати так:

.

Якщо розглядати j -й стовпець оберненої матриці як вектор, то він є розв’язком лінійної системи вигляду (3.1) з матрицею A і спеціальною правою частиною (у якій на j -му місці стоїть одиниця, а на інших нулі). Таким чином, для обертання матриці треба розв’язати n систем лінійних рівнянь з однаковою матрицею A і різними правими частинами. Зведення матриці A до трикутної виконується при цьому тільки один раз, а праві частини перетворюються за формулами (3.6)-(3.7).

Перетворення матриці вимагає порядку  операцій. Дії з перетворення правих частин систем і зворотний хід методу Гауса повторюються 7n разів, а однократне перетворення правих частин і зворотний хід вимагають порядку  операцій. Отже, сумарні обчислювальні витрати на пошук оберненої матриці становлять: .

Обертання матриці зводиться до розв’язання n систем лінійних рівнянь, але вимагає лише приблизно втроє більше дій, ніж розв’язання однієї системи рівнянь. Це обумовлюється тим, що при розв’язку лінійної системи велика частина обчислень пов'язана з приведенням матриці до трикутного вигляду, а це при обертанні матриці робиться тільки один раз. Зворотний хід і перетворення правих частин виконуються набагато швидше.

 

Метод Краута

Суть методу Краута, або LU -розкладання, полягає в тому, що це своєрідний перезапис методу Гауса. Він дозволяє зробити зручною комп’ютерну реалізацію методу Гауса. Можна явно виділити два етапи, у яких один робить перетворення з матрицею А системи, інший – з вектором правих частин b. Отже, нехай дана СЛАР Ax = b, наприклад, система розміром 4 ´ 4. Запишемо розширену матрицю системи

Тоді, за Гаусом можна явно виділити два етапи (тобто два кроки) – прямий хід (ПХ) і зворотний (ЗХ):

1) ПХ:

2)    ЗХ:

На прямому ході ми робимо так звані “виключення”, тобто приводимо матрицю до трикутного вигляду. Тепер легко знайти x₄, а потім і x₃ і т.д. Це був зворотний хід методу Гауса. Всі ці перетворення виконувалися не із самою матрицею, а з розширеною матрицею.

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

Розглянемо  -ий крок методу Гауса, на якому здійснюється занулення піддіагональних елементів -го стовпчика матриці . Як було зазначено раніше, з цією метою використовується операція

У термінах матричних операцій така операція еквівалентна множенню , де елементи матриці  визначаються таким чином:

тобто матриця  має

вигляд .

При цьому вираз для зворотної операції запишеться у вигляді , де

.

У результаті прямого ходу методу Гауса отримаємо

де - верхня трикутна матриця, а  - нижня трикутна матриця, що має вигляд

.

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

Запишемо A × x = b, як

L × U × x = b.

Позначимо

U × x = y.

І, отже,                     L × y= b.

Таким чином, прямий хід методу LU -декомпозицiї складається з розкладу матриці A на нижню L та верхню U трикутні матриці – це прямий хiд.

Потiм визначається вектор y на основі співвідношень: , .

На зворотному ході методу LU -декомпозицiї розв’язується рівняння U × x = y. З урахуванням того, що U – трикутна матриця,

, .

Отже, LU -розкладання є просто свого роду іншою формою запису еквівалентних перетворень матриці за методом Гауса, але проведених з урахуванням умови А = L × U.

Теорема 1. Для існування LU -розкладання матриці А необхідно й достатньо, щоб у матриці А всі головні мінори були відмінні від нуля.

У довільної невиродженої матриці А головні мінори, тобто , , …, , можуть дорівнювати нулю. Тоді необхідно переставити рядки так, щоб головні мінори стали відмінними від нуля.

Звичайно перестановка рядків не проводиться окремо від процедури вилучення, ці два процеси поєднуються в один. Якщо a ₁₁ = 0, переставимо рядки матриці А так, щоб у лівому верхньому куті виявився ненульовий елемент. У першому стовпці такий елемент завжди знайдеться, інакше detА = 0. Якщо після першого кроку дістанемо a₂₂⁽¹⁾ = 0, то виконаємо, як і вище, переставлення: у другому стовпці завжди знайдеться ненульовий елемент, інакше два перші стовпці були б лінійно залежні і det А = 0. Помістимо рядок з ненульовим елементом у другому стовпці на місце другого рядка, тоді a ₂₂ ⁽¹⁾ ≠ 0. Продовжуючи цей процес вилучення й перестановки рядків (якщо елемент a _kk ^(k-1) =0) до k = n, дістанемо LU -розкладання матриці А з додатковою матрицею Р перестановок рядків

PA = LU.

Матриця Р одержується з одиничної матриці Е перестановкою тих самих рядків. Наприклад, перестановці другого та четвертого рядків матриці відповідає

P =

Таким чином, ми отримали LUP-розкладання.

Приклад. Розв'яжемо СЛАР за схемою LU -розкладання: 

Виконаємо дії за алгоритмом і отримаємо матриці L та U у вигляді:

L = , U = .

Спочатку знаходимо розв’язок системи

.

Отримаємо: g = {1, 0, 4}.

Тепер реалізуємо зворотний хід методу Гауса, розв’язуючи систему :

.

Отже, остаточна відповідь: x ₁ = 4, x ₂ = 4, x ₃ = -3.

Метод прогонки

 

Це - ще одна модифікація методу Гауса для систем лінійних алгебраїчних рівнянь спеціального вигляду. Нехай потрібно знайти розв’язок системи так званих триточкових рівнянь:

с₀у₀-b₀y₁=f₀,     i=0;

-a_iy_i-1+c_iy_i-b_iy_i+1=f_i, 1 £ i £ N-1;                 (3.8)

-a_Ny_N-1+c_Ny_N=f_N, i=N.

Такі системи виникають як результат апроксимації крайових задач для звичайних диференціальних рівнянь другого порядку, а також при реалізації різницевих схем для рівнянь у часткових похідних.

Переходимо до побудови алгоритму розв’язування системи (3.8). На першому кроці з усіх рівнянь системи (3.8) для i=1,2,...,N виключається за допомогою першого рівняння (3.8) невідоме у₀, потім з перетворених рівнянь для i=2,3,...,N за допомогою рівняння, що відповідає i=1, виключається невідоме у₁ і т.д. У результаті одержимо одне рівняння відносно у _N. На цьому прямий хід методу закінчується. На зворотному  ході для     i=N-1,N-2,...,0 знаходиться у_i через уже знайдені у_i+1, y_i+2,..., y _N і перетворені праві частини.

Використовуючи підходи методу Гауса, проведемо виключення невідомих з (3.8). Позначивши a ₁ =b₀/c_0, b ₁ =f₀/c₀, запишемо (3.8):

y₀- a ₁ y₁= b ₁,                i=0;

-a_iy_i-1+c_iy_i-b_iy_i+1=f_i,           1 £ i £ N-1;       (3.9)

-a_Ny_N-1+c_Ny_N=f_N,               i=N.

Візьмемо перші два рівняння системи (3.9)

y₀- a ₁ y₁= b ₁,            -a_iy_i-1+c_iy_i-b_iy_i+1=f_i.

Помножимо перше рівняння на a₁ і додамо до другого рівнянням. Будемо мати (c₁-a₁ a ₁₎ y₁-b₁y₂=f₁+a₁ b _{1 ,} або після ділення на c₁-a₁ a ₁

у₁- a ₂ у₂= b ₂, a ₂ =  , b ₂ = .

Усі інші рівняння системи (3.9) у₀ не містять, тому на цьому перший крок процесу виключення закінчується. В результаті одержимо нову “скорочену” систему

y₁- a ₂ y₂= b ₂,                  i=1;

-a_iy_i-1+c_iy_i-b_iy_i+1=f_i, 2 £ i £ N-1;                (3.10)

-a_Ny_N-1+c_Ny_N=f_N,               i=N,

яка не містить невідоме у₀  і має аналогічну (3.9) структуру. Якщо ця система буде розв’язана, то невідоме у₀ знайдеться із рівняння y₀- a ₁ y₁= b ₁. До системи (3.10) можна знову застосувати описаний спосіб виключення невідомих. На другому кроці буде виключене невідоме у₁, на третьому – у₂ і т.д. У результаті l -го кроку одержимо систему для невідомих у_l, y_l+1,..., y_N  

y_l- a _l+1 y_l+1= b _l+1,            i=l;

-a_iy_i-1+c_iy_i-b_iy_i+1=f_i, l+1 £ i £ N-1;               (3.11)

-a_Ny_N-1+ c_Ny_N = f_N,           i=N.

і формули для знаходження у_i з номерами i £ l-1

у_i= a _i+1 у_i+1+ b _i+1, i=l-1, l-2,..., 0. (3.12)

Коефіцієнти a _i і b _i знаходяться за формулами

a _i+1 = , b _i+1 = , i=1,2,...,

a ₁ = , b ₁ =  .

Вважаючи в (3.12) l= N-1, одержимо систему рівнянь для y _N і y_N-1

              y_{N -1} -a_N у _N = b _N,

          -a_Ny_N-1+ c_Ny_N = f_N,

з якої знайдемо у _N = b _N+1, y_{N -1} = a _N у+ b _N.

Таким чином, одержимо остаточні формули для знаходження невідомих

        у_i= a _i+1 у_i+1+ b _i+1, i=N-1, N-2,..., 0,

у _N = b _N+1,                                          (3.13)

де коефіцієнти знаходяться за рекурентними співвідношеннями:

a _i+1 =  , i=1, 2, …, N-1, a ₁ =    (3.14)

b _i+1 =  , i=1, 2,..., N-1;  b ₁ =   (3.15)

Отже, формули (3.13)-(3.15) описують метод Гауса, що у застосуванні до системи (3.8) одержав спеціальну назву - метод прогонки. Коефіцієнти a _i і b _i називаються прогонковими коефіцієнтами, формули (3.14), (3.15) описують прямий хід прогонки, а (3.13) - зворотний хід. Оскільки значення у_i  знаходяться тут послідовно при переході від i+1 до i, то формули (3.13)-(3.15) називають іноді правою прогонкою.

Метод зустрічних прогонок. Аналогічно до правої виводяться формули лівої прогонки:

x _i = , i=N-1, N-2,..., 1;        (3.16)

h _i = , i=N-1, N-2,..., 0; , (3.17)

y_i+1= x _i+1 у_i+ h _i+1, i=0, 1,..., N-1;    . (3.18)

Тут значення у_i знаходяться послідовно при зростанні індексу i (зліва направо).

Іноді виявляється зручним комбінувати праву і ліву прогонки, одержуючи так званий метод зустрічних прогонок. Цей метод доцільно застосовувати, якщо треба знайти тільки одне невідоме, наприклад y_m (0 £ m £ N), або групу невідомих. Одержимо формули методу зустрічних прогонок. Нехай 1 £ m £ N і за формулами (3.14)-(3.17) знайдені a ₁, a ₂,..., a _m, b ₁, b ₂,..., b _m, і x _N, x _N-1,..., x _m, h _N, h _N-1,..., h _m. Випишемо формули (3.13), (3.18) для зворотного ходу правої і лівої прогонок для i=m-1. Будемо мати систему, з якої знайдемо y_m

y_m =  .

Використовуючи знайдене y_m, за формулами (3.13) для i=m-1, m-2,..., 0 знайдемо послідовно y_m-1, y_m-1,..., y₀, а за формулами (3.18) для i=m, m+1,...,N обчислимо інші y_m+1, y_m+2,...,y _N.

Отже, формули методу зустрічних прогонок мають вигляд:

  a_i+1= ,   i=1, 2,..., m-1,  a ₁ = ,   

  b _i+1 = ,   i=1, 2,..., m-1,   b ₁ = ,

x _i = ,  i=N-1, N-2,..., m, , (3.19)

h _i = ,  i=N-1, N-2,..., m, ,

для обчислення прогонкових коефіцієнтів і

       у_i= a _i+1 у_i+1+ b _i+1,  i=m-1, m-2,..., 0;

       у_i+1= x _i+1 у_i+ h _i+1,   i=m,m+1,..., N-1;                (3.20)

y_m=

для визначення розв’язків.