Впорядкування СЛАР

Вибір головного елемента для підвищення точності. Метод вибору головного елемента дозволяє підвищити точність розв’язування СЛАР. Якщо припустити в СЛАР, що , то в цьому випадку не можна використовувати метод Гаусса, оскільки в за алгоритмом методу потрібно ділити перше рівняння системи на . Елемент, на який виконується ділення, називають ведучим (головним). У такій ситуації слід поміняти перше рівняння на інше, в якому , і процес стає реалізовуваним.

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

Так, в прикладі:

при частковому впорядкуванні міняємо місцями 1-е і 3-е рівняння.

Отримаємо

При повному впорядкуванні додатково до цього поміняємо місцями 1-й і 3-й стовпець, отримаємо:

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

3.7 Ітераційні методи

Ітерація – результат повторного використання якої-небудь математичної операції.

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

Розглянемо один із способів, що дозволяє уточнити розв’язок, отриманий за допомогою прямого методу.

Знайдемо розв’язок СЛАР за допомогою прямого методу.

(3.17)

Нехай це буде вектор

.

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

(3.18)

У матричному вигляді АХ⁽⁰⁾ = В⁽⁰⁾.

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

, , .

Віднімаючи кожне рівняння системи (3.18) від відповідного рівняння системи (3.17), з урахуванням вказаних позначень, отримаємо:

 

(3.19)

 

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

Таким же способом можна знайти нові поправки до розв’язку і наступні наближення розв’язку:

;

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

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

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

(3.20)

то ітераційний процес припиняється.

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

 

 

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

Найпростішим ітераційним методом рішення СЛАР є ітераційний метод Гауса (метод простої ітерації).

Проілюструємо цей метод на прикладі розв’язування СЛАР 3-го порядку

 

(3.21)

 

Припустимо, що . Розв’яжемо перше рівняння відносно , друге рівняння – відносно , третє – відносно .

Маємо:

(3.22)

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

(3.23)

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

Кожні наступні наближення знаходимо аналогічно:

У загальному випадку для СЛАР го порядку:

 

. (3.24)

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

 

(3.25)

або

, якщо . (3.26)