Численные методы решения нелинейных уравнений. Комбинированный метод Дэккера и Брэнта.

Комбинированный метод Дэккера и Брэнта (TheVanWijngaarden-Dekker-BrentMethod) - это итерационный численный метод для решения нелинейного уравнения  непрерывной функции. Данный метод был разработан в 1960-х годах в Математическом центре в Амстердаме (A. van Wijngaarden, J. A. Zonneveld and E. W.Dijkstra (1963), J. H. Wilkinson (1967), G. Peters and J. H. Wilkinson (1969), T. J. Dekker (1969)), а затем данный метод был улучшен Richard Peirce Brent (1971).  Данный метод относится к методам интервалов локализации корня и представляет собой алгоритм одномерного поиска.

Рассмотренный метод основан на замене исходной функции  обратной квадратичной функцией, которая строится по трем точкам ( и  ), где точки () характеризуют текущий интервал неопределенности в котором выполняется поиск приближенного значения корня функции , а точка  определяется исходя из пропорции золотого сечения. Например, точка  расположена от начала интервала неопределенности на расстоянии 0,618 от длины отрезка.

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

где  ˗ степень полинома 

  ˗  значение значения интерполирующей функции  в точке ;

 ˗  базисные полиномы, которые определяются по формуле:

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

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

 

 

Рис.1. Квадратичная функция и обратная квадратичная функция, которые построены по трем точкам.

Рассмотрим случай, когда функция  пересекает ось абсцисс, для этого в качестве аргумента функции возьмем . Тогда уравнение преобразуется к виду:

 

 

 

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

где переменные определяются по следующим формулам

 

;  .

Следует обратить внимание, что возможны ситуации, когда три различных точки обращают значение функции в одинаковые значения, что в свою очередь дает неустойчивое решение по  методу Дэккера и Брэнта. В таких ситуациях вместо метода Дэккера и Брэнта используется метод хорд. В соответствии с методом хорд в качестве следующей точки приближенного значения корня функции   выбирается точка пересечения секущей с осью абсцисс:

 

Алгоритм нахождения корня нелинейного уравнения по методу Дэккера и Брэнта

1. Найти начальный интервал неопределенности  одним из методов отделения корней. Задать погрешность расчета (малое положительное число  ) и начальный шаг итерации (k=0).

2. Определить среднюю точку в рассматриваемом интервале по методу золотого сечения .

Определить значения функции в трех точках: по краям рассматриваемого  интервала  и в средней интервала.

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

,

где 

 

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

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

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

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

1 интервал: если , то новый интервал 

2 интервал: если , то новый интервал 

5. Проверяем значение корня на предмет заданной точности, в случае: 

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

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

 

Пример решения уравнений методом Дэккера и Брэнта

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

Вариант решения нелинейного уравнения в программном комплексе MathCAD представлен на рисунке 3.

Результаты расчетов, а именно динамика изменения приближенного значения корня, а также погрешности расчета от шага итерации представлены в графической форме (см. рис.2).

Рис.2. Результаты расчета по методу Дэккера и Брэнта

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

Рис.3. Листинг программы в MathCad

 

 

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

Комментарии  

#1 Admin 12.05.2015 08:29
В статье рассмотрен численный метод решения нелинейного уравнения, который используется в функции root () программного комплекса MathCad. По умолчанию функция root () использует несколько методов для расчета корней уравнений: метод Риддера (Ridder) и метод Брента (Brent).

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