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

Уравнение типа F (x)=0 или x=f (x) называется нелинейным. Решить уравнение это значит найти такое x, при котором уравнение превращается в тождество. В общем случае уравнение может иметь 0; 1; 2;??? корней. Рассмотренные ниже численные методы решения нелинейных уравнений позволяют находить один корень на заданном интервале [a, b]. При этом на интервале должен существовать только один корень. Рассмотрим несколько методов решения нелинейных уравнений.

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

Метод деления отрезка пополам имеет другие названия: метод половинного деления, метод дихотомии, метод проб, метод бисекций.

Пусть корень уравнения f (x) = 0 отделен на отрезке[a;b], т. е. f (a)•f (b)<0.

Алгоритм приближенного вычисления корня методом половинного деления.

Исходные данные: f (x) — функция; е — требуемая точность; a, b — границы заданного интервала (границы поиска корня).

Результат: xпр — приближенный корень уравнения f (x) = 0.

Метод решения:

Шаг 1. Выбрать середину отрезка[a;b] в качестве приближенного корня.

Шаг 2. Если f (c)=0, то c — искомый корень уравнения, на этом прекращаем вычисления. В противном случае перейти к шагу 3.

Шаг 3. Точный корень уравнения x* отличается от c не более чем на половину длины отрезка, т. е. не более чем на (полученная точность). Проверяем условие. Если условие не выполняется, т. е. полученная точность нас не устраивает (она больше, чем требуемая), то перейти к шагу 4; в противном случае прекратить вычисления, поскольку мы достигли требуемой точности, и приближенным корнем уравнения f (x) = 0 считать середину c отрезка [a;b].

Шаг 4. Определить интервал дальнейшего поиска корня. Из двух образовавшихся при делении отрезков переходим к той из его половин [a;c] и [c;b], на концах которого функция принимает значения разных знаков.

Случай 1 (рис. 1). Корень на отрезке [a;c]. f (a)•f©?0, граница b сдвигается влево — заменить b на с: b:= c.

Рис. 1 Графическая иллюстрация метода половинного деления

Случай 2 (рис. 1). Корень на отрезке [c;b]. f (a)•f (c)>0, граница a сдвигается вправо — заменить a на с: a:= c.

Перейти к шагу 1.

Алгоритм деления отрезка пополам довольно медленный, но зато абсолютно застрахован от неудач. Основное достоинство метода состоит в том, что его скорость сходимости не зависит от вида функции f (x). Данный метод не имеет дополнительных условий сходимости, кроме f (a)•f (b)<0.

Блок-схема программы Метод касательных Пусть на отрезке [a; b] отделен корень с уравнения f (x) = 0 и f -функция непрерывна на отрезке [a; b], а на интервале (a; b) существуют отличные от нуля производные f ' и f «.

Так как f '(x)? 0, то запишем уравнение f (x) = 0 в виде:

x = x — (f (x) / f '(x)) (1).

Решая его методом итераций можем записать:

x_n+1 = x _n— (f (x _n) / f '(x _n)) (2).

Если на отрезке [a;b] f '(x) * f «(x) > 0, то нулевое приближение выбираем x₀=a. Рассмотрим геометрический смысл метода. Рассмотрим график функции y=f (x). Пусть для определенности f `(x) > 0 и f «(x) > 0 (рис. 1). Проведем касательную к графику функции в точке B (b, f (b)). Ее уравнение будет иметь вид:

y = f (b) + f '(b) * (x — b)

Полагая в уравнении y = 0 и учитывая, что f '(x)? 0, решаем его относительно x. Получим:

x = b — (f (b) /f `(b))

Нашли абсциссу x₁ точки c₁ пересечения касательной с осью Оx:

x₁ = b — (f (b) — f ' (b))

Проведем касательную к графику функции в точке b₁ (x₁; f (x₁)).Найдем абсциссу x₂ точки с₂ пересечения касательной с осью Ox:

x₂ = x₁ — (f (x₁) / (f '(x₁))

Вообще:

x_k+1 = x _k — (f (x _k) / f '(x _k)) (3).

Таким образом, формула (3) дает последовательные приближения (x_k) корня, получаемые из уравнения касательной, проведенной к графику функции в точке b _k (x _k; f (x _k0) метод уточнения корня c [a;b] уравнения f (x) = 0 с помощью формулы (3) называется методом касательной или методом Ньютона.

Геометрический смысл метода касательных состоит в замене дуги y = f (x) касательной, одной к одной из крайних точек. Начальное приближение x ₀=a или x₀ = b брать таким, чтобы вся последовательность приближения х _k принадлежала интервалу (a;b). В случае существования производных f ', f «, сохраняющих свои знаки в интервале, за х₀ берется тот конец отрезка [a;b], для которого выполняется условие f '(х₀) * f (х₀) > 0. Для оценки приближения используется общая формула:

|c-x _k-1 |? | f (x _k+1)/m|, где m = _min f '(x) на отрезке [a;b].

На практике проще пользоваться другим правилом :

Если на отрезке [a;b] выполняется условие 0 < m < | f (x)| и ?????заданная точность решения, то неравенство | x _k+1-x _k|? ??? влечет выполнение неравенства |c-x _k-1|? ???

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

|c-x _k-1|? ???

Блок-схема программы Метод хорд Пусть на отрезке [a;b] функция непрерывна, принимает на концах отрезка значение разных знаков, а производная f '(x) сохраняет знак. В зависимости от знака второй производной возможны следующие случаи расположения кривых (рис. 1).

Рис. 1 Возможные случаи расположения кривых.

Алгоритм приближенного вычисления корня методом хорд.

Исходные данные: f (x) — функция; е — требуемая точность; x₀ — начальное приближение.

Результат: xпр — приближенный корень уравнения f (x) = 0.

Метод решения:

Рис. 2 Геометрическая интерпретация метода хорд для случая f '(x) f ''(x)>0

Рассмотрим случай, когда f '(x) и f ''(x) имеют одинаковые знаки (рис. 2).

График функции проходит через точки A₀(a, f (a)) и B₀(b, f (b)). Искомый корень уравнения (точка x*) нам неизвестен, вместо него возьмет точку х₁ пересечения хорды А₀В₀ с осью абсцисс. Это и будет приближенное значение корня.

В аналитической геометрии выводится формула, задающая уравнение прямой, проходящей через две точки с координатами (х1; у1) и (х2; у2):

.

Тогда уравнение хорды А₀В₀ запишется в виде: .

Найдем значение х = х₁, для которого у = 0:. Теперь корень находится на отрезке [x₁;b]. Применим метод хорд к этому отрезку. Проведем хорду, соединяющую точки A₁(x₁, f (x₁)) и B₀(b, f (b)), и найдем х₂ — точку пересечения хорды А₁В₀ с осью Ох: x₂=x₁ .

Продолжая этот процесс, находим: x₃=x₂. Получаем рекуррентную формулу вычисления приближений к корню x_n+1=x_n.

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

Таким образом, получаем расчетные формулы метода хорд:

x_n+1=x_n; x₀=a. (4).

Вычисления очередных приближений к точному корню уравнения продолжается до тех пор, пока не достигнем заданной точности, т. е. должно выполняться условие: |x_n+1-x_n|<, где — заданная точность.

Теперь рассмотрим случай, когда первая и вторая производные имеют разные знаки, т. е. f '(x) f ''(x)<0. (рис. 3).

Рис. 3 Геометрическая интерпретация метода хорд для случая f '(x) f ''(x)<0

Соединим точки A₀(a, f (a)) и B₀(b, f (b)) хордой А₀В₀. Точку пересечения хорды с осью Ох будем считать первым приближение корня. В этом случае неподвижным концом отрезка будет являться конец а.

Уравнение хорды А₀В₀:. Отсюда найдем x₁, полагая y = 0: x₁=b. Теперь корень уравнения x[a;x₁]. Применяя метод хорд к этому отрезку, получим x₂=x₁. Продолжая и т. д., получим x_n+1=x_n.

Расчетные формулы метода:

x_n+1=x_n, x₀=0. (5).

Условие окончания вычислений: |x_n+1-x_n|<. Тогда хпр = xn+1 с точностью Итак, если f '(x) f ''(x)>0 приближенное значение корня находят по формуле (4), если f '(x) f ''(x)<0, то по формуле (5).

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

Пример. Проиллюстрировать действие этого правила на уравнении.

(x-1)ln (x)-1=0, если отрезок изоляции корня [2;3].

Решение. Здесь f (x)=(x-1)ln (x)-1.

f '(x)=ln (x)+;

f ''(x)=

Вторая производная в этом примере положительна на отрезке изоляции корня [2;3]: f ''(x)>0, f (3)>0, т. е. f (b) f''(x)>0. Таким образом, при решении данного уравнения методом хорд для уточнения корня выбираем формулы (4).

Блок-схема программы.