Новые многофункциональные материалы и нанотехнологии

14
§ 2.2. Интерполяционный полином Лагранжа
Алгебраические полиномы с действительными коэффициентами являются хорошо изученными функциями и весьма простыми для вычислений. Их удобно складывать и перемножать, дифференцировать и интегрировать. Алгебраический полином степени n можно записать в стандартной форме (1.4), хотя допустимы и другие представления. Из-за простоты работы с алгебраическими полиномами их часто используют в качестве интерполянтов.
Пусть исходной информацией являются (n + 1) пар чисел x
i
, y
i
(i = 0,
1,
...,
n
), сведенных в таблицу вида 2.1. Будем строить интерполирующую функцию в виде алгебраического полинома.
Из теории функций известно, что через n + 1 произвольных точек на плоскости, заданных координатами x
i
, y
i
(i = 0, 1, ... , n), всегда можно провести график алгебраического полинома с действительными коэффициентами, если числа x
i

(i = 0, 1, ... , n) различны. Если степень полинома m = n, то, вообще говоря, такой полином является единственным. Согласно требованию (2.1), в узлах интерполяции x
i

(i =
0, 1, ... , n) значения этого полинома P
m
(x) точно совпадают с данными значениями y
i
(i= 0, 1, ... , n) интерполируемой функции f(x):
P
m
(x
i
) = y
i
(i = 0, 1, ... , n).
(2.2)
Таким образом, всегда можно найти полином P
m
(x) степени m = n, который может служить интерполирующей функцией.
В специальных случаях, когда точки x
i
, y
i
(i = 0, 1, ..., n) расположены особым образом, степень полинома может быть меньше n.
Например, если данные точки расположены точно на одной прямой, то через них пройдет график линейной функции (полинома первой степени) независимо от количества данных точек.
При m > n полиномов, графики которых проходят через заданные точки, бесконечно много.
Рассмотрим ситуацию, когда расстояния между узлами неодинаковы.
В таком случае целесообразно построить интерполяционный полином Лагранжа
. Этот полином строится в виде суммы:

15
L
n
(x) =
i
n
i
i
y
x
⋅
∑
=
)
(
0
l
,
(2.3) где
i
l
(x)
− функции аргумента x, называемые коэффициентами
Лагранжа
(i = 0, 1, ..., n).
По свойству интерполирующего полинома (2.1) должно выполняться условие:
L
n
(x
i
) = y
i
(i = 0, 1, ..., n).
(2.4)
Для выполнения (2.4) на коэффициенты Лагранжа налагается следующее требование:
i
l
(x
j
) =
δ
i j
(i, j = 0, 1, ..., n),

(2.5)

где
δ
i j
– символ Кронекера (
δ
i j
= 0 при i
≠ j и δ
i j
= 1 при i = j ).
Чтобы обеспечить выполнение равенств (2.5), коэффициенты
Лагранжа
i
l (x)
представим в виде произведений:
i
l
(x) = с
i

(x
− x
o
) (x
− x
1
)... (x
− x
i-
1
) (x
− x
i+
1
)... (x
− x
n
),
(2.6) где с
i

− некоторые постоянные величины, пока неизвестные.
В выражении для i-го коэффициента Лагранжа отсутствует множитель (x
− x
i
), поэтому каждое i-е произведение (2.6) содержит n скобок, и каждый коэффициент Лагранжа представляет собой полином степени n.
Для определения явного вида постоянных величин с
i
можно воспользоваться равенством
i
l
(x
i
) = 1 (i = 0, 1, ..., n), согласно требованию (2.5). Тогда из (2.6) сразу следует, что 1 / с
i
=
∏
≠
=
−
n
i
j
j
j
i
x
x
,
0
)
(
Таким образом, коэффициенты
Лагранжа представляются произведениями отношений разностей:
i
l
(x) =
∏
≠
=
−
−
n
i
j
j
j
i
j
x
x
x
x
,
0
)
(
)
(

(2.7)

16
Легко убедиться непосредственной подстановкой, что для каждого коэффициента (2.7) выполняется условие (2.5).
Интерполяционный полином в форме Лагранжа получается подстановкой найденных коэффициентов (2.7) в выражение (2.3):
L
n
(x) =
∑
∏
=
≠
=








−
−
⋅
n
i
n
i
j
j
j
i
j
i
x
x
x
x
y
0
,
0
)
(
)
(

(2.8)
Для большей наглядности запишем полином Лагранжа 3-й степени в развернутом виде:
L
3
(x) =
y
0
)
)(
)(
(
)
)(
)(
(
3 0
2 0
1 0
3 2
1
x
х
x
х
x
х
x
х
x
х
x
х
−
−
−
−
−
−
+
y
1
)
)(
)(
(
)
)(
)(
(
3 1
2 1
0 1
3 2
0
x
х
x
х
x
х
x
х
x
х
x
х
−
−
−
−
−
−
+
+
y
2
)
)(
)(
(
)
)(
)(
(
3 2
1 2
0 2
3 1
0
x
х
x
х
x
х
x
х
x
х
x
х
−
−
−
−
−
−
+
y
3
)
)(
)(
(
)
)(
)(
(
2 3
1 3
0 3
2 1
0
x
х
x
х
x
х
x
х
x
х
x
х
−
−
−
−
−
−

Использование полинома
Лагранжа для интерполяции иллюстрируется следующим примером.
Пример 1. Пусть значения функции заданы таблицей 2.2. Требуется построить по ним полином Лагранжа.
Таблица 2.2

Так как таблица 2.2 содержит 5 узлов, интерполяционный полином
Лагранжа должен иметь 4-ю степень. Подставляя эти числовые значения таблицы в общую формулу (2.8), находим явный вид полинома Лагранжа для данной задачи:

L
4
(x) =
−4
)
5 2
)(
5
,
3 2
)(
2
,
1 2
)(
1 2
(
)
5
)(
5
,
3
)(
2
,
1
)(
1
(
−
−
−
−
−
−
+
−
−
−
−
+
х х
х х
+
i
0 1
2 3
4
x
i

−2
−1 1,2 3,5 5
y
i

−4 0
3,8
−2 7

17
+ 3,8
)
5 2
,
1
)(
5
,
3 2
,
1
)(
1 2
,
1
)(
2 2
,
1
(
)
5
)(
5
,
3
)(
1
)(
2
(
−
−
+
+
−
−
+
+
х х
х х
−
−2
)
5 5
,
3
)(
2
,
1 5
,
3
)(
1 5
,
3
)(
2 5
,
3
(
)
5
)(
2
,
1
)(
1
)(
2
(
−
−
+
+
−
−
+
+
x
x
x
x
+
+ 7
)
5
,
3 5
)(
2
,
1 5
)(
1 5
)(
2 5
(
)
5
,
3
)(
2
,
1
)(
1
)(
2
(
−
−
+
+
−
−
+
+
x
x
x
x

Сумма содержит только 4 слагаемых, так как коэффициент Лагранжа
1
l
(x) умножается на нулевое значение y
1
= 0. Приведение полинома к стандартному виду даст следующее выражение:
L
4
(x) = 0,0819538 x
4
− 0,181866 x
3
− 1,43424 x
2
+ 2,19964 x + 3,37007.
График построенного полинома приведен на рис. 2.2.















-2 0
2 4
6
-4
-2 0
2 4
6 8

y
x
Рис. 2.2. Интерполяционный полином Лагранжа, проведенный через 5 заданных точек таблицы 2.2.
Как было указано в начале данного параграфа, полином Лагранжа строится для произвольного набора узлов. Но вычисление значения полинома Лагранжа для заданного аргумента x по формуле (2.8) требует большого количества вычислений. Можно подсчитать, что при этом

18 необходимо выполнить 2n (n + 1) + n сложений и вычитаний, а также 2n
(n + 1) умножений и делений.
В подробных курсах численных методов доказывается, что полином
Лагранжа (2.8) обладает свойством единственности [1].
Полиномы, интерполирующие таблицы данных с постоянным шагом, позволяют проводить более быстрые вычисления, сравнительно с использованием универсального полинома Лагранжа.

§ 2.3. Интерполяция по равноотстоящим узлам
Рассмотрим случай, когда известны значения интерполируемой функции f(x) в равноотстоящих узлах. При этом узлы интерполяции x
i

выражаются формулой:
x
i
= x
0
+ i
⋅
h
, где i = 0, 1, ..., n .
(2.9)
Постоянный параметр h называется шагом интерполяции.
В такой задаче исходными данными являются (n + 3) чисел: начальный узел интерполяции x
0
, шаг интерполяции h и (n + 1) значений неизвестной функции y
i
(i = 0, 1, ..., n) в узлах интерполяции.
Будем строить полином P
n
(x) степени n, обладающий свойством (2.2)
P
n
(x
i
) = y
i
(i = 0, 1, ..., n),
(2.10) где значения x
i
заданы формулой (2.9).
Полиномы для интерполяции по равноотстоящим узлам впервые были построены Ньютоном, который был как гениальным физиком, так и гениальным математиком.
Первый полином Ньютона строится в форме:
P
n
(x) = a
0
+
∑
∏
=
−
=








−
⋅
n
i
i
j
j
i
x
x
a
1 1
0
)
(

(2.11) или в развернутом виде:
P
n
(x) = a
0
+ a
1
(x
−
x
0
) + a
2
(x
−
x
0
) (x
−
x
1
) + a
3
(x
−
x
0
) (x
−
x
1
) (x
−
x
2
) +...
+ a
n
(x
−
x
0
)...(x
−
x
n-
1
).

19
Коэффициенты полинома a
i
необходимо выразить через известные величины x
0
, h, n,
y
i
(i = 0, 1, . . . n), пользуясь требованием (2.10), т.е. прохождением графика полинома через все точки заданной системы.
Сразу заметим, что подстановка x = x
0
в выражение (2.11) дает
P
n
(x
0
)=a
0
. Следовательно, согласно (2.10), мы получаем значение свободного члена искомого полинома:
a
0
= y
0

(2.12)
Остальные коэффициенты полинома Ньютона выразим через конечные разности, описанные в предыдущей главе. Можно доказать эквивалентность условия (2.10) тому, что
∆
k
P
n
(x
0
) =
∆
k
y
0
(k = 0, 1, ... , n).
(2.13)
Доказательство основано на том, что согласно (1.15), n-я конечная разность любой функции f(x) выражается через n последовательных значений этой функции в равноотстоящих точках, отличающихся на шаг h.
Будем строить последовательно конечные разности
∆
i
P
n
(x), где (i =
0, 1, ... , n), для произвольной точки интерполяции x и заданного шага h.
Для нахождения первого коэффициента a
1
составим первую конечную разность полинома (2.11):

∆
1
P
n
(x) = P
n
(x+ h)
−
P
n
(x).

(2.14)
Пользуясь свойством линейности конечных разностей, будем их вычислять для отдельных слагаемых суммы (2.11) и выносить за скобки общие множители a
i

(i = 0, 1, ... , n):
i =
0
a
0

− a
0
=
0
i =
1
a
1
[(x + h
− x
0
)
− (x − x
0
)] = a
1
h
i =
2
a
2
[(x+ h
− x
0
) (x + h
− x
1
)
− (x − x
0
) (x
− x
1
)] =
= a
2
[(x + h
− x
0
) (x
− x
0
)
− (x − x
0
) (x
− x
0

− h)] = a
2 2h(x
− x
0
).
В последнем преобразовании использовалось, что x
1
= x
0
+ h.
Дальнейшими вычислениями можно показать, что среди сомножителей остальных коэффициентов a
i
(i > 2) обязательно

20 присутствуют множители (x
− x
0
). В результате получим следующее для первой конечной разности исходного полинома:
∆
1
P
n
(x) = a
1
h + 2a
2
(x
− x
0
) h + 3 a
3
(x
− x
0
) (x
− x
1
) h +...
+ n a
n
(x
− x
0
)...(x
− x
n
−
2
) h.

(2.15)

Теперь если в (2.15) положить x = x
0
, получим:
∆
1
P
n
(x
0
) = a
1
h. С другой стороны, из (2.13) и (2.10) следует:
∆
1
P
n
(x
0
) = y
1

−
y
0
. Сравнивая два выражения для
∆
1
P
n
(x
0
), получаем представление первого коэффициента искомого полинома через известные величины:
a
1
= (y
1

− y
0
) / h.

(2.16)
Для вычисления коэффициента a
2
рассматривается вторая конечная разность полинома (2.11):
∆
2
P
n
(x) =
∆
1
P
n
(x + h)
−

∆
1
P
n
(x).
Ясно, что она не будет содержать слагаемого с коэффициентом a
1
, т.к. этот коэффициент является множителем константы в сумме
∆
1
P
n
(x), согласно (2.15). Если провести преобразования, аналогичные проделанным для первой конечной разности исходного полинома, то мы получим, что свободным членом нового полинома
∆
2
P
n
(x) будет 2a
2
h
2
, а остальные члены будут содержать сомножители (x
−
x
0
). Тогда ясно, что в точке x = x
0
получим:
∆
2
P
n
(x
0
) = 2a
2
h
2

С другой стороны, по формуле (1.3) для произвольной функции имеем:
∆
2
P
n
(x
0
) = P
n
(x
2
)
−

2P
n
(x
1
) + P
n
(x
0
), а по условию (2.10):
∆
2
P
n
(x
0
) = y
2

−

2 y
1

−
y
0

Сравнение дает выражение для второго коэффициента искомого полинома:
a
2
= (y
2

−

2 y
1

−
y
0
) / (2h
2
).
(2.17)

21
Для получения остальных коэффициентов искомого полинома (2.11) необходимо повторять аналогичную процедуру с высшими конечными разностями. В результате мы получим следующее общее выражение для коэффициентов интерполянта Ньютона:

a
i
=
i
i
h
i
y
!
)
(
0
∆

(2.18)
Следовательно, интерполяционный полином Ньютона выразится через конечные разности порядков 1, ... , n, вычисленные в нулевом узле
x
0
:

P
n
(x) = y
0
+
∑
∏
=
−
=








−
∆
n
i
i
k
k
i
i
x
x
h
i
y
0 1
0 0
)
(
!
)
(

(2.19)
То, что построенный полином удовлетворяет условию (2.10), проверяется непосредственной подстановкой. Положим x = x
j
, где x
j
– произвольный узел, и подставим в (2.19). При этом учтем, что все разности (x
j
−
x
k
) кратны целому числу шагов h при k
≠ j и равны нулю при k = j. Следовательно, все слагаемые суммы (2.19) с индексами i > j содержат множитель, равный нулю. В результате получим:
P
n
(x
j
) = y
0
+ j
∆y
0
+
2
)
1
(
−
⋅ j
j

∆
2
y
0
+ … +
!
1
)
1
(
j
j
j
⋅
⋅
−
⋅

∆
j
y
0.
Использование (1.14) и (2.13) позволяет представить правую часть последнего уравнения в виде
P
n
(x
0
+ jh
) = P
n
(x
j
) = y
j
, что и требовалось доказать.
Для практических расчетов полином Ньютона (2.19) удобнее представлять, вводя новую переменную:
q =
(x
−
x
0
) / h.

(2.20)
Тогда интерполяционный полином Ньютона представится так:

22
P
n
(x) = y
0
+ q
⋅∆
1
y
0
+
!
2
)
1
(
−
q
q
⋅
∆
2
y
0
+
!
3
)
2
)(
1
(
−
− q
q
q
⋅
∆
3
y
0
+...

+
!
)
1
)...(
1
(
n
n
q
q
q
+
−
−
⋅
∆
n
y
0


(2.21)
Анализ формулы (2.21) показывает, что погрешность построенного интерполянта Ньютона принимает наименьшие значения для аргументов, близких к нулевому узлу x
0
(см. § 2.5). Пример, приведенный в предыдущем параграфе для полинома Лагранжа, показывает, что не всегда целесообразно строить полином по всем узлам, так при этом могут возникать необоснованные «выбросы». В практических расчетах часто заранее выбирается степень интерполирующего полинома. Затем в качестве нулевого x
0
берется узел, ближайший слева к значению аргумента x, для которого требуется вычислить значение неизвестной функции f (x). Интерполянт n-й степени (2.21) строится с помощью значений функции y
i
в узле x
0
и в n узлах, расположенных правее аргумента x. Значения функции в узлах левее x
0
не используются.
Пример 2. Исходные данные сведены в таблицу 2.3 с постоянным шагом h = 0,1.
Таблица 2.3
x
i
3,0 3,1 3,2 3,3 3,4 3,5 3,6
y
i
0,550 0,450 0,365 0,293 0,234 0,185 0,146
Пусть требуется вычислить значение функции f(x) для аргумента
x
=3,22. Узлы в таблице 2.3 являются равноотстоящими (шаг h = 0,1), поэтому целесообразно построить интерполянт Ньютона.
Ограничимся полиномом 3-го порядка. За нулевой узел, как было рекомендовано ранее, возьмем ближайший слева к значению x = 3,22 , т.е. узел x
0
= 3,2. Полином будем строить по четырем узлам x
i
≥ 3,2.
Составим таблицу конечных разностей
∆
k
y
i
(k =1, 2, 3), необходимых для построения полинома (2.21) при n = 3. Таблицу построим по типу примера 2 предыдущей главы (см. табл. 1.1). Напомним, что разности порядка выше первого вычисляются как разности разностей предыдущего порядка, стоящие в соседнем левом столбце таблицы 2.4.

23
Таблица 2.4

i
x
i
y
i

∆y
i
∆
2
y
i
∆
3
y
i
0 3,2 0,365
− 0,072 0,013
− 0,003 1
3,3 0,293
− 0,059 0,01 2
3,4 0,234
− 0,049

3 3,5 0,185


Для значений x = 3,22 и x
0
= 3,2 вычислим параметр q = (3,22–3,2)/0,1 =
0,2 и подставим все требуемые числа в формулу (2.21):
f
(3,22) = P
3
(x = 3,22) = 0,365 + 0,2 (
−0,072) +
2
)
1 2
,
0
(
2
,
0
−
0,013 +
+
!
3
)
2 2
,
0
)(
1 2
,
0
(
2
,
0
−
−
(
−0,003) ≈ 0,349.
Исходные значения функции в узлах интерполирования были заданы с тремя значащими цифрами (см. табл.2.3), поэтому, согласно правилам, результат округляем до трех значащих цифр.
Приведем формулы для двух важных частных случаев интерполяции.
1. Линейная интерполяция. Интерполяционный полином (2.21) строится по двум узлам и является линейной функцией:
P
1
(x) = y
0
+ q
⋅∆
1
y
0
или P
1
(x) = y
0
+
h
x
x
0
−
(y
1
− y
0
). (2.22)

Последнюю формулу легко получить с помощью рисунка 2.1, соединив точки (x
0
, y
0
) и (x
1
, y
1
) отрезком прямой линии. Соединяя отрезками прямых точки (x
i
, y
i
) и (x
i+
1
, y
i+
1
) для соседних узлов, можно получить график кусочно-линейной интерполяции.
Практика показывает, что для большинства физических задач такой вид интерполяции неприменим, так как дает большую погрешность.
2. Квадратичная интерполяция. Для построения интерполяционного полинома (2.21) выбираются три узла. Полином становится квадратичной функций следующего вида:

24
P
2
(x) = y
0
+ q
⋅
∆
1
y
0
+
2
)
1
(
−
q
q
⋅
∆
2
y
0
или
P
2
(x) = y
0
+ q
⋅
(y
1
− y
0
) +
2
)
1
(
−
q
q
⋅

(y
2
− 2 y
1
+ y
0
).
(2.23)
Выше было показано, что интерполянт (2.21) строится с использованием n значений функции в узлах данной таблицы, которые расположены правее аргумента x, для которого проводится интерполяция. Если же аргумент x находится ближе к концу таблицы, например, лежит в интервале (x
n
−
1
, x
n
), то построить полином вида (2.21) невозможно (за исключением линейного). В подобных случаях следует вместо полинома (2.21) использовать второй

Скачать 0.96 Mb.

Поделитесь с Вашими друзьями: