Методы решения некорректно поставленных задач
Среди математических задач выделяется класс задач, решения которых неустойчивы к малым изменениям исходных данных. Они характеризуются тем, что сколь угодно малые изменения исходных данных могут приводить к произвольно большим изменениям решений. Задачи подобного типа, по существу, являются плохо поставленными. Они принадлежат к классу некорректно поставленных задач.
Быстро растущее использование вычислительной техники требует развития вычислительных алгоритмов для решения широких классов задач. Но что надо понимать под ВлрешениемВ» задачи? Каким требованиям должны удовлетворять алгоритмы нахождения Вл решений В»?
Классические концепции и постановки задач не отражают многих особенностей встречающихся на практике задач. Мы покажем это на примере.
Рассмотрим систему линейных алгебраических уравнений
Az=u,
где z тАФ искомый вектор, и тАФ известный вектор, А ={aij} тАФ квадратная матрица с элементами aij.
Если система невырожденная, т. е. detA ¹ 0, то она имеет единственное решение, которое можно найти по известным формулам Крамера или другими способами.
Если система вырожденная, то она имеет решение (притом не единственное) лишь при выполнении условий разрешимости, состоящих из равенств нулю со- ответствующих определителей.
Таким образом, прежде чем решить систему, надо проверить, вырожденная она или нет. Для этого требуется вычислить определитель системы detA.
Если п тАФ порядок системы, то для вычисления detА требуется выполнить около п3 операций. С какой бы точностью мы ни производили вычисления, при достаточно большом значении п, вследствие накопления ошибок вычисления, мы можем получить значение detА, как угодно отличающееся от истинного. Поэтому желательно иметь (построить) такие алгоритмы нахождения решения системы, которые не требуют предварительного выяснения вырожденности или невырожденности системы.
Кроме того, в практических задачах часто правая часть u и элементы матрицы А,
т. е. коэффициенты системы уравнений, известны нам приближенно. В этих случаях вместо системы, мы имеем дело с некоторой другой системой A1z=u1 такой, что
||А1тАФ А||<=h, ||u1-u||<=d, где смысл норм обычно определяется характером задачи. Имея вместо матрицы А матрицу А1, мы тем более не можем высказать определенного суждения о вырожденности или невырожденности системы.
В этих случаях о точной системе Az = и нам известно лишь то, что для матрицы А и правой части и выполняются неравенства || А1тАФА || <= h и || и1тАФи <=d. Но систем с такими исходными данными (А, и) бесконечно много, и в рамках известного нам уровня погрешности они неразличимы. Среди таких Влвозможных точных системВ» могут быть и вырожденные.
Поскольку вместо точной системы мы имеем приближенную систему A1z=и1, то речь может идти лишь о нахождении приближенного решения. Но приближенная система может быть и неразрешимой. Возникает вопрос: что надо понимать под приближенным решением системы? Оно должно быть также устойчивым к малым изменениям исходных данных (А, и).
В данной работе будет введено понятие приближенного решения некорректно поставленных задач, а также будет рассмотрено несколько методов нахождения таких решений.
1. ПОНЯТИЕ КОРРЕКТНО ПОСТАВЛЕННЫХ И НЕКОРРЕКТНО ПОСТАВЛЕННЫХ ЗАДАЧ
1.1. Различают корректно поставленные, и некорректно поставленные задачи. Понятие корректной постановки задач математической физики было введено
Ж. Адамаром в связи с желанием выяснить, какие типы граничных условий наиболее естественны для различных типов дифференциальных уравнений (для эллиптических, например,тАФ задача Дирихле и ей аналогичные, для гиперболических тАФ задача Коши).
Решение всякой количественной задачи обычно заключается в нахождении ВлрешенияВ» z по заданным Влисходным даннымВ» и, z=R(u). Мы будем считать их эле- ментами метрических пространств F и U с расстояниями между элементами 
; u1, u2ÎU; z1,z2ÎF. Метрика обычно определяется постановкой задачи.
1.2. Пусть определено понятие ВлрешенияВ» и каждому элементу иÎU отвечает единственное решение z=R(u) из пространства F.
Задача определения решения z=R(u) из пространВнства F по исходным данным
иÎU называется устойчивой на пространствах (F, U), если для любого числа e > О можно указать такое число d (e) > 0, что из неравенства rU(u1,u2)<= d (e) следует rF(z1,z2)<= e, где z1=R(u1),z2=R(u2); u1,u2ÎU; z1,z2ÎF.
Задача определения решения z из пространства F по Влисходным даннымВ» и из пространства U называется корректно поставленной на паре метрических простВнранств (F, U), если удовлетворяются требования (услоВнвия):
1) для всякого элемента и ÎU существует решение z из пространства F,
2) решение определяется однозначно;
3) задача устойчива на пространствах (F, U). В математической литературе длительное время суВнществовала точка зрения, согласно которой всякая маВнтематическая задача должна удовлетворять этим требоВнваниям .
Задачи, не удовлетворяющие перечисленным требоваВнниям, называются некорректно поставленными.
Следует отметить, что определение некорректно поВнставленных задач относится к данной паре метриВнческих пространств (F, U), так как в других метриках та же задача может быть корректно поставленной .
1.3. Задача нахождения приближенного решения неВнкорректно поставленной задачи вида
Az = и, иÎ U, (1; 3,1)
в естественном классе элементов F является практически недоопределенной. Эта задача является некорректно поставленной, например, в случаях, когда А тАФ вполне непрерывный оператор. Тогда обратВнный ему оператор A-1 вообще говоря, не будет непрерывным на U и решение уравнения (1; 3,1) не будет устойчивым к малым изменениям правой части и (в метрике пространства U). ИсходВнными данными здесь являются правая часть уравнения u и оператор А.
Предположим, что оператор А нам известен точно, а правая часть уравнения (1; 3,1) известна с точностью d, т. е. вместо ее точного значения uT нам известны элемент и1 и число d такие, что rU(uT,u1)<= d. По этим данным, т. е. по (u1, d), требуется найти такой элемент zd , коВнторый стремился бы (в метрике F) к zT при dВо0. ТаВнкой элемент мы будем называть приближенным (к zT) решением уравнения Az = и1.
Элементы zÎF, удовлетворяющие условию rU(Az, и1)<= d, будем называть сопоставимыми по точности с исВнходными данными (и1, d). Пусть QdтАФсовокупность всех таких элементов z ÎF. Естественно приближенные реВншения уравнения Az=и1 искать в классе Qd элементов z, сопоставимых по точности с исходными данными
(и1, d ).
Однако в ряде случаев этот класс элементов слишком широк. Среди этих элементов есть такие, которые могут сильно отличаться друг от друга ( в метрике пространства F ). Поэтому не все элементы класса Qdможно брать в качестве приближенного решения уравнения (1;3,1).
2. МЕТОД ПОДБОРА. КВАЗИРЕШЕНИЯ
Возможность определения приближенных решений некорректно поставленных задач, устойчивых к малым изменениям исходных данных, основывается на испольВнзовании дополнительной информации относительно решеВнния. Возможны различные типы дополнительной инфорВнмации.
В первой категории случаев дополнительная инфорВнмация, носящая количественный характер, позволяет сузить класс возможных решений, например, до комВнпактного множества, и задача становится устойчивой к малым изменениям исходных данных. Во второй категоВнрии случаев для нахождения приближенных решений, устойчивых к малым изменениям исходных данных, исВнпользуется лишь качественная информация о решения (например, информация о характере его гладкости).
В настоящей главе будет рассмотрен метод подбора, имеющий широкое практическое применение, метод квазирешения, а также метод замены исходного уравнеВнния близким ему и метод квазиобращения. В качестве некорректно поставленной задачи мы будем рассматриВнвать задачу решения уравнения
Az=u (2; 0,1)
относительно z, где uÎU, zÎF, U и FтАФметрические пространства. Оператор А отображает F на U. ПредпоВнлагается, что существует обратный оператор А-1, но он не является, вообще говоря, непрерывным.
Уравнение (2; 0,1) с оператором А, обладающим укаВнзанными свойствами, будем называть операторным уравВннением первого рода, или, короче,тАФ уравнением перВнвого рода.
2.1. Метод подбора решения некорректно поставленных задач
2.1.1. Широко распространенным в вычислительной практике способом приближенного решения уравнения (2; 0,1) является метод подбора. Он состоит в том, что для элементов z некоторого заранее заданного подкласВнса возможных решений М (МÎF) вычисляется операВнтор Az, т. е. решается прямая задача. В качестве приВнближенного решения берется такой элемент z0 из мноВнжества М, на котором невязка rU(Az,u) достигает миниВнмума, т. е.
rU(Az0,u)=inf rU(Az,u)
zÎM
Пусть правая часть уравнения (2;0,1) известна точВнно, т. е. и=uT, и требуется найти его решение zT. Обычно в качестве М берется множество элементов z, зависящих от конечного числа параметров, меняющихся в ограниченных пределах так, чтобы М было замкнутым множеством конечномерного пространства. Если искомое точное решение zT уравнения (2; 0,1) принадлежит мноВнжеству М, то 
и достигается эта нижняя граница на точном решении zT. Если уравнение (2;0,1) имеет единственное решение, то элемент z0, минимизирующий rU(Az,и), определен однозначно.
Практически минимизация невязки rU(Az,и) произВнводится приближенно и возникает следующий важный вопрос об эффективности метода подбора, т. е. о возможВнности как угодно приблизиться к искомому точному реВншению.
Пусть {zn} тАФ последовательность элементов, для коВнторой rU(Azn,u) Во0 при nВо¥. При каких условиях можно утверждать, что при этом и rF(zn,zT) Во0, т. е. что {zn} сходится к zT?
Это вопрос обоснования эффективности метода подбора.
2.1.2. Стремление обосновать успешность метода подбора привело к установлению общефункциональных требоваВнний, ограничивающих класс возможных решений М, при которых метод подбора является устойчивым и znВоzT. Эти требования заключаются в компактности мноВнжества М и основываются на приводимой ниже известВнной топологической лемме.
Лемма. Пусть метрическое пространство F отобраВнжается на метрическое пространство U и Uo тАФ образ мноВнжества Fo, FoÌ F, при этом отображении. Если отобраВнжение FВоU непрерывно, взаимно однозначно и множестВнво Fo компактно на F, то обратное отображение UoВоFo множества Uo на множество Fo также непрерывно по метВнрике пространства F.
Доказательство. Пусть z тАФ элементы множества F (zÎF), а uтАФэлементы множества U (uÎU). Пусть функция u=j(z) осуществляет прямое отображение FВоU, а функция z=y(u)тАФобратное отображение UВоF.
Возьмем произвольный элемент u0 из Uo. Покажем, что функция y(u) непрерывна на u0. Предположим, что это неверно. Тогда существует такое число e1 > 0, что для всякого d > 0 найдется элемент и1 из Uo, для которого rU(и1, и0) <d, в то время как rF(z1,z0)>= e1. Здесь z=y(u1), z0=y(u0) и z1ÎFo, z0ÎF0.
Возьмем последовательность {dn} положительных чиВнсел dn , сходящуюся к нулю при пВо¥. Для каждого dn найдется элемент un1 из Uo, для которого rU(иn1, и0)<dn , но rF(zn1,z0)>= e1 , где zn1=y(un1). Очевидно, последоваВнтельность {un1} сходится к элементу u0. Так как zn1 приВннадлежат компактному на F множеству Fo, то из послеВндовательности {zn1} можно выбрать подпоследовательность {Z1nk}, сходящуюся по метрике F к некоторому элементу z0 ÎF. При этом z01¹z0 , так как для всякого nkrF(Z1nk,z0)>= e1 , следовательно и rF(z10,z0)>= e1 . Этой подпоследовательности {Z1nk} отвечает последовательВнность элементов u1nk= j (Z1nk) из Uo, сходящаяся к u10= j(z10) и являющаяся подпоследовательностью поВнследовательности {u1n}. Так как последовательность {u1n}сходится к и0 =j(z0), то u10=j(z10)=u0=j(z0) , т. е. j(z0)= j(z10). В силу взаимной однозначности отобВнражения FВоU z10=z0, что противоречит ранее установВнленному неравенству z10¹z0. Лемма доказана.
Эту лемму можно сформулировать короче.
Если отображение FoàUo компакта Fo на множество Uo взаимно однозначно и непрерывно, то обратное отобраВнжение UoàFo также непрерывно.
Эквивалентность этих формулировок следует из того, что замыкание F*0 множества Fo, компактного на F, являВнется компактом.
Таким образом, минимизирующая последовательность {zn} в методе подбора сходится к zT при nà¥, если:
а)zT принадлежит классу возможных решений М;
б) множество М тАФ компакт.
Пусть оператор А непрерывен и вместо точной правой части uT мы имеем элемент ud такой, что rU(ud,uT )<= d, причем ud принадлежит множеству AM (образу множестВнва М при отображении его с помощью оператора A) и М есть компакт. Пусть {dn} тАФ последовательность полоВнжительных чисел таких, что dn à0 при nàоо. Для кажВндого п методом подбора можно найти такой элемент zdn , что rU(A zdn ,ud)<=dn . Элементы zdn будут близки к реВншению zT уравнения Az=uT. В самом деле, при отобраВнжении с помощью непрерывного оператора образ AM компакта М есть компакт и, следовательно, по лемме обратное отображение, осуществляемое оператором A-1, непрерывно на AM. Так как
rU(A zdn ,u)<= rU(A zn ,ud)+rU(ud,uT),
то
rU(A zdn ,uT)<=dn+d=gdn.
Из этого неравенства и из непрерывности обратного отображения АМà М следует, что rF(zdn ,zT)<= e(gdn) , причем e(gdn)à0 при gdnà0. Таким образом, при нахожВндении приближения zdn к zT надо учитывать уровень поВнгрешности d правой части ud.
2.1.3. На основе изложенных соображений М. М. ЛавВнрентьев сформулировал понятие корректности по Тихонову. В применении к уравнению (2; 0,1) задача наВнзывается корректной по Тихонову, если известно, что для точного значения u=uT существует единственное решеВнние zT уравнения (2; 0,1), AzT=uT, принадлежащее заВнданному компакту М. В этом случае оператор А-1 непреВнрывен на множестве N=AM и, если вместо элемента uT нам известен элемент ud такой, что rU( uT, ud)<=d и udÎN, то в качестве приближенного решения уравнения (2; 0,1) с правой частью u= ud можно взять элемент zd=A-1ud. При dà0 (udÎN) zd будет стремиться к zT. Множество F1 (F1 Ì F), на котором задача нахождения решения уравнения (2; 0,1) является корректно поставВнленной, называют классом корректности. Так, если операВнтор А непрерывен и осуществляет взаимно однозначное отображение, то компакт М, к которому принадлежит zT, является классом корректности для уравнения (2; 0,1). Таким образом, если задача (2; 0,1) корректна по ТихоВннову и правая часть уравнения uÎAM, то метод подбора с успехом может быть применен к решению такой задачи. На первый вопрос дан исчерпывающий ответ.
Рассмотрим задачу решения интегрального уравнения Фредгольма первого рода
(2;1,1)
на множестве М1 монотонно убывающих (возрастающих) и равномерно ограниченных функций |z(s)|<=B. Она корректна по Тихонову, так как множество M1 тАФ компакт в пространстве L2.
Действительно, возьмем любую последовательность E= {z1(s), z2(s), .. zn(s), ..} из M1. Согласно теореме Хелли о выборе существуют подпоследовательность
E1 = {Zn1 (s), Zn2 (s), .., Znk (s), ..},
последовательности Е и функция z*(s) из множества M1, z*(s) ÎL2, такие, что
всюду, кроме, может быть, счетного множества точек разрыва функции z*(s). Из поточечной сходимости подВнпоследовательности Е1 к функции z*(s) всюду, кроме, может быть, счетного множества точек, следует, как известно, сходимость подпоследовательности E1 к функВнции z*(s) по метрике L2.
Таким образом, в качестве приближенного решения на множестве М1 уравнения (2; 1,1) с приближенно известВнной правой частью u1 Î АМ1 можно брать точное решение этого уравнения с правой частью u=u1 . Эта последВнняя задача эквивалентна задаче нахождеВнния на множестве M1 функции, минимизирующей функВнционал
N[z,u1]=|| A1z тАУ u1 ||2L2 .
Пусть rU(uT, u1)<= d. Тогда, очевидно, в качестве приВнближенного решения уравнения (2; 1,1) можно брать функцию zd, для которой
|| A1zd тАУ u1 ||2L2<= d2 . (2;1,2)
Если заменить интегральный оператор A1z интегральВнной суммой на фиксированной сетке с n узлами и обознаВнчить значения искомой функции в узловых точках через zi , то задача построения приближенного решения уравнеВнния (2; 1,1) сведется к задаче нахождения конечномерВнного вектора, минимизирующего функционал N[z,и1] и удовлетворяющего неравенству (2; 1,2).
В ряде других случаев компактные классы корректВнности можно указать эффективно, что дает возможность строить устойчивые приближенные решения.
2.1.4. В силу погрешности исходных данных элемент и может не принадлежать множеству AM. В этих условиях уравнение (2; 0,1) не имеет решения (классического) и возникает вопрос: что надо понимать под приближенным решением уравнения (2; 0,1)?
В этом случае вводится понятие квазирешения и метод подбора при условии компактности множества М позвоВнляет найти приближение к квазирешению. В следующем параграфе вопрос о квазирешении рассматривается подВнробнее.
2.2. Квазирешения
2.2.1. Пусть оператор А в уравнении (2; 0,1) тАФ вполне непрерывный. Построение устойчивого к малым изменеВнниям правой части и приближенного решения уравнения (2; 0,1) по формуле
z=A-1u (2; 2,1)
возможно в тех случаях, как отмечалось в 2.1. , когда реВншение ищется на компакте МÌF и правая часть уравнеВнния принадлежит множеству N = AM.
Обычно не существует эффективных критериев, позВнволяющих установить принадлежность элемента и множеству N. Это приходится предполагать известным априори. В практических задачах часто вместо точного значения правой части иT нам известно ее приближенное значение u1, которое может не принадлежать множеству N=AM. В этих случаях нельзя строить приближенное решение уравнения (2; 0,1) по формуле (2; 2,1), так как симВнвол А-1u может не иметь смысла.
2.2.2. Стремление устранить затруднения, связанные с отВнсутствием решения уравнения (2; 0,1) при неточной правой части, привело В. К. Иванова к понятию квазирешения уравнения (2; 0,1) тАФ обобщению понятия решения этого уравнения.
Элемент z1ÎМ, минимизирующий при данном и функВнционал rU(Az1,и) на множестве М, называется квазирешеВннием уравнения (2; 0,1) на М,
Если М тАФ компакт, то квазирешение, очевидно, существуВнет для любого иÎU и если, кроме того, иÎAM, то кваВнзирешение z1 совпадает с обычным (точным) решением уравнения (2; 0,1). Квазирешение может быть и не одно. В этом случае под квазирешенпем будем разуметь любой элемент из множества квазирешений D.
Можно указать достаточные условия, при которых квазирешение единственно и непрерывно зависит от праВнвой части и.
Напомним определение. Пусть элемент у и множество Q принадлежат пространству U. Элемент q множества Q называется проекцией элемента у на множество Q, q=Ру, если выполняется равенство
Вместе с этим смотрят:
"Инкарнация" кватернионов
* Алгебры и их применение
*-Алгебры и их применение
10 способов решения квадратных уравнений
Cпособы преобразования комплексного чертежа, применение при изображении предметов