Методы решения некорректно поставленных задач. Методы_решения_некорректно_поставленных_задач_-_StudentLib. Рассмотрим систему линейных алгебраических уравнений

• Название: Рассмотрим систему линейных алгебраических уравнений
• Анкор: Методы решения некорректно поставленных задач
• Дата: 13.07.2022
• Размер: 270.5 Kb.
• Имя файла: Методы_решения_некорректно_поставленных_задач_-_StudentLib.com[1.doc
• Тип: Документы; #630246
• страница: 1 из 4

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

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

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

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

Az=u,

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

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

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

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

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

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

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

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

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

Поскольку вместо точной системы мы имеем приближенную систему 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), если для любого числа  > О можно указать такое число  () > 0, что из неравенства _U(u₁,u₂)<= () следует _F(z_1,z₂)<=, где 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) известна с точностью , т. е. вместо ее точного значения u_T нам известны элемент и¹ и число  такие, что _U(u_T,u¹)<=. По этим данным, т. е. по (u¹, ), требуется найти такой элемент z_ , ко­торый стремился бы (в метрике F) к z_T при 0. Та­кой элемент мы будем называть приближенным (к z_T) решением уравнения Az = и¹.

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

(и¹, ).

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

_U(Az₀,u)=inf _U(Az,u)

zM

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

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

Пусть {z_n} — последовательность элементов, для ко­торой _U(Az_n,u)0 при n. При каких условиях можно утверждать, что при этом и _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=(z) осуществляет прямое отображение FU, а функция z=(u)—обратное отображение UF.
Возьмем произвольный элемент u₀ из Uo. Покажем, что функция (u) непрерывна на u₀. Предположим, что это неверно. Тогда существует такое число ₁ > 0, что для всякого  > 0 найдется элемент и¹ из Uo, для которого _U(и¹, и₀) <, в то время как _F(z¹,z₀)>=₁. Здесь z=(u¹), z₀=(u₀) и z¹Fo, z₀F₀.

Возьмем последовательность {_n} положительных чи­сел _n , сходящуюся к нулю при п. Для каждого _n найдется элемент u_n¹ из Uo, для которого _U(и_n¹, и₀)< _n , но _F(z_n¹,z₀)>=₁ , где z_n¹=(u_n¹). Очевидно, последова­тельность {u_n¹} сходится к элементу u₀. Так как z_n¹ при­надлежат компактному на F множеству Fo, то из после­довательности {z_n¹} можно выбрать подпоследовательность {Z¹n_k}, сходящуюся по метрике F к некоторому элементу z₀ F. При этом z₀¹z₀ , так как для всякого n_k_F(Z¹n_k,z₀)>=₁ , следовательно и _F(z¹₀,z₀)>=₁ . Этой подпоследовательности {Z¹n_k} отвечает последователь­ность элементов u¹n_k= (Z¹n_k) из Uo, сходящаяся к u¹₀=(z¹₀) и являющаяся подпоследовательностью по­следовательности {u¹_n}. Так как последовательность {u¹_n}сходится к и₀ =(z₀), то u¹₀=(z¹₀)=u₀=(z₀) , т. е. (z₀)=(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_ такой, что _U(u_,u_T )<=, причем u_ принадлежит множеству AM (образу множест­ва М при отображении его с помощью оператора A) и М есть компакт. Пусть {_n} — последовательность поло­жительных чисел таких, что _n 0 при nоо. Для каж­дого п методом подбора можно найти такой элемент z^_n , что _U(A z^_n ,u_)<=_n . Элементы z^_n будут близки к ре­шению z_T уравнения Az=u_T. В самом деле, при отобра­жении с помощью непрерывного оператора образ AM компакта М есть компакт и, следовательно, по лемме обратное отображение, осуществляемое оператором A^-1, непрерывно на AM. Так как
_U(A z^_n ,u)<=_U(A z_n ,u_)+_U(u_,u_T),

то

_U(A z^_n ,u_T)<=_n+=^_n.

Из этого неравенства и из непрерывности обратного отображения АМ М следует, что _F(z^_n ,z_T)<=(^_n) , причем (^_n)0 при ^_n0. Таким образом, при нахож­дении приближения z^_n к z_T надо учитывать уровень по­грешности  правой части u_.

2.1.3. На основе изложенных соображений М. М. Лав­рентьев сформулировал понятие корректности по Тихонову. В применении к уравнению (2; 0,1) задача на­зывается корректной по Тихонову, если известно, что для точного значения u=u_T существует единственное реше­ние z_T уравнения (2; 0,1), Az_T=u_T, принадлежащее за­данному компакту М. В этом случае оператор А^-1 непре­рывен на множестве N=AM и, если вместо элемента u_T нам известен элемент u_ такой, что _U( u_T, u_)<= и u_N, то в качестве приближенного решения уравнения (2; 0,1) с правой частью u= u_ можно взять элемент z_=A^-1u_ . При 0 (u_N) z_ будет стремиться к 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 .

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

|| A₁z_ – u¹ ||²_L2<= ² . (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)?

В этом случае вводится понятие квазирешения и метод подбора при условии компактности множества М позво­ляет найти приближение к квазирешению. В следующем параграфе вопрос о квазирешении рассматривается под­робнее.