Методы решения некорректно поставленных задач
Другие рефераты
Среди математических задач выделяется класс задач, решения которых неустойчивы к малым изменениям исходных данных. Они характеризуются тем, что сколь угодно малые изменения исходных данных могут приводить к произвольно большим изменениям решений. Задачи подобного типа, по существу, являются плохо поставленными. Они принадлежат к классу некорректно поставленных задач. Быстро растущее использование вычислительной техники требует развития вычислительных алгоритмов для решения широких классов задач. Но что надо понимать под «решением» задачи? Каким требованиям должны удовлетворять алгоритмы нахождения « решений »? Классические концепции и постановки задач не отражают многих особенностей встречающихся на практике задач. Мы покажем это на примере. Рассмотрим систему линейных алгебраических уравнений Az=u, где z — искомый вектор, и — известный вектор, А ={aij} — квадратная матрица с элементами aij. Если система невырожденная, т. е. detA ? 0, то она имеет единственное решение, которое можно найти по известным формулам Крамера или другими способами. Если система вырожденная, то она имеет решение (притом не единственное) лишь при выполнении условий разрешимости, состоящих из равенств нулю со- ответствующих определителей. Таким образом, прежде чем решить систему, надо проверить, вырожденная она или нет. Для этого требуется вычислить определитель системы detA. Если п — порядок системы, то для вычисления detА требуется выполнить около п3 операций. С какой бы точностью мы ни производили вычисления, при достаточно большом значении п, вследствие накопления ошибок вычисления, мы можем получить значение detА, как угодно отличающееся от истинного. Поэтому желательно иметь (построить) такие алгоритмы нахождения решения системы, которые не требуют предварительного выяснения вырожденности или невырожденности системы. Кроме того, в практических задачах часто правая часть u и элементы матрицы А, т. е. коэффициенты системы уравнений, известны нам приближенно. В этих случаях вместо системы, мы имеем дело с некоторой другой системой A1z=u1 такой, что ||А1— А||<=h, ||u1-u||<=?, где смысл норм обычно определяется характером задачи. Имея вместо матрицы А матрицу А1, мы тем более не можем высказать определенного суждения о вырожденности или невырожденности системы. В этих случаях о точной системе Az = и нам известно лишь то, что для матрицы А и правой части и выполняются неравенства || А1—А || <= h и || и1—и|| <=?. Но систем с такими исходными данными (А, и) бесконечно много, и в рамках известного нам уровня погрешности они неразличимы. Среди таких «возможных точных систем» могут быть и вырожденные. Поскольку вместо точной системы мы имеем приближенную систему A1z=и1, то речь может идти лишь о нахождении приближенного решения. Но приближенная система может быть и неразрешимой. Возникает вопрос: что надо понимать под приближенным решением системы? Оно должно быть также устойчивым к малым изменениям исходных данных (А, и). В данной работе будет введено понятие приближенного решения некорректно поставленных задач, а также будет рассмотрено несколько методов нахождения таких решений. 1. ПОНЯТИЕ КОРРЕКТНО ПОСТАВЛЕННЫХ И НЕКОРРЕКТНО ПОСТАВЛЕННЫХ ЗАДАЧ 1.1. Различают корректно поставленные, и некорректно поставленные задачи. Понятие корректной постановки задач математической физики было введено Ж. Адамаром в связи с желанием выяснить, какие типы граничных условий наиболее естественны для различных типов дифференциальных уравнений (для эллиптических, например,— задача Дирихле и ей аналогичные, для гиперболических — задача Коши). Решение всякой количественной задачи обычно заключается в нахождении «решения» z по заданным «исходным данным» и, z=R(u). Мы будем считать их эле- ментами метрических пространств F и U с расстояниями между элементами [pic]; u1, u2?U; z1,z2?F. Метрика обычно определяется постановкой задачи. 1.2. Пусть определено понятие «решения» и каждому элементу и?U отвечает единственное решение z=R(u) из пространства F. Задача определения решения z=R(u) из пространства F по исходным данным и?U называется устойчивой на пространствах (F, U), если для любого числа ? > О можно указать такое число ? (?) > 0, что из неравенства ?U(u1,u2)<= ? (?) следует ?F(z1,z2)<= ?, где z1=R(u1), z2=R(u2); u1,u2?U; z1,z2?F. Задача определения решения z из пространства F по «исходным данным» и из пространства U называется корректно поставленной на паре метрических пространств (F, U), если удовлетворяются требования (условия): 1) для всякого элемента и ?U существует решение z из пространства F, 2) решение определяется однозначно; 3) задача устойчива на пространствах (F, U). В математической литературе длительное время существовала точка зрения, согласно которой всякая математическая задача должна удовлетворять этим требованиям . Задачи, не удовлетворяющие перечисленным требованиям, называются некорректно поставленными. Следует отметить, что определение некорректно поставленных задач относится к данной паре метрических пространств (F, U), так как в других метриках та же задача может быть корректно поставленной . 1.3. Задача нахождения приближенного решения некорректно поставленной задачи вида Az = и, и? U, (1; 3,1) в естественном классе элементов F является практически недоопределенной. Эта задача является некорректно поставленной, например, в случаях, когда А — вполне непрерывный оператор. Тогда обратный ему оператор A-1 вообще говоря, не будет непрерывным на U и решение уравнения (1; 3,1) не будет устойчивым к малым изменениям правой части и (в метрике пространства U). Исходными данными здесь являются правая часть уравнения u и оператор А. Предположим, что оператор А нам известен точно, а правая часть уравнения (1; 3,1) известна с точностью ?, т. е. вместо ее точного значения uT нам известны элемент и1 и число ? такие, что ?U(uT,u1)<= ?. По этим данным, т. е. по (u1, ?), требуется найти такой элемент z? , который стремился бы (в метрике F) к zT при ?>0. Такой элемент мы будем называть приближенным (к zT) решением уравнения Az = и1. Элементы z?F, удовлетворяющие условию ?U(Az, и1)<= ?, будем называть сопоставимыми по точности с исходными данными (и1, ?). Пусть Q?—совокупность всех таких элементов z ?F. Естественно приближенные решения уравнения Az=и1 искать в классе Q? элементов z , сопоставимых по точности с исходными данными (и1, ? ). Однако в ряде случаев этот класс элементов слишком широк. Среди этих элементов есть такие, которые могут сильно отличаться друг от друга ( в метрике пространства 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, т. е. решается прямая задача. В качестве приближенного решения берется такой элемент z0 из множества М, на котором невязка ?U(Az,u) достигает минимума, т. е. ?U(Az0,u)=inf ?U(Az,u) z?M Пусть правая часть уравнения (2;0,1) известна точно, т. е. и=uT, и требуется найти его решение zT. Обычно в качестве М берется множество элементов z, зависящих от конечного числа параметров, меняющихся в ограниченных пределах так, чтобы М было замкнутым множеством конечномерного пространства. Если искомое точное решение zT уравнения (2; 0,1) принадлежит множеству М, то [pic] и достигается эта нижняя граница на точном решении zT. Если уравнение (2;0,1) имеет единственное решение, то элемент z0, минимизирующий ?U(Az,и), определен однозначно. Практически минимизация невязки ?U(Az,и) производится приближенно и возникает следующий важный вопрос об эффективности метода подбора, т. е. о возможности как угодно приблизиться к искомому точному решению. Пусть {zn} — последовательность элементов, для которой ?U(Azn,u) >0 при n>?. При каких условиях можно утверждать, что при этом и ?F(zn,zT) >0, т. е. что {zn} сходится к zT? Это вопрос обоснования эффективности метода подбора. 2.1.2. Стремление обосновать успешность метода подбора привело к установлению общефункциональных требований, ограничивающих класс возможных решений М, при которых метод подбора является устойчивым и zn>zT. Эти требования заключаются в компактности множества М и основываются на приводимой ниже известной топологической лемме. Лемма. Пусть метрическое пр
| |  скачать работу |
Другие рефераты
|
