Реферат: Методы решения некорректно поставленных задач

ВВЕДЕНИЕ

Среди математических задач выделяется класс задач, решения которых неустойчивы к малым изменениям исходных данных. Они характеризуются тем, что сколь угодно малые изменения исходных данных могут приводить к произвольно большим изменениям решений. Задачи подобного типа, по существу, являются плохо поставленными. Они принадлежат к классу некорректно поставленных задач.

Быстро растущее использование вычислительной техники требует развития вычислительных алгоритмов для решения широких классов задач. Но что надо понимать под «решением» задачи? Каким требованиям должны удовлетворять алгоритмы нахождения « решений »?

Классические концепции и постановки задач не отражают многих особенностей встречающихся на практике задач. Мы покажем это на примере.

Рассмотрим систему линейных алгебраических уравнений

Az=u ,

где z — искомый вектор, и — известный вектор, А ={a_ij } — квадратная матрица с элементами a _ij .

Если система невырожденная, т. е.detA ¹0, то она имеет единственное решение, которое можно найти по известным формулам Крамера или другими способами.

Если система вырожденная, то она имеет решение (притом не единственное) лишь при выполнении условий разрешимости, состоящих из равенств нулю со- ответствующих определителей.

Таким образом, прежде чем решить систему, надо проверить, вырожденная она или нет. Для этого требуется вычислить определитель системыdetA.

Если п — порядок системы, то для вычисления detА требуется выполнить около п ³ операций. С какой бы точностью мы ни производили вычисления, при достаточно большом значении п, вследствие накопления ошибок вычисления, мы можем получить значение detА, как угодно отличающееся от истинного. Поэтому желательно иметь (построить) такие алгоритмы нахождения решения системы, которые не требуют предварительного выяснения вырожденности или невырожденности системы.

Кроме того, в практических задачах часто правая часть u и элементы матрицы А,

т. е. коэффициенты системы уравнений, известны нам приближенно. В этих случаях вместо системы, мы имеем дело с некоторой другой системойA¹ z=u¹ такой, что

||А ¹ — А ||<=h , ||u¹ -u||<= d, где смысл норм обычно определяется характером задачи. Имея вместо матрицы А матрицу А ¹ , мы тем более не можем высказать определенного суждения овырожденности или невырожденности системы.

В этих случаях о точной системе Az = и нам известно лишь то, что для матрицы А и правой части и выполняются неравенства ||А¹ —А ||<= h и ||и ¹ —и || < = d. Но систем с такими исходными данными (А, и) бесконечно много, и в рамках известного нам уровня погрешности они неразличимы. Среди таких «возможных точных систем» могут быть и вырожденные.

Поскольку вместо точной системы мы имеем приближенную систему A ¹ z =и ¹ , то речь может идти лишь о нахождении приближенного решения. Но приближенная система может быть и неразрешимой. Возникает вопрос: что надо понимать под приближенным решением системы? Оно должно быть также устойчивым к малым изменениям исходных данных (А, и).

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

1. ПОНЯТИЕ КОРРЕКТНО ПОСТАВЛЕННЫХ И НЕКОРРЕКТНО ПОСТАВЛЕННЫХ ЗАДАЧ

1.1. Различают корректно поставленные, и некорректно поставленные задачи. Понятие корректной постановки задач математической физики было введено

Ж. Адамаром в связи с желанием выяснить, какие типы граничных условий наиболее естественны для различных типов дифференциальных уравнений (для эллиптических, например,— задача Дирихле и ей аналогичные, для гиперболических — задача Коши).

Решение всякой количественной задачи обычно заключается в нахождении «решения» z по заданным «исходным данным» и, z=R(u). Мы будем считать их эле- ментами метрических пространствF иU с расстояниями между элементами; u₁ , u₂ ÎU; z₁ ,z₂ ÎF. Метрика обычно определяется постановкой задачи.

1. 2. Пусть определено понятие «решения» и каждому элементу и ÎU отвечает единственное решениеz=R(u) из пространстваF.

Задача определения решенияz=R(u) из простран­ства F по исходным данным

и ÎU называется устойчивой на пространствах (F, U), если для любого числа e> О можно указать такое число d (e) > 0, что из неравенства r_U (u₁ ,u₂ )<= d (e) следуетr_F (z_1, z₂ )<= e, гдеz₁ =R(u₁ ), z₂ =R(u ₂ ) ; u₁ ,u₂ ÎU; z₁ ,z₂ Î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, т. е. вместо ее точного значения u_T нам известны элемент и ¹ и число d такие, что r_U (u_T ,u¹ )<= d. По этим данным, т. е. по (u¹ , d), требуется найти такой элемент z_d , ко­торый стремился бы (в метрике F) кz_T при d®0. Та­кой элемент мы будем называть приближенным (к z_T ) решением уравнения Az = и ¹ .

Элементы zÎF, удовлетворяющие условию r_U (Az, и ¹ ) <= d, будем называть сопоставимыми по точности с ис­ходными данными (и ¹ , d). Пусть Q_d —совокупность всех таких элементов z ÎF. Естественно приближенные ре­шения уравнения Az=и ¹ искать в классе Q_d элементов z , сопоставимых по точности с исходными данными

(и ¹ , d ).

Однако в ряде случаев этот класс элементов слишком широк. Среди этих элементов есть такие, которые могут сильно отличаться друг от друга ( в метрике пространства F ). Поэтому не все элементы класса Q_d можно брать в качестве приближенного решения уравнения (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, т. е. решается прямая задача. В качестве при­ближенного решения берется такой элемент z₀ из мно­жества М, на котором невязкаr_U (Az,u ) достигает мини­мума, т. е.

r_U (Az₀ ,u ) = inf r_U (Az,u )

zÎM

Пусть правая часть уравнения (2;0,1) известна точ­но, т. е. и =u_T , и требуется найти его решение z_T . Обычно в качестве М берется множество элементов z, зависящих от конечного числа параметров, меняющихся в ограниченных пределах так, чтобы М было замкнутым множеством конечномерного пространства. Если искомое точное решение z_T уравнения (2; 0,1) принадлежит мно­жеству М, то и достигается эта нижняя граница на точном решении z_T . Если уравнение (2;0,1) имеет единственное решение, то элемент z₀ , минимизирующий r_U (Az,и), определен однозначно.

Практически минимизация невязки r_U (Az,и ) произ­водится приближенно и возникает следующий важный вопрос об эффективности метода подбора, т. е. о возмож­ности как угодно приблизиться к искомому точному ре­шению.

Пусть {z_n } — последовательность элементов, для ко­торой r_U (Az_n ,u) ®0 при n®¥. При каких условиях можно утверждать, что при этом и r_F (z_n ,z_T ) ®0, т. е. что {z_n } сходится к z_T ?

Это вопрос обоснования эффективности метода подбора.

2.1.2. Стремление обосновать успешность метода подбора привело к установлению общефункциональных требова­ний, ограничивающих класс возможных решений М, при которых метод подбора является устойчивым и z_n ®z_T . Эти требования заключаются в компактности мно­жества М и основываются на приводимой ниже извест­ной топологической лемме.

Лемма.Пусть метрическое пространство 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.

Возьмем произвольный элемент u₀ из Uo. Покажем, что функция y(u) непрерывна на u₀ . Предположим, что это неверно. Тогда существует такое число e₁ > 0, что для всякого d > 0 найдется элемент и ¹ из Uo, для которого r_U (и ¹ , и ₀ ) < d, в то время как r_F (z¹ ,z₀ )>= e₁ . Здесь z=y(u¹ ), z₀ =y(u₀ ) и z¹ ÎFo, z₀ ÎF₀ .

Возьмем последовательность {d_n } положительных чи­сел d_n , сходящуюся к нулю при п ®¥. Для каждого d_n найдется элемент u_n ¹ из Uo, для которого r_U (и _n ¹ , и ₀ ) < d_n , но r_F (z_n ¹ ,z₀ )>= e₁ , где z_n ¹ =y(u_n ¹ ). Очевидно, последова­тельность {u_n ¹ } сходится к элементу u₀ . Так как z_n ¹ при­надлежат компактному на F множеству Fo, то из после­довательности {z_n ¹ } можно выбрать подпоследовательность {Z¹ n_k }, сходящуюся по метрике F к некоторому элементу z₀ ÎF. При этом z₀ ¹ ¹z₀ , так как для всякого n_k r_F (Z¹ n_k ,z₀ )>= e₁ , следовательно и r_F (z¹ ₀ ,z₀ )>= e₁ . Этой подпоследовательности {Z¹ n_k } отвечает последователь­ность элементов u¹ n_k = j (Z¹ n_k ) из Uo, сходящаяся к u¹ ₀ = j(z¹ ₀ ) и являющаяся подпоследовательностью по­следовательности { u¹ _n }. Так как последовательность { u¹ _n } сходится к и ₀ =j(z₀ ), то u¹ ₀ =j(z¹ ₀ )=u₀ =j(z₀ ) , т. е. j(z₀ )= j(z¹ ₀ ). В силу взаимной однозначности отоб­ражения F ®U z¹ ₀ =z₀ , что противоречит ранее установ­ленному неравенству z¹ ₀ ¹z₀ . Лемма доказана.

Эту лемму можно сформулировать короче.

Если отображение Fo-Uo компакта Fo на множество Uo взаимно однозначно и непрерывно, то обратное отобра­жение Uo-Fo также непрерывно.

Эквивалентность этих формулировок следует из того, что замыкание F^* ₀ множества Fo, компактного наF, явля­ется компактом.

Таким образом, минимизирующая последовательность {z_n } в методе подбора сходится к z_T при n-¥, если:

а)z_T принадлежит классу возможных решений М;

б) множество М — компакт.

Пусть оператор А непрерывен и вместо точной правой части u_T мы имеем элемент u_d такой, что r_U (u_d ,u_T )<= d, причем u_d принадлежит множествуAM (образу множест­ва М при отображении его с помощью оператора A) и М есть компакт. Пусть {d_n } — последовательность поло­жительных чисел таких, что d_n -0 при n-оо. Для каж­дого п методом подбора можно найти такой элемент z^d _n , что r_U (A z^d _n ,u_d )<=d_n . Элементы z^d _n будут близки к ре­шению z_T уравненияAz=u_T . В самом деле, при отобра­жении с помощью непрерывного оператора образAM компакта М есть компакт и, следовательно, по лемме обратное отображение, осуществляемое оператором A^-1 , непрерывно наAM. Так как

r_U (A z^d _n ,u)<=r_U (A z_n ,u_d )+r_U (u_d ,u_T ),

то

r_U (A z^d _n ,u_T )<=d_n +d=g^d _n .

Из этого неравенства и из непрерывности обратного отображения АМ - М следует, что r_F (z^d _n ,z_T )<= e(g^d _n ) , причем e(g^d _n )-0 приg^d _n -0. Таким образом, при нахож­дении приближения z^d _n к z_T надо учитывать уровень по­грешности d правой части u_d .

2.1.3. На основе изложенных соображений М. М. Лав­рентьев сформулировал понятие корректности по Тихонову. В применении к уравнению (2; 0,1) задача на­зывается корректной по Тихонову, если известно, что для точного значения u=u_T существует единственное реше­ние z_T уравнения (2; 0,1), Az_T =u_T, принадлежащее за­данному компакту М. В этом случае оператор А ^-1 непре­рывен на множествеN=AM и, если вместо элемента u_T нам известен элемент u_d такой, что r_U ( u_T , u_d )<=dи u_d ÎN, то в качестве приближенного решения уравнения (2; 0,1) с правой частью u= u_d можно взять элемент z_d =A^-1 u_d .При d-0(u_d ÎN) z_d будет стремиться к z_T . МножествоF₁ (F₁ ÌF), на котором задача нахождения решения уравнения (2; 0,1) является корректно постав­ленной, называют классом корректности. Так, если опера­торА непрерывен и осуществляет взаимно однозначное отображение, то компакт М, к которому принадлежит z_T , является классом корректности для уравнения (2; 0,1). Таким образом, если задача (2; 0,1) корректна по Тихо­нову и правая часть уравнения uÎAM, то метод подбора с успехом может быть применен к решению такой задачи. На первый вопрос дан исчерпывающий ответ.

Рассмотрим задачу решения интегрального уравнения Фредгольма первого рода

(2;1,1)

на множестве М ₁ монотонно убывающих (возрастающих) и равномерно ограниченных функций |z(s)|<=B. Она корректна по Тихонову, так как множествоM₁ — компакт в пространстве L₂ .

Действительно, возьмем любую последовательность E= {z₁ (s), z₂ (s), .... z_n (s), ...} изM₁ . Согласно теореме Хелли о выборе существуют подпоследовательность

E₁ = {Zn₁ (s), Zn₂ (s), ...,Zn_k (s), ...},

последовательности Е и функция z*(s) из множества M₁ , z*(s) ÎL₂ , такие, что

всюду, кроме, может быть, счетного множества точек разрыва функции z*(s). Из поточечной сходимости под­последовательности Е ₁ к функции z*(s) всюду, кроме, может быть, счетного множества точек, следует, какизвестно, сходимость подпоследовательности E₁ к функ­ции z*(s) по метрике L₂ .

Таким образом, в качестве приближенного решения на множестве М₁ уравнения (2; 1,1) с приближенно извест­ной правой частью u¹ ÎАМ ₁ можно брать точное решение этого уравнения с правой частью u=u¹ . Эта послед­няя задача эквивалентна задаче нахожде­ния на множествеM₁ функции, минимизирующей функ­ционал

N[z,u¹ ]=|| A₁ z – u¹ ||² _L2 .

Пусть r_U (u_T , u¹ )<= d. Тогда, очевидно, в качестве при­ближенного решения уравнения (2; 1,1) можно брать функцию z_d , для которой

|| A₁ z_d – u¹ ||² _L2 <= d² . (2;1,2)

Если заменить интегральный оператор A₁ z интеграль­ной суммой на фиксированной сетке с n узлами и обозна­чить значения искомой функции в узловых точках через z_i , то задача построения приближенного решения уравне­ния (2; 1,1) сведется к задаче нахождения конечномер­ного вектора, минимизирующего функционалN[z, и ¹ ] и удовлетворяющего неравенству (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^-1 u (2; 2,1)

возможно в тех случаях, как отмечалось в 2.1. , когда ре­шение ищется на компакте М ÌF и правая часть уравне­ния принадлежит множеству N =AM.

Обычно не существует эффективных критериев, поз­воляющих установить принадлежность элемента и множеству N. Это приходится предполагать известным априори. В практических задачах часто вместо точного значения правой части и _T нам известно ее приближенное значение u¹ , которое может не принадлежать множеству N =AM. В этих случаях нельзя строить приближенное решение уравнения (2; 0,1) по формуле (2; 2,1), так как сим­вол А^-1 u может не иметь смысла.

2.2.2. Стремление устранить затруднения, связанные с от­сутствием решения уравнения (2; 0,1) при неточной правой части, привело В. К. Иванова к понятию квазирешения уравнения (2; 0,1) — обобщению понятия решения этого уравнения.

Элемент z¹ ÎМ, минимизирующий при данном и функ­ционалr_U (Az¹ ,и) на множестве М, называется квазиреше­нием уравнения (2; 0,1) на М,

Если М — компакт, то квазирешение, очевидно, существу­ет для любого и ÎU и если, кроме того, и ÎAM, то ква­зирешение z¹ совпадает с обычным (точным) решением уравнения (2; 0,1). Квазирешение может быть и не одно. В этом случае под квазирешенпем будем разуметь любой элемент из множества квазирешенийD.

Можно указать достаточные условия, при которых квазирешение единственно и непрерывно зависит от пра­вой части и.

Напомним определение. Пусть элемент у и множество Q принадлежат пространству U. Элементq множестваQ называется проекцией элемента у на множество Q, q =Ру, если выполняется равенство

Теорема 1. Если уравнение Аz= u может иметь на компакте М не болееодного решения и проекция каждого элемента uÎU на множество N = AM единственна, то квазирешение уравнения (2; 0,1) единственно и непре­рывно зависит от правой части u.

Доказательство. Пусть z¹ — квазирешение и и ¹ =А z¹ . Очевидно, и ¹ есть проекция элемента u на множе­ство N =AM. По условию теоремы она определяется од­нозначно. Отсюда, в силу взаимной однозначности ото­бражения множества М на множествоN, следует един­ственность квазирешения z¹ .

Очевидно, что z¹ = А^-1 u=А ^-1 Ри. Согласно лемме о непрерывности обратного отображения компакта (см. предыдущий параграф) оператор А^-1 непрерывен на N. Оператор проектирования Р непрерывен на U. Поэтому А^-1 P — непрерывный на U оператор и, следовательно, квазирешение z¹ непрерывно зависит от правой части и.

Таким образом, при переходе к квазирешению восста­навливаются все условия корректности, т. е. задача на­хождения квазирешения уравнения (2; 0,1) на компакте М является корректно поставленной.

Если условие единственности решения уравнения (2; 0,1) не выполнено, то квазирешения образуют некото­рое множествоD элементов компакта М. В этом случае без упомянутых в теореме 1 ограничений на множество N имеет место непрерывная зависимость множества квази­решений D от и в смысле непрерывности многозначных отображений. Для случая, когда уравнение (2; 0,1) линейно, легко получить более общие результаты, содержащиеся в сле­дующей теореме .

Теорема 2.Пусть уравнение (2; 0,1) линейно, одно­родное уравнение Az=0имеет только нулевое решение, множество М выпукло, а всякая сфера в пространстве U строго выпукла. Тогда квазирешение уравнения (2; 0,1) на компакте М единственно и непрерывно зависит от пра­вой части и.

Доказательство. Пусть z¹ — квазирешение и u¹ =Az¹ . Так как множество М выпукло, то в силу линей­ности оператора А множество N =AM также выпукло. Очевидно, что и ¹ есть проекция элемента и на множество N. В силу того, что сфера в пространстве U по условию теоремы строго выпукла, проекция и определяется одно­значно. Далее доказательство завершается, как в тео­реме 1.

2.2.3. ПустьF и U — гильбертовы пространства, М ÎS_R — шар (|| z ||<=R ) в пространстве F и А — вполне непре­рывный линейный оператор.

В этом случае квазирешение уравнения (2; 0,1) мож­но представить в виде ряда по собственным элементам (функциям, векторам) j_n оператора А*А, где А* — опе­ратор, сопряженный оператору А.

Известно, что А*А — самосопряженный положитель­ный вполне непрерывный оператор из F в F. Пусть l₁ >=l₂ >=…>=l_n >=… — полная система его собственных значений, a j₁ , j₂ ,…, j_n ,…—отвечающая им полная ортонормированная система его собственных элементов (функций, векторов). Элемент А*и можно представить в виде ряда

(2;2,2)

В этих условиях справедлива

Теорема 3. Квазирешение уравнения (2, 0,1) намножествеS_R выражается формулами:

(2;2,3)

если

(2;2,4)

и

если

(2;2,5)

Здесьb —корень уравнения

(2;2,6)

Доказательство. Квазирсшение минимизирует функционал

r_U ² (Az,u) == (Az —u, Az — u) (2;2,7)

(где (v,w ) — скалярное произведение элементовv иw из U), уравнение Эйлера для которого имеет вид

A*Az=A*u. (2;2,8)

Решение этого уравнения будем искать в виде ряда по системе {j_n }:

(2;2,9)

Подставляя этот ряд в уравнение (2; 2,8) и используя разложение (2;2,2), находим с_n =b_n / l_n . Следователь­но, неравенство (2; 2,4) означает, что ||z||<R и речь идет о нахождении безусловного экстремума функциона­ла (2; 2,7). Ряд (2; 2,3) и будет решением задачи.

Если же выполняется неравенство (2; 2,5), то это означает, что ||z||>=R и надо решать задачу на услов­ные экстремум функционала (2; 2,7) при условии, что || z ||² =R² . Методом неопределенных множителей Лагранжа эта задача сводится к нахождению безусловного экстремума функционала

(Аz-u, Аz-u) +b (z, z),

а последняя — к решению отвечающего ему уравнения ЭйлераA*Az +bz=А*и. Подставляя сюда z в виде ряда (2; 2,9) и используя разложение (2; 2,2), находим

Параметр b определяем из условия || z ||² =R² , которое эквивалентно (2; 2,6).

2.3. Приближенное нахождение квазирешений

В предыдущем параграфемы видели, что нахождение квазирешения связано с нахождением элемента в беско­нечномерном пространстве. Для приближенного нахожде­ния квазирешения естественно переходить к конечномер­ному пространству. Можно указать достаточно общий под­ход к приближенному нахождению квазирешений урав­нения (2; 0,1) , в котором А—вполне непре­рывный оператор.

Будем полагать, что выполнены указанные в 2.2. дос­таточные условия существования единственного квазире­шения на заданном множестве М, т. е. полагаем, что множество М — выпуклый компакт и сфера в пространст­ве U строго выпукла. Пусть

M₁ Ì M₂ Ì...Ì M_n Ì...

— возрастающая цепочка компактных замкнутых множеств М _n такая, что замыкание их объединения совпадает с М. Квазирешение уравнения (2; 0,1) сущест­вует на каждом множестве М _n . Но оно может быть не единственным. Обозначим через Т _n совокупность всех квазирешений на множестве М _n .

Покажем, что в качестве приближения к квазиреше­нию z¹ на множестве М можно брать любой элемент z¹ _n из Т _n . При этом

Пусть N_n = АМ _n и В _n — множество проекций элемен­та и на множествоN_n . Очевидно, что В _n =АТ _n и N₁ Í N₂ Í …Í N_n ; тогда

r_U (u,N₁ )>= …>=r_U (u,N_n )>=… r_U (u,N)= r_U (u,Az¹ ) .(2;3,1)

Так как множествовсюду плотно на N, тодлявсякого e >0 найдется такое число n₀ (e), что для всех п > n₀ (e)

r_U (u,N_n )<r_U (u,N)+e (2; 3,2)

Из (2; 3,1) и (2; 3,2) следует, что

(2;3,3)

(2;3,4)

Каждое множествоВ _n есть компакт, так как оно является замкнутым подмножеством компактаN_n . ПоэтомувВ _n найдется такой элемент у_n , что

r_U (y_n ,u) = inf r_U (y,u)

yÎB_n

Последовательность {y_n } имеет хотя бы одну пре­дельную точку, принадлежащуюN, так как N — компакт. Пусть у ₀ — какая-нибудь предельная точка множества {y_n } и {уn_k } — подпоследовательность, сходящаяся к y₀ , т. е.

Из (2; 3,3) и (2; 3,4) следует, что

Таким образом,

r_U (u,y₀ )=r_U (u,N).

Отсюда и из единственности квазирешения на множестве М следует, что

y₀ =Az¹ .

Так как у ₀ — произвольная предельная точка множества {y_n }, то последовательность {у_n } сходится к А z¹ . Это и означает,что в качестве приближения к квазирешению мож­но брать любой элемент z¹ _n из множества Т_п , так как в силу леммы параграфа 2.1. z¹ _n -z* при n-¥.

Если в качестве М_п брать конечномерные (n-мерные) множества, то задача нахождения приближенного квази­решения на компакте М сводится к минимизации функ­ционалаr_U (Az,u) на множестве М_п , т. е. к нахождению минимума функции п переменных.

2.4. Замена уравнения А z = u близким ему

Уравнения вида (2; 0,1), в которых правая часть u не принадлежит множествуN=AM, изучались М. М. Лав­рентьевым . Ему принадлежит идея замены исходного уравнения (2; 0,1) близким ему, в некотором смысле, уравнением, для которого задача нахождения решения устойчива к малым изменениям правой части и разрешима для любой правой части u ÎU. В простей­шем случае это делается следующим образом.

ПустьF ºU ºН — гильбертовы пространства, А — линейный, ограниченный, положительный и самосопря­женный оператор,S_R º {х, ||x||<=R,xÎF} есть шар радиуса R в пространстве F, В — вполне непрерывный оператор, определенный на S_R при любом R > 0. В ка­честве класса корректности М берется множество D_R =BS_R — образ шара S_R при отображении с помощью оператора В. Предполагается, что искомое точное решение z_T уравнения (2; 0,1) с правой частью u=u_T существует и принадлежит множеству D_R . Уравнение (2; 0,1) заме­няется уравнением

(A+aE)z º Az+az=u , (2:4,1)

где a>0 – числовой параметр. Решение уравнения

z_a =(A+aE)^-1 u , (2; 4,2)

при соответствующем выборе параметра a, принимается за приближенное решение уравнения (2; 0,1). Здесь Е — единичный оператор.

Замечание. Для оценки уклонения r_F (z_T ,z_d ) приближенного решения от точного можно использовать мо­дуль непрерывности w обратного оператора на N.

Пусть u₁ , u₂ Î N иr_U (u₁ ,u₂ )<=d. Тогда

w(d,N)= sup r_F (A^-1 u₁ ,A^-1 u₂ ).

u₁ ,u₂ ÎN

Очевидно, что еслиr_U (u_T ,u_d )<=dи z_d =A^-1 u_d , то

r_F (z_T ,z_d )<=w(d,N).

Вернемся к уравнению (2; 4,1). Если || Az ||<=d и w(d,D_R ) = sup|| z ||, то легко

D_R

получить оценку уклонения z_a от z_T . Очевидно, что

|| z_a - z_T ||<=||z_a ¹ - z_T || + ||z_a - z_a ¹ ||, (2;4,3)

где

z_a ¹ =(A + aE)^-1 u_T .

Следовательно,

||z_a - z_T ||<=w(d,D_R ) + d/a. (2;4,4)

Если известен модуль непрерывности w(d,D_R ) или его мажоранта, то из (2; 4,4) можно найти значение пара­метра wкак функцию d, при котором правая часть в не­равенстве (2; 4,4) будет минимальной.

2. 5. Метод квазиобращения

2.5.1. Известно, что задача Коши для уравнения тепло­проводности с обратным течением времени является не­устойчивой к малым изменениям начальных значений. Неустойчивость сохраняется и в случаях, когда решение подчиняется некоторым дополнительным граничным усло­виям. Для устойчивого решения таких задач разработан метод квазиобращения . Мы изложим существо его для простейшего уравнения теплопроводности, не вда­ваясь в вопросы обоснования. Подробное изложение в применении к более широкому классу задач содержится в .

2.5.2. Рассмотрим прямую задачу. ПустьD — конечная область n-мерного евклидова пространства Rⁿ точек x = (x₁ ,x₂ , ..., x_n ), ограниченная кусочно-гладкой по­верхностью S, a t — время. Пусть, далее, j(x) — заданнаянепрерывная в D функция. Прямая задача состоит в на­хождении решения u= u (x,t) уравнения

(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ÎL₂ . Такая функция может и не соответст­вовать никакой «начальной» функции j(х). Таким обра­зом, может не существовать в классе функций С решения обратной задачи. Поэтому будем рассматривать задачу нахождения некоторого обобщенного решения обратной задачи.

Пусть заданы число T > 0 и функция y(x), опреде­ленная в областиD, y(x) ÎL₂ . На функциях j(х) класса С определен функционал

Обобщенным решением обратной задачи будем называть функцию j(х)., на которой достигается

f₀ =inf f(j)

jÎC

Замечание. «Естественный» подход к решению этой задачи — выбрать функцию j(х).так, чтобы f(j)=0 .

Для этого достаточно найти решение прямой задачи

u(x, t) = 0 для х Î S, 0 < t <T;

u(x,T) = y(x)

и положить j (x) = u(x,0). Но такая задача при задан­ной функции y(x) из L₂ , вообще говоря, неразрешима и, кроме того, неустойчива к малым изменениям функ­ции y(x).

На некотором классе обобщенных функций j (x) f₀ =0 . Поэтому рассматривается задача на­хождения приближенного значения f₀ с заданным уровнем погрешности.

Для заданного числаe > 0найти функциюj_e (x), на которойf(j_e )<=e.

Эта задача и решается методом квазиобращения.

Идея метода квазиобращения состоит в том, что вмес­то оператора теплопроводности находится «близ­кий» ему оператор В _a , для которого задача с обращением отсчета времени

B_a u_a = 0,xÎD, t < Т, a > 0;

u_a (x,T)= y(x);

u_a (x,t)= 0 для xÎ S, t< Т

устойчива. Решив эту задачу, полагают j (x)=u_a (x,0). Обычно в качестве оператора В _a берут оператор и решают прямую задачу

xÎ D, t<T, a>0;

u_a (x,T)= y(x);

u_a (x,t)= 0 для xÎ S, 0< t<= Т

Du_a =0 для xÎ S, 0< t<= Т.

Затем полагают

j (x)=u _a (x,0).

Следует отметить, что u _a не сходится в обычном смыс­ле при 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 не является компактом.

Пусть z_T есть решение уравненияAz =u_T , т. е. Az_T = u_T .Часто вместо u_T мы имеем некоторый элемент u_d и известное число d > 0 такие, что r_U (u_d ,u_T )<= d, т. е. вместо точных исходных данных (u_T ,А) мы имеем при­ближенные исходные данные (u_d , А) и оценку их погрешности d. Задача состоит в том, чтобы по известным исход­ным данным (u_d ,A, d) найти приближение z_d к элементу z_t ,обладающее свойством устойчивости к малым измене­ниям u_d . Очевидно, что в качестве приближенного реше­ния z_d уравнения (3; 0,1) нельзя брать точное решение этого уравнения с приближенной правой частью и = u_d , т. е. элемент z_T , определяемый по формуле

z_d =A^-1 u_d

так как оно существует не для всякого элемента u ÎU ине обладает свойством устойчивости к малым изменениям правой части и.

Числовой параметр d характеризует погрешность пра­вой части уравнения (3;0,1). Поэтому представляется естественным определить z_d с помощью оператора, зави­сящего от параметра, значения которого надо брать согла­сованными с погрешностью d исходных данных u_d . Эта согласованность должна быть такой, чтобы при d-0, т. е. при приближении (в метрике пространства U ) правой части u_d уравнения (3; 0,1) к точному значению u_T , при­ближенное решение z_d стремилось бы (в метрике прост­ранстваF) к искомому точному решениюz_t уравнения Az_T =u_T .

Пусть элементы z_T ÎF и u_T ÎU связаны соотношением Az_T = u_T .

Определение 1. Оператор R(и, d), действующий из пространства U в пространство F, называется регуля-ризирующим для уравнения A z = и (относительно эле­мента u_T ), если он обладает свойствами:

1) существует такое числоd1 > 0, что оператор R(u, d) определен для всякого d, 0<=d<=d1, и любого u_d ÎU такого, что

r_U (u_d ,u_T )<= d;

2) для всякого e > 0 существует d0=d0(e, u_d )<=d1 такое, что из неравенства

r_U (u_d ,u_T )<= d<= d0;

следует неравенство

r_F (z_d ,z_T )<= e,

где

z_d =R(u_d ,d).

Здесь не предполагается, вообще говоря, однозначность оператораR(u, d). Через z_d обозначается произвольныйэлемент из множества {R(u_d ,d)} значений оператора R(u_d ,d).

3.1.2. В ряде случаев целесообразнее пользоваться другим определением регуляризирующего оператора (P.O.).

Определение 2. Оператор R(u, a), зависящий от параметра a и действующий из U в F, называется регуляризирующим для уравнения A z =и (относительно эле­мента u_T ), если он обладает свойствами:

1) существуют такие числаd1>0, a1>0, что опера­торR(u, a) определен для всякого a, принадлежащего промежутку (0, a1), и любого uÎU, для которого

r_U (u,u_T )<=d1;

2) существует такой функционал a=a(u, d), опреде­ленный на множестве Ud₁ º{u; r(u,u_T )<= d1} эле­ментов и ÎU, что для любого e > 0 найдется число d(e)<=d1 такое, что если u¹ ÎU и r_U (u¹ ,u_T )<= d<= d(e), то

r_F (z_a ,z_T )<= e , где

z_a =R(u¹ , a(u¹ ,d)).

В этом определении не предполагается однозначность оператора R(u¹ , a(u¹ ,d)). Следует отметить, что при a= d получаем определение 1 .

3.1.3. Если r_U (u_d ,u_T )<= d, то известно, что в качест­ве приближенного решения уравнения (3; 0,1) с прибли­женно известной правой частью u_d можно брать элемент z_a =R(d, a), полученный с помощью регуляризирующе­го оператора R(u, a ), где a=a(u_d )=a1(d) согласовано с погрешностью исходных данных u_d . Это решение назы­вается регуляризованным решением уравнения (3; 0,1). Числовой параметр aназывается параметром регуляриза­ции. Очевидно, что всякий регуляризирующий оператор вместе с выбором параметра регуляризации a, согласо­ванного с погрешностью исходных данных u_d ,a=a(u_d ), определяет устойчивый к малым изменениям правой час­ти и метод построения приближенных решений уравнения (3;0,1). Если известно, что r_U (u_d ,u_T )<= d, то согласно определению регуляризирующего оператора можно так выбрать значение параметра регуляризации a=a(u_d ) ,

что при d-0 регуляризованное решение R(u_d ,a(u_d )) стремится (в метрике F) к искомому точному ре­шению z_T , т. е.r_F (z_T ,z_{a (u d )} ). Это и оправдывает пред­ложение брать в качестве приближенного решения урав­нения (3; 0,1) регуляризованное решение.

Таким образом, задача нахождения приближенного решения уравнения (3; 0,1), устойчивого к малым изме­нениям правой части, сводится:

а) к нахождению регуляризирующих операторов;

б) к определению параметра регуляризации aпо до­полнительной информации о задаче, например, по величи­не погрешности, с которой задается правая часть u_d .

Описанный метод построения приближенных решений называется методом регуляризации.

3.2. О решении вырожденных и плохо обусловленных систем линейных алгебраических уравнений

3.2.1. Известно, с какими трудностями связано решение так называемых плохо обусловленных систем линей­ных алгебраических уравнений: малым изменениям пра­вых частей таких систем могут отвечать большие (выхо­дящие за допустимые пределы) изменения решения.

Рассмотрим систему уравнений

А z = u , (3; 2,1)

где А — матрица с элементами a_ij , А ={a_ij }, z — иско­мый вектор с координатами z_j , z={z_j }, и — известный вектор с координатами и _i , u = {u_i }, i, j =1, 2, ..., п . Система (3; 2,1) называется вырожденной, если опреде­литель системы равен нулю, detA = 0. В этом случае матрица А имеет равные нулю собственные значения. У плохо обусловленных систем такого вида матрица А имеет близкие к нулю собственные значения.

Если вычисления производятся с конечной точностью, то в ряде случаев не представляется возможным уста­новить, является ли заданная система уравнений вырож­денной или плохо обусловленной. Таким образом, плохо обусловленные и вырожденные системы могут быть не­различимыми в рамках заданной точности. Очевидно, такая ситуация имеет место в случаях, когда матрица А имеет достаточно близкие к нулю собственные значения.

В практических задачах часто правая часть и и эле­менты матрицы А, т. е. коэффициенты системы (3; 2,1), известны приближенно. В этих случаях вместо системы (3; 2,1) мы имеем дело с некоторой другой системой Az=и такой, что ||A-A||<=h, ||u-u||<= d, где смысл норм обычно определяется характером задачи. Имея

вместо матрицы А матрицу A, мы тем более не можем высказать определенного суждения о вырожденности или невырожденности системы (3; 2,1).

В этих случаях о точной системе А z=u , решение которой надо определить, нам известно лишь то, что для матрицы А и правой части и выполняются неравенства

||A-A||<=h, ||u-u||<= d. Но систем с такими исходными данными (А, и) бесконечно много, и в рамках извест­ного нам уровня погрешности они неразличимы. Поскольку вместо точной системы (3; 2,1) мы имеем приближенную систему А z= и, то речь может идти лишь о нахождении приближенного решения. Но приближенная система А z =и может быть неразрешимой. Возникает вопрос:

что надо понимать под приближенным решением систе­мы (3; 2,1) в описанной ситуации?

Среди «возможных точных систем» могут быть и вы­рожденные. Если они разрешимы, то имеют бесконечно много решений. О приближенном нахождении какого из них должна идти речь?

Таким образом, в большом числе случаев мы должны рассматривать целый класс неразличимых между собой (в рамках заданного уровня погрешности) систем урав­нений, среди которых могут быть и вырожденные, и неразрешимые. Методы построения приближенных реше­ний систем этого класса должны быть одними и теми же, общими. Эти решения должны быть устойчивыми к малым изменениям исходных данных (3; 2,1).

В основе построения таких методов лежит идея «от­бора». Отбор можно осуществлять с помощью специальных, заранее задаваемых функционалов W[ z ] , входящих в постановку задачи.

Неотрицательный функционал W[ z ] , определенный на всюду плотном в F подмножестве F₁ множества F, называется стабилизирующим функционалом, если:

а) элемент z_T принадлежит его области определения;

б) для всякого числа d>0 множество F_1,d элементов z из F₁ , для которых

W[ z ]<=d, компактно на F.

3.2.2. Итак, рассмотрим произвольную систему линейных алгебраических уравнений (короче — СЛАУ)

Аz =u, (3; 2,2)

в которой z и u—векторы, z=(z₁ , z₂ , ...,z_n ) ÎRⁿ , и =(u₁ ,u₂ , ... ,u_n ) ÎR^m , А— матрица с элементами a_ij , А = {a_ij }, где j =1, 2, ..., n; i= 1, 2, ..., т, и число п не обязано быть равным числу т.

Эта система может быть однозначно разрешимой, вы­рожденной (и иметь бесконечно много решений) и не­разрешимой.

Псевдорешением системы (3; 2,2) называют вектор z, минимизирующий невязку || Az – u || на всем пространстве Rⁿ . Система (3; 2,2) может иметь не одно псевдоре­шение. Пусть F_A есть совокупность всех ее псевдореше­ний и z¹ — некоторый фиксированный вектор изRⁿ , оп­ределяемый обычно постановкой задачи.

Нормальным относительно вектора z¹ решением си­стемы (3;2,2) будем называть псевдорешение z⁰ с ми­нимальной нормой || z – z¹ ||, т. е. такое, что

|| z⁰ – z¹ || =

Здесь . В дальнейшем для простоты записи будем считать z¹ = 0 и нормальное относительно вектора z¹ =0 решение называть просто нормальным ре­шением.

Для любой системы вида (3; 2,2) нормальное решение существует и единст­венно.

Замечание 1. Нормальное решение z° системы (3;2,2) можно определить также как псевдорешение, минимизирующее заданную положительно определенную квадратичную форму относительно координат вектора z—z¹ . Все излагаемые ниже результаты остаются при этом справедливыми.

Замечание 2. Пусть ранг матрицы А вырожден­ной системы (3; 2,1) равен r < n и z_r+1 ,z_r+2 , … , z_n — базис линейного пространства N _A , состоящего из элемен­тов z, для которых А z = 0 , N_A = {z; А z = 0}. Решение z° системы (3; 2,1), удовлетворяющее n—r условиям ортогональности

(z⁰ – z¹ , z_S )= 0, S= r + 1, r + 2, .. ,n, (3; 2,3)

определяется однозначно и совпадает с нормальным ре­шением.

3.2.3. Нетрудно видеть, что задача нахождения нормаль­ного решения системы (3; 2,2) является некорректно поставленной. В самом деле, пусть А — симметричная матрица. Если она невырожденная, то ортогональным преобразованием

z = Vz*, u = Vu*

ее можно привести к диагональному виду и преобразо­ванная система будет иметь вид

l_i z_i *=u_i * , i= 1, 2,. ..,п,

где l_i — собственные значения матрицы А.

Если симметричная матрица А — невырожденнаяи имеет ранг r, то n – r ее собственных значений равны нулю. Пусть

l_i ¹0 для i=1, 2, ..., r;

и

l_i =0 для i=r+1,r+2, …, n.

Полагаем, что система (3; 2,2) разрешима. При этом u_i *= 0 для i =r + 1, ..., n.

Пусть «исходные данные» системы (А и и) заданы с погрешностью, т. е. вместо А и и заданы их прибли­жения А и u :

|| A – A ||<=h, ||u – u||<=d. При этом

(3;2,4)

Пусть l_i — собственные значения матрицы А. Извест­но, что они непрерывно зависят от А в норме (3; 2,4). Следовательно, собственные значения l_r+1 , l_r+2 , …,l_n могут быть сколь угодно малыми при достаточно малом h.

Если они не равны нулю, то

z_i *=.

Таким образом, найдутся возмущения системы в пре­делах любой достаточно малой погрешности А и и, для которых некоторые z_i * будут принимать любые наперед заданные значения. Это означает, что задача нахожде­ния нормального решения системы (3; 2,2) является неустойчивой.

Ниже дается описание метода нахождения нормального решения системы (3; 2,2), устойчивого к малым (в норме (3; 2,4)) возму­щениям правой части и , основанного на методе регуляризации.

3.3 . Метод регуляризации нахождения нормального решения

3.3.1. Пусть z° есть нормальное решение системы

А z = и. (3; 3,1)

Для простоты будем полагать, что прибли­женной может быть лишь правая часть, а оператор (матрица) А — точный.

Итак, пусть вместо и мы имеем вектор и, || и — и ||<=d ;т. е. вместо системы (3;3,1) имеем систему

Требуется найти приближение z_d к нормальному реше­нию системы (3;3,1), т. е. к вектору z° такое, что z_d -z° при d-0. Отметим, что векторы u и u (один из них или оба) могут не удовлетворять классическому ус­ловию разрешимости.

Поскольку система (3; 3,1) может быть неразреши­мой, то inf ||Az-u|| = m >=0, где inf берется по всем векторам zÎ Rⁿ .

Естественно искать приближения z_d в классе Q_d век­торов z, сопоставимых по точности с исходными данны­ми, т. е. таких, что || Az – u ||<=m+d. Но поскольку вместо вектора u мы имеем вектор u, то мы можем найти лишь

m=inf || Az – u ||.

zÎ Rⁿ

Отметим, что из очевидных неравенств

||Az – u ||<=||Az – u || + || u – u || ,

||Az – u ||<= || Az – u || + ||u – u ||

следуют оценки m<=m+d, m<=m+d, приводящие к не­равенству | m — m|<=d. Поэтому будем искать прибли­жение z_d к нормальному решению z° в классе Q_d векто­ров z, для которых ||А z — и || < = m+2d. Отметим, что если имеется информация о разрешимости системы (3;3,1), то m = 0 ив качестве класса Q_d можно брать класс векторов z, для которых ||А z — и | | < = d. Класс Q_d есть класс формально возможных приближенных решений.

Но нельзя в качестве z_d брать произвольный вектор из класса Q_d , так как такое «приближение» будет неустойчивым к малым изменениям правой части уравнения (3;3,2). Необходим принцип отбора. Он естественным образом вытекает из постановки задачи. В самом деле согласно определению нормального решения искомое ре­шение z° должно быть псевдорешением с минимальной нормой. Поэтому в качестве приближения к z° естествен­но брать вектор z_d из Q_d , минимизирующий функционал

W[ z ] = ||z||² на множестве Q_d .

Таким образом, задача сводится к минимизации функ­ционала W[ z ] = ||z||² на множестве Q_d векторов z, для которых выполняется условие || А z — u || <=m+2d.

3.3.2. Пусть z_d — вектор из Q_d , на котором функционал ||z||² достигает минимума на множестве Q_d . Его можно рассматривать как результат применения к правой части u уравнения (3; 3,2) некоторого оператора R₁ ( u , d), зависящего от параметра d. Справедлива

Теорема 1. Оператор R₁ (u, d) обладает следующи­ми свойствами:

1) он определен для всякогоu ÎR^m и любогоd > 0;

2 ) приd- 0 z _d == R₁ (u, d) стремится к нормальному решениюz ° уравнения Аz=u, т. е. он является регуляризирующим для уравнения Аz=u .

3.3.3. Пусть z_d — вектор, на котором функционал W[ z ] = ||z||² достигает минимума на множестве Q_d . Легко ви­деть из наглядных геометрических представлений, что вектор z_d лежит на границе множестваQ_d , т.е. ||Az_d - u ||=m+2d= d₁ .

Это следует непосредственно также из того, что функционал W[ z ] = ||z||² является сстабилизирующим и квазимонотонным. Стабилизирующий функционал W[ z ] называется квазимонотонным , если каков бы ни был элемент z из F₁ , не принадлежащий множеству M₀ , в любой его окрестности найдется элемент z₁ из F₁ , для которого W[ z₁ ]< W[ z ], т.е. если функционал не имеет локальных минимумов на множестве F₁ \ M₀ .

Задачу нахождения вектора z_d можно поставить так:среди векторов z, удовлетворяющих условию ||Az – u ||= m+2d, найти вектор z_d с минимальной нормой, т. е. минимизирующий функционал W[ z ]=||z||² .

Последнюю задачу можно решать методом Лагранжа, т. е. в качестве z_d брать вектор z^a , минимизирующий функционал

М^a [z, u] = ||Az - u ||² + a||z||² ,a>0,

с параметром a, определяемым по невязке, т. е. из ус­ловия ||Аz^a — u||=d1. При этом параметр aопределяется однозначно .

3.3.4. Поскольку М^a [z, u] — квадратичный функционал, то для любых u ÎR^m и a> 0 существует лишь один минимизирующий его вектор z^a . В самом деле, допустим,

что существуют два вектора z^a и z^a , минимизирующие его. Рассмотрим векторы z, расположенные на прямой (пространства Rⁿ ) , соединяющей z^a и z^a :

z = z^a + b(z^a -z^a ).

Функционал М^a [z, u] на элементах этой прямой есть неотрицательная квадратичная функция от b. Следова­тельно, она не может достигать наименьшего значения при двух различных значениях b: b = 0 (z= z^a ) иb=1 (z= z^a ).

Компоненты z_j ^a вектора z^a являются решением си­стемы линейных алгебраических уравнений

получающихся из условий минимума функционала М^a [z, u]:

Здесь

Компоненты z_j ^a могут быть определены и с помощью какого-нибудь другого алгоритма минимизации функцио­налаМ^a [z, u].

Вектор z^a можно рассматривать как результат приме­нения к u некоторого оператора z^a =R(u, a), завися­щего от параметра a.

Покажем, что оператор R₀ (u, a) является регуляризирующим для системы (3;3,1), т. е. обладает свойствами 1) и 2) определения 2 (см. 3.1.2.). В п. 3.3.2. было сказано, что он определен для всяких u ÎR^m и a> О и, следовательно, обладает свойством 1). Теперь пока­жем справедливость свойства 2), т. е. существование таких функций a=a(d) , что векторы z^a(d) = R₀ (u, a(d)) сходятся к нормальному решению z° системы (3; 3,1) при d-0. Это непосредственно следует из приводимой ниже теоремы 2.

Теорема 2( Тихонова). Пусть z° есть нормальное решение си­стемы Az=u и вместо вектора u мы имеем вектор u такой, что ||u—u||<=d. Пусть, далее,b1(d)и b2(d) — какие-либо непрерывные на [0, d2] и положительные на (0, d2] функции, монотонно стремящиеся к нулю при d- 0 и такие, что

Тогда для любой .положительной на (0, d2] функции a=a(d) , удовлетворяющей условиям

векторы z^a(d) = R₀ (u,a(d)) сходятся к нормальному ре­шению z⁰ системы Az = u при d-0, т. е.

Примечание. Доказательства теорем в данном разделе опущены, т.к. основной теоретической частью работы является раздел «Метод Подбора. Квазирешения». Метод Тихонова описан из-за использования его в численном эксперименте.

ЗАКЛЮЧЕНИЕ

Для реализации численного примера был выбран метод Тихонова решения плохо обусловленных СЛАУ. В качестве исходной была взята СЛАУ Az=u, имеющая в матричной записи вид:

Определитель матрицы коэффициентов этой системы близок к нулю – он равен 0.000125. Попробуем решить эту систему с помощью обратной матрицы:

z=A^-1 u

Получим z₁ =316

z₂ =-990

z₃ =832

Теперь предположим, что правая часть нам известна приближенно, с погрешностью 0.1 Изменим, к примеру, третий элемент вектора-столбца с 1 на 1.1 :

Попробуем решить новую систему также с помощью обратного оператора. Мы получаем другой результат:

z₁ =348

z₂ =-1090

z₃ =916.

Мы видим, что малому изменению правой части данной системы отвечают весьма значительные изменения решения. Очевидно, эта система – плохо обусловленная, и здесь не может идти речи о нахождении решения близкого к точному с помощью обратного оператора.

Будем искать решение методом Тихонова. В теоретической части было показано, что целесообразно использовать регуляризирующий оператор следующего вида: (aE + A^T A)z^a =A^T u_d , где E – единичная матрица, z^a -- приближенное нормальное решение, A^T – транспонированная исходная матрица, a -- параметр регуляризации,

u_d -- правая часть, заданная неточно. Эту задачу можно решать стандартными методами, задав предварительно функцию a=a(d) , удовлетворяющую условиям теоремы Тихонова. В моем примере это функция a(d)=d/4^d . Далее будем решать регуляризованную задачу с точностью e=0.001 ,последовательно изменяя значения a.

В качестве контр-примера можно подставить в программу любую функцию a(d) , не удовлетворяющую условиям теоремы Тихонова. Любая положительная функция монотонно возрастающая, не обладающая свойством a(d)-0 при d-0, не будет минимизировать невязку.

Текст программы приведен в приложении 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])<0.001) and (abs(U[2]-U1[2])<0.001) and

(abs(U[3]-U1[3])<0.001) then AllRight:=true

else AllRight:=false

end;

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;

Assign(f,'c:\tikh.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.