ВВЕДЕНИЕ
Среди математических задач выделяется класс задач, решения которых
неустойчивы к малым изменениям исходных данных. Они характеризуются тем,
что сколь угодно малые изменения исходных данных могут приводить к
произвольно большим изменениям решений. Задачи подобного типа, по
существу, являются плохо поставленными. Они принадлежат к классу
некорректно поставленных задач.
Быстро растущее использование вычислительной техники требует развития
вычислительных алгоритмов для решения широких классов задач. Но что надо
понимать под «решением» задачи? Каким требованиям должны удовлетворять
алгоритмы нахождения « решений »?
Классические концепции и постановки задач не отражают многих
особенностей встречающихся на практике задач. Мы покажем это на примере.
Рассмотрим систему линейных алгебраических уравнений
Az=u,
где z — искомый вектор, и — известный вектор, А ={aij} — квадратная
матрица с элементами aij.
Если система невырожденная, т. е. detA ? 0, то она имеет единственное
решение, которое можно найти по известным формулам Крамера или другими
способами.
Если система вырожденная, то она имеет решение (притом не единственное)
лишь при выполнении условий разрешимости, состоящих из равенств нулю со-
ответствующих определителей.
Таким образом, прежде чем решить систему, надо проверить, вырожденная
она или нет. Для этого требуется вычислить определитель системы detA.
Если п — порядок системы, то для вычисления detА требуется выполнить
около п3 операций. С какой бы точностью мы ни производили вычисления,
при достаточно большом значении п, вследствие накопления ошибок
вычисления, мы можем получить значение detА, как угодно отличающееся от
истинного. Поэтому желательно иметь (построить) такие алгоритмы
нахождения решения системы, которые не требуют предварительного
выяснения вырожденности или невырожденности системы.
Кроме того, в практических задачах часто правая часть u и элементы
матрицы А,
т. е. коэффициенты системы уравнений, известны нам приближенно. В этих
случаях вместо системы, мы имеем дело с некоторой другой системой
A1z=u1 такой, что
||А1— А|| О можно указать такое число ? (?) > 0, что из неравенства
?U(u1,u2) 0, что для всякого ? > 0 найдется элемент и1 из Uo, для
которого ?U(и1, и0) , в то время как ?F(z1,z0)>=??1. Здесь z=?(u1),
z0=?(u0) и z1?Fo, z0?F0.
Возьмем последовательность {?n} положительных чисел ?n , сходящуюся к
нулю при п??. Для каждого ?n найдется элемент un1 из Uo, для которого
?U(иn1, и0)=??1 , где zn1=?(un1). Очевидно,
последовательность {un1} сходится к элементу u0. Так как zn1 принадлежат
компактному на F множеству Fo, то из последовательности {zn1} можно
выбрать подпоследовательность {Z1nk}, сходящуюся по метрике F к
некоторому элементу z0 ?F. При этом z01?z0 , так как для всякого nk
?F(Z1nk,z0)>=??1 , следовательно и ?F(z10,z0)>=??1 . Этой
подпоследовательности {Z1nk} отвечает последовательность элементов
u1nk=?? (Z1nk) из Uo, сходящаяся к u10=??(z10) и являющаяся
подпоследовательностью последовательности {u1n}. Так как
последовательность {u1n} сходится к и0 =?(z0), то u10=?(z10)=u0=?(z0) ,
т. е. ?(z0)=??(z10). В силу взаимной однозначности отображения F?U
z10=z0, что противоречит ранее установленному неравенству z10?z0. Лемма
доказана.
Эту лемму можно сформулировать короче.
Если отображение Fo(Uo компакта Fo на множество Uo взаимно однозначно и
непрерывно, то обратное отображение Uo(Fo также непрерывно.
Эквивалентность этих формулировок следует из того, что замыкание F*0
множества Fo, компактного на F, является компактом.
Таким образом, минимизирующая последовательность {zn} в методе подбора
сходится к zT при n(?, если:
а)zT принадлежит классу возможных решений М;
б) множество М — компакт.
Пусть оператор А непрерывен и вместо точной правой части uT мы имеем
элемент u? такой, что ?U(u?,uT )=?2>=…>=?n>=… — полная система его
собственных значений, a ?1,??2,…,??n,…—отвечающая им полная
ортонормированная система его собственных элементов (функций, векторов).
Элемент А*и можно представить в виде ряда
(2;2,2)
В этих условиях справедлива
Теорема 3. Квазирешение уравнения (2, 0,1) на множестве SR выражается
формулами:
(2;2,3)
если
(2;2,4)
и
если
(2;2,5)
Здесь ? — корень уравнения
(2;2,6)
Доказательство. Квазирсшение минимизирует функционал
??????????????????????????????????????????U2 (Az, u) == (Az — u, Az — u)
(2;2,7)
(где (v,w ) — скалярное произведение элементов v и w из U), уравнение
Эйлера для которого имеет вид
A*Az=A*u.
(2;2,8)
Решение этого уравнения будем искать в виде ряда по системе {?n}:
(2;2,9)
Подставляя этот ряд в уравнение (2; 2,8) и используя разложение (2;2,2),
находим сn=bn/?n. Следовательно, неравенство (2; 2,4) означает, что
||z||
и надо решать задачу на условные экстремум функционала (2; 2,7) при
условии, что || z ||2 = R2. Методом неопределенных множителей Лагранжа
эта задача сводится к нахождению безусловного экстремума функционала
(Аz-u, Аz-u) + ? (z, z),
а последняя — к решению отвечающего ему уравнения Эйлера A*Az+?z=А*и.
Подставляя сюда z в виде ряда (2; 2,9) и используя разложение (2; 2,2),
находим
Параметр ? определяем из условия || z ||2 = R2 , которое эквивалентно
(2; 2,6).
2.3. Приближенное нахождение квазирешений
В предыдущем параграфе мы видели, что нахождение квазирешения связано с
нахождением элемента в бесконечномерном пространстве. Для приближенного
нахождения квазирешения естественно переходить к конечномерному
пространству. Можно указать достаточно общий подход к приближенному
нахождению квазирешений уравнения (2; 0,1) , в котором А—вполне
непрерывный оператор.
Будем полагать, что выполнены указанные в 2.2. достаточные условия
существования единственного квазирешения на заданном множестве М, т. е.
полагаем, что множество М — выпуклый компакт и сфера в пространстве U
строго выпукла. Пусть
M1 ??M????????Mn ????
совпадает с М. Квазирешение уравнения (2; 0,1) существует на каждом
множестве Мn . Но оно может быть не единственным. Обозначим через Тn
совокупность всех квазирешений на множестве Мn .
Покажем, что в качестве приближения к квазирешению z1 на множестве М
можно брать любой элемент z1n из Тn . При этом
Пусть Nn = АМn и Вn — множество проекций элемента и на множество Nn .
Очевидно, что Вn = АТn и N1 ? N2 ? …? Nn; тогда
? U(u,N1)>= …>=? U (u,Nn)>=… ? U (u,N)= ? U (u,Az1) .
(2;3,1)
всюду плотно на N, то для всякого ? >0 найдется такое число n0(?), что
для всех п >n0(?)
?U(u,Nn)?U(u,N)+??
(2; 3,2)
Из (2; 3,1) и (2; 3,2) следует, что
(2;3,3)
Поскольку
то
(2;3,4)
Каждое множество Вn есть компакт, так как оно является замкнутым
подмножеством компакта Nn. Поэтому в Вn найдется такой элемент уn , что
?U(yn ,u) = inf ?U(y,u)
y?Bn
Последовательность {yn} имеет хотя бы одну предельную точку,
принадлежащую N, так как N — компакт. Пусть у0 — какая-нибудь предельная
точка множества {yn} и {уnk} — подпоследовательность, сходящаяся к y0 ,
т. е.
Из (2; 3,3) и (2; 3,4) следует, что
Таким образом,
?U(u,y0)=??U(u,N).
Отсюда и из единственности квазирешения на множестве М следует, что
y0=Az1.
Так как у0 — произвольная предельная точка множества {yn}, то
последовательность {уn} сходится к Аz1. Это и означает, что в качестве
приближения к квазирешению можно брать любой элемент z1n из множества Тп
, так как в силу леммы параграфа 2.1. z1n(z* при n(?.
Если в качестве Мп брать конечномерные (n-мерные) множества, то задача
нахождения приближенного квазирешения на компакте М сводится к
минимизации функционала ?U(Az, u) на множестве Мп , т. е. к нахождению
минимума функции п переменных.
2.4. Замена уравнения Аz=u близким ему
Уравнения вида (2; 0,1), в которых правая часть u не принадлежит
множеству N=AM, изучались М. М. Лаврентьевым . Ему принадлежит идея
замены исходного уравнения (2; 0,1) близким ему, в некотором смысле,
уравнением, для которого задача нахождения решения устойчива к малым
изменениям правой части и разрешима для любой правой части u??U. В
простейшем случае это делается следующим образом.
Пусть F??U??Н — гильбертовы пространства, А — линейный, ограниченный,
положительный и самосопряженный оператор, SR ? {х, ||x|| 0. В качестве класса корректности М
берется множество DR=BSR — образ шара SR при отображении с помощью
оператора В. Предполагается, что искомое точное решение zT уравнения (2;
0,1) с правой частью u=uT существует и принадлежит множеству DR.
Уравнение (2; 0,1) заменяется уравнением
(A+?E)z ? Az+?z=u ,
(2:4,1)
где ?>0 – числовой параметр. Решение уравнения
z?=(A+?E)-1u ,
(2; 4,2)
при соответствующем выборе параметра ?, принимается за приближенное
решение уравнения (2; 0,1). Здесь Е — единичный оператор.
Замечание. Для оценки уклонения ?F(zT,z?) приближенного решения от
точного можно использовать модуль непрерывности ? обратного оператора на
N.
Пусть u1, u2 ? N и ?U(u1,u2) 0}, удовлетворяющего граничным условиям
u(х, t) =0 при x?S
(2; 5,2)
и начальным условиям
u(x, 0)=??(x).
(2; 5,3)
Здесь
Известно, что решение такой задачи существует. Каждой функции ?(x)?C
отвечает решение задачи (2; 5,1)— (2; 5,3). Будем обозначать его через
u(х, t;??).
Обратная задача состоит в нахождении функции ?(х) по известной функции
u(х,t;??). В реальных задачах функция u(x,t;?) обычно получается в
результате измерений и, следовательно, известна приближенно. Будем
полагать, что u?L2. Такая функция может и не соответствовать никакой
«начальной» функции ?(х). Таким образом, может не существовать в классе
функций С решения обратной задачи. Поэтому будем рассматривать задачу
нахождения некоторого обобщенного решения обратной задачи.
Пусть заданы число T > 0 и функция ?(x), определенная в области D,
?(x)??L2. На функциях ?(х) класса С определен функционал
Обобщенным решением обратной задачи будем называть функцию ?(х)., на
которой достигается
f0=inf
f(?)
??C
Замечание. «Естественный» подход к решению этой задачи — выбрать функцию
?(х).так, чтобы f(?)=0 .
Для этого достаточно найти решение прямой задачи
u(x, t) = 0 для х ? S, 0 0 найти функцию ??(x), на которой f (??) 0;
u? (x,T)=??(x);
u? (x,t) = 0 для x? S, t0;
u? (x,T)=??(x);
u? (x,t) = 0 для x? S, 0 0 такие, что
?U(u?,uT) 0, что оператор R(u, ?) определен для
всякого ?, 0 0 существует ?0=?0(?, u?)0,??1>0, что оператор R(u,?? ) определен
для всякого ?, принадлежащего промежутку (0,??1), и любого u?U, для
которого
?U(u,uT) 0 найдется число
?(?)0 множество F1,d элементов z из F1 , для которых
?[ z ](3; 3,2) Аz = u. Требуется найти приближение z? к нормальному решению системы (3;3,1), т. е. к вектору z° такое, что z? (z° при ? (0. Отметим, что векторы u и u (один из них или оба) могут не удовлетворять классическому условию разрешимости. Поскольку система (3; 3,1) может быть неразрешимой, то inf ||Az-u|| = ? >=0, где inf берется по всем векторам z ? Rn.
Естественно искать приближения z? в классе Q? векторов z, сопоставимых
по точности с исходными данными, т. е. таких, что || Az – u || 0;
2) при ? (0 z?== R1(u,??) стремится к нормальному решению z° уравнения
Аz=u, т. е. он является регуляризирующим для уравнения Аz=u .
3.3.3. Пусть ?z? — вектор, на котором функционал ?[ z ] = ||z||2
достигает минимума на множестве Q?. Легко видеть из наглядных
геометрических представлений, что вектор z? лежит на границе множества
Q?, т.е. ||Az? – u ||=? +2? =?1.
Это следует непосредственно также из того, что функционал ?[ z ] =
||z||2 является сстабилизирующим и квазимонотонным. Стабилизирующий
функционал ?[ z ] называется квазимонотонным , если каков бы ни был
элемент z из F1 , не принадлежащий множеству M0 , в любой его
окрестности найдется элемент z1 из F1, для которого ?[ z1 ]?[ z ],
т.е. если функционал не имеет локальных минимумов на множестве F1\ M0.
Задачу нахождения вектора z? можно поставить так: среди векторов z,
удовлетворяющих условию ||Az – u ||=? +2? , найти вектор z? с
минимальной нормой, т. е. минимизирующий функционал ?[ z ]=||z||2.
Последнюю задачу можно решать методом Лагранжа, т. е. в качестве z?
брать вектор z?, минимизирующий функционал
М? [z, u] = ||Az - u ||2+??||z||2, ?>0,
с параметром ?, определяемым по невязке, т. е. из условия ||Аz?— u||=?1.
При этом параметр ? определяется однозначно .
3.3.4. Поскольку М? [z, u] — квадратичный функционал, то для любых
u??Rm и ?> 0 существует лишь один минимизирующий его вектор z?. В самом
деле, допустим,
что существуют два вектора z? и z?, минимизирующие его. Рассмотрим
векторы z, расположенные на прямой (пространства Rn), соединяющей z? и
z?:
z = z? + ?(?z? – z?).
Функционал М? [z, u] на элементах этой прямой есть неотрицательная
квадратичная функция от ?. Следовательно, она не может достигать
наименьшего значения при двух различных значениях ?: ? = 0 (z = z?) и
?=1 (z = z?).
Компоненты zj? вектора z? являются решением системы линейных
алгебраических уравнений
получающихся из условий минимума функционала М? [z, u]:
Здесь
Компоненты zj? могут быть определены и с помощью какого-нибудь другого
алгоритма минимизации функционала М? [z, u].
Вектор z? можно рассматривать как результат применения к u некоторого
оператора z?=R(u, ?), зависящего от параметра ?.
Покажем, что оператор R0(u, ?) является регуляризирующим для системы
(3;3,1), т. е. обладает свойствами 1) и 2) определения 2 (см. 3.1.2.). В
п. 3.3.2. было сказано, что он определен для всяких u??Rm и ? > О и,
следовательно, обладает свойством 1). Теперь покажем справедливость
свойства 2), т. е. существование таких функций ?=???? , что векторы
z???? = R0(u, ????) сходятся к нормальному решению z° системы (3; 3,1)
при ?(0. Это непосредственно следует из приводимой ниже теоремы 2.
Теорема 2( Тихонова). Пусть z° есть нормальное решение системы Az= u и
вместо вектора u мы имеем вектор u такой, что ||u—u||
Нашли опечатку? Выделите и нажмите CTRL+Enter
