Головна |
швидкість збіжностіРаніше стверджувалося, що якщо ітераційний метод в деякому сенсі сходиться, то він сходиться до вирішення вихідної задачі (2.1). Зрозуміло, що швидкість досягнення результату істотно залежить від того, наскільки вдало ("близько" до вирішення) вибрано початкове наближення. У загальному випадку умови збіжності ітераційного методу розв'язання системи лінійних алгебраїчних рівнянь визначаються наступною теоремою, доказ якої можна знайти, наприклад, в книзі [1]. Теорема 2.5. ітераційний метод сходиться при будь-якому початковому наближенні тоді і тільки тоді, коли всі власні значення матриці по модулю менше одиниці. При практичному використанні ітераційних методів важливий не тільки сам факт збіжності послідовності одержуваних рішень, але і швидкість, з якою ця послідовність сходиться до точного результату. Якщо для похибки використовуваного методу має місце оцінка виду , то кажуть, що ітераційний метод сходиться зі швидкістю геометричної прогресії зі знаменником q. Ця оцінка показує, у скільки разів зменшується початкова похибка після проведення певної кількості ітерацій. Задамо довільне число k> 0 і вимагатимемо, щоб після виконання N ітерацій початкова похибка зменшилася не менше, ніж в k раз, тобто . Це має місце в разі , Звідки отримуємо . Ціла частина цього дробу буде мінімальним числом ітерацій, необхідне для досягнення заданої точності. вираз називається швидкістю збіжності итерационного методу. Ця швидкість цілком визначається властивостями матриці переходу і не залежить від номера ітерації, вибору початкового наближення і задається точності. Чим вище швидкість збіжності, тим вища продуктивність обраного методу розв'язання системи лінійних алгебраїчних рівнянь. поліноми Чебишева[13] Для подальшого розгляду визначимо, згідно [8], норму , звану чебишёвской. Розглянемо задачу: серед усіх поліномів ступеня N зі старшим коефіцієнтом, рівним 1, знайти такий многочлен , Для якого величина мінімальна. Такий многочлен зветься полінома Чебишева. розглянемо функцію . (2.15) Зробимо тригонометричні перетворення: Складаючи почленно два останніх рівності, отримуємо рекурентне співвідношення для побудови функції . Відповідно до формули (2.15) І далі, відповідно до отриманої залежністю На рис. 2.4 показані деякі поліноми побудованої системи. Мал. 2.4. поліноми TN(X) при N = 2, 3, 4, 5, 6 Можна помітити, що в загальному випадку коефіцієнт при старшій ступеня визначається наступним чином: (2.16) визначимо функцію у вигляді . (2.17) Очевидно, що є поліномом ступеня N зі старшим коефіцієнтом, рівним 1. Визначимо корені цього полінома: оскільки є поліномом ступеня N, він має не більше N коренів, причому всі вони різні і лежать на відрізку [-1, 1]: . Таблиця 2.4 коріння полінома для N = 1, 2, 3, 4, 5, 6 і 7
Цілком очевидно (рис. 2.4), що поліноми приймають екстремальні значення в тих точках, де функція cos () приймає значення +1 або -1. У цих точках поліном приймає чергуються за знаком значення ; при цьому чебишёвская норма дорівнює . Лемма 2.2. Нехай існує система точок така, що , Причому в зазначених точках функція має чергуються знаки. Тоді серед усіх поліномів ступеня N зі старшим коефіцієнтом, рівним 1, многочлен найменш ухиляється від 0. Доведення. Нехай існує поліном ступеня N зі старшим коефіцієнтом 1 (рис. 2.5), причому , тобто . побудуємо функцію , Відмінну від нуля і є поліномом ступеня (N-1). Мал. 2.5. Графіки поліномів Q5(X), S5(X) і їх різниці У точках екстремумів маємо . тоді і в силу припущення функція R (x) на відрізку [-1, 1] змінює знак N раз, а значить має N коренів, чого не може бути, оскільки R (x) є поліномом ступеня (N-1). Таким чином, твердження леми 2.2 доведено. Оскільки побудований раніше поліном Чебишева задовольняє всім вимогам леми, він є найменш ухиляється від нуля на відрізку [-1, 1]. У разі необхідності відшукання полінома, що найменш ухиляється від нуля на довільному відрізку [a, b], слід перейти до нової змінної , яка тепер приймає значення . У цьому випадку функція PN(X) приймає вид: . Формула (2.16) представляється у вигляді: Тепер можна отримати поліном зі старшим коефіцієнтом 1, тобто поліном Чебишева для відрізка [a, b]: . (2.18) Коріння цього многочлена визначаються аналогічно розглянутому вище випадку: Очевидно, що в цьому випадку . Може розглядатися ще одне завдання: знайти многочлен ступеня N, найменш ухиляються від нуля на відрізку [a, b] серед многочленів, що задовольняють умові . Перенорміруем поліном (2.18) так, щоб , , де . Коріння цього многочлена розташовані в точках . Введемо позначення: ; Розглянемо співвідношення: ; - Непарна функція; - Парна функція; - Непарна функція; - Парна функція; ... покладемо , тоді , . вводячи позначення , Уявімо певний вище коефіцієнт у вигляді . Тепер очевидно, що побудований поліном приймає екстремальні значення, рівні . Збіжність ітераційних методів | Ітераційний метод з чебишёвскім набором параметрів метод Гаусса | Визначення числа операцій алгоритму методу Гауса | Обчислення визначника матриці | Побудова зворотної матриці | Метод квадратного кореня | Визначення числа операцій алгоритму методу квадратного кореня | Стійкість системи лінійних алгебраїчних рівнянь | Доведення | Доведення | Ітераційні методи рішення | |