ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ, 2007, том 47, < 9, с. 1512-1523
УДК 519.626
ПРИНЦИП ЛАГРАНЖА В ЗАДАЧЕ ОПТИМАЛЬНОГО ОБРАЩЕНИЯ ЛИНЕЙНЫХ ОПЕРАТОРОВ В КОНЕЧНОМЕРНЫХ ПРОСТРАНСТВАХ ПРИ НАЛИЧИИ АПРИОРНОЙ ИНФОРМАЦИИ О РЕШЕНИИ1
© 2007 г. А. В. Баев
(119992 Москва, Ленинские горы, МГУ, физ. ф-т) e-mail: andrewbayev@mail.ru Поступила в редакцию 22.12.2006 г.
Описано применение принципа Лагранжа для оптимального восстановления в задаче о решении систем линейных алгебраических уравнений. Описаны новые, оптимальные методы решения таких систем, использующие информацию о погрешности данных и априорную информацию о решении. Библ. 7.
Ключевые слова: оптимальное восстановление, система линейных алгебраических уравнений.
1. ВВЕДЕНИЕ
Любую обратную задачу можно представить в виде операторного уравнения Ax = b, где x - неизвестная характеристика рассматриваемой задачи, b - известная характеристика, A - известный оператор. Часто на практике эту задачу сводят к решению системы конечного числа уравнений с конечным числом неизвестных. Если оператор A линейный, то задача сводится к системе линейных алгебраических уравнений (СЛАУ) относительно конечномерного вектора. В данной работе исследована задача оптимального восстановления компонент этого вектора в случае, когда матрица и правая часть СЛАУ заданы с погрешностью и известны априорные ограничения на точное решение.
2. ПОСТАНОВКА ЗАДАЧИ И ОСНОВНЫЕ ТЕОРЕМЫ Задачу решения системы линейных алгебраических уравнений сформулируем в виде операторного уравнения. Пусть A : [ —» - линейный оператор. Рассмотрим выпуклое уравновешенное множествоMс [ и зафиксируем элемент y е A(M). Из вложения y е A(M) следует, что 3x е M: Ax = y. Рассмотрим следующую задачу решения СЛАУ с априорной информацией о решении:
Ax = y, x е M. (2.1)
Такая задача имеет решение (например, x = x). Пусть { et }г"= 1 с [ - "естественный" базис в [ и {gj} m= ic - "естественный" базис в Далее любой линейный оператор между пространствами [ и будем отождествлять с его матрицей относительно введенных базисов, векторы конечномерных пространств представлять в виде столбцов из координат в "естественных" базисах, а действие оператора на вектор представлять в виде произведения матрицы оператора на этот столбец. При этом k-ю координату конечномерного вектора x в "естественном" базисе будем обозначать через xk. Любой линейный функционал в конечномерном пространстве будем представлять вектором , из этого пространства, а действие функционала , на вектор x представлять в виде естественного скалярного произведения: ,(x) = (€, x). В практических задачах не всегда есть возможность оперировать с точными значениями элемента y и оператора A. Зададим
1)Работа выполнена при частичной финансовой поддержке РФФИ (код проекта 05-01-00049).
выпуклое уравновешенное множество Q с r™. Пусть в задаче (2.1) вместо элемента y известен
элемент v е r™ такой, что v- y е Q. Также будем считать, что известен не оператор A, а лишь его приближение - оператор B. Рассмотрим множество (см. [1])
© с r": © dQ + (A - B )(M).
Легко показать, что выполнено включение v - BX е ©. Всю информацию о погрешности задания оператора A и правой части y объединим в множество ©, которое будем называть окрестностью погрешности. Итак, считаем, что в задаче известны M, v, B и © такие, что X е M и v -BX е ©. В качестве ответа задачи можно требовать вектор из множества M, обладающий некоторыми свойствами близости к X. Задачу поиска «-мерного вектора можно разбить на n задач поиска одного числа: для всех q е {1, 2, ..., «} будем решать задачу оптимального восстановления линейного функционала eq (см. [1]-[3]). Сформулируем постановку задачи из этих работ.
Обозначение. Если X и Y - некоторые множества, то YX - множество всех отображений из X в Y.
Для удобства введем обозначенияX := rn, Y := r™. Пусть , е X*. Любую функцию ф : Y —» r будем называть методом восстановления функционала , на множестве Mпо информации (B, ©), а погрешностью метода восстановления ф будем называть величину
% (,, M, B, ©,ф) := sup |<,, x> - ф(y)|.
X е M, y е Y : y - Bx е ©
Величину
E(,, M, B, ©) := inf %(,, M, B, ©, ф)
фе R7
Y
назовем погрешностью оптимального восстановления, а любой ф е r , на котором достигается этот минимум, назовем методом оптимального восстановления. Если M и © уравновешены и выпуклы, то среди методов оптимального восстановления существует метод ф, который
линеен, т.е. ф е Y *. Этот факт для более общей постановки задачи доказан в [4] и [5]. Таким образом, inf в определении погрешности оптимального восстановления можно брать по множеству Y *. В дальнейшем задачи на поиск минимума и экстремалей будем записывать следующим образом:
f (X) —► min, P (x).
x
Подобная запись означает, что ищется минимум значения функционала f по аргументу x; на месте выражения P(x) будут стоять условия, задающие множество изменения аргумента x; решением такой задачи на экстремум будем считать элемент x, который удовлетворяет условию P(x) и на котором достигается минимум. Таким же образом будем записывать и задачи на поиск максимума. Задачу поиска метода оптимального восстановления функционала , на множестве M по информации (B, ©) будем ставить так же, как и в [1]:
sup |<,, x> - <ф,y>| — min, фе Y*. (2.2)
X е M, ф
y е Y : y - Bx е ©
В этой задаче будем искать погрешность E(,, M, B, ©) и метод ф оптимального восстановления. Их интерпретация такова: приближением для числа <€, X > считается число <ф, v>, а погрешностью этого приближения считается E(,, M, B, ©).
Сопоставим задаче (2.2) другую экстремальную задачу, которую назовем ассоциированной к (2.2) (см. [2]):
<,, x> —► max, (x, y)е XX Y, x е M, y - Bx е ©, y = 0. (2.3)
(X, y)
Из результатов [2] следует
Теорема 1. Пусть Xи Y- действительные конечномерные линейные пространства, Mс Xи © с Y выпуклы и уравновешены, , е X*, оператор В : X —- Y линейный. Определим функцию Лагранжа x : (X х Y) х Y* —- r:
х((х, у),А) = - <, х> + a у>. (2.4)
Если элемент (х, 0) е X х Y является допустимой точкой в задаче (2.3) (т.е. х е M и - Bx е ©), тогда верно следующее:
1) два условия эквивалентны:
а) (X, 0) является решением задачи (2.3),
б) ЗА е Y * : x(( X, 0), А) = inf x ((х, у), А);
х е M, у е Y : у - Вх е ©
2) при выполнении этих двух эквивалентных условий ф = А является методом оптимального восстановления в задаче (2.2) и его погрешность (т.е. значение минимума в задаче (2.2)) такова:
E (,, M, В, ©) = <,, х>= -x(( х, 0 ),А).
Далее всюду будем считать, что множество © выпукло и уравновешено, а решение ассоциированной задачи (2.3) существует. Пусть (х, 0) - одно из решений. Функцию Лагранжа (2.4) для задачи (2.2) можно рассматривать как линейный функционал (-€, А) в пространстве i х irm:
<(А), (х,у)> := <х> + <А,у> = x((х,у), А). Задача минимизации функции Лагранжа выглядит так:
<х > = inf <(-,,А),(х, у )>. (2.5)
х е M,
m
у е R : у - Вх е ©
После простых преобразований задача минимизации (2.5) примет вид такой задачи максимизации:
0= sup (<(,, -А),(х,у)> - <,, х>),
х е M,
m
у е R : у - Вх е ©
что эквивалентно выполнению неравенства
<(,, -А),(х,у) - (х, 0)>< 0 (2.6)
V(х, у) е r" х rm : х е M, у - Вх е ©. (2.7)
Мы получили, что задача минимизации функции Лагранжа приобрела вид задачи решения вариационного неравенства. Но отличие состоит в том, что экстремаль задачи нам известна (это элемент (х, у) = (х, 0)), а найти требуется функционал (,, - А), для которого выполнено неравенство (2.6) на множестве, заданном условием (2.7). Теорема 1 обосновывает следующий алгоритм поиска:
1) находим (х, 0) - решение задачи (2.3);
2) ищем множитель Лагранжа А, при котором функция Лагранжа (2.4) достигает минимума на (х, 0), т.е. ищем такое А, что выполнено (2.6), (2.7);
3) ответ в задаче будет такой: А - метод оптимального восстановления, <€, х > - его погрешность.
Докажем вспомогательные утверждения.
Теорема 2. Пусть X и Y- конечномерные действительные линейные пространства, , е X*, Mс X и © с Y выпуклы и уравновешены, В : X —► Y - линейный оператор. Для этих объектов
рассмотрим задачу (2.2). Пусть ^ - функция Лагранжа для этой задачи, (x, 0) - решение задачи (2.3), А - множитель Лагранжа, существование которого утверждает теорема 1 , ^0 : X X X Y* —► [, ^0(x, А) d=f -(,, x) + (А, Bx). Тогда справедливы следующие утверждения:
1) ^0(x, А) = ^((x, Bx), А) Vx е X, VA е Y*;
2) E(,, M, B, о) = - inf ^о (x, А) + sup (А, w) , inf ^о(x, А) достигается на x;
x е M w е О x е M
3) (А, bx) = sup (А, w), bx е о.
w е О
Доказательство. 1. Равенство ^0(x, А) = ^((x, Bx), А) следует из определений и
2. По теореме 1, имеем
E(,, M, B, о) = ( ,, x) = - inf ^ ((x, y ),А) = - inf inf x, y ),А),
x е M, x е My е Y:
y е Y : y - Bx е О y - Bx е О
и по той же теореме левый inf достигается на элементе (x, y) = (x, 0), т.е. внешний inf в правой части достигается на элементе x = x. Преобразуем выражение
inf £((x,y),A), = inf £((x, Bx + w),А) = inf (-(,, x) + (А, Bx + w)) =
y е Y: w е Y: w е О
y - Bx е О w е О
= -(,, x) + (А, Bx) + inf (А, w) = ^0(x, А) + inf (А, w).
w е О w е О
Так как о уравновешено, то
inf (А, w) = -sup (- (А, w)) = -sup (А, -w) = -sup (А, w).
w е О w е О w е О w е О
Итак, получаем, что
E (,, M, B, о) = - inf ((x,A) -sup (А, w)) = - inf (x, А) + sup (А, w),
x е M w е О x е M w е О
и все минимумы в этих равенствах достигаются на x = x. Утверждения п. 2 этой теоремы доказаны.
3. Пусть (x, 0) - решение задачи (2.3), поэтому - Bx е о. Из уравновешенности множества о получим Bx е о. Из предыдущего пункта этой теоремы следует, что
(,, x) = E(,, M, B, о) = - inf (x, А) + sup (А, w) =
x е M w е О
= (x, А) + sup (А, w) = (,, x) - (А, Bx) + sup (А, w).
w е О w е О
Из этого равенства следует утверждение п. 3 этой теоремы.
Теорема 3. Пусть J и Ъ - множества из конечного числа элементов, X- действительное конечномерное линейное пространство, {ac}c е Ъ сX- конечный набор ненулевых векторов. Для любого а е J введем действительное конечномерное линейное пространство Ya и линейный оператор Ga : X —- Ya. Рассмотр
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.