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

Автор: Магарил-Ильяев Георгий Георгиевич

Журнал: Владикавказский математический журнал @vmj-ru

Статья в выпуске: 4 т.6, 2004 года.

Бесплатный доступ

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

Короткий адрес: https://sciup.org/14318128

IDR: 14318128

Текст научной статьи Оптимальная интерполяция и принцип Лагранжа



6_4.dvi

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

Октябрь–декабрь, 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 . Другими словами, в качестве метода восстановления х(т ) мы рассматриваем линейную функцию 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 с.
Статья научная