Контрольні питання

1. Як визначити абсолютну похибку?

2. Як визначити відносну похибку?

3. Які значущі цифри називаються вірними?

4. Як кількість вірних знаків пов’язана з похибкою числа?

5. Класифікація похибок.

Практична робота № 2

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

Теоретичні відомості

Методи розв'язування систем лінійних рівнянь виду (2.1) діляться на дві групи: точні та ітераційні.

(2.1)

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

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

Формули Крамера мають велике теоретичне значення, але через великий обсяг обчислювальної роботи мало ефективні при чисельному розв’язуванні лінійних систем. За цими формулами потрібно обчислювати значення -го визначників порядку _, для чого необхідно виконати значну кількість арифметичних операцій.

Найпростішим методом розв'язання систем лінійних алгебраїчних рівнянь є метод послідовного виключення змінних, або метод Гауса. Є кілька модифікацій цього методу. Розглянемо схему єдиного ділення, за якою систему розв'язують в два етапи. На першому етапі вихідну систему рівнянь зводять до рівносильної їй системи трикутної форми. Цей процес перетворення називають прямим ходом. На другому етапі, який називають зворотним ходом, знаходять розв'язок лінійної системи рівнянь трикутної форми.

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

Застосування методу Гауса для розв'язання системи лінійних рів­нянь з великою кількістю невідомих досить громіздке. Крім того, кіль­кість невідомих може бути така велика, що коефіцієнти системи не завжди можна розмістити в оперативній пам'яті ЕОМ. Тоді застосувати для її розв'язання метод Гауса взагалі не можна. У цих випадках розв'язують систему ітераційними методами.

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

Нехай діагональні елементи матриці _{виду (2.1)} відмінні від нуля. Тоді, розв'язавши перше рівняння системи відносно , а друге - відносно і т. д., дістанемо систему:

(2.2)

де:

Початкові наближення можуть обиратися за формулою:

.

Систему (2.2) запишемо у вигляді:

. (2.3)

Систему (2.3) називають системою нормального виду. Розв'яжемо її методом послідовних наближень. За початкове наближення візьмемо, наприклад, стовпець вільних членів, тобто _.

Обчислення наступних наближень відбувається через попередні.

Перевірка умови збіжності виконується за наступною формулою:

або (2.4)

Критерієм зупинки методу простої ітерації є перевірка виконання умови , де - задана точність.

Метод Зейделя – є модифікацією методу простої ітерації. У методі простої ітерації при обчисленні компонентів вектора-стовпця на -му кроці використовуються значення ветора-стовпця , обчисленого на попередньому кроці. Метод Зейделя відрізняється від методу простої ітерації тільки тим, що при обчисленні -го наближення компоненти враховуються значення , обчислені на цьому ж кроці. Система лінійних рівнянь для розв’язання методом Зейделя має вигляд:

(2.5)

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

або .

Приклад 2.1

Розв’язати систему рівнянь методом Гауса відповідно системі (2.1):

(2.6)

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

2. За схемою єдиного ділення розв’язуємо систему у такий спосіб:

2.1. Усі числа першого рядка ділимо на . Отримуємо:

. (2.7)

2.2. Виключимо тепер змінну з другого та третього рівняння системи (2.6). Для цього рівняння (2.7) помножимо послідовно: спочатку на коефіцієнт і віднімемо його від другого рівняння системи (2.2), а потім на і віднімемо від третього рівняння системи (2.6).

Одержуємо:

(2.8)

2.3. Поділимо коефіцієнти першого рівняння системи (2.8) на . Одержуємо:

.

2.4. З системи (2.8) виключимо змінну так само, як і з системи (2.6). Дістанемо рівняння:

.

Після перетворень одержимо систему рівнянь трикутної форми:

(2.9)

На цьому прямий хід методу Гауса завершено.

2.5. Розв’язком системи (2.6) буде розв’язок системи (2.9). Оскільки системи (2.6) та (2.9) еквівалентні:

На цьому зворотний хід методу Гауса завершено.

6. Виконання перевірки.

Підставляємо знайдені значення , та у систему (2.6):

Отже, перевірка показала, що одержані значення співпадають із значеннями стовпця вільних членів системи (2.6).

Приклад 2.2

Розв’язати систему рівнянь методом простої ітерації з точністю :

(2.10)

1. Перевіряємо умову збіжності виду (2.4): - для 1-го рівняння умова збіжності виконується;

- для 2-го рівняння умова збіжності не виконується;

- для 3-го рівняння умова збіжності не виконується. Отже, система не є збіжною.

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

.

Друге рівняння нової системи одержимо, якщо від третього рівняння даної системи (2.10) віднімемо перше. У результаті матимемо систему:

. (2.11)

Перевіримо виконання умови збіжності для системи (2.11):

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

3. Тепер систему (2.11) зведемо до нормального виду:

(2.12)

4. Знайдемо початкові наближення. Для цього стовпець вільних членів поділимо на відповідні діагональні коефіцієнти:

5. Виконаємо першу ітерацію. Для цього підставимо знайдені початкові наближення у систему (2.12):

Виконаємо наступну ітерацію. Одержані значення , , підставимо у систему (2.12):

Ітерації продовжуються доти, поки не виконається умова .

Приклад 2.3

Метод Зейделя. Метод застосуємо до системи (2.12).

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

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

Виконаємо наступну ітерацію:

Умова закінчення пошуку аналогічна методу простої ітерації, тобто .