УМОВИ ЗАСТОСУВАННЯ МЕТОДУ ГАУССА.
Раніш було показано, що метод Гаусса перетворює вихідну систему
рівнянь
(1)
до еквівалентної системи
, (2)
де С- верхня трикутна матриця з одиницями на головнїй діагоналі.
З’ясуємо тепер, як зв’язанi між собою вектори правих частин f та y.
Раніш ми переконалися, що праві частини системи (2) обчислюються
за формулами
,
З цих співвідношень можна послідовно одержати
, (3)
де -числові коефіцієнти, причому .
Співвідношення (3) можна записати у матричному вигляді
, (4)
де B -нижня трикутна матриця з елементами на головній діагоналі.
Нагадаємо, що головне припущення при формуліровці методу Гаусса
полягало у тому, що усі Тому на діагоналі матриці В стоять
ненульові елементи, , тобто В має обернену, a . Підставляючи
останнє у (2), приходимо до рівняння
звідки
. (5)
Порівнюючи (5) з рівнянням (1), приходимо до висновку, що як
наслідок застосування методу Гаусса одержане розкладання вихідної
матриці А у добуток A=BC , де В- нижня трикутна матриця з ненульовими
елементами на головній діагоналі, С-верхня трикутна матриця з
одиничною головною діагоналлю.
Зараз можно тлумачити метод Гаусса таким чином. Нехай задано
матрицю A і вектор f. Спочатку утворюється розклад А у добуток двох
трикутних матриць . Далі послідовно розв’язуються дві системи
рівнянь
(6)
(7)
з трикутними матрицями, звідки і одержується шуканий вектор x. Розклад
А=ВС відповідає прямій ході методу Гаусса, а розв’язання системи (6)-
(7)- зворотній ході. Зауважимо, що у наведеному раніш алгоритмі
розклад A=BC та розв’язання системи (6) провадиться одночасно.
Водночас з сказаного можна зробити наступний висновок. Тому що
,
то метод Гаусса дозволяє одночасно з ров’язаннням системи (1)
обчислити визначник матриці А простим множенням ведучих елементів.
Коли ж задачею є просто обчислення визначника матриці, то це можна
зробити методом Гаусса, при цьому немає необхідності обчислювати праві
частини перетворюємих рівнянь.
Далі, додержуючись стандартних позначень, нижні трикутні матриці
будемо позначати L (від англійського lower- нижній), та верхні
трикутні - літерою U (від англійського upper-верхній).
Позначимо через -кутовий мінор порядку j матриці А, тобто
.
Теоретичне обгрунтування можливості розкладу матриці у добуток
двох трикутних матриць містить наступна теорема.
Теорема про LU- розклад. Нехай усі кутові мінори матриці А
відмінні від нуля, . Тоді матрицю А можна подати єдиним чином у
вигляді добутка
А=LU ,
(8)
де L- нижня трикутна матриця з ненульовими діагональними елементами і
U -верхня трикутна матриця з одиничною головною діагоналлю.
Доведення. Доведемо сформульоване твердження спочатку для
матриць другого порядку. Будемо шукати розклад матриці
у вигляді
,
де - невідомі досі числа. Для відшукання цих чисел маємо систему
рівнянь:
,
яка має єдиний розвязок
.
За припущенням теореми , тобто елементи та
відмінні від нуля.
Подальше доведення проведемо методом математичної індукції.
Нехай твердження вірне для матриць порядку доведемо, що воно
вірне і для матриць порядку к.
Подамо матрицю А порядку К у вигляді
(9)
та позначимо
; ,
.
Згідно з умовами теореми і тоді за припущеннями індукції існує
розклад матриці ;
де -відповідно нижня і верхня трикутні матриці, що володіють
вказаними у теоремі властивостями. Будемо шукати розклад матриці (9)
у вигляді
, (10)
де - невідомі досі вектори.
Помножимо матриці в правій частині рівняння (10) і, враховуючи
(9), приходимо до системи рівнянь
; (11)
; (12)
; (13)
З припущенння індукції виходить існування матриць ;.
Тому з (11) і (12) одержуємо
;
і,далі, з (13)
.
Таким чином,-розклад матриці А існує. З розкладу (10) виходить,
що
.
За умовами теореми , а за припущеннями індукції , і тому
. Тим самим індукція завершена і доведена можливість шуканого
розкладу.
Доведемо тепер, що такий розклад єдиний. Припустимо, що матрицю
А можна розкласти двома способами
.
Тоді i . (14)
Матриця у лівій частині рівняння (14) є верхньою трикутною, а в
правій частині - нижньою трикутною. Така рівність можлива лише у
випадку. якщо матриці і діагональні. Але на діагоналі
матриці (а тому і матриці ) стоять одиниці, отже ці матриці
одиничні
.
Звідси одержуємо ; ,тобто розклад (8) єдиний. Теорема
повністю доведена.
Зауважимо, що коли хоча б один з углових мінорів матриці А
дорівнював нулеві, то вказаний - розклад неможливий. Це легко
побачити на прикладі матриць другого порядку.
Висновок. Метод Гаусса можливо використовувати тоді, та й лише
тоді, коли усі кутові мінори матриці А відмінні від нуля.
Було показано, що метод Гаусса приводить до розкладу вихідної
матриці у добуток двох трикутних. Більш детально описати структуру цих
трикутних матриць можливо за допомогою так званих елементарних
трикутних матриць.
Матриця називається елементарною нижньою трикутною
матрицею, якщо вона має вигляд
.
У матриці усі елементи головної діагоналі окрім
дорівнюють одиниці. З решти елементів відмінними від нуля можуть
бути лише елементи -го стовпчика, що розташовані нижче .
Оберненою до є елементарна нижня трикутна матриця
.
Розглянемо спочатку для наочності систему , що складається
з трьох рівнянь:
,
, (15)
.
Після першого кроку виключення за методом Гаусса перетворена
система приймає вигляд
,
, (16)
.
Звідси видно, що матриця системи (16) одержується з
вихідної матриці А шляхом множення А зліва на елементарну матрицю
(17)
так, що .При цьому систему (16) можна записати у вигляді
.
Матрицю (17) будемо називати елементарною трикутною матрицею, що
відповідає першому кроку виключення методу Гаусса.
Перепишемо систему (16) у вигляді
,
, (18)
.
Здійснимо другий крок методу Гаусса, тобто виключимо невідому з
останнього рівняння.
Тоді одержимо систему вигляду
,
, (19)
.
Можна переконатися,що перехід від (18) до (19) здійснюється завдяки
множення системи (18) на елементарну трикутну матрицю
. (20)
Таким чином,після другого кроку виключення приходимо до системи
, (21)
де матриці і означені згідно (17), (20).
Нарешті, перемножаючи (21) на матрицю
одержимо систему
, (22)
матриця якої є верхньою трикутною матрицею з одиничною головною
діагоналлю.
Звідки виходить, зокрема, що A=LU, де -нижня трикутна
матриця.
Таким чином, -розклад матриці А може бути одержаний за
допомогою елементарних трикутних матриць: спочатку будуються матриці
та обчислюється , а потім відшукується .Відзначимо, що
матриці мають простий вигляд
; ; ;
.
причому на діагоналі матриці містяться ведучі елементи методу
виключення.
Запис методу Гаусса у вигляді (22) детально описує процес
виключення.
Усе згадане раніш переноситься без винятку на системи рівнянь
довільного порядку (2).
Процес виключення можна записати формулою
, (23)
де елементарна нижня трикутна матриця на к-му кроці виключення
має вигляд
.
Матриця здійснює виключення невідомого з рівнянь з
номерами к+1, к+2, ... ,m.
Матриці існують і мають вигляд
.
1 2 3 4 5 6 7 8 9 10 11 12 13 14
