Численные методы решения нелинейных уравнений

Если законы функционирования модели нелинейны, а моделируемые процесс или система обладают одной степенью свободы (т.е. имеют одну независимую переменную), то такая модель, как правило, описывается одним нелинейным уравнением.

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

Дано нелинейное уравнение:

$$f(x) = 0$$

Необходимо решить это уравнение, т. е. найти его корень $$\overline{x}$$.

(рис 4.1)

Если функция имеет вид многочлена степени m,

$$f(x)=a_0 x^m + a_1 x^{m-1} + a_2 x^{m-2} + \ldots + a_{m-1} x + a_m,$$

где ai - коэффициенты многочлена, $$i=\overline{1,m}$$, то уравнение f(x)=0 имеет m корней (рис. 4.2).

(рис 4.2)

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

Примеры:

$$arctgx + 1-x =0,$$ $$x-e^\frac{-x}{10}=0.$$

Такие уравнения обычно имеют бесконечное множество решений.

Как известно, не всякое уравнение может быть решено точно. В первую очередь это относится к большинству трансцендентных уравнений.

Доказано также, что нельзя построить формулу, по которой можно было бы решать произвольные алгебраические уравнения степени, выше четвертой.

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

Большинство употребляющихся приближенных методов решения уравнений являются, по существу, способами уточнения корней. Для их применения необходимо знание интервала изоляции [a,b], в котором лежит уточняемый корень уравнения (рис. 4.3).

(рис 4.3)

Процесс определения интервала изоляции [a,b], содержащего только один из корней уравнения, называется отделением этого корня.

Процесс отделения корней проводят исходя из физического смысла прикладной задачи, графически, с помощью таблиц значений функции f(x) или при помощи специальной программы отделения корней. Процедура отделения корней основана на известном свойстве непрерывных функций: если функция непрерывна на замкнутом интервале [a,b] и на его концах имеет различные знаки, т.е. f(a)f(b)<0, то между точками a и b имеется хотя бы один корень уравнения (1). Если при этом знак функции f'(x) на отрезке [a,b] не меняется, то корень является единственным на этом отрезке.

Процесс определения корней алгебраических и трансцендентных уравнений состоит из 2 этапов:

отделение корней, - т.е. определение интервалов изоляции [a,b], внутри которого лежит каждый корень уравнения;

уточнение корней, - т.е. сужение интервала [a,b] до величины равной заданной степени точности $$\varepsilon$$.

Для алгебраических и трансцендентных уравнений пригодны одни и те же методы уточнения приближенных значений действительных корней:

метод половинного деления (метод дихотомии);

метод простых итераций ;

метод Ньютона (метод касательных) ;

модифицированный метод Ньютона ( метод секущих );

метод хорд и др.

Метод половинного деления

Дано нелинейное уравнение:

$$f(x)=0$$

Найти корень уравнения, принадлежащий интервалу [a,b], с заданной точностью $$\varepsilon$$.

Для уточнения корня методом половинного деления последовательно осуществляем следующие операции:

Делим интервал пополам:$$t=\frac{a+b}{2} \text{ – координаты середины отрезка} [a,b];$$

В качестве нового интервала изоляции принимаем ту половину интервала, на концах которого функция имеет разные знаки рис 4.4(рис 4.4)

Для этого:

a) Вычисляем значение функции f(x) в точках a и t.

b) Проверяем: если f(a)f(t) < 0, то корень находится в левой половине интервала [a,b] (рис.4.4.а). Тогда отбрасываем правую половину интервала и делаем переприсвоение b=t.

c) Если f(a)f(t) < 0 не выполняется, то корень находится в правой половине интервала [a,b] (рис.4.4.б). Тогда отбрасываем левую половину и делаем переприсвоение a=t. В обоих случаях мы получим новый интервал [a,b] в 2 раза меньший предыдущего.

Процесс, начиная с пункта 1, циклически повторяем до тех пор, пока длина интервала [a,b] не станет равной либо меньшей заданной точности, т.е.$$\lvert b-a \rvert \le \varepsilon.$$

Схема алгоритма уточнения корней по методу половинного деления представлена на рис. 4.5.

(рис 4.5) Схема алгоритма уточнения корней по методу половинного деления

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

В ряде случаев весьма удобным приемом уточнения корня уравнения является метод последовательных приближений (метод итераций).

Пусть с точностью $$\varepsilon$$ необходимо найти корень уравнения f(x)=0, принадлежащий интервалу изоляции [a,b]. Функция f(x) и ее первая производная непрерывны на этом отрезке.

Для применения этого метода исходное уравнение f(x)=0 должно быть приведено к виду

$$x=\varphi(x)$$

В качестве начального приближения 0 выбираем любую точку интервала [a,b].

Далее итерационный процесс поиска корня строится по схеме:

$$x_1=f(x_0), \\ x_2=f(x_1), \\ \ldots \\ x_n=f(x_{n-1})$$

В результате итерационный процесс поиска реализуется рекуррентной формулой (4.3). Процесс поиска прекращается, как только выполняется условие

$$\lvert x_n-x_{n-1} \rvert \le \varepsilon$$

или число итераций превысит заданное число N.

Для того, чтобы последовательность х1, х2,…, хn приближалась к искомому корню, необходимо, чтобы выполнялось условие сходимости:

$$\lvert \varphi'(x) \rvert <1.$$ (рис 4.6) Геометрический смысл метода

Переходим к построению схемы алгоритма (рис. 4.7). Вычисление функции $$\varphi(x)$$ оформим в виде подпрограммы.

(рис 4.7) Схема алгоритма уточнения корня методом итераций

Метод Ньютона (метод касательных)

Рассмотренные ранее методы решения нелинейных уравнений являются методами прямого поиска. В них для нахождения корня используется нахождение значения функции в различных точках интервала [a,b].

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

Дано нелинейное уравнение:

f(x)=0

Найти корень на интервале [a,b] с точностью $$\varepsilon$$.

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

Выберем начальную точку x0=b (конец интервала изоляции). Находим значение функции в этой точке и проводим к ней касательную, пересечение которой с осью Х дает нам первое приближение корня x1.

(рис 4.8)

x1 = x0 – h0,

где

$$h_0= \frac{f(x_0)}{\tg(\alpha)}= \frac{f(x_0)}{f'(x_0)}.$$

Поэтому

$$x_1=x_0-\frac{f(x_0)}{f'(x_0)}.$$

В результате итерационный процесс схождения к корню реализуется рекуррентной формулой

$$x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}$$

Процесс поиска продолжаем до тех пор, пока не выполнится условие:

$$\lvert x_{n+1}-x_n \rvert \le \varepsilon$$

Упростим условие (4.7), исходя из (4.6). Получим:

$$\lvert \frac{f(x_n)}{f'(x_n)}\rvert \le\varepsilon.$$

Метод обеспечивает быструю сходимость, если выполняется условие:

$$f(x_0)\cdot f''(x_0) > 0,$$

т.е. первую касательную рекомендуется проводить в той точке интервала [a,b], где знаки функции f(x0) и ее кривизны f"(x0) совпадают.

Схема алгоритма уточнения корня метод Ньютона приведена на рис. 4.9

(рис 4.9) Схема алгоритма уточнения корня методом Ньютона

Модифицированный метод Ньютона (метод секущих)

В этом методе для вычисления производных на каждом шаге поиска используется численное дифференцирование по формуле:

$$f'(x)= \frac{\Delta f(x)}{\Delta x}$$

Тогда рекуррентная формула (4.6) будет иметь вид:

$$x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}=x_n-\frac {f(x_n) \Delta x}{\Delta f(x_n)}=\\ =x_n-\frac {f(x_n) \Delta x}{f(x_n+ \Delta x)-f(x_n)},$$

где $$\Delta x \approx \varepsilon$$

Метод хорд

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

При этом в процессе поиска семейство хорд может строиться:

а) при фиксированном левом конце хорд, т.е. z=a, тогда начальная точка х0=b (рис. 4.10а);

б) при фиксированном правом конце хорд, т.е. z=b, тогда начальная точка х0=a (рис. 4.10б);

(рис 4.10)

В результате итерационный процесс схождения к корню реализуется рекуррентной формулой:

для случая а)

$$x_{n+1}=x_n - \frac{f(x_n)}{f(x_n)-f(a)} (x_n - a);$$

для случая б)

$$x_{n+1}=x_n - \frac{f(x_n)}{f(x_n)-f(b)} (x_n - b);$$

Процесс поиска продолжается до тех пор, пока не выполнится условие

$$\lvert x_{n+1}–x_n\rvert \le \varepsilon \text{ или } \lvert h\rvert \le \varepsilon.$$

Метод обеспечивает быструю сходимость, если f(z)f"(z) > 0, т.е. хорды фиксируются в том конце интервала [a,b], где знаки функции f(z) и ее кривизны f"(z) совпадают.

Схема алгоритма уточнения корня методом хорд представлена на рис. 4.11.

(рис 4.11) Схема алгоритма уточнения корня методом хорд