Второй интерполяционный полином ньютона

Второй интерполяционный полином ньютона

Пусть y = y(x), y1 = y(x1), …, yn = y(xn) — значения функции y(x) в узлах интерполяции. Тогда разности

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

Разностями второго порядка или вторыми разностями называются разности первых разностей, т.е.

Аналогично определяются последующие разности. Например, разность (к+1)-го порядка получается из разности k-го порядка по формулам

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

Введем так называемые разделенные разности .

Разделенные разности первого порядка определяются формулой

Разделенные разности второго порядка определяются формулой

Разделенные разности k-го порядка определяются формулой

В случае равностоящих узлов с шагом h для разделенных разностей имеем формулы:

Если у(x)=Pn(x) — полином степени n , то для него первая разделенная разность P(x, x) = (P(x) – P(x)) / (x – x) — есть полином степени (n-1), вторая разделенная разность P(x,x,x1) — полином степени (n-2), так что разделенная разность (n+1)-го порядка равна нулю.

Разделенные разности располагаются по схеме:

Рассмотрим первую разделенную разность для функции y(x)

и т.д. Отсюда получаем формулу

. (6.10)

Если положить в формуле (6.10) x = xk, k = 0, 1, …, n, получим Pn(xk) = yk.

Следовательно, полином (6.10) является интерполяционным полиномом, построенным по (n+1) узлам x, x1, . , xn . Он называется интерполяционным многочленом Ньютона.

В силу того, что любой k-й член полинома Ньютона (6.10) зависит только от к первых узлов интерполяции и от значений функции в этих узлах, добавление новых узлов вызывает лишь добавление в формуле (6.10) новых членов без изменения первоначальных, в этом состоит существенное, с точки зрения организации вычислений, преимущество полинома Ньютона по сравнению с полиномом Лагранжа.

Формулу для полинома Ньютона (6.10) можно переписать в следующем виде:

В данном случае базис состоит из функций вида

,

В этом случае ck = y(x, x1, . xk), После вычисления коэффициентов ck , значения полинома Ньютона в точке x удобно вычислять по схеме Горнера

Вычисление значений x полинома Pn(x) (после вычисления ck) требует n умножений и 2n сложений (или вычитаний), т.е. Q = 3n.

На практике избегают пользоваться интерполяционными многочленами высоких степеней. Объясняется это тем, что с ростом числа узлов сетки погрешность интерполирования f(x) – Ln(x) может не только не уменьшаться, но и в некоторых случаях постепенно расти с увеличением n. В этом случае говорят, что интерполяционный процесс расходится. Например, последовательность многочленов Ньютона, построенных для непрерывной функции f(x) = x на отрезке [-1, 1] не сходится к функции f(x) = x ни в одной точке отрезка [-1, 1] кроме точек –1, 0, 1. Поэтому более предпочтительной является интерполяция сплайнами, к рассмотрению которой мы переходим.

Читайте также:  Где закупать товар в китае

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: Увлечёшься девушкой-вырастут хвосты, займёшься учебой-вырастут рога 10356 — | 8005 — или читать все.

Рассмотрим понятие конечных разностей.

Пусть задана функция у=f на отрезке [х, х„], который разбит на п одинаковых отрезков (случай равноотстоящих значений аргумента): Ax=h = const. Для каждого узла х, х, + /г, . х„ () + п h определены значения функции в виде

Введем понятие конечных разностей.

Конечные разности первого порядка

Конечные разности второго порядка Аналогично определяются конечные разности высших порядков:

Конечные разности функций удобно располагать в таблицах, которые могут быть диагональными (табл. 5.1) или горизонтальными (табл. 5.2).

Первая интерполяционная формула Ньютона

Пусть для функции у=/(х) заданы значения у, =/(х,) для равностоящих значений независимых переменных:

где h — шаг интерполяции.

Необходимо найти полином Р„ <х)степени нс выше п, принимающий в точках (узлах) х, значения:

Интерполирующий полином ищется в виде:

Задача построения многочлена сводится к определению коэффициентов а, из условий:

Полагаем в (5.13) х=х, т. к. второе, третье и другие слагаемые равны 0, то

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

Аналогично можно найти другие коэффициенты. Общая формула имеет вид:

Подставляя эти выражения в формулу (5.13), получаем:

где х„ ух — узлы интерполяции; х — текущая переменная; h — разность между двумя узлами интерполяции; h — величина постоянная, т. е. узлы интерполяции равно отстоят друг от друга.

Этот многочлен называют интерполяционным полиномом Ньютона для интерполяции в начале таблицы (интерполирование «вперед»), или первым полиномом Ньютона.

Для практического использования этот полином записывают в преобразованном виде, вводя обозначение t=(х — x)/h, тогда

Читайте также:  Запись виндовс на флешку через руфус

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

Блок-схема алгоритма метода Ньютона для интерполирования «вперед» приведена на рис. 5.3, программа — в приложении.

Пример 5.3. Дана таблица значений теплоемкости вещества в зависимости от температуры Cp=f (табл. 5.3).

С помощью разделенных разностей можно построить многочлен

P n (x) = f(x 0 ) + (x − x 0 ) · f(x 0 , x 1 ) + (x − x 0 )(x − x 1 ) · f(x 0 , x 1 , x 2 ) + . . .

+(x − x 0 )(x − x 1 ) . . . (x − x n−1 ) · f(x 0 , x 1 , . . . , x n ).

Он называется интерполяционным полиномом Ньютона для заданной функции . Эта форма записи более удобна для применения, поскольку при добавлении к узлам x 0 , x 1 , . . . , x n нового узла x n+1 все вычисленные ранее члены остаются без изменения, а в формулу добавляется только одно слагаемое. Применяя же формулу Лагранжа надо делать все вычисления вновь.

Если значение функции заданы для равноотстоящих значений аргумента x 0 , x 1 = x 0 + h, . . . , x n = x 0 + n · h (постоянную величину h = x i+1 − x i , i = 0, 1, . . . , n называют шагом интерполяции),

• Назад • Первая • Предыдущая • Следующая • Последняя • Перейти • Предметный указатель

то интерполяционный полином приобретет вид

− x 1 ) . . . (x − x n−1 ).

Здесь k y 0 — конечные разности k-го порядка. Они определяются по формуле

= i=0 ( − 1) i c k i y k−i ,

где c k i — биномиальные коэффициенты.

Сравнивая эту формулу с предыдущей, легко установить, что при x i = x 0 + ih (i = 0, n) конечные и

разделенные разности связаны соотношением вида

f(x 0 , x 1 , . . . , x n ) =

Для практического использования формулу ( 6.5 ) записывают в превращенном виде. Для этого введем новую переменную величину t, положив x = x 0 + ih, где t = — количество шагов h, необходимых для достижения точки x из точки x 0 . После внесения указанных величин в выражение для P n (x) получим первую интерполяционную формулу Ньютона для интерполирования вперед, то есть вблизи начала таблицы:

Читайте также:  Где найти корзину в телефоне самсунг

t(t − 1) . . . (t − n + 1)

Предположим, что точка интерполяции расположена ближе к конечной точке x n таблицы. В этом случае узлы интерполяции следует брать в порядке x n , x n − h, x n − 2h, . . .. Формула Ньютона для ин-

• Назад • Первая • Предыдущая • Следующая • Последняя • Перейти • Предметный указатель

терполирования назад тогда будет иметь вид

P n (x) = f(x n ) + f(x n , x n−1 )(x − x n ) + +f(x n , x n−1 , x n−2 )(x − x n )(x − x n−1 )+

. . . + f(x 0 , x 1 , . . . , x n )(x − x n )(x − x n−1 ) . . . (x − x 1 ).

Разделенные разности можно выразить через конечные разности, если воспользоваться возможностью переставлять в них аргументы, и соотношением ( 6.7 ), из которых вытекает

f(x n , x n−1 , x n−2 ) = f(x n−2 , x n−1 , x n ) =

Введем переменную t, положив x = x n + th, получим для f(x) формулу Ньютона для интерполирования в конце таблицы

= y(x) вторую интерполяционную

t(t + 1) . . . (t + n − 1)

Как первая, так и вторая интерполяционные формулы Ньютона могут быть использованы для экстраполяции функции, то есть для нахождения значений функции y, значение аргументов x которой лежат вне таблицы. Если x 0 и значение x близкое к x 0 , то выгодно использовать первый интер-

поляционный полином Ньютона, тогда t = x − x n и t > 0. Таким образом, первая интерполяционная h

формула Ньютона применяется для интерполирования вперед и экстраполирования назад, а вторая — наоборот, для интерполирования назад и экстраполирования вперед.

Укажем, что операция экстраполирования, вообще говоря, менее точная, нежели операция интерполирования.

• Назад • Первая • Предыдущая • Следующая • Последняя • Перейти • Предметный указатель

Многочлены Чебышева

Как видно из формулы ( 6.3 ), погрешность замены функции y = f(x) интерполяционным многочленом зависит от выбора узлов интерполяции x 1 , x 2 , . . . , x N . Прежде чем перейти к вопросу о рациональном выборе узлов интерполяции, рассмотрим некоторые свойства одного из важнейших и хорошо изученных сейчас классов специальных функций — многочленов Чебишева первого рода, которые часто используютсяся для приближения функций. Многочлен Чебишева n-й степени определяется по формуле

Ссылка на основную публикацию
Вин 10 1809 отзывы
Microsoft выпустила очередное крупное, то есть в этот раз некрупное обновление для операционной системы Windows 10. Я думаю, ни для...
Блюстакс как войти в аккаунт гугл
Приложение Bluestacks – специальная утилита для компьютеров, позволяющая создать виртуальный образец смартфона либо планшета на ПК. Эмулятор позволяет запустить любую...
Блюр эффект в макияже
Мы, современные женщины, очень разбалованы косметикой. Мы хотим моментального эффекта, поэтому так прочно сидим на сыворотках и тканевых масках, которые...
Винда загружается только в безопасном режиме
После обновления операционной системы как Windows 7, так и Windows 10, пользователи могут столкнуться с неполадкой, когда компьютер загружается только...
Adblock detector