- •Методичні вказівки до практичних занять
- •Обчислювальна математика
- •2010 Зміст
- •Урахування похибок
- •1.1 Основні джерела похибок
- •1.2 Основні поняття
- •1.3 Правила обчислення похибок
- •1.4 Деякі правила обчислення максимальних граничних похибок
- •1.5 Приклади
- •1.6 Задачі
- •Методи розв'язування нелінійних рівнянь
- •2.1 Відокремлення коренів
- •2.2 Метод половинного поділу (бісекцій або діхотомії)
- •2.3 Метод січних (хорд, пропорційних частин)
- •2.4 Метод Ньютона (дотичних, лінеаризації)
- •2.4.1 Модифікований метод Ньютона
- •2.4.2 Метод Ньютона-Бройдена
- •2.5 Метод хорд та дотичних (комбінований метод)
- •2.6 Метод простих ітерацій
- •Методи розв'язування систем нелінійних рівнянь
- •3.1 Метод простих ітерацій
- •3.2 Метод Зейделя
- •3.3 Метод Ньютона
- •3.4 Модифікований метод Ньютона
- •Розв’язування систем лінійних алгебраїчних рівнянь (слар)
- •4.1 Метод ітерації
- •4.2 Зведення слар до вигляду, який придатний до застосування методу ітерації.
- •4.3 Метод Зейделя
- •4.4 Метод релаксації
- •4.5 Метод прогонки
- •4.6 Методика розв’язування задачі
- •5. Наближення функцій
- •5.1 Інтерполяція
- •5.2 Інтерполяційна формула Лагранжа
- •5.3 Оцінка похибки інтерполяційної формули Лагранжа
- •5.4 Збіжність функціонального інтерполяційного процесу неперервних функцій
- •5.5 Методика розв’язування задачі лінійної інтерполяції
- •5.6 Методика розв’язування задачі параболічної інтерполяції
- •5.7 Поліноми Чебишева
- •5.8 Інші методи інтерполяції. Інтерполяційний многочлен Ньютона
- •5.9 Методи інтегрально-диференціальної інтерполяції
- •5.10 Методи інтегрального згладжування
- •5.11 Метод найменших квадратів
- •5.12 Особливості мнк
- •5.13 Метод найкращого інтегрального наближення
- •5.14 Методи інтерполяції та згладжування на основі сплайнів
- •5.15 Інтерполяційні диференціальні кубічні сплайни
- •Список використаних джерел
3.4 Модифікований метод Ньютона
У цьому методі обернена матриця знаходиться тільки один раз в початковій точці . Збіжність спрощеного метода Ньютона в загальному випадку гірша, ніж безпосередньо метода Ньютона.
Приклад 1. Знайти додатний розв’язок системи спрощеним методом Ньютона з точністю.
Із малюнку слідує, що для знаходження початкового наближення можна взяти
Рис. 3.2. Графіки функцій
Так як , то знаходимо
Так як , то знаходимо третє наближення:
Так як , то знаходимо четверте наближення:
Так як , то ітераційний процес закінчений.
Розв’язування систем лінійних алгебраїчних рівнянь (слар)
Способи розв’язування СЛАР в основному розподіляються на дві групи:
Точні методи. Правило Крамера – історично перший метод, потребує арифметичних дій.Метод Гауса – потребує арифметичних дій, щоприі т.д. Для сумісних СЛАР метод Гауса є одним із найефективніших. Зростання об’єму обчислень при збільшенніn та неможливість проведення точних обчислень обмежує ефективність цих методів.
Ітераційні методи (метод ітерації, метод Зейделя, метод релаксації) [1].
4.1 Метод ітерації
Нехай задана система лінійних алгебраїчних рівнянь (СЛАР):
(4.1)
або в матричному вигляді (4.2)
Розв’яжемо І рівняння відносно , ІІ – відноснотощо. Отримаємо еквівалентну систему (4.3):
(4.3)
або в матричному вигляді , (4.4)
де -відповідно вектор стовпчики невідомих і вільних коефіцієнтів, причому - елементи матриціпри.
Систему (4.4) розв’яжемо методом послідовних наближень. За нульове наближення беремо стовпчик вільних коефіцієнтів .
Далі наближення обчислюємо за формулою:
(4.5)
Якщо послідовність - наближення розв’язку системи (4.5), то у розгорнутому вигляді отримаємо:
(4.6)
Інколи систему (4.1) зводять до (4.3) так, щоб коефіцієнти тобто для рівняння, наприклад,записують у вигляді зручному для застосування методу ітерацій
Метод ітерації, який визначається формулами (4.5) або (4.6) добре збігається, якщо елементи матриці малі за абсолютною величиною, тобто для успішного застосування процесу ітерації модулі діагональних елементів матриці коефіцієнтівА системи (4.1) повинні бути більше суми модулів недіагональних елементів (домінантна матриця А), вільні коефіцієнти при цьому на збіжність ролі не грають.
Приклад 1. Розв’язати СЛАР методом ітерації:
(4.7)
Перевіряємо матрицю коефіцієнтів А на домінантність:
- матриця А – домінантна.
Зводимо систему (4.7) до нормального вигляду (4.8):
(4.8)
У матричній формі метод ітерації для (4.8) має вигляд:
(4.9)
За нульові наближення коренів системи (4.9) приймаємо Підставляючи ці значення у праві частини (4.9) отримаємо перше та друге наближення коренів:
Аналогічно обчислимо наступні наближення:
тощо.
При застосуванні метода ітерацій немає необхідності за нульове наближення приймати стовпчик вільних членів. Збіжність процесу ітерації залежить тільки від властивості матриці , причому при виконанні відомих умов процес збігається при довільному початковому векторі. Збіжний процес має властивість "самовиправлятися", тобто окремі помилки в обчисленнях не відображуються на кінцевому результаті, тому що помилкове наближення можна уявити собі, як новий початковий вектор.
Інколи обчислюють не самі наближення, а їх різниці:Звідси
За нульове наближення приймають . Дляk-го наближення: . Тоді:
- якщо тоі;
- якщо тоі
Остаточно
Приклад 2. Розв’язати систему
Запишемо систему у вигляді (4.3):
і т.д.
Таблиця 4.1
Результати обчислень
к | |||
0 |
-1,5 |
0,2 |
0 |
1 |
0,100 |
0,900 |
0,230 |
2 |
0,335 |
0,032 |
0,350 |
3 |
-0,159 |
-0,061 |
-0,021 |
4 |
-0,20 |
0,011 |
-0,008 |
5 |
0,010 |
0,009 |
0,006 |
6 |
0,002 |
-0,004 |
0,003 |
7 |
-0,004 |
0,000 |
-0,001 |
8 |
0,000 |
0,002 |
0,000 |
9 |
0,001 |
0,000 |
0,001 |
-1,235 |
1,089 |
0,560 |
Недоліком цього метода ітерації є систематичне накопичення похибок при збільшенні числа доданків, у результаті чого виникають значні похибки шуканих коренів.
Теорема 1. Якщо для зведеної системи (4.3) виконано хоча б одну з умов: деабодето процес ітерацій (4.5) сходиться до єдиного розв’язку цієї системи, незалежно від вибору початкового наближення.
Наслідок. Для системи метод ітерації збігається, якщотобто якщо модулі діагональних коефіцієнтів для кожного рівняння системи більше суми модулів усіх інших коефіцієнтів за винятком вільних коефіцієнтів.
Теорема 2. Для СЛАР ітераційний процесзбігається за будь-якого початкового наближеннятоді і тільки тоді, коли всі власні числа матриціза модулем менші від одиниці, тобто корені характеристичного рівняння задовольняють
Приклад 3. Методом простої ітерації розв’язати систему:
Тоді:
Коефіцієнти, отриманої системи задовольняють умовам теореми Збіжність ітерацій гарантована. При цьомуТочністьк-го наближення
У якості початкового наближення візьмемо елементи стовпчика вільних коєфіцієнтів, округливши їх значення до двох знаків після комиОбчислимо:
Так як всі , топричому похибка значень не перевищує
Точне значення
Приклад 4. Розв’язати систему, зробивши три ітерації. Вказати похибку отриманого результату.
Тоді:
Умови збіжності виконані
Початкове наближення далі
Похибка