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

 

В отличие от двух предыдущих этот метод позволяет найти не один, а несколько корней, если таковые имеются на выбранном интервале. Он предоставляет возможность локализовать каждый из искомых корней (определить все отрезки [ 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. Вычислить y 2: = 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.