Умови застосування методу Гауса

Раніш було показано, що метод Гаусса перетворює вихідну систему рівнянь

(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) на матрицю

одержимо систему

L₃L₂L₁Ax = L₃L₂L₁f (22)

матриця якої U = L₃L₂L₁A є верхньою трикутною матрицею з одиничною головною діагоналлю.

Звідки виходить, зокрема, що A=LU, де L = L₃^-1L₂^-1L₁^-1 - нижня трикутна матриця.

Таким чином, LU -розклад матриці А може бути одержаний за допомогою елементарних трикутних матриць: спочатку будуються матриці L_1, L_2, L₃ та обчислюється U = L₃L, а потім відшукується L = L₁^-1L₂^-1L₃^-1.Відзначимо, що матриці L_k^-1 мають простий вигляд

; ; ;

.

причому на діагоналі матриці містяться ведучі елементи методу виключення.

Запис методу Гауса у вигляді (22) детально описує процес виключення.

Усе згадане раніш переноситься на системи рівнянь довільного порядку (2).

Процес виключення можна записати формулою

, (23)

де елементарна нижня трикутна матриця на к -му кроці виключення має вигляд

.

Матриця здійснює виключення невідомого з рівнянь з номерами к+1, к+2,...,m.

Матриці існують і мають вигляд

.

Лекція 10 ІТЕРАЦІЙНІ МЕТОДИ РОЗВ’ЯЗАННЯ

СИСТЕМ ЛІНІЙНИХ АЛГЕБРАЇЧНИХ РІВНЯНЬ.

Розглядається система лінійних алгебраїчних рівнянь

(1)

де - квадратна матриця вимірності

- вектор - стовпець правих частин системи;

- вектор - стовпець невідомих.

Ідея найпростіших ітераційних методів розв’язання системи (1) полягає у наступному. За допомогою еквівалентних перетво-рень система (1) зводиться до системи вигляду

(2)

де -квадратна матріця

-відомий вектор.

А потім задається деяке початкове наближення (наприклад, у якості першого наближення береться вектор , або деякий розв’язок системи (1), який одержується іншим методом з деякою похибкою). Інші наближення послідовно знаходяться за рекурентною формулою

(3)

доки на деякому кроці не буде досягнута задана точність

обчислення значення невідомого вектору .

Виникає питання, за яких умов на послідовність

збігається (у певному розумінні) до точного розв’язку .

Не зупиняючись на подробицях (дивись спецкурс ‘Додат-кові розділи чисельного аналізу’), дамо деякі достатні умови, за яких

або

або

Швидкість збіжності оцінюється нерівністю

де - відстань між векторами та , що може бути заданою:

коли виконується умова (4);

коли виконується умова (5);

коли виконується умова (6).

Задаючи потрібну точність можна з рівності

одержати необхідну кількість ітерацій , щоб досягти задане .

Наведені умови є достатніми для збіжності методу ітерацій, але аж ніяк не необхідними. Необхідні і достатні умови збіжності методу ітерацій дає наступна теорема, яку сформулюємо без доведення.

ТЕОРЕМА: Нехай система (2) має єдиний розв’язок. Послідовні наближення (3) збігаються до розв’язку системи (2) за довільного початкового наближення тоді та й тільки тоді, коли усі власні значення матриці за модулем менше одиниці.

Повернемось зараз до способів приведення (1) до форми (2). Запишемо (1) у розгорнутій формі

Якщо для усіх , то можна (7) зобразити у вигляді

Звідси два найпростіших ітераційних метода.

Метод Якобі, який задається рекурентним співвідношенням:

Метод Зейделя, де вже знайдені компоненти беруться у правій частині співвідношення з (n+1) -го наближення, а інші- з n- го наближення:

Можна дати матричну форму методів Якобі і Зейделя.

Нехай матрицю А наведено у вигляді:

де -нижня трикутна матриця з нульовою головною діагонал-лю;

D - діагональна матриця з на головній діагоналі;

-верхня трикутна матриця з нульовою головною діагоналлю.

За припущенням існує

Тоді зображенню у формі (8) відповідає

або

Таким чином, методу Якобі відповідає ітераційна процедура

Методу Зейделя відповідає

Використовуючи сформульовані раніш достатні умови збіжності , самостійно переконайтесь, що достатніми умовами збіжності методу Якобі є

або

тобто діагональне переваження матриці А.

Можна довести, що за вказаних умов збігається і метод Зейделя.

Покажемо, що до форми (2), що задовольняє умовам збіжності, може бути зведена довільна система (1) з

Дійсно,візьмемо матрицю де -матриця з достатньо малими за модулем елементами. Множачи (1) зліва на С маємо

тобто одержали форму (2) з

За рахунок вибору достатньо малих можна задовольнити умовам збіжності.

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

Лекція 11-13. Диференціальні рівняння

Звичайним диференціальним рівнянням називається рівняння, що містить похідні невизначеної функції і однієї незалежної змінної. Найпростішим звичайним диференціальним рівнянням є рівняння 1-го порядку

y^`=f(x,y). (1)

Основна задача, що відноситься до цього рівняння, є задача Коші: знайти розв’язання рівняння (1)

y=y(x), (2)

яке задовольняє початковій умові y(х₀)= y₀; іншими словами, потрібно знайти інтегральну криву у=(х), що проходить через задану точку М(х_0, y₀) (мал. 1).

у

Якщо права частина f(x,y) непе-

рервна в деякій області R, обумовлений у=у(х)

нерівностями М₀

| x-x₀ |<a; | y-y₀ |<b,

у₀ у
то існує щонайменше

одне розв’язання(2), визначене в 0 х₀ х х

межах | x- x₀ |<h, де h- позитивне число.

Рис.1

Це розв’язання єдине, якщо в R виконана умова Липшица

| f(x,`y) – f(x,y) | £ N |`y – y |, (3)

де N- деяка постійна (стала Липшица), що залежить, у загальному випадку, від a і b. Якщо f(x,y) має граничну похідну f _y^` (x,y) у R, то можна покласти

N=max|f ^`(x,y) | при (x,y)ÎR.

Дата добавления: 2014-01-07