Довольно распространенным методом интерполирования является метод Ньютона. Интерполяционный полином для этого метода имеет вид:
P n (x) = a 0 + a 1 (x-x 0) + a 2 (x-x 0)(x-x 1) + ... + a n (x-x 0)(x-x 1)...(x-x n-1).
Задача состоит в отыскании коэффициентов a i полинома P n (x). Коэффициенты находят из уравнения:
P n (x i) = y i , i = 0, 1, ..., n,
позволяющего записать систему:
a 0 + a 1 (x 1 - x 0) = y 1 ;
a 0 + a 1 (x 2 - x 0) + a 2 (x 2 - x 0)(x 2 - x 1) = y 2 ;
- - - - - - - - - - - - - - - - - - - - - - - - - - - -
a 0 +... + a n (x n - x 0)(x n - x 1) ... (x n - x n-1) = y n ;
Используем метод конечных разностей. Если узлы x i заданы через равные промежутки h, т.е.
x i+1 - x i = h,
то в общем случае x i = x 0 + i×h, где i = 1, 2, ..., n. Последнее выражение позволяет привести решаемое уравнение к виду
y 1 = a 0 + a 1 ×h;
y 2 = a 0 + a 1 (2h) + a 2 (2h)h;
- - - - - - - - - - - - - - - - - - -
y i = a 0 + a 1 ×i×h + a 2 ×i×h[(i-1)h] + ... + a i ×i!×h i ,
откуда для коэффициентов получаем
где Dу 0 – первая конечная разность.
Продолжая вычисления, получим:
где D 2 у 0 - вторая конечная разность, представляющая собой разность разностей. Коэффициент а i можно представить в виде:
Поставляя найденные значения коэффициентов а i в значения для P n (x), получим интерполяционный полином Ньютона:
Преобразуем формулу, для чего введем новую переменную , где q – число шагов, необходимых для достижения точки х, двигаясь из точки х 0 . После преобразований получаем:
Полученная формула известна как первая интерполяционная формула Ньютона, или формула Ньютона для интерполирования "вперед". Ее выгодно использовать для интерполирования функции y = f(x) в окрестности начального значения х – х 0 , где q мало по абсолютной величине.
Если записать интерполяционный многочлен в виде:
то аналогичным образом можно получить вторую интерполяционную формулу Ньютона, или формулу Ньютона для интерполирования "назад":
Ее обычно используют для интерполирования функции вблизи конца таблицы.
При изучении данной темы необходимо помнить, что интерполяционные многочлены совпадают с заданной функцией f(x) в узлах интерполяции, а в остальных точках, в общем случае, будут отличаться. Указанная ошибка дает нам погрешность метода. Погрешность метода интерполяции определяется остаточным членом, который для формул Лагранжа и Ньютона одинаков и который позволяет получить следующую оценку для абсолютной погрешности:
| |
Если интерполирование осуществляется с одинаковым шагом, то формула для остаточного члена видоизменяется. В частности, при интерполировании "вперед" и "назад" по формуле Ньютона выражение для R(x) несколько отличаются друг от друга.
Анализируя полученную формулу, видно, что погрешность R(x) представляет собой, с точностью до постоянной произведение двух множителей, из которых один, f (n+1) (x), где x лежит внутри , зависит от свойств функции f(x) и не поддается регулированию, а величина другого,
определяется исключительно выбором узлов интерполирования.
При неудачном расположении этих узлов верхняя граница модуля |R(x)| может быть весьма большой. Поэтому возникает задача о наиболее рациональном выборе узлов интерполирования x i (при заданном числе узлов n) с тем, чтобы полином П n+1 (х) имел наименьшее значение.
Рассмотрим понятие конечных разностей.
Пусть задана функция у=f{x) на отрезке [х 0 , х„], который разбит на п одинаковых отрезков (случай равноотстоящих значений аргумента): Ax=h = const. Для каждого узла х 0 , х, =х 0 + /г, ..., х„ =х () + п h определены значения функции в виде
Введем понятие конечных разностей.
Конечные разности первого порядка
Конечные разности второго порядка
Аналогично определяются конечные разности высших порядков:
Конечные разности функций удобно располагать в таблицах, которые могут быть диагональными (табл. 5.1) или горизонтальными (табл. 5.2).
Диагональная таблица
Таблица 5.1
Горизонтальная таблица
Таблица 5.2
|
а 5 у, |
||||||
|
А 5 Уо |
||||||
|
а 4 у. |
||||||
Первая интерполяционная формула Ньютона
Пусть для функции у=/(х) заданы значения у, =/(х,) для равностоящих значений независимых переменных:
где h - шаг интерполяции.
Необходимо найти полином Р„{х) степени нс выше п, принимающий в точках (узлах) х, значения:
Интерполирующий полином ищется в виде:
Задача построения многочлена сводится к определению коэффициентов а, из условий:
Полагаем в (5.13) х=х 0 , т. к. второе, третье и другие слагаемые равны 0, то
Найдем коэффициент а { .
Приэс=Х1 получим:
Для определения а 2 составим конечную разность второго порядка. При х=х 2 получим:
Аналогично можно найти другие коэффициенты. Общая формула имеет вид:
Подставляя эти выражения в формулу (5.13), получаем:
где х„ у х - узлы интерполяции; х - текущая переменная; h - разность между двумя узлами интерполяции; h - величина постоянная, т. е. узлы интерполяции равно отстоят друг от друга.
Этот многочлен называют интерполяционным полиномом Ньютона для интерполяции в начале таблицы (интерполирование «вперед»), или первым полиномом Ньютона.
Для практического использования этот полином записывают в преобразованном виде, вводя обозначение t=(х - x 0)/h, тогда
Эта формула применима для вычисления значений функции для значений аргументов, близких к началу интервала интерполирования.
Блок-схема алгоритма метода Ньютона для интерполирования «вперед» приведена на рис. 5.3, программа - в приложении.
Пример 5.3. Дана таблица значений теплоемкости вещества в зависимости от температуры C p =f{T) (табл. 5.3).
Таблица 5.3
Воспользуемся формулой (5.16):
Рис. 5.3.
После выполнения преобразований получим интерполяционный многочлен вида:
Полином имеет третью степень и дает возможность вычисления при помощи найденной формулы значения у для неизвестного х.
Пример 5.4. В табл. 5.3.1 приведены значения теплоемкости в зависимости от температуры. Определить значение теплоемкости в точке Г=450 К.
Воспользуемся первой интерполяционной формулой Ньютона. Конечные разности рассчитаны в предыдущем примере (табл. 5.3.2), запишем интерполяционный многочлен при х=450 К:
Таким образом, теплоемкость при температуре 450 К будет
Значение теплоемкости при Г=450 К получили такое же, что и рассчитанное по формуле Лагранжа.
Вторая интерполяционная формула Ньютона
Для нахождения значений функций в точках, расположенных в конце интервала интерполирования, используют второй интерполяционный полином Ньютона. Запишем интерполяционный многочлен в виде
Коэффициенты а 0 , а ь ..., а„ определяем из условия:
Полагаем в (5.18) х=х„, тогда
Полагаем х
=х„_|, тогда
следовательно,
Если x = x n - 2 i то
Аналогично можно найти другие коэффициенты многочлена (5.18):
Подставляя эти выражения в формулу (5.18), получим вторую интерполяционную формулу Ньютона, или многочлен Ньютона для интерполирования «назад»:
Введем обозначения:
Произведя замену в (5.19), получим:
Это вторая формула Ньютона для интерполирования «назад».
Пример 5.5. Вычислить теплоемкость (см. табл. 5.3) для температуры Г=550 К.
Воспользуемся второй формулой Ньютона (5.19) и соответствующими конечными разностями (см. табл. 5.4):
Следовательно, значение теплоемкости при температуре 550 К равно
Лекция 4
1. Конечные разности2. Первая интерполяционная формула
Ньютона
3. Вторая интерполяционная формула
Ньютона
4. Погрешности интерполяции
Конечные разности 1–го порядка
Если интерполируемая функция y = f(x) задана вравноотстоящих узлах, так что xi = x0 + i∙h, где h – шаг таблицы, а
i = 0, 1, … n, то для интерполяции могут применяться формулы
Ньютона, использующие конечные разности.
Конечной разностью первого порядка называется разность yi
= yi+1 - yi, где
yi+1= f(xi+h) и yi = f(xi). Для функции, заданной
таблично в (n+1) узлах, i = 0, 1, 2, …, n, конечные разности
первого порядка могут быть вычислены в точках 0, 1, 2,…, n - 1:
y 0 y1 y 0 ,
y1 y 2 y1,
.......................
yn 1 yn yn 1.
Конечные разности высших порядков
Используя конечные разности первого порядка, можнополучить конечные разности второго порядка 2yi = yi+1 - yi:
2 y 0 y1 y 0 ;
2 y1 y 2 y1;
..........................
2 y n 2 y n 1 y n 2 .
Конечные разности k-го порядка в узле с номером i могут
быть вычислены через разности (k-1)–го порядка:
k yi k 1yi 1 k 1yi
Любые конечные разности можно вычислить через значения
функции в узлах интерполяции, например:
2 y 0 y1 y 0 (y 2 y1) (y1 y 0) y 2 2y1 y 0 .
Таблица конечных разностей
xy
Δy
Δ2y
Δ3y
x0
y0 Δy0 = y1 – y0 Δ2y0 = Δy1 – Δy0 Δ3y0 = Δ2y1 – Δ2y0
x1 = x0 + h
y1 Δy1 = y2 – y1 Δ2y1 = Δy2 – Δy1
x2 = x0 + 2h
y2 Δy2 = y3 – y2
x3 = x0 + 3h
y3
По величине конечных разностей можно
сделать
вывод
о
степени
интерполяционного
многочлена,
описывающего
таблично
заданную
функцию.
Если
для
таблицы
с
равноотстоящими
узлами
конечные
разности k-го порядка постоянны или
соизмеримы с заданной погрешностью, то
функцию можно представить многочленом
k-й степени.
Конечные разности и степень многочлена
Рассмотрим, например, таблицу конечных разностей длямногочлена y = x2 – 3x + 2.
0
y
-0.16
2y
0.08
3y
0
1.2
-0.16
-0.08
0.08
0
1.4
-0.24
0
0.08
1.6
-0.24
0.08
1.8
-0.16
x
y
1.0
Конечные разности третьего порядка равны нулю, а все
конечные разности второго порядка одинаковы и равны 0.08. Это
говорит о том, что функцию, заданную таблично, можно
представить многочленом 2–й степени (ожидаемый результат,
учитывая способ получения таблицы).
Пусть функция y = f(x) задана в n+1 равноотстоящих узлах xi , i = 0, 1,
2,…n с шагом h. Требуется найти интерполяционный многочлен Pn(x)
степени n, удовлетворяющий условию:
Pn(xi) = yi, i =0, 1, 2, …,n .
Будем искать интерполяционный многочлен в виде:
Pn(x) = a0 + a1(x-x0) + a2(x-x0)(x-x1) + … + an(x-x0)(x-x1)…(x-xn-1),
где аi, i = 0, 1, 2,…n – неизвестные коэффициенты, не зависящие от узлов
интерполяции. Найдем эти коэффициенты из условий интерполяции.
Пусть х = x0, тогда Pn(x0) = y0 = a0. Следовательно, a0 = y0.
Пусть х = x1, тогда Pn(x1) = y1 = a0 + a1(x1 - x0) = y0 + a1(x1 - x0), откуда
a1
y1 y0 y0
.
x1 x0
h
Теперь пусть х = х2 , тогда:
Pn (x 2) y 2 a0 a1(x 2 -x 0) a2 (x 2 -x 0)(x 2 -x1) y 0
y 0
2h a2 2h2.
h
Выразив из этого выражения a2, получим:
y 2 2 y0 y0 y 2 2(y1 y0) y0 y 2 2y1 y 0 2 y 0
a2
.
2h2
2h2
2h2
2h2
Первая интерполяционная формула Ньютона
Продолжая подстановки, можно получить выражение для любогокоэффициента с номером i:
i y 0
ai
,
i! hi
i 0,1,...,n.
Подставив найденные значения коэффициентов в исходное выражение,
получим первую интерполяционную формулу Ньютона:
y0
2 y0
n y 0
Pn (x) y0
(x x0)
(x x 0)(x x1) ...
(x x 0)...(x x n 1).
1!h
2!h2
n!hn
Из формулы видно, что в ней используется верхняя строка таблицы
конечных разностей (слайд 4). Особенностью формулы является также
последовательное увеличение степени многочлена по мере добавления
очередных слагаемых. Это позволяет уточнять получаемый результат без
пересчета уже учтенных слагаемых.
Первая интерполяционная формула Ньютона
Первая интерполяционная формула Ньютона может быть записана вболее компактном и удобном для программной реализации виде.
Обозначив
q
x x0
,
h
x x 0 qh
и проведя несложные преобразования вида:
x x1 x x 0 h
q 1;
h
h
x xn
x x2
q n 1,
q 2;.....;
h
h
получим первую интерполяционную формулу Ньютона, выраженную
относительно неизвестной q:
n y 0
2 y0
q(q 1)...(q n 1).
q(q 1) ...
Pn (x) Pn (x0 hq) y0 y0q
n!
2!
10. Первая интерполяционная формула Ньютона
Конечные разности высших порядков, используемые в формулеНьютона, имеют обычно большую погрешность, связанную с ошибками
округления при вычитании близких значений. Поэтому соответствующие
слагаемые формулы имеют также большую погрешность. Чтобы уменьшить
их вклад в сумму, то есть в конечный результат, надо, чтобы выполнялось
условие |q| < 1. Это обеспечивается, если точка интерполяции x находится
между двумя первыми узлами таблицы: x0 < x < x1. По этой причине
интерполяцию с использованием первой формулы Ньютона называют
интерполяцией в начале таблицы или интерполяцией вперед.
интерполяции первая интерполяционная формула Ньютона принимает
следующий вид:
P1(x) y0 y0q.
P2 (x) y 0 y 0 q 2 y 0
q(q 1)
.
2
11. Пример использования первой интерполяционной формулы Ньютона
что и в примере на слайде 6. Требуется найти приближенное
значение функции в точке x = 1.1 путем квадратичной
интерполяции по первой формуле Ньютона.
x
1.0
1.2
1.4
1.6
1.8
y
0
-0.16
-0.24
-0.24
-0.16
y
-0.16
-0.08
0
0.08
2y 3y
0.08 0
0.08 0
0.08
Шаг таблицы h = 0.2
q = (x – x0)/h = 0.5
q(q 1)
2
0.5(0.5 1)
0 (0.16) 0.5 0.08
0.09
2
P2 (x) y 0 Δy 0 q Δ 2 y 0
Результат совпадает с
значением многочлена
y = x2 – 3x + 2, из которого
получена таблица
12. Схема алгоритма вычислений по первой интерполяционной формуле Ньютона
13. Вторая интерполяционная формула Ньютона
Вторая формула Ньютона обладает аналогичными свойствамиотносительно правой части таблицы. Для ее построения используют
многочлен вида:
Pn(x) = a0 + a1(x-xn) + a2(x-xn)(x-xn-1) + … + an(x-xn)(x-xn-1)…(x-x1),
где аi, i = 0, 1, 2, … n – коэффициенты, не зависящие от узлов интерполяции.
Для определения коэффициентов аi будем в это выражение поочередно
подставлять узлы интерполяции. При х = xn Pn(xn) = yn, следовательно,
a0 = yn.
При х = xn-1 имеем Pn(xn-1) = yn-1 = a0 + a1(xn-1-xn) = yn + a1(xn-1-xn),
откуда
a1
yn 1 yn yn yn 1 yn 1
.
xn 1 xn xn xn 1
h
14. Вторая интерполяционная формула Ньютона
Продолжая подстановки, получим выражения для всех коэффициентовмногочлена и вторую интерполяционную формулу Ньютона:
n y 0
yn 1
2 yn 2
Pn (x) yn
(x xn)
(x xn)(x xn 1)
(x xn)...(x x1).
2
n
1!h
2!h
n!h
Из формулы видно, что в ней используется нижняя диагональ таблицы
конечных разностей (слайд 4). Как и в первой формуле Ньютона, добавление
очередных слагаемых ведет к последовательное увеличению степени
многочлена, что позволяет уточнять получаемый результат без пересчета уже
учтенных слагаемых.
Введя обозначение: q
x xn
,
h
x xn hq
и, проделав несложные преобразования, получим вторую интерполяционную
формулу Ньютона, выраженную относительно переменной подстановки q:
n y 0
2 yn 2
Pn (x) yn yn 1q
q(q 1) ...
q(q 1)...(q n 1).
2!
n!
15. Вторая интерполяционная формула Ньютона
Из тех же соображений, что и в случае первой формулы Ньютона, дляуменьшения вычислительной погрешности надо, чтобы выполнялось условие
|q| < 1. Это обеспечивается, если точка интерполяции x находится между
двумя последними узлами таблицы: xn-1 < x < xn. По этой причине
интерполяцию с использованием второй формулы Ньютона называют
интерполяцией е конце таблицы или интерполяцией назад.
Для частных случаев линейной (n=1) и квадратичной (n=2)
интерполяции вторая интерполяционная формула Ньютона принимает
следующий вид:
P1 (x) y n y n 1q
2 y n 2
P2 (x) y n y n 1 q
q(q 1)
2!
16. Пример использования второй интерполяционной формулы Ньютона
Пусть интерполируемая функция f(x) задана той же таблицей,что и в примере на слайде 11. Требуется найти приближенное
значение функции в точке x = 1.7 путем квадратичной
интерполяции по второй формуле Ньютона.
x
1.0
1.2
1.4
1.6
1.8
y
0
-0.16
-0.24
-0.24
-0.16
y
-0.16
-0.08
0
0.08
2y 3y
0.08 0
0.08 0
0.08
Шаг таблицы h = 0.2
q = (x – xn)/h = -0.5
Результат совпадает с
значением многочлена
y = x2 – 3x + 2, из
которого получена
таблица
q(q 1)
2
0.5(0.5 1)
0.16 0.08 (0.5) 0.08
0.21
2
P2 (x) y n Δy n 1 q Δ 2 y n 2
17. Схема алгоритма вычислений по второй интерполяционной формуле Ньютона
18. Погрешности интерполяции
Интерполирующая функция в точках междуузлами интерполяции заменяет интерполирующую
функцию приближенно:
f(x) = F(x) + R(x), где R(x) – погрешность
интерполяции.
Для оценки погрешности необходимо иметь
необходимо иметь определенную информацию об
интерполируемой функции f(x). Предположим, что
f(x) определена на отрезке , содержащем все
узлы xi, и при x, принадлежащем , имеет все
производные f"(x), f""(x), … f(n+1)(x) до (n+1)–го
порядка включительно.
19. Погрешности интерполяции
Тогда20. Выбор узлов интерполяции по формуле Лагранжа
При фиксированной степени многочлена:x*
x0
x1
x2
x3
x4
x5
x
При последовательном увеличении степени
многочлена
x*
x4
x2
x0
x1
x3
x5
x
21. Практическая оценка погрешности интерполяции по формуле Лагранжа
На практике оценка максимального значения производной (n+1)–гопорядка Mn+1 при использовании формулы Лагранжа редко бывает возможна,
и поэтому используют приближенную оценку погрешности
R n (x) f(x) Ln (x) Ln 1 (x) Ln (x) ,
где n число используемых узлов.
Из приведенной формулы следует, что для оценки погрешности
интерполяции многочленом Лагранжа n–й степени необходимо
дополнительно вычислить значение многочлена (n+1)–й степени. Если
допустимая погрешность интерполяции задана, то необходимо, добавляя все
новые узлы, увеличивать степень многочлена до тех пор, пока модуль
разности между двумя последними значениями многочлена |Ln+1(x)-Ln(x)| не
станет меньше заданного значения.
22. Схема алгоритма интерполяции по формуле Лагранжа с заданной точностью
23. Оценка погрешностей интерполяционных формул Ньютона
Для интерполяционныхприобретают следующий вид.
1–я формула Ньютона:
R n (x) h
n 1
формул
Ньютона
оценки
q(q 1) (q n) (n 1)
f
(n 1)!
R n (x) h n 1
q(q 1) (q n)
M n 1
(n 1)!
2–я формула Ньютона:
R n (x) h
n 1
q(q 1) (q n) (n 1)
f
(n 1)!
R n (x) h n 1
q(q 1) (q n)
M n 1
(n 1)!
погрешности
24. Практическая оценка погрешностей интерполяционных формул Ньютона
При использовании интерполяционных формул Ньютона величинуf(n+1)(ξ) можно приближенно оценивать по величинам конечных разностей:
f
(n 1)
n 1
Δ y0
() n 1
h
и в этом случае формулы для оценки погрешности приобретают следующий
вид:
1–я формула Ньютона:
R n (x)
q(q 1) (q n) n 1
Δ y0
(n 1)!
2–я формула Ньютона:
R n (x)
q(q 1) (q n) n 1
Δ y0
(n 1)!
25. Интерполяция по формулам Ньютона с заданной точностью
Сравнивая эти формулы с формуламиНьютона, можно увидеть, что для оценки
погрешности при интерполяции многочленом
n–й степени надо взять дополнительный узел
и вычислить слагаемое (n+1)–й степени.
Если задана допустимая погрешность
интерполяции ε, то надо последовательно
добавлять новые узлы и, соответственно,
новые слагаемые, увеличивая степень
интерполяционного многочлена до тех пор,
пока очередное слагаемое не станет меньше ε.
Аннотация
Пояснительная записка курсовой работы "Интерполяция функции одной переменной методом Ньютона" содержит в себе введение, анализ задания описанием входных и выходных данных, обзор литературных источников, описание математической модели и методов вычислительной математики, пояснения к алгоритму, текст программы, инструкцию. При изучении дисциплины "Информатика" для написания курсовой работы использовались различные литературные источники, которые перечислены в настоящем документе. В данной курсовой работе приведена программа, которая применяется для интерполяции таблично заданной функции методом Ньютона. В ней был использован метод структурного программирования для облегчения написания и отладки программы, а также повышения ее наглядности и читаемости. Целью написания данной работы было получение и закрепление практических навыков разработки алгоритмов различными методами. Представленная программа реализована на языке программирования Pascal. Пояснительная записка содержит 25 листов, на которых размещено два рисунка, текст программы и описание программы и алгоритма.
Введение
Анализ задания
Математическая модель задачи
Программирование функции формулы Ньютона
Обзор литературных источников
Разработка программы по схеме алгоритма
Инструкция пользования программой
Текст программы
Исходные данные и результат решения контрольного примера
Заключение
Список использованных источников
Введение
Современное развитие физики и техники тесно связано с использованием электронных вычислительных машин (ЭВМ). В настоящее время ЭВМ стали обычным оборудованием многих институтов и конструкторских бюро. Это позволило от простейших расчетов и оценок различных конструкций или процессов перейти к новой стадии работы - детальному математическому моделированию (вычислительному эксперименту), которое существенно сокращает потребность в натурных экспериментах, а в ряде случаев может их заменить.
Сложные вычислительные задачи, возникающие при исследовании физических и технических проблем, можно разбить на ряд элементарных -таких как вычисление интеграла, решение дифференциального уравнения и т. п. Многие элементарные задачи являются несложными и хорошо изучены. Для этих задач уже разработаны методы численного решения, и нередко имеются стандартные программы решения их на ЭВМ. Есть и достаточно сложные элементарные задачи; методы решения таких задач сейчас интенсивно разрабатываются.
В связи с этим современный специалист с высшим образованием должен обладать не только высоким уровнем подготовки по профилю своей специальности, но и хорошо знать математические методы решения инженерных задач, ориентироваться на использование вычислительной техники, практически освоить принципы работы на ЭВМ.
Анализ задания
В качестве входных данных использованы:
1. Количество узлов.
2. Табличные значения функции.
Выходными данными, т.е. результатом программы является:
1. Значения таблично заданной функции в промежуточных значениях.
2. График полинома.
Математическая модель задачи
При выполнении курсовой работы была выбрана следующая математическая модель:
Интерполяция и приближение функций.
1. Постановка задачи.
Одной из основных задач численного анализа является задача об интерполяции функций. Часто требуется восстановить функцию
для всех значений на отрезке если известны ее значения в некотором конечном числе точек этого отрезка. Эти значения могут быть найдены в результате наблюдений (измерений) в каком-то натурном эксперименте, либо в результате вычислений. Кроме того, может оказаться, что функция задается формулой и вычисления ее значений по этой формуле очень трудоемки, поэтому желательно иметь для функции более простую (менее трудоемкую для вычислении) формулу, которая позволяла бы находить приближенное значение рассматриваемой функции с требуемой точностью в любой точке отрезка. В результате возникает следующая математическая задача.Пусть и» отрезке
задана сетка сои в ее узлах заданы значения функции
, равные .Требуется построить интерполянту - функцию
, совпадающую с функцией в узлах сетки: .Основная цель интерполяции - получить быстрый (экономичный) алгоритм вычисления значений
для значений , не содержащихся в таблице данных.2. Интерполяция по Ньютону
Дана табличная функция:
| i | ||
| 0 | ||
| 1 | ||
| 2 | ||
| .. | .. | .. |
| n |
Точки с координатами
называются узловыми точками или узлами.Количество узлов в табличной функции равно N=n+1.
Необходимо найти значение этой функции в промежуточной точке, например,
, причем . Для решения задачи используется интерполяционный многочлен.Интерполяционный многочлен по формуле Ньютона имеет вид:
где n – степень многочлена,
Интерполяционная формула Ньютона формула позволяет выразить интерполяционный многочлен
через значение в одном из узлов и через разделенные разности функции , построенные по узлам .Сначала приведем необходимые сведения о разделенных разностях.
Пусть в узлах
,известны значения функции
. Предположим, что среди точек , , нет совпадающих. Разделенными разностями первого порядка называются отношения , , .Будем рассматривать разделенные разности, составленные по соседним узлам, т. е. выражения
Интерполяция применяется во многих задачах, связанных с вычислениями. Укажем некоторые из этих задач. Обработка физического эксперимента – построение приближенных формул по данным вычислительного эксперимента. Здесь возникают нестандартные задачи интерполяции, так как обычно пишутся формулы, возможно, более простой структуры.
Интерполяционные формулы используются также при вычислении интегралов, при написании разностных аппроксимаций для дифференциальных уравнений, на основе интегральных тождеств.
Часто требуется восстановить функцию f(x)
на отрезке a ≤ x ≤ b
, если известны её значения в некотором конечном числе точек этого отрезка.
На практике чаще всего применяют интерполяцию многочленами. Это связано, прежде всего, с тем, что многочлены легко вычислять, легко аналитически находить их производные и множество многочленов плотно в пространстве непрерывных функций. Мы рассмотрим более подробно метод Ньютона.
В таблице 1 приведены данные временной сложности алгоритмов.
Таблица 1
Входные данные:
x
— координата, в которой необходимо вычислить.
n
– Количество узлов.
Step
– шаг интерполяции
Множество MasX
– Значения x
.
Множество MasY
– Значения f(x)
.
Выходные данные:
res
– значение полинома в точке x
.
Алгоритмическая модель метода Ньютона:
Множество mas мощностью |n + 2, n + 1|;
Для всех i от 0..2:
Для всех j от 0..n+1:
Если i = 0:
masi,j = MasXj;
иначе Если i = 1:
masi,j = MasYj;
m = n;
Для всех i от 2..n+2:
Для всех j от 0..m:
masi,j = mas(i-1),(j+1) – mas(i–1),j;
m = m-1;
Множество dy0 мощностью |n + 1|;
Для всех i от 0..n+1:
dy0i = mas(i + 1),0;
res = dy00;
Множество xn мощностью |n|;
xn0 = x - mas0,0;
Для всех i от 1..n:
ans = xni - 1 * (x - mas0, i);
xni = ans;
ans = 0;
m1 = n + 1;
fact = 1;
Для всех i от 1..m1:
fact = fact * i;
res = res + (dy0i * xni - 1) / (fact * stepi);
На рисунке 1 изображена схема интерполяции метода Ньютона.
Рисунок 1 — интерполяция метода Ньютона
// x - координата, в которой необходимо вычислить значение полинома Ньютона; n - количество узлов; MasX - массив x; MasY - массив значений x; step - шаг public double Newton(double x, int n, double MasX, double MasY, double step) { double[,] mas = new double; for (int i = 0; i < 2; i++) { for (int j = 0; j < n + 1; j++) { if (i == 0) mas = MasX[j]; else if (i == 1) mas = MasY[j]; } } int m = n; for (int i = 2; i < n + 2; i++) { for (int j = 0; j < m; j++) { mas = mas - mas; } m--; } double dy0 = new double; for (int i = 0; i < n + 1; i++) { dy0[i] = mas; } double res = dy0; double xn = new double[n]; xn = x - mas; for (int i = 1; i < n; i++) { double ans = xn * (x - mas); xn[i] = ans; ans = 0; } int m1 = n + 1; int fact = 1; for (int i = 1; i < m1; i++) { fact = fact * i; res = res + (dy0[i] * xn) / (fact * Math.Pow(step, i)); } return res; }
Составим таблицу значений для f(x) = x^3.
Найдем полимер в точке 2.1: f(2.1) = 2.1^3=9,261
С помощью программной функции мы получили такой же результат (Рисунок 2).
Рисунок 2 — применение функции
Нами были рассмотрены основные метода интерполяции многочленами. На практике чаще всего применяют интерполяцию многочленами. Это связано, прежде всего, с тем, что многочлены легко вычислять, легко аналитически находить их производные и множество многочленов плотно в пространстве непрерывных функций. Мы рассмотрели более подробно метод Ньютона.
Мы построили математическое описание методов, после чего приступили к разработке схемы программы.
Разработали программу реализующую интерполяцию метода Ньютона, на языке C# в Visual Studio 2012.
Протестировали программу, все тесты на основе заданных нами данных были успешно пройдены.