Оптимальная интерполяция и принцип Лагранжа



Владикавказский математический журнал

Октябрь–декабрь, 2004, Том 6, Выпуск 4

ОПТИМАЛЬНАЯ ИНТЕРПОЛЯЦИЯ И ПРИНЦИП ЛАГРАНЖА ¹

Г. Г. Магарил-Ильяев

Дорогому учителю Владимиру Михайловичу Тихомирову с благодарностью за науку

На примере задачи интерполяции, демонстрируется применение принципа Лагранжа для решения задач оптимального восстановления линейных функционалов.

Задача интерполяции, которая здесь рассматривается, заключается в следующем. Пусть на отрезке [a, b] заданы n точек a 6 t i <...< t n 6 b, и в этих точках известны значения некоторой функции xQ, т. е. известны числа x(t i ),..., x(t n ), а мы хотим определить значение этой функции в другой точке т Е [a, b], где т = t i , 1 6 i 6 n. Стандартный прием состоит в том, что строят полином p ( • ) степени n — 1 такой, что p (t i ) = x(t i ), 1 6 i 6 n (он определен однозначно и называется интерполяционным полиномом Лагранжа) и считают, что х(т ) = p (т). Можно поступить проще: соединяя точки (t i , x(t i )) и (t i+i ,x(t i+i )), i = 1,...,n — 1, отрезками прямых, получим кусочно линейную функцию f( • ) и будем считать, что х(т) = f(т). Можно придумать и другие способы восстановления (как мы будем говорить) функции x( ^ ) в точке т . При этом ясно, что до тех пор пока нет никакой априорной информации о функции x( ^ ), мы не можем отдать предпочтение ни одному из таких способов. Предположим теперь, что такая информация о функции x( ^ ) имеется и она заключается в том, что x( ^ ) принадлежит некоторому фиксированному классу функций C на отрезке [a, b]. Такого рода информация может появиться, например, из следующих соображений: пусть функция x( ^ ) имеет некую физическую природу и известно (в силу этой природы), что резкие скачки x( ^ ) невозможны. Формализовать это можно, например, так: производная функции x( ^ ) по модулю не превосходит некоторого положительного числа. Тем самым выделится класс функций C , которому наша функция принадлежит.

Итак, будем исходить из того, что мы наблюдаем значения функции xQ, про которую известно, что она принадлежит некоторому классу функций C . В этой ситуации мы уже можем сравнивать различные способы восстановления функций из C в точке τ . Поступаем следующим образом. Пусть m( ^ ) — произвольная функция n переменных. Для каждого x( ^ ) в качестве оценки х(т) возьмем число m(x(t i ),..., x(t n )). Эффективность такого метода восстановления х(т) на классе C будем характеризовать величиной

е(т, C,t i , ... ,t n ; m0) = sup | х(т) — m(x(t i ),..., x(t n )) | ,                  (1)

x(-)eC

дающей максимальное (на классе) расхождение между истинным значением функции в точке т и оценкой этого значения с помощью функции (метода) m0.

Заметим, что оценка х(т ) с помощью интерполяционного полинома Лагранжа состоит в том, что мы берем число p (т ) = ^2П ₌₁ l i (T )x(t i ), где li0, 1 6 i 6 n, — полиномы степени n — 1 такие, что l i (T j ) = 1, если i = j, и l i (T j ) = 0, если i = j . Другими словами, в качестве метода восстановления х(т ) мы рассматриваем линейную функцию m« i ,...,C n ) = Р П=1 l i (T )&.

Нас интересует вопрос, на каком методе восстановления m0 величина (1) достигает своего минимального значения и чему это значение равно? Точнее говоря, нас интересует величина

Е(т, C,t i ,... ,t n ) = inf е(т, C,t i ,... ,t n ; m0) (2) m(-)

(где нижняя грань берется по всем функциям n переменных), которая называется по грешностью оптимального восстановления и метод m( • ), на котором эта нижняя грань достигается, называемый оптимальным методом восстановления .

Нахождение оптимальной погрешности восстановления и оптимального метода восстановления будем называть задачей оптимальной интерполяции на классе C .

В данной работе мы решаем эту задачу для случая, когда C = W ^ ([a, b]) (совокупность функций x( - ) на [a, b], у которых (n — 1)-ая производная x ^(n-1) ( • ) абсолютно непрерывна на [a, b] и ||x ⁽ⁿ⁾ ( ^ ) k L _M ([_a,b]) 6 1) и показываем, что интерполяционный полином Лагранжа — оптимальный метод восстановления. Основная цель, которую мы при этом преследуем — продемонстрировать применение принципа Лагранжа для решения задачи оптимального восстановления. Этот принцип позволяет получать решения многих экстремальных задач, в некотором смысле, автоматически. Он заключается в том, что надо составить функцию (функцию Лагранжа), которая есть сумма минимизируемого или максимизируемого функционала и функций, задающий различные ограничения с неопределенными множителями (множителями Лагранжа) и тогда решение исходной задачи удовлетворяет необходимым условиям минимума в более простой задаче — в задаче на минимум функции Лагранжа без ограничений (при некотором наборе множителей Лагранжа). Этот прием (который впервые был сформулировал Лагранжем для задач с ограничениями типа равенств) оказался универсальным — он верен (при весьма широких предположениях) для любых экстремальных задач с ограничениями типа равенств, неравенств и включений. Если задача выпукла, то функция Лагранжа на решении достигает минимума и более того, если множитель Лагранжа при минимизируемом (или максимизируемом) функционале отличен от нуля, то функция, которая удовлетворяет необходимым условиям минимума функции Лагранжа, является решением исходной задачи. Подробнее о принципе Лагранжа и его приложениях см. в [1] и [2]. Не бояться применять принцип Лагранжа для решения самых различных задач я научился у В. М. Тихомирова.

Применением принципа Лагранжа, доказывается следующая

Теорема 1. Справедливо равенство

n

E ^{( t,w}«d ^{([ a,}b ^{]) ,t} i ^,...^,t n ) = -j П^{(т —} t j ) n!

j=i

и метод m(^ i ,... , £ _n ) = ^2П =1 l i (T )£ i (интерполяционный полином Лагранжа) является оптимальным.

C Свяжем с задачей оптимального восстановления следующую экстремальную задачу

х(т ) ^ max, x(t i ) = 0, 1 6 i 6 1, x( - ) G W ^ ([a, b])                (3)

и обозначим через S(т, W^, ([a, b]), t ₁ ,..., t n ) ее значение. Покажем, что

E ^{( т}, W n ^([a,b]) ,t i , . ..,t n ) >  S ^(т, W n ^([a,b]) ,t i ,. ..,t n ) .                  ⁽⁴⁾

Действительно, пусть x( -) — допустимая функция в (3). Тогда и — x( -) — допустимая функция в этой задаче и мы имеем для любого метода m( - )

2х(т) 6 | х(т) — m(0) + х(т) + m(0) | 6 | х(т) — m(0) | + | — х(т) — m(0) |

6 2 sup       | х(т) — m(0) | 6 2 sup       | х(т) — m(x(t ₁ ),...,x(t n )) | .

x(-)eC ([a,b])                           x(^)eW " ([a,b])

x(t i )=0, i=1_v..,n

Переходя справа к нижней грани по всем методам m( - ), а затем слева к верхней грани по всем допустимым в (3) функциям x( - ), получаем требуемое утверждение. B

Задача оптимального восстановления является (в определенном смысле) двойственной к задаче (3) (см. [2]) и поэтому решив последнюю, мы найдем и оптимальный метод и погрешность оптимального восстановления.

Задачу (3) запишем формально следующим образом

/ 5(t — т )x(t) dt ^ max, a

[ 5(t — ti)x(t) = 0, 1 6 i 6 1, x(n)(t) = u(t), |u(t)| 6 1, a где 5(- — £) — 5-функция в точке £ и последнее неравенство понимается п. в.

Мы выпишем необходимые условия максимума в ней, рассуждая эвристически, не ссылаясь ни на какие точные результаты, а руководствуясь лишь здравым смыслом и верой в то, что принцип Лагранжа верен. Это приведет нас к некоторым соотношениям, справедливость которых мы уже проверим непосредственно. Так как задача (3) выпукла, то эти соотношения позволят нам найти ее решение, а затем доказать все утверждения теоремы.

Отметим, что внешне задача (5) — стандартная задача оптимального управления и можно было бы сразу выписать необходимые условия максимума, но мы их получим, исходя из общих рассуждений.

Выпишем функцию Лагранжа задачи, не включая в нее ограничение | u(t) | 6 1 и воспринимая ограничение x ⁽ⁿ⁾ (t) = u(t) как континуум равенств, каждое из которых надо умножить на множитель Лагранжа p(t), а затем их «просуммировать»:

L (x( * ),u( * ),A) = J \( — 5(t

— т ) + XX ^6(t — t i ))x(t) + p (t)(x ⁽ⁿ⁾ (t) — u(t)) dt. i=i

Здесь A = ( — 1,^ ₁ ,... , ц _п ,p ( • )) (мы взяли множитель Лагранжа при максимизируемом функционале равным — 1, чтобы полученные необходимые условия максимума оказались и достаточными).

Если пара (b( - ), b( - )) — решение задачи (5), то согласно принципу Лагранжа существует такое А, что функция Лагранжа должна достигать минимума в этой точке по x( ^ ) и по uQ, т. е. должны выполняться условия:

L X(•) (b( • ),b( • ), А) = 0,    min L (bG),uG),A) = L (b( - ), b( - ), А).            (6)

Mt ^{)| 6 1}

Первое соотношение означает, что

- II

n

— S(t — т ) + ^2^ i 5(t — t i ) I x(t) + p (t)x ⁽ⁿ⁾ (t) I dt = 0 V xQ. i=1             /                       /

Интегрируя последнее слагаемое под знаком интеграла n раз по частям, приходим к равенству

/ Hit a

n

— т) + X m5(t — ti) + (—1)np(n)(t))x(t) dt i=1

+ X( — 1) k (P ^(k) (b)x ^(n-k-1) (b) — P ^(k) (a)x ^(n-k-1) (a)) = 0, k=0

верному для всех x( - ), и тем самым

—5(t — т) + X №5(t — ti) + (—1)np(n) (t) = 0(7)

i=1

и                            p(k)(a)= p(k)(b) = 0, k = 0,1,...,n — 1.

Из второго соотношения в (6) вытекает, что b(n) (t) = sign p (t).

Соотношения (7), (8) и (9) и есть необходимые условия максимума в задаче (3), которые можно было сразу выписать.

Теперь проанализируем полученные соотношения. Интегрируя (7), получаем, что

P (t) = (п — ГЙ ((t — т)+-1 — X ^ (t — tj )+-1) •

Покажем, что эта функция (с произвольными ^i, 1 6 i 6 n) сохраняет знак на [a, b]. Действительно, если это не так, то p (•) имеет нуль на (a, b). Поскольку p (a) = p (b) = 0, то по теореме Ролля p> (•) имеет на (a, b) не менее двух нулей. Продолжая, получим с учетом (8), что кусочно линейная функция p(n—2) (•) имеет на (a, b) не менее n — 1 нуля, а значит, снова в силу (8), на отрезке [a, b] она имеет не менее n + 1 нуля. Тогда по элементарному следствию из теоремы Ролля кусочно постоянная функция p(n-1)0 имеет на [a, b] не менее n перемен знака. Но эта функция с n интервалами постоянства (она может иметь разрывы только в точках т,t1,... ,tn) и поэтому у нее не может быть больше, чем n — 1 перемен знака. Итак, p (•) не меняет знак на [a, b] и тогда согласно (9) функция Ь0 есть полином n-го порядка со старшим коэффициентом по модулю равным 1/n! По условию x(tj) = 0, 1 6 j 6 n, и очевидно, ж(т) > 0. Этими условиями ж0 определяется однозначно: x(t) = a(1/n!) nj=i(t - tj), где а = sign ПП=1(т - tj).

Определим теперь числа ^ j , 1 6 j 6 n. Возьмем любой полином q(^) степени не выше n — 1, умножим на него обе части равенства (7) и проинтегрируем по отрезку [a, b]. Тогда получим q(т) = ^2n =i ^ j q(t j )• Подставляя сюда, определенные выше полиномы l j ( • ) G P n-i , найдем, что ^ j = l j (т), j = 1,..., n. Таким образом,

n

q^(т) = X ^l j ^{(т )}q⁽t j )•

j=i

Обозначим через W^([a, b]) пространство функций на [a, b], у которых (n — 1)-ая производная абсолютно непрерывна, а n-ая производная принадлежит L^([a, b]) (так что W^([a,b]) = {x(0 G Wn([a,b]) : ||x(n)(^)kLM([a,b]) 6 1}). Умножим (7) на функцию x0 из этого пространства и проинтегрируем по частям. Тогда будем иметь nb

х(т ) — ^^I j (т )x(t j ) = J p (t)x ⁽ⁿ⁾ (t) dt.

Итак, рассуждая эвристически, мы получили соотношения (11) и (12). Теперь будем рассуждать точно. Элементарная проверка показывает, что равенство (11) действительно имеет место для любого полинома степени не выше n — 1.

Покажем теперь, что тождество (12) справедливо для любой функции x( ^ ) G W^([a, b]) с функцией p ( • ), определяемой формулой (10), где ^ j = l j (т ), 1 6 j 6 n.

Из определения p ( • ) сразу следует, что p ^(k) (a) = 0, k = 0,1,..., n — 1. Далее p ^(k) (b) = 0, k = 0,1,..., n — 1, поскольку полиномы q k (t) = (1 — t) ^k , k = 0,1,..., n — 1, удовлетворяют (11). Используя это обстоятельство и интегрируя n — 1 раз по частям в интеграле справа в (12), убеждаемся после несложных преобразований, что равенство (12) справедливо.

Покажем, что функция $(•) — решение задачи (3). Подставляя в (12) любую допустимую в (3) функцию x( ^ ) и оценивая по модулю, будем иметь

х(т)= Г p (t)x ⁽ⁿ⁾ (t) dt 6 Г aa

| p (t) | dt.

Выше было показано, что p ( • ) не меняет знака на [a, b] и поэтому функция x ^{( n )} (^) (которая есть константа) совпадает с точностью до знака с signp ( • ). Подставим ж0 в (12) и учитывая, что ж(т) > 0, получим

^{Ь (т}) =

/ p (t)X ( ⁿ⁾ (t) dt =

a

a

p (t) sign p (t) dt

= a i p (t) i dt.

Таким образом, bQ — решение задачи (3). Тогда вследствие (4) верно

n

n

E(т,W n ([a,b]),t i ,...,t n ) > Ь(т) = - П(т — t j ) . n! ,

j =i

Из (12) и (13) для любого x( ^ ) G W^([a, b]) имеем

x

n                      pb                         1 n

(т)— X'(т)x(tj) 6    |p(t)|dt =ь(т) = — П(т—tj) , j=i                a                     n! j=i

n

b

n

т. е.

n

n

E ( t,W^ ([a,b]),t i ,...,t n ) 6 - П(т — t j ) -П!

j=1

Отсюда и (14) следует нужная оценка для E(т, W ^ ([a, b]), t i ,..., t n ) и оптимальность метода m (&,..., £ _n ) = j l j (т) j . B

Отметим, что если рассматривать задачу оптимальной интерполяции для случая, когда заданы n точек a 6 t i < ... < t n 6 b, а класс C = W ^ ([a, b]), где n = r, то при n < r задача не имеет смысла, так как можно построить, например, полином степени n (он, очевидно, будет принадлежать данному классу), который в точке τ принимает сколь угодно большие значения. Если же n > r, то задача осмысленна и здесь оптимальным методом будет интерполяционный сплайн. Доказательство получается на том же пути, что и в рассмотренном случае, но нужно воспользоваться еще утверждениями о существовании разного рода сплайнов.