- •Методичні вказівки до практичних занять
- •Обчислювальна математика
- •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.1)
яку можна записати у векторному вигляді:
де і- вектор стовпчики;.
Потрібно знайти розв'язок ; системи (3.1) такий, що
Розв’язання цієї системи є набагато складнішою задачею, ніж розв’язування одного рівняння. Такі системи розв’язують, як правило, ітераційними методами. Для трьох і більше змінних задовільних способів знаходження нульових наближень немає, але іноді можна вибрати, виходячи з фізичних міркувань або з аналізу задачі [2].
Зауваження 1. Проблема розв’язку системи (3.1) виникає при розв’язуванні багатьох прикладних задач. Наприклад, пошук безумовного екстремуму функцій багатьох змінних за допомогою необхідних умов, при застосуванні неявних методів інтегрування звичайних диференціальних рівнянь тощо.
Зауваження 2. Задача знаходження комплексних коренів може бути зведена до задачі розв’язування 2n рівнянь з 2n невідомими. Для цього вважаютьта дійсну і уявну частини функції прирівнюють до 0:
Зауваження 3. Початкове наближення для всіх методів, які розглядаються, для випадку двох змінних ()можна знайти графічно, визначивши координати точки перетину кривих, що описуються, рівняннями: і
Зауваження 4. Задача (3.1) може бути зведена до задачі пошуку мінімуму функції
.
Її мінімальне значення (рівне нулю) досягається в точці, яка є розв’язком системи (3.1): .
3.1 Метод простих ітерацій
Перетворимо систему рівнянь (3.1) до еквівалентного вигляду
, , (3.2)
або у векторній формі , де, а- визначені та неперервні в околі кореня.
Виберемо початкове наближення ; тоді наступні наближення отримаємо за формулою
(3.3)
При цьому ітерації закінчуються, якщо: .
Дослідимо умови збіжності ітераційного процесу (3.3). Проаналізуємо похибку окремої компоненти на
(s +1)-й ітерації. Припустимо, що вектор-функція має неперервні частинні похідні в деякому околі розв'язку ξ= . Тоді, застосовуючи формулу скінчених приростів Лагранжа, запишемо так:
(х(s))( ) =, (3.4)
де - деяка проміжна точка, причому ξ.
Позначимо через Мs матрицю Якобі
Тоді (3.4) можна записати у матричному вигляді х–=(х(s)) -() = М(х) – ), звідки х–= МММ(х(0)) – ), і достатня умова збіжності ітераційного процесу (3.3) буде така МММдля .
Виконується така теорема.
Теорема 1. Якщо функції неперервні разом зі своїми першими похідними в деякій області , що містить розв'язок , то для збіжності методу (3.3) необхідно і достатньо, щоб модулі всіх власних чисел матриці Якобі М були менші від одиниці < 1, а початкове наближення ― в околі розв’язку х*.
Для виконання цієї умови достатньо, щоб норма матриці М була меншою від одиниці, тобто виконувалася одна з умов (M- елементиМ):
Ці умови будуть виконуватися, якщо
тобто матриці Якобі М – домінантна - модулі діагональних елементів матриці будуть більші від суми модулів інших елементів відповідних рядків.
Для системи рівнянь диференційованих функцій,маємо такі достатні умови збіжності методу простих ітерацій.
Теорема 2. Про достатню умову збіжності метода простих ітерацій.
Нехай функції і, неперервні в області, причому виконана нерівність
<1 (3.5)
Якщо послідовні наближення (3.3) не виходять із області , от процес послідовних наближень збіжнийі векторєдиним розв’язком системи (3.2).
Зауваження 1. Ітераційний процес (3.3) відповідає паралельному процесу ітерацій, тому що для обчислення наближення усіх змінних враховуються тільки знайдені раніше-наближення.
Зауваження 2. Система (3.1) може бути перетворена до вигляду (3.2) різними способами таким чином, щоб використовувалась умова збіжності (3.5). Один зі способів, наприклад, полягає у перетворенні:
,
де - неособлива матриця,,
- матриця Якобі.
Якщо , то потрібно вибрати інше початкове наближення.
Зауваження 3. У якості можна використовувати інші норми векторів.
Зауваження 4. Замість (3.5) можна використовувати:
<1 (3.6)
Зауваження 5. Умови (3.5), (3.6) виконуються, якщо: N<1.
Оцінку похибки s-го наближення можна описати нерівністю
Збіжність методу ітерацій вважають доброю, якщо N <, у цьому разі < 1, тобто якщо в двох послідовних наближеннях збігаються, наприклад, перші три десяткові знаки після коми, то похибка останнього наближення не перевищує 0,001.
Приклад 1. Перевірити систему на збіжність ітераційного процесу, припускаючи, що розв'язок належить області :
Розв'язування. Перетворимо систему до вигляду
і обчислимо частинні похідні:
< 1;
.
Отже, < 1;< 1, тобтоумови збіжності виконуються.
Приклад 2. Методом простих ітерацій з точністю 0,001 знайти корені системи: які розташовані в І квадранті.
Запишемо систему у вигляді, зручному для ітерацій:
Знаходимо частинні похідні:
де .
Для вибору початкового наближення знаходимо координати точок перетину кривих іПриблизне значення точки перетину у першому квадранті. В околі точкимаємо:
Тоді , тобто умови збіжності метод простої ітерації виконуються.
За методом простої ітерації отримаємо:
.
Рис. 3.1. Графічний вибір початкового наближення