Оценка погрешности
интерполяционных формул
При заданном наборе узлов интерполяции
существует один и только один
интерполяционный многочлен. Формулы Лагранжа,
Ньютона, Гаусса и другие порождают один и тот
же многочлен (при условии, что вычисления
производятся точно). Разница между ними лишь в
алгоритме построения, а многочлен Лагранжа не
содержит явных выражений для коэффициентов.
Исходя из принципа построения
интерполяционного полинома, следует, что в
точках узлов значения полинома и табличной
функции полностью совпадают. В других же точках
существует разница между полиномом и функцией,
которая определяется остаточным членом
R
xf
x
L
x
n
n
Пусть функция f (x ) во всей области a x b
n
1
имеет производные f
x
,f
x
,f
x
,...,
f
x
до n 1 порядка включительно. Введём
вспомогательную функцию
u
x
f
x
L
x
k
x
n
n
1
где
x
x
x
x
x
x
x
...
x
x
n
1
0
1
2
n
k - постоянный коэффициент.
x0,x1,x2,....
xn
Функция u x имеет n 1 корень в точках
Выберем коэффициент k таким образом,
чтобы функция u x имела n 2 -й
корень в любой, но фиксированной, точке x
отрезка
не совпадающей с
a ,b
узловыми точками.
Для этого нужно положить
f
x
L
x
k
x
0(*-*)
n
n
1
Отсюда, так как
, следует
k
x
0
n1
fxL
x
n
k
x
n
1
(*--*)
При таком выборе коэффициента k функция u x
будет иметь n 2 корня на отрезке a ,b
и обращаться в нуль на концах каждого отрезка
x
,
x
,
x
,
x
,
...,
x
,
x
x
,
x
,...
x
,
x
0
1
1
2
i
i
1
n
1
n
Применяя теорему Ролля к каждому из этих
отрезков, можно сделать вывод, что производная
u x имеет не менее n 1 корня на отрезке a ,b .
Теорема Ролля
Производная f x действительного многочлена
f (x) имеет нечётное число действительных корней
между двумя соседними действительными корнями
многочлена f (x ).
Вторая производная u x имеет не менее
n корней на отрезке a ,b . Продолжая
эти рассмотрения для производных более
высоких порядков, можно сделать вывод,
n1
x
что производная u
имеет хотя
n1
бы один нуль на отрезке a ,b , т.е. u 0
.
n
1
n1
x
n
1
!
Так как Ln x0и
, то из
n
1
n
1
n
1
(*-*) имеем
u x
f x
k
n
1
!
1
и при x получаем 0
n
fn
k
1
!
f
, откуда следует k n1!
n1
(*---*)
Сравнивая правые части (*--*) и (*---*)
получаем соотношение
n
1
f
x
L
x
f
n
n
1
!
x
n
1
и, следовательно,
f
(*-4-*)
f
x
L
x
x
n
1
n
1
! n
n
1
т.к x произвольно, то можно записать
(*-4-*) в виде
n
1
f
(*-5-*)
R
x
f
x
L
x
x
n
n
1
n
1
! n
где зависит от x и лежит внутри
отрезка a ,b .
Введя обозначение M
max
f
x
n
1
a
x
d
получаем оценку абсолютной погрешности
интерполяционной формулы Лагранжа
n
1
M
n
1
R
x
f
x
L
x
x
n
n
n
1
n
1
!
(*-6-*)
x
x
x
x
x
...
x
x
n
1
0
1
n
x x0
Используя замену q
h
записать как (*-7-*)
можно (*-6-*)
M
n
1
n
1
R
x
f
x
L
x
q
q
1
q
2
...
q
n
h
n
n
n
1
!
Из проведенной оценки абсолютной
погрешности интерполяционной формулы
Лагранжа можно для функции f (x ) с
равноотстоящими узлами (первая
интерполяционная формула Ньютона)
записать
n
1
f
n
1
R
x
q
q
1
q
2
...
q
n
h
n
n
1
!
где - некоторое промежуточное
значение между узлами интерполирования
x0,x1,x2,....
xn и точкой x .
Интерполяционная формула Ньютона, как
правило, обрывается на членах,
содержащих такие разности, которые в
пределах заданной точности можно
считать постоянными.
n 1
Полагая, что конечные разности y
почти постоянны для функции f (x ) и шаг h
достаточно мал, и учитывая, что
n
1
y
x
lim
n
1
h
0h
n
1
f
можно положить
y
0
n1
h
n
1
f
n
1
тогда остаточный член для первой
интерполяционной формулы Ньютона
n
1
y
n
1
0
R
x
q
q
1
q
2
...
q
n
h
n
n
1
!
При тех же условиях остаточный член для
второй интерполяционной формулы
Ньютона
n
1
y
n
1
n
R
x
q
q
1
q
2
...
q
n
h
n
n
1
!
Выбор способа интерполяции –
локального или глобального - определяется
особенностями решаемой задачи
(точностью, быстродействием и др.).
Повышение степени интерполяционного
полинома (при локальной интерполяции) не
всегда повышает точность интерполяции,
т.к. не всегда ясно поведение производной
n1
f
x при увеличении n
Интерполяция табличной функции
с неравноотстоящими узлами
Единственность полинома Лагранжа.
Пусть существует другой полином Qn x
степени не выше n , который решает задачу
интерполяции Qnxi yi
Построим новый многочлен
,
Rx
Lx
Qx
n
n
n
который имеет степень не выше n и во всех
xn обращается в нуль, в силу
узлах x0,x1,x2,....
x
x
L
y
равенства значений Q
.
n
i
n
i
i
xn
Получается, что точки x0,x1,x2,....
являются корнями многочлена Rn x
.
Многочлен Rn x не может иметь более
корней n . Следовательно, многочлены Qn xi и
Ln xi должны полностью совпадать
Разделённые разности
На практике часто встречаются таблицы
с неравноотстоящими узлами, т.е. таблицы с
переменным шагом. Для этих таблиц понятие
конечных разностей обобщается введением
так называемых разделённых разностей.
Пусть функция y f x задана
yn
таблично y0,y
1,y
2,...
xn , а
и значения аргумента x
0,x
1,x
2,....
x
x
x
0
i
i
1
i
i
0
,
1
,
2
,...
соответствующие значения функции, у которой
разности не равны между собой.
Отношения вида
y
y
i
1
i
xi,xi1
x
x
i
1
i
называются разделёнными разностями первого
порядка.
По аналогии - разделённые разности второго
порядка запишутся как
x
,
x
x
,
x
i
2
i
1
i
1
i
x
,
x
,
x
i
i
1
i
2
x
x
i
2
i
По аналогии строятся разделённые разности
более высоких порядков.
Интерполяционная формула Ньютона
для неравноотстоящих значений
аргумента записывается как
P
x
y
x
,
x
x
x
0
0
1
0
x
,
x
,
x
x
x
x
x
...
0
1
2
0
1
x
,
x
,...
x
x
x
x
x
...
x
x
0
1
n
0
1
n
1
Интерполяция сплайнами
Механическая модель сплайна
Узлы фиксации
Гибкий стержень
Форма этого стержня описывается функцией y S x
Из курса сопротивления материалов известно, что
уравнение свободного равновесия имеет вид
IV
S
x 0
следовательно, между парой соседних узлов
интерполяции функция S x является
многочленом степени не выше третьей.
S
x
S
x
a
b
x
x
c
x
x
d
x
x
,
i
i
i
i
1
i
2
i
1 i
x
x
x
i
1
i
(*)
3
i
1
На каждом отрезке xi1 xxi имеется четыре
неизвестных коэффициента
ai , bi , ci ,di , следовательно, на всём интервале
x0 , xn число неизвестных - 4n . Для их
определения необходимо построить систему 4n
уравнений.
На каждом отдельном участке xi 1 , xi из условия
прохождения графика функции S x через заданные
точки следует
S
x
y
,S
x
y
i
i
1
i
1
i
i
i
Эти условия можно записать в виде
S
x
a
y
i
i
1
i
1
i
1
S
x
a
b
c
h
d
h
y
i
i
i
ih
i
i
2
ii
h
x
x
,
i
i
i
1
3
ii
i
1
,2
,
3
,
...,
n
Эта система содержит уравнений 2n .
Свободное равновесие обеспечиваются условиями
непрерывности первых и вторых производных во
внутренних узлах интерполяции, т.е. условиями
гладкости второго порядка кривой во всех
внутренних точках –
S
x
S
x
,S
x
S
x
, (**)
i
i
i
1
i
i
i
i
1
i
i
1
,
2
,
3
,
...
,
n
1
Вычисляя эти производные из многочлена
2
(***)
S
x
b
2
c
x
x
3
d
x
x
,
i
i
i
i
1
i
i
1
S
x
2
c
6
d
x
x
i
i
i
i
1
Подставляя эти выражения в (**)получаем
уравнений
2
b
b
2
h
c
3
h
i
1
i
i i
id
i
(*)
ci1 ci 3
h
id
i
i1
,2
,3
,...
,n
1
(*4*)
2n 2
Оставшиеся необходимые два уравнения
получаются из условий закрепления концов
сплайна, в которые входят значения первой и
второй производной функции S x в точках x 0 и
i
i
S
b
2
c
n . Из (***) следует,
ix
1
i, S
ix
1
i
и, следовательно, в точке x 0 имеем ,
x
S
x
b
,S
x
2
c
1
0
1
1
0
1
т.е. значения производных в точке x 0
присутствуют в системе. Значения производных в
точке x n отсутствуют в системе, поэтому они
вводятся с помощью дополнительных переменных
bn 1 и c n 1 , т.е.
S
x
b
,S
x
2
c
n
n
1
n
n
1
Из условия непрерывности производных в точке x n
2
следует, что b
b
2
h
c
3
h
d
n
1
n
nn
n
ni
c
c
3
h
d
n
1
n
n
n
С учётом этих дополнений (*4*) можно
рассматривать для всего диапазона индексов
i 1,2,3,...,n
Построенная таким образом система содержит
4n 2 неизвестных и 4n уравнений.
Эту систему можно дополнить одним из двух
условий закрепления концов сплайна:
S
x
b
k
, S
x
b
k
0
1
1
n
n
1
2 (%)
или
S
x
2
c
m
, S
x
2
c
m
0
1
1
n
n
1
2(%%)
где k1, k2, m
1, m
2 - заданные числа.
Например, из рис. «Механическая модель сплайна»
видно, что при заданных углах наклона и
k
tg
, k
tg
1
2
При свободном закреплении концов сплайна, можно
приравнять нулю кривизну линии в точках
закрепления (т.е. вторые производные равны
нулю). Полученная таким образом функция
называется свободным кубическим сплайном.
С учётом (%) или (%%) получаем систему 4 n 2
уравнений для определения коэффициентов
- 2n уравнений,
a
i
1
,2
,...,
n
i,d
i
b
i,c
i
i
1
,2
,...,
n
1 - 2n 2 уравнений.
Полученную систему линейных алгебраических
уравнений можно существенно упростить,
используя условия сшивки функции S x на
n)
границах отдельных участков (в узлах i 1, 2,...,
по значениям функции и её первой и второй
производным.
ai = yi 1
ci1 ci
di
3hi
y
y
i
i
1 h
i
b
c
2
c
i
i
1
i
h
3
i
Система уравнений относительно коэффициентов
y1 y0
2
1
h1*c1 h1*c2
k1
3
3
h1
ci
y2 y1 y1 y0
h1*c1 2h1 h2 *c2 h2 *c3 3
h h
1
2
y3 y2 y2 y1
h2 *c2 2h2 h3*c3 h3 *c4 3
h h
c
3
2
..........
..........
..........
..........
.........
i
yn yn1 yn1 yn2
hn1*cn1 2hn1 hn *cn hn *cn1 3
h
h
n
n1
yn yn1
1
2
hn *cn hn *cn1 k2
3
3
hn
1
3
5
0
2
4
y
y
1
0
k
1
h
1
y
y0
y2y
1
1
1
2
3
*
h
h
0
0
0
0
c
1
1
h
h
3
1
2
1
3
h 2
h
h
h
0
0
0 c
y
y2 y2y
1
2
2
3
1
1
2 3
*
0
h
2
h
h
h
0
0
c
3
h
h
2
2
3
3
3
2
0
h3h4 h4
0
h
2
0 c
y
y
y2
3
4 y
4
3
3
3
*
0
h
h4h5 h5 c5 h4
0
0
h
2
3
4
1
2
y
y4 y4y
5
3
6
c
3
0
0
0
0
h
h
5
5
*
h
3
3
h
5
4
k ynyn1
2
h
n
аппроксимация
Аппроксимация табличной функции
y
f(xi)
Невязка
yi
i f(xi )yi
mini2
x
xi
y
Экспериментальные
данные с погрешностью
измерений
Аппроксимирующая
функция
x
Метод наименьших квадратов.
Метод наименьших квадратов заключается в
построении функции приближения на всём
множестве точек xi
. В качестве функции
приближения используем полином
x
c
c
x
c
x
c
x
...
c
x
0 1
2
3
2
3
m
m
Для каждого значения табличной функции y f (x)
можно записать
c
c
x
cx
cx
...
cx y
1
0
1
1
1
2
21
3
31
m
m1
c
c
x
cx
cx
...
cx y
2
0
1
2
2
2
22
3
32
m
m2
i
2
3
m
c
c
x
c
x
c
x
...
c
x
y
3
0
13
23
33
m3
3
..........
..........
..........
..........
..........
..........
.........
...
2
3
m
c
c
x
c
x
c
x
...
c
x
y
n
0
1n
2n
3n
mn
n
где i - невязка, т.е. разница между значением y i
и значением приближающей функции xi в
точке xi .
Наилучшее приближение табличной функции
y f (x) определяется путём минимизации
функции S построенной из невязок i .
n
n
xi,c0,c1,c2,...,
yi
S
c
m
i
0
2
i
2
i
0
или
n
S
c
c
x
cx
...
cx y
0
1
i
i
i
0
2
2i
m
mm
2
cm
Считаем коэффициенты c0,c
1,c
2,...,
независимыми переменными, тогда условия
минимума функции S определяются из
выполнения условий минимума
S
S
S
S
0
,
0
,
0
,
0
c
c
c
c
0
1
2
m
n
S
2c0 c1xi c2xi2 c3xi3 ...cmximyi 0
co
i0
n
S
2c0 c1xi c2xi2 c3xi3 ...cmximyi xi 0
c1
i0
n
S
2c0 c1xi c2xi2 c3xi3 ...cmximyi xi2 0
c2
i0
..........
..........
..........
..........
..........
..........
..........
...
n
S
2
3
m
m
2c0 c1xi c2xi c3xi ...cmxi yi xi 0
cm
i0
cm
Собирая коэффициенты при неизвестныхc0,c1,c2,...,
получаем систему уравнений
n
n
n
n
n
0
i
0
i
0
i
0
i
0
i
n
n
n
n
n
n
0
i
0
i
0
i
0
i
0
i
0
i
m
3
2
n1c0c1
yi
x
c
...
x
c
x
c
x
i
m
i
3
i
2
i
1
m
4
3
2
x
x
c
...
x
c
x
c
x
c
x
c
i
i
iy
m
i
3
i
2
i
1
i
0
n
n
n
n
n
n
2
x
x
c
...
x
c
x
c
x
c
x
c
i yi
m
3
2
1
0
0
i
2
i
0
i
3
i
0
i
4
i
0
i
5
i
0
i
2
m
i
0
i
.......
..........
..........
..........
..........
..........
..........
..........
..........
n
n
n
n
n
n
0
i
0
i
0
i
0
i
0
i
0
i
m
m
2
3
m
2
m
1
m
m
x
x
c
...
x
c
x
c
x
c
x
c
i i yi
m
i
3
i
2
i
1
i
0
Получена система линейных относительно
cm уравнений, в
коэффициентов c0,c1,c2,...,
которой при любом n m 1 число уравнений равно
числу неизвестных. Такая система называется
нормальной системой и решается методами
решения СЛАУ, рассмотренными в последующих
разделах.
