Метод итераций
Предварительно необходимо преобразовать уравнение f(x) = 0 к виду x = (x).
В качестве начального приближения x0 выбирается любая точка интервала [a,b].
Дальнейшие приближения определяются следующим образом :
x1= (x0) ,
x2= (x1) ,
.
.
.
xn= (xn-1) ( n=1,2,… ) . (1.4)
Геометрическая интерпретация метода
Рис. 1.8 Рис. 1.9
Корень уравнения x= (x) является абсциссой точки пересечения прямой y=x с кривой y= (x).
Если последовательность приближений сходящаяся ( т. е. существует предел ), то
,
.
Причем последовательность может сходиться монотонно : <...<xn<...<x2<x1<x0 ( рис. 1.8) или колебательно : x1<x3<...<<...<x2<x0 ( рис. 1.9 ) .
Вид
решения зависит от знака
( табл. 1.7 ) .
Таблица 1.7
-
Вид решения
sign
“лестница”
+
“спираль”
-
Однако применение метода не всегда приводит к желаемому результату ( т. е. процесс может расходиться ( см. рис. 1.10 , рис. 1.11 )) .
Рис. 1.10 Рис. 1.11
Достаточное
условие сходимости
итерационного процесса
.
Пример. f(x) = x3 - x - 1 = 0 ;
1 [ 1,2 ] .
1 вариант : x = x3 - 1;
= 3x2 3 при 1 x 2.
Условие сходимости не выполнено.
2
вариант :
x
=
;
=
<
при 1
x
2.
Условие сходимости выполнено.
Эквивалентное преобразование уравнения f(x) = 0 к виду x = (x)
f(x) = 0 f(x) = 0 x = x - f(x) ,
где - параметр;
x - f(x) = (x).
Выбор
: если 0 <
m
(x)
M,
где m- min,
M- max,
то необходимо 0 = 1 - (x) q < 1;
0 1 - M 1 - m q;
=
; q
= 1 -
.
Оценка погрешности приближения
f(x) = x - (x),
(x) = 1- 1 - q,
xn - (xn) = f(xn) - f( ) = (n) xn- (1 - q) xn - ,
xn
-
.
Учитывая, что xn+1 = (xn)
-
xn
.
Т.
к. xn+1
- xn
=(xn)
- (xn-1)=
(xn
- xn-1)
q
(xn
–
xn-1),
то
- xn
xn
- xn-1
.
Итерационный процесс прекращается при выполнении неравенства
xn
- xn-1
<
.
Более грубая оценка
xn - xn-1 < или ( xn - xn-1 )2 < 2.
Достоинство метода. Надежность (обладает самокоррекцией): ошибка в вычислениях, при которой х остается в пределах [a, b], не влияет на конечный результат, т.к. ошибочное значение можно рассматривать как новое х0 .
Пример. Необходимо методом итераций уточнить корень [0;1] уравнения
х 3 - 3х +1 = 0 с точностью 10 –3 (табл. 1.8).
Преобразованное уравнение
.
Таблица 1.8
n |
х n |
(x n) |
0 |
0 |
0,3333 |
1 |
0,3333 |
0,3457 |
2 |
0,3457 |
0,3471 |
3 |
0,3471 |
0,3473 |
4 |
0,3473 |
|
х 4 - х 3 <
0,347 .
Замечания. 1. Рассмотренные методы уточнения корней одинаково применимы как к алгебраическим , так и к трансцендентным уравнениям .
2. Операция отделения корней значительно сложнее для трансцендентных уравнений , чем для алгебраических .