Скорость сходимости итерационных методов

Введем обозначения: , . Для оценки скорости сходимости необходимо определить зависимость между и .

Если в процессе итераций, начиная с некоторого , выполняется

, где , (3.4.1)

то скорость сходимости итерационного процесса определяется показателем . При скорость сходимости линейная, при – квадратичная, при – сверхлинейная. Если (3.4.1) устанавливается при , то скорость сходимости называется асимптотической.

В случае метода простых итераций:

или ,

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

(3.4.2)

Несмотря на схожесть выражений для метода хорд и секущих, скорость их сходимости различна. Так для метода хорд получим, разлагая выражение для в точке в ряд Тейлора и ограничиваясь тремя слагаемыми:

Учитывая, что , сокращая в числителе и знаменателе и разлагая знаменатель в ряд, получим:

(3.4.3)

Оценка (3.8) с учетом того, что расстояние между точками и меньше длины интервала изоляции дает:

, (3.4.4)

то есть скорость сходимости линейная.

В методе секущих в выражении (3.2.4) необходимо заменить на . Предположим, что соотношение для скорости сходимости имеет вид:

.

Подставляя полученное из него выражение для в (3.4.3), получим для степеней r и t :

, и , , .

Таким образом, сходимость метода секущих сверхлинейная.

Для метода касательных, вычитая из левой и правой части (3.3.1) значение корня и разлагая функцию в ряд, получим:

Откуда:

, (3.4.4)

то есть сходимость метода касательных квадратичная.

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

Если точки перегиба на интервале изоляции нет, то используется метод секущих. Если вычисление первой производной не требует значительного машинного времени, то целесообразно применять самый быстрый метод из рассмотренных - метод Ньютона (касательных).