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

 

Нахождение корней уравнений - одна из наиболее часто встречающихся задач. Вместе с тем не всегда есть возможность найти аналитическое решение уравнения. В первую очередь это относится к большинству трансцендентных уравнений, т.е. уравнений, в которых неизвестная х находится под знаком трансцендентной функции, например, x² - sin 5x = 0.

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

 

a₀xⁿ + a₁x^n-1 + a₂x^n-2 +... + a_n = 0, n³5.

 

Для поиска корней таких уравнений используются численные (приближенные) методы, которые по своей сути являются способами уточнения корней [3-5].

В общем случае запись нелинейного уравнения имеет вида

 

f(x) = 0. (30)

 

Задача решения нелинейного уравнения состоит из двух этапов:

1) локализация корней, т.е. определение интервала изоляции (интервала неопределенности), в котором расположен корень;

2) определение с заданной точностью точности ε приближенного значения корня.

Для локализации корней можно воспользоваться следующей теоремой.

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

Задача локализации корней обычно решается построением схематического графика функции y=f(x) (рисунок 9).

Корень x* будет только один, если первая производная функции f’(x) существует и сохраняет постоянный знак внутри интервала [a, b] (рисунок 10).

 

 

 

Рисунок 9 – Графическая локализация корней уравнения

 

 

 

 

Рисунок 10 – Графическое представление постоянства знака производной функции f’(x)

 

 

Определение приближенного значения корня уравнения выполняется численными методами. Рассмотрим самые распространенные из них.

 

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

 

Данный метод является наиболее простым.

Считается, что локализация корней уравнения проведена, и на отрезке [a, b] расположен один корень, который необходимо уточнить с погрешностью e (рисунок 11). Принято обозначать: a - левая граница отрезка, b - правая.

 

 

 

Рисунок 11 – Графическая интерпретация метода половинного деления

 

 

Метод дихотомии заключается в следующем (см. рисунок 11). Вначале вычисляется значение функции при x=a, т.е. f(a). Определяется середина отрезка

 

d = (a + b) / 2 (31)

 

и вычисляется значение функции f(d).

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

 

f(a)×f(d)<0 (32)

 

и в зависимости от результата переобозначают начало a или конец b интервала. Если это условие (32) выполняется, то в середину отрезка перемещается правая граница отрезка, т.е. b = d, иначе a = d.

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

 

(b-a) < e. (33)

 

Приближенное значение корня принимается как середина отрезка [a, b]:

 

x^* = (a+ b) / 2. (34)

 

Блок-схема метода половинного деления представлена на рисунке 12.

 

 

 

 

Рисунок 12 - Блок-схема алгоритма поиска корней уравнения методом половинного деления

Метод хорд

 

 

Идея метода хорд заключается в том, что кривая y=f(x) на участке [a, b] заменяется хордой и в качестве приближенного значения корня х^*=x_n принимается точка пересечения оси абсцисс с хордой (рисунок 13).

 

 

 

 

Рисунок 13 – Графическая интерпретация метода хорд

Запишем уравнение хорды, проходящей через точки С с координатами (a, f(a)) и D – (b, f(b)):

 

.

 

Абсцисса точки пересечения хорды с осью ОХ находится из этого выражения при y=0, т.е.

 

.

 

Выполнив преобразования, получаем выражение для нахождения приближенного корня:

 

. (35)

 

Полученное значение x_n можно снова использовать для дальнейшего уточнения корня, рассматривая интервал [a, x_n] или [x_n , b] в зависимости от знака функции в точке x_n - f(x_n).

Если значения функции при х=а и х=x_n имеют разные знаки, т.е. выполняется условие

 

f(a)×f(x_n)<0, (36)

то в точку x_n перемещается правая граница отрезка, т.е. b = x_n, иначе a = x_n.

Вычисления повторяются до тех пор, пока выполняется условие

 

½ x_n+1 - x_n ½ ³ e. (37)

 

Блок-схема, реализующая метод хорд, приведена на рисунке 14.

 

 

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

 

Этот метод основан на замене функции y=f(x) в точке начального приближения x=x₀ касательной, пересечение которой с осью х дает первое приближение корня х₁ и т.д. (рисунок 15).

В качестве x₀ выбирают тот конец отрезка [a, b] (т.е. точку С или точку D), для которого выполняется условие:

f(x₀)×f '' (x₀) > 0. (38)

 

 

 

 

Рисунок 14 - Блок-схема алгоритма поиска корней уравнения методом хорд

 

Рисунок 15 – Графическая интерпретация метода Ньютона

 

 

Для графической иллюстрации (рисунок 15), где начальное приближение находится в точке D, т.е. x₀ = b, запишем:

 

,

 

откуда или .

 

Тогда, в общем виде выражение для нахождения корня можно записать:

x_n+1 = x_n - f(x_n) / f '(x_n), (39)

 

Итерационный процесс уточнения корня выполняется до тех пор, пока соблюдается условие

 

½ x_n+1 - x_n ½ ³ e. (40)

 

Метод Ньютона обладает высокой скоростью сходимости. Обычно абсолютная точность решения 10^-5 - 10^-6 достигается через 5-6 итераций.

Блок-схема, реализующая метод Ньютона, приведена на рисунке 16.

 

 

 

 

 

Рисунок 16 - Блок-схема алгоритма поиска корня уравнения методом Ньютона

Комбинированные методы

 

 

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

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

На рисунке 17 приведена блок-схема комбинированного метода хорд-Ньютона.

 

 

 

 

Рисунок 17 - Блок-схема комбинированного метода хорд-Ньютона