19.2.3. Метод прохождения отрезка с переменным шагом

В отличие от двух предыдущих этот метод позволяет найти не один, а несколько корней, если таковые имеются на выбранном интервале. Он предоставляет возможность локализовать каждый из искомых корней (определить все отрезки [a,b]). Сами корни находят одним из первых двух методов.

Суть метода заключается в следующем.

1. Выбирается интервал [А, В] значений аргумента Х, на котором ищутся корни.

2. Определяется начальное значение шага Н = (В - А)/ n, где n — начальное количество точек на интервале.

3. Проходят интервал [А, В] с шагом Н, вычисляя значения функции f(x) и f(x+H).

4. Если вычисленная пара значений функции имеет разные знаки, корень локализован. Его можно определить, например методом Ньютона. После нахождения корня отступают от него на величину шага Н.

5. Уменьшают шаг, например: Н:= Н / 2

6. Пункты 3 — 5 выполняют до тех пор, пока не будут найдены все корни.

Алгоритм нахождения корня описанным методом, который предполагает, что в программе будет использована функция f(x) и ее производная Prf(x), а также процедура нахождения корня уравнения методом Ньютона, приведен ниже.

1.1. Ввести А, В и Е.

1.2. Ввести Предполагаемое количество корней.

1.3. Вычислить начальный шаг Н = (В - А)/ n.

2. Повторять

2.1. Найдено_корней:= 0.

2.2. Х:= А.

2.3. Пока Х < B выполнить.

2.3.1. Вычислить у1:= f(X);

2.3.2. Вычислить y2:= f(x+H);

2.3.3. Если у1 и у2 имеют разные знаки, то

а) положить Левая_граница:= Х;

б) положить Правая_граница:= Х + Н;

в) найти корень методом Ньютона и вывести его;

г) Найдено_корней:= Найдено_корней + 1;

2.3.4. Х:= Х + Н;

2.4. Н:= Н / 2;

Пока не будет (Предполагаемое = Найдено_корней) Или (Н  Е).

3. Закончить.

Программа для этого алгоритма будет иметь вид

Program Roots;

Const

n= 20; { начальное количество точек на интервале }

Var

A, B, X, y1, y2, lev, Prav, E : Real;

Predpol, Naideno: Integer; { количества корней }

Function f(x: Real): Real;

Begin

f:= { здесь должна быть формула для вычисления функции}

End;

Function Prf(x: Real): Real;

Begin

Prf:= { здесь будет формула для вычисления производной}

End;

Procedure Newton(Lev,E: Real; Var x:Real);

{ нахождение корня методом Ньютона }

{ Lev - левая граница, x - корень }

Var

Y, xn: Real;

Begin

x := Lev;

{ вычисление корня }

Repeat

xn := x-f(x)/Prf(x);

y := Abs(xn-x);

x := xn;

Until y <= E;

X:= xn;

End;

Begin

Writeln('Введите интервал нахождения корней и погрешность');

Readln(A, B, E);

Writeln('Введите предполагаемое количество корней');

Readln(Predpol);

{ Начальный шаг }

H:=(B-A)/2;

{ Поиск корней }

Repeat

Naideno:=0; { найдено корней }

X:=A;

While x < B do

Begin

Y1:= f(x);

Y2:= f(x+H);

If ((y1>=0) And (y2<0))Or((y1<0) And (y2>=0)) then

Begin

{ корень локализован }

Lev:= x;

Newton(Lev, E, x);

Y1:= f(x);

Writeln('Корень = ', Xsl:8:4);

Writeln('Функция = ', y2:10:7);

End;

X:= x + H;

End;

H:= H / 2;

Until (Predpol = Naideno) Or (H <= E);

If Predpol <> Naideno Then

Writeln('Количество корней задано неверно');

Writeln('Работа окончена');

Readln;

End.