Необхідна і достатня умова збіжності у стаціонарних методах

(4)

Система (4) є однорідною відносно (3). Ітераційний метод буде збігатися якщо . Рівність (4) перепишемо в іншому виді (5)

S- матриця перходу від n-ї до n+1 ітерації, тоді справедлива теорема.

Теорема

Ітераційний метод (3) збігається при будь-якому початковому наближенні тоді і тільки тоді, якщо всі власні значення матриці S

Оцінки швидкості збіжності стаціонарних ітераційних методів

У попередній теоремі показано, що для дослідження збіжності ітераційного методу необхідно досліджувати всі власні значення матриці або володіти інформацією про спектр матриці. Для оцінки ітераційних методів важливим є не тільки факт збіжності, але й швидкість збіжності з яким метод збігається до точного розвязку. Так як ітераційний метод здійснюється за скінченну кількість кроків, то нам необхідно знати у скільки разів зменшиться початкова похибка після проведеного числа ітерацій.

Будемо говорити, що метод збігається із швидкістю геометричної прогресії, якщо виконується така нерівність (7)

Оцінку (7) можна використати для визначення кількості операцій для того щоб початкова похибка зменшувалася задане число разів. Введемо число і будемо вимагати

(8)

Із (8) бачимо, що після виконання ітерацій виконується нерівність

(9)

Після виконання (9) і початкова похибка зменшиться на разів, тоді - найменша кількість кроків, при яких зменшується початкова похибка, а –швідкість збіжності ітераційного методу. Тоді швидкість збіжності повністю визначає властивості матриці S і не залежить від номера ітерації і від вибору початкового наближення. Чим вища швидкість збіжності, тим кращий ітераційний метод, тому якість методів прийнято порівнювати по їх швидкості збіжності.

Теорема 1

Нехай матриці А і В є симетричними і додатньовизначеними і для неї справедлива нерівність

(10), де , тоді при (11) ітераційний метод (3) є збіжним і для похибки будуть справедливі оцінки

(14)

Зауважимо, що найбільш точними константами при при яких виконується нерівність (10) являється

-оптимальний параметр бо мінімізує вираз (14)

Наслідокю розглянемо метод простої ітерації

Многочлени Чебишева 1-го роду і многочлени Чебишева на відрізку [0,1]

В багатьох задачах чисельного аналізу ми зіштовхуємось з проблемою мінімізації похибки обчислювального алгоритму. Для мінімізації похибки ми будемо використовувати властивості многочлена Чебишева, тобто многочленів які мало відрізняються від нуля.

Задача. Серед всіх многочленів n-го степеня з старшим коефіцієнтом 1 знайти такий многочлен для якого буде мінімальною. Многочлен який володіє такою властивістю називається многочленом, який якнайменше відмінний від нуля на проміжку [-1,1]. Покажемо що многочлен виду являється многочленом Чебишева. Розглянемо многочлен (2). Для такого многочлена можемо записати

(3)

Із (3) :

Многочлен – многочлен n-го степення із старшим коефіцієнтом « » де

Запишемо властивості многочлена

1. Для - многочлен n-го степеня з старшим коефіцієнтом

2. Многочлени степеня є парними функціями

Многочлен ( ) степеня є непарними функціями

парні

непарні

Із (3) : – парна

– непарна

3. Многчлен має n дійсних коренів на [-1,1]

4. Многочлен приймає свої найбільші значення на проміжку [-1,1] в точках

Тоді многочлен також є многочленом n-го степеня з із старшим коефіцієнтом «1». Корені будуть розміщені в точках (4) де , а екстремуми будуть знаходитись в точках (5) .

При чому (6) і відповідно (7)

Доведемо, що серед многочленів степеня n із старшими коефіцієнтами «1». Многочлен найменше відхиляється від нуля на проміжку [-1,1]. Введемо в розгляд многочлен степення n із старшими коефіцієнтами «1». Введемо в розгляд позначення

Лема. Нехай система точок (8) (9) при чому ) почергово міняє знак на проміжку [-1,1] , тоді серед всіх многочленів n-го степення з старшими коефіцієнтами «1» многочлен якнайменше відхиляється від нуля.

Із умов (6) і (7) многочлен ,буде задовольняти умовам Леми і тому такий многочлен буде многочленом k-го степеня з старшим коефіцієнтом «1» який якнайменше відрізняється ві нуля.