Вычислительная математика как часть математики, страница 6

С другой стороны, , следовательно, . Отсюда:  – непрерывно дифференцируемая функция. Отметим, что уравнение:x = j₂(x) эквивалентно уравнению f(x) = 0. Из графика (рис. 2.4)  видно, что функция j₂(x) переводит отрезок [0, 1] в себя.

Условие, что функция j(x) переводит отрезок [a, b] в себя, можно переформулировать следующим образом: пусть [a, b] – область определения функции j(x), а [c, d] – область изменения j(x). Если отрезок [c, d] принадлежит отрезку [a, b], то функция j(x) переводит отрезок [a, b] в себя.

Найдем :

,      .

Все условия для  функции j(x) выполнены.

Формула итерационного процесса: x_n+1 = j₂(x_n).

3. Начальное приближение: x₀ = 0.

4. Условие остановки итерационного процесса:

.

При выполнении этого условия x_n+1 – приближенное значение корня на отрезке [0,1], найденное методом простой итерации с точностью e. На рис. 2.5. иллюстрируется применение метода простой итерации.

Теорема о сходимости и оценка погрешности

Пусть отрезок [a, b] содержит один корень уравнения  x = j(x), функция j(x) является непрерывно дифференцируемой на отрезке [a, b], переводит отрезок [a, b] в себя, и выполнено условие:

.

Тогда для любого начального приближения x₀Î[a, b] последовательность  сходится к корню уравнения y = j(x) на отрезке[a, b] и справедлива оценка погрешности:

.

Устойчивость метода простой итерации. При выполнении условий теоремы о сходимости алгоритм метода простой итерации является устойчивым.

Сложность метода простой итерации. Объем памяти ЭВМ, необходимый для реализации метода простой итерации, незначителен. На каждом шаге нужно хранить x_n, x_n+1, q иe.

Оценим число арифметических действий, необходимых для реализации метода простой итерации. Запишем оценку для числа n₀ = n₀(e) такого что, для всех n ³ n₀ выполняется неравенство:

Из этой оценки вытекает, что чем ближе q к единице, тем медленнее сходится метод.

Замечание. Не существует общего правила построения j(x) по f(x) так, чтобы выполнялись все условия теоремы о сходимости. Часто используется следующий подход: в качестве функции j выбирается функция j(x) = x + k× f(x), где k – константа.

При программировании метода простой итерации для остановки итерационного процесса часто требуют одновременного выполнения двух условий:

   и   .

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

2.5. Метод Ньютона

1. Пусть известен отрезок [a, b], который содержит один корень уравнения f(x) = 0. Функция  f(x)  является  дважды  непрерывно дифференцируемой на отрезке [a, b] (f(x) Î C²[a, b]). Функция f принимает на концах отрезка [a, b] значения разных знаков (f(a)×f(b) <0). Первая и вторая производные функции f не обращаются в ноль на отрезке [a, b] (f  ¢  ¹ 0, f  ¢¢ ¹ 0). При выполнении этих условий для уточнения корня можно использовать метод Ньютона

2. Формула метода:   .

3. Точка x₀ – начальное приближение – выбирается из условия: f(x₀)×f ¢¢ (x) > 0. В качестве x₀ выбирается, как правило, один из концов отрезка [a, b]:

если f(a)×f ¢¢ (x) > 0,     то x₀ = a;

если f(b)×f ¢¢ (x) > 0,     то x₀ = b.

Отметим, что, так как f ¢¢ (x) не меняет знак на отрезке [a, b] и f(a)×f(b) < 0, то на отрезке [a, b] выполнено только одно из предыдущих условий: либо f(a)×f ¢¢ (x) > 0, либо f(b)×f ¢¢ (x) > 0.

При выполнении этих условий последовательность {x_n} сходится к точному значению корня на отрезке [a, b].

4. Для метода Ньютона известны несколько условий остановки итерационного процесса. Рассмотрим одно из них: , где . При выполнении этого условия x_n+1 является приближенным значением корня уравнения  на отрезке [a, b], найденным методом Ньютона с точностью e. Условие остановки итерационного процесса вытекает из оценки погрешности для метода Ньютона: .

При программной реализации метода Ньютона, как правило, для остановки итерационного процесса требуется выполнение одновременно двух условий:

    и          .

Пример