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

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

1) Прямі методи зводяться до скінчених алгоритмів для обчислення коренів рівнянь (тобто розв’язки шукають за певними формулами). Вони дають розв’язки після виконання відомого для даного n (n – порядок) числа арифметичних операцій.

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

Оцінити ефективність будь-якого методу можна за допомогою двох – трьох важливих характеристик:

• числа операцій, необхідних для реалізації даного методу;

• об’єму пам’яті;

• чутливості до переносу похибок заокруглення (або обчислювальної стійкості).

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

До групи прямих методів розв’язування систем лінійних алгебраїчних рівнянь належать:

– метод Гаусса та його різновиди:

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

б) метод Гаусса з вибором головного елемента (частковим або повним). Число арифметичних операцій при цьому складає ~ сумувань та ~ множень.

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

– LU-розклад (lower-upper –нижній-верхній)

Якщо використовувати алгоритм Краута, то число операцій складе .

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

– метод Халецького (схема).

При розкладі симетричних матриць можна зменшити число операцій і об’єм пам’яті. Повна вартість складає половині вартості методу Гаусса + n обчислень квадратного кореня. Метод чисельно стійкий.

– метод Жордана (роблять діагональну матрицю замість трикутної). Досить рідко використовується на практиці.

До прямих методів відносяться також методи для кліткових та розріджених матриць.

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

Чому виникла потреба в ітераційних методах? Чим не влаштовують прямі методи?

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

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

Крім того, розв’язування систем ітераційними методами спрощується ще й тому, що на кожній ітерації розв’язується система з одними і тими ж матрицями.

До ітераційних належить: метод простої ітерації, метод Зейделя, метод верхньої релаксації, та інші.