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

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

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

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

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

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

К и ї в -- 2 0 0 3

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

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

Офіційні опоненти: доктор фіз.-мат.наук, професор

Морозов Володимир Олексійович,

науково-дослідний обчислювальний центр

Московського державного університету

ім. М.В.Ломоносова,

головний науковий співробітник

доктор фіз.-мат.наук, професор

Бабич Михайло Данилович,

Інститут кібернетики ім.В.М.Глушкова НАН України,

провідний науковий співробітник

доктор фіз.-мат.наук, професор

Сявавко Мар'ян Степанович,

Львівський державний аграрний університет,

завідувач кафедри

Провідна установа: Львівський національний університет

ім. І.Франка, кафедра інформаційних систем

Захист відбудеться "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в, вико-

ристовуваних т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 методи розв'язання яких буду-ються в роздiлах II--IV. Наведемо опис цих класiв.

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

де . Надалi при побудовi УПС базис обирається вiдповiдно до умови (3).

Для будь-яких покладемо

де - простiр лiнiйних операторiв , а такий оператор, що рiвнiсть виконується при будь-яких .

Обидва класи операторiв є модельними при вивченн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д .

Теорема 2.2. При

Оптимальний в степеневiй шкалi порядок складностi для класу рiвнянь

надають гальоркiнська iнформацiя

i алгоритм

Теорема 2.3. При

Оптимальний в степеневiй шкалi порядок складностi для класу рiвнянь

реалiзується в рамках алгоритму

що використовує iнформацiю (9).

Теорема 2.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внянь (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сце

Теорема 2.7. При

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

i iтеративний метод

де - локальний сплайн мiнiма-льного дефекту по рiвномiрному розбиттю (12), що побудований у виглядi лiнiйної комбiнацiї -сплайнiв порядку , а - скiнченновимiрний оператор

з ядром у виглядi двовимiрного iнтерполяцiйного оператора Лагран-жа, побудованого на сiтцi з вузлiв Чебышова (11).

Трет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 такi, що i , причому при деякiй констант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), (13) розум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 р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 3.10.

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

b) Якщо параметри , , такi, що точка належить множинi

то

c) Якщо параметри , , так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йсне число таке, що при 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ємо довiльне число, при якому множина не порожня, тобто

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

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

класi рiвнянь реалiзуються в рамках алгоритму

де , , параметр задовольняє спiвв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в:

1.

2.

3.

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

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

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

г) обчислення наближеного розв’язку згідно з ітерованим мето-

дом Тихонова

і принципом нев’язки

Теорема 4.6. Для досягнення оптимального порядку точностi на класi рiвнянь (1) з операторами i з нормальними розв'язками , , алгоритму (23)-(26) потрiбно

значень функцiоналiв вигляду (14).

Як випливає з результатiв Г.М.Вайнiкко i Р.Плато, алгоритмам, що вико-ристовують гальоркiнську схему дискретизацiї, для забезпечення на тих самих класах рiвнянь (1) найкращої точностi потрiбно

гальоркiнської iнформацiї. Порiвняння оцiнок (27) i (28) дозволяє зробити висновок, що запропонований вище метод є бiльш економiчним при будь-якому

.

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

1.

2.

3.

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

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

в) обчислення скалярних добутків (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.

ВИСНОВКИ

1.

2.

гарантують найкращу за порядком точнiсть розв'язання на широких класах

рiвнянь Фредгольма II роду з коефiцiєнтами скiнченної гладкостi.

3.

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

4.

торних р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дженнях.

Автор збер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// Journal of Complexity. -- 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.Солодкий С.Г.

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