1. МЕТОДИ РОЗВ’ЯЗУВАННЯ СИСТЕМ
ЛІНІЙНИХ АЛГЕБРИЧНИХ РІВНЯНЬ
Розглянемо чисельні методи розв’язування систем лінійних алгебричних рівнянь
, (1)
де A - матриця m*m, - шуканий вектор, - заданий вектор.
Припускаємо, що та визначник матриці А відмінний від нуля, так що існує єдиний розв’язок Х. З курсу алгебри відомо, що систему (1) можна розв’язати за формулами Крамера1. Для великих m цей спосіб практично нереалізований тому, що потребує порядку m! aрифметичних дій. Тому широко використовуються інші методи розв’язування, наприклад, метод Гауса2, який потребує дій.
Методи чисельного розв’язування системи (1) поділяються на дві групи:
- прямі методи;
- ітераційні методи.
У прямих (або точних) методах розв’язок Х системи (1) відшукується за скінченну кількість арифметичних дій. Внаслідок похибок заокруглення прямі методи насправді не приводять до точного розв’язку системи (1) і назвати їх точними можливо лише залишаючи осторонь похибки заокруглення.
Ітераційні методи (їх також називають методами послідовних наближень) полягають у тому, що розв’язок x системи (1) відшукується як границя при послідовних наближень де n- номер ітерації. Як правило, за скінченну кількість ітерацій ця границя не досягається.
1.1. МЕТОД ГАУСА
Запишемо систему (1) у розгорнутому вигляді:
(2)
Метод Гаусса розв’язання системи (2) полягає у послідовному вилученні невідомих з цієї системи.
Припустимо, що . Поділивши перше рівняння на , отримаємо
, (3)
де
Розглянемо тепер рівняння системи (2), що залишилися
. (4)
Помножимо (3) на та віднімемо одержане рівняння з і-го рівняння системи (4), .
У результаті отримаємо наступну систему рівнянь
(5)
Tут позначено:
. (6)
Матриця системи (5) має вигляд:
.
Матриці такої структури заведено позначати так:
,
де хрестиками позначені ненульові елементи.
У системі (5) невідоме х міститься тільки в першому рівнянні, тому у подальшому достатньо мати справу із скороченою системою рівнянь:
(7)
Тим самим ми здійснили перший крок методу Гаусса. Коли , то з системи (7) зовсім аналогічно можна вилучити невідоме x2 і прийти до системи, еквівалентній (2),що має матрицю такої структури:
. (8)
При цьому перше рівняння системи (5) залишається без зміни.
Вилучаючи таким же чином невідомі , приходимо остаточно до системи рівнянь виду
(9)
що еквівалентна початковій системі (2).
Матриця цієї системи
(10)
містить нулі усюди нижче головної діагоналі. Матриці такого виду називаються верхніми трикутними матрицями. Нижньою трикутною матрицею називається така матриця, у якої дорівнюють нулю усі елементи, що містяться вище головної діагоналі.
Побудова системи (9) складає прямий хід методу Гаусса. Зворотний хід полягає у відшуканні невідомих з системи (9). Тому що матриця системи має трикутний вигляд, можна послідовно, починаючи з , відшукати всі невідомі. Дійсно,
, ...
Загальні форми зворотного ходу мають вигляд
(11)
При реалізації на ЕОМ прямого ходу методу Гаусса немає необхідності діяти із змінними . Досить вказати алгоритм, за яким початкова матриця А перетворюється до трикутного вигляду (10), та вказати відповідне перетворення правих частин системи.
Одержимо ці загальні формули. Нехай вже здійснені перші кроків, тобто вже вилучені змінні . Тоді маємо систему
(12)
Розглянемо k-те рівняння цієї системи:
, (13)
та припустимо, що . Поділивши обидві частини цього рівняння на , отримаємо
, (14)
де .
Далі помножимо рівняння (14) на та віднімемо отримане співвідношення з i-го рівняння системи (12). У результаті остання група рівнянь системи (12) набуває наступного вигляду:
(15)
де .
Таким чином, у прямому ході методу Гауса коефіцієнти рівнянь перетворюються за наступним правилом
(16)
(17)
(18)
Обчислення правих частин системи (7) здійснюється за формулами:
(19)
(20)
Коефіціенти і праві частини ; зберігаються у пам’яті ЕОМ і використовуються при здійсненні зворотного ходу за формулами (11).
1.2. МЕТОД ПРОСТОЇ ІТЕРАЦІЇ
Розглянемо систему лінійних рівнянь
(21)
де - задана числова квадратна матриця -го порядку, - заданий вектор вільних членів.
Метод простої ітерації полягає в наступному. Вибирається довільне початкове наближення вектору і будується ітераційна послідовність векторів за формулою
(22)
Ітераційний процес триває до тих пір поки не виконається умова його збіжності
, (23)
де - похибка збіжності ітераційного процесу задана у відсотках.
Для збіжності методу простої ітерації при будь-якому початковому наближенні необхідно і достатньо, щоб всі власні значення матриці В були за модулем меншими від одиниці. Ця умова пов’язана з необхідністю розв’язування рівняння
. (24)
1.3. МЕТОД ЗЕЙДЕЛЯ
Ітераційний метод Зейделя відрізняється від методу простої ітерації тим, що на -й ітерації при обчисленні -ої компоненти вектору використовуються значення , обчислені на тій же ітерації. Ітераційний процес Зейделя має вигляд
(25)
В матричному вигляді система рівнянь (25) має вигляд
, (26)
де

Для збіжності методу Зейделя необхідно і достатньо, щоб всі власні значення матриці були за модулем менші від одиниці. Нагадаємо, що в загальному випадку власні значення є комплексними величинами , тоді вище згадана умова записується у вигляді
(27)
Рівняння =0 тотжнє рівнянню
(28)
Слід зауважити, що в загальному метод Зейделя має кращу збіжність ніж метод простої ітерації. Хоча все залежить від параметрів конкретної задачі, тому не виключена ситуація, що метод простої ітерації дасть кращі результати. Однозначну відповідь на це питання дають рівняння (24), (28).
Ітераційний процес (26) завершуємо при виконанні умови його збіжності (23).
2. МЕТОДИ РОЗВ’ЯЗУВАННЯ СИСТЕМ
НЕЛІНІЙНИХ АЛГЕБРИЧНИХ РІВНЯНЬ
Розглянемо нелінійне векторне рівняння
, (29)
де - нелінійна вектор-функція, - вектор шуканих змінних

2.1. МЕТОД ПРОСТОЇ ІТЕРАЦІЇ
Цей метод можна застосувати лише у цьому випадку, якщо рівняння (29) можна звести до вигляду
, (30)
де .
Ітераційний процес, який розв’язує (30) можна записати у вигляді
(31)
Умова його збіжності має вигляд
, (32)
де - розв’язок рівняння (29).
2.2. МЕТОД ЗЕЙДЕЛЯ
Аналогом методу Зейделя при розв’язуванні нелінійних систем рівнянь є ітераційний процес, згідно якому послідовні наближення визн