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