реферат, рефераты скачать Информационно-образоательный портал
Рефераты, курсовые, дипломы, научные работы,
реферат, рефераты скачать
реферат, рефераты скачать
МЕНЮ|
реферат, рефераты скачать
поиск
Методы решения некорректно поставленных задач

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

ВВЕДЕНИЕ

Среди математических задач выделяется класс задач, решения которых

неустойчивы к малым изменениям исходных данных. Они характеризуются тем,

что сколь угодно малые изменения исходных данных могут приводить к

произвольно большим изменениям решений. Задачи подобного типа, по существу,

являются плохо поставленными. Они принадлежат к классу некорректно

поставленных задач.

Быстро растущее использование вычислительной техники требует развития

вычислительных алгоритмов для решения широких классов задач. Но что надо

понимать под «решением» задачи? Каким требованиям должны удовлетворять

алгоритмы нахождения « решений »?

Классические концепции и постановки задач не отражают многих

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

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

Az=u,

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

с элементами aij.

Если система невырожденная, т. е. detA ? 0, то она имеет единственное

решение, которое можно найти по известным формулам Крамера или другими

способами.

Если система вырожденная, то она имеет решение (притом не единственное)

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

ответствующих определителей.

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

или нет. Для этого требуется вычислить определитель системы detA.

Если п — порядок системы, то для вычисления detА требуется выполнить

около п3 операций. С какой бы точностью мы ни производили вычисления, при

достаточно большом значении п, вследствие накопления ошибок вычисления, мы

можем получить значение detА, как угодно отличающееся от истинного. Поэтому

желательно иметь (построить) такие алгоритмы нахождения решения системы,

которые не требуют предварительного выяснения вырожденности или

невырожденности системы.

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

матрицы А,

т. е. коэффициенты системы уравнений, известны нам приближенно. В этих

случаях вместо системы, мы имеем дело с некоторой другой системой A1z=u1

такой, что

||А1— А|| О можно указать такое число ? (?) > 0, что из неравенства ?U(u1,u2)0. Такой элемент мы будем называть приближенным (к

zT) решением уравнения Az = и1.

Элементы z?F, удовлетворяющие условию ?U(Az, и1)0

при n>?. При каких условиях можно утверждать, что при этом и ?F(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=?(z) осуществляет прямое отображение

F>U, а функция z=?(u)—обратное отображение U>F.

Возьмем произвольный элемент u0 из Uo. Покажем, что функция ?(u) непрерывна

на u0. Предположим, что это неверно. Тогда существует такое число ?1 > 0,

что для всякого ? > 0 найдется элемент и1 из Uo, для которого ?U(и1, и0)

= ?1. Здесь z=?(u1), z0=?(u0) и z1?Fo,

z0?F0.

Возьмем последовательность {?n} положительных чисел ?n , сходящуюся к нулю

при п>?. Для каждого ?n найдется элемент un1 из Uo, для которого ?U(иn1,

и0)< ?n , но ?F(zn1,z0)>= ?1 , где zn1=?(un1). Очевидно, последовательность

{un1} сходится к элементу u0. Так как zn1 принадлежат компактному на F

множеству Fo, то из последовательности {zn1} можно выбрать

подпоследовательность {Z1nk}, сходящуюся по метрике F к некоторому элементу

z0 ?F. При этом z01?z0 , так как для всякого nk ?F(Z1nk,z0)>= ?1 ,

следовательно и ?F(z10,z0)>= ?1 . Этой подпоследовательности {Z1nk}

отвечает последовательность элементов u1nk= ? (Z1nk) из Uo, сходящаяся к

u10= ?(z10) и являющаяся подпоследовательностью последовательности {u1n}.

Так как последовательность {u1n} сходится к и0 =?(z0), то

u10=?(z10)=u0=?(z0) , т. е. ?(z0)= ?(z10). В силу взаимной однозначности

отображения F>U z10=z0, что противоречит ранее установленному неравенству

z10?z0. Лемма доказана.

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

Если отображение Fo(Uo компакта Fo на множество Uo взаимно однозначно

и непрерывно, то обратное отображение Uo(Fo также непрерывно.

Эквивалентность этих формулировок следует из того, что замыкание F*0

множества Fo, компактного на F, является компактом.

Таким образом, минимизирующая последовательность {zn} в методе подбора

сходится к zT при n(?, если:

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

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

Пусть оператор А непрерывен и вместо точной правой части uT мы имеем

элемент u? такой, что ?U(u?,uT )=?2>=…>=?n>=… — полная система его собственных

значений, a ?1, ?2,…, ?n,…—отвечающая им полная ортонормированная система

его собственных элементов (функций, векторов). Элемент А*и можно

представить в виде ряда

[pic]

(2;2,2)

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

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

формулами:

[pic]

(2;2,3)

если

[pic]

(2;2,4)

и

[pic]

если

[pic]

(2;2,5)

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

[pic] (2;2,6)

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

?U2 (Az, u) == (Az — u, Az — u)

(2;2,7)

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

Эйлера для которого имеет вид

A*Az=A*u.

(2;2,8)

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

[pic]

(2;2,9)

Подставляя этот ряд в уравнение (2; 2,8) и используя разложение (2;2,2),

находим сn=bn/?n. Следовательно, неравенство (2; 2,4) означает, что ||z||=R и надо решать задачу на условные экстремум функционала (2; 2,7)

при условии, что || z ||2 = R2. Методом неопределенных множителей Лагранжа

эта задача сводится к нахождению безусловного экстремума функционала

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

а последняя — к решению отвечающего ему уравнения Эйлера A*Az+?z=А*и.

Подставляя сюда z в виде ряда (2; 2,9) и используя разложение (2; 2,2),

находим

[pic]

Параметр ? определяем из условия || z ||2 = R2 , которое эквивалентно (2;

2,6).

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

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

с нахождением элемента в бесконечномерном пространстве. Для приближенного

нахождения квазирешения естественно переходить к конечномерному

пространству. Можно указать достаточно общий подход к приближенному

нахождению квазирешений уравнения (2; 0,1) , в котором А—вполне непрерывный

оператор.

Будем полагать, что выполнены указанные в 2.2. достаточные условия

существования единственного квазирешения на заданном множестве М, т. е.

полагаем, что множество М — выпуклый компакт и сфера в пространстве U

строго выпукла. Пусть

M1 ? M2 ?...? Mn ?...

— возрастающая цепочка компактных замкнутых множеств Мn такая, что

замыкание их объединения [pic] совпадает с М. Квазирешение уравнения (2;

0,1) существует на каждом множестве Мn . Но оно может быть не единственным.

Обозначим через Тn совокупность всех квазирешений на множестве Мn .

Покажем, что в качестве приближения к квазирешению z1 на множестве М

можно брать любой элемент z1n из Тn . При этом

[pic]

Пусть Nn = АМn и Вn — множество проекций элемента и на множество Nn .

Очевидно, что Вn = АТn и N1 ? N2 ? …? Nn; тогда

? U(u,N1)>= …>=? U (u,Nn)>=… ? U (u,N)= ? U (u,Az1) .

(2;3,1)

Так как множество [pic]всюду плотно на N, то для всякого ? >0 найдется

такое число n0(?), что для всех п >n0(?)

?U(u,Nn)< ?U(u,N)+ ?

(2; 3,2)

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

[pic] (2;3,3)

Поскольку

то

[pic]

[pic]

(2;3,4)

Каждое множество Вn есть компакт, так как оно является замкнутым

подмножеством компакта Nn. Поэтому в Вn найдется такой элемент уn , что

?U(yn ,u) = inf ?U(y,u)

y?Bn

Последовательность {yn} имеет хотя бы одну предельную точку,

принадлежащую N, так как N — компакт. Пусть у0 — какая-нибудь предельная

точка множества {yn} и {уnk} — подпоследовательность, сходящаяся к y0 , т.

е.

[pic]

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

[pic]

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

?U(u,y0)= ?U(u,N).

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

y0=Az1.

Так как у0 — произвольная предельная точка множества {yn}, то

последовательность {уn} сходится к Аz1. Это и означает, что в качестве

приближения к квазирешению можно брать любой элемент z1n из множества Тп ,

так как в силу леммы параграфа 2.1. z1n(z* при n(?.

Если в качестве Мп брать конечномерные (n-мерные) множества, то задача

нахождения приближенного квазирешения на компакте М сводится к минимизации

функционала ?U(Az, u) на множестве Мп , т. е. к нахождению минимума функции

п переменных.

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

Уравнения вида (2; 0,1), в которых правая часть u не принадлежит

множеству N=AM, изучались М. М. Лаврентьевым . Ему принадлежит идея замены

исходного уравнения (2; 0,1) близким ему, в некотором смысле, уравнением,

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

части и разрешима для любой правой части u ?U. В простейшем случае это

делается следующим образом.

Пусть F ?U ?Н — гильбертовы пространства, А — линейный, ограниченный,

положительный и самосопряженный оператор, SR ? 0. В качестве класса корректности М берется множество

DR=BSR — образ шара SR при отображении с помощью оператора В.

Предполагается, что искомое точное решение zT уравнения (2; 0,1) с правой

частью u=uT существует и принадлежит множеству DR. Уравнение (2; 0,1)

заменяется уравнением

(A+?E)z ? Az+?z=u ,

(2:4,1)

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

z?=(A+?E)-1u ,

(2; 4,2)

при соответствующем выборе параметра ?, принимается за приближенное решение

уравнения (2; 0,1). Здесь Е — единичный оператор.

Замечание. Для оценки уклонения ?F(zT,z?) приближенного решения от

точного можно использовать модуль непрерывности ? обратного оператора на N.

Пусть u1, u2 ? N и ?U(u1,u2) 0}, удовлетворяющего граничным условиям

u(х, t) =0 при x?S

(2; 5,2)

и начальным условиям

u(x, 0)= ?(x).

(2; 5,3)

Здесь

[pic]

Известно, что решение такой задачи существует. Каждой функции ?(x)?C

отвечает решение задачи (2; 5,1)— (2; 5,3). Будем обозначать его через u(х,

t; ?).

Обратная задача состоит в нахождении функции ?(х) по известной функции

u(х,t; ?). В реальных задачах функция u(x,t;?) обычно получается в

результате измерений и, следовательно, известна приближенно. Будем

полагать, что u?L2. Такая функция может и не соответствовать никакой

«начальной» функции ?(х). Таким образом, может не существовать в классе

функций С решения обратной задачи. Поэтому будем рассматривать задачу

нахождения некоторого обобщенного решения обратной задачи.

Пусть заданы число T > 0 и функция ?(x), определенная в области D,

?(x) ?L2. На функциях ?(х) класса С определен функционал

[pic]

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

которой достигается

f0=inf f(?)

??C

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

?(х).так, чтобы f(?)=0 .

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

[pic]

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

u(x,T) = ?(x)

и положить ? (x) = u(x,0). Но такая задача при заданной функции ?(x) из L2,

вообще говоря, неразрешима и, кроме того, неустойчива к малым изменениям

функции ?(x).

На некотором классе обобщенных функций ? (x) f0=0 . Поэтому

рассматривается задача нахождения приближенного значения f0 с заданным

уровнем погрешности.

Для заданного числа ? > 0 найти функцию ??(x), на которой f (??) 0;

u? (x,T)= ?(x);

u? (x,t) = 0 для x? S, t< Т

устойчива. Решив эту задачу, полагают ? (x)=u?(x,0). Обычно в качестве

оператора В? берут оператор [pic] и решают прямую задачу

x? D, t0;

[pic]

u? (x,T)= ?(x);

u? (x,t) = 0 для x? S, 0< t 0 такие, что

?U(u?,uT) 0, что оператор R(u, ?) определен для

всякого ?, 0 0 существует ?0=?0(?, u?)0, ?1>0, что оператор R(u, ? ) определен

для всякого ?, принадлежащего промежутку (0, ?1), и любого u?U, для

которого

?U(u,uT) 0 найдется число

?(?)0 множество F1,d элементов z из F1 , для

которых

?[ z ]=0, где inf берется по всем векторам z ? Rn.

Естественно искать приближения z? в классе Q? векторов z,

сопоставимых по точности с исходными данными, т. е. таких, что || Az – u

|| 0;

2) при ? (0 z?== R1(u, ?) стремится к нормальному решению z°

уравнения Аz=u, т. е. он является регуляризирующим для уравнения Аz=u .

3.3.3. Пусть z? — вектор, на котором функционал ?[ z ] = ||z||2

достигает минимума на множестве Q?. Легко видеть из наглядных

геометрических представлений, что вектор z? лежит на границе множества Q?,

т.е. ||Az? - u ||=? +2? =?1.

Это следует непосредственно также из того, что функционал ?[ z ] = ||z||2

является сстабилизирующим и квазимонотонным. Стабилизирующий функционал ?[

z ] называется квазимонотонным , если каков бы ни был элемент z из F1 , не

Страницы: 1, 2



© 2003-2013
Рефераты бесплатно, рефераты литература, курсовые работы, реферат, доклады, рефераты медицина, рефераты на тему, сочинения, реферат бесплатно, рефераты авиация, курсовые, рефераты биология, большая бибилиотека рефератов, дипломы, научные работы, рефераты право, рефераты, рефераты скачать, рефераты психология, рефераты математика, рефераты кулинария, рефераты логистика, рефераты анатомия, рефераты маркетинг, рефераты релиния, рефераты социология, рефераты менеджемент.