1.4. Метод простых итераций.
Пусть задано уравнение f(x)=0, где f(x) – непрерывная функция. Чтобы найти действительные корни этого уравнения, заменим его равносильным:
x=(x). (4)
Теперь, чтобы решить уравнение (4) применяют метод последовательных приближений (метод итерации). Выбирают некоторое начальное приближение x0 и последовательно вычисляют следующие приближения:
xk=(xk-1), k= 1.2,... (5)
Сходимость последовательности {хk} обеспечивается соответствующим выбором функции (х) и начального приближения х0. Выбирая по-разному функцию (х), можно составит разные итерационные методы решения уравнения (4).
а) 0<’ (x) <1;
б)'-1<’ (x) <0;
в)’ (x) >1;
г)’ (x) <-1
Рисунок 1. – Геометрическое представление метода итераций
Метод итерации имеет простой геометрический смысл. Построим графики функций у=х и у=(х). Абсцисса точки сечения графиков этих функций является корнем уравнения (4) (рис. 1).
На отрезке [а; b] произвольно выбираем точку х0 и проводим через нее прямую, параллельную оси ординат до пересечения с кривой у=(х) в точке A0 (x0, (x0)). Из точки А0 проведем прямую, параллельную оси абсцисс, до пересечения с прямой y=x. В результате получим точку В1 с ординатой (x0). Спроектировав точку B1 на ось Ох, находим абсциссу x1=(x0). Аналогично через х1 проводим прямую, параллельную оси ординат, до пересечения с кривой у=(х) в точке A1 (x1, (x1)). Из точки А1 проводим прямую, параллельную оси абсцисс, до пересечения с прямой у=х в точке B2 (x2, (x1)), абсцисса которой х2=(х1) и т.д. В результате совместные абсциссы точек A1 и B1, A2 и B2 есть последовательными приближениями x1, x2, x3... корня х*.
Если |' (х)|< 1, то последовательные приближения xk сходятся к корню х*, если |' (х)|> 1, то последовательные приближения отдаляются от него.
Скорость сходимости зависит также от выбора начального приближения x0. Чем ближе к корню х* выбрано x0, тем быстрее будет найден результат.
Процесс итераций можно закончить, если будет выполнено следующее неравенство
|xk – xk-1|<.
1.5 Метод Ньютона.
Пусть уравнение f(х)=0 на отрезке [а; b] имеет изолированный корень x*, то есть f (a) f (b) < 0, а функции f (x) и f' (x) непрерывны и сохраняют свой знак на [a; b].
Пусть хk - k-е приближение корня. Разложим f (х) в ряд Тейлора в окрестности точки хk.
.
Вместо уравнения f (х)=0 рассмотрим уравнение
f (xk) +f’ (xk)(x-xk)=0,
Которое учитывает только линейную относительно х — хk часть ряда Тейлора. Разрешив его относительно x, получим
.
Взяв найденное значение х за следующее приближение, получим
,
k=0.1, 2, …. (6)
Формула
(6) определяет
метод Ньютона.
Он имеет простую геометрическую
интерпретацию. Значение, хk+1
является абсциссой точки пересечения
касательной
с кривой у=f(x)
в точке (xk,
f(xk))
(рис. 2). Поэтому метод Ньютона называют
еще
методом касательных.
Из рис.2 видно, что последовательные
приближения сходятся к корню х* монотонно.
За начальное приближение в методе Ньютона следует брать точку
x0
[a; b],
в которой
.
Достаточные условия сходимости метода Ньютона дает такая теорема.
Теорема. Пусть на отрезке [a; b] функция f (х) имеет непрерывные с устойчивыми знаками производные f’(x) 0, f'’(x)0 и f(a)f(b)<0. Тогда существует такая окружность R [a; b] корня х* уравнения f(x)=0, что для любого x0 R последовательность {xk}, вычисленная по формуле (6), сходится к корню х*.
Преимущество метода Ньютона перед методом итерации в том, что он имеет более высокую скорость сходимости.
Недостатком метода Ньютона является то, что на каждой итерации нужно вычислять не только значение функции f(х), но и значение ее производной f' (х).