Перевірка існування розв’язку

 

Нехай – квадратна матриця порядку , тоді визначник порядку

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

,

де – кількість інверсій переставлення .

Зазначимо, що зі зростанням різко збільшується число доданків у формулі для детермінанта, тому ця формула не є зручною вже при ( доданки). На практиці для обчислення визначників вищих порядків застосовують методи, які використовують такі властивості визначників:

Властивість 1. Значення визначника матриці не змінюється при транспонуванні цієї матриці.

Властивість 2. Детермінант добутку двох матриць дорівнює добутку детермінантів цих матриць.

Властивість 3. Якщо в детермінанті поміняти місцями два рядки (або два стовпці), то визначник змінить знак на протилежний.

Властивість 4. Визначник з двома пропорційними рядками (стовпцями) дорівнює нулю.

Властивість 5. Якщо всі елементи будь-якого рядка (стовпця) дорівнюють нулю, то визначник дорівнює нулю.

Властивість 6. Якщо всі елементи будь-якого рядка (стовпця) мають загальний множник, то його можна винести за знак детермінанта.

Властивість 7. Якщо кожен елемент будь-якого рядка (стовпця) є сумою двох доданків, то такий визначник дорівнює сумі двох визначників, в одному з них відповідний рядок (стовпчик) складається з перших доданків, а в іншому – з других доданків; інші рядки (стовпці) – такі ж як у вихідному детермінанті.

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

 

Метод зниження порядку

 

Полягає в обчисленні визначників -го порядку.

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

Алгебраїчним доповненням елемента визначника називається відповідний мінор , взятий з певним знаком

Властивість 9. Визначник дорівнює сумі добутків елементів будь-якого рядка (стовпця) на їхні алгебраїчні доповнення.

. (1.4)

Ця властивість називається розкладанням визначника по елементах рядка (стовпця).

Використовуючи наведені властивості, можна зручно обчислювати визначники вищих порядків. Метод зниження порядку – добитися, щоб в деякому рядку (стовпці) стало якомога більше нулів, і розкласти визначник по елементах цього рідка (стовпця).

Зрозуміло, що формула (1.4) значно спрощується, якщо всі крім одного елементи рядку або стовпця дорівнюють 0 (метод ефективного зниження порядку).

 

Метод Гауса за схемою Жордана

 

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

для верхньої трикутної: ,

для нижньої трикутної: ,

для діагональної: .

В методі Гауса за схемою Жордана необхідно привести визначник до діагонального виду (використовуючи властивості 3,6-8) і скористатися властивістю 10.

 

 

Прямі методи

 

Метод Крамера

 

Згідно даного методу кожне невідоме системи (1.1) представляється у виді відношення визначників. Запишемо його для системи рівнянь порядку :

Тоді

, ,

де , , .

В методі Крамера необхідно обчислити () визначник -го порядку, що при великому значенні потребує значної кількості арифметичних операцій. Тому метод застосовується лише для розв’язку систем, що містять декілька рівнянь.

 

Метод зворотної матриці

 

Якщо система рівнянь – невироджена, тобто визначник матриці системи , то система (1.1) або еквівалентне їй матричне рівняння (1.3), має єдиний розв’язок.

За умови існує обернена матриця . Помноживши обидві частини рівняння (1.3) зліва на матрицю , одержимо

або

. (1.5)

Формула (1.5) дає розв’язок рівняння (1.3).

 

Метод Гауса

 

– За схемою одиничного ділення

Метод заснований на приведенні матриці системи (1.2) до трикутного виду. Це досягається послідовним виключенням невідомих з рівнянь системи (1.1). Спочатку за допомогою першого рівняння виключається із усіх наступних рівнянь системи. Потім за допомогою другого рівняння перетвореної системи виключається із третього і всіх наступних рівнянь. Цей процес, називаний прямим ходом методу Гауса, продовжується доти, поки в лівій частині останнього ( -го) рівняння не залишиться лише один доданок з невідомим , тобто матриця системи буде приведена до трикутного виду.

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

Розглянемо схему застосування методу Гауса для системи з трьох рівнянь:

(1.6)

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

, (1.7)

де ,

,

Помноживши друге рівняння системи (1.7) на і додавши результат до третього рівняння, виключимо тим самим з третього рівняння. В результаті система (1.7) прийме вид:

, (1.8)

де ,

.

Система (1.8) має трикутний вид. На цьому закінчується прямий хід методу Гауса.

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

Зворотний хід починається з рішення третього рівняння системи (1.8):

.

Використовуючи це значення, можна знайти з другого рівняння, а потім з першого:

,

.

Аналогічно будується обчислювальний алгоритм для лінійної системи з довільним числом рівнянь.

 

– З вибором головного елементу

Ця модифікація методу Гауса полягає в тому, що вимога нерівності 0 коефіцієнтів замінюється на більш жорстку: зі всіх елементів, що залишилися в -му стовпці, необхідно обрати найбільший за модулем, і переставити рівняння системи так, що цей елемент став діагональним.

 

– За схемою Жордана

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

Алгоритм розв’язку системи (1.1) методом Гауса-Жордана.

1. Нехай .

2. Перевірити, чи відмінний діагональний елемент від .

3. Якщо відмінний, то -й рядок стає робочим рядком. Якщо , то необхідно замінити -й рядок на -й (), в якій .

4. Для обчислюємо нові матричні елементи, які позначимо, подібно попереднім, за правилом:

, якщо ,

, якщо ,

де

;

аналогічно представимо нові праві частини рівнянь:

.

5. Збільшуємо на одиницю, якщо , и переходимо до пункту 2. Це приведе до того, що всі елементи -го стовпця, за виключенням діагонального елементу, дорівнюватимуть . В результаті отримаємо діагональну матрицю:

.

6. Обчислення вектора-розв’язку :

.

 

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

Модифікація методу Гауса. Цей метод використовується для розв’язку частинного випадку розріджених систем лінійних рівнянь – рівнянь з тридіагональною матрицею. Такі системи виникають при числовому розв’язку крайових задач для диференціальних рівнянь.

Запишемо систему рівнянь в виді:

де .

Метод прогонки складається з двох етапів – прямої прогонки (аналог прямого ходу методу Гауса) та зворотної прогонки (аналогу зворотного ходу методу Гауса). Пряма прогонка полягає в вираженні кожного невідомого через за допомогою прогоночних коефіцієнтів:

.

З першого рівняння

.

Оскільки , отже: .

З другого рівняння:

,

,

,

.

Так само : , де .

Аналогічно можна обчислити прогоночні коефіцієнти для будь-якого .

,

де .

Отже,

.

Далі виконується зворотна прогонка, для чого спочатку обчислюється з останнього рівняння:

,

,

,

,

.

Потім за формулою

.

та формулами прогоночних коефіцієнтів.

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

 

 

Числові методи

 

Метод уточнення коренів

 

Цей метод дозволяє уточнити розв’язок, отриманий за допомогою прямого методу. Метод уточнення коренів дає можливість зменшити помилки обчислень, а саме помилки округлення.

Розглянемо систему лінійних рівнянь (1.1):

.

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

.

Введемо позначення – похибка значень невідомих, , .

Віднімаючи з вихідної системи систему рівнянь з наближеними значеннями коренів, отримаємо таку систему:

.

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

.

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

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

 

Метод простої ітерації

 

Проілюструємо цей метод на прикладі розв’язку системи:

(1.9)

Збіжність даного методу гарантується, якщо діагональні елементи не дорівнюють 0 і для них виконується умова:

,

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

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

Припустимо, що для даної системи умова збіжності виконується. Виразимо невідомі , , з першого, другого і третього рівнянь системи (1.9) відповідно:

. (1.10)

Задамо деякі початкові (нульові) наближення значень невідомих. В якості нульових значень можуть бути обрані: стовпець вільних членів , відношення , а також будь-які інші значення (наприклад, нульові), тому що виконання умови збіжності забезпечує досягнення результату при будь-яких початкових умовах.

Підставляючи ці значення в праву частину рівнянь системи (1.10), одержуємо нове (перше) наближення для невідомих , , .

. (1.11)

Використовуючи обчислені значення , , , можна тим саме способом провести другу ітерацію, у результаті якої будуть знайдені другі наближення до розв’язку , , . Наближення з номером можна представити у виді:

. (1.12)

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

, (1.13)

або критерієм по відносних відхиленнях (при )

, (1.14)

де – задана похибка невідомих. При виконанні умови (1.13) або (1.14) процес ітерацій припиняється і за шукані розв’язки приймаються їх останні обчислені значення.

Описаний алгоритм може бути розширений на систему з лінійних рівнянь.

 

Метод Зейделя

 

Ітераційний метод Зейделя відрізняється від методу простої ітерації тим, що на -й ітерації при обчисленні використовуються значення , ,..., , обчислені на тій самій ітерації. Наближення на -м кроці стосовно до системи (1.9) за методом Зейделя має вид:

, (1.15)

Зазначені вище умова збіжності та умова припинення обчислень для методу простої ітерації залишаються вірними для методу Зейделя.

 

Завдання

 

Розв’язати систему лінійних рівнянь:

1) прямими методами (зворотної матриці, Крамера, Гауса) з двома знаками після коми;

2) уточнити отриманий в п. 1) розв’язок числовими методами (уточнення коренів, ітерацій або Зейделя) з точністю ;

3) Навести блок-схеми алгоритмів використаних методів.

 

№	Система рівнянь	Методи
1.		1) метод Крамера; 2) метод уточнення коренів;
2.		1) метод Крамера; 2) метод простої ітерації;
3.		1) метод Крамера; 2) метод Зейделя;
4.		1) метод зворотної матриці; 2) метод уточнення коренів;
5.		1) метод зворотної матриці; 2) метод простої ітерації;
6.		1) метод зворотної матриці; 2) метод Зейделя;
7.		1) метод Гауса за схемою одиничного ділення; 2) метод уточнення коренів;
8.		1) метод Гауса за схемою одиничного ділення; 2) метод простої ітерації;
9.		1) метод Гауса за схемою одиничного ділення; 2) метод Зейделя;
10.		1) метод Гауса з вибором головного елементу; 2) метод уточнення коренів;
11.		1) метод Гауса з вибором головного елементу; 2) метод простої ітерації;
12.		1) метод Гауса з вибором головного елементу; 2) метод Зейделя;
13.		1) метод Гауса за схемою Жордана; 2) метод уточнення коренів;
14.		1) метод Гауса за схемою Жордана; 2) метод простої ітерації;
15.		1) метод Гауса за схемою Жордана; 2) метод Зейделя;
16.		1) метод Крамера; 2) метод уточнення коренів;
17.		1) метод Крамера; 2) метод простої ітерації;
18.		1) метод Крамера; 2) метод Зейделя;
19.		1) метод зворотної матриці; 2) метод уточнення коренів;
20.		1) метод зворотної матриці; 2) метод простої ітерації;
21.		1) метод зворотної матриці; 2) метод Зейделя;
22.		1) метод Гауса за схемою одиничного ділення; 2) метод уточнення коренів;
23.		1) метод Гауса за схемою одиничного ділення; 2) метод простої ітерації;
24.		1) метод Гауса за схемою одиничного ділення; 2) метод Зейделя;
25.		1) метод Гауса з вибором головного елементу; 2) метод уточнення коренів;
26.		1) метод Гауса з вибором головного елементу; 2) метод простої ітерації;
27.		1) метод Гауса з вибором головного елементу; 2) метод Зейделя;
28.		1) метод Гауса за схемою Жордана; 2) метод уточнення коренів;
29.		1) метод Гауса за схемою Жордана; 2) метод простої ітерації;
30.		1) метод Гауса за схемою Жордана; 2) метод Зейделя;