МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ
БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ
УНИВЕРСИТЕТ»
ИНТЕРПОЛЯЦИЯ АЛГЕБРАИЧЕСКИМИ
МНОГОЧЛЕНАМИ.
СПЛАЙН-ИНТЕРПОЛЯЦИЯ
Учебно-методическое пособие
для лекционных занятий в вузах
Составители:
В.П. Трофимов,
А.П. Карпова,
М.Н. Небольсина
Издательско-полиграфический центр
Воронежского государственного университета
2012
1
Стр.1
ТЕОРИЯ ПРИБЛИЖЕНИЯ ФУНКЦИЙ
ОДНОЙ ВЕЩЕСТВЕННОЙ ПЕРЕМЕННОЙ
1. Интерполяция алгебраическими многочленами
1. 1. Постановка задачи интерполяции
точках x X i
i
,
x
f ( )x
Пусть для функции f X R→:
, n .
0,
x 0
f x( 0
)
, X ⊂ известны ее значения в (n + 1)-й
R
∈ = … Запишем эти значения функции f в табл. 1.1
Таблица 1.1
x n
x 1
f x( 1
<
)
…
…
Далее будем считать, что выполнено условие
a ≤ x 0 < x1 < x n ≤ b .
функции f ( )x при x x ii
n ( ;
i
0 ,
Задача приближенного вычисления для заданной табл. 1.1 значения
≠ , …= 0,
принимающий в точках x x ,
(
0 , 1
0 , 1
P x x x ,1 … , x n ;
, x n
i
f x ) = P x ;
n (
, x n
f ),
f ) = P x f ),
n ( ;
те же значения, что и функция :f
.
i = … n
0 , 1,
,
, n называется задачей интерполяции
(распространения внутрь).
Решение этой задачи можно найти следующим образом: строится алгебраический
многочлен степени не выше n
(1.1)
(1.2)
называется многочлен (1.1) степени не выше ,n удовлетворяющий условию
(1.2). Точки
Вычисление значения f ( )x при x ≠ x ,
f x( ) ≈ P x f )
i
n ( ;
i = … n по формуле
(1.3)
0 ,
Замечание 1.1. Если x ∉ ; [a b ], то вычисление
,
называется интерполяцией функции f с помощью алгебраического многочлена.
f
( )x с помощью
(1.3) называют экстраполяцией.
Замечание 1.2. Существуют различные формы записи интерполяционного
многочлена.
Теорема 1.1. Для табл. 1.1 интерполяционный многочлен существует
и единственен.
Доказательство. Запишем интерполяционный многочлен в виде
.
P x x x ,1 … , x f ) = a 0 + a x + + a x
n ( ;
0 ,
n ;
3
1
n
n
Интерполяционным многочленом (интерполянтой) для табл. 1.1
x x , называются узлами интерполяции.
f x( n
)
Стр.3
2) многочлен
равен 1 при x = и равен нулю во всех остальных узлах.
Итак, для любого k = 0,… n
0 )( −
(x x x x )1 …(x xk−1 )(x xk+1)…(x x )
(xk − x x − x )1 …(x − xk−1 )(x − xk+1 )… k
x k
−
0 )(
0 )( −
k
−
k
,
l n ) ( ) =
(
k
x
интерполяции:
Введем многочлен
( ) (
k
(x x x x )1 …(x xk−1)(x xk+1)…(x xn )
(xk − x xk − x )1 …(xk − xk−1)(xk − xk+1)… k
( )x
−
0 )(
ω x = −x x x x )
Теперь многочлен l n ) ( ) можно записать в виде
(
ω = −kx x x x )1 …(x x
x
0 )( k
k
k
x
−
l n ) ( ) =
(
нимает в узле kx значение
n ( ; )
(x)
По построению многочлен f x k ) l k
( k
(x xk )
(
−
)
интерполяции.
Следовательно, многочлен
L x f =∑f x l x =∑f x( )
n
n
k
k=0
L x f = f x( ) , i = 0 ,… ).
n ( ; )
i
i
, n
( ) ⋅ k
( )
n
( )
k=0
k
(x xk )
− ω′
ω
(x)
( )xk
полином L ( ; )fxn
(1.6)
является интерполяционным многочленом для табл. 1.1 (имеет степень не
выше n и
Формулу (1.6) называют интерполяционной формулой Лагранжа, а
– интерполяционным многочленом Лагранжа.
Замечание 1.4. Число арифметических операций, необходимых для
вычисления по формуле (1.6), имеет порядок O n( 2
).
Пример. Найдем интерполяционный многочлен Лагранжа для n = 1 .
В этом случае формула (1.6) примет вид
L x f = ( )
1( ; )
ки ())(;0x f x
0
0
x x
f x x x
0 − + ( )
1
− 1
1
Графиком функции L1( ; )fx
и ( 1; ( ))1
x x
f x x x
1
− =
−
0
0
f x x x− − f x x x0 ) .
( )(
0
1)
x x1
0 −
является прямая, проходящая через точx
f x . Такая полиномиальная интерполяция называется
линейной полиномиальной (не путать с линейным интерполированием
(см. важное замечание 1.1)).
6
( )( −
1
′ x( )
n
k
( )
( ) имеет степень ,n приx
f
x и равен нулю во всех остальных узлах
.
(1.5)
−
−
−
−
−
(x − xn )
Заметим, что производная многочлена
′ x( ) (
( )x в точке k
x
k − k−1)(x x
k − k+1)… k(x xn ) .
−
.
(n + 1)-й степени, построенный по узлам
0 )( − 1 …(x xn−1)(x xn ) .
−
k
− n
(x − x )
n
ω
ω
ω ω
Стр.6
Задание. Найдите интерполяционные многочлены Лагранжа для n = 2, 3 .
Замечание 1.5. Поскольку интерполяционный многочлен (1.6) линейно
зависит от значений функции f x , то интерполяционный многочлен для
( )i
суммы функций равен сумме интерполяционных многочленов слагаемых.
1.3. Погрешность интерполяции
r x f ) = f x( ) − P x f
Погрешностью интерполяции называется разность
).
n ( ;
r x ;
n (
i
(
n ( ;
Очевидно, что в узлах интерполяции x x , , x n
f ) = f x i ) − P x ;
n (
0 , 1
i
f ) 0 .
=
В остальных точках погрешность интерполяции, вообще говоря, отлична
от нуля.
Замечание 1.6. Из предложения 1.1 следует, что погрешность интерполяции
r x f ≡) 0
(
( f ∈ Ρ n( 1)+
i ;
для любой функции f ∈ Ρ , где Ρ
( n )
, deg f = +n ).
1
В этом случае
где c = const .
( 1)
rn
n ( ; )
rn x f
(x)
n + 1 и узлы интерполяции x k
Следовательно,
c
( ; )
x f = f
( 1)
n+
( ; ) = f x P x f
, n
,
(
0,
r x f = ⋅ω = ⋅ − 0 )( −
так как P ( ; )fxn
Отсюда найдем c f n+
– многочлен степени ,n то
x
( 1) ( )
= +
(n 1 )!
ность интерполяции имеет вид
n ( ;
погрешности интерполяции можно получить формулу, аналогичную (1.8).
Теорема 1.2. Если
f C n( 1)+
∈
;
грешность интерполяции определяется формулой
7
ций, n + 1 раз непрерывно дифференцируемых на отрезке []), то для
[a b], то для любого x ∈ ;[a b ] поконкретного
сказать о погрешности интерполяции нельзя.
Если функция
f C n( 1)+
∈
;
;
Однако для произвольной функции, заданной только табл. 1.1, ничего
[a b] (C n( + 1 )
[a b ] – пространство функa
b;
r x f ) = ⋅c ω x( ) =
f
( )x P x f = f
n
− n
( 1)
n+
( ; )
Продифференцировав по x это равенство
n+
( ) − n ( ; ) есть многочлен степени
k = … являются его корнями.
c x x x x )1 …(x xn−1)(x xn ) , (1.8)
−
( 1)
n+
( )x c n
P x f
n
( 1) ( ; ) 0 .≡
+
. Таким образом, для f ∈Ρ n( 1 )+
( n + 1)
( )
x
(n + 1)!
ω x( ).
погреш(1.9)
−
n
+ 1 раз, получим
( 1 )!
= ⋅ +
,
( n )
странство многочленов степени не выше n .
Найдем погрешность интерполяции для многочлена степени
– проn
+ 1
(1.7)
Стр.7
r x f ) =
n ( ;
где
де (1.8), положив с с( ),x=
r x f ) = c x ω x( ).
смотрим вспомогательную функцию
n ( ;
отрезка []:
a b;
Очевидно, что ϕ ∈ C n( +1)
,
0 ,
a b;
Зафиксируем произвольное x ∈ ; [a b ], x ≠ x i = … n и расот
переменной :z
( )
n ( ;
i ,
ϕ z( ) = r z f ) − c x ω z( ) =
= f z( ) − P z f ) − c x ω z( ).
n ( ;
;
( )
[a b ] и обращается в нуль в n + 2 точках
z = x x x ,1 , x n . По теореме Ролля функция
′ (производная от функцииϕ по z ) обращается в нуль по крайней мере в
n + 1 точках отрезка []
, при этом ϕ ∈′
Таким образом,
(
n
( 1) ( )z
n+
крайней мере в одной точке
P n + 1 ) ( ;x f
получаем
ϕ
( n + 1 )
( )ξ = f n + 1 )
(
Следовательно,
и
r x f ) =
n ( ;
где
= ( ) ∈ [a b].
x
;
интерполяции зависит от выбора узлов интерполяции
гладкости функции .f
8
Теорема доказана.
Важное замечание 1.2. Из формулы (1.10) следует, что погрешность
x x , и
0 , 1
, x n
f
( )ξ − c x( ) ( n + 1)! 0 .
( n + 1 )
⋅
c x( ) =
f
( )
ξ
( n + 1 )!
( n + 1 )
( )
ξ
( n + 1)!
ω x( ),
=
∈ [a b ];
(
Учитывая, что для любого x
) 0
≡
C a b ]
n
( )
[ ;
нулю по крайней мере в n точках этого отрезка, ϕ ∈′′
далее.
n C a b );
( 1)
+ ∈ [
x
]
и ξ = ξ( ).x
и ω + 1 ) ( ) ≡ ( n + 1)! ,
( n
, функция
C n( −1 )
[];a b
′′ равна
и так
обращается в нуль по
0,
,
( ) ⋅
f
( n + 1 )
( )
ξ
( n + 1)!
– некоторая точка отрезка [a b ];
( ξ = ξ( )∈ [a b]).
ω x( ),
x
;
Доказательство. Будем разыскивать погрешность интерполяции в ви(1.10)
ϕ
ϕ
ξ
ϕ
ϕ
ϕ
ξ
ξ
ξ
Стр.8