19.2. Решение уравнений приближенными методами

В общем виде уравнение может быть записано так:

f(x)=0,

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

• метод деления отрезка пополам;

• метод Ньютона и

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

19.2.1. Метод деления отрезка пополам

Это — наиболее простой метод, позволяющий найти корень для функции любого вида, если только правильно выбран интервал, на котором он существует. Метод использует известное из математики свойство, которое заключается в следующем. Если на некотором отрезке функция меняет знак, то на этом отрезке она пересекает ось Х, т.е. имеет корень.

Поиск корня осуществляется следующим образом.

1. Выбирается интервал [a,b] значений аргумента Х, на котором ищется корень. (На этом интервале, как отмечалось выше, функция должна менять знак).

2. Начальное значение корня X₀ принимается равным левой (a) или правой (b) границе интервала.

3. Вычисляется очередное приближение по формуле

Х = (Правая_граница - Левая_граница)/2.

4. Определяются значения функции f на одной из границ отрезка (например, левой) и в точке очередного приближения Х.

5. Если эти значения имеют разные знаки, то одну из границ (правую — см. п. 4) переносят в точку Х.

Пункты 3 — 5 повторяют до тех пор, пока разность между двумя соседними значениями Х не станет меньше или равно заданной погрешности Е. Последнее приближение Х считается корнем.

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

Алгоритм

1. Ввести a, b и Е.

2. Найти корень функции f(x) на отрезке [a,b].

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

Уточненный алгоритм, в котором предыдущее и следующее приближения корня обозначены Х_пред и Х_след, можно представить в виде.

1. Ввести a, b и Е.

2.1. Левая_граница:= a;

2.2. Правая_граница:= b;

2.3. Х_пред:= Левая_граница;

2.4. Повторять

2.4.1. Х_след:= (Правая_граница - Левая_граница)/2.

2.4.2. у1:= f(X_пред).

2.4.3. у2:= f(Х_след).

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

Правая_граница:= Х_след

Иначе

Левая_граница:= Х_след

2.4.5. у:= |Х_след - X_пред|

2.4.6. X_пред := Х_след

Пока не будет у  Е.

2.5. Вывести Х_след и у2.

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

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

Program Div2;

Var

Xsl, Xpr, a, b, E, y1, y2, Lev, Prav, y: Real;

Function f(x: Real): Real;

Begin

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

End;

Begin

Writeln('Введите границы отрезка и погрешность');

Readln(a, b, E);

Lev:= a;

Prav:= b;

Xpr:=Lev;

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

Repeat

Xsl:= (Prav - Lev)/ 2;

Y1:= f(Xpr);

Y2:= f(Xsl);

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

Prav:= Xsl

Else

Lev:= Xsl;

Y:= Abs(Xsl - Xpr);

Xpr:= Xsl;

Until y <= E;

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

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

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

Readln;

End.

19.2.2. Метод Ньютона

Этот метод еще называют методом касательных. Он позволяет быстрее найти корень (сходится за меньшее количество приближений), чем предыдущий. Метод заключается в следующем.

1. Выбирается интервал [a,b] значений аргумента Х, на котором ищется корень. На этом интервале функция должна менять знак.

2. Начальное значение корня X₀ принимается равным левой (a) или правой (b) границе интервала.

3. Вычисляется очередное приближение по формуле

Х_след = Х_пред – f(Х_пред)/f ^'(Х_пред)

4. Если |Х_след - Х_пред| <= E, то Х_след – корень, в противном случае

присвоить значение Х_след переменной Х_пред и перейти к п. 3.

В отличие от метода деления отрезка пополам рассмотренный алгоритм позволяет определить корень не для любой функции, а если:

1) f(x) дифференцируема;

2) f ^'(x) ≠ 0 в Е-окрестности корня.

Неудачный выбор Х₀ может привести к тому, что приближения "расходятся" от точки корня.

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

Обозначим:

Х_o => x0; E => E; Х_пред => x; Х_след => xn

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

Program Newton;

Var

y, x0, X, xn, E : Real;

Function f(x: Real): Real;

Begin

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

End;

Function Prf(x: Real): Real;

Begin

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

End;

Begin

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

Readln(a, E);

x := a;

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

Repeat

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

y := Abs(xn-x);

x := xn;

Until y <= E;

Writeln('Корень = ',xn:8:4,' разность = ',y:8:6);

Y:=f(x);

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

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

Readln;

End.

Можно определить количество приближений (итераций), оно равно числу повторений цикла.