3. Решение нелинейных уравнений

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

Простейшим и надежным алгоритмом уточнения корня является метод деления отрезка пополам. Пусть на отрезке [a, b] функция f(x) непрерывна и на концах этого отрезка имеет разные знаки, т.е. f(a)f(b)<0. Очевидно, что середина отрезка служит приближением к корню уравнения (4) с точностью (b–a)/2. В середине отрезка x₁=(a+b)/2 определяется знак функции f(x), затем выбирается та половина отрезка, на концах которой функция f(x) принимает значения разных знаков, и деление повторяется. Если требуется найти корень с точностью , то деление отрезка пополам продолжается до тех пор, пока длина отрезка не станет меньше 2. Тогда середина последнего отрезка даст значение корня с требуемой точностью.

Алгоритм метода:

1. Найти .

2. Вычислить .

3. Если , то принять , иначе

4. Проверить условие , если оно выполняется, перейти к пункту 1, если оно не выполняется, закончить вычисления, считая корнем x с точностью .

Метод деления отрезка пополам имеет линейную скорость сходимости.

Пример. Решить уравнение 0,5^x+2=(x–2)².

Решение в системе компьютерной математике Maple:

1) Задаем функцию f(x)= 0,5^x+2–(x–2)²

> f:=t->0.5^t+2-(t-2)^2;

2) Отделяем корни, для этого строим график функции f(x). Поскольку заранее неизвестно, на каком промежутке (или промежутках) расположены корни уравнения (нули функции f(x) ), график функции сначала строим на достаточно большом отрезке, например на отрезке [–20,20], а затем локализуем его для лучшей визуализации корней.

> plot(f(t),t=-20..20);

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

> plot(f(t),t=-10..20);

Чтобы еще точнее локализовать корни, строим график на интервале от –6,5 до 5:

> plot(f(t),t=-6.5..5);

Видим, что график пересекает ось x в трех точках, т.е. имеем три корня. Сначала найдем первый корень, лежащий на отрезке [–7,–5].

3) Присвоим значения переменным

> eps:=0.001: a:=–7: b:=–5: n:=0:

4) Ниже реализован основной алгоритм метода в виде цикла

> while (b-a)>eps do

x:=(a+b)/2;

if evalf(f(x)*f(a))>0 then a:=x else b:=x fi;

n:=n+1;

od:

5) Вывод результата (x – корень, n – число итераций)

> evalf(x); n;

–5.926818850

14

Итак, первый корень равен –5.927, для его нахождения потребовалось 14 итераций. Чтобы найти второй корень, расположенный вблизи нуля, нужно выполнить шаги 3)–5), придав переменным a и b соответственно значения –1 и 1. Аналогично ищется третий корень, лежащий между a=3 и b=4.

Метод простой итерации

Метод простой итерации применяется к решению нелинейного уравнения с выделенным линейным членом вида

x = (x) (6)

и состоит в построении последовательности {x_n}, начиная с некоторого заданного начального значения x₀ по правилу

x_n+1 = (x_n)

Если имеет на отрезке S={x: |x–x₀|<} непрерывную производную, то достаточным условием сходимости метода простой итерации является выполнение неравенства

|(x)|<1 (x S) (7)

Если исходное уравнение имеет вид (4), то для применения метода предварительно следует преобразовать его к эквивалентному виду (5), например, следующим образом. Умножим уравнение f(x)=0 на некоторую постоянную  и сложим с тождеством x=x. Получим эквивалентное уравнение x=x+f(x), обозначим правую часть (x)= x+f(x). Подбором  добиваемся, чтобы (x) в окрестности корня удовлетворяла условию (7).

Метод простой итерации относится к классу методов с линейной скоростью сходимостью.

> restart;

> f:=t->0.5^t+2-(t-2)^2;

> x0:=1.;phi:=x+lambda*f(x);

> u:=diff(phi,x): r:=subs(x=x0,u): evalf(");

> solve(abs(r)<1,lambda);

RealRange(Open(–1.209609323), Open(0))

> eps:=0.0001: n:=0:

> while abs(f(x0))>eps do

x0:=subs(lambda=-.15,x=x0,phi);

n:=n+1;

od:

> evalf(x0); n;

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

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

, , n = 0, 1, 2,…

Геометрически x_n+1 является значением абсциссы точки пересечения касательной к кривой y=f(x) в точке (x_n, f(x_n)) с осью абсцисс, поэтому метод Ньютона называют также методом касательных.

Сходимость метода Ньютона квадратичная (при условии f(x*)0 ).

> restart;

> f:= t->0.5^t+2-(t-2)^2; fd:=t->D(f)(t);

> x0:=1.: n:=0: eps:= 0.0001:

> while abs(f(x0))>eps do

x:=x0-f(x0)/fd(x0);

x0:=x; n:=n+1;

if n=50 then break fi;

od:

> evalf(x);

> n; x-x0;

Метод секущих

В методе Ньютона еа каждом шаге нужно вычислять значения функции и производной. На практике часто применяются методы, требующие вычисления лишь значений функции. Заменив производную f(x_n) в методе Ньютона разделенной разностью по двум точкам x_n и x_n+h_n, получим итерационную формулу

, n = 0, 1, 2,… (8)

Формула (8) называется методом секущих (хорд) для решения уравнения вида f(x)=0.

Приближение является абсциссой точки пересечения секущей прямой, проведенной через точки (x_n, f(x_n)) и (x_n+h_n, f(x_n+h_n)), с осью x. Часто берут h_n=x_n+1–x_n, тогда формула (8) принимает вид

, n = 0, 1, 2,…

> restart;

> f:=t->exp(-t)-sin(t);

> x0:=1.: eps:=0.0001: h:=eps: n:=0:

> x:=x0-h*f(x0)/( f(x0+h)-f(x0) );

> while abs(f(x))>eps and abs(x-x0)>eps do

h:=x-x0; x0:=x;

x:=x0-h*f(x0)/( f(x0)-f(x0-h) );

n:=n+1;

> od:

> evalf(x);n;

Если известны числа a и b, такие, что f(a)f(b)<0 , т.е. заранее известно, что на отрезке [a,b] существует корень уравнения, то целесообразно использовать алгоритм

1. Найти .

2. Вычислить .

3. Если , то , иначе

4. Проверить условие , если оно выполняется, перейти к пункту 1, если оно не выполняется, закончить вычисления, считая корнем x с точностью .

> restart;

> f:=t->exp(-t)-sin(t);

> eps:=0.001: a:=0: b:=2.: n:=0: x:=(a+b)/2:

> while abs(f(x))>0.0001 do

x:=x-(b-a)*f(x)/( f(b)-f(a) );

if evalf(f(x)*f(a))>0 then a:=x else b:=x fi;

n:=n+1;

od:

> evalf(x);n;