Случай равномерного распределения узлов интерполяции

В случае равномерного распределения узлов интерполяции выражаются через расстояние между узлами интерполяции h и начальную точку :

,

и, следовательно,

Подставив эти выражения в формулу базисного полинома и вынеся h за знаки перемножения в числителе и знаменателе, получим

Теперь можно ввести замену переменной

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

19. Построение кривой по точкам. Интерполяционный полином Ньютона. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.

Многочлен Ньютона интерполяционный – как и другие интерполяционные формулы (см. интерполяция), служит для построения многочлена n -й степени, который совпадает в (n +1) точке co значениями неизвестной искомой функции у = f (x).

Пусть в точках х ₀, х ₁, …, х _n+1 значения функции у = f (x) равны соответственно у ₀ = f (x ₀), y ₁ = f (x ₁), …, y _n+1 = f (x _n+1).

Построим интерполяционный многочлен Ньютона с помощью метода неопределенных коэффициентов. Для этого запишем искомый многочлен в виде
P_n (x) = b ₀ + b ₁(x – x ₀) + b ₂(x – x ₀)(x – x ₁) + b ₃(x – x ₀)(x – x ₁)(x – x ₂) + … + b _n(x – x ₀)…(x – x _n). (1)

Последовательно подставляя в формулу (1) вместо х данные значения х ₀, х ₁,..., х _n+1, получим для нахождения неопределенных коэффициентов b ₀, b ₁,..., b _n«треугольную» систему уравнений

(при подстановке в равенство (1) вместо х числа х ₀ в правой части равенства обратились в нуль все слагаемые, кроме первого: там везде был множитель (х – х ₀), обратившийся в нуль; при подстановке х = х ₁ обратились в нуль все слагаемые, кроме первого и второго – они содержат множитель (х – х ₁) и т.д.).

Полученную систему удобно решать: из первого её уравнения находим свободный член искомого многочлена b ₀; подставив его во второе уравнение, находим коэффициент b ₁ при первой степени х в искомом многочлене:

и т.д.

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