- •§ 2. Решение нелинейных алгебраических уравнений с одной переменной
- •§2. Решение нелинейных алгебраических уравнений с одной переменной
- •2.1. Задача отделения корней. Уточнение корней методом половинного деления (метод дихотомии)
- •Методом хорд (секущих)
- •Методом касательных (Ньютона)
- •Методом итераций
- •Методом парабол
- •2.7. Методы ускорения сходимости
Методом итераций
Часто этот метод называют еще методом последовательных приближений.
Заменим уравнение (1.15) равносильным ему w(х) - х = =0,преобразовав для этого функциюF(х). Из этого уравнения получимw(х)= х и выберем любым способомх0 О [а, b], которое затем подставим в левую часть уравненияw(х0)= х1. Полученное значениех1снова подставим в левую часть и получимw(х1)= х2. Продолжая этот процесс, запишем последовательность чиселх1 , х2 , ..., xn, которая может либо сходиться, т.е.иметь предел, либо расходиться, т.е.не иметь предела. Тогда в соответствии с полученным результатом в первом случае этот предел назовем корнем уравнения (1.15), во втором случае сделаем вывод о невозможности получения решения данным способом. Оба этих варианта определяются теоремой сходимости итерационного процесса.
Теорема.Пусть на отрезке [а, b] имеется единственный корень уравнения х = w(х) и во всех точках этого отрезка производная F'(х) удовлетворяет неравенству |F’(х)|< q < 1. Если при этом выполняется и условие а < <w(х) < b, то итерационный процесс сходится, а за нулевое приближение х0 можно взять любое число из отрезка [а, b].
Последнее утверждение означает, что{хi} О [а, b]. Чем меньше|w'(х)|, тем лучше сходимость итерационного процесса.
Пусть теперь x- точное значение корня, ахk- приближенное. Попробуем оценить погрешность метода. Согласно теореме [Бахвалов, 1973а],q определяется из|w'(хk)| < q < 1. Тогда должно быть справедливо соотношение
|x -хk| < q(q - 1)-1 |хk - хk -1|.
Если положить, что xотличается отхkна величину,меньшую e, то|x- хk| < e и последовательность{хk} надовычислять до тех пор, пока не будут выполнены условия
q(q - 1)-1 |хk - хk-1 | <eили|хk - хk-1 |<e (q - 1)/q,
откуда можно сделать следующий вывод: так как уравнение F(х) = 0 приводится к виду w(х)= хразными способами, то для метода итераций следует выбрать такое уравнение дляw(х), для которого выполняется условие теоремы.
В заключение отметим, что при использовании метода простых итераций основным и, пожалуй, самым важным моментом является выбор функции w(х) в уравнениих = =w(х), эквивалентном исходному. Для метода итераций следует подбирать функциюw(х) так, чтобы обязательно выполнялось условие|w'(х)| < q < 1. При этом не нужно забывать, что скорость сходимости последовательности приближений {хi} к корнюxтем выше, чем меньше числоq.
Если предположить, что все условия для реализации расчетов по методу простой итерации выполнены, то программа (без проверок) может быть очень простой:
Function iter1 (x0: real; eps : real;
var k : integer; ki : integer) : real;
var x, y : real;
begin k := 0;
y := x0;
repeat x := y;
y := funcI (x);
inc (k);
until (abs(x-y) < eps) or ( k > ki); iter1 := x;
end.
Но если заранее неизвестно: выполняются условия или нет, то в процедуру надо включить дополнительную проверку, что не намного усложнит программу:
Function iter2 (x0: real; eps : real;
var k,L : integer; ki : integer) : real;
var x, y, eps1, eps2 : real;
begin k := 0;
y := x0; l := 0;
x := y;
y := funcI (x);
k := 1;
eps1 := abs (x-y);
repeat x := y;
y := funcI (x);
inc (k);
eps2 := abs (x-y);
if eps2 > eps1 then L := 1;
if k > ki then l := 2;
eps1 := eps2;
until (eps2 < eps) or ( l<>0 );
iter2 := x;
end.
Формальные параметры обеих процедур. Входные:x0 (типreal) - начальное приближение корня;eps(типreal) - параметр, используемый для окончания итерационного процесса;ki(типinteger) - максимальное количество разрешенных итераций;func- имя внешней процедуры-функции (типreal), возвращающей значениеw(х).Выходные:x0 (типreal) - приближенное значение корня, вычисленное с заданной точностью;k(типinteger) - количество выполненных итераций;l(типinteger) - параметр, контролирующий работу процедуры (только вiter2):l= 0 - вычисления выполнены с заданной точностью и вx0 находится значение корня;l= 1 - вычисления прерваны из-за того, что итерационный процесс стал расходиться (не выполнены условия применимости метода, сформулированные в теореме);l = 2 - слишком много итераций (больше, чемki). Следует выбрать другое приближение, более близкое кx, или подобрать иную функциюw(х).
Для проверки процедуры методом итераций уточнялся корень с точностью до 0,00001 для уравнения F(х) = 5х3- - 20х+ 3.
Для отделения корней исследовалась производная уравнения F '(х) =15х2 - 20, корни которой легко определились аналитически: это. Определим знаки функции на интервалах
]-; -]; [-;]; [; +[.
Таблица 1.11
Параметр |
Характеристики интервалов | ||||
Интервал |
- 3 |
-2 |
0 |
+ 1 |
+ 2 |
sign ( F (x) ) |
- |
+ |
+ |
- |
+ |
Следовательно, корни расположены наинтервалах [-3; -2]; [0; 1] и [1; 2]. Теперь уравнениеF(х) = 0 следует привести к видух = w(х), что можно сделать разными способами:
х = х +(5х3- 20х +3); w1(х) = 5х3- 19х+ 3;
х = (5х3+ 3) / 20; w2 (х) = (5х3+ 3) / 20;
х = ; w3 (х) = .
Определим теперь, какая из полученных w(х) подходит к использованию в итерационном процессе
;
.
Методом итераций уточним корень на отрезке [0, 1], выбрав вторую форму представления функции w(x).Два других корня уравнения находим по теореме Виетта. За начальное приближение возьмемх0 = 0,75 иq0 = х0 = 0,75. Пользуясь формулой для вычисления погрешности, определимeтак,чтобы разность между двумя последовательными приближениями была бы заданной точности:
|хn - хn-1| < 0.00001(1 — 0.75) / 0.75 =
= 0.00001 — 0.25/0.75 = 0.000003,
т.е. когда |хn - хn-1| < 0.000003, то итерационный процесс можно завершить, считая, что заданная точность достигнута.
Процедура-функция, по которой вычисляют w(х), имеет вид
Function funcI (x :real) : real;
begin funcI := (5.0*x*sqr(x) + 3) / 20.0; end.
Результаты работы программы можно оформить так (табл. 1.12).
Таблица 1.12
Уточнение корня методом итераций на [0, 1] | ||
xi |
w (xi ) |
Итерация |
0.100000 0.150250 0.150848 0.150858 |
0.150250 0.150848 0.150858 0.150858 |
k = 1 k = 2 k = 3 k = 4 |
Два остальных корня вычисляют по теореме Виетта: F(х) = (х- 0.1514)(5х2+ 0.757х- 19.8853),откудах2их3определяются аналитически.
Уточним корни на отрезках [-3; -2] и [1; 2] любым изученным ранее методом, например дихотомии или комбинированным. Используя программы из п. 2.2 и 2.3, получаем оставшиеся два корня (табл. 1.13).
Таблица 1.13
-
Интервал отрезка
[-3; -2]
[1; 2]
Mетод хорд
Mетод касат.
Итерация
Метод хорд
Метод касат.
Итерация
-2.057690
-2.068692
-2.071076
-2.071157
-2.071157
2.373913
2.119586
2.072719
2.071159
2.071157
k = 1
k = 2
k = 3
k = 4
k = 5
1.912281 1.920268 1.920299 1.920299
1.925000
1.920317
1.920299
1.920299
k =1
k =2
k =3
k =4
x = -2.071157; F(x) = 0.0000039561; k = 5
x = 1.920299; F(x) = -0.0000000159; k = 4
2.6. ПРИБЛИЖЕННОЕ РЕШЕНИЕ УРАВНЕНИЯ F(х)=0