4.3. Класифікація методів розв’язання систем лінійних алгебраїчних рівнянь та їх порівняльні характеристики

Методи розв’язання систем лінійних алгебраїчних рівнянь ділять на дві групи: точні та ітераційні [1 – 4].

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

До точних методів розв’язання СЛАР відносять: правило Крамера, метод Гаусса, метод головних елементів метод Гаусса–Жордана, схему Халецького, метод квадратних коренів тощо.

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

Метод Гаусса потребує виконання 2/3n³+О(n²) арифметичних операцій (n – кількість невідомих) і займає n² комірок пам’яті. Його застосовують для розв’язання СЛАР з щільно заповненою матрицею.

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

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

В багатьох випадках виникає необхідність розв’язання СЛАР, в якій матриця коефіцієнтів є незмінною, а стовпець вільних членів є змінним. Тоді доцільно застосовувати обчислення за схемою Халецького. В такому випадку один раз обчислюються значення елементів трикутних матриць і багатократно розв’язуються нижня і верхня трикутні системи, котрі потребують виконання n² операцій множення і ділення.

Якщо матриця коефіцієнтів системи симетрична – доцільно застосовувати метод квадратних коренів, який потребує вдвічі меншої кількості комірок пам’яті і арифметичних операцій – відповідно n/2(n+1) 1/3n²+O(n).

Застосування точних методів для розв’язування СЛАР з велокою кількістю невідомих досить громіздке. Крім того, кількість невідомих може бути така велика, що коефіцієнти системи не завжди можна розташувати в оперативній пам’яті комп’ютера. Тоді системи розв’язують за допомогою ітераційних методів [1].

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

До ітераційних методів розв’язання СЛАР відносять: метод простої ітерації (або метод ітерації), метод Зейделя, метод верхньої релаксації тощо.

Далі детальніше розглянемо теоретичні та практичні питання розв’язання СЛАР точними та ітераційними методами.