автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.16, диссертация на тему:Оптимизация методов решения линейных условно-корректных задач

:3 а-

шшстерство зысшего и среднего специального '..образования розср новосибирски* ордш трудового' красного знаг.тени государственна университет изюм ленинского комсомола

На лравах рукописи

боярша нина сергеев11л

УДК.517.У48

оптимизация методов решения линейных •

УСЛОБНО-ШРЕСТШХ ЗАДАЧ ■

Специальность 05.13.16 - применений вычислительной техники,

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

Автопеферат

диссортацин на соискание умелой степени кандидата физико '.етег'чгкче^ких наук

Работа выполнена в Новосибирском ордена Трудового Красного, Знамени государственном университете игл. Ленинского комсомола.'' •

Научные руководители - доктор физико-математических наук,

профессор ю.Е.Акиконов, - кандидат'физико-математических наук А.Г.Марчук Официальные оппоненты - доктор физико-математических наук

Г.Н.Ерохин

кандидат физико-математических наук • Ю.Н.Валицкий

Ведущая организация - Московский ордена Ленина, ордена Октябрьской Революции и- ордена Трудового Красного Знамени университет им. М.^.Ломоносова, НИВЦ.

Защита состоится "ЛГ" 1990 года в

часов нй заседании специализированного совета К.063.98.05 по принуждению учено!! степени кандидата физико-математических наук при Новосибирском государственном университете им. Ленинского комсомола по аяресу: 030050, г.Новосибирск, 90, ул. Пирогова, 2.

С диссертацией глокно ознакомиться в библиотеке Новосибирского государственного университета.

Автореферат разослан "^У" й.&ЩётсО' 1990 года

Ученый секретарь специализированного совета

кандидат'йгзико-ттештических наук Н.Ч.Сергеев-Альбов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

стуальность теш. Применение математических методов- в-

и ...л

I. /.. ЛИП ал ел

теории' измерений и •интерпретации привело к постановкам .задач,, которые ранее считались кокорректниг!.. Основопояаг^ющио • работы

A.Н.Тихонова, М.', 1.Лаврентьева, В.К.Иванова создали ;Т>унда»ен нового направления математики - теории решения некорректно поставленных- задач. Трудность численного решения некорректных зе-дач обичко связана с тем, что '/.сходные данные дат них могут быть нечестны лишь приближенно о некоторой погрешностью... Налнуие этой погрешности неизбежно, если исходные ,,аннпе зависят от некоторых измердег.асс Физических величин или если задача решается с поглодаю ЭВМ. Поэтому большинство -реальных .зад-ч приходится решать, располагая лишь неполной ш не точной информацией-.- Ка основе такоЧ ингюр?."лдии нельзя решить задачу сколь угодно- точно, следовательно, представляс-тя ва\таи* задача нахочдения-приближенного решения с предельноточностью. Таш'л предельные но. точности (оптимальные ) кетпди исследовались в ; аботах З.К,.''ла-нова, З.А ..'Лорозсза, В.В.Иванова, С.Б.Стечкина,. В.Н.Стр.хова,

B.З.Арестова, Т.И.Королш", А.Г.Марчука, К..Ю.Осипенко, А.И.Гребенникова, К.Мииелли, Т.Рквлича, ,!Ч.Трау<5а, Х.Воиышкозского и других. Кроме того,, рассматриваемые задачи представляют '»нтерес, поскольку изучаемое постановки имеют реальную физическую интерпретацию, являются модельными при описании .¡роцессов, связа: ;шх с геофизическими исследованиями.

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

'детодика - исследования. Метода .а исследования опирается на применение методов р/ккци-нальнтп анализа и :прии <Ьунк1_,л1'г к общим и конкретнг т нос 'зновкам задач восстановления. Некоторые исходные постановки с едятся к ре энию линеаризованных задач.

Научная т тизна. В диссертационной работе получены следук чие результаты:

- в гидъе .ртовоы прос-ранстве с множес-чом корректное ^ -шаром радиуса Н получено значение предельно* точности

■ прмбяиличного решения задачи восстановления линейного [функционала (é,x) в случав точных исходных данных, а

• даш ■приближенных данных наедено квазичебиневское решение . с лрйдельио?! точностью; аналогичные оценки предельно^ •точности получен», для. чебншевского решения систеш линей—

■ инх уравнений с точно и приближенно заданной правой .час-■ тью;, ....

- 'в--банахово?.! простракстг? с выпуклым, центрально-сишет-•ричним 1лножеством корректности. получены оценки предель-■ "неточности приближенного решения и точности пролзволь-"кого. метода решения задачи восстановления линейного опе-паюра-через модуль непрерывности оператора; , --доказана оптимальность по. порядку одного сглаживающего ■• алгоритмаjв банаховом пространстве с выпуклым, централь-ко-симметгячным мнокестзо.ч корректности;. исследована -одгч. постановка задачи трехмерной томографии и для нее получено численное решение оптю.вльным но точ-ностиметодои.

"Теоретическая и Практическая 'ценность.- 1'работе получены теоретические результаты по.оценкам точности приближенных методов, которыо могут быть.использованы для построения оптамалькых. по точности-рашени» ряда'линеЯннх-условно-корректных задач. Тео-ре-пческне разработки в дассертгции иллюстрируются примера™. Последняя глава диссертации целиком посвящена прилоаен:тю задаче трехмерной томографии. , '

Апробация •ряботч. Результаты диссертации опубликованы "в работах [.Г - б] и докладывались на I и II конференциях молодых ученгх Сибири и Дальнего Востока (НГУ, г.-Новосибирск, 1987, 1988 гг..), на III Всесоюзной конференции по условно-корректным задачам математической физики (г. Алма-Ата, 1989 г.), на се:ди-натах по обратньм-задачам для ®«Йеренциальных уравнений (iL! СО АН СССР, руководитель - профессор Ю.Е.Аникоиов), по математическому моделированию .(Н1У, руководитель - 'профессор. В.Н./ Врагов

Структура и объем работы. -Диссертационная работа состоит • из введения, трех глав и библиографии. Работа■содернит 73 страниц« машнописного текста. Библиография -включаот 59 наименований . ' ' - ' • '

содержание работы

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

В первой главе дано определение чебшпевского решения зада-г-чи восстановления и предельно*! точности приближенного решения» рассмотрены частные случаи существования чебымевских и квази-чеб ¡«невских решений.

Пусть имеется троЧка пространстг Х' . Y , z : X - лцней-ное, Y, 2 - банаховы пространства с нормами Ц-Ц, и соответственно.

6 - линейны« оператор с областью определения 2>(й>) С X и областью значений Я(в)С Z .

Требуется восстановись приблг. .генное ^начеииэ оператора 6

2 = б* , г еZ на элементах Х'ё X , известии^ своим проявлением па некотором-линейном операторе А : X —? Y так,'что задан t^e Y тако«, что

гда S >0 _ уровень ошибки в данных. У

Определим множество Qc как множество всех X € л ;

Qcfy)*{x* X : KAse-yl.^i .

Пусть, кроме того, элементы х удовлетворяют условию

2' & ^ , \j с x

где W - некоторое подмножество пространства что

ад) <\V*= ф > V *ф

и будем считать, что

aft) л V * ф

x , Tf?

Cf? -о<?

Точность приближенного решений 2 естественно определить как. .

хеЩуШ/

тогда .предельно^! точностью будет величина

Щ -¡М У1?. г); .

Такое 2 , на котором достигается эта нижняя грань, будем называть чвбшезскигл решением задачи.восстановления значений оператора Ъ , поскольку эта задача эквивалентна нахождению че-б.шсвского центра множества £>•

Если приближенное решение «? получено при отображении множества начальных данных задачи /} \д' -г о 5 в пространство 2 ,

где ' ¡¡¡/^1 * í ^ » т0 чебшювское решение £

наедено оптю-альным по точности методом , т.е. методом,

для которого достигается точная нинснчя грань

в классе всех отображений (V,

В ;>§ 2-4 первой главы рассматриваются частнне постановки задачи восстановления, когда мокно постоять чебышевское решение и на'-5ти его предельную точность.. .

Пусть X и -У - гильбертов;: пространства, - линейный ограккченьнЧ оператор, о - О , тогда для множества корректности вида.

чеб.лпевским решением задачи восстановления значений линейного оператора Б будет

V

Экстремальность оператора ВА(ДА)следует из результатов работ

В.А.Морозова и А.И.Гребенникова, а предельная годность прябли-. женного тюшения

о /(._ . п

ч

"А-х'О

с <-- и

получена К.Мишелли и 'а'.Ривлпшш. В § 2 первой главы показано, что в случае, когда £ =» Я , 3 - линейный (Ъупкцют'ал величина )){%) может быть уточнена и ¡моет окончательный вид

т -'//- !а гаа%1{ц(а гаауа-£)4

Пусть теперь исходные данные известии приближенно так,-ч">&<

у= т , где ц» а'х- - точное значение "сходних данных, : 11?Ц тогрешость в даьннх. При вштолне;ш;.:.

условия малости -

1(ауаа% атаа1г)!« м- 11агаа7\с

в § 3 главы I на гшокестве корректности

\V-izt X ; Н'М м]-

получено чебышевское с точностью до членов порядка малости или квазичебшзевское решение задачи восстановлена линейного (лункционяда (ё ,2.*}

(С*-*'*>»•*)

с предельной точность»

где

*

г

]?е!"0Я си тему линейных алгебраических уравнений (СЛАУ) с прймЬ'угольноЯ матрицей А . nxftl , Iii w полного.ранга, право; частью ^ е йЛ :

lAv-yliS ,

и ограничением в виде

IlTzIL* м}

где ' - матрица с * ^ , к ? т полного ранга, ¡1 • L - евклидова норда в Д > J)' 11« ~ евклидова норма в R , нетрудно заметить, :то эту задачу можно свести к предыдущей. Так как X $.'" . то представляя к&кдую компоненту вектора сс в видэ

гдо Ы - есничньй вектор & - {о,.. ,i мошо применить

методику предыдущих построений. В § 4 главы I пока-зно, что чебкшевским решением СЛАУ дня £Г =« О будет

с предельной точностью .

v(y) = И'fr)

■ 1 i с 4 п

гдо

ч- ftЩй '¡(т У)т(«А - В)ё: i

и для В > О . ("правая часть с погрешностью

7 : IITMb')

в случае выполнения условия малости

<ч- М-

для к&вдоЯ компоненты хвазичебымевское решение будет с предельно» точностью

Я Г.

е-а гаат,

\

где

В явном виде написать предельную точность приближенного решения задачи восстаног дения удается в редких случаях, поэтому встает вопрос об оценке величины У(0 чер'-з структурные ха рактеристики задачи. Для получе :ля оценок точности решения многими учеными вводились различные оценочные тункцяи, большинство из которых связано о модулем непрерывности оператора

Предполагаем, что У , 2 ~ ¿знаховы пространства, и/- ви-пуклое, центрально-симметричное множество линейного пространства X или множество вида

где I - некоторый линейны? ограничивавши** оператор га X в банахово пространство Ъг .

Используя известное неравенство

где Ш) ~ константа Юнга пространства X.

ни) Ху)

//(у) - диаметр множества М* Б^^^Ц)

ясно, что оценки величины У (у) моясно получить через •

В § I главы 2 получены оценки дая величины

1.

где

2.

где

8(0- ^-1 1Ах р!,

хе\\/

а величина г (■?) - максимальны» диаметр пересечения единичного шара с выпуклым множеством, отстоящим на расстоянии £ от центра. Очевидно, что

пРи о* ,

а для гильбертова пространства ^ (£ ) = X

Кроме ^ого, показано, что „яя .любого выпуклого и центрально-симметричного множества \л/имеет место равенство'

В § 2 второй главы исследуется точность произвольного метода решения задачи восстановлены Ф{\') •* А, V -г 2/ • очределяемая величинами

ф

Ж* и'

* о

Показано, что

о 4 эеф) - 1(<р) ^

и, если ограничиться »днокеством линейных методов, то среди решв' ни"' экстремально** задачи

%(<р)

существует такой, что для него справедливо

а решение задачи наховденкя линейного ограниченного метода Ф с мини;.ально'! оценкой ^(Ф) совпадает о решением экстремально1'» задачи:

?сфо) = г(о>) т й,

при некотором £,>0 ' > гДе

т(<4>) = 4и.р (6-ФЛ)рс

ос <= й-'

В случав а = £ , задача ЧГ совпадает с задачей С.Б. Стечкина о наилучшем приближении неограниченного оператора ог-раниченними; ее связь с задаче*» нахождения исследовалась

в работах В.В.Арестова, В.Н.Габушина.

Выбирая приблияеншг! метод, естественно в первую очередь рассматривать тот, которн*'! гарантирует минимальную погрешность ЭеОФ) . Полученные С.А.Смоляком, Н.С.Бахваловкм, А.Г.!.1арчуком, К.Ю.Осипенко, К.Мишелли, Т.Ривлиним, а также В.К.Ивановым, В.В.Лрестовым, В.А.Морозовым оценки величины Э€ (Ф) , позволяют определить оптимальный метод как метод, для которого

и оптимальны"* по порядку с константой . с 1 .,' если

В заключительном параграфе второ« главы показана оптимальность по порядку с константой С-'К+Х. одного сглаживающего алгоритма.

Последняя глава диссертация посвящена исследованию трехмерной задачи томографии. По заданным значениям интегралов

ГШ Ш-М'^

вдоль прямых I требуется восстановить функцию JUf^) ,

ос е й 5 . ммеющую носитель в пире

¡[are Г teij i ]

Аппроксимируя функцию JUfa) полной системой Функций

оа

Ы* I '

после -пиегрирования получим ,

Г/кя) J '

В частности, если ju(^) имеет вид

/¿(«0 = ^Си U (f**).+ /к. ¿¿л-fu,*)] ,

то дтя № - h/t*N2. значеш» интегралов это будет СЛАУ, которая в данной остановке, как правило, является переопределенной, и проекционные данные oU , вычисляются в явном виде как нормальное обобщенное решение ОМУ, дающее оптимальное по точности решение да::но» СЛАУ. Для численно« реализации это*} задачи использована подпрограмма ftS OL.V.

Основные результаты диссертации опубликована в работах:

1. Предельная точность решения в л.гневных задачах восстановления // Методы исследования обратных и некорректных задач. Новосибирск. IS87. С, 48-58 (совместно с А.Г.Марчуком).

2. Об оптимальных методах вычисления значений оператора в банаховом лространсг е // Единственность, устойчивость и методы решения задач математической физики. Новосибирск. 1987.

С. 25-32 (совместно с А.Г.Марчуком).

3. Г чстремальнче зад"чг оптимизации точности линейных систем // Математический анализ и дифференциальные уравнения. Новосибирск. I987. С. 3-10.

4. Очтшалыше по точности методы решения линейного операторного уравнения // Тезисы конференции молодых ученых Сибири и Дальнего Востока. Новосибирск. 1987. С. 19-20.

5. Некоторые оценки предельной точности раиени-Ч условно-коррект-

ных задач // Тезисы II конференции молоды:: ученых Сибири и Дальнего Востока. Новосибирск. 1988. С. Э7-ЗГ, 6. Об оптимальных методах восстановления оператора, на решениях операторного уравнения // Тезисы Всесоюзной конферещда (2 - б октября 1989 г., Алма-Ата) Условно-корректные задачи математической физики. Красноярск. 1989. 0. 26.