Ф.П. Васильев - Методы решения экстремальных задач (1125244), страница 34
Текст из файла (страница 34)
4. Следует, однако, отметить, что на практике погрешность задания исходных данных обычно бывает фнкснрованнон н не может быть сделана сколь угодно малой. В частности, условие стремления к нулю последовательности [6») нз (4) выполняется лишь в редких случаях н является весьма жестким требованием к задаче. В то же время при 6» ) 6) 0 равенства !нп (6»-)-е») я»' — 0 н 1цп я»=0 не» со » со совместимы, и бессмысленно требовать их выполнения.
В этом случае естественным образом возникает следующая проблема; как при фиксированном 6»=6)0 выбрать параметр регулярнзации я»=я=я(6) и точность е»=е=е(6), чтобы точка и» и(6) нз (2) была бы по возможности ближе к У„в нужной метрике ру В [17, 80, 105, 163) предлагаются н обсуждаются различные подходы к проблеме выбора параметра регуляризацин применительно к задачам минимизации функций вида / (и) = ! Аи †„з, связанным с уравнениями Аи= — Ь, где А — некоторый оператор, действующий из одного банахова пространства в другое банахово пространство. Для более широких классов задач мнннмнзанин эта проблема пока еще малоизучена. Поэтому мы здесь ограничимся некоторыми эвристическими соображениями по поводу выбора параметров метода Тихонова.
Сначала сделаем общее замечание, касающееся практического определения корректности нлн некорректности той нли иной задачи минимизации. За исключением известных классов некорректных задач [17, 80, 105, 1631, далеко не всегда ясно, будет ли рассматриваемая !90 задача корректной в требуемой метрике р или нет. Поэтому в таких случаях численное решение задачи минимизации, видимо, следует начинать не с использования метода стабилизации, а с более простых итерационных методов, пригодных, вообще говоря, для решения лишь задач первого типа. Предположим, что выбранный нами метод построения (и») оказался сходящимся и монотонным, т.
е. 1пп» (и»)= ь с» У (о») )»' (и»ы), й=1, 2, ... Пусть, кроме того, множество (у» состоит из единственной точки и,. Если задача корректна в метрике р, то последовательность (и») будет р-сходиться к и„ и можно ожидать, что расстояние р(ию и,„) при близких номерах я, т ведет себя «правильно», т.
е. не меняется резко и постепенно уменьшается Если же задача минимизации не является р-корректной, то возможны два случаю 1) последовательность (и») тем не менее ведет себя «правильно» вЂ” это может слунсить признаком того, что применяемый метод дает р-регулярную последовательность, и в этом случае, видимо, нет необходимости в использовании метода стабилизации или какого- либо другого метода регуляризации; 2) последовательность (и») ведет себя «неправильно», дает большой «разброс», т.
е. расстояние р(ию им) при близких я, и резко меняется и не имеет тенденции к убыванию при возрастании 1«, и†это явление «разброса» (и») может служить признаком некорректности задачи К сожалению, понятия «правильного» или «неправильного» поведения последовательности (и»), «разброса» (иа) вряд ли могут быть строго определены. Здесь можно лишь утешиться тем, что на практике упомянутые понятия выраба. тываются при решении большой серии однотипных задач минимизации, при анализе физического смысла параметров задачи и оказываются полезными при численном решении рассматриваемого класса задач.
Предположим, что при решении задачи минимизации выбранным методом мы заметили «разброс» (и»), н сделав вывод о некорректности задачи, далее воспользовались методом стабилизации Тогда выбор аь=п(6), е»=з(6) при фиксированном 6»=6)О, можно бы осуществить, например, следующи»г образом. Сначала задаемся не очень «малыми» числами з»=е, и»=и Затем начинаем дробить величину а, например, беря а»=п 2», /«=О, 1, ..., и при каждом таком а» н фиксированном е»=а из условия (2) определяем точки и», и,, ...
..., и», ... Этот процесс продолжаем до тех пор, пока не будет за. мечен «разброс» (и»). Появление «разброса» считаем признаком рассогласования в изменении величин (и»), (з»=з), (6»= 6). Пытаясь преодолеть «разброс», далее дробим з» =з (например, пополам) и при фиксированном новом значении за=а начинаем дробить полученную ранее величину ы, определяем точки (и») из условия (2) и т. д Таной процесс попеременного дробления а и е продолжаем до тех пор, пока с его помощью удается устранить явление «разброса» (и»).
Если дальнейшее дробление перестает устранять «разброс» (и»), то процесс прекращаем, считая, что при заданной точности 6»=6 получено «лучшее» согласование параметров ыь, е», Если достигнутый результат все же неудовлетворителен, то надо поточнее задать исходные данные, т. е.
обеспечить новое меньшее значение 6» =6 и снова повторить описанный процесс дробления с«, з и т. д. Выше мы предположили для простоты, что величины ч» из (5) равны нулю. Если же та =я ) О, то в процессе дробления, конечно, должна участвовать и величина ч, — для этого, разумеется, нужно обеспечить вычисление приближенных значений стабилизатора с любой требуемой относительной погрешнястью в смысле неравенства (5).
!9! Подчеркнем, что все рассуждения этого пункта не претендуют на какую-либо строгость и могут быть легко раскритикованы. Тем не менее изложенные эвристические соображения могут быть полезными при применении метода стабилизации для решения некорректных задач минимизации. Как видим, практическое использование метода стабилизации, вообще говоря, является непростым делом и может потребовать от вычислителя немалого искусства и терпения. Впрочем, то же самое можно сказать, пожалуй, о большинстве численных методов.
5. Остановимся на применениях метода Тихонова к некоторым классам задач минимизации. П р и м е р 1. Начнем с задачи минимизации функции ,/(и) = ) Аи — Ь)' (9) на множестве (/=Е", где А — матрица порядка тмп, Ь вЂ” вектор из Е . Эта задача тесно связана с линейной алгебраической системой уравнений Аи=Ь. (10) Л именно, если система (10) имеет хотя бы одно решение о„, то !п!,/(и) = /(и„) = / = О, и обратно, если ,/(гв) = /„=О, то ц„— решение системы (10). В том случае, когда /,=/(о ))О, точку и называют квазирешением системы (!0).
Покажем, что квазирешение всегда существует, т. е. функция (9) на Е" достигает своей нижней грани. Е(ля этого введем множество Ед=(щ оенЕ", о=Ам). Очевидно, Ед — подпространство в Ем. Как известно [70), любое подпространство в конечномерном евклидовом пространстве замкгтуто в евклидовой метрике. Поэтому Ед— замкнутое выпуклое множество в Е . По теореме 1А.2 тогда существует проекция Рь (6)=Ьд точки 6 на множество Ед, причем Ьд — Ь ортогоиально к множеству Ед, т. е. (Ьд — 6, Аи1= 0 для всех и ен Е", в частности, (Ьд — Ь, Ьд) =О. Условие Ьд найд означает, что существует точка о ен Е" такая, что Ао=Ьд. Нетрудно убедиться, что во всех точках е, удовлетворяющих системе уравнений Аи= Ьд, и только в них функция (9) достигает своей нижней грани на Е". В самом деле, /(и)=)Аи— — Ьд+Ьд — 6'а= Аи — 6д)'+2(Аи, Ьд — Ь/ — 2(Ьд, Ьд— — Ь)+, 'Ьд — 6.'=) Аи — Ьд )а+!Ьд — Ь)е =: ) Ьд — Ь)а=~ Ас— — Ь)'=./(о) ггрг~ всех и е-=Е" Отсюда следует, что ./„=- =,/(и) и множество точек минимума (/в =(и: и енЕ", Р92 у (и) = с „) непусто, и, более того, У„= | и: и»:— Е", А и= =Ьл) — гиперплоскость размерности и — г, где г=гапдЛ.
Рассмотрим задачу отыскания точки и» е-:1/», ближе все»о расположенной к задан» ой точке и ~ Е". Иначе говоря, будем искать Й-»»ормальное решение задачи минимизации функции (9) при условии, что О(и)=|и — й|'. Так как (с', — выпуклое замкнутое множество, а 0 (и)— сильно выпуклая функция, то Й-нормаль»»ое решение и, существует и единственно. Пусть вместо матрицы А и вектора Ь известны лишь их приближения А», Ь», причем ||А» — А|| =.и», |Ь» — Ь!~о», юг=1, 2, ..., 1(ш о» =-0 » оэ (11) Тогда вместо точной функции У(и) нам придется иметь дело с ее приближением с» (и) = | А»сс — Ь» |». Как было показано в 9 3 (см. пример 3.1 и упражнение 3.3), в этом случае задача определения 11-нормального решения, вообще говоря, будет некорректной.
Покажем, что для решения этой задачи может быть применен описанный выше метод стабилизации. Прежде всего заметим, что функции с (и), 11(и) удовлетворя»от условиям 1), 2) леммы 4.2 при В= Е". Далее покажем, что погрешность |,с' (и) — с'» (и) | согласована со стабилизатором 11 (и) в смысле неравенства (4). С учетом (11) имеем |.с»(и) — с (и) |( ( | ((А„— А) и+ (Ь вЂ” Ь,), (А»+ А) и — (Ь+ Ь»)с | ==. ( (о» | и |+ о») ((|| А, | + || А |1) | и |+ | Ь | + | Ь» ,') = ( и» (1+ | и |) 1(2 ( А ||+ и„) | и | + 2 | Ь! + о»1 =.
о» (1+|и |) 2 (( А | + | Ь ! + о»). Но 1+ | и | == 1+ | и |+ | и — и» ( (1+» и |) (1+ | и — й |) =" ~ 2 (1+ | й |) (1+ |и — и |'), так что | /» с(сс) — у (и) |.=с- б» х х (1+»1 (и)), где б„= 4 (1+ | и |) (| А 1+ | Ь |+ о») о„, й = =1, 2, ..., и~Е". Составим функцию Тихонова Т, (и) = | Л»и — Ь»!»+а»х х',и — и|', й=1, 2, ... С помощьш какого-либо метода минимизации прн ка»кдом 1=1, 2, ... определим точку и»»-:Е" из услоьия Т» (и„) ( 1п1 Т» (и) - |- е». Е" 7 Ф.
П. В»сссль»» а гь »2 У (и) = ) ~~ А (з, 1) и (1) г(1 — Ь (з)) г(э с а (14) на множестве (/=Е»[а, Ь), где [а, Ь), [с, г() — заданные отрезки, Ь(з) ~7.»[с, о1, А(з, 1) яЕ»Я), Я=((з, 1): с( (з-=.г(, а(1(Ь). Зта задача тесно связана с интегральным уравнением Фредгольма первого рода ь ~ А(з, 1) и(()Й=Ь(з), с~з(д, (15) а и является некорректной в метрике Ла[а, Ь1 (см.
упражнения 1,4 и 1.5). Как известно (см., например, [17, 1051), уравнение (15), в общем случае, не имеет решения при каждом Ь(з) енй,[с, с»), а функция (14) достигает своей нижней грани не при всех Ь(з) а= Е,[с, о!. Чтобы задача второго типа имела смысл для функции (14), мы будем предполагать, что при заданных А (з, 1), Ь(з) множество Уа = (и=и(1): и(1) енЕ»[а, Ь), У(и)=(пав/(и)) непусто. Поскольку У (и) выпукла и непрерыгна в метрике Е,[а, Ь), то У, выпукло и замкнуто в этой метрике, Кроме того, согласно теореме 1.3.5, тогда l(и) слабо 194 Если (е,), (и»), (о„) будут стремиться к нулю, причем !пп (е»+о,)а»' =-0 (считаем, что т, из (5) равен нулю » сю при всех й), то получаемая из (12) последовательность (и») сходится к»»-нормальному решению иа.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
