Bisection, Newton и Secant математические алгоритмы поиска корней с использованием Python

Введение

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

В этой статье представлена ​​теория четырех стандартных алгоритмов поиска корня и их реализация в Python с нуля.

Возьмем уравнение 1 в качестве примера:

Рисунок 1 представляет собой график уравнения 1 на интервале [-1, 5]. Нуль или корень — это любоезначение x, когда f(x) равно 0, т. е.место, где кривая перемещается по оси X. В этом случае корень находится где-то между x₀ = 1 и x₁= 2.

Целью этой статьи является аппроксимация корня в Python с помощью некоторых числовых операций.

Три метода для достижения этой цели:

  1. Метод деления пополам
  2. Метод Ньютона
  3. Метод секущих

Метод деления пополам

Метод деления пополам аппроксимирует корни непрерывных функций путем многократного деления интервала в середине.

Метод применяется, когда известны два значения с противоположными знаками.

Если есть кореньf(x)на интервале[x₀, x₁] тоf(x₀) и f(x₁) должен иметь другой знак. то есть f(x₀)f(x₁) ‹ 0.

При необходимости просмотрите эту статью Теорема о промежуточных значениях.



Теорема о промежуточном значении в Python
Проверка существования решения функции с помощью теоремы о промежуточном значенииmedium.com



Пусть x₀ и x₁ будут начальной и конечной точками предполагаемого интервала. Затем с помощью уравнения 2 вычислите среднюю точку (x₂) между [x₀, x₁].

Следующим предположением является либо середина между x₀ и x₂, либо x₂и x₁, в зависимости от того, с какой стороны находится корень. падает на. Конвергенция идет медленно.

Gist 1 дает пример реализации алгоритма деления пополам.

Сохранение последовательных аппроксимаций корня и графическое построение На рис. 2 показан итеративный характер алгоритма.

Выполнение метода деления пополам для уравнения 1 с указанием интервала между [1, 2] возвращает решение при x≈1,324718475. Анализ рисунка 1 показывает, что это значение соответствует ожидаемому.

Для достижения этого результата процедура заняла около 18 итераций. Улучшение оценок происходит постепенно.

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

x₀ и x₁ — начальная и конечная точки интервала, например, [1, 2].



Вывод границы ошибки для метода деления пополам
Это вопрос домашнего задания, я хотел бы знать, может ли кто-нибудь пролить на него свет. Пусть $x_n = \frac{a_n + b_n}{2}…scicomp.stackexchange.com



Реализуйте уравнение, используя код Python в Gist 3.

Метод Ньютона

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

  • n: счетчик итераций
  • xₙ₊₁:следующая оценка
  • xₙ:текущая наилучшая оценка
  • f(xₙ): функция оценивается как xₙ
  • f’(xₙ): производная от f при xₙ

Очевидно, что для этой процедуры требуется первая производная от f(x), поэтому f(x) должна быть дифференцируемой.

Gist 3 предоставляет код Python для реализации итеративного решения для метода Ньютона. Он использует библиотеку Sympy для оценки f’(xₙ). При каждом проходе цикла значения параметров подставляются в уравнение 1 для определения xₙ₊₁.

Допуск предел контролирует прерывание процесса, и это условие срабатывает, когда f(xₙ) приближается к нулю.

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

При начальном предположении x = 9 этот метод возвращает f(x) = 0 @ x = 1,324718834. Для достижения точности 1e-5 требуется 8 итераций.

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

Метод секущих

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

Уравнение 4 должно быть реализовано в Python либо итеративно, либо рекурсивно.

Метод Python в Gist 4 рекурсивно ищет корни, используя метод Secant.

Начиная с начальных значений x₀ = 1 и x₁ = 2, процедура выводит корень f(x) при x = 1.324717957, за 8 рекурсивных вызовов. На рис. 4 визуализированы секущие линии, сгенерированные при каждом проходе.

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

Заключение

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

Если вас интересуют Python, инженерия и наука о данных, подпишитесь и ознакомьтесь с другими моими статьями.



Присоединяйтесь к Medium по моей реферальной ссылке — Эндрю Джозеф Дэвис
Как участник Medium, часть вашего членского взноса идет авторам, которых вы читаете, и вы получаете полный доступ ко всем историям. …medium.com





Основы матричной алгебры в Python | Часть 1
Понимание и реализация основных концепций и операций матричной алгебры с помощью Pythontowardsdatascience.com



Рекомендации

[1] Исчисление: полный курс, 8-е издание — Роберт А. Адамс, Университет Северной Каролины, Чапел-Хилл, США.