num-meth
.pdf
2.4. Конечные разности. Конечно-разностные методы интерполяции. Интерполяция по формулам Нь
2.4Конечные разности. Конечно-разностные методы интерполяции. Интерполяция по формулам Ньютона для сетки равноотстоящих узлов
Желательным свойством интерполяционного многочлена был бы его более простой вид и возможность легко перестраивать его степень (аналогично тому, как это имеет место для формулы Тейлора).
Сначала будем рассматривать интерполяцию на системе равноотстоящих узлов, т.е. xi = x0 + ih, где h – некоторая постоянная (для данной сетки) величина, называемая
шагом сетки.
Величины ∆y0 = y1 − y0, . . . , ∆yn−1 = yn − yn−1 называются конечными разностями первого порядка (последовательности значений {yk}nk=0), или просто первыми разностями.
Величины ∆2y0 = ∆y1 − ∆y0, . . . , ∆2yn−1 = ∆yn−1 − ∆yn−2 называются конечными разностями второго порядка, или просто вторыми разностями.
В общем случае, величина ∆kyi = ∆k−1yi+1 −∆k−1yi называется конечной разностью порядка k, или просто k-й разностью. Методом математической индукции можно показать справедливость формулы:
|
|
|
∑j |
|
|
|
|
|
i |
|
|
|
|
∆kyi = Ckjyk+i−j |
|
||
|
|
|
=0 |
|
|
Далее, учитывая, что: |
|
|
|
|
|
lim |
yi+1 − yi |
= lim |
f(xi + h) − f(xi) |
= f′(xi, ) |
|
h |
h |
||||
h→0 |
h→0 |
|
|||
имеем:
lim ∆yi = hf′(xi)
h→0
Таким образом, первые разности характеризуют первую производную аппроксимируемой функции. Теперь, для вторых разностей имеем:
∆2yi |
= |
∆yi+1 − ∆yi |
≈ |
f′(xi + h) − f′(xi) |
≈ |
f′′(x |
) |
|
h2 |
h2 |
h |
||||||
|
i |
|
Можно показать по индукции, что имеет место более общая формула:
∆kyi ≈ hkf(k)(xi)
Сказанное обосновывает часто используемую замену производных конечными разностями. Отметим, что n-е конечные разности многочлена степени n постоянны (или практически постоянны, с учетом ошибок вычислений), а все последующие равны 0 (замечаем, что ровно те же утверждения справедливы и для производных).
Желая придать интерполяционному многочлену Лагранжа возможно более простой вид, будем его искать в следующем виде. Положим
Pn(x) = a0 + a1(x − x0) + · · · + an(x − x0) . . . (x − xn−1)
Коэффициенты найдем из условия интерполяции Pn(xi) = yi. Учитывая, что, например, Pn(x0) = y0 = a0, находим первый коэффициент многочлена. Второй коэффициент
52 |
Глава 2. Полиномиальная интерполяция функций |
||
получим их равенства Pn(x1) = a0 + a1(x1 − x0) = y1, откуда a1 = |
∆y0 |
. Положим теперь |
|
|
|||
h |
|||
i = 2.
a0 + a1(x2 − x0) + a2(x2 − x0)(x2 − x1) = y2
y0 + ∆hy0 (x2 − x0) + a2(x2 − x0)(x2 − x1) = y2
y0 + ∆hy0 · 2h + a2 · 2h · h = y2
y0 + 2∆y0 + a2 · 2h2 = y2
a2 = |
y2 − y0 − 2∆y0 |
||||
|
|
|
|
2h2 |
|
a2 |
= |
y2 − 2y1 + y0 |
|||
|
|
|
|
2h2 |
|
|
a2 = |
∆2y0 |
|
||
|
2h2 |
||||
Далее можно показать, что:
∆ky0 ak = k!hk
Тогда искомый многочлен принимает вид:
Pn(x) = y0 + |
∆y0 |
(x − x0) + |
∆2y0 |
(x − x0)(x − x1) + · · · + |
∆ny0 |
(x − x0) . . . (x − xn−1) |
h |
2h2 |
n!hn |
Многочлен такого вида называется первым интерполяционным многочленом Ньютона. Поскольку каждое слагаемое, начиная со второго, содержит множитель (x−x0), то ло-
гично предположить, что данный многочлен лучше всего использовать при приближении функции в окрестности точки x0 (снова находим аналогию между конечными разностями и производными, интерполяционной формулой Ньютона и разложением в ряд Тейлора).
Поэтому узел x0 |
будем называть базовым. Введем замену переменных q = |
x − x0 |
. При |
||||||||||||||||||
h |
|||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
для любого i получим, что (x − xi) = h(q − i). Тогда приходим к формуле: |
|
|
|||||||||||||||||||
f(x) |
≈ |
P |
(x |
|
+ qh) = y |
|
+ q∆y |
|
+ |
q(q − 1) |
∆2y |
|
+ |
· · · |
+ |
q(q − 1) . . . (1 − n + 1) |
∆ny |
|
|||
|
n |
|
n |
|
0 |
|
0 |
2! |
|
0 |
|
|
n! |
|
0 |
||||||
– первый интерполяционной формуле Ньютона.
Поскольку на практике оказывается достаточно многочлена небольшой степени для достижения нужной точности приближения, в качестве базового узла можно принимать любой ближайший к данной точке узел, при условии что после есть достаточно узлов для построения интерполяционной формулы.
Заметим, что описанный процесс нельзя применить, если интересующая нас точка находится в конце сетки. Однако это можно исправить, если записать формулу несколько иначе, а именно за базовый узел взять последний, а затем отсчитывать узлы в обратном порядке. Таким образом получается, так называемая, второй интерполяционный полином Ньютона:
2.4. Конечные разности. Конечно-разностные методы интерполяции. Интерполяция по формулам Нь
|
|
|
|
|
∆yn−1 |
|
|
|
∆2yn−2 |
|
|
|
|
|
|
|
∆ny0 |
|
|
||||
Pn(x) = yn + |
|
h |
(x − xn) + |
|
2h2 |
(x − xn)(x − xn−1) + · · · + |
n!hn |
(x − xn) . . . (x − x1) |
|||||||||||||||
Используя обозначение q = |
x − x0 |
, приходим ко второй интерполяционной фор- |
|||||||||||||||||||||
муле Ньютона: |
|
|
|
|
h |
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
f(x) |
≈ |
P |
(x |
|
|
+ qh) = y |
|
+ q∆y |
n−1 |
+ |
q(q − 1) |
∆2y |
n−2 |
+ |
· · · |
+ |
q(q − 1) . . . (1 − n + 1) |
∆ny |
|
||||
|
n |
|
n |
|
|
n |
|
|
|
2! |
|
|
|
|
|
n! |
|
0 |
|||||
Далее, рассмотрим случай, когда базовый узел берется в середине сетки. Тогда остальные узлы нумеруются индексами ±i: x0, x−1, x1, ....
В таком случае получается первая интерполяционная формула Гаусса:
f(x) ≈ P n(x0 + qh) = y0 + q∆y0 + q(q − 1)∆2y−1 + 2!
(q + 1)q(q − 1)(q − 2)∆4y−2 + . . . (2.1) 4!
Как видно, в этом процессе последовательно подключаются точки стоящие справа и слева (в таком порядке) от базового узла. Можно эти точки подключать наоборот – сначала те, что слева, а затем – те, что справа. Тогда получим вторую интерполяционную формулу Гаусса:
|
f(x) ≈ Pn(x0 + qh) = y0 + q∆y−1) + |
q(q + 1) |
2 |
|
|
||||||
|
|
|
∆ y−1 |
+ |
|
||||||
|
2! |
|
|
||||||||
+ |
(q + 1)q(q −e |
1) |
∆3y |
2 + |
(q + 2)(q + 1)q(q − 1) |
∆4y |
2 + . . . |
(2.2) |
|||
3! |
|
|
|||||||||
|
|
− |
|
4! |
|
|
− |
|
|
|
|
Формулы Гаусса не являются вполне симметричными, но более симметричные формулы легко получить из формул Гаусса. Например, полусумма первой и второй Гауссовых формул дает формулу Стирлинга:
f(x) |
≈ |
P |
(x |
|
+ qh) = y |
|
+ q |
∆y−1 + ∆y0 |
+ |
q2 |
∆2y |
|
+ + |
q(q2 − 1) |
· |
∆3y−2 − ∆3y−1 |
|
|
2 |
|
−1 |
|
2 |
||||||||||
|
S |
|
0 |
|
0 |
|
2 |
|
3! |
|||||||
Если взять полусумму второго многочлена Гаусса и того же полинома, но с увеличенными на единицу нижними индексами (т.е. за базовую берется точка x1), то получим
формулу Бесселя:
f(x) |
|
P |
|
(x |
|
+ qh) = |
y0 + y1 |
+ q |
|
1 |
∆y |
|
+ |
q(q − 1) |
|
∆2y−1 + ∆2y0 |
+ |
|
||||||
|
|
|
|
|
|
|
|
|
||||||||||||||||
≈ |
|
|
|
− |
2) |
|
|
|
|
|
|
|||||||||||||
|
|
B |
|
0 |
2 |
( |
|
0 |
|
|
2! |
|
|
|
2 |
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(q − |
|
) q(q − |
1) |
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
3 |
|
|
(2.3) |
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
+ |
|
|
|
|
|
|
|
∆ y−1 |
+ . . . |
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3! |
|
|
|
||||||
54 |
Глава 2. Полиномиальная интерполяция функций |
2.5Интерполяция на сетке с неравноотстоящими узлами
2.5.1Разделенные разности. Интерполяция по формулам Ньютона для сетки неравноотстоящих узлов
Для построения интерполяционных формул, имеющих перед классической интерполяционной формулой Лагранжа преимущества, какими обладают конечноразностные формулы, и применимых в более общем по сравнению с последними случае произвольного расположения упорядоченных несовпадающих узлов x0, x1, . . . , xn на промежутке [a, b], вместо конечных разностей используют разделенные разности (разностные отношения).
Сначала через значения функции f(x0), f(x1), . . . , f(xn) определяют разделенные разности первого порядка:
f(x0; x1) = f(x1) − f(x0) x1 − x0
f(x1; x2) = f(x2) − f(x1) x2 − x1
· · · · · · · · · · · · · · · · · · · · · · · · · · ·
f(xn−1; xn) = f(xn) − f(xn−1) xn − xn−1
На этих разностях базируются разделенные разности второго порядка:
f(x0; x1; x2) = f(x1; x2) − f(x0; x1) x2 − x0
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
f(xn−2; xn−1; xn) = f(xn−1; xn) − f(xn−2; xn−1) xn − xn=2
и т.д. Таким образом, если определены k-е разностные отношения f(xi; xi+1; . . . ; xi+k), то (k + 1)-е определяются через них равенством:
f(xi−1; xi; . . . ; xi+k) = |
f(xi; xi+1; . . . ; xi+k) − f(xi−1; xi; . . . ; xi+k−1) |
. |
(2.4) |
|
xi+k − xi−1 |
|
|
Легко убедиться, что операция взятия разделенной разности, как и в случае конечной разности, аддитивна и однородна, т.е. линейна. Кроме того, разделенная разность является симметрической функцией своих аргументов, что позволяет менять в ней местами аргументы.
Доказательство симметричности опирается на представление k-й разделенной разности через значения функции в узлах, имеющее вид:
k |
|
|
|
|
|
|
|
|
f(xi+j) |
|
|
|
|
|
|
||
f(xi; xi+1; . . . ; xi+k) = |
|
|
|
|
|
|
|
|
|
|
|
|
|
. |
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
(xi+j |
− |
xi) . . . (xi+j |
− |
xi+j |
− |
1)(xi+j |
− |
xi+j+1) . . . (xi+j |
− |
xi+k) |
|||||||
∑j |
|
|
|
|
|
|
|
|
|
|
|
|
|||||
=0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(2.5) |
|
При k = 1 справедливость выражения (2.5) очевидна: |
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
||||||||||
f(xi; xi+1) = |
f(xi+1) − f(xi) |
= |
|
f(xi+1) |
+ |
|
f(xi) |
. |
|
|
|
||||||
|
|
|
|
|
|
|
|||||||||||
|
|
|
xi+1 − xi |
|
|
xi+1 − xi |
xi − xi+1 |
|
|
|
|||||||
Для произвольных натуральных k свойство (2.5) доказывается на основе (2.4) по индукции.
2.5. Интерполяция на сетке с неравноотстоящими узлами |
55 |
Как и для конечных разностей, взятие разделенной разности многочлена понижает его степень на единицу. Это следует из рассмотрения разделенной разности f(xi; xi+1) степенной функции f(x) = xn:
f x |
|
x |
xin+1 − xin |
|
xn−1 |
|
xn−2 |
· |
x |
i + · · · + |
x |
|
xn−2 |
|
xn−1. |
i; |
i+1) = xi+1 − xi |
|
|
|
|
||||||||||
( |
|
= |
i+1 |
+ |
i+1 |
|
|
i+1 |
i |
+ |
i |
Отсюда приходим к заключению, что разделенные разности n-го порядка многочлена n-й степени
Pn(x) = a0xn + a1xn−1 + · · · + an−1x + an
постоянны.1 Значит, как и в конечноразностном случае, анализируя таблицу разделенных разно-
стей, по порядку почти совпадающих разделенных разностей можно сделать вывод о предпочтительной степени многочлена, подходящего для интерполирования данной функции.
В основу построения интерполяционного многочлена по типу первого интерполяционного многочлена Ньютона, но для случая неравных промежутков между узлами xi, положим следующие рассуждения.
Пусть ϕ(x) — некоторая функция с известными значениями в узлах x0, x1, . . . , а x
— произвольная фиксированная точка. По определению разделенной разности первого порядка имеем
ϕ(x; x0) = |
ϕ(x0) − ϕ(x) |
= |
ϕ(x) − ϕ(x0) |
, |
|
x0 − x |
|
|
|||
откуда |
|
x − x0 |
|
||
|
|
|
|
|
|
ϕ(x) = ϕ(x0) + ϕ(x; x0)(x − x0). |
(2.6) |
||||
Для разделенной разности второго порядка по точкам x, x0, x1 записываем представление
ϕ(x; x0; x1) = |
ϕ(x0; x1) − ϕ(x; x0) |
= |
ϕ(x; x0) − ϕ(x0; x1) |
, |
x1 − x |
|
|||
|
|
x − x1 |
||
следствием которого является выражение
ϕ(x; x0) = ϕ(x0; x1) + ϕ(x; x0; x1)(x − x1).
Подставляя его в (2.6), приходим к равенству
ϕ(x) = ϕ(x0) + ϕ(x0; x1)(x − x0) + ϕ(x; x0; x1)(x − x0)(x − x1).
Формально, на основе определяющего разделенные разности рекуррентного соотношения (2.4), этот процесс может быть продолжен. В результате можно записать формулу, описывающую своеобразное разложение ϕ(x) по произведениям разностей (x − xi), коэффициентами в котором являются разделенные разности различных порядков:
ϕ(x) = ϕ(x0) + ϕ(x0; x1)(x − x0) + ϕ(x0; x1; x2)(x − x0)(x − x1) + · · · +
+ϕ(x0; x1; . . . , xn)(x − x0) . . . (x − xn−1)+ (2.7) +ϕ(x; x0; x1; . . . ; xn)(x − x0) . . . (x − xn−1)(x − xn).
Если ϕ(x) = Pn(x) — многочлен степени n, то процесс подобного разложения исчерпается. Разложение будет состоять из n + 1 слагаемого, и все они будут иметь конкретные коэффициенты, так как последняя, содержащая x, разделенная разность в (2.7), т.е.
1Показано, что Pn(x; x + h1; : : : ; x + hn) = a0, а (n + 1)-е и все последующие разделенные разности равны нулю.
56 |
Глава 2. Полиномиальная интерполяция функций |
ϕ(x; x0; . . . ; xn) = Pn(x; x0; . . . ; xn) имеет (n + 1)-й порядок и, значит, равна нулю. Таким образом, для любого многочлена степени n справедливо тождество:
Pn(x) = Pn(x0) + Pn(x0; x1)(x − x0) + Pn(x0; x1; x2)(x − x0)(x − x1) + · · · + +Pn(x0; x1; . . . ; xn)(x − x0)(x − x1) . . . (x − xn−1).
Предположим, что этот многочлен Pn(x) является интерполяционным для некоторой функции f(x). Тогда во всех узлах x0, x1, . . . , xn он должен иметь одинаковые с ней значения, а значит, должны быть одинаковыми и их разделенные разности. Отсюда приходим к интерполяционной формуле Ньютона для неравноотстоящих узлов:
f(x) ≈ Pn(x) = f(x0) + f(x0; x1)(x − x0) + f(x0; x1; x2)(x − x0)(x − x1) + · · · + |
(2.8) |
+f(x0; x1; . . . ; xn)(x − x0)(x − x1) . . . (x − xn−1).
Подставив f(x) вместо ϕ(x) в (2.7), с учетом (2.8) получаем точное равенство f(x) = Pn(x) + f(x; x0; . . . ; xn)(x − x0) . . . (x − xn−1)(x − xn),
второе слагаемое в котором может рассматриваться в качестве остаточного члена, т.е.
Rn(x) = f(x) − Pn(x) = f(x; x0; . . . ; xn)Πn+1(x), |
(2.9) |
где Πn+1(x) — введенный ранее многочлен.
Поскольку для вычисления разности f(x; x0; . . . ; xn) требуется знание значения f(x) наряду с известными значениями f(x0), . . . , f(xn), представляемое формулой (2.9) выражение Rn(x) фактически можно использовать только для оценивания погрешности интерполирования по формуле (2.8) через максимальные величины модулей разделенных разностей (n + 1)-го порядка (если в них содержится достаточно незашумленной информации) или для получения других выражений остаточного члена при тех или иных предположениях о данной функции. В частности, можно вывести формулу:
f(n+1)(ξ)
Rn(x) = (n + 1)! Πn+1(x)
Можно показать, что f(x0; . . . ; xr) ≈ f(k)(x)
При практическом использовании интерполяционной формулы (2.8) приходится полагаться на убывание модулей слагаемых в Pn(x) при увеличении номера слагаемого. Такое убывание обычно происходит до некоторых пор, затем начинается рост модулей из-за влияния ошибок округления.
2.5.2Многочлены Чебышева. Свойства многочленов Чебышева
Определение 2.5.1. Многочленом Чебышева называется функция
Tn(x) = cos(n arccos x), |
(2.10) |
где n N0, x [−1, 1].
Убедимся, что функция Tn(x), представленная с помощью тригонометрических функций, на самом деле является многочленом при n = 0, 1, 2, . . . .
Непосредственной подстановкой значений n = 0 и n = 1 получаем T0(x) = 1, T1(x) = x. Положив α = arccos x, имеем:
T1(x) = cos α, |
Tn(x) = cos nα, |
Tn−1(x) = cos(n − 1)α, |
Tn+1(x) = cos(n + 1)α, |
2.5. Интерполяция на сетке с неравноотстоящими узлами |
57 |
и так как (по формуле суммы косинусов)
cos(n + 1)α + cos(n − 1)α = 2 cos α cos nα,
то, значит, справедливо равенство
Tn+1(x) + Tn−1(x) = 2T1(x)Tn(x),
которое можно переписать в виде:
Tn+1(x) = 2xTn(x) − Tn−1(x). |
(2.11) |
Эта формула определяет при n = 1, 2, 3, . . . последовательность функций Tn(x), начинающуюся с T0(x) = 1, T1(x) = x, рекуррентно. При этом нужно иметь в виду, что здесь x [−1, 1], как в определении многочленов Чебышева.
Подставляя в рекуррентную формулу (2.11) заданные начальные члены последовательности {Tn(x)}, найдем несколько ее последующих членов:
T2(x) = 2x2 − 1;
T3(x) = 2x(2x2 − 1) − x = 4x3 − 3x;
T4(x) = 2x(4x3 − 3x) − 2x2 + 1 = 8x4 − 8x2 + 1;
T5(x) = 2x(8x4 − 8x2 + 1) − 4x3 + 3x = 16x5 − 20x3 + 5x
и т.д.
Анализ рекуррентной формулы (2.11) позволяет считать очевидными следующие фак-
ты:
1.все функции Tn(x), определенные в (2.10), являются многочленами при любом натуральном n;
2.степени этих многочленов возрастают с увеличением n, причем старший член многочлена Tn(x) равен 2n−1xn;
3.многочлены Tn(x) при четных n выражаются через степенные функции только нечетных степеней, а при нечетных – только нечетных.
Наряду с многочленами Чебышева Tn(x) часто используют многочлены, получаемые из Tn(x) делением на старший коэффициент, т.е.
˜ |
1 |
|
Tn(x) = |
2n−1 |
Tn(x) |
— многочлены со старшим коэффициентом, равным 1. Будем называть их нормированными многочленами Чебышева.
Рассмотрим некоторые свойства многочленов Чебышева, имеющие отношение к проблеме аппроксимации функций.
˜
Теорема 2.5.1. Многочлен Чебышева Tn(x) (а значит, и многочлен Tn(x)) имеет на отрезке [−1, 1] ровно n различных действительных корней, причем все они задаются формулой
xk = cos |
2k + 1 |
π, где k = 0, 1, . . . , n − 1. |
(2.12) |
2n |
58 |
Глава 2. Полиномиальная интерполяция функций |
Доказательство. Корни многочлена Чебышева Tn(x) можно получить, решая тригонометрическое уравнение
|
|
cos(n arccos x) = 0. |
|
|
Имеем: |
|
|
|
|
n arccos x = |
π |
+ πk arccos x = |
2k + 1 |
π. |
|
|
|||
2 |
2n |
Поскольку главные значения арккосинуса должны принадлежать промежутку [0, π], целая переменная k здесь должна принимать значения от 0 до n − 1. Переходя на этом промежутке к обратной функции (беря косинус от левой и правой частей последнего равенства) и учитывая, что cos arccos x = x, приходим к выводу, что n действительных корней многочлена Tn(x), определяемые формулой (2.12), на самом деле существуют.
Их несовпадение и принадлежность отрезку [−1, 1] следует из того, что они представляют собой значения косинуса, соответствующие различным значениям его аргумента, расположенным на промежутке его монотонности.J
Теорема 2.5.2. Корни многочленов Чебышева перемежаются с точками их наибольших и наименьших значений, равных соответственно +1 и −1 для Tn(x) и +1/2n−1 и −1/2n−1
˜
для Tn(x). А именно при j = 0, 1, . . . , n имеют место экстремумы:
T |
(x |
) = ( |
1)j, |
T˜ |
(x |
) = |
(−1)j |
x |
|
= cos |
j |
π. |
2n−1 в точках |
|
n |
||||||||||
n |
j |
|
− |
n |
j |
|
|
j |
|
|
Теорема 2.5.3 (теорема Чебышева). Из всех многочленов степени n со старшим коэф-
˜
фициентом, равным 1, нормированный многочлен Чебышева Tn(x) наименее уклоняется от нуля на отрезке [−1, 1].
Следствие 2.5.1. Среди всех многочленов степени n вида
Pn(x) = xn + a1xn−1 + · · · + an |
(2.13) |
˜
нормированный многочлен Чебышева Tn(x) минимизирует максимальное расстояние
˜
от графика многочлена при x [−1, 1] до оси абсцисс, т.е. Tn(x) – многочлен с наименьшей нормой (так называемой чебышевской нормой) на множестве многочленов вида (2.13) в пространстве C[−1, 1].
Замечание 2.5.1. Иногда бывает более удобным использовать смещенные многочлены Чебышева Tn (x), которые определяются на отрезке [0, 1] и могут быть получены из классических многочленов Чебышева Tn(x) заменой в них аргумента x на 2x − 1.
2.5.3Задача об оптимальной расстановке узлов для минимизации максимальной ошибки
Интерполяционные многочлены, построенные по системе равноотстоящих узлов, проще в использовании, чем интерполяционный многочлен Лагранжа, предполагающий произвольное расположение несовпадающих узлов на промежутке интерполирования [a, b]. Однако многочлен Лагранжа обладает большими возможностями. Если можно располагать узлы в пределах отрезка [a, b] произвольно, то имеет смысл использовать большее количество точечной информации о функции там, где она более сильно изменяется. Особенно существенным это замечание может оказаться при эрмитовой интерполяции.
2.5. Интерполяция на сетке с неравноотстоящими узлами |
59 |
Подойдем к проблеме расположения узлов интерполяции с несколько иной стороны. Желая, чтобы интерполяционный многочлен Лагранжа Ln(x) в целом хорошо приближал функцию f(x) на отрезке [a, b], поставим вопрос: как расположить на нем n + 1 узлов интерполяции xi (i = 0, 1, . . . , n), чтобы при этом минимизировать максимальную на [a, b] погрешность?
Поскольку, согласно (1.15),
x [a,b] | |
|
− |
|
|
| ≤ |
Mn+1 |
|
| |
|
|
| |
|
(2.14) |
|
n |
|
|
|
n+1 |
|
|||||||
|
|
(n + 1)! |
x [a,b] |
|
|
||||||||
max |
f(x) |
|
L |
(x) |
|
|
max |
|
Π |
|
(x) |
, |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
и величина Mn+1 = max |f(n+1)(x)| не зависит от расположения узлов, займемся изу-
x [a,b]
чением определенного в (1.10) многочлена Πn+1(x).
Выполним преобразование независимой переменной, положив
x = a + b + b − at.
2 2
Легко видеть, что эта линейная замена осуществляет взаимно однозначное соответствие между x [a, b] и t [−1, 1]. Тогда узлам интерполяции xi [a, b] можно сопоставить точки ti [−1, 1], полагая
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
xi = |
a + b |
+ |
b − a |
ti. |
|
|
|
|
|
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
Тогда образующие Πn+1(x) сомножители x − xi преобразуются по формуле |
|
|
|
||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x |
− |
x |
|
|
= |
b − a |
(t |
− |
t |
), |
|
|
|
|
|
|
|
|
||||||||
|
и, следовательно, |
|
|
|
|
|
|
|
|
|
|
|
i |
|
|
|
|
2 |
|
|
|
i |
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
∏ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
∏ |
|
|
|
|
( |
b |
|
) |
|
|
|
|
|
|
|
|
|
|
|
|
|
( |
|
|
|
|
|
|
|
|
|
|
|
||||
Π |
|
(x) = |
n (x |
− |
x |
) = |
|
− a |
|
|
|
|
|
(t |
− |
t |
) = |
|
b − a |
n+1 (t |
t )(t |
t |
) . . . (t |
t |
|
). |
(2.15) |
|||||||||||||
|
n+1 |
|
i=0 |
i |
|
|
|
2 |
|
|
|
i=0 |
|
|
|
|
|
i |
|
|
|
2 |
) |
|
− 0 |
− 1 |
|
− |
n |
|
||||||||||
|
Из (2.15) очевидно, что значение x |
[a,b] |Πn+1( |
x |
)| будет минимальным, когда будет ми- |
||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
max |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
нимальным значение t [ |
|
1,1] |
|Πn+1 |
( |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
)|, где |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||
|
|
|
|
|
|
|
max |
|
|
|
t |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
− |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Πn+1(t) = (t − t0)(t − t1) . . . (t − tn) |
|
|
|
|
|
|
|||||||||||||||||||||||
— многочлен n + 1 степени, в котором точки ti [−1, 1] |
(i = 0, 1, . . . , n) считаем парамет- |
|||||||||||||||||||||||||||||||||||||||
рами. Так как коэффициент при старшей степени многочлена Πn+1(t) в его каноническом
представлении равен 1, то, в силу теоремы 2.5.3, величина max |Πn+1(t)| (а, значит, и
t [−1,1]
max |Πn+1(x)|) будет минимальной в том случае, когда Πn+1(t) – нормированный полином
x [a,b]
˜
Чебышева Tn+1(t).
˜
Полагая Πn+1(t) = Tn+1(t), имеем: с одной стороны, точки t0, t1, . . . , tn являются узлами интерполяции (для переведенной задачи интерполяции с исходного отрезка [a, b] на отрезок [−1, 1]), с другой стороны, в силу структуры многочлена Πn+1(t), они служат
˜
его корнями, а, значит, и корнями Tn+1(t). Из этого следует, что справедливо следующее утверждение:
Утверждение 2.5.1. Максимальная погрешность интерполирования достаточно гладкой функции на отрезке [−1, 1] многочленом n-й степени будет минимальной, когда в качестве узлов интерполяции t0, t1, . . . , tn [−1, 1] берутся корни многочлена Чебышева
˜
Tn+1(t) (как известно, совпадающие с корнями Tn+1(t)).
60 Глава 2. Полиномиальная интерполяция функций
Будем называть такие узлы интерполяции чебышевскими узлами интерполяции. Знание экстремальных значений многочлена Чебышева позволяет уточнить величину максимального отклонения Ln(x) от f(x) при таком выборе узлов, т.е. когда точки ti
˜
(= cos 22ni+1+2 π, i = 0, n) являются корнями Tn+1(t), а xi = a+2 b + b−2a ti. А именно, поскольку
|
| |
˜ |
|
| |
|
1 |
, то, согласно (2.15), |
|
t [ 1,1] |
T |
n+1 |
(t) |
= |
2n |
|||
max |
|
|
|
|
|
|||
−
max |
Π |
|
|
(x) |
| |
= |
( |
b − a |
) |
n+1 1 |
|||||||||
|
|
|
|
2n |
|
||||||||||||||
x [a,b] | |
|
n+1 |
|
|
|
|
2 |
|
|||||||||||
подставляя это в неравенство (2.14), получаем: |
|
|
|
||||||||||||||||
max |
|
f(x) |
|
|
L |
|
(x) |
|
|
|
Mn+1 |
||||||||
| |
− |
n |
| ≤ (n + 1)! |
||||||||||||||||
x |
|
[a,b] |
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
= (b − a)n+1 ;
22n+1
(b − a)n+1
22n+1
.
Полученная оценка называется наилучшей равномерной оценкой погрешности интерполяции.
Утверждение 2.5.2. Если функция f(x) бесконечно дифференцируема на [a, b] и в качестве узлов интерполяции берутся корни многочлена Чебышева (приведенные к отрезку [a, b]), то
max |
| |
f(x) |
− |
L |
(x) |
| n−→ |
0. |
|
x |
[a,b] |
|
n |
|
|
|||
|
|
|
|
|
|
|
→∞ |
|
Поскольку max |f(x) − Ln(x)| – не что иное, как f(x) − Ln(x) C[a,b] – чебышевская
x [a,b]
норма в пространстве C[a, b], можно говорить, что для достаточно гладких функций f(x) при специальном расположении узлов интерполяции последовательность интерполяционных многочленов Лагранжа {Ln(x)} (построенных по точным значениям функции f(x)) сходится к f(x) по норме Чебышева. Другими словами, имеет место равномерная сходимость последовательности {Ln(x)} к f(x).
Обобщением этого факта для непрерывных (необязательно дифференцируемых) функций и произвольных (необязательно интерполяционных) многочленов является следующая теорема.
Теорема 2.5.4 (Вейерштрасса). Для любой непрерывной на [a, b] функции f(x) найдется такой многочлен Qn(x), что
|f(x) − Qn(x)| < ε ε > 0 x [a, b].
Таким образом, если отказаться от того, чтобы аппроксимирующий функцию f(x) многочлен Qn(x) степени n был интерполяционным, от f(x) достаточно потребовать непрерывность на [a, b], чтобы за счет повышения степени многочлена при надлежащем подборе его коэффициентов величина чебышевской нормы f(x) −Qn(x) C[a,b] могла быть сделана сколь угодно малой.
Если степень n аппроксимирующего f(x) многочлена Qn(x) зафиксировать и распоряжаться только его коэффициентами, то в общем случае величину f(x) −Ln(x) C[a,b] нельзя сделать сколь угодно малой. Однако показано, что для любой функции f(x) C[a, b] существует единственный такой многочлен Qfn(x), который из всех многочленов Qn(x) степени n наилучшим образом аппроксимирует на [a, b] функцию f(x), т.е. такой, что
f(x) − Qfn(x) C[a,b] = inf f(x) − Qn(x) C[a,b].
Такой многочлен называется многочленом наилучшего равномерного приближения для f(x) на [a, b] или ее чебышевским приближением.
