|
§ 1. Интерполирование алгебраическими многочленами
1.
Интерполяционная формула Лангранжа.
Пусть на отрезке
ai^Lx^Lb
заданы точки
xh,
£ =
0
,
1
, . . . ,
п
(узлы интерполирования
) ,
в которых известны значения функции
f(x).
Задача
интерполиро
вания алгебраическими многочленами
состоит в том, чтобы
по
строить многочлен
Ьп(х)==а0 + а ^ +
. .. +
апх п
(
1
)
степени
п,
значения которого в заданных точках
xk, k =
0
,
1
, . . . ,
п,
совпадают со значениями функции
f(x)
в этих точках.
Для любой непрерывной функции
f(x)
сформулированная зада
ча имеет единственное решение. Действительно, для отыскания ко
эффициентов а„, «
1
, ■
■
•,
ап
получаем систему линейных уравнений
aQ + a ^ i
+
а2х}
+ . . . +
апх?
= / (*,-),
i
=
0
,
1
, .. .,
п,
(
2
)
определитель которой (определитель Вандермонда [12, с. 33]) от
личен от нуля, если среди точек
хи i =
0
,
1
, . . . ,
п,
нет совпадающих.
Многочлен
Ln{x),
удовлетворяющий условиям
Ln{Xi)=f(Xi),
i= 0 ,
п,
(3)
называется
интерполяционным многочленом
для функции
f(x),
построенным по узлам {*;}?.
127
Решение системы (2) можно записать различным образом. Наи
более употребительна запись интерполяционного многочлена в
форме Лагранжа и в форме Ньютона.
Интерполяционная формула Лагранжа позволяет представить
многочлен
Ln(x)
в виде линейной комбинации
П
и
(*)
= 2
с>
<
м / (**)
(4)
k=Q
значений функции
f(x)
в узлах интерполирования.
Найдем явное выражение для коэффициентов
ск(х).
Из условий
интерполирования (3) получаем
П
2
ck
( X i )
f {Xu)
=
f
( X i ) ,
i =
0, 1, . . .,
n.
£=0
Эти соотношения будут выполнены, если на функции
ск{х)
нало
жить условия
Ck (Xi)
=
0
,
1
.
k,
■
k,
i =
0
,
1
,
п,
которые означают, что каждая из функций
ck{x), k = 0,
1
, . . . ,
п,
имеет не менее
п
нулей на
[а, Ь].
Поскольку
L„(x
) — многочлен
степени
п,
коэффициенты
ск(х)
естественно искать также в виде
многочленов степени
п,
а именно в виде
ск(х) = К к(х—х0) (х—х 1) . . . ( х —хк- 1) (х—хк+1) . . . ( х —хп).
Из условия с„(хь) = 1 находим
—
{Хи
Х(^
(х'и Хк) . . . (Хи ■
Xu—
i) (Xu Xuui) • ■
- (Хи
Хп
).
Таким образом, коэффициенты
ск{х)
интерполяционного много
члена (4) находятся по формулам
П
Ck (х) =
— --------- .
(5)
П
(xk ~ xi)
/
Ф&
Часто коэффициенты
ск(х)
записывают в другом виде. Введем
многочлен oi(x) степени
п+
1
:
со
(х) = (х—х0) (x—x l) . . . ( x —xk- i) (х—хк) (х—хк+1) . . . ( х —хп)
(
6
)
и вычислим его производную в точке
хк:
со'
(хк)
=
(хк—х0) ... {хк—хк^ ) (xh—xh+i) . . . (хк—х п) .
Тогда получим, что
Ck ( х ) =
<о
(х)
(X — хк)
со'
(хк)
128
Итак,
интерполяционный многочлен Лагранжа
имеет вид
Ln (х)
=
2
&=0
(X
—
Xk )
( O '
( x k )
f(Xk)
или, более подробно,
£ « ( * ) =
2
----
--------- /"Ы -
ft=o4
(Xk~~ Х!^
i¥*k
(7)
(
8
)
2. Интерполяционная формула Ньютона.
Эта формула позволя
ет выразить интерполяционный многочлен
Ln(x)
через значение
/(х) в одном из узлов и через разделенные разности функции
f(x),
построенные по узлам
х0,
х„
.
..,
хп.
Она является разностным ана
логом формулы Тейлора
f(x) = f
(х0)
+ ( х - х 0) Г
(Х0)
+
Г
(Х „ ) +
. ..
Сначала приведем необходимые сведения о разделенных раз
ностях. Пусть в узлах
хк^ [ а , b),
6
= 0, 1, . . . ,
п,
известны значения
функции
f(x).
Предположим, что среди точек хй, 6 = 0 , 1, . . . ,
п,
нет
совпадающих.
Разделенными разностями первого порядка
назы
ваются отношения
f(Xi ,
х,) =
f
(*/) —
f
(*,)
Xj
— x;
i,
/ =
0
,
1
, . . .,
n, 1ф'].
Будем рассматривать разделенные разности, составленные по
соседним узлам, т. е. выражения
f ( x 0,
х,), /(х,, х2), . . . , /(х п_ь
х п).
По этим разделенным разностям первого порядка можно по
строить
разделенные разности второго порядка
:
!
(*о>
х и
х2) =
f ( x lt xd — f ( x n, X,)
f
(*i, хг, х3)
=
/ (Xfi—
2
, Xfi-
1
»
хп)
=
Х о
—
Х
0
f
( Х о ,
х3) — f ( x x,
Х п )
Х
3
—
X
j
f {хп_х, хп) — f (*„_2, xn_J
Аналогично определяются разделенные разности более высоко
го порядка. Например, если известны разности
6
-го порядка
f
X j +
1, . . . , Xj+fc) ,
/ (Xj+ i,
то
разделенная разность
(
6
+
1
)-го
порядка
определяется как
/ (X/, Х /+1, . . . , Х /+А, Х /+£+1) =
__ /
f {Xj, х
)+1
......... Х/+&)
xi+k^ — Xj
5 А . А . С а м а р с к и й ,
А . В . Г у л и н
129
При вычислении разделенных разностей принято записывать
их в виде таблицы
Хо
f (Хо)
f
(*0. * l)
X
1
f (Xl)
f (xa, xlt x2)
f
( Xl , X2)
f (x%)
/ (*„,
x u . . .
Xn )
f (xn-
2
’ xn-
1
> xn)
•
f ( xn-V xn)
х п
f(Xn)
Разделенная разность
k-ro
порядка следующим образом выра
жается через значения функции
f(x)
в узлах:
1+к
/ (*,■)
/
(xi
I ■*■/+.ii • • ■
I
xi+k)
=
2
7
^
•
(
0
)
l~'
П
(Xi — xfr
1ф i
L=j
Эту формулу можно доказать методом индукции. Нам потребуется
частный случай формулы (9):
/(*„.*!.
*n) = ^
----- =
П (JC£ — JCf)
/
=0
,
I
f (Xi)
(Xi
— *o) (* i
— Xi )
(X;
— x {_ j )
( XC
—
* l 4 l ) • ■ •
( x c —
X n )
•
(
10
)
Интерполяционным многочленом Ньютона
называется много
член
Рп
(
X
) =
= / (*о) + (*
— хо)
/ (*0.
xi)
+
{X — X
q
)
{X
—
*i)
f
(XQ,
xu
x2) + . . .
. . . +
(X
— x0)
(x
—
Xj)
. . .
(x —
x„_!) / (*0, Xi, .. .,
xn).
(II)
Покажем, что многочлен
Рп(х)
совпадает с многочленом Л а
гранжа (
8
). Рассмотрим наряду с
Ln(x)
многочлены
L„(x) =} (ха) ,
130
(12)
L,(x),
L„_,(x) и представим
L„{x)
в виде
Ln (х) = L0 (х)
+ ^
iL!
(*) —
Ц -
1
(*))•
/'=i
Из условий интерполяции (3) получаем, что
L,-l {xh) = Li {xk) = f { x k)
при й = 0 , 1,
/—1 и /== 1, 2, . . . ,
п.
Следовательно, разность
Lj{
х )
—С,_,(х) представляет собой алгебраический многочлен сте
пени /, который обращается в нуль в точках
х0, х„ . . . ,
х ^ „
т. е.
Ц
(х) — L,_, (х) = Л; (х—х0) (х—Xi)... (х—х,-4) ,
(13)
где
Aj
— числовой коэффициент. Этот коэффициент находится из
условия
Lj
(* j) —
Lj-i (xj) = A j (xj—x„) (Xj
x , ) . . . (xj Xj—,) ,
откуда, учитывая условие
Lj(xj) = f ( x s),
получаем
/
( Xj ) — L h l (Xj )
(xj ~ x 0)...(xl —xf_1)m
'
(14)
Подставим в (14) вместо слагаемого
Lj-iixj)
его значение, вы
численное согласно (
8
), т. е.
L
/ - 1
(x i)
=
= ' у f
(х*)
{Х'
~
Хо) {xi ~ Xl) ■■■ (xi ~ Xk~J (Xi
~
Xk" ] • ■
•
(xi
~ */-i>
— xo) (*k — x i)
■
■
• ( * * -
x k - 0 (x k — x k+i) ■■■( 4 — x i -
1
)
Тогда получим
f
(*/)
A , =
(xj
—
xa) ■■■(xj — xj-l)
_ %
ПЧ)
h i*i-
Xk)
(xk — xo) ■ ■
■
(xk — Xk-X) (xk — xk+l) ■■■(xk — Xi -
1
)
____________________ w
___________________ _
(X* — Xo) . . . (XA -
x ft_ j ) (x* - x fe K ) . . . ( r /; -
—
X j )
i
Сопоставляя это выражение с (10), видим, что Л,- совпадает с раз
деленной разностью /-го порядка:
A j = f
(х0, хь . . . , Xj).
Отсюда и из (12), (13) приходим к интерполяционной формуле
Ньютона
Ln (х) —
= / (*о) + (*
— Х
0
) / (^о.
xl)
+ (X — х0) (х — Xj) / (х0, ХЬ ха) + . . .
. . . 4- (х — х0) (х — Xi) . . . (х — х„_,) / (х0, х1т . . . . х„). (15)
5*
131
Подчеркнем еще раз, что формулы (
8
) и (15) представляют со
бой различную запись одного и того же многочлена
йц + й[Л'-(-Й2Л'“ + . . . + Й„Л'',)
’ V
удовлетворяющего условиям интерполяции (
2
).
Интерполяционную формулу Ньютона удобнее применять в том
случае, когда интерполируется одна и та же функция
f(x),
но чис
ло узлов интерполяции постепенно увеличивается. Если узлы ин
терполяции фиксированы и интерполируется не одна, а несколько
функций, то удобнее пользоваться формулой Лагранжа.
З а м е ч а н и е . При выводе формулы (15) не предполагалось, что узлы
Ха, Xi, . . . , х п расположены в каком-то определенном порядке. Поэтому роль точ
Do'stlaringiz bilan baham: |
