ВВЕДЕНИЕ Среди математических задач выделяется класс задач, решения которых неустойчивы к малым изменениям исходных данных. Они характеризуются тем, что сколь угодно малые изменения исходных данных могут приводить к произвольно большим изменениям решений. Задачи подобного типа, по существу, являются плохо поставленными. Они принадлежат к классу некорректно поставленных задач. Быстро растущее использование вычислительной техники требует развития вычислительных алгоритмов для решения широких классов задач. Но что надо понимать под «решением» задачи? Каким требованиям должны удовлетворять алгоритмы нахождения « решений »? Классические концепции и постановки задач не отражают многих особенностей встречающихся на практике задач. Мы покажем это на примере. Рассмотрим систему линейных алгебраических уравнений Az=u, где z искомый вектор, и известный вектор, А ={aij} квадратная матрица с элементами aij. Если система невырожденная, т. е. detA № 0, то она имеет единственное решение, которое можно найти по известным формулам Крамера или другими способами. Если система вырожденная, то она имеет решение (притом не единственное) лишь при выполнении условий разрешимости, состоящих из равенств нулю со- ответствующих определителей. Таким образом, прежде чем решить систему, надо проверить, вырожденная она или нет. Для этого требуется вычислить определитель системы detA. Если п порядок системы, то для вычисления detА требуется выполнить около п3 операций. С какой бы точностью мы ни производили вычисления, при достаточно большом значении п, вследствие накопления ошибок вычисления, мы можем получить значение detА, как угодно отличающееся от истинного. Поэтому желательно иметь (построить) такие алгоритмы нахождения решения системы, которые не требуют предварительного выяснения вырожденности или невырожденности системы. Кроме того, в практических задачах часто правая часть u и элементы матрицы А, т. е. коэффициенты системы уравнений, известны нам приближенно. В этих случаях вместо системы, мы имеем дело с некоторой другой системой A1z=u1 такой, что ||А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) 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) = e1. Здесь z=y(u1), z0=y(u0) и z1ОFo, z0ОF0. Возьмем последовательность {dn} положительных чисел dn , сходящуюся к нулю при ﮥ. Для каждого dn найдется элемент un1 из Uo, для которого rU(иn1, и0)= e1 , где zn1=y(un1). Очевидно, последовательность {un1} сходится к элементу u0. Так как zn1 принадлежат компактному на F множеству Fo, то из последовательности {zn1} можно выбрать подпоследовательность {Z1nk}, сходящуюся по метрике F к некоторому элементу z0 ОF. При этом z01№z0 , так как для всякого nk rF(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. Лемма доказана. Эту лемму можно сформулировать короче. Если отображение FoUo компакта Fo на множество Uo взаимно однозначно и непрерывно, то обратное отображение UoFo также непрерывно. Эквивалентность этих формулировок следует из того, что замыкание F*0 множества Fo, компактного на F, является компактом. Таким образом, минимизирующая последовательность {zn} в методе подбора сходится к zT при nҐ, если: а)zT принадлежит классу возможных решений М; б) множество М компакт. Пусть оператор А непрерывен и вместо точной правой части uT мы имеем элемент ud такой, что rU(ud,uT ) rU(A zdn ,u) по Тихонову и правая часть уравнения uОAM, то метод подбора с успехом может быть применен к решению такой задачи. На первый вопрос дан исчерпывающий ответ. Рассмотрим задачу решения интегрального уравнения Фредгольма первого рода (2;1,1) на множестве М1 монотонно убывающих (возрастающих) и равномерно ограниченных функций |z(s)| всюду, кроме, может быть, счетного множества точек разрыва функции 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) Если заменить интегральный оператор 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=Ру, если выполняется равенство где Теорема 1. Если уравнение Аz=u может иметь на компакте М не более одного решения и проекция каждого элемента uОU на множество N = AM единственна, то квазирешение уравнения (2; 0,1) единственно и непрерывно зависит от правой части u. Доказательство. Пусть z1 квазирешение и и1=Аz1. Очевидно, и1 есть проекция элемента u на множество N = AM. По условию теоремы она определяется однозначно. Отсюда, в силу взаимной однозначности отображения множества М на множество N, следует единственность квазирешения z1. Очевидно, что z1 = А-1u=А-1Ри. Согласно лемме о непрерывности обратного отображения компакта (см. предыдущий параграф) оператор А-1 непрерывен на N. Оператор проектирования Р непрерывен на U. Поэтому А-1P непрерывный на U оператор и, следовательно, квазирешение z1 непрерывно зависит от правой части и. Таким образом, при переходе к квазирешению восстанавливаются все условия корректности, т. е. задача нахождения квазирешения уравнения (2; 0,1) на компакте М является корректно поставленной. Если условие единственности решения уравнения (2; 0,1) не выполнено, то квазирешения образуют некоторое множество D элементов компакта М. В этом случае без упомянутых в теореме 1 ограничений на множество N имеет место непрерывная зависимость множества квазирешений D от и в смысле непрерывности многозначных отображений. Для случая, когда уравнение (2; 0,1) линейно, легко получить более общие результаты, содержащиеся в следующей теореме . Теорема 2. Пусть уравнение (2; 0,1) линейно, однородное уравнение Az=0 имеет только нулевое решение, множество М выпукло, а всякая сфера в пространстве U строго выпукла. Тогда квазирешение уравнения (2; 0,1) на компакте М единственно и непрерывно зависит от правой части и. Доказательство. Пусть z1 квазирешение и u1=Az1. Так как множество М выпукло, то в силу линейности оператора А множество N=AM также выпукло. Очевидно, что и1 есть проекция элемента и на множество N. В силу того, что сфера в пространстве U по условию теоремы строго выпукла, проекция и определяется однозначно. Далее доказательство завершается, как в теореме 1. 2.2.3. Пусть F и U гильбертовы пространства, МОSR шар (|| z ||=l2>=…>=ln>=… полная система его собственных значений, a j1, j2,…, jn,…отвечающая им полная ортонормированная система его собственных элементов (функций, векторов). Элемент А*и можно представить в виде ряда (2;2,2) В этих условиях справедлива Теорема 3. Квазирешение уравнения (2, 0,1) на множестве SR выражается формулами: (2;2,3) если (2;2,4) и если (2;2,5) Здесь b корень уравнения (2;2,6) Доказательство. Квазирсшение минимизирует функционал rU2 (Az, u) == (Az u, Az u) (2;2,7) (где (v,w ) скалярное произведение элементов v и w из U), уравнение Эйлера для которого имеет вид A*Az=A*u. (2;2,8) Решение этого уравнения будем искать в виде ряда по системе {jn}: (2;2,9) Подставляя этот ряд в уравнение (2; 2,8) и используя разложение (2;2,2), находим сn=bn/ln. Следовательно, неравенство (2; 2,4) означает, что ||z||=R и надо решать задачу на условные экстремум функционала (2; 2,7) при условии, что || z ||2 = R2. Методом неопределенных множителей Лагранжа эта задача сводится к нахождению безусловного экстремума функционала (Аz-u, Аz-u) + b (z, z), а последняя к решению отвечающего ему уравнения Эйлера A*Az+bz=А*и. Подставляя сюда z в виде ряда (2; 2,9) и используя разложение (2; 2,2), находим Параметр b определяем из условия || z ||2 = R2 , которое эквивалентно (2; 2,6). 2.3. Приближенное нахождение квазирешений В предыдущем параграфе мы видели, что нахождение квазирешения связано с нахождением элемента в бесконечномерном пространстве. Для приближенного нахождения квазирешения естественно переходить к конечномерному пространству. Можно указать достаточно общий подход к приближенному нахождению квазирешений уравнения (2; 0,1) , в котором Авполне непрерывный оператор. Будем полагать, что выполнены указанные в 2.2. достаточные условия существования единственного квазирешения на заданном множестве М, т. е. полагаем, что множество М выпуклый компакт и сфера в пространстве U строго выпукла. Пусть M1 М M2 М...М Mn М... возрастающая цепочка компактных замкнутых множеств Мn такая, что замыкание их объединения совпадает с М. Квазирешение уравнения (2; 0,1) существует на каждом множестве Мn . Но оно может быть не единственным. Обозначим через Тn совокупность всех квазирешений на множестве Мn . Покажем, что в качестве приближения к квазирешению z1 на множестве М можно брать любой элемент z1n из Тn . При этом Пусть Nn = АМn и Вn множество проекций элемента и на множество Nn . Очевидно, что Вn = АТn и N1 Н N2 Н …Н Nn; тогда r U(u,N1)>= …>=r U (u,Nn)>=… r U (u,N)= r U (u,Az1) . (2;3,1) Так как множество всюду плотно на N, то для всякого e >0 найдется такое число n0(e), что для всех п >n0(e) rU(u,Nn) (2;3,4) Каждое множество Вn есть компакт, так как оно является замкнутым подмножеством компакта Nn. Поэтому в Вn найдется такой элемент уn , что rU(yn ,u) = inf rU(y,u) yОBn Последовательность {yn} имеет хотя бы одну предельную точку, принадлежащую N, так как N компакт. Пусть у0 какая-нибудь предельная точка множества {yn} и {уnk} подпоследовательность, сходящаяся к y0 , т. е. Из (2; 3,3) и (2; 3,4) следует, что Таким образом, rU(u,y0)= rU(u,N). Отсюда и из единственности квазирешения на множестве М следует, что y0=Az1. Так как у0 произвольная предельная точка множества {yn}, то последовательность {уn} сходится к Аz1. Это и означает, что в качестве приближения к квазирешению можно брать любой элемент z1n из множества Тп , так как в силу леммы параграфа 2.1. z1nz* при nҐ. Если в качестве Мп брать конечномерные (n-мерные) множества, то задача нахождения приближенного квазирешения на компакте М сводится к минимизации функционала rU(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+aE)z є Az+az=u , (2:4,1) где a>0 числовой параметр. Решение уравнения za=(A+aE)-1u , (2; 4,2) при соответствующем выборе параметра a, принимается за приближенное решение уравнения (2; 0,1). Здесь Е единичный оператор. Замечание. Для оценки уклонения rF(zT,zd) приближенного решения от точного можно использовать модуль непрерывности w обратного оператора на N. Пусть u1, u2 О N и rU(u1,u2) (2;5,1) в области G є {x О D, t > 0}, удовлетворяющего граничным условиям u(х, t) =0 при xОS (2; 5,2) и начальным условиям u(x, 0)= j(x). (2; 5,3) Здесь Известно, что решение такой задачи существует. Каждой функции j(x)ОC отвечает решение задачи (2; 5,1) (2; 5,3). Будем обозначать его через u(х, t; j). Обратная задача состоит в нахождении функции j(х) по известной функции u(х,t; j). В реальных задачах функция u(x,t;j) обычно получается в результате измерений и, следовательно, известна приближенно. Будем полагать, что uОL2. Такая функция может и не соответствовать никакой «начальной» функции j(х). Таким образом, может не существовать в классе функций С решения обратной задачи. Поэтому будем рассматривать задачу нахождения некоторого обобщенного решения обратной задачи. Пусть заданы число T > 0 и функция y(x), определенная в области D, y(x) ОL2. На функциях j(х) класса С определен функционал Обобщенным решением обратной задачи будем называть функцию j(х)., на которой достигается f0=inf f(j) jОC Замечание. «Естественный» подход к решению этой задачи выбрать функцию j(х).так, чтобы f(j)=0 . Для этого достаточно найти решение прямой задачи u(x, t) = 0 для х О S, 0 0 найти функцию je(x), на которой f (je) 0; ua (x,T)= y(x); ua (x,t) = 0 для xО S, t xО D, t0; ua (x,T)= y(x); ua (x,t) = 0 для xО S, 0 Затем полагают j (x)=ua(x,0). Следует отметить, что uaне сходится в обычном смысле при a 0. 3.МЕТОД РЕГУЛЯРИЗАЦИИ РЕШЕНИЯ ОПЕРАТОРНЫХ УРАВНЕНИЙ В главе предыдущем разделе рассмотрены случаи, когда класс возможных решений уравнения (2; 0,1) является компактом. Однако для ряда прикладных задач характерна ситуация, когда этот класс F не является компактом, и, кроме того, изменения правой части уравнения Аz= u, (3; 0,1) связанные с ее приближенным характером, могут выводить за пределы множества AF образа множества F при отображении его с помощью оператора А. Такие задачи называются существенно некорректными. Был разработан новый подход к решению некорректно поставленных задач, позволяющий строить приближенные решения уравнения (3; 0,1), устойчивые к малым изменениям исходных данных, для существенно некорректных задач. В основе этого подхода лежит фундаментальное понятие регуляризирующего оператора (P.O.) . Для упрощения изложения в настоящей главе мы будем полагать, что в уравнении (3; 0,1) приближенной может быть лишь правая часть и, а оператор А известен точно. 3.1. Понятие регуляризирующего оператора 3.1.1. Пусть оператор А в уравнении (3; 0,1) таков, что обратный ему оператор A-1 не является непрерывным на множестве AF и множество возможных решений F не является компактом. Пусть zT есть решение уравнения Az =uT, т. е. AzT=uT. Часто вместо uT мы имеем некоторый элемент ud и известное число d > 0 такие, что rU(ud,uT)приближенного решения zd уравнения (3; 0,1) нельзя брать точное решение этого уравнения с приближенной правой частью и= ud, т. е. элемент zT, определяемый по формуле zd=A-1 ud так как оно существует не для всякого элемента u ОU и не обладает свойством устойчивости к малым изменениям правой части и. Числовой параметр d характеризует погрешность правой части уравнения (3;0,1). Поэтому представляется естественным определить zd с помощью оператора, зависящего от параметра, значения которого надо брать согласованными с погрешностью d исходных данных ud . Эта согласованность должна быть такой, чтобы при d0, т. е. при приближении (в метрике пространства U) правой части ud уравнения (3; 0,1) к точному значению uT, приближенное решение zd стремилось бы (в метрике пространства F) к искомому точному решению zt уравнения AzT =uT. Пусть элементы zT О F и uT О U связаны соотношением AzT = uT. Определение 1. Оператор R(и, d), действующий из пространства U в пространство F, называется регуля-ризирующим для уравнения Az = и (относительно элемента uT), если он обладает свойствами: 1) существует такое число d1 > 0, что оператор R(u, d) определен для всякого d, 0 0 существует d0=d0(e, ud)0, a1>0, что оператор R(u, a ) определен для всякого a, принадлежащего промежутку (0, a1), и любого uОU, для которого rU(u,uT) 0 найдется число d(e) 0,1), устойчивого к малым изменениям правой части, сводится: а) к нахождению регуляризирующих операторов; б) к определению параметра регуляризации a по дополнительной информации о задаче, например, по величине погрешности, с которой задается правая часть ud. Описанный метод построения приближенных решений называется методом регуляризации. 3.2. О решении вырожденных и плохо обусловленных систем линейных алгебраических уравнений 3.2.1. Известно, с какими трудностями связано решение так называемых плохо обусловленных систем линейных алгебраических уравнений: малым изменениям правых частей таких систем могут отвечать большие (выходящие за допустимые пределы) изменения решения. Рассмотрим систему уравнений Аz=u, (3; 2,1) где А матрица с элементами aij, А ={aij}, z искомый вектор с координатами zj , z={zj}, и известный вектор с координатами иi ,u= {ui}, i, j =1, 2, ..., п. Система (3; 2,1) называется вырожденной, если определитель системы равен нулю, detA = 0. В этом случае матрица А имеет равные нулю собственные значения. У плохо обусловленных систем такого вида матрица А имеет близкие к нулю собственные значения. Если вычисления производятся с конечной точностью, то в ряде случаев не представляется возможным установить, является ли заданная система уравнений вырожденной или плохо обусловленной. Таким образом, плохо обусловленные и вырожденные системы могут быть неразличимыми в рамках заданной точности. Очевидно, такая ситуация имеет место в случаях, когда матрица А имеет достаточно близкие к нулю собственные значения. В практических задачах часто правая часть и и элементы матрицы А, т. е. коэффициенты системы (3; 2,1), известны приближенно. В этих случаях вместо системы (3;2,1) мы имеем дело с некоторой другой системой Az=и такой, что ||A-A||zT принадлежит его области определения; б) для всякого числа d>0 множество F1,d элементов z из F1 , для которых W[ z ] Здесь . В дальнейшем для простоты записи будем считать z1= 0 и нормальное относительно вектора z1=0 решение называть просто нормальным решением. Для любой системы вида (3; 2,2) нормальное решение существует и единственно. Замечание 1. Нормальное решение z° системы (3;2,2) можно определить также как псевдорешение, минимизирующее заданную положительно определенную квадратичную форму относительно координат вектора zz1. Все излагаемые ниже результаты остаются при этом справедливыми. Замечание 2. Пусть ранг матрицы А вырожденной системы (3; 2,1) равен r zi*=. Таким образом, найдутся возмущения системы в пределах любой достаточно малой погрешности А и и, для которых некоторые zi* будут принимать любые наперед заданные значения. Это означает, что задача нахождения нормального решения системы (3; 2,2) является неустойчивой. Ниже дается описание метода нахождения нормального решения системы (3; 2,2), устойчивого к малым (в норме (3; 2,4)) возмущениям правой части и , основанного на методе регуляризации. 3.3. Метод регуляризации нахождения нормального решения 3.3.1. Пусть z° есть нормальное решение системы Аz = и. (3; 3,1) Для простоты будем полагать, что приближенной может быть лишь правая часть, а оператор (матрица) А точный. Итак, пусть вместо и мы имеем вектор и, || и и || Требуется найти приближение zd к нормальному решению системы (3;3,1), т. е. к вектору z° такое, что zd z° при d 0. Отметим, что векторы u и u (один из них или оба) могут не удовлетворять классическому условию разрешимости. Поскольку система (3; 3,1) может быть неразрешимой, то inf ||Az-u|| = m >=0, где inf берется по всем векторам z О Rn. Естественно искать приближения zd в классе Qd векторов z, сопоставимых по точности с исходными данными, т. е. таких, что || Az u || 0; 2) при d 0 zd== R1(u, d) стремится к нормальному решению z° уравнения Аz=u, т. е. он является регуляризирующим для уравнения Аz=u . 3.3.3. Пусть zd вектор, на котором функционал W[ z ] = ||z||2 достигает минимума на множестве Qd. Легко видеть из наглядных геометрических представлений, что вектор zd лежит на границе множества Qd, т.е. ||Azd - u ||=m +2d =d1. Это следует непосредственно также из того, что функционал W[ z ] = ||z||2 является сстабилизирующим и квазимонотонным. Стабилизирующий функционал W[ z ] называется квазимонотонным , если каков бы ни был элемент z из F1 , не принадлежащий множеству M0 , в любой его окрестности найдется элемент z1 из F1, для которого W[ z1 ]0, с параметром a, определяемым по невязке, т. е. из условия ||Аza u||=d1. При этом параметр a определяется однозначно . 3.3.4. Поскольку Мa [z, u] квадратичный функционал, то для любых u ОRm и a> 0 существует лишь один минимизирующий его вектор za. В самом деле, допустим, что существуют два вектора za и za, минимизирующие его. Рассмотрим векторы z, расположенные на прямой (пространства Rn), соединяющей za и za: z = za + b( za - za). Функционал Мa [z, u] на элементах этой прямой есть неотрицательная квадратичная функция от b. Следовательно, она не может достигать наименьшего значения при двух различных значениях b: b = 0 (z = za) и b=1 (z = za). Компоненты zja вектора za являются решением системы линейных алгебраических уравнений получающихся из условий минимума функционала Мa [z, u]: Здесь Компоненты zja могут быть определены и с помощью какого-нибудь другого алгоритма минимизации функционала Мa [z, u]. Вектор za можно рассматривать как результат применения к u некоторого оператора za=R(u, a), зависящего от параметра a. Покажем, что оператор R0(u, a) является регуляризирующим для системы (3;3,1), т. е. обладает свойствами 1) и 2) определения 2 (см. 3.1.2.). В п. 3.3.2. было сказано, что он определен для всяких u ОRm и a > О и, следовательно, обладает свойством 1). Теперь покажем справедливость свойства 2), т. е. существование таких функций a=a(d) , что векторы za(d) = R0(u, a(d)) сходятся к нормальному решению z° системы (3; 3,1) при d0. Это непосредственно следует из приводимой ниже теоремы 2. Теорема 2( Тихонова). Пусть z° есть нормальное решение системы Az= u и вместо вектора u мы имеем вектор u такой, что ||uu|| Тогда для любой .положительной на (0, d2] функции a=a(d) , удовлетворяющей условиям векторы za(d) = R0(u, a(d)) сходятся к нормальному решению z0 системы Az = u при d0, т. е. Примечание. Доказательства теорем в данном разделе опущены, т.к. основной теоретической частью работы является раздел «Метод Подбора. Квазирешения». Метод Тихонова описан из-за использования его в численном эксперименте. ЗАКЛЮЧЕНИЕ Для реализации численного примера был выбран метод Тихонова решения плохо обусловленных СЛАУ. В качестве исходной была взята СЛАУ Az=u, имеющая в матричной записи вид: Определитель матрицы коэффициентов этой системы близок к нулю он равен 0.000125. Попробуем решить эту систему с помощью обратной матрицы: z=A-1u Получим z1=316 z2=-990 z3=832 Теперь предположим, что правая часть нам известна приближенно, с погрешностью 0.1 Изменим, к примеру, третий элемент вектора-столбца с 1 на 1.1 : Попробуем решить новую систему также с помощью обратного оператора. Мы получаем другой результат: z1=348 z2=-1090 z3=916. Мы видим, что малому изменению правой части данной системы отвечают весьма значительные изменения решения. Очевидно, эта система плохо обусловленная, и здесь не может идти речи о нахождении решения близкого к точному с помощью обратного оператора. Будем искать решение методом Тихонова. В теоретической части было показано, что целесообразно использовать регуляризирующий оператор следующего вида: (aE + ATA)za=ATud , где E единичная матрица, za -- приближенное нормальное решение, AT транспонированная исходная матрица, a -- параметр регуляризации, ud -- правая часть, заданная неточно. Эту задачу можно решать стандартными методами, задав предварительно функцию a=a(d) , удовлетворяющую условиям теоремы Тихонова. В моем примере это функция a(d)=d/4d. Далее будем решать регуляризованную задачу с точностью e=0.001 ,последовательно изменяя значения a. В качестве контр-примера можно подставить в программу любую функцию a(d) , не удовлетворяющую условиям теоремы Тихонова. Любая положительная функция монотонно возрастающая, не обладающая свойством a(d)0 при d0, не будет минимизировать невязку. Текст программы приведен в приложении 1. Полная распечатка результатов приведена в приложении 2. Здесь же представлены окончательные значения на выходе из программы. Приближение к нормальному решению Z(1)= 3.47834819174013E+0002 Z(2)=-1.08948394975175E+0003 Z(3)= 9.15566443137791E+0002 Значение правой части при подстановке прибл. решения U1(1)= 9.99997717012495E-0001 U1(2)= 1.00000741970775E+0000 U1(3)= 1.09948402394883E+0000 Значение параметра регуляризации: 2.61934474110603E-0010 ПРИЛОЖЕНИЯ Приложение 1. Текст программы для реализации метода Тихонова на языке PASCAL Uses CRT; type real=extended; const matrixA: array[1..3,1..3] of real = ((-19/20,1/5, 3/5), (-1 ,0.1, 0.5), (-0.01 ,0 ,1/200)); One: array [1..3,1..3] of real = ((1,0,0), (0,1,0), (0,0,1)); U:array[1..3] of real = (1,1,1.1); var i,j,k,q:byte; A,At,A1,A2,Ar,One1:array[1..3,1..3] of real; delta,Det,S,alpha:real; B,Z,U1:array[1..3] of real; f:text; Procedure TransA; begin for i:=1 to 3 do for j:=1 to 3 do At[i,j]:=A[j,i] end; Function Koef(par1,par2:byte):real; var Sum:byte; Tmp:real; begin Sum:=par1+par2; Tmp:=1; for k:=1 to sum do Tmp:=Tmp*(-1); Koef:=Tmp; end; Function AlAdd(par1,par2:byte):real; type element=record value:real; flag:boolean; end; var BB:array[1..2,1..2] of real; AA:array[1..3,1..3] of element; k,v,w:byte; N:array[1..4] of real; P1:real; begin for v:=1 to 3 do for w:=1 to 3 do begin AA[v,w].value:=A2[v,w]; AA[v,w].flag:=true end; for v:=1 to 3 do AA[par1,v].flag:=false; for v:=1 to 3 do AA[v,par2].flag:=false; { for v:=1 to 3 do begin for w:=1 to 3 do write(AA[i,j].value:2:3, ); writeln end; } k:=1; for v:=1 to 3 do for w:=1 to 3 do begin if AA[v,w].flag then begin N[k]:=AA[v,w].value; { writeln(N[k]);} k:=k+1 end; end; BB[1,1]:=N[1]; BB[1,2]:=N[2]; BB[2,1]:=N[3]; BB[2,2]:=N[4]; { writeln(alg dop,par1,par2, ,BB[1,1]*BB[2,2]-BB[1,2]*BB[2,1]);} AlAdd:=BB[1,1]*BB[2,2]-BB[1,2]*BB[2,1]; end; Function DetCount:real; var S1:real; z:byte; begin S1:=0; for z:=1 to 3 do S1:=S1+A2[1,z]*Koef(1,z)*AlAdd(1,z); DetCount:=S1; end; Procedure RevMatr; begin for i:=1 to 3 do for j:=1 to 3 do Ar[j,i]:=Koef(i,j)*AlAdd(i,j)/DetCount; { for i:=1 to 3 do begin for j:=1 to 3 do write(Ar[i,j], ); writeln; end;} end; Function AllRight:boolean; begin writeln(f,­Ґўп§Є Ї® 1-¬г н«-вг,(abs(U[1]-U1[1]))); writeln(f,­Ґўп§Є Ї® 2-¬г н«-вг,(abs(U[2]-U1[2]))); writeln(f,­Ґўп§Є Ї® 3-¬г н«-вг,(abs(U[3]-U1[3]))); writeln(F); if (abs(U[1]-U1[1]) Function Pow(par1:real;par2:byte):real; var S2:real; z:byte; begin S2:=1; if par2=0 then begin Pow:=1; exit end else for z:=1 to par2 do S2:=S2*par1; Pow:=S2; end; BEGIN clrscr; Ass ign(f,c: ikh.txt); Rewrite(f); for i:=1 to 3 do for j:=1 to 3 do A[i,j]:=matrixA[i,j]; TransA; Det:=0.000125; {----------------------------} for i:=1 to 3 do begin S:=0; for j:=1 to 3 do begin S:=S+At[i,j]*U[j]; B[i]:=S end; end; {----------------------------} for i:=1 to 3 do for j:=1 to 3 do begin S:=0; for k:=1 to 3 do begin S:=S+At[i,k]*A[k,j]; A1[i,j]:=S end end; {-----------------------------} q:=1; repeat alpha:=q/pow(4,q); for i:=1 to 3 do for j:=1 to 3 do One1[i,j]:=One[i,j]*alpha; for i:=1 to 3 do for j:=1 to 3 do A2[i,j]:=One1[i,j]+A1[i,j]; RevMatr; {------------------------------} for i:=1 to 3 do begin S:=0; for j:=1 to 3 do begin S:=S+Ar[i,j]*B[j]; Z[i]:=S end; end; for i:=1 to 3 do begin S:=0; for j:=1 to 3 do begin S:=S+A[i,j]*Z[j]; U1[i]:=S end end; q:=q+1; until AllRight; {------------------------------} clrscr; writeln(ЏаЁЎ«Ё¦Ґ­ЁҐ Є ­®а¬«м­®¬г аҐиҐ­Ёо); for i:=1 to 3 do writeln(Z(,i,)=,z[i]); writeln; writeln(‡­зҐ­ЁҐ Їаў®© збвЁ ЇаЁ Ї®¤бв­®ўЄҐ ЇаЁЎ«. аҐиҐ­Ёп); for i:=1 to 3 do writeln(U1(,i,)=,U1[i]); writeln; writeln(‡­зҐ­ЁҐ Їа¬Ґва ॣг«паЁ§жЁЁ:); writeln(alpha); Close(f); readln; END. Приложение 2. Распечатка результатов пересчета на каждом шаге невязка по 1-му эл-ту 7.75620788018006E-0002 невязка по 2-му эл-ту 9.12970302562861E-0002 невязка по 3-му эл-ту 1.09101153877771E+0000 невязка по 1-му эл-ту 3.51667654246499E-0002 невязка по 2-му эл-ту 4.81631787337596E-0002 невязка по 3-му эл-ту 1.09057642915500E+0000 невязка по 1-му эл-ту 8.14255746519741E-0003 невязка по 2-му эл-ту 1.75271999674588E-0002 невязка по 3-му эл-ту 1.09024740493812E+0000 невязка по 1-му эл-ту 1.64128226088452E-0004 невязка по 2-му эл-ту 1.40420815653456E-0003 невязка по 3-му эл-ту 1.09002512985506E+0000 невязка по 1-му эл-ту 1.09651876415789E-0003 невязка по 2-му эл-ту 8.01044623892439E-0003 невязка по 3-му эл-ту 1.08980075500722E+0000 невязка по 1-му эл-ту 3.24092274239579E-0003 невязка по 2-му эл-ту 1.28969442769472E-0002 невязка по 3-му эл-ту 1.08943309314635E+0000 невязка по 1-му эл-ту 4.29878415191160E-0003 невязка по 2-му эл-ту 1.47864580098997E-0002 невязка по 3-му эл-ту 1.08840358157784E+0000 невязка по 1-му эл-ту 4.64764022304719E-0003 невязка по 2-му эл-ту 1.53489294761093E-0002 невязка по 3-му эл-ту 1.08488736141985E+0000 невязка по 1-му эл-ту 4.70263264899617E-0003 невязка по 2-му эл-ту 1.53524096326819E-0002 невязка по 3-му эл-ту 1.07252416252061E+0000 невязка по 1-му эл-ту 4.54618391386039E-0003 невязка по 2-му эл-ту 1.47935415193105E-0002 невязка по 3-му эл-ту 1.03007092553528E+0000 невязка по 1-му эл-ту 3.97950585276394E-0003 невязка по 2-му эл-ту 1.29378307693635E-0002 невязка по 3-му эл-ту 9.00028069734717E-0001 невязка по 1-му эл-ту 2.71895340473448E-0003 невязка по 2-му эл-ту 8.83742514077426E-0003 невязка по 3-му эл-ту 6.14624514462952E-0001 невязка по 1-му эл-ту 1.25089904346179E-0003 невязка по 2-му эл-ту 4.06552487723671E-0003 невязка по 3-му эл-ту 2.82729125073012E-0001 невязка по 1-му эл-ту 4.15581257891512E-0004 невязка по 2-му эл-ту 1.35064829843828E-0003 невязка по 3-му эл-ту 9.39264706989556E-0002 невязка по 1-му эл-ту 1.18814900667952E-0004 невязка по 2-му эл-ту 3.86149131520602E-0004 невязка по 3-му эл-ту 2.68533566153482E-0002 невязка по 1-му эл-ту 3.22671215741144E-0005 невязка по 2-му эл-ту 1.04868192738639E-0004 невязка по 3-му эл-ту 7.29267248287954E-0003 невязка по 1-му эл-ту 8.61328853146714E-0006 невязка по 2-му эл-ту 2.79931897352870E-0005 невязка по 3-му эл-ту 1.94668264668650E-0003 невязка по 1-му эл-ту 2.28298750498679E-0006 невязка по 2-му эл-ту 7.41970775380851E-0006 невязка по 3-му эл-ту 5.15976051172231E-0004 Приближение к нормальному решению Z(1)= 3.47834819174013E+0002 Z(2)=-1.08948394975175E+0003 Z(3)= 9.15566443137791E+0002 Значение правой части при подстановке прибл. решения U1(1)= 9.99997717012495E-0001 U1(2)= 1.00000741970775E+0000 U1(3)= 1.09948402394883E+0000 Значение параметра регуляризации: 2.61934474110603E-0010 СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 1.А.Н.ТИХОНОВ, В.Я.АРСЕНИН «МЕТОДЫ РЕШЕНИЯ НЕКОРРЕКТНЫХ ЗАДАЧ» МОСКВА «НАУКА» 1979. 2.Г.И.МАРЧУК «МЕТОДЫ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ» МОСКВА «НАУКА» 1977. 3.Л.И.ГОЛОВИНА «ЛИНЕЙНАЯ АЛГЕБРА И НЕКОТОРЫЕ ЕЕ ПРИЛОЖЕНИЯ» МОСКВА «НАУКА» 1975. 4.В.И.РАКИТИН, В.Е.ПЕРВУШИН «ПРАКТИЧЕСКОЕ РУКОВОДСТВО ПО МЕТОДАМ ВЫЧИСЛЕНИЙ» МОСКВА «ВЫСШАЯ ШКОЛА» 1998. 5.В.В.ФАРОНОВ «ПРОГРАММИРОВАНИЕ НА ПЕРСОНАЛЬНЫХ ЭВМ В СРЕДЕ TURBO PASCAL» -- ИЗДАТЕЛЬСТВО МГТУ 1990.