В математической области численного анализа , Ньютон многочлен , названный в честь его изобретателя Исаака Ньютона , [1] является интерполяционным полиномом для заданного набора точек данных. Полином Ньютона иногда называют интерполяционным полиномом разделенных разностей Ньютона, потому что коэффициенты полинома вычисляются с использованием метода разделенных разностей Ньютона .
ОпределениеУчитывая набор из k + 1 точек данных
где никакие два х J не являются одинаковыми, интерполяционный полином Ньютона является линейной комбинацией из Ньютона базисных полиномов
с базисными полиномами Ньютона, определенными как
для j > 0 и.
Коэффициенты определяются как
где
- обозначение разделенных разностей .
Таким образом, полином Ньютона можно записать как
Формула деленной разности Ньютона
Многочлен Ньютона можно выразить в упрощенной форме, когда расположены последовательно с равным интервалом. Вводя обозначения для каждого а также , различия можно записать как . Таким образом, полином Ньютона становится
Это называется вперед разделенная разность формула Ньютона [ править ] .
Формула обратной разделенной разности Ньютона
Если узлы переупорядочены как , полином Ньютона принимает вид
Если на равном расстоянии от а также для i = 0, 1, ..., k , то
называется Ньютон назад , разделенная разность формула [ править ] .
ЗначимостьФормула Ньютона представляет интерес, потому что это прямая и естественная версия полинома Тейлора с разностями. Многочлен Тейлора сообщает, куда пойдет функция, на основе ее значения y и ее производных (скорости изменения, скорости изменения скорости изменения и т. Д.) При одном конкретном значении x . Формула Ньютона - это полином Тейлора, основанный на конечных разностях, а не на мгновенных скоростях изменения.
Добавление новых очковКак и в случае с другими формулами разности, степень интерполяционного полинома Ньютона может быть увеличена путем добавления дополнительных членов и точек, не отбрасывая существующие. Форма Ньютона проста в том, что новые точки всегда добавляются на одном конце: прямая формула Ньютона может добавлять новые точки справа, а обратная формула Ньютона может добавлять новые точки слева.
Точность полиномиальной интерполяции зависит от того, насколько близко интерполированная точка находится к середине значений x используемого набора точек. Очевидно, что по мере добавления новых точек на одном конце эта середина становится все дальше и дальше от первой точки данных. Следовательно, если неизвестно, сколько точек потребуется для желаемой точности, середина значений x может быть далеко от того места, где выполняется интерполяция.
Гаусс, Стирлинг и Бессель разработали формулы для решения этой проблемы. [2]
Формула Гаусса поочередно добавляет новые точки на левом и правом концах, тем самым сохраняя центр набора точек в одном и том же месте (рядом с оцененной точкой). При этом используются термины из формулы Ньютона с переименованием точек данных и значений x в соответствии с вашим выбором, какая точка данных обозначена как точка данных x 0 .
Формула Стирлинга по-прежнему сосредоточена вокруг конкретной точки данных для использования, когда оцененная точка находится ближе к точке данных, чем к середине из двух точек данных.
Формула Бесселя по-прежнему сосредоточена вокруг определенной середины между двумя точками данных для использования, когда оцененная точка находится ближе к середине, чем к точке данных.
Бессель и Стирлинг достигают этого, иногда используя среднее значение двух разностей, а иногда используя среднее значение двух произведений биномов по x , тогда как для значений Ньютона или Гаусса используется только одно различие или произведение. Стирлинг использует среднюю разницу в нечетных выражениях (для разницы используется четное число точек данных); Бессель использует среднюю разницу в четных градусах (для разницы используется нечетное количество точек данных).
Сильные и слабые стороны различных формулДля любого заданного конечного набора точек данных существует только один полином наименьшей возможной степени, который проходит через все из них. Таким образом, уместно говорить о «форме Ньютона» или форме Лагранжа и т. Д. Интерполяционного полинома. Однако имеет значение способ получения полинома. Есть несколько подобных методов, например, Гаусса, Бесселя и Стирлинга. Они могут быть получены из значений Ньютона путем переименования значений x точек данных, но на практике они важны.
Бессель против Стирлинга
Выбор между Бесселем и Стирлингом зависит от того, находится ли интерполированная точка ближе к точке данных или ближе к середине между двумя точками данных.
Ошибка полиномиальной интерполяции приближается к нулю, когда точка интерполяции приближается к точке данных. Таким образом, формула Стирлинга обеспечивает повышение точности там, где это меньше всего необходимо, а Бессель обеспечивает повышение точности там, где это необходимо больше всего.
Таким образом, формулу Бесселя можно назвать наиболее точной разностной формулой и, в целом, наиболее точной из известных формул полиномиальной интерполяции.
Методы разделенных разностей и методы Лагранжа
Иногда говорят, что Лагранж требует меньше работы, и иногда его рекомендуют для задач, в которых заранее известно из предыдущего опыта, сколько терминов необходимо для достаточной точности.
Преимущество методов разделенных разностей состоит в том, что можно добавить больше точек данных для повышения точности. Термины, основанные на предыдущих точках данных, можно продолжать использовать. С обычной формулой Лагранжа, чтобы решить проблему с большим количеством точек данных, потребовалось бы заново выполнить всю задачу.
Существует «барицентрическая» версия Лагранжа, которая избавляет от необходимости заново выполнять все вычисления при добавлении новой точки данных. Но это требует, чтобы значения каждого термина были записаны.
Но способность Гаусса, Бесселя и Стирлинга удерживать точки данных в центре близко к интерполированной точке дает им преимущество перед Лагранжем, когда заранее неизвестно, сколько точек данных потребуется.
Кроме того, предположим, что кто-то хочет выяснить, является ли линейная интерполяция достаточно точной для некоторого конкретного типа проблемы. Это можно определить, оценив квадратичный член формулы разделенной разности. Если квадратичный член пренебрежимо мал - это означает, что линейный член достаточно точен без добавления квадратичного члена, - тогда линейная интерполяция достаточно точна. Если проблема достаточно важна или если квадратичный член почти достаточно велик, чтобы иметь значение, то можно было бы определить, достаточно ли велика сумма квадратичных и кубических членов, чтобы иметь значение в проблеме.
Конечно, для такого определения можно использовать только метод разделенных разностей.
Для этой цели следует выбрать формулу разделенной разности и / или ее точку x 0, чтобы формула использовала в качестве своего линейного члена две точки данных, между которыми будет выполняться интересующая линейная интерполяция.
Формулы разделенных разностей более универсальны и полезны для решения большего числа задач.
Формула Лагранжа наиболее эффективна, когда вся интерполяция будет выполняться при одном значении x , при этом только значения y точек данных меняются от одной задачи к другой, и когда из прошлого опыта известно, сколько терминов необходимо для достаточная точность.
С формой Ньютона интерполяционного многочлена существует компактный и эффективный алгоритм для объединения членов, чтобы найти коэффициенты многочлена. [3]
Точность
Когда в терминах Стирлинга или Бесселя последний использованный термин включает в себя среднее значение двух разностей, тогда используется на одну точку больше, чем при интерполяции Ньютона или других полиномов для той же степени полинома. Таким образом, в этом случае методы Стирлинга или Бесселя не помещают полином степени N −1 через N точек, а вместо этого торгуют эквивалентностью с полиномом Ньютона для лучшего центрирования и точности, что дает этим методам иногда потенциально большую точность для данной степени полинома. , чем другие полиномиальные интерполяции.
Общий случайДля частного случая x i = i существует тесно связанный набор многочленов, также называемых многочленами Ньютона, которые являются просто биномиальными коэффициентами для общего аргумента. То есть есть и полиномы Ньютона дано
В этой форме полиномы Ньютона порождают ряды Ньютона . Они, в свою очередь, являются частным случаем общих разностных полиномов, которые позволяют представлять аналитические функции через обобщенные разностные уравнения.
СутьРешение интерполяционной задачи приводит к проблеме линейной алгебры, в которой мы должны решить систему линейных уравнений. Используя стандартный мономиальный базис для нашего интерполяционного полинома, мы получаем очень сложную матрицу Вандермонда . Выбирая другой базис, базис Ньютона, мы получаем систему линейных уравнений с гораздо более простой нижнетреугольной матрицей, которую можно решить быстрее.
Для k + 1 точек данных мы строим базис Ньютона как
Используя эти многочлены как основу для мы должны решить
для решения задачи полиномиальной интерполяции.
Эта система уравнений может быть решена итеративно путем решения
ВыводХотя формулу интерполяции можно найти, решив линейную систему уравнений, есть потеря интуиции в том, что показывает формула, и почему формула интерполяции Ньютона работает не сразу. Для начала нам понадобится следующий результат:
. Это равенство означает, что реверсирование членов разделенной разницы не влияет на конечный результат. Докажем этот результат по индукции.
Основа :
Индукция : предположим, что результат верен для разделенной разницы, включающей менеетермины. Используя предположение индукции, мы видим, что где предположение индукции использовалось при 2-м равенстве.
Чтобы вывести формулу интерполяции, мы теперь воспользуемся следующим результатом, который также будет доказан с помощью индукции:
где - единственный полином степени (не выше) проходя через точки . С этим результатом мы теперь можем точно определить ошибку между интерполяционным полиномом в и истинная ценность .
Основа : где - единственный полином степени 0, проходящий через .
Индукция : предположим, что результат верен, когда имеется меньше, чемточки. Позволять - многочлен степени (не выше) проходя через
где - единственный полином степени (не выше) проходя через точки . Предпоследнее равенство вытекает из предположения индукции как вовлекает очков и, таким образом, . Приближаясь к желаемому результату, мы теперь утверждаем, чтопоскольку оба многочлена проходят через и имеют степень (не выше) . Оба эти критерия однозначно определяют полином. Тот факт, что левая сторона проходит через легко понять, как определяется как быть. Чтобы продемонстрировать прохождение левой стороны через, мы будем использовать первый доказанный выше результат вместе с предположением индукции:
где 2-е равенство следует из того, что - многочлен степени (не выше) проходя через удовлетворяющие предположению индукции. Продолжая шаг индукции выше, мы теперь видим, чтогде - многочлен степени проходя через Таким образом, доказательство завершено.
Вся эта работа теперь приводит к тому, откуда взялась формула интерполяции Ньютона. Преобразуя результат выше, отметим, что- многочлен степени (не выше) проходя через , и, таким образом, мы видим, что "продолжая" многочлен к следующей точке требует добавления термина давая нам интерполяционную формулу Ньютона.
Многочлен ТейлораПредел полинома Ньютона, если все узлы совпадают, является полиномом Тейлора , потому что разделенные разности становятся производными.
ЗаявлениеКак видно из определения разделенных разностей, новые точки данных могут быть добавлены к набору данных для создания нового полинома интерполяции без пересчета старых коэффициентов. И когда точка данных изменяется, нам обычно не нужно пересчитывать все коэффициенты. Кроме того, если x i распределены эквидистантно, вычисление разделенных разностей становится значительно проще. Поэтому для практических целей обычно предпочтительнее использовать формулы разделенных разностей, чем форму Лагранжа .
Примеры
Разделенные различия можно записать в виде таблицы. Например, для функции f нужно интерполировать по точкам. Писать
Затем интерполирующий полином формируется, как указано выше, с использованием самых верхних записей в каждом столбце в качестве коэффициентов.
Например, предположим, что мы должны построить интерполирующий полином к f ( x ) = tan ( x ), используя разделенные разности в точках
| | | | |
| | | | |
Используя шестизначную точность, строим таблицу
Таким образом, интерполирующий полином равен
Если в таблице указано большее количество разрядов точности, первый и третий коэффициенты окажутся равными нулю.
Другой пример:
Последовательность такой, что а также , т. е. они из к .
Получаете наклон порядка следующим образом:
Как у нас на спусках порядок , возможен следующий заказ:
Наконец, определим наклон порядка :
Когда у нас есть наклон, мы можем определить следующие многочлены:
- .
- .
Смотрите такжеРекомендацииВнешние ссылки