Вторая пачка часть 90
со¬от¬вет¬ст¬вующие подпро¬грам¬мы).
Итоговая точка, получаемая алгоритмом, за¬пи¬сы¬ва¬ет¬ся в виде b + p/q, но деление не вы¬пол¬ня-ет¬¬ся до тех пор, пока оно не станет безопасным и дейс¬т¬ви¬тельно не¬об¬ходимым, так как если будет вы¬бра¬на точ¬ка по методу би¬сек¬ций, то деление воб¬ще не нуж¬но.
Версия алгоритма Брента, во-первых, всегда сх¬дит¬ся, да¬же при плавающей арифметике. Во-втрых, ко¬ли¬чес¬тво итераций не может стать больше чис¬ла
,
где tol1 := 0.5*tol + 2.0*eps*abs(B). В-третьих, нуль R, по¬лу¬чаемый алгоритмом, таков, что FUNC га-ран¬ти¬рованно ме¬няет знак в определенном ин¬тер¬ва¬ле, при¬бли¬зи¬тель¬но совпадающим с
[R - exp(tol*ln2), R + exp(tol*ln2)].
В-четвертых, сам Брент тщательно проверял свой а묬¬¬го¬ритм на самых разнообразных функциях и устବ¬¬¬новил, что в типичном случае для гладкой фунꬬ¬¬¬ции требуется не более 10 итераций. В об¬щем сл󬬬чае Брент ни разу не встретил функции, для ко¬т¬рой количество итераций бы¬ло больше трех¬знач¬-ного чис¬ла. Более подробно смот¬рите работу Брента (1973).
Формальные параметры процедуры. Входные: ax, bx (тип real) - определяют отрезок, на ко-то¬ром ищется ко¬рень уравнения; tol (тип real) - точность, с ко¬то¬рой дол¬жен быть определен корень урав¬не¬ния. Вы¬ходные: про¬це¬дура-функ¬ция возвращает на鬬денное с заданной точ¬нос¬тью значение корня на отрезке [ax, bx].
Описанная процедура выглядит:
FUNCTION ZEROIN (AX, BX, TOL : REAL) : REAL;
LABEL 20, 30;
VAR A,B,C,D,E,EPS,FA,FB,FC,TOL1,XM,P,Q,R,S:REAL;
DN : BOOLEAN;
BEGIN EPS := 1.0;
DN := FALSE;
REPEAT
EPS := EPS / 2.0;
TOL1 := 1.0 + EPS;
UNTIL TOL1 <= 1.0;
A := AX;
B := BX;
FA := FUNC (A);
FB := FUNC (B);
20: C := A;
FC := FA;
D := B - A;
E := D;
REPEAT
IF ABS (FC) < ABS (FB) THEN
BEGIN A := B;
B := C; C := A;
FA := FB; FB := FC;
FC := FA;
END;
{*** ПРОВЕРКА СХОДИМОСТИ ***}
TOL1 := 2.0*EPS*ABS(B) + 0.5*TOL;
XM := 0.5 * (C-B);
IF ABS (XM) <= TOL1 THEN DN := TRUE
ELSE
IF FB=0
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
