Реализация различных алгоритмов поиска корней в Python

С реальным применением в науке о данных и логистической регрессии

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

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

Алгоритмы поиска корней – это численные методы, которые аппроксимируют значение x, удовлетворяющее условию f(x) = 0 любой непрерывной функции f(x). Пусть g(x)будет производной от f(x). Затем можно максимизировать или минимизировать f(x) путем нахождения корней g(x), где g(x) = 0. Мы используем алгоритмы поиска корней, чтобы найти эти корни.

Обратите внимание, что все представленные здесь алгоритмы являются итерационными. Поэтому, если я упоминаю «текущее значение x», это просто означает значение текущей итерации.

Для всех наших примеров я буду использовать эту функцию ниже,

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

1. Метод фиксированной точки

Для начала я выберу самый простой (на мой взгляд) алгоритм, чтобы дать вам представление о том, как работают алгоритмы поиска корней. Идея этого алгоритма заключается в том, что после того, как вы установили f(x) = 0, вы должны привести оставшееся уравнение в следующую форму x = g(x). Позвольте мне показать вам, как это сделать с нашей функцией,

Обратите внимание, что вы можете найти несколько g(x) для любого f(x), причем каждый g(x)имеет разные свойства сходимости. Следующий шаг — рассмотреть уравнение x = g(x) с точки зрения итерации.

Левая часть представляет собой следующую итерацию обновления x, а правая часть содержит текущее значение x.

Напомним, что для нахождения корней f(x) с помощью итерации с фиксированной точкой необходимо:

1. Установите f(x) = 0
2. Преобразовать в x = g(x)
3. Установите инициализированное значениеx⁰
4. Обновите x, изменив его на g(x)
5. Перейти к шагу 4, если значение |f(x)| не меньше эпсилон ϵ

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

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

Если я вызову следующий код,

FixedPoint(g, 4)

я бы получил

2.965794554141745

На этом метод фиксированной точки заканчивается.

2. Метод Ньютона-Рафсона

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

Идея метода Ньютона-Рафсона заключается в том, что при текущем значении x мы хотим провести касательную к f(x) в точке x. Затем мы устанавливаем следующее значение x на пересечении, где касательная пересекается с осью x.

Давайте сделаем математику. Напомним, в младших классах средней школы нас учат, что, имея 2 точки координат в плоскости xy, мы можем найти градиент линии, которая проходит через 2 точки, используя эту формулу:

Переводя это на нашу задачу, у нас есть два набора координат. Наша первая координата — это текущая итерация x и соответствующее ему значение y в функции или просто f(x). Наша вторая координата — это наше новое значение x и соответствующее ему значение y. Но помните, что мы устанавливаем новое значение x как пересечение касательной и оси x, то есть его значение y всегда будет 0.

Имея эти координаты, мы хотим найти градиент линии, проходящей через эти точки. Градиент — это просто производная от f(x), вычисляемая при текущем значении x в соответствии с определением множества.

Завершающей строкой расчета является формула Ньютона-Рафсона. Напомним, шаги этого алгоритма довольно просты,

1. Установите инициализированное значение x⁰
2. Найти f(x) и f’(x) по текущему значению x
3. Обновите x, используя формулу Ньютона-Рафсона.
4. Перейти к шагу 2, если значение |f(x)| не меньше эпсилон ϵ

Чтобы поместить это в код,

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

Запустив следующую строку,

NewtonRaphson(f, 4)

Вернулся бы

2.9657944029135495

На этом заканчивается метод Ньютона-Рафсона.

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

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

Для этого мы используем следующую аппроксимацию производной f(x), оцененной при текущем значении x.

Обратите внимание, что в этом приближении используются текущая и предыдущая итерации x. Затем мы подставляем это приближение в формулу Ньютона-Рафсона.

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

1. Установите инициализированное значение x⁰ и x¹, указывающее предыдущее и текущее значение x
2. Обновите x с помощью формулы секущей, учитывая два последних значения x.
3. Перейти к шагу 2, если значение |f(x)| не меньше эпсилон ϵ

Чтобы поместить это в код,

Запустив следующую строку,

SecantMethod(f, 2, 4)

Вернулся бы

2.9657943958960433

На этом метод секущих заканчивается.

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

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

Пусть L — нижняя граница, а U — верхняя граница. Общая идея заключается в том, что если f(L)f(U) ‹ 0, или, другими словами, f(L) и f(U) разного знака, то между ними должен быть хотя бы один корень. Мы используем метод, несколько похожий на бинарный поиск, чтобы найти этот корень. Обратите внимание, что это означает, что L и U должны иметь разные знаки.

Пусть R будет нашим текущим предположением о корне f(x), мы устанавливаем R как середину L и U.

Если R не является фактическим корнем f(x), нам нужно будет оценить, находится ли корень ниже R или выше его. Мы можем проверить это, используя ту же логику, что и раньше, т. е. проверить, если f(L)f(R) ‹ 0 и f(R )f(U) ‹ 0. Если верно первое, то мы хотим ограничить область поиска в пределах L и R, поэтому мы обновляем U=Rи сохраняем значение L. Точно так же, если верно последнее, мы обновляем L=R и сохраняем значение U. Мы продолжаем делать это до тех пор, пока f(R) не станет достаточно близко к нулю.

Давайте повторим это,

1. Задайте исходное предположение L и U, где хотя бы один корень R должен находиться между регионами L ‹ R ‹ U
2. Установите R в качестве середины между L и U с использованием формулы обновления Bisection.
3. Проверьте на наличие f(L)f(R) ‹ 0 и f(R)f(U) ‹ 0
4. Если верно первое, установите U=Rи сохраните значение L. Если верно последнее, установите L=Rи сохраните значение U.
5. Перейти к шагу 2, если значение |f(R)| не меньше эпсилон ϵ

BisectionMethod(f, 0, 5)

2.96579440290151

FalsePosition(f, 0, 4)

2.965794050755957