- •Лекція 1 етапи розв‘язування задач на еом .Елементи теорії похибок
- •1.1 Точні і наближені числа. Джерела похибок. Класифікація похибок
- •1.2 Абсолютна і відносна похибки
- •1.3 Десятковий запис наближених чисел. Значуща цифра числа. Дійсна значуща цифра
- •1.4 Зв’язок між числом дійсних знаків і похибкою числа
- •1.6 Обчислювальний експеримент та його основні етапи. Поняття стійкості та коректності
- •2.3 Особливості методів Гауса
- •Лекція № 3 розв‘язування систем лінійних алгебраїчних рівнянь
- •2.1 Основні поняття та визначення
- •2.2 Класифікація методів розв’язання слар на еом
- •2.3.1 Метод Гауса з послідовним виключенням невідомих
- •2.3.2 Метод Гауса за схемою Халецького
- •2.3.3 Метод Гауса з вибором головного елемента
- •2.3.4 Метод Гауса з одиничними коефіцієнтами
- •2.3.5 Метод Гауса-Жордана
- •Лекція №3 наближені методи розв'язання слар на еом
- •3.1 Постановка задачі та класифікація методів
- •3.2 Загальний підхід до розв’язання слар наближеними методами
- •3.3 Умови збіжності ітераційного процесу
- •3.4 Метод послідовних наближень (метод Якобі)
- •3.5 Метод Гауса-Зейделя
- •3.6 Метод верхньої релаксації
- •Лекція № 4 чисельні методи роз’вязання нелінійних рівнянь та систем нелінійних рівнянь
- •4.1 Загальні поняття та визначення
- •4.2 Принципи розв’язання нелінійних рівнянь на еом
- •4.3 Чисельні методи уточнення коренів
- •4.3.1 Метод половинного ділення
- •4.3.2 Метод хорд
- •4.3.3 Метод Ньютона (метод дотичних)
- •4.3.4 Комбінований метод
- •4.3.5 Метод ітерацій (метод послідовних наближень)
- •4.4 Чисельні методи розв’язання систем нелінійних рівнянь
- •5.1 Способи завдання функцій
- •5.2 Математична постановка задачі інтерполювання
- •5.2.1 Інтерполяційний багаточлен Лагранжа
- •5.2.2 Перша інтерполяційна формула Ньютона для рівновіддалених вузлів інтерполяції
- •Лекція №6 Апроксимація табличних функцій
- •6.1 Апроксимація табличних функцій
- •6.1.1 Апроксимація табличних функцій степеневими поліномами
- •6.1.2 Апроксимація узагальненими поліномами
- •6.1.3 Апроксимація ортогональними поліномами
- •6.1.4 Апроксимація тригонометричними поліномами (гармонійний аналіз)
- •7.1 Основні поняття та визначення
- •7.2 Чисельні методи знаходження визначеного інтегралу
- •7.2.1 Метод прямокутників
- •7.2.2 Метод трапецій
- •7.2.3 Метод Сімпсона
- •8.1 Метод Ньютона-Котеса
- •8.2 Метод Чебишева
- •8.3 Метод Гауса
- •8.4 Загальний підхід до визначення інтегралів на еом
- •9.1. Основні визначення та поняття
- •9.2. Класифікація численних методів розв'язання задачі Коші
- •9.3 Одноточкові методи розв'язання задачі Коші на еом
- •9.1.1 Модифікації методу Ейлера
- •9.1.2 Метод Рунге–Кутта
- •9.4 Методи прогнозу і корекції (багатоточкові методи)
- •9.4.1 Метод Мілна
- •9.4.2 Метод Адамса - Башфорта
- •9.4.3 Метод Хемінга
- •10.1 Чисельні методи розв’язання крайових задач
- •10.1.1 Методи стрільби
- •10.1.2 Кінцево-різницеві методи
- •10.1.3 Метод прогонки
- •11.1 Різницеві методи розв'язування диференційних рівнянь у частинних похідних
- •11.2 Етапи чисельного розв'язування диференційних рівнянь (др) у частинних похідних на еом
- •11.3 Еліптичні рівняння
- •11.4 Гіперболічні рівняння
- •12.1 Параболічні рівняння
- •13.1 Метод загального пошуку
- •13.2 Метод половинного ділення (розділення відрізка навпіл)
- •13.3 Метод дихотомії
- •13.4 Метод “золотого перетину”
- •13.5 Метод Фібоначчі
- •13.6 Порівняння методів одновимірного пошуку
- •14.1 Основні поняття та визначення
- •14.2 Критерії оптимальності
- •14.3 Градієнтні методи
- •14.3.1 Найшвидший підйом з використанням одномірного пошуку
- •14.3.2 Метод найшвидшого спуску
- •14.3.3 Метод Флетчера – Рівса
- •14.3.4 Метод Девідона – Флетчера – Пауела
- •14.3.5 Метод конфігурацій Хука – Дживса
- •14.3.6 Метод конфігурацій Розенброка
3.3 Умови збіжності ітераційного процесу
Описаний вище алгоритм дозволяє отримати розв’язок системи (3.2) близький до точного (з заданою похибкою ) тільки в тому випадку, коли ітераційний процес пошуку розв’язку СЛАР збігається.
Теорема
про збіжність.
Ітераційний процес пошуку розв’язку
системи лінійних алгебраїчних рівнянь
виду (3.5) наближеними методами збігається,
якщо будь-яка канонічна норма матриці
.
Канонічною нормою матриці називається будь-яке дійсне додатне число, яке визначається за такими умовами:
перша
канонічна норма – це
максимальна з сум модулів елементів
матриці коефіцієнтів
по
стрічкам:
,
(3.9)
друга канонічна норма – це максимальна з сум модулів елементів матриці коефіцієнтів по стовбцям:
,
(3.10)
третя канонічна норма – це корінь квадратний з сум квадратів модулів всіх елементів матриці коефіцієнтів :
.
Наслідок 1: Ітераційний процес розв’язання системи (3.4) збігається, якщо сума модулів елементів стрічок матриці коефіцієнтів або сума модулів елементів її стовбців менш одиниці, тобто виконується умова
<1
або умова
<1.
(3.11)
Наслідок 2: Ітераційний процес розв’язання системи (3.4) збігається, якщо елементи головної діагоналі більше суми модулів елементів відповідної стрічки крім діагонального елементу цієї стрічки, тобто виконується умова:
або
умова
.
(3.12)
Приклад.
Визначити, чи збігається ітераційний процес для системи рівнянь
або
Матриця
даної
системи має вигляд:
Визначаємо норми:
Таким чином, перша та друга канонічні норми менш одиниці, тобто ітераційний процес для даної системи збігається.
Розглянемо особливості алгоритмів наближених методів.
3.4 Метод послідовних наближень (метод Якобі)
Нехай задана система лінійних алгебраїчних рівнянь виду (3.2). Метод послідовних наближень (метод Якобі) відноситься до ітераційних методів, тому потребує перетворити дану систему до нормального вигляду (3.5) та знайти канонічні норми матриці , для того щоб визначити умови збіжності ітераційного процесу (3.9) - (3.11) пошуку розв’язку системи с заданою похибкою відповідно теоремі про збіжність. Якщо жодна з умов (3.3) – (3.11) не виконується, то дану систему необхідно перетворити по певним правилам, та знову перевірити умови збіжності ітераційного процесу (3.9) – (3.11). Якщо жодна з умов знову не виконується, то метод послідовних наближень не має сенсу використовувати. Якщо хоча б одна з умов (3.9) – (3.11) виконується, то ітераційний процес пошуку розв’язку системи с заданою похибкою збігається і метод послідовних наближень можна використовувати.
По-перше, вибирається певне значення вектору початкових наближень , яке підставляється в праву частину системи рівнянь виду:
, (3.13)
що легко розв’язується для знаходження вектора розв’язку першого наближення , тому що в правої частині містить всі визначені елементи.
По-друге, перевіряється виконання умови закінчення ітераційного процесу виду:
де - задана похибка результатів розв’язання задачі. Якщо умова не виконується, то підставляється в праву частину системи (3.5) і знаходиться :
та знову перевіряється виконання умови закінчення ітераційного процесу виду:
.
За аналогією будь-яке (К+1)-е наближення можна обчислити за формулою:
,
де к=0,1,2.....
(3.14)
Якщо
послідовність
,
що отримана в результаті ітераційного
процесу, має границю
,
то ця границя є розв’язком системи.
Умова закінчення ітераційного процесу
має вигляд:
,
(3.15)
де - задана похибка результатів розв’язання системи.
Алгоритмічно
перевірка умови (3.15) представляє собою
алгоритм пошуку максимального відхилення
між координатами вектора
і
і
порівняння його з заданою похибкою
.
Алгоритм методу послідовних наближень зображено на рисунку 3.1
Рисунок 3.1. – Схема алгоритму методу послідовних наближень
Оцінка похибки метода Якобі
Якщо
задана допустима похибка обчислень
і
x
- вектор точного розв’язку системи
лінійних рівнянь, а
-те
наближення до вектору точного розв’язку,
то для оцінки похибки метода послідовних
наближень використовується формула:
,
(3.16)
де
-
одна з 3 норм матриці
;
-
аналогічна норма вектора
;
-
кількість ітерацій, необхідна для
досягнення потрібної точності
.
