Практические руководства
Полиномиальная интерполяция
Покрытие полиномиальной интерполяции Лагранжа, полиномиальной интерполяции Ньютона и сплайновой интерполяции
Интерполяция
Представьте, что вы хотите отслеживать температуру в течение дня в своем огороде. Вы измеряете температуру ровно каждый час и в итоге получаете следующие 24 измерения температуры:
Вы можете нанести эти данные на график с помощью любого инструмента по вашему выбору, чтобы получить так называемую диаграмму рассеяния: для каждой меры будет точка.
Следующий шаг, который вас, вероятно, заинтересует, - это преобразование этого графика рассеяния в линейный график. Однако у вас нет данных между точками данных, поэтому у вас нет точной информации о том, как рисовать линии.
Вы можете сделать это с помощью интерполяции. Интерполяция - это задача разумной оценки значений между точками данных.
Методы интерполяции
Для интерполяции можно использовать множество различных подходов. Самый простой метод - Линейная интерполяция, при котором вы проводите прямую линию от каждой точки данных к следующей точке данных. Несмотря на свою простоту, этот метод часто совершенно неверен, поскольку он создает график с большим количеством "углов":
Другой базовый подход к интерполяции - это Интерполяция ближайших соседей, в которой вы оцениваете каждое значение с помощью ближайшего соседа. Например, вы использовали бы измерение 11 часов в качестве оценки с 10:30 до 11:30, затем вы использовали бы измерение 12 часов с 11:30 до 12:30 и т. Д. получить график следующего вида:
Этот график может показаться странным: он называется кусочным графом. В строках нет непрерывности, так как оценочное значение "перескакивает" от одного соседа к другому, когда оно достигает порогового значения. В нашем примере порог составляет полчаса, но он, конечно, зависит от примера, с которым вы работаете.
Полиномиальная интерполяция
Полиномиальная интерполяция - это улучшенный метод интерполяции, который пытается найти полиномиальную функцию, которая лучше всего соответствует вашим данным. Если вы не сильны в математике, просто думайте о полиномиальных функциях как о математическом семействе многих функций.
Давайте посмотрим на определение многочлена:
Многочлен определяется как выражение, состоящее из переменных и коэффициентов, которое включает только операции сложения, вычитания, умножения и неотрицательного целочисленного возведения переменных в степень.
Тем не менее, это очень широкое определение: есть еще много различных функций, которые соблюдают это правило. В семействе многочленов так много разных многочленов, что вы всегда можете найти тот, который соответствует вашим данным.
Степень полинома определяется наибольшей степенью в формуле. Например, многочлен степени 2 содержит квадрат x, а многочлен степени 3 имеет где-то кубику (степень 3) и т. Д. Давайте рассмотрим несколько примеров многочленов, чтобы понять широкий диапазон возможностей полиномиальных функций.
Пример многочлена степени 2
Многочлен степени 2 - парабола. Примером этого является следующая функция:
y = 1 + x + x**2
Выглядит это так:
Пример многочлена степени 3
Многочлен степени 3 - кубика. Примером этого является следующая функция:
y = 1 + x + x**2 + x**3
Выглядит это так:
Пример полинома шестой степени
Многочлены более высокой степени могут принимать очень сложные формы. Примером этого является следующая функция:
y = 1/100 * (x**6 — 2x**5-26x**4+28x**3+145x**2-26x-80 )
Выглядит это так:
Как видно на графиках, полиномы позволяют определять очень сложные формы. В то же время кривые остаются намного более гладкими, чем полученные с помощью линейной интерполяции или интерполяции ближайших соседей. Это основная причина того, что полиномиальная интерполяция в настоящее время является наиболее популярным методом интерполяции для большинства случаев использования.
Методы полиномиальной интерполяции
Точная цель полиномиальной интерполяции - найти полином наименьшей возможной степени, который идет к точкам набора данных. Самая низкая степень сводится к простейшей версии многочлена.
Для каждого набора данных существует только один простейший многочлен: есть один и только один правильный многочлен, и цель состоит в том, чтобы его найти. Тем не менее, в этой статье мы собираемся обсудить три распространенных метода полиномиальной интерполяции:
- Полиномиальная интерполяция Лагранжа
- Полиномиальная интерполяция Ньютона, также называемая интерполяционным полиномом разделенных разностей Ньютона
- Сплайн интерполяции, а точнее кубический сплайн интерполяции
Многочлен Лагранжа и многочлен Ньютона дают один и тот же результат, но они получают результат с помощью разных вычислений. Методы Лагранжа и Ньютона приводят к получению полиномиальной функции наименьшего порядка, проходящей через точки данных.
Сплайн-интерполяция немного отличается, поскольку оценивает не один многочлен, а скорее кусочно-размерный многочлен. «Настоящая» полиномиальная интерполяция может потребовать очень сложного полинома, чтобы точно пройти через все ваши точки данных. Когда сложность становится слишком высокой, полином может принять чрезвычайно изменчивую кривую, содержащую множество нежелательных всплесков между точками данных.
Сплайн-интерполяция - решение этой проблемы, поскольку она определяет несколько более простых многочленов на подмножествах данных. Это обеспечивает отличный баланс между плавностью и простотой. Сплайн-интерполяция - лучшее решение для многих задач интерполяции.
Давайте теперь рассмотрим три обсуждаемых метода интерполяции более подробно.
Полиномиальная интерполяция Лагранжа
Первый метод полиномиальной интерполяции, который мы рассмотрим, - это полиномиальная интерполяция Лагранжа. Это метод, который позволяет вам найти многочлен с наименьшим порядком, который проходит через все точки набора данных.
Формула интерполяции Лагранжа
В этой статье мы не будем вдаваться в математические доказательства того, почему формула интерполяции Лагранжа работает, но мы рассмотрим, как использовать ее вручную.
Вот формула интерполяции Лагранжа:
Начать понимание легче с части 2. В части 2 в основном говорится, что для каждого набора значений x и y в наборе данных вы умножаете значение y на «вычисление части 1» значения x.
Это вычисление части 1 должно выполняться отдельно для каждого значения x. Расчет можно понять следующим образом. Для каждого значения x, отличного от рассматриваемого значения x (назовите рассматриваемое значение x j и все остальные m), вы получите (x — m) / (j-m). Затем вы берете продукт из них.
Полиномиальная интерполяция Лагранжа на небольшом ручном примере
Представьте, что у вас есть три точки данных:
(x = 2, y = 4)
(x = 4, y = 16)
(x = 6, y = 36)
Сначала вы вычисляете часть 1 формулы интерполяции Лагранжа для каждой точки данных:
- Для первой точки данных:
[ (x — 4) / (2 — 4) ] * [ (x — 6) / (2 — 6) ]
- Для второй точки данных
[ (x — 2) / (4–2) ] * [ (x — 6) / (4–6) ]
- Для третьей точки данных
[ (x — 2) / (6–2) ] * [ (x — 4) / (6–4) ]
Затем вы берете сумму произведений y и решения x части 1 для каждой комбинации точек данных:
4 * [ (x — 4) / (2–4) ] * [ (x — 6) / (2–6) ]
+ 16 * [ (x — 2) / (4–2) ] * [ (x — 6) / (4–6) ]
+ 36 * [ (x — 2) / (6–2) ] * [ (x — 4) / (6–4) ]
После этого вы можете упростить формулу и получить x ** 2.
Использование Python для поиска полиномиальной интерполяции Лагранжа
Замечательно видеть, как выполнить ручной подход к решению интерполяции полинома Лагранжа, но это большая работа. Давайте теперь посмотрим, как можно использовать инструмент Python для автоматического поиска лучшего полинома. Конечно, в большинстве программ научных вычислений существуют альтернативы.
Давайте начнем с того же примера, который мы только что сделали вручную.
В этом примере Scipy реализация полиномиальной интерполяции Лагранжа успешна: квадрат x был правильно идентифицирован.
Теперь главный вопрос: можем ли мы использовать интерполяцию полинома Лагранжа, чтобы найти полином для температуры в нашем примере огорода? Этот пример явно намного сложнее и потребует очень сложного многочлена. Давайте посмотрим, что произойдет, когда мы применим инструмент Scipy к этой проблеме:
Ясно, что подход Лагранжа явно не может найти многочлен для этого американского случая. Это не проблема и даже ожидаемое поведение. В документации Scipy говорится:
Предупреждение. Эта реализация численно нестабильна. Не ожидайте, что сможете использовать более 20 точек, даже если они выбраны оптимально.
Теперь, когда мы понимаем, что интерполяция полиномом Лагранжа не может работать на таком большом примере интерполяции, давайте перейдем к методу интерполяции полинома Ньютона и посмотрим, даст ли он лучший результат.
Полиномиальная интерполяция Ньютона
Теперь давайте посмотрим на метод Ньютона для нахождения полинома с наименьшим порядком. Этот метод должен дать тот же ответ, что и полиномиальная интерполяция Лагранжа, но использует другой метод расчета.
Интерполяционный многочлен разделенных разностей Ньютона
Метод полиномов Ньютона иногда также называют интерполяционным полиномом разделенных разностей Ньютона. Причина этого в том, что коэффициенты полинома вычисляются с использованием метода, называемого разделенными разностями, который был изобретен Исааком Ньютоном.
Ваши x-точки должны быть расположены на одинаковом расстоянии и упорядочены для использования метода прямого полинома Нетвона. Формула выглядит следующим образом
Полином Лагранжа против полинома Ньютона
Многочлен Ньютона имеет некоторые практические преимущества перед многочленом Лагранжа. Это позволяет добавлять в расчет дополнительные точки данных без повторения всего расчета.
Интерполяция полиномов Ньютона в Python
Чтобы выполнить интерполяцию полинома Ньютона, нам нужно найти реализацию, поскольку у нее нет реализации в Scipy. Вы можете использовать приведенный ниже код Python для полиномиальной интерполяции Ньютона (кредиты на StackOverflow):
Давайте начнем с тестирования кода полиномиальной интерполяции Ньютона на примере небольших данных с функцией x в квадрате:
Как вы видите на графике, полиномиальная интерполяция Ньютона успешно нашла функцию x-квадрат на основе трех точек данных. Хорошие новости. Теперь давайте посмотрим, сможем ли мы использовать тот же метод для данных о температуре в нашем огороде!
Глядя на этот график, вы видите, что в некотором смысле реализация Ньютона работает лучше, чем реализация Лагранжа: по крайней мере, Ньютон просматривает все точки данных.
Тем не менее, с этим решением есть серьезная проблема: этот многочлен слишком сложен и, следовательно, он оценивает экстремальные пики температуры с полуночи до 5 утра и с 8 вечера до полуночи.
Это ясно показывает недостаток полиномиальной интерполяции в ее официальном определении. Вы заставляете модель находить один и только один многочлен, который подходит для всех ваших точек данных, но ваши данные на самом деле не соответствуют идеальному многочлену. Поэтому решение часто представляет собой принудительный, слишком сложный многочлен с некоторыми крайними ошибками в определенных местах.
Давайте найдем решение этой проблемы: Сплайн-интерполяция.
Сплайн-интерполяция
Сплайн-интерполяция сильно отличается от двух предыдущих методов интерполяции. Вы можете считать, что методы Лагранжа и Ньютона - это чистая полиномиальная интерполяция: они фактически интерполируют с использованием одной и только одной полиномиальной функции.
Сплайн-интерполяция - это вариант полиномиальной интерполяции, который подходит не только для одного сложного полинома, а скорее для множества полиномов меньшей степени. Таким образом вы избегаете подбора слишком сложных многочленов и получаете более гладкую кривую с меньшей ошибкой интерполяции.
Кубическая интерполяция сплайна
Чтобы выполнить интерполяцию сплайна, вам нужно подогнать полином от каждой точки к следующей. В итоге вы получите множество подфункций, которые вместе составляют полную функцию интерполяции.
Конечно, начальные и конечные значения каждого сегмента линии должны соответствовать предыдущему или следующему сегменту. Это можно сделать только при кубических или более сложных полиномах.
Использование кубических сплайнов также имеет то преимущество, что вы избегаете подгонки слишком сложных кривых, подобных той, которую мы видели в методе Ньютона. Поэтому стандартный метод интерполяции сплайнов - использовать только кубические сплайны.
Кубическая сплайн-интерполяция в Python
Большинство научных программ предлагает метод интерполяции кубического сплайна. Давайте посмотрим, как приблизиться к интерполяции кубического сплайна с помощью Scipy в Python. Начнем с небольшого примера с тремя точками данных.
Неудивительно: точно так же, как Лагранж и Ньютон, кубический сплайн также нашел функцию x-квадрат. Давайте посмотрим, как он работает с данными о температуре в огороде.
Как видите, кубический сплайн предлагает очень «естественную» интерполяцию. Это намного более гладко, чем линейная интерполяция или интерполяция ближайших соседей, которые вы видели раньше. В то же время он намного менее сложен, чем «чистые» полиномиальные методы, предложенные Лагранжем и Ньютоном.
Линейная интерполяция и интерполяция ближайшего соседа может по-прежнему иметь преимущества в своей теоретической простоте, а интерполяция Лагранжа и Ньютона по-прежнему имеет преимущество на очень простых данных, которые идеально представляют полином низкого порядка. Тем не менее, гладкость и простота сплайновой интерполяции делают ее незаменимым методом для решения многих современных задач интерполяции.
Ключевые выводы
- В этой статье вы открыли для себя пять методов интерполяции, из которых три метода для полиномиальной интерполяции.
- Линейная интерполяция - это простейший метод интерполяции, поскольку он состоит в рисовании прямых линий между каждой точкой данных и следующей. Интерполяция ближайших соседей использует ближайшее измеренное значение в качестве оценки значений между ними.
- Интерполяция полинома Лагранжа и Интерполяция полинома Ньютона (или интерполяционный полином разделенных разностей Ньютона) - это два метода, которые детерминистически находят полином низшего порядка, который проходит через все ваши точки данных.
- Сплайновая интерполяция, особенно Кубическая сплайновая интерполяция, является более гибкой альтернативой, которая находит кусочный многочлен. Это позволяет уменьшить порядок используемых многочленов с тем преимуществом, что они проще и ближе к реальности. Это происходит за счет использования множества многочленов в кусочной функции, а не определения одного общего многочлена.
Надеюсь, эта статья была для вас полезной. Не сомневайтесь, следите за обновлениями математики, статистики и данных!
