Уточнение корней уравнений
Для численного решения алгебраических уравнений разработано множество итерационных методов (методов последовательного приближения к точному значению) уточнения корня. Задача ставится так: при заданном одном или двух (зависит от метода) начальных приближениях корня уравнения F(X)=0 получить приближение корня с заданной точностью ε.
Требуемая точность ε определяет условие завершения итерационного процесса, которое задаётся отношением |Xn-Xn-1| < ε, где Xn и Xn-1 – соседние приближения корня, полученные на (n-1) –м и n–м шагах его уточнения, а начальные (грубые) приближения корней можно найти, например, по результатам табулирования функции F(X).
Метод простых итераций
Для уточнения корня уравнения вида F(X)=0 его следует преобразовать к уравнению X=G(X). Исходными данными для уточнения корня являются требуемая точность ε и начальное приближение X0. Очередное приближение X1 корня вычисляется на основе текущего приближения X0 по формуле X1=G(X0) (на первом шаге уточнения корня Х0 представляет начальное приближение), после чего X0 получает значение X1 и процесс повторяется, пока модуль разности между Х0 и Х1 больше ε.
|
|
Применение метода приводит к решению, если |G'(Х)|<1 внутри интервала, содержащем корень уравнения.
Пример. Пусть известно, что при заданном начальном приближении корня X0 метод простых итераций обеспечит получение решения уравнения X=(X-0,1)4 +0,1. Тогда для нахождения корня с заданной точностью ε можно использовать следующий фрагмент программы.
uses
SysUtils, Math;
var
X0, X1, Eps, dX: Extended;
begin
ReadLn(X0,Eps);
repeat
X1:=IntPower(X0-0.1, 4)+0.1;
dX:=Abs(X0-X1);
X0:=X1
until dX<Eps;
WriteLn('С точностью ',Eps, ' корень равен ',X0);
............
end.
Метод не всегда обеспечивает нахождение корня. Так, при ε =10-3 и X0<1,1, где в окрестности корня 0,1 |G'(X)| = |4(X-0,1)3 |<1 будет найден этот корень (как будет проходить уточнение корня, показано стрелками на рис.3.1). Но в окрестности корня 1,1 (1,1 – второй корень уравнения), где |G'(X)| >1 каждый шаг процесса будет приводить к удалению от корня, что, в конечном счете, приведет к переполнению разрядной сетки машины и аварийному останову.
Чтобы найти корень уравнения X=G(X) при условии |G'(X)|>1, его следует преобразовать к виду X=H(X), где H(X) - обратная относительно G(X) функция, и использовать для поиска корня. С учетом сказанного, изменим текст фрагмента программы, чтобы была возможность находить все корни уравнения X=(X-0,1)4 +0,1, при любых начальных приближениях, когда |G'(X)|¹0.
uses
SysUtils, Math;
var
X0, X1, Eps, dX, P: Extended;
begin
ReadLn(X0,Eps);
P:=Abs(4*IntPower(X0-0.1,3));
if P=0 then
begin
WriteLn('Нарушено условие применимости метода!');
ReadLn;
Halt;
end
else if P<1 then
|
|
//Использование исходной функции
repeat
X1:=IntPower(X0-0.1, 4)+0.1;
dX:=Abs(X0-X1);
X0:=X1
until dX<Eps
else if P>1 then
//Использование обратной функции
repeat
X1:=Power(X0-0.1,0.25)+0.1;
dX:=Abs(X0-X1);
X0:=X1
until dX<Eps;
WriteLn('С точностью ',Eps, ' корень равен ',X0);
.......
end.
В некоторых случаях возможно зацикливание – бесконечное выполнение цикла программы (например, для уравнения X =1/X) или медленная сходимость процесса (например, для уравнения X = 1/(X-10-6).
Чтобы обеспечить информативность программ при зацикливании или очень медленной сходимости, в программах вводят ограничения на число итераций, и если за заданное число шагов заданная точность не достигается, то процесс останавливается и выдается соответствующее сообщение.
Пример. Составить фрагмент программы для решения следующей задачи. Найти корень уравнения X = 1/(X-10-6) с заданной точностью ε. Если за заданное число N шагов точность не будет достигнута, то прекратить выполнение программы и вывести с пояснениями модуль разности между двумя последними приближениями, значение ε и значение N, иначе вывести найденное значение корня и число шагов, за которое оно было найдено.
var
X0, X1, Eps:Extended;
I, N:Integer;
F:Boolean;
begin
ReadLn(X1,Eps,N);
F:=False;
for I:=1 to N do
begin
X0:=X1;
X1:=1/(X0-1E-6);
F:=Abs(X0-X1)<Eps;
if F then
//Решение найдено
break;//Выход из цикла
end;
if F then
WriteLn('Корень X0 = ',X0:12,' найден за ',i,' шагов')
else
WriteLn('Заданная точность ',Eps:0,' не достигнута за '
,N,' шагов');
.......
end.
Выполнив эту программу при X0=0,5, ε =10-3, N=5000000 можно убедиться, что после 5000000 итераций заданная точность достигнута не будет.