Метод Ньютона: 1- и 2-я интерполяционные формулы Ньютона.

Оценка погрешности
интерполяционных формул

При заданном наборе узлов интерполяции
существует один и только один
интерполяционный многочлен. Формулы Лагранжа,
Ньютона, Гаусса и другие порождают один и тот
же многочлен (при условии, что вычисления
производятся точно). Разница между ними лишь в
алгоритме построения, а многочлен Лагранжа не
содержит явных выражений для коэффициентов.

Исходя из принципа построения
интерполяционного полинома, следует, что в
точках узлов значения полинома и табличной
функции полностью совпадают. В других же точках
существует разница между полиномом и функцией,
которая определяется остаточным членом


R
xf
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
n1
fxL
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 . Продолжая
эти рассмотрения для производных более
высоких порядков, можно сделать вывод,
n1
x 
что производная u
имеет хотя
n1
бы один нуль на отрезке a ,b , т.е. u 0
.
n
1

n1



x

n

1
!
Так как Ln x0и 
, то из
n

1

n

1


n

1

(*-*) имеем
u x

f x

k
n

1
!

1

и при x   получаем 0

n


fn

k

1
!
 
 

  

f

, откуда следует k  n1!
n1
(*---*)
Сравнивая правые части (*--*) и (*---*)
получаем соотношение
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
 n1
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
!
Выбор способа интерполяции –
локального или глобального - определяется
особенностями решаемой задачи
(точностью, быстродействием и др.).
 Повышение степени интерполяционного
полинома (при локальной интерполяции) не
всегда повышает точность интерполяции,
т.к. не всегда ясно поведение производной
n1
f
x при увеличении n


Интерполяция табличной функции
с неравноотстоящими узлами

Единственность полинома Лагранжа.
Пусть существует другой полином Qn  x 
степени не выше n , который решает задачу
интерполяции Qnxi  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,xi1
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

На каждом отрезке xi1 xxi имеется четыре
неизвестных коэффициента
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

(*)
ci1 ci 3
h
id
i
i1
,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
ci1 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 2h1 h2 *c2 h2 *c3 3
 h  h 

1
 2

 y3  y2 y2  y1 
h2 *c2 2h2 h3*c3 h3 *c4 3
 h  h 

c
3
2


..........
..........
..........
..........
.........
i
 yn  yn1 yn1  yn2 

hn1*cn1 2hn1 hn *cn hn *cn1 3

 h

h
n
n1


yn  yn1
1
2
hn *cn  hn *cn1 k2 
3
3
hn
1
3
5
0
2
4
y
y


1
0

k
1


h
1


y
y0
y2y
 
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 y2y
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

h3h4 h4
0
h
2
0 c
y
y
y2
3
4  y
4
3
3



3
*






0
h
h4h5 h5  c5   h4
0
0
h
2
3

4




1
2
y
y4 y4y


5
3
6
c
 3
0
0
0
0
h
h



5
5
*

  h

3
3 

h
5
4



 k ynyn1

2


h
n


аппроксимация
Аппроксимация табличной функции
y
f(xi)
Невязка
yi
i f(xi )yi
mini2
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
2c0 c1xi c2xi2 c3xi3 ...cmximyi 0
co
i0


n
S
2c0 c1xi c2xi2 c3xi3 ...cmximyi xi 0
c1
i0


n
S
2c0 c1xi c2xi2 c3xi3 ...cmximyi xi2 0
c2
i0


..........
..........
..........
..........
..........
..........
..........
...
n
S
2
3
m
m
2c0 c1xi c2xi c3xi ...cmxi yi xi 0
cm
i0



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
n1c0c1
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 число уравнений равно
числу неизвестных. Такая система называется
нормальной системой и решается методами
решения СЛАУ, рассмотренными в последующих
разделах.