Введение

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

Формула разности Ньютона, разделенной вперед

Полином Ньютона может быть выражен в упрощенной форме, когда значения аргументов расположены последовательно с равным шагом. Если x₀, x₁, ..., xₖ расположены последовательно и равноотстоящи, то есть xᵢ = x₀ + ih для i = 0, 1, ..., k, и некоторая переменная x выражена как x = x₀ + hν, то разность Δf(x₀ + hν) может быть записана как Таким образом, полином Ньютона принимает вид

Это называется формулой Ньютона для интерполяции с использованием разделенных разностей вперед.

Значение

Формула Ньютона представляет интерес, поскольку является прямой и естественной формой полинома Тейлора, выраженной через конечные разности. Полином Тейлора позволяет определить поведение функции, основываясь на её значении и значениях производных (скорости изменения и скорости изменения скорости изменения и т.д.) в одной конкретной точке x. Формула Ньютона – это полином Тейлора, построенный на основе конечных разностей вместо мгновенных скоростей изменения.

Добавление новых пунктов

Как и в случае с другими формулами разностей, степень ньютоновского интерполяционного многочлена может быть увеличена путем добавления дополнительных членов и точек без отбрасывания существующих. Форма Ньютона отличается простотой: новые точки всегда добавляются с одного конца – формула Ньютона прямого порядка позволяет добавлять новые точки справа, а формула Ньютона обратного порядка – слева. Точность полиномиальной интерполяции зависит от того, насколько близко интерполируемая точка находится к середине диапазона значений x используемого набора точек. Очевидно, что при добавлении новых точек с одного конца эта середина все дальше удаляется от первой точки данных. Следовательно, если заранее неизвестно, сколько точек потребуется для достижения необходимой точности, середина диапазона значений x может оказаться далеко от точки, в которой выполняется интерполяция. Гаусс, Стирлинг и Бессель разработали формулы для решения этой проблемы. Формула Гаусса поочередно добавляет новые точки слева и справа, тем самым сохраняя набор точек центрированным вблизи одного и того же места (вблизи точки, в которой производится вычисление). При этом она использует члены из формулы Ньютона, переименовывая точки данных и значения x в соответствии с выбором точки данных, которая обозначается как x0. Формула Стирлинга остается центрированной вокруг конкретной точки данных и используется, когда вычисляемая точка ближе к точке данных, чем к середине между двумя точками данных. Формула Бесселя остается центрированной вокруг середины между двумя точками данных и используется, когда вычисляемая точка ближе к середине, чем к точке данных. Бессель и Стирлинг достигают этого, иногда используя среднее значение двух разностей, а иногда – среднее значение двух произведений биномов от x, в то время как формулы Ньютона или Гаусса используют только одну разность или произведение. Стирлинг использует среднюю разность в членах нечетной степени (для вычисления которой используется четное число точек данных), а Бессель – среднюю разность в членах четной степени (для вычисления которой используется нечетное число точек данных).

Сильные и слабые стороны различных формул

Для любого заданного конечного набора точек данных существует только один полином наименьшей возможной степени, проходящий через все эти точки. Таким образом, корректно говорить о "форме Ньютона", "форме Лагранжа" и т.п. интерполяционного полинома. Однако различные методы вычисления этого полинома могут обладать разной вычислительной эффективностью. Существует несколько схожих методов, таких как методы Гаусса, Бесселя и Стирлинга. Их можно вывести из метода Ньютона, переобозначая значения x точек данных, но на практике они представляют собой самостоятельную ценность.

Бессел против Стерлинга

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

Методы с разделённой разницей против Лагранжа

Иногда говорят, что интерполяция по Лагранжу требует меньше вычислений, и её рекомендуют для задач, в которых заранее, исходя из предыдущего опыта, известно необходимое количество членов для достижения достаточной точности. Методы разделенных разностей имеют преимущество, поскольку позволяют добавлять больше точек данных для повышения точности, при этом члены, вычисленные на основе предыдущих данных, могут быть повторно использованы. В случае с обычной формулой Лагранжа, увеличение количества точек данных потребует полного пересчета. Существует "барицентрическая" версия интерполяции по Лагранжу, которая позволяет избежать повторного вычисления всей формулы при добавлении новой точки данных, однако она требует сохранения значений каждого члена. Способность методов Гаусса, Бесселя и Стирлинга располагать точки данных симметрично относительно точки интерполяции дает им преимущество перед интерполяцией по Лагранжу, когда заранее неизвестно, сколько точек данных потребуется. Кроме того, предположим, что необходимо определить, достаточно ли точна линейная интерполяция для конкретного типа задачи. Это можно сделать, оценив квадратичный член формулы разделенных разностей. Если квадратичный член пренебрежимо мал – то есть линейный член обеспечивает достаточную точность без его добавления – то линейная интерполяция является достаточной. Если задача достаточно важна, или квадратичный член почти достигает значимого значения, то можно оценить, достаточно ли велика сумма квадратичного и кубического членов для влияния на результат. Разумеется, для этого можно использовать только методы разделенных разностей. В этом случае следует выбирать формулу разделенных разностей и/или точку x0 таким образом, чтобы линейный член формулы использовал две точки данных, между которыми выполняется интересующая нас линейная интерполяция. Формулы разделенных разностей более универсальны и применимы к большему числу задач. Формула Лагранжа наиболее эффективна, когда интерполяция выполняется для одного и того же значения x, а значения y точек данных меняются от задачи к задаче, и когда, исходя из предыдущего опыта, известно необходимое количество членов для достижения достаточной точности. Для интерполирующего многочлена в форме Ньютона существует компактный и эффективный алгоритм для объединения членов и нахождения коэффициентов многочлена.

Точность

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

Общее положение

Для частного случая xi = i существует тесно связанный набор многочленов, также называемых многочленами Ньютона, которые представляют собой просто биномиальные коэффициенты для общего аргумента. Иначе говоря, многочлены Ньютона также задаются в следующей форме: эти многочлены генерируют ряд Ньютона. В свою очередь, ряд Ньютона является частным случаем общих полиномов конечных разностей, позволяющих представить аналитические функции с помощью обобщенных дифференциальных уравнений.

Полином Тейлора

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

Применение

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