1.      Метод простой итерации

 

Пусть требуется решить уравнение

f(x) = 0.

Для того чтобы можно было вести итерационный процесс, преобразуем это уравнение к равносильному ему уравнению вида:

x = g(x).                                                           (5.1)

Например, преобразовывать можно по одной из схем:

x= x - f(x),

x= x + f(x),

x= x - c f(x),

x= xh(x) f(x),

где спостоянная, неравная нулю, h(x) – функция необращающаяся в ноль в некоторой достаточно большой окрестности корня уравнения (5.1).

Пусть функция g(x) непрерывна в исследуемой области оси Ox. Пусть последовательность (xk) определяется формулой:

xk +1 = g(xk),                                                        (5.2)

где x0 – некоторое начальное значение из промежутка локализации корня. Если эта последовательность сходится к некоторому числуx, то в силу непрерывности функции g(x)  в пределе выполняется равенство

x = g(x),

т.о. x - корень  уравнения (5.1).

Процесс вычисления корняx уравнения (5.1) по формуле (5.2), начиная с некоторого x0, называется методом итерации или методом последовательного приближения.

Существование и единственность корня уравнения (5.2) основывается на принципе сжимающих отображений.

Определение 5.1. Непрерывная функция g(x) называется сжимающей на отрезке  [a, b], если

1)     " (x Î [a, b])  g(x)Î [a, b],

2)     $ (qÎ (0,1)) " (x1 , x2Î [a, b]) | g(x2) - g(x1)| £ q|x2 - x1|.

Сжимающая функция переводит отрезок [a, b] в отрезок [a1, b1]Ì [a, b], отрезок [a1, b1] в отрезок [a2, b2]Ì [a1, b1] и т.д. Получим последовательность отрезков,

[a, b] É [a1, b1] É [a2, b2] ÉÉ [ak, bk]É

длины которых убывают по закону |ak - bk| £ qk |a - b|. Поэтому по принципу Кантора имеется только одна точка x, которая принадлежит всем отрезкам одновременно и для ее выполняется равенство x = g(x). Она является неподвижной точкой функции g(x).

Теорема 5.1. Пусть функция g(x) определена и дифференцируема на отрезке [a, b], и выполняются условия:

1) " (x Î [a, b])  g(x)Î [a, b],

2)    $ (qÎ (0,1)) " (xÎ (a, b)) | g' (x) | £ q.

Тогда уравнение (5.1) имеет единственный на [a, b] кореньx, к которому сходится, определяемая по формуле (5.2), последовательность(xk), начинающаяся с любого x0 Î [a, b], при этом для любого k = 1, 2, … 'справедливы оценки погрешности

.                                (5.3)

Теорема 5.2. Пусть на отрезке [x0-r, x0+r] функция f(x) определена и дифференцируема и производная удовлетворяет неравенству

|g' (x) | £ q < 1.                                                                  (5.4)

Тогда если величина x0 Î [a, b] такова, что

| x0  - g' (x0) | £ r (1 - q),                                                       (5.5)

то на отрезке  [x0 - r, x0 + r] имеется единственный корень x  уравнения (5.1), к которому сходится, определяемая по формуле (5.2), последовательность(xk), начинающаяся с x0, при этом для любого k = 1, 2, … справедливы оценки погрешности (5.3).

Уравнение (4.1) привести к виду (5.2) можно осуществить многими, в том числе отмеченными выше способами. При этом необходимо получить уравнение вида (5.1), которое равносильно исходному и пригодно для проведения итерации. Для завершения расчета можно использовать правило | xk -1 - xk | £ (1- q )e/q Þ x » xk ±e.

Алгоритм нахождения корня методом итерации.

Ввод: Функция g(х), q - оценка производной g'(х), точность вычисления e корня, допуск d - малое число, связанное с реальной точностью вычисления g(х). Промежуток [a, b] существования корня.

Вывод: корень с уравнения.

c:=(a+b)/2;  

1.  d:= g(c);

если |c - d| <(q-1)e/q, то конец

в противном случае с:=d, идти к шагу 1.

Пример. Методом итерации найти корень уравнение 2xsin x 1 = 0 (точность 0,01) в интервале (0, 2). Имеем a = 1, b = 2, e = 0,01, d = 0,001. Преобразуем уравнение к виду  

х = 1 – 0,5sin x.

Имеем g (х) = 1 – 0,5sin x, g' (х) = –0.5 cos x, q = 0.5, c =1, (1-q)e/q = e.

Шаг

1

2

3

4

5

6

c

1

0,5793

0,7263

0,6679

0,6903

0,6816

f(c)

0,5793

0,7263

0,6679

0,6903

0,6816

0.6849

Корень уравнения: x = 1,68 ±0,01 .