Вычисление корней с использованием итерационных функций

В дальнейшем мы будем рассматривать другой подход для расчета корней. Уравнение f (x) = 0 может быть представлено в следующей эквивалентной форме:

где g'(x) — некоторая итерационная функция и /(х*) = 0 соответствует х* = g'(x*). Оказалось, что итерационные алгоритмы проще конструировать на основе эквивалентной формы (2.1). Итерационный процесс определяется следующим образом: зададим начальное значение х₀ и будем вычислять последующие приближения по формуле.

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

Теорема 2.3. Пусть I = а, Ь ограниченный интервал и g (x) функция, действующая из / в /. В дополнение g (x) удовлетворяет условию Липшица.

для произвольных точек у и z в /. Пусть х₍₎ е / и х^₊₁ = g (Xk), тогда последовательность {х*} сходится к единственному решению х* е / уравнения х = g'(x).

На основе этой теоремы можно получить оценку ошибки k-ro приближения, которая зависит от двух последовательных приближений и константы Липшица L. Так как х^ — X/J = ⁼ Ig (Xk) — g (Xk i)|, мы можем заключить из условия Липши;

Рис. 23. Последовательные приближения, генерируемые итерационным процессом (2.2):

О ~ gx) > 0; б - g'(x) < 0.

ца, что для всех k xk+ — Xj < Lхь+ — х^. Пусть п произвольное положительное целое число. Тогда.

и.

Следовательно, мы можем записать Пусть п —? оо, тогда.

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

Имеется большое разнообразие методов для решения уравнения f (x) = 0. Мы рассмотрим лишь основные подходы, основанные на следующих трех типах итерационных процессов:

1) одноточечная итерация.

2) многоточечная итерация.

где р], Р" — некоторые функции;

3) одноточечная итерация с памятью.

Теперь следует разъяснить термин «быстрая сходимость» более подробно. Сделаем это на примере итерационного процесса (2.4). Сначала введем ошибку k-ro приближения как вк = Xk — х*_у тогда хь = + х* и хь+ = е^₊ + х*. После подстановки этих выражений в (2.4) мы можем разложить g (e/t + х*) по степеням в окрестности точки .г* (предполагая, что все производные функции g (x) до порядка р включительно непрерывны):

Учитывая, что х* = g (x*)_f мы получаем.

Если g^M(x*) = 0 для /2=1,…, р — 1 и g^x*) * 0, тогда итерационная функция g (x) имеет порядок р и, как следует из (2.7),.

где р называется порядком последовательности {.г*} и С — константой асимптотической сходимости. Когда р = 1, итерационная последовательность имеет линейную сходимость к!*, а прир > 1 сходимость сверхлинейная. Легко видеть, что если e/f достаточно мала, тогда при р > 1 итерационная последовательность может сходиться очень быстро.

Нам осталось обсудить один практически важный вопрос: как оценить ошибку k-ro приближения к точному решению х*. Это можно сделать на основе неравенства (2.3). Если е х* - г_р, х* + е_р], то выполняются следующие условия:

В дополнение к условию (2.9) обычно требуют также выполнения условия.

Это условие следует из постановки проблемы. Таким образом, итерационный процесс завершается, когда одно из этих условий выполняется.