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

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

Методы численного решения нелинейных уравнений

Задачу решения я разделил на 3 части:

• 
  Аналитический способ отделения корней
  
• 
  Численные методы уточнения корней
  
• 
  Программная реализация вычислительного процесса
  

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

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

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

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

Комбинированный метод или метод хорд и касательных

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

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

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

Предварительно необходимо преобразовать уравнение f(x) = 0 к виду x = φ(x).

В качестве начального приближения x0 выбирается любая точка интервала [a,b].
Выделяют 2 итерационных метода: лестница и спираль. Если знак производной φ(x) положителен, то используют метод лестницы и наоборот спирали.

Главным и достаточным условием сходимости итерационного процесса является |φ'(x)|<1.

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

Практика. Применение методов.

Возьмем для примера задачу из области автоматизированного управления — нахождения нулей характеристического уравнения передаточной функции замкнутой системы автоматического управления высокого порядка для оценки ее устойчивости по методу Ляпунова. Сам метод выходит за рамки данного поста, но в прямом методе Ляпунова используется нахождение нулевых корней для выявления устойчивости системы. А для нахождения корней вполне подходят перечисленные методы. Какой метод эффективнее? На этот вопрос сложно ответить не зная конкретной системы к которой это будет применяться. Следует учитывать не только скорость операций, но так же и занимаемые ресурсы.

Вывод:

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

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

Мат.часть описанных методов.

PS: Первый пост и еще не совсем освоился. Помещаю пост в алгоритмы, т.к. блога по выч.мату не нашел.
Теги: 

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