Интерполяционные полиномы Лагранжа и Ньютона

Вначале определим полином первой степени, проходящий через точки (х₀, у₀) и (х, у). Линейный полином.

имеет требуемое свойство, так как Р (х₀) = г/₀ и Р (х) = у Построим теперь полином степени не выше чем N, удовлетворяющий условиям.

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

где сомножители 1_п(х) задаются как.

Полином (8.2) называется интерполяционным полиномом Лагранжа степени N. Для вычисления значения интерполяционного полинома в некорой точке х, не прибегая к явному вычислению коэффициентов полинома, применяется схема Невилла (Neville). На первом этапе зададим значения.

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

и окончательно мы получаем.

Пример 8.1 (интерполяционный полином Лагранжа) В табл. 8.1 представлены значения у_п в соответствующих точках х_п и требуется провести гладкую кривую через эти точки.

Таблица 8.1

Определим сомножители 1_п(х), которые для данного набора данных записываются как.

Тогда интерполяционный полином Лагранжа имеет вид.

Предположим, что нам нужно вычислить значение Р$(х) в промежуточной точке х = 3, тогда схема Невилла (8.3) представляется в виде следующей таблицы:

Легко проверить, что Pq^S)(3) = Рд{3). На рис. 8.1 показан интерполяционный полином Лагранжа вместе с исходными данными из табл. 8.1.

Рис. 8.1. Гладкая кривая, описывающая данные из табл. 8.1:

О — данные;—интерполяционный полином Лагранжа Представление интерполяционного полинома в форме (8.2) имеет простой вид, и поэтому оно часто используется для теоретического анализа. Однако с точки зрения практических вычислений такое представление применимо только для небольших значений N. С увеличением N сомножители 1_п(х) возрастают и начинают сильно осциллировать. Существует другое представление интерполяционного полинома, которое лучше подходит для вычислений, и оно основано на разделенных разностях. Пусть заданы различные точки х₀,…, x_N и значения в этих точках у₀, …, у_jV. Разделенные разности нулевого порядка есть просто значения у_п:

Разделенные разности порядка k в точке х_п вычисляются, но следующим рекурентным формулам:

Тогда, используя введенные обозначения, интерполяционный полином, удовлетворяющий условию (8.1), записывается в виде.

Полином (8.4) называется интерполяционным полиномом Ньютона. Его можно представить и в другой форме:

Используя это представление, значение интерполяционного полинома Ньютона в некоторой точке х может быть вычислено простым и эффективным способом. Этот алгоритм называется схемой Горнера (Horner) и задается следующими рекурентными формулами:

Тогда требуемое значение полинома равно последнему элементу этой последовательности, т. е. Р^(х) = я₀.

Таблица 8.2

Пример 8.2 (интерполяционный полином Ньютона) Рассмотрим данные, представленные в табл. 8.1. Разделенные разности, вычисленные на основе этих данных, показаны в табл. 8.2.

Коэффициенты интерполяционного полинома Ньютона расположены в первом столбце этой таблицы. Тогда этот полином записывается в виде.