Одноточечный итерационный процесс

Вначале мы рассмотрим случай, когда g'(x*) ^ 0.

Как это следует из (2.7), = g (x*)ek и при условии.

будет линейная сходимость. Условие (2.10) невозможно использовать на практике, по мы можем потребовать выполнения следующего условия:

Тогда теоретическое условие (2.10) будет также выполнено.

Простейший способ представить исходное уравнение в виде (2.1) следующий:

что дает итерационную схему.

Эта схема называется методом простой итерации. Для того чтобы условие (2.11) выполнялось, параметр, а должен подчиняться условиям.

Для определенности можно выбрать.

Начальное приближение xq следует выбирать из интервала I.

Пример 2.2 (метод простой итерации).

Параметр, а определяется как.

Начальное приближение Хо = 0 и требуемая точность г_р = = 10 ^г>. Результаты расчетов показаны в табл. 2.2.

Таблица 2.2

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

Существует специальная процедура, которая позволяет ускорить сходимость, используя приближения, полученные методом простой итерации. Выражение (2.7) для метода (2.13) может быть записано в виде.

или.

Рассмотрим две последовательные итерации.

После исключения R, мы можем выразить х* из этих двух уравнений:

Если мы возьмем z/_i+{ в качестве приближения к х*, тогда точность этого приближения будет 0((7у,)²), т. е. последовательность {zk} имеет сходимость второго порядка, в то время как последовательность {химеет линейную сходимость. Преобразование {ду} —? {z^} называется процессом Эйткена.

Пример 2.3 (процесс Эйткена) Рассмотрим процесс Эйткена, основанный на данных из примера 2.2. Результаты расчетов представлены в табл. 2.3.

Таблица 23

Если сравнить эти результаты с результатами из примера 2.2, то заметно, что достигается некоторое ускорение сходимости.

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

Пусть производные f (x) до порядка s включительно непрерывны на отрезке /.Тогда, применяя разложение по формуле Тейлора функции f (x) в окрестности х_к € I, получим.

где уI, лежит в интервале, который зависит от х_к и х.

Рис. 2.4. Графическое представление итерационной схемы, основанной на разложении (2.15).

Следующее приближение к х* находится из уравнения (рис. 2.4).

Таким образом, выражая х*₊₁ из уравнения (2.16), мы получим отображение X/, —> х*₊₁, что и определяет некоторую итерационную схему. Можно показать, что последовательность, генерируемая итерационной схемой (2.16), имеет порядок р = s.

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

Пустьх* е /, производные/^(s)(x) непрерывны на отрезке Inf'(x)f^(sx) * О для всех х е I. Если условия.

выполняются и min (x*, х*) < x^+j < шах (х*, хД тогда итерационная последовательность {хД генерируемая итерационной схемой (2.16), монотонно сходится кх*.

Теперь рассмотрим конкретные методы, которые следуют из общего подхода (2.15) и (2.16). Когда s = 2, уравнение (2.16) имеет следующий вид:

Решая это уравнение относительно х^, мы получим итерационную схему где.

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

представляет собой касательную к графику /(.г) в точке х^. Тогда приближение х*₊₁ есть точка пересечения касательной с осью х. Для того чтобы выбрать начальное приближение лго, необходимо использовать условие (2.17) при s = 2.

Пример 2.4 (метод Ньютона).

Условие (2.17) для данной функции записывается как.

и оно выполняется, например, если х_ц < 0.5. Выберем х₀ = 0 и г_р= 10'³. Результаты расчетов приведены в табл. 2.4.

Таблица 2.4

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

В случае s = 3 уравнение (2.16) принимает следующую форму:

Решая это уравнение относительно получим.

Для того чтобы условия теоремы 2.1 выполнялись, необходимо взять знак «+», когда f'(x) > 0, и знак «-», когда f'(x) < 0. Также необходимо учесть, что сумма последних двух слагаемых в выражении (2.21) стремится к нулю вблизи корня. Это может привести к потере точности. Известно, что для квадратного уравнения ах² + Ьх + с = 0 справедливо следующее выражение:

Применяя это преобразование к выражению (2.21), мы окончательно получим следующую итерационную схему:

Начальное условие лг₀ следует выбирать из условия (2.18) при s = 3.

Пример 2.5 (итерационная схема (2.22)).

Условие (2.18) для данной функции записывается как.

и оно выполняется, например, если 0 < Xq < 1. Выберем x₍₎ = = 0.001 и г_р = 10 ⁵. Результаты расчетов приведены в табл. 2.5.

Таблица 2.5

Этот пример демонстрирует итерационный процесс с очень быстрой сходимостью.

Полином РХ^хк+1) можно превратить в полином первой степени, и при этом порядок итерационной последовательности не изменится. Уравнение (2.20) можно модифицировать двумя способами.

1. Заменить один из сомножителей {х_к+ — х_к) в (х_к+ — х_к)² на f (Xk)/f'(Xh). После решения модифицированного уравнения относительно (х_к+{— х_к) мы получим следующую итерационную схему:

Это метод Хэлли (Halley).

2. Заменить (Хк+ — х_к)² на (f (x_k)/fx_k))². Тогда после решения уравнения относительно (х_к* — х_к) мы получим.

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