Оптимальні за точністю стратегії розв’язування некоректних задач

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

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

Оптимальні за точністю стратегії розв'язування некоректних задач

Автореферат

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

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

Актуальність теми

На сьогоднішній день спостерігається значний інтерес дослідників до проблем ефективного розв'язування некоректних задач, що обумовлено широкою областю їх застосування у багатьох галузях науки - таких, як гідродинаміка, геофізика, нелінійна оптика, спектроскопія, астрофізика, рентгенівська томографія, теорія обробки сигналів і зображень тощо. Основи теорії некоректних задач було закладено ще в 60-70-х роках XX ст. в роботах А.М. Тіхонова, М.М. Лаврент'єва, В.К. Іванова та їх учнів. Подальший розвиток цієї області обчислювальної математики привів до розробки великої кількості стійких методів розв'язування некоректних задач, а це, в свою чергу, викликало потребу у класифікації цих методів. Відповідно до сучасних вимог обчислювальної математики важливими критеріями ефективності наближених методів є точність апроксимації шуканого розв'язку і об'єм інформаційних витрат.

Вперше проблему побудови алгоритмів розв'язування некоректних задач, економічних з огляду об'єму використаної дискретної інформації, було розглянуто в статті Г.М. Вайнікко і Р. Плато 1990 р., де для дискретизації задачі застосовувалася стандартна проекційна схема Гальоркіна.

Подальший розвиток досліджень у цьому напрямку пов'язаний з модифікацією стандартної гальоркінської схеми дискретизації. Перший результат на шляху підвищення ефективності (у вказаному значенні) алгоритмів був отриманий С.В. Переверзєвим у 1995 р. за рахунок застосування східчастого гіперболічного хреста для дискретизації некоректних задач у випадку відомої гладкості шуканого розв'язку. У подальшому ця ідея була узагальнена С.Г. Солодким, що дозволило підвищити ефективність методів шляхом підбору параметрів гіперболічного хреста в залежності від гладкісних властивостей вхідних даних задачі. Такий підхід дозволив розробити багато ефективних стійких алгоритмів розв'язування широких класів некоректних задач. Вказаними проблемами також займалися E. Schock, P. Maass, R. Ramlau, U. Tautenhahn, P. Mathe, M.T. Nair, X. Luo, F. Li та інші. Проте всі попередні дослідження не вичерпали до кінця можливостей застосування модифікованої проекційної схеми дискретизації. Зокрема, залишилися відкритими питання про ефективність використання такого підходу в комбінації з багатьма методами регуляризації при застосуванні адаптивної схеми дискретизації некоректних задач.

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

Зв'язок роботи з науковими програмами, планами, темами

Робота проводилася згідно з загальним планом досліджень відділу теорії наближень Інституту математики НАН України в рамках держбюджетних тем ``Оптимізація методів чисельного аналізу і паралельних обчислень'' (номер 0105U000155) та ``Оптимізація методів розв'язування некоректних задач та розвиток теорії паралельних асинхронних обчислень'' (номер 0111U001010).

Мета і завдання дослідження

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

Об'єктом дослідження є лінійні некоректні задачі.

Предметом дослідження є чисельні методи наближеного розв'язування лінійних некоректних задач.

Як методи дослідження у дисертаційній роботі використовуються методи функціонального аналізу та обчислювальної математики.

Наукова новизна одержаних результатів

Основні результати, які визначають наукову новизну і виносяться на захист, такі:

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

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

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

Практичне значення одержаних результатів

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

Особистий внесок здобувача

Постановка задач і визначення загального плану досліджень належать науковому керівнику і співавтору робіт С.Г. Солодкому. Всі результати дисертації, що виносяться на захист, отримано автором самостійно.

Апробація результатів дисертації

Основні результати дисертації доповідалися і обговорювалися на семінарах Інституту математики НАН України, а також на:

* Mini-school ``Inverse and Ill-posed problems'' (Warsaw, March 25 - 28, 2008);

* українському математичному конгресi - 2009 (до 100-річчя від дня народження Миколи Боголюбова) (Київ, 27 - 29 серпня 2009 року);

* міжнародному симпозіумі ``Питання оптимізації обчислень - XXXV'' (Крим, Кацивелі, 24 - 29 вересня 2009 року);

* конференції ``Сучасні проблеми прикладної математики та інформатики'' (Львів, 8 - 9 жовтня 2009 року);

* конференції ``Теория приближений и ее приложения (памяти Николая Павловича Корнейчука)'' (Дніпропетровськ, 14-17 червня 2010 року);

* Mini Special Semester on Inverse Problems at RICAM (Linz, June 29 - July 3, 2010);

* міжнародній конференції ``Integral equations - 2010'' (Львів, 25-27 серпня 2010 року).

Публікації. Основні результати роботи опубліковано в 9 роботах, з них 4 статті - у спеціалізованих фахових журналах і 5 - у тезах доповідей наукових конференцій.

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

Основний зміст роботи

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

У вступі обґрунтовано актуальність теми дисертації, сформульовано мету дослідження, коротко викладено зміст основних результатів роботи.

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

(1)

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

де - рівень похибки вхідних даних.

В параграфі 1.1 наведені означення коректності задачі за Адамаром та нормального розв'язку , а також сформульована умова джерела гельдерівського типу гладкості:

(2)

де , - відома стала, а - невідома величина.

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

(3)

де - параметр регуляризації, а система функцій є твірною системою для цього методу. Функції вважаються кусково-неперервними на відрізку і такими, що задовольняють такі додаткові умови:

(4)

Тут , а , - додатні константи, незалежні від .

Наприкінці параграфу 1.2 наведено приклади найбільш відомих методів регуляризації, що задовольняють умови (3) - (4). Кваліфікація методу визначає клас задач з розв'язками (2), на яких в межах цього методу можна досягти оптимальний порядок точності.

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

В другому розділі введено до розгляду класи , , компактних лінійних операторів , , що діють в гільбертовому просторі і при будь-якому і деяких фіксованих задовольняють умови

Тут - ортопроектор на лінійну оболонку перших елементів деякого ортонормованого базису в . У випадку замість використовується позначення .

Через позначаємо клас рівнянь (1) з операторами , розв'язками гельдерівського типу гладкості (2) та правими частинами , що заповнюють в просторі кулю радіусу з центром в , а невідомий параметр , який характеризує ступінь гладкості розв'язку, належить до інтервалу .

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

(5)

У параграфі 2.2 запропонована модифікована проекційна схема дискретизації, основна ідея якої полягає у виборі області , з якої вибираються індекси скалярних добутків (5), у вигляді гіперболічного хреста

(6)

де

(7)

Згідно з цією схемою дискретизації використовуються скінченновимірні вхідні дані

 (8)

Метод регуляризації обирається відповідно до умов (3) - (4), оператор має вигляд (8), а значення параметра дискретизації знаходиться зі співвідношення

(9)

За правило зупинки відповідної обчислювальної процедури використано принцип нев'язки: обчислення зупинятимемо як тільки буде виконуватися умова

(10)

при деяких фіксованих константах .

Будь-який регуляризуючий проекційний метод, який задовольняє умови (3) - (4), (7) - (10), будемо позначати .

Основний результат цієї частини дисертації сформульовано у параграфі 2.3.

Теорема 1. В рамках будь-якого методу на класі , , досягається оптимальна за порядком оцінка похибки .

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

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

В параграфі 3.2 розглядається комбінація адаптивної стратегії дискретизації і -методу регуляризації для наближеного розв'язування некоректних задач з класу у разі розв'язків з при . Запропонований алгоритм за правило зупинки використовує принцип нев'язки і полягає в наступній послідовності кроків:

Алгоритм I

1. Вхідні дані:

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

3. Ітерації по

- вибір рівня дискретизації як мінімального натурального числа, що задовольняє умову

- якщо значення змінилося, то і обчислюється гальоркінська інформація з номерами індексів з області :

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

(11)

де , - відомі сталі.

4. Правило зупинки згідно з принципом нев'язки

де .

5. Наближений розв'язок: .

Оцінку точності запропонованого алгоритму отримано в параграфі 3.3.

Теорема 2. Алгоритм I досягає оптимальний порядок точності на класі рівнянь , .

Наслідок 1. Для досягнення оптимального порядку точності на цьому класі рівнянь в рамках алгоритму I достатньо обчислити

(12)

гальоркінських функціоналів.

Добре відомо, що для досягнення оптимального порядку точності на класах в рамках стандартної неадаптивної гальоркінської схеми дискретизації необхідно обчислити скалярних добутків (5). Таким чином, запропонований алгоритм використовує значно менший об'єм дискретної інформації в порівнянні зі стандартними методами.

В параграфах 3.4, 3.5 досліджуються апроксимаційні властивості адаптивної схеми дискретизації на класах у випадку довільного , тобто при відсутності будь-яких обмежень на гладкість шуканого розв'язку. Для такої задачі використано регуляризатор з більш високою кваліфікацією, а саме, метод Факєєва - Ларді.

Структура досліджуваного в параграфі 3.4 алгоритму II аналогічна обчислювальній схемі алгоритму I з урахуванням використання іншого методу регуляризації, тобто наближений розв'язок обчислюється не за правилом (11), а у відповідності до методу Факєєва - Ларді

де .

Оцінку точності цього алгоритму отримано в параграфі 3.5.

Теорема 3. Алгоритм II досягає оптимальний порядок точності на класі рівнянь , .

Наслідок 2. Для досягнення оптимального порядку точності на цьому класі рівнянь в рамках алгоритму II достатньо обчислити (12) гальоркінських функціоналів.

Таким чином, алгоритм II також досягає оптимальний порядок точності. До того ж, на відміну від алгоритму I, він може ефективно застосовуватися на більш широких класах задач завдяки більш високій кваліфікації задіяного методу регуляризації.

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

(13)

з оператором , Тут - обмежена -вимірна область з неперервною за Ліпшицем межею, а ядро таке, що є компактним оператором з нескінченновимірною областю значень, який діє з в .

Вважаємо, що оператор діє уздовж шкали соболєвських просторів з кроком , тобто знайдуться такі константи , що для фіксованого і всіх

Нехай - деяка скінченна множина попарно різних точок. Розглянемо напівдискретне рівняння

(14)

де , , а оператор визначений за правилом , , тобто - звуження на множину ().

Якщо - точний розв'язок початкового рівняння (13), то він є також розв'язком (14) і може бути представлений у вигляді

де - узагальнений обернений оператор Мура-Пенроуза до , а належить ядру . Наближення будуватимемо до елементу .

Густина даних множини в області визначається таким чином:

У параграфі 4.2 запропоновано алгоритм, який використовує ітерований метод Тіхонова. Позначимо символом наближений розв'язок, отриманий за допомогою цього методу на -му кроці ітерації:

де - тотожний оператор.

Розбиття множини вважатимемо рівномірним, тобто при деякій константі . Тоді справджується нерівність

(15)

Тут

де - деяка відома стала.

Оптимальне значення параметра регуляризації врівноважує значення цих двох функцій, тобто і

Для вибору параметра регуляризації використаємо принцип рівноваги. Для його реалізації розглянемо множини

 (16)

За параметр регуляризації в рамках принципу рівноваги береться елемент

(17)

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

Теорема 4. Для ітерованого методу Тіхонова при виборі значення параметра регуляризації згідно з принципом рівноваги (17) має місце оцінка

Наслідок 3. Має місце оцінка

де . Зокрема, якщо для , то

У параграфі 4.3 отримано аналогічний результат для іншого регуляризатора, а саме, -методу. Отже, нехай - наближений розв'язок, отриманий за допомогою цього методу:



де , - відомі величини, а

(18)

Відповідний результат міститься у наступному твердженні.

Теорема 5. Для -методу при параметрі регуляризації , обраному згідно з принципом рівноваги з множини (18), має місце оцінка

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

У параграфі 4.4 представлено результати обчислювального експерименту, який підтверджує ефективність підходу, запропонованого у параграфі 4.2.

Висновки

У дисертаційній роботі отримано такі основні результати:

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

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

* Для напівдискретних некоректних задач у шкалах соболєвських просторів було розроблено два алгоритми, які для регуляризації використовують ітерований метод Тіхонова і -метод, відповідно. При цьому показано, що вказані алгоритми є оптимальними за порядком при застосуванні принципу рівноваги для вибору значення параметра регуляризації.

Список опублікованих праць за темою дисертації

1. Лукьянова Е.А. О минимизации объёма дискретной информации при решении некорректных задач / Е.А. Лукьянова, Е.А. Волынец // Динамические системы. - 2007. - №22. - C. 11-20.

2. Solodky S.G. On the efficient method of solving ill-posed problems by adaptive discretization / S.G. Solodky, E.A. Volynets // Зб. праць Інституту математики НАН України. - 2009. - Т. 6, №2. - С. 524-549.

3. Solodky S.G. Adaptive scheme of discretization for one semiiterative method in solving ill-posed problems / S.G. Solodky, E.A. Volynets // Український математичний вісник. - 2010. - Т. 7, №4. - С. 553-569.

4. Pereverzev S.V. The balancing principle in solving semi-discrete inverse problems in Sobolev scales by Tikhonov method / S.V. Pereverzev, S.G. Solodky, E.A. Volynets // Applicable Analysis. - The special Klibanov Issue. - 2011. - P. 1-13.

5. An ecnomical discretization strategy for -method: матеріали українського математичного конгресу - 2009 (до 100-річчя від дня народження Миколи Боголюбова), (Київ, 27-29 серп. 2009 р.) / Інститут математики НАН України, 2009.

6. Про економічну стратегію дискретизації некоректних задач: матеріали XVI Всеукр. наукової конф. [«Сучасні проблеми прикладної математики та інформатики»], (Львів, 8-9 жовтня 2009 р.). - Львів: ЛНУ ім. Івана Франка, 2009. - Т. 2. - C 196.

7. Об эффективном использовании адаптивной схемы дискретизации для решения линейных некоректных задач: праці міжн. симпозіуму [«Питання оптимізації обчислень - XXXV»], (Кацивелі, 24-29 вересня 2009 р). Ін-т кібернетики ім. В.М. Глушкова НАН України. - К.: Ін-т кібернетики ім. В.М. Глушкова НАН України, - 2009. С. 328-333.

8. About solving semi-discrete inverse problems in Sobolev scales by Tikhonov method: зб. тез наукової конф. [«Теория приближений и ее приложения (памяти Николая Павловича Корнейчука)»], (Дніпропетровськ, 14-17 червня 2010 р.) / Дніпропетровський нац. ун-т ім. О. Гончара. - 2010. С. 70-71.

9. Aposteriory parameter choice in solving semi-discrete problems in Sobolev scales by Tikhonov method: procidings of the intern. conference [«Integral equations - 2010»], (Львів, 25-27 серп. 2010 р.). - Львів: ЛНУ ім. Івана Франка, 2010.

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