Оптимальная интерполяция и принцип Лагранжа
Автор: Магарил-Ильяев Георгий Георгиевич
Журнал: Владикавказский математический журнал @vmj-ru
Статья в выпуске: 4 т.6, 2004 года.
Бесплатный доступ
На примере задачи интерполяции, демонстрируется применение принципа Лагранжа для решения задач оптимального восстановления линейных функционалов.
Короткий адрес: https://sciup.org/14318128
IDR: 14318128
Текст научной статьи Оптимальная интерполяция и принцип Лагранжа
Владикавказский математический журнал
Октябрь–декабрь, 2004, Том 6, Выпуск 4
ОПТИМАЛЬНАЯ ИНТЕРПОЛЯЦИЯ И ПРИНЦИП ЛАГРАНЖА 1
Г. Г. Магарил-Ильяев
Дорогому учителю Владимиру Михайловичу Тихомирову с благодарностью за науку
На примере задачи интерполяции, демонстрируется применение принципа Лагранжа для решения задач оптимального восстановления линейных функционалов.
Задача интерполяции, которая здесь рассматривается, заключается в следующем. Пусть на отрезке [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П =1 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 (n) ( ^ ) 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 1 ,..., t n ) ее значение. Покажем, что
E ( т, W n ([a,b]) ,t i , . ..,t n ) > S (т, W n ([a,b]) ,t i ,. ..,t n ) . (4)
Действительно, пусть 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 1 ),...,x(t n )) | .
x(-)eC ([a,b]) x(^)eW " ([a,b])
x(t i )=0, i=1v..,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 (n) (t) = u(t) как континуум равенств, каждое из которых надо умножить на множитель Лагранжа p(t), а затем их «просуммировать»:
L (x( * ),u( * ),A) = J \( — 5(t
— т ) + XX ^6(t — t i ))x(t) + p (t)(x (n) (t) — u(t)) dt. i=i
Здесь A = ( — 1,^ 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 (n) (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 (n) (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 (n) (t) dt 6 Г aa
| p (t) | dt.
Выше было показано, что p ( • ) не меняет знака на [a, b] и поэтому функция x ( n ) (^) (которая есть константа) совпадает с точностью до знака с signp ( • ). Подставим ж0 в (12) и учитывая, что ж(т) > 0, получим
Ь (т) =
/ p (t)X ( n) (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, то задача осмысленна и здесь оптимальным методом будет интерполяционный сплайн. Доказательство получается на том же пути, что и в рассмотренном случае, но нужно воспользоваться еще утверждениями о существовании разного рода сплайнов.
Список литературы Оптимальная интерполяция и принцип Лагранжа
- Алесеев В. М., Тихомиров В. М., Фомин С. В. Оптимальное управление.-М.: Наука, 1979.-429 с.
- Магарил-Ильяев Г. Г., Тихомиров В. М. Выпуклый анализ и его приложения.-М.: Эдиториал УРСС, 2003.-176 с.