Оптимальні схеми дискретизації операторних рівнянь

Размещено на http://www.allbest.ru/

НАЦІОНАЛЬНА АКАДЕМІЯ НАУК УКРАЇНИ

IНСТИТУТ МАТЕМАТИКИ

Автореферат

дисертації на здобуття наукового ступеня доктора фізико-математичних наук

ОПТИМАЛЬНI СХЕМИ ДИСКРЕТИЗАЦIЇ ОПЕРАТОРНИХ РIВНЯНЬ

01.01.07. - обчислювальна математика

СОЛОДКИЙ Сергiй Григорович УДК 519.642

Київ - 2003

Дисертацією є рукопис

Робота виконана в Інституті математики НАН України

Офіційні опоненти: доктор фіз.-мат.наук, професор Морозов Володимир Олексійович, науково-дослідний обчислювальний центр Московського державного університету ім. М.В.Ломоносова, головний науковий співробітник

доктор фіз.-мат.наук, професор Бабич Михайло Данилович, Інститут кібернетики ім.В.М.Глушкова НАН України, провідний науковий співробітник

доктор фіз.-мат.наук, професор Сявавко Мар'ян Степанович, Львівський державний аграрний університет, завідувач кафедри

Провідна установа: Львівський національний університет ім. І.Франка, кафедра інформаційних систем

Захист відбудеться "25" листопада 2003 р. о 15 годині на засіданні спеціалізованої вченої ради Д.26.206.02 при Інституті математики НАН України за адресою: 01601, Київ 4, МСП, вул. Терещенківська, 3.

З дисертацією можна ознайомитися в бібліотеці інституту.

Автореферат розісланий "24" жовтня 2003 р.

Вчений секретар спеціалізованої вченої ради Пелюх Г.П.

Загальна характеристика роботи

Актуальнiсть теми. У зв'язку зi зрослою потребою в розв'язаннi багатьох практичних задач математичної фiзики, механiки i ряду iнших дисциплiн природознавства на початку двадцятого столiття iнтенсивний розвиток набули дослiдження в галузi наближених методiв. Значний внесок у побудову i обгрунтування нових методiв зробили багато вiдомих вчених, серед яких варто видiлити В.Рiтца, Б.Г.Гальоркiна, I.Г.Бубнова, М.М.Крилова, М.М.Боголюбова, М.Ф.Кравчука. Важливий етап у розвитку наближених методiв бере початок iз 40-х рокiв минулого столiття, коли розрiзненi до цього часу методи стали вивчатися з єдиної точки зору. Прагнення до знаходження найкращого алгоритму для конкретної задачi призвело до систематизацiї пропонованих методiв. Пiдвалини для побудови iєрархiчної системи алгоритмiв були закладенi Л.В.Канторовичем у рамках створеної ним загальної теорiї наближених методiв для розв'язання операторних рiвнянь. Згiдно з цiєю теорiєю одним з основних критерiїв оцiнки ефективностi наближених методiв вважається швидкiсть збiжностi апроксимацiй до шуканого розв'язку. Звiдси цiлком природно виникає питання про побудову оптимальних методiв. Проблемами оптимiзацiї методiв розв'язання операторних рiвнянь у рiзний час активно займалися М.О.Красносельський, М.С.Бахвалов, К.I.Бабенко, С.Г.Мiх-лiн, В.В.Iванов, Г.М.Вайнiкко, В.Л.Макаров, В.К.Задiрака, В.В. Хлобистов, А.Ю.Лучка, Б.Г.Габдулхаєв, С.В.Переверзєв i багато iнших. Найбiльш повна iнформацiя про цi дослiдження мiститься в монографiях останнiх двох названих авторiв.

Зазначимо, що в сучасному чисельному аналiзi поняття оптимальностi трактується неоднозначно. Так, наприклад, за об'єкт оптимiзацiї дослiджуваних методiв може розглядатися розмiрнiсть розв'язуваної системи рiвнянь, ранг апроксимуючого оператора i т.д. Можна видiлити 2 основнi пiдходи до оптимiзацiї наближених методiв, що використовують рiзнi цiльовi функцiї. А саме, по-перше, оптимiзацiя по точностi, коли шукається найкращий за точнiстю метод серед усiх можливих методiв iз фiксованим рiвнем певного обчислювального ресурсу (прикладами такого роду задач є поперечники), i по-друге, оптимiзацiя по складностi, в рамках якої здiйснюється вибiр методу, що вимагає мiнiмальних витрат обчислювальних ресурсiв, серед усiх методiв, що досягають наперед заданого рiвня точностi. За останнi сорок рокiв значну увагу придiлено дослiдженням оптимiзацiйних задач у розумiннi другого зi згаданих пiдходiв. Основоположниками такого пiдходу до оптимiзацiї алгоритмiв вважаються А.М.Колмогоров i А.Г.Вiтушкiн, якi дослiджували складнiсть є-задання функцiї. При цьому пiд складнiстю є - задання розумiлося мiнiмальне число членiв у зображеннi функцiї, що гарантує точнiсть вiдновлення є. На цей час iстотного розвитку набув напрямок, що зв'язаний з поняттями iнформацiйної й алгоритмiчної складностi. Цi поняття уперше були введенi в розгляд американськими вченими Дж.Траубом i Х.Вожьняковським у рамках IBC-теорiї (Information Based Complexity Theory). Пiд iнформацiйною складнiстю задачi розумiється найменший обсяг дискретної iнформацiї, необхiдний для визначення наближеного розв'язку iз заданою точнiстю, а пiд алгоритмiчною складнiстю - мiнiмальне число арифметичних операцiй, що потрiбно виконати для побудови цього розв'язку. На доцiльнiсть розгляду обох пiдходiв до оптимiзацiї (по точностi i по складностi) з єдиної точки зору було вказано М.П.Корнєйчуком. Це стало можливим пiсля впровадження ним поняття iнформацiйного поперечника. Таким чином, всi основнi твердження дисертацiї можуть одночасно трактуватися як результати в областi оптимiзацiї як по точностi, так i по складностi.

Основну увагу в дисертацiї придiлено дослiдженню оптимiзацiї по точностi, а також iнформацiйної i алгоритмiчної складностi операторних рiвнянь, що є узагальненням одновимiрних iнтегральних рiвнянь Фредгольма I i II роду з ядрами скiнченної гладкостi. При цьому розглядаються ядра двох модельних типiв гладкостi: по-перше, ядра соболєвського типу гладкостi, а, по-друге, ядра, що мають домiнуючу мiшану частинну похiдну. Зазначимо, що при вивченнi оптимального наближення функцiй багатьох змiнних була встановлена принципова розбiжнiсть мiж названими типами гладкостi. А саме, при вiдновленнi перiодичних функцiй другого типу вдається iстотно полiпшити точнiсть наближення за рахунок використання гiперболiчного хреста.

Першi порядковi оцiнки складностi перiодичних рiвнянь Фредгольма II роду з ядрами зазначених типiв були знайденi С.В.Переверзєвим у випадку iзотропної гладкостi. Пiзнiше цi результати були узагальненi ним у спiльнiй роботi з нiмецькими математиками Ш.Хайнрiхом i К.Франк на багатовимiрний випадок. У подальшому була також дослiджена складнiсть слабо-сингулярних рiвнянь i рiвнянь II роду з аналiтичними ядрами. У ходi перерахованих дослiджень було встановлено низку цiкавих фактiв. Насамперед з'ясувалося, що застосування оптимальних методiв вiдновлення коефiцiєнтiв дослiджуваних рiвнянь не дозволяє побудувати найкращий метод розв'язання самих рiвнянь. Далi, при розв'язуваннi рiвнянь другого роду iдея гiперболiчного хреста дає можливiсть реалiзувати оптимальнi наближення також у випадку ядер соболєвського типу гладкостi. Крiм того, останнiй ефект має мiсце не тiльки в перiодичному випадку. У зв'язку з цим становить iнтерес не тiльки обчислення складностi для бiльш загальних i iнших класiв операторних рiвнянь II роду, але також можливiсть поширення наведених вище висновкiв на цi класи.

Що стосується некоректних задач, основнi положення теорiї яких викладенi в монографiях А.М.Тихонова i В.Я.Арсенiна, В.К.Iванова, В.В.Васiна i В.П.Танани, В.О.Морозова i О.I.Гребеннiкова, А.Б.Бакушинського i О.В.Гон-чарського, Г.М.Вайнiкко i О.Ю.Веретеннiкова, а також багатьох iнших, то проблема складностi таких рiвнянь ранiше взагалi не вивчалася. Бiльш того, у спецiальнiй лiтературi вiдомi висловлювання щодо принципової неможливостi постановки цiєї проблеми (див., наприклад, посилання [136] дисертацiї). Таким чином, вивчення оптимальної дискретизацiї некоректних задач дозволяє, по-перше, спростувати думку, що iснувала ранiше, про безперспективнiсть подiбного роду дослiджень, а по-друге, вперше одержати уявлення про складнiсть розв'язання таких задач. В рамках дисертацiї також дослiджено адаптивний пiдхiд до дискретизацiї рiвнянь I роду з ядрами соболєвського типу гладкостi у випадку, коли параметр регуляризацiї вибирається згiдно з принципом нев'язки В.О.Морозова. Тут пiд адаптивною дискретизацiєю розумiється змiна обсягу використаної дискретної iнформацiї на кожному кроцi iтерацiї обчислювальної процедури. В описанiй ситуацiї стосовно iтерацiйних методiв регуляризацiї спроби побудувати адаптивнi схеми дискретизацiї наштовхуються на значнi труднощi, що пов'язанi з принципово новим зображенням наближеного розв'язку. Таким чином, побудова оптимальних алгоритмiв вимагає подолання низки проблем iдейного характеру.

Пiдбиваючи пiдсумок вище сказаному, можна зробити наступний висновок. Конструювання економiчних схем дискретизацiї з метою обчислення iнформацiйної i алгоритмiчної складностi операторних рiвнянь дозволяє у подальшому не тiльки судити про вiдносну трудомiсткiсть наближеного розв'язання кожного дослiджуваного рiвняння, виходячи з його належностi до того чи iншого класу, але також будувати ефективнi алгоритми розв'язання конкретних рiвнянь, що i робить тему дисертацiї актуальною.

Зв'язок iз науковими програмами, планами, темами. Робота виконана вiдповiдно до наукової теми Iнституту математики НАН України (шифр теми - 1.1.7). Метою роботи є розробка проекцiйних схем дискретизацiї iнтегральних операторiв з ядрами скiнченної гладкостi та їхнiх узагальнень, обчислення точних порядкiв iнформацiйної i алгоритмiчної складностi вiдповiдних класiв рiвнянь I i II роду з вивченими операторами, а також побудова економiчних наближених методiв, що реалiзують цi порядки.

Методи дослiдження. Для розв'язання перерахованих вище задач використанi методи теорiї оптимальних алгоритмiв, теорiї некоректних задач, загальної теорiї наближених методiв, функцiонального аналiзу i теорiї функцiй.

Наукова новизна. Усi результати, що отриманi в дисертацiйнiй роботi, є новими i полягають у наступному:

побудовано iтерацiйний метод, що гарантує оптимальну за порядком точнiсть розв'язання рiвнянь Вольтерра другого роду з нескiнченно диференцiйовними ядрами;

вперше дослiджена задача iнформацiйної i алгоритмiчної складностi розв'язання операторних рiвнянь, якi є узагальненням одновимiрних iнтегральних рiвнянь Фредгольма першого роду з коефiцiєнтами скiнченної гладкостi;

побудовано оптимальнi за складнiстю проекцiйнi методи розв'язання некоректних задач як у випадку апрiорного, так i у випадку апостерiорного вибору параметра регуляризацiї;

на основi iдеї гiперболiчного хреста розробленi новi проекцiйнi схеми дискретизацiї для розв'язування операторних рiвнянь I i II роду;

встановлено, що алгоритми розв'язання некоректних задач, що побудовано на базi адаптивного пiдходу до дискретизацiї, є бiльш економiчними у значеннi обсягу використаної дискретної iнформацiї, нiж стандартнi методи.

Теоретичне i практичне значення. Результати, що наведенi в дисертацiї, i методи їхнього одержання є цiкавими для фахiвцiв в галузi чисельного аналiзу i теорiї наближення. Запропонованi автором пiдходи можуть бути використанi при подальших дослiдженнях, присвячених оптимiзацiї методiв наближеного розв'язання операторних рiвнянь, а також при побудовi i аналiзi ефективностi алгоритмiв розв'язання конкретних прикладних задач.

Апробацiя результатiв дисертацiї. Матерiали дисертацiї доповiдалися на Мiжнароднiй конференцiї "Теорiя наближень i задачi обчислювальної математики" (Днiпропетровськ, 1993), Мiжнародних симпозiумах "Алгоритми i складнiсть неперервних задач" (Дагштуль, Нiмеччина, 1996, 1998, 2000), другiй школi "Ряди Фур'є: теорiя i застосування" (Кам'янець-Подiльський, 1997), Мiжнародному симпозiумi "Питання оптимiзацiї обчислень - XXVII" (Київ, 1997), Мiжнароднiй конференцiї "Методи наближення i ортогональнi ряди" (Тарту, Естонiя, 1998), Мiжнародному конгресi математикiв (Берлiн, Нiмеччина, 1998), шостiй мiжнароднiй математичнiй школi "Метод Ляпунова i його застосування" (Алушта, 2002). За результатами роботи були зробленi доповiдi на семiнарах Iнституту математики НАН України, Iнституту кiбернетики НАН України, Київського нацiонального унiверситету iм. Т.Шевченка, Обчислювального центру Московського держунiверситету, Львiвського нацiонального унiверситету iм. I.Франка, унiверситетiв м.Кайзерслаутерн i м.Майнц (Нiмеччина).

Публiкацiї i особистий внесок здобувача. Викладенi в дисертацiї результати отриманi автором самостiйно i опублiкованi в статтях [1--21] та тезах доповiдей [22--26]. Результати, що мiстяться в спiльних iз С.В.Переверзєвим роботах [4, 5, 18, 19], є частковим випадком загальних результатiв дисертацiї.

Структура та обсяг роботи. Дисертацiя викладена на 300 сторiнках машинописного тексту i складається з вступу, чотирьох роздiлiв, висновкiв i списку цитованої лiтератури, що мiстить 138 джерел.

Змiст роботи

Перший роздiл дисертацiї мiстить визначення низки математичних понять, що є об'єктами подальших дослiджень, i доведення декiлькох важливих допомiжних тверджень. Також введенi в розгляд новi схеми дискретизацiї, що лежать в основi пропонованих нижче оптимальних методiв. У пiдроздiлi 1.1 наводяться основнi типи лiнiйних iнтегральних рiвнянь Фредгольма i Вольтерра. Крiм того, в короткiй формi викладаються обранi факти з iсторiї розвитку методiв наближеного розв'язання рiвнянь. Значна увага при цьому придiляється висвiтленню проблеми оптимiзацiї таких методiв. У пiдроздiлi 1.2 дається означення проекцiйної схеми дискретизацiї, де в якостi дискретної iнформацiї використовуються значення функцiоналiв, що обчисленi на операторi i вiльному членi рiвняння. Дискретна iнформацiя такого вигляду називається гальоркiнською iнформацiєю про розв'язуване рiвняння.

Далi вводяться в розгляд двi новi проекцiйнi схеми дискретизацiї, якi будемо називати узагальненими проекцiйними схемами (УПС). Отже, нехай - гiльбертiв простiр, в якому впроваджено скалярний добуток i породжувана ним норма . Виберемо в деякий ортонормований базис .

Перша пропонована УПС полягає в замiнi вихiдних коефiцiєнтiв розв'язуваного рiвняння (оператора i вiльного члена) на скiнченновимiрнi елементи.

Характерною рисою другої запропонованої УПС є одночасне використання скалярних добуткiв вигляду. З цiєю метою задiяний гiперболiчний хрест, симетричний щодо бiсектриси першого квадранта координатної площини.

Крiм того, обчислюються порядковi вiдносно оцiнки обсягу гальоркiнської iнформацiї, що задiяна обома УПС. Кiлькiсть скалярних добуткiв, використовуваних тiєю чи iншою схемою дискретизацiї, будемо позначати . Величина , де або , розглядається як цiльова функцiя в дослiджуваних нами екстремальних задачах. Обидвi УПС i фiгурують у всiх наближених методах, що побудованi в рамках дисертацiї (за винятком пiдроздiлу 2.4).

Пiдроздiл 1.3 мiстить визначення операторних класiв, що задають рівняння вiдповiдно першого i другого роду, оптимальнi методи розв'язання яких будуються в роздiлах II--IV. Наведемо опис цих класiв.

Обидва класи операторiв є модельними при вивченнi оптимальних наближених методiв. Зазначимо, що при простiр є узагальненням соболєвського простору разiв диференцiйовних на функцiй , де за базис можуть бути використанi ортонормована система функцiй Хаара, пiдпростiр тригонометричних многочленiв або ортонормована система полiномiв Лежандра, що розглянута на вiдрiзку . Тодi належнiсть iнтегральних операторiв класу означає виконання для довiльної умови.

Множини ядер iнтегральних операторiв (4), що задовольняють (5), є узагальненням класiв функцiй соболєвського типу гладкостi. А множини ядер, для яких виконується спiввiдношення (6), розширюють класи функцiй, що мають домiнуючу мiшану частинну похiдну.

Об'єктом дослiджень є множини рiвнянь iнтегральнi оператори (4) яких належать класам (умова (5)) i (умова (6)). На закiнчення пiдроздiлу 1.3 встановлено низку апроксимацiйних властивостей операторiв iз класiв і , що використовуються у подальшому.

У другому роздiлi дисертацiї розглядається задача оптимальної дискретизацiї рiвнянь II роду (2) i (8). У пiдроздiлi 2.1 наводиться постановка дослiджуваної проблеми. Отже, нехай - деяка множина банахового простору i - певний клас лiнiйних операторiв з . Сукупнiсть рiвнянь (2), де i , позначимо .

Пiд способом задання iнформацiї про рiвняння з будемо розумiти довiльний набiр неперервних функцiоналiв, визначених на множинах i . Через позначимо сукупнiсть усiх таких наборiв , що задовольняють спiввiдношення. При фiксованому наборi рiвнянню (2) ставиться у вiдповiднiсть числовий вектор.

При розв'язуваннi рiвняння (2) пiд алгоритмом будемо розумiти оператор, що зiставляє векторовi у якостi наближеного розв'язку елемент , однозначно визначений скiнченним набором числових параметрiв. У свою чергу значення цих параметрiв знаходяться в результатi виконання деякого обмеженого числа елементарних арифметичних операцiй (е.а.о.) над компонентами вектора iнформацiї . При фiксованому через будемо позначати множину алгоритмiв , що використовують iнформацiю i потребують для побудови виконання не бiльш е.а.о. Величина показує, яку мiнiмальну похибку можна досягти на класi за допомогою найрiзноманiтнiших алгоритмiв, що для своєї реалiзацiї вимагають не бiльш нiж е.а.о., i характеризує при цьому алгоритмiчну складнiсть рiвнянь з дослiджуваного класу.

Пiдроздiли 2.2, 2.3 присвяченi визначенню величини для класiв одно-значно розв'язуваних у гiльбертовому просторi рiвнянь (2) з вiльними членами iз кулi радiуса у просторi i з операторами , вiдповiдно, iз класiв (див. пiдроздiл 2.2) i (див.пiдроздiл 2.3), а також їхнiх iнтегральних аналогiв (8). Щоб навести основнi результати виконаних дослiджень, домовимося далi в нерiвностях вигляду

,

розумiти рiзнi додатнi сталi, що не залежать вiд .

Слiд зазначити, що в порiвняннi з результатами попередникiв у випадку першого модельного класу операторiв вдалося знайти оптимальний у степеневiй шкалi порядок величини для будь-яких , а також зменшити степiнь логарифмiчного множника в оцiнцi зверху. Що стосується другого випадку (оператори , то тут крiм узагальнення вiдомого ранiше результату С.В.Переверзєва на всю шкалу класiв перiодичних iнтегральних рiвнянь (8), вдалося також розв'язати поставлену задачу для загального випадку операторних рiвнянь (2).

У пiдроздiлi 2.4 дослiджується задача побудови оптимальних у сенсi величини методiв розв'язання рiвнянь Вольтерра з нескiнченно диференцiйовними ядрами такими, що i вiльними членами , ( - простiр разiв неперервно диференцiйовних на функцiй). Через позначимо вiдповiдний клас рiвнянь (10). Оптимальний степеневий порядок алгоритмiчної складностi для класу рiвнянь надають дискретна інформація i iтеративний метод

Третiй роздiл присвячений наближеному розв'язанню операторних рiвнянь I роду (1). У пiдроздiлi 3.1 дається поняття некоректної за Адамаром задачi та викладається постановка проблем, що дослiджуються в дисертацiї, формулювання яких наведено нижче.

Отже, нехай - дiйсний гiльбертiв простiр. Будемо вважати, що у (1) i . Крiм того, припустимо, що замiсть (1) у нашому розпорядженнi є збурене рівняння.

Метою наших дослiджень є наближене знаходження розв'язку рiвняння (1) iз мiнiмальною нормою, що прийнято називати нормальним. Iнтерес саме до нормального розв'язку (1) обумовлюється тим, що довiльний розв'язок рiвняння (1) може бути зображений у виглядi суми i будь-якого елемента з . Звiдси випливає, що наближене знаходження елемента вимагає додаткових обчислювальних витрат у порiвняннi iз задачею вiдновлення нормального розв'язку. Таким чином, складнiсть знаходження елемента можна розглядати як нижню межу для складностi визначення будь-якого розв'язку (1).

Оскiльки оператор компактний, то (1) є нестiйкою задачею, i для побудови стiйкого наближення необхiдна регуляризацiя вихiдного рiвняння.

Нехай - довiльна обмежена область координатної площини. Пiд проекцiйним методом розв'язання рiвняння (1) будемо розумiти довiльне правило , , згiдно з яким набору скалярних добуткiв у якостi наближеного розв'язку (1) зiставляється елемент. Таким чином, проекцiйний метод розв'язання (1) можна зобразити у виглядi комбiнацiї методу регуляризацiї i проекцiйної схеми дискретизації .

Звичайно в теорiї некоректних задач ефективнiсть того чи iншого наближеного методу перевiряється на множинi нормальних розв'язкiв . Пiд похибкою алгоритму на деякому класi операторiв розумiємо величину

Пiд оптимальною похибкою проекцiйної схеми на будемо розумiти величину

Вiдомо, що жоден наближений метод (не обов'язково проекцiйний) не може гарантувати на класi рiвнянь (1) iз розв'язками , що заповнюють множину , точнiсть вiдновлення вищого за величину .

Через позначимо множину найрiзноманiтнiших проекцiйних схем , де - довiльний базис простору , для яких при виконуються спiввiдношення

Згiдно з наведеними умовами у множину включенi тiльки тi проекцiйнi схеми, за допомогою яких реалiзується оптимальний порядок точностi (умова (15)). Суть умови (16) полягає в тому, що дискретизацiя вихiдного рiвняння (1) не призводить до збiльшення порядку заданого рiвня похибки . Величину будемо називати iнформацiйною складнiстю проекцiйних методiв розв'язання рiвнянь (1). Позначимо через множину найрiзноманiтнiших проекцiйних методiв , що задовольняють (15), (16) i для побудови наближеного розв'язку потребують виконання не бiльш е.а.о. Величину назвемо алгоритмiчною складнiстю проекцiйних методiв розв'язання рiвнянь (1).

У якостi регуляризаторiв надалi будуть використанi методи, що зображенi у виглядi функцiї вiд оператора розв'язуваного рiвняння. Цi регуляризатори визначаються спiввiдношенням , де функцiя задовольняє певнi умови, а - параметр регуляризацiї. Клас таких методiв вперше був впроваджений до розгляду А.Б.Бакушинським. На закiнчення пiдроздiлу наводиться кiлька прикладiв найбiльш вiдомих регуляризаторiв iз (а саме, метод Тихонова, його узагальнений i iтерований варiанти, а також iтерацiйнi процедури Ландвебера i Факеєва-Лардi).

Змiст пiдроздiлу 3.2 має допомiжний характер. У доведених тут твердженнях встановлено низку апроксимацiйних властивостей УПС, що визначенi у пiдроздiлi 1.2, на класах операторiв i .

У пiдроздiлi 3.3 розглядається задача побудови проекцiйних методiв, що забезпечують збiжнiсть по нормi апроксимацiй до нормального розв'язку рiвняння (1). Основним результатом пiдроздiлу є встановлення достатнiх умов на параметри регуляризацiї i УПС , при виконаннi яких гарантована збiжнiсть наближень.

Побудовi проекцiйних методiв розв'язання рiвнянь (1), що досягають опт-имального порядку точностi на множинах нормальних розв'язкiв , присвячений пiдроздiл 3.4. При цьому припускається, що значення фiксоване i вiдоме. Пропонованi проекцiйнi методи використовують УПС iз множини i регуляризатори з класу . Параметри УПС обираються таким чином, щоб забезпечити мiнiмально можливi витрати гальоркiнської iнформацiї (14). Слiд зазначити, що проблема найкращого вибору параметрiв гiперболiчного хреста в дослiджуваному випадку принциповим чином вiдрiзняється вiд ситуацiї, що характерна при розв'язуваннi рiвнянь II роду. А саме, у пропонованих нижче схемах для досягнення оптимальностi потрiбно обирати параметри i не тiльки в залежностi вiд "диференцiальних" характеристик i оператора розв'язуваного рiвняння, але також i вiд гладкiсних властивостей шуканого розв'язку. У наступних твердженнях висунуто економiчнi УПС у сенсi величини для розв'язання рiвнянь (1) з операторами з обох модельних класiв.

Теорема 3.10. Нехай , а параметри i проекцiйної схеми обираються вiдповiдно до наступних правил:

a) при

b) при

c) при

Схема належить , якщо при деяких сталих виконуються нерівності

Оптимальна за порядком оцiнка точностi досягається в рамках проекцiйного методу .

Теорема 3.11. Нехай , а параметри i проекцiйної схеми обираються вiдповiдно до наступних правил:

a) при

b) при

c) при

Схема належить , якщо виконуються спiввiдношення (17) i (18). Оптимальна за порядком оцiнка точностi досяга-ється в рамках проекцiйного методу .

Ранiше задача обчислення мiнiмальних iнформацiйних витрат для традицiйної гальоркiнської схеми дискретизацiї дослiджувалася Г.М.Вайнiкко i Р.Плато у статтi "On the Regularization of Projection Methods for solving Ill-posed Problems"// Numer.Math., 1990, V.57, P.63--79. Порiвняння отриманих ними результатiв iз вiдповiдними оцiнками величини для УПС iз теорем 3.10 i 3.11 дозволяє зробити наступний висновок. Стандартну гальоркiнську схему вдається полiпшити в сенсi величини за рахунок використання гiперболiчного хреста в рамках УПС:

1) для при , де , i при всiх ,

2) для при всiх i .

На закiнчення пiдроздiлу встановлено, що проекцiйнi методи якi побудованi на основi УПС iз теорем 3.10 i 3.11, гарантують збiжнiсть наближень до довiльного нормального розв'язку задачi (1).

Метою дослiджень пiдроздiлу 3.5 є визначення нижнiх оцiнок величини , що дозволяють вказати мiнiмальний порядок iнформацiйної складностi рiвнянь Фредгольма (7) з операторами з класiв i . При цьому встановлено, що побудованi у попередньому пiдроздiлi економiчнi УПС є оптимальними в сенсi використовуваної гальоркiнської iнформацiї (14). Порядковi оцiнки iнформацiйної складностi зазначених класiв iнтегральних рiвнянь наведенi в наступних 3 теоремах.

Теорема 3.15. Для справедливi оцiнки

Оптимальний порядок iнформацiйної складностi проекцiйних методiв на класi iнтегральних рiвнянь (7) з операторами з i реалiзується в рамках УПС за умови, що параметри , i схеми дискретизацiї обранi як у теоремi 3.11.

Теорема 3.17. Для справедливi оцiнки

Оптимальний порядок iнформацiйної складностi проекцiйних методiв на класi iнтегральних рiвнянь (7) з операторами з i реалiзується в рамках УПС за умови, що параметри , i схеми дискретизацiї обранi як у теоремi 3.10.

Теорема 3.18. а) Якщо i , то

b) Якщо , i , то

Оптимальний порядок iнформацiйної складностi проекцiйних методiв на класi iнтегральних рiвнянь (7) з операторами з i реалiзується в рамках УПС за умови, що параметри , i схеми дискретизацiї обранi як у теоремi 3.11. Оцiнки алгоритмiчної складностi проекцiйних методiв розв'язання некоректних задач обчисленi у пiдроздiлi 3.6. Якщо у попереднiх пiдроздiлах 3.4, 3.5, де вивчалася iнформацiйна складнiсть у сенсi величини , проблема зводилася до побудови проекцiйних схем дискретизацiї, що використовують найменшу кiлькiсть скалярних добуткiв (14), то тепер для знаходження алгоритмiчної складностi потрiбно висунути проекцiйний метод , що вимагає при побудовi наближеного розв'язку мiнiмального обсягу е.а.о. Центральнi результати цього пiдроздiлу сформульованi в наступних двох теоремах.

Теорема 3.20. Для справедливi оцiнки

Оптимальний порядок алгоритмiчної складностi проекцiйних методiв на класi iнтегральних рiвнянь (7) з операторами з i реалiзується в рамках методу

Оптимальний порядок алгоритмiчної складностi проекцiйних методiв на класi iнтегральних рiвнянь (7) з операторами з i реалiзується в рамках методу (19), де , за умови, що параметри , i УПС обранi як у теоремi 3.11.

Зауважимо, що оптимальний проекцiйний метод (19), який фiгурує в теоремах 3.20 i 3.21, використовує в якостi регуляризатора узагальнений варiант методу Тихонова.

У пiдроздiлах 3.7 i 3.8 дослiджується ситуацiя, коли оператори у (1) i у (13) є самоспряжними i невiд'ємними. При розв'язуваннi такої задачi апро-ксимуючий оператор рекомендується вибирати також самоспряжним, але необов'язково невiд'ємним. Тому для розв'язання зазначеної проблеми у пiдроздiлi 3.7 будуються симетричнi УПС . Доводиться, що побудованi таким чином проекцiйнi методи гарантують оптимальний порядок точностi на класах рiвнянь (1) iз , де i . Далi обчислюються порядковi оцiнки величини при обраних параметрах УПС. Порiвняння цих оцiнок iз вiдповiдними результатами для гальоркiнської схеми дискретизацiї показує, що УПС забезпечує бiльш економiчний пiдхiд у сенсi величини . У пiдроздiлi 3.8 на розглянутих класах рiвнянь (1) обчислюються нижнi оцiнки для . Одержанi тут результати встановлюють оптимальнiсть у значеннi iнформацiйної складностi для проекцiйних методiв, що побудованi у попередньому пiдроздiлi. Крiм того, порiвняння цих результатiв з оцiнками з пiдроздiлу 3.5 дозволяє зробити несподiваний висновок, що симетрування дискретної схеми призводить при до збiльшення обсягу задiяної гальоркiнської iнформацiї.

Дослiдженню оптимальних проекцiйних методiв розв'язання некоректних задач присвячено також роздiл IV. Характерною рисою останнього роздiлу дисертацiї є вивчання ситуацiї, коли iнформацiя про величину , що фiгурує в означеннi множини , або вiдсутня, або неточна. Побудова наближених методiв за допомогою регуляризаторiв iз вимагає в цьому випадку застосування апостерiорного вибору параметра регуляризацiї. Короткий опис рiзних пiдходiв до такого вибору значення мiститься у пiдроздiлi 4.1. Найбiльша увага при цьому придiляється принципу нев'язки, iдея застосування якого належить В.О.Морозову. Суть названого принципу полягає в припиненнi обчислювальної процедури по досягненнi наперед заданого рiвня вiдхилення, що має порядок . У подальших дослiдженнях дисертацiї задiяний саме цей принцип. На закiнчення пiдроздiлу 4.1 обчислена порядкова оцiнка iнформацiйних витрат найкращої гальоркiнської схеми дискретизацiї, що була запропонована Г.М.Вайнiкко i Р.Плато.

У пiдроздiлi 4.2 вивчається задача побудови оптимальних методiв для iнтегральних рiвнянь (7) з операторами з класiв , , у припущеннi, що оператор вiдомий точно, тобто у (13). Пропонованi алгоритми використовують УПС iз пiдроздiлу 1.2 i принцип нев'язки. В якостi регуляри-затора розглянуто 2 методи з класу : iтерований варiант методу Тихонова i iтерацiйний метод Ландвебера. Обидва алгоритми не тiльки дозволяють полiпшити вiдповiдний результат для стандартної гальоркiнської схеми, але до того ж реалiзують мiнiмальний порядок iнформацiйної складностi. Наведемо постановку дослiджуваної задачi. Отже, потрiбно обчислити величину.

Таким чином, нас цiкавлять тi схеми дискретизацiї, за допомогою яких реалiзується оптимальна за порядком точнiсть наближення для всiх iз деякого iнтервалу .

Тут . За область вiзьмемо гiперболiчний хрест , де - довiльне дiйсне число таке, що при i при . Нехай

Теорема 4.3. Для достатньо малих справедливi оцiнки

Оптимальнi за порядком оцiнки iнформацiйної складностi на розглянутому класi рiвнянь реалiзуються в рамках алгоритму

, ,, а параметр обирається з геометричної сiтки , , , згiдно з умовами

Зазначимо, що вiдмовляючись у рамках запропонованого вище алгоритму вiд знання точного значення , ми в той же час використовуємо значення верхньої межi iнтервалу, якому належить . Необхiднiсть використання обумовлена тим, що iтерований метод Тихонова (20) може гарантувати оптимальну за порядком точнiсть лише для обмеженого дiапазону значень . Щоб позбутися вiд застосування в обчисленнях величини , слiд взяти в якостi регуляризатора iтерацiйний метод iз класу .

На вiдмiну вiд попереднього алгоритму тепер параметр не обирається з геометричної сiтки, а визначається кiлькiстю виконаних крокiв iтерацiйного процесу , .

Як i ранiше, складнiсть дослiджуваної задачi будемо оцiнювати за допомогою величини , причому пiд тепер розумiємо довiльне число, при якому множина не порожня, тобто

Теорема 4.5. При достатньо малих справедливi оцiнки

Слiд зазначити, що побудованi в теоремах 4.3, 4.5 алгоритми мають такi властивостi:

забезпечують збiжнiсть до довiльного нормального розв'язку,

гарантують оптимальну збiжнiсть до будь-якого розв'язку з множини

, ,

не вимагають знання величини ,

використовують мiнiмально можливий обсяг гальоркiнської iнформацiї.

У заключному пiдроздiлi дисертацiї дослiджена задача скорочення кiлькостi дискретної iнформацiї, що використовується при розв'язуваннi рiвнянь (1) з операторами з класу i з нормальними розв'язками при всiх . У випадку фiксованого точно вiдомого значення гальоркiнська схема дискретизацiї була полiпшена лише при (див. пiдроздiл 3.5). А оскiльки найбiльший обсяг дискретної iнформацiї, що необхiдна для досягнення оптимального порядку точностi, потрiбний саме при , то досягнення поставленої мети в дослiджуванiй ситуацiї було б несподiваним фактом. Проте застосування адаптивної стратегiї при дискретизацiї дозволяє побудувати бiльш економiчнi алгоритми.

Ранiше iдея адаптивної дискретизацiї некоректних задач була запропонована Е.Шоком. Суть цiєї iдеї полягає в узгодженнi рiвня дискретизацiї з параметром регуляризацiї. Введемо в розгляд нову адаптивну стратегiю дискретизацiї, яка полягає у використаннi оператора i характеризується вибором рiвня дискретизацiї вiдповiдно до спiввiдношення

Тут параметр збiльшується при зменшеннi величини згiдно з правилом

дискретизація інтегральний оператор рівняння

.

На основi адаптивного пiдходу до дискретизацiї (22) побудованi 2 алгоритми для розв'язання некоректних задач, що в якостi регуляризатора використовують iтеративний метод Тихонова (20) i процедуру Ландвебера (21) вiдповiдно. Причому в рамках цих алгоритмiв вибiр параметра регуляризацiї здiйснюється вiдповiдно до принципу нев'язки.

Будемо вважати, що , . Розпишемо докладно перший iз пропонованих алгоритмiв:

Вихідні дані: , , , , .

Ініціалізація: , .

Ітерація по :

а) вибір параметра регуляризації :

б) вибір рівня дискретизації (,):

в) обчислення скалярних добутків

г) обчислення наближеного розв'язку згідно з ітерованим методом Тихонова і принципом нев'язки

Теорема 4.6. Для досягнення оптимального порядку точностi на класi рiвнянь (1) з операторами i з нормальними розв'язками , , алгоритму (23)-(26) потрібно значень функцiоналiв вигляду (14). Як випливає з результатiв Г.М.Вайнiкко i Р.Плато, алгоритмам, що використовують гальоркiнську схему дискретизацiї, для забезпечення на тих самих класах рiвнянь (1) найкращої точностi потрiбно гальоркiнської iнформацiї. Порiвняння оцiнок (27) i (28) дозволяє зробити висновок, що запропонований вище метод є бiльш економiчним при будь-якому .

Перейдемо до другого алгоритму:

Вихідні дані: , , , .

Ініціалізація: ,

Ітерація по :

а) вибір параметра регуляризації :

б) вибір рівня дискретизації (,):

в) обчислення скалярних добутків (24);

г) обчислення наближеного розв'язку згідно з процедурою Ландвебера

Теорема 4.7. Для досягнення оптимального порядку точностi на класi рiвнянь (1) з операторами i з нормальними розв'язками , алгоритму (24), (29)-(31) потрiбно (27) гальоркiнської iнформацiї (14).

Порiвняємо побудованi в теоремах 4.6 i 4.7 алгоритми. Отже, обидва алгоритми гарантують найкращу за порядком точнiсть розв'язання рiвнянь iз розглянутого класу i використовують однаковий за порядком обсяг (27) гальоркiнської iнформацiї. Разом з тим останнiй алгоритм має певнi переваги у порiвняннi з алгоритмом (23)-(26). Насамперед при реалiзацiї алгоритму (24), (29)-(31) вiдсутнє так зване насичення, тобто оптимальний порядок точностi досягається при всiх одночасно. Далi, другий алгоритм має бiльш просту структуру. А саме, у першому випадку виконується подвiйна iтерацiя - ми переходимо до наступного значення , розв'язавши разiв вiдповiдне рiвняння Ейлера (25). У той же час останнiй алгоритм являє собою ординарну iтерацiйну процедуру. Нарештi, метод Ландвебера є явною iтерацiйною схемою. Iншими словами, у рамках алгоритму (24), (29)-(31) не виникає потреби розв'язувати систему рiвнянь, оскiльки всi члени в правiй частинi (30) вiдомi.

Окремо розглянуто ситуацiю, коли нижня межа можливих значень вiдома i дорiвнює . У цьому випадку вдається також побудувати оптимальнi проекцiйнi методи, що використовують бiльш економiчну УПС у порiвняннi з гальоркiнською схемою.

На закiнчення пiдроздiлу 4.3 наведенi результати обчислювання тестових прикладiв, за допомогою яких демонструється ефективнiсть алгоритмiв, що використовуються в теоремах 4.6 i 4.7.

Висновки

Розвинуто iдею гiперболiчного хреста. Це дозволило розробити новi проекцiйнi схеми дискретизацiї для ефективного розв'язання операторних рiвнянь I i II роду.

На основi отриманих схем побудованi проекцiйно-iтеративнi методи, що гарантують найкращу за порядком точнiсть розв'язання на широких класах рiвнянь Фредгольма II роду з коефiцiєнтами скiнченної гладкостi.

Знайдено точний у степеневiй шкалi порядок алгоритмiчної складностi наближеного розв'язання рiвнянь Вольтерра другого роду з нескiнченно диференцiйовними ядрами.

Визначено точнi порядки iнформацiйної i алгоритмiчної складностi операторних рiвнянь, що є узагальненням iнтегральних рiвнянь Фредгольма першого роду з коефiцiєнтами скiнченної гладкостi. У випадку апрiорного вибору параметра регуляризацiї побудованi оптимальнi в сенсi складностi проекцiйнi методи розв'язання некоректних задач, що використовують новi схеми дискретизацiї.

5. Знайдено порядки iнформацiйної складностi проекцiйних методiв на класах рiвнянь I роду у випадку, коли параметр регуляризацiї обирається апостерiорi.6. Встановлено, що використання симетричних схем при дискретизацiї рiвнянь із самоспряжними невiд'ємними операторами призводить до iстотного збiльшення обсягу задiяної дискретної iнформацiї.

7. Побудовано алгоритми розв'язання некоректних задач, що являють собою комбiнацiю запропонованого адаптивного пiдходу до дискретизацiї, принципу нев'язки i деяких методiв регуляризацiї (iтерованого методу Тихонова i методу Ландвебера). Встановлено, що цi алгоритми є бiльш економiчними у сенсi використаної дискретної iнформацiї, нiж стандартнi методи.Результати дисертацiї, що викладенi в роздiлах III i IV, є першими в галузi складностi некоректних задач. Iдеї i методи, що розвиненi в дисертацiї, були використанi в багатьох iнших роботах (див., наприклад, посилання [125,135] дисертацiї). Все це дозволяє зробити висновок, що дисертацiя є новим важливим кроком у розвитку теорiї оптимальних алгоритмiв, а її результати мають численнi зв'язки з iншими результатами в цiй галузi i можуть бути використанi у вiдповiдних дослiдженнях.

Основні положення дисертації опубліковані в наступних роботах

1. Солодкий С.Г. Оптимизация алгоритмов приближенного решения уравнений Вольтерра с бесконечно дифференцируемыми ядрами // Укр.мат.журн.- 1994. - 46, N 11. - С.1534--1545.

2. Солодкий С.Г. Сложность уравнений Фредгольма II рода с ядрами из анизотропных классов дифференцируемых функций //Укр.мат. журн. - 1996. - 48, N 4. - С.525--532.

3. Солодкий С.Г. Сложность проекционных методов решения некорректных задач // Укр.мат.журн. - 1996. - 48, N 8. - С.1114--1124.

4. Pereverzev S.V., Solodky S.G. The Minimal Radius of Galerkin Information for the Fredholm Problem of the First Kind// 1996. -- 12. -- P.176--202.

5. Pereverzev S.V., Solodky S.G. An efficient Discretization for Solving Ill-Posed Problems// Lectures in Applied Mathematics. -- 1996. -- 32. -- P.643--649.

6. Солодкий С.Г. О дискретизации некорректных задач // Журн. вычисл. математики и мат.физики. - 1996. - 36, N 8. - С.15--22.

7. Солодкий С.Г. Экономичный подход к дискретизации метода М.М.Лаврентьева // Сиб.мат.журн. - 1997. - 38, N 2. - С.396--404.

8. Солодкий С.Г. Об информационной сложности некоторых классов операторных уравнений// Укр.мат.журн. - 1997. - 49, N 9. - С.1271--1277.

9. Солодкий С.Г. Об одном подходе к дискретизации некорректных задач // Докл. РАН. - 1997. - 356, N 5. - С.608--611.

10.Солодкий С.Г. Об одной схеме дискретизации уравнений Фредгольма I рода // Дифференц.уравнения. - 1997. - 33, N 11. - С.1547--1551.

11.Солодкий С.Г. Информационная сложность проекционных алгоритмов решения уравнений Фредгольма I рода. I// Укр.мат.журн. - 1998. - 50, N 5. - С.699--711.

12.Солодкий С.Г. Информационная сложность проекционных алгоритмов решения уравнений Фредгольма I рода. II// Укр.мат.журн. - 1998. - 50, N 6. - С.838--844.

13.Солодкий С.Г. О модификации проекционной схемы решения некорректных задач // Изв. вузов. Математика. - 1998. - N 11. - С.83--90.

14.Солодкий С.Г. Оптимизация проекционных методов решения линейных некорректных задач// Журн.вычисл.математики и мат. физики. - 1999. - 39, N 2. - С.195--203.

15.Солодкий С.Г. Оптимизация проекционных схем дискретизации некорректных задач// Укр.мат.журн. - 1999. - 51, N 10. - С.1398--1410.

16.Solodky S.G. Complexity for some classes of well-posed problems // Proc. Estonian Sci. Phys. Math. -- 1999. -- 48, N 2. -- P.123--132.

17.Solodky S.G. A generalized projection scheme for solving ill-posed problems // Journal of Inverse and Ill-Posed Problems. -- 1999. -- 7, N 2. -- P.185--200.

18.Переверзев С.В., Солодкий С.Г. Оптимальная дискретизация некорректных задач // Укр.мат.журн. - 2000. - 52, N 1. - С.106--121.

19.Maass P., Pereverzev S.V., Ramlau R., Solodky S.G. An adaptive discretization for Tikhonov-Phillips regularization with a posteriori parameter selection // Numer. Math. -- 2001. -- 87. -- P.485--502.

20.Solodky S.G. The Optimal Approximations for Solving Linear Ill-Posed Problems// Journal of Complexity. -- 2001. -- 17, N 1. -- P.98--116.

21.Солодкий С.Г. Адаптивная дискретизация некорректных задач // Докл. РАН. - 2002. - 382, N 4. - С.460--462.

22.Solodky S.G. Information Complexity of Some Classes of Ill-Posed Problems// Abstracts of the International Seminar on Algorithms and Complexity for Continuous Problems. - Dagstuhl (Germany), 1996. -- P.17.

23.Солодкий С.Г. Проекцiйна схема дискретизацiї некоректних задач// Тези доповiдей II-й школи Ряди Фур'є: теорiя i застосування. - Київ (Україна), 1997. -- C. 117.

24.Solodky S.G. Optimization of projection methods for solving ill-posed problems// Abstracts of the International Conference on Approximation methods and orthogonal expansions. - Tartu (Estonia), 1998. -- P.31.

25.Solodky S.G. Optimization of projection methods for solving linear ill-posed problems // International Congress of Mathematicians. Abstracts of Short Communications. -- Berlin (Germany), 1998. -- P.314--315.

26.Солодкий С.Г. Конечномерная модификация некоторых методов регуляризации// Шоста Кримська Мiжнародна математична школа МФЛ-2002. - Сiмферополь (Україна), 2002. -- C. 132.

Анотації

Солодкий С.Г. Оптимальнi схеми дискретизацiї операторних рiвнянь. - Рукопис.

Дисертацiя на здобуття наукового ступеня доктора фiзико-математичних наук за спецiальностю 01.01.07. - обчислювальна математика. - Iнститут математики НАН України, Київ, 2003

Дисертацiя присвячена дослiдженню складностi операторних рiвнянь I i II роду, що є узагальненням iнтегральних рiвнянь Фредгольма i Вольтерра. Головна увага придiляється розвитку проекцiйних схем дискретизацiї, що використовують iдею гiперболiчного хреста. За допомогою цих схем для широких класiв операторних рiвнянь обчисленi точнi порядки iнформацiйної i алгорітмичної складностi. Для некоректних задач (рiвнянь I роду з компактними операторами) побудованi оптимальнi наближенi методи як у випадку апрiорного, так i апостерiорного вибору параметра регуляризацiї. На прикладi рiвнянь з операторами соболєвського типу гладкостi демонструється перевага адаптивної стратегiї дискретизацiї у порiвняннi зi стандартними методами.

Ключовi слова: узагальнена проекцiйна схема дискретизацiї, гальоркiнська iнформацiя, гiперболiчний хрест, iнформацiйна складнiсть, алгорітмична складнiсть, некоректна задача, метод регуляризацiї, параметр регуляризацiї, принцип нев'язки, адаптивна стратегiя дискретизацiї.

Солодкий С.Г. Оптимальные схемы дискретизации операторных уравнений. - Рукопись.

Диссертация на соискание ученой степени доктора физико-математических наук по специальности 01.01.07. - вычислительная математика. - Институт математики НАН Украины, Киев, 2003.

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

Диссертационная работа включает введение, четыре главы, выводы и список литературы из 138 наименований. Общий объем работы составляет 300 страниц машинописного текста.

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

Первая глава диссертации содержит определения математических понятий, служащих объектами дальнейших исследований, а также доказательство ряда вспомогательных утверждений. Приводятся основные типы линейных интегральных уравнений Фредгольма и Вольтерра. В краткой форме излагаются сведения об истории развития приближенных методов решения уравнений. Особое внимание при этом уделяется освещению проблемы оптимизации таких методов. Дается определение проекционной схемы дискретизации. Вводятся в рассмотрение две новые проекционные схемы дискретизации, построенные на идее гиперболического креста. Вычислены порядковые оценки общего количества дискретной информации, задействованной предлагаемыми схемами. Содержится определение классов интегральных операторов с ядрами конечной гладкости и их обобщений. При этом рассматриваются ядра двух модельных типов гладкости: ядра соболевского типа гладкости и ядра, имеющие доминирующую смешанную частную производную. В заключение главы установлен ряд аппроксимационных свойств изучаемых классов операторов при помощи предлагаемых схем дискретизации.

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

Третья глава посвящена приближенному решению уравнений первого рода с компактными операторами. Дается понятие некорректной по Адамару задачи, содержится краткий обзор основных направлений исследования таких задач. Излагается постановка изучаемых в диссертации проблем. Объектом исследований является сложность некорректных задач. При этом под информационной сложностью понимается наименьший объем дискретной информации, необходимый для нахождения приближенного решения с заданной точностью, а под алгоритмической сложностью - минимальное число арифметических операций, которые требуется выполнить для построения этого решения. Приводится определение метода регуляризации некорректной задачи, а также ряд примеров наиболее известных методов регуляризации. Рассмотрена задача построения проекционных методов, обеспечивающих в гильбертовом пространстве сходимость по норме аппроксимаций к искомому решению. Установлены достаточные условия на параметры регуляризации и проекционных схем, при выполнении которых сходимость приближений гарантирована. Построены проекционные методы решения уравнений первого рода, достигающие оптимальный порядок точности на множествах истокопредставимых решений в случае априорного выбора параметра регуляризации. Параметры задействованных схем дискретизации выбраны таким образом, чтобы обеспечить минимально возможные затраты дискретной информации. Проведено сравнение полученных при этом оценок информационных затрат с известными ранее результатами. Установлено преимущество предлагаемых методов в указанном смысле. Вычислены порядковые оценки информационной и алгоритмической сложности некорректных задач. Отдельно исследована ситуация, когда оператор решаемого уравнения является самосопряженным и неотрицательным. Исследованию оптимальных методов решения некорректных задач при условии апостериорного выбора параметра регуляризации посвящена четвертая глава. Содержится краткое описание различных подходов к такому выбору параметра регуляризации. Наибольшее внимание уделено принципу невязки, идея применения которого принадлежит В.А.Морозову. Построены алгоритмы решения операторных уравнений первого рода, состоящие в комбинации предлагаемой схемы дискретизации, принципа невязки и методов регуляризации (итерированного метода Тихонова и итерационной процедуры Ландвебера). В случае операторов из классов соболевского типа гладкости удается применить адаптивную стратегию дискретизации, состоящую в изменении объема задействованной дискретной информации на основе выполненных ранее вычислений. Такой подход позволяет строить алгоритмы, экономичные в смысле информационных затрат. В случае операторов с ядрами второго модельного типа гладкости вычислен точный порядок информационной сложности.

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

Solodky S.G. Optimal discretization schemes for operator equations. --Manuscript.

Thesis for a scientific degree of Doctor of Physical and Mathematical Sciences, speciality 01.01.07. - computational mathematics. The National Ukrainian Academy of Sciences, Institute of Mathematics, Kiev, 2003.

The thesis is devoted to the investigation of the complexity of first and second kind operator equations that can be considered as a generalization of integral Fredholm and Volterra equations. The main attention is paid to the development of projection discretization schemes used the idea of hyperbolic cross. By means of such schemes the exact order estimates of information and algorithmic complexity are computed for wide classes of operator equations. For ill-posed problems (for equations of the first kind with compact operators) the optimal approximation methods are constructed in the case of apriori as well as of aposteriori choice of regularization parameter. By examples of equations with operators of Sobolev smoothness it is demonstrated the advantage of the adaptive discretization strategy in comparison with standard methods.

Keywords: generalized projection scheme of discretization, Galerkin informa-tion, hyperbolic cross, information complexity, algorithmic complexity, ill-posed problem, regularization method, regularization parameter, discrepancy principle, adaptive discretization strategy.

Размещено на Allbest.ru

...