Скорость сходимости

Ранее утверждалось, что если итерационный метод в некотором смысле сходится, то он сходится к решению исходной задачи (2.1). Понятно, что быстрота достижения результата существенно зависит от того, насколько удачно (“близко” к решению) выбрано начальное приближение. В общем случае условия сходимости итерационного метода решения системы линейных алгебраических уравнений определяются следующей теоремой, доказательство которой можно найти, например, в книге [1].

Теорема 2.5. Итерационный метод

сходится при любом начальном приближении тогда и только тогда, когда все собственные значения матрицы по модулю меньше единицы.

При практическом использовании итерационных методов важен не только сам факт сходимости последовательности получаемых решений, но и скорость, с которой эта последовательность сходится к точному результату. Если для погрешности используемого метода имеет место оценка вида

,

то говорят, что итерационный метод сходится со скоростью геометрической прогрессии со знаменателем q. Эта оценка показывает, во сколько раз уменьшается начальная погрешность после проведения заданного числа итераций.

Зададим произвольное число k>0 и потребуем, чтобы после выполнения N итераций начальная погрешность уменьшилась не менее, чем в k раз, то есть . Это имеет место в случае , откуда получаем

.

Целая часть этой дроби будет минимальным числом итераций, необходимым для достижения заданной точности. Выражение называется скоростью сходимости итерационного метода. Эта скорость целиком определяется свойствами матрицы перехода и не зависит от номера итерации, выбора начального приближения и задаваемой точности. Чем выше скорость сходимости, тем выше производительность выбранного метода решения системы линейных алгебраических уравнений.

Полиномы Чебышёва1

Для дальнейшего рассмотрения определим, согласно [8], норму

,

называемую чебышёвской.

Рассмотрим задачу: среди всех полиномов степени N со старшим коэффициентом, равным 1, найти такой многочлен , для которого величина минимальна. Такой многочлен носит название полинома Чебышёва.

Расмотрим функцию

. (2.15)

Произведем тригонометрические преобразования:

Складывая почленно два последних равенства,

получаем рекуррентное соотношение для построения функции . В соответствии с формулой (2.15)

И далее, в соответствии с полученной зависимостью

На рис. 2.4 показаны некоторые полиномы построенной системы.

Рис. 2.4. Полиномы T_N(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

N=1	N=2	N=3	N=4	N=5	N=6	N=7
0	0,707106781	0,866025404	0,923879533	0,951056516	0,965925826	0,974927912
-	-0,70710678	0	0,382683432	0,587785252	0,707106781	0,781831482
-	-	-0,866025404	-0,382683432	0	0,258819045	0,433883739
-	-	-	-0,923879533	-0,587785252	-0,258819045	0
-	-	-	-	-0,951056516	-0,707106781	-0,433883739
-	-	-	-	-	-0,965925826	-0,781831482
-	-	-	-	-	-	-0,974927912

Вполне очевидно (рис. 2.4), что полиномы принимают экстремальные значения в тех точках, где функция cos( ) принимает значения +1 или -1.

В этих точках полином принимает чередующиеся по знаку значения ; при этом чебышёвская норма равна .

Лемма 2.2. Пусть существует система точек такая, что , причем в указанных точках функция имеет чередующиеся знаки. Тогда среди всех полиномов степени N со старшим коэффициентом, равным 1, многочлен наименее уклоняется от 0.

Доказательство. Пусть существует полином степени N со старшим коэффициентом 1 (рис. 2.5), причем

,

то есть .

Построим функцию , отличную от нуля и являющуюся полиномом степени (N-1).

Рис. 2.5. Графики полиномов Q₅(x), S₅(x) и их разности

В точках экстремумов имеем

.

Тогда и в силу предположения функция R(x) на отрезке [-1, 1] меняет знак N раз, а значит имеет N корней, чего не может быть, поскольку R(x) является полиномом степени (N-1).

Таким образом, утверждение леммы 2.2 доказано.

Поскольку построенный ранее полином Чебышёва удовлетворяет всем требованиям леммы, он является наименее уклоняющимся от нуля на отрезке [-1, 1].

В случае необходимости отыскания полинома, наименее уклоняющегося от нуля на произвольном отрезке [a, b], следует перейти к новой переменной

,

которая теперь принимает значение .

В этом случае функция P_N(x) принимает вид:

.

Формула (2.16) представляется в виде:

Теперь можно получить полином со старшим коэффициентом 1, то есть полином Чебышёва для отрезка [a, b]:

. (2.18)

Корни этого многочлена определяются аналогично рассмотренному выше случаю:

Очевидно, что в этом случае .

Может рассматриваться еще одна задача: найти многочлен степени N, наименее уклоняющийся от нуля на отрезке [a, b] среди многочленов, удовлетворяющих условию .

Перенормируем полином (2.18) так, чтобы ,

,

где .

Корни этого многочлена расположены в точках

.

Введем обозначения:

;

Рассмотрим соотношения:

;

- нечетная функция;

- четная функция;

- нечетная функция;

- четная функция;

...

Положим , тогда

,

.

Вводя обозначение , представим определенный выше коэффициент в виде

.

Теперь очевидно, что построенный полином принимает экстремальные значения, равные

.