Точність та обчислювальна складність наближеного розв’язування нелінійних функціональних рівнянь

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

Національна академія наук України

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

УДК 517.957

Автореферат

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

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

Спеціальність 01.05.02 -- математичне моделювання та обчислювальні методи

Мамай Леся Михайлівна

Київ 2009

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

Актуальність теми. Наукові дослідження сучасних складних природничих явищ і процесів, що виникають у фізиці, хімії, біології, економіці, екології та інших областях діяльності людини реалізуються шляхом створення та дослідження їх математичних моделей. Такі моделі розглянуті і досліджені у роботах багатьох вчених, зокрема І.В. Сергієнка, В.С. Дейнеки, В.Л. Макарова, В.К. Задіраки, В.В. Скопецького, А.В. Гладкого, А.О. Чикрія та інших. У багатьох випадках математичні моделі характеризуються нелінійними функціональними рівняннями (НФР), зокрема нелінійними інтегральними рівняннями (НІР) та системами нелінійних скалярних рівнянь (СНСР). Проте до цього часу не досить добре вивчена та досліджена проблема глобального розв'язування таких рівнянь. Це пояснюється складністю задачі, оскільки, як відомо, НФР, в залежності від своєї структури, можуть мати один розв'язок, скінчене чи нескінченне число розв'язків або в розглядуваній області не мати їх взагалі, причому ні кількість розв'язків ні місце їх розташування наперед не відомі. Процес розв'язування таких рівнянь складається з двох етапів: відокремлення ізольованих розв'язків та їх ітераційного уточнення.

На відміну від процесу відокремлення розв'язків, процес уточнення за допомогою ітераційних методів, розробці і дослідженню яких присвячені, зокрема, роботи Л.В. Канторовича, М.А. Красносельського, Г.М. Вайнікко, Л.А. Ківістіка, В.М. Фрідмана, є досить добре вивчений. Відокремлення розв'язків, що полягає у знаходженні області єдиності розв'язку досліджений слабо. В теоретичному плані цей процес базується на елементах загальної теорії наближених методів, яка для лінійних операторних та функціональних рівнянь детально описана у відомих монографіях Л.В. Канторовича і Г.А. Акілова та М.А. Красносельського, Г.М. Вайнікко, П.М. Забрейко і ін. Основу цієї теорії складають дві теореми про зв'язок між точним рівнянням і послідовністю відповідних наближених рівнянь -- так звані пряма теорема, що дозволяє на основі даних про точне рівняння встановити розв'язність “наближеного” рівняння і збіжність наближеного розв'язку до відповідного точного та обернена теорема, яка на основі даних про існування розв'язку наближеного рівняння (при фіксованому значенні параметра апроксимації) дозволяє робити висновок про розв'язність точного рівняння і близькість відповідних розв'язків. Для деяких класів нелінійних операторних та інтегральних рівнянь наведені елементи загальної теорії наближених методів знайшли своє відображення у працях М.Д. Бабича. У цих роботах за область єдиності ізольованих розв'язків розглядаються замкнені кулі , центри яких визначаються як розв'язки наближених рівнянь, а радіуси знаходяться із достатніх умов існування у кулі єдиного розв'язку та збіжності ітераційного методу. Питанням наближеного розв'язування НІР присвячені також роботи Л.В. Канторовича, Г.А. Акілова, М.А. Красносельського, Г.М. Вайнікко, П.М. Забрейко, Е.А. Волкова. Багато методів розв'язування нелінійних функціональних рівнянь, зокрема нелінійних інтегральних рівнянь, базуються на переході до апроксимаційних рівнянь більш простої структури, що можуть бути зведені до еквівалентних систем нелінійних скалярних та трансцендентних рівнянь (СНАТР), проблема глобального розв'язування яких є актуальною і складною науковою проблемою. Деякі методи глобального розв'язування таких систем розглядалися, зокрема, в роботах В.Ю. Семенова та Е.А. Волкова. Вагомі результати щодо глобального наближеного розв'язування СНАТР одержані в роботі М.Д. Бабича та Л.Б. Шевчук, де практично розроблений і реалізований алгоритм відокремлення в заданій області всіх ізольованих розв'язків системи нелінійних алгебраїчних і трансцендентних рівнянь.

Як відомо, наближене розв'язування нелінійних рівнянь супроводжується появою різного роду похибок, які необхідно враховувати при побудові наближених розв'язків. Крім цього точність наближеного розв'язування рівнянь тісно пов'язана з обчислювальною складністю процесу розв'язування. Ці питання досліджувалися у роботах К.В Ємельянова та А.М. Ільїна, В.В. Іванова, В.К. Задіраки, М.Д. Бабича, С.В. Переверзєва та ін.

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

Зв'язок роботи з науковими програмами, планами, темами. Дисертація виконана в рамках держбюджетної теми Інституту кібернетики імені В.М. Глушкова НАН України. Тема ВК 140.03 номер державної реєстрації 0103U003259 “Розробити ефективні за складністю алгоритми наближеного розв'язування задач цифрової обробки сигналів та зображень, задачі Коші для системи звичайних диференціальних рівнянь, деяких класів нелінійних рівнянь, глобальної мінімізації функцій та захисту інформації”, виконаної у 2004-2007 роках.

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

Реалізація сформульованої мети передбачає дослідження і розв'язання наступних задач:

· побудову для вихідного (точного) рівняння послідовності апроксимаційних рівнянь та дослідження взаємозв'язку між ними щодо існування і відповідності їх розв'язків та збіжності методу переходу до апроксимаційних рівнянь;

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

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

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

· знаходження і дослідження оцінки повної похибки та оцінки обчислювальної складності наближеного розв'язування НІР зі степеневою нелінійністю комбінованим методом відокремлення розв'язків і їх ітераційного уточнення;

· проведення порівняльного аналізу ітераційних методів найскорішого спуску (МНС), мінімальних нев'язок (ММН) та мінімальних похибок (ММП) за характеристиками швидкості збіжності та області застосування.

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

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

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

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

· елементи загальної теорії наближених методів реалізовані вперше на класі нелінійних інтегральних рівнянь зі степеневою нелінійністю та багатьма ізольованими розв'язками;

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

· застосовано метод вироджених ядер щодо зведення НІР до відповідної системи нелінійних скалярних рівнянь;

· для відокремлення і знаходження всіх ізольованих розв'язків СНСР застосовано і модифіковано алгоритм, а для їх уточнення використано ітераційні методи МНС, ММН та ММП;

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

· в загальному випадку (для будь-якого наближеного розв'язку) одержані оцінки всіх видів похибок (неусувної, методу, заокруглення і повної);

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

· проведено обчислювальний експеримент щодо відокремлення усіх ізольованих розв'язків нормальної системи нелінійних скалярних рівнянь третього порядку та перевірки умов застосування ітераційних методів МНС, ММН та ММП;

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

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

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

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

Особистий внесок здобувача. Викладені в дисертації матеріали повністю опубліковані у фахових наукових виданнях. Основні результати отримані автором особисто. У роботі [2] автором сформульовані і доведені дві теореми про співвідношення між ітераційними методами МНС, ММН та ММП розв'язання рівнянь за величинами їх нев'язок, параметрів швидкості збіжності та областей збіжності. У роботі [4] для класу нелінійних інтегральних рівнянь зі степеневою нелінійністю автором сформульовані і доведені три допоміжні леми 1, 2, 3 та теореми 2, 3 про зв'язок точного рівняння і послідовність відповідних наближених рівнянь. Знайдені оцінки констант, які є складовими функцій радіусів куль єдності розв'язків, що характеризують достатні умови теорем існування, із яких визначаються інтервали змін радіусів куль єдності розв'язків. У роботі [5] наведено оцінки елементів складових похибок неусувної, методу і заокруглення та загальну оцінку повної похибки. Тут наведена і оцінка обчислювальної складності комбінованого алгоритму глобального наближеного розв'язування наведеного класу нелінійних інтегральних рівнянь. У роботах [1]-[3] реалізовано теоретичні положення щодо відокремлення ізольованих розв'язків на прикладах нормальної систем нелінійних скалярних рівнянь третього порядку та НІР з кубічною нелінійністю. Наведені результати досліджень були предметом виступу автора на наукових форумах [6]-[11].

Апробація результатів дисертації. Результати, які викладені в дисертаційній роботі доповідалися і обговорювалися на таких наукових конференціях, школах-семінарах, симпозіумах: Міжнародній школі-семінарі “Теорія прийняття рішень” (Ужгород, 2002); ІІ-й міжнародній школі-семінарі “Теорія прийняття рішень” (Ужгород, 2004); Міжнародній конференції “Питання оптимізації обчислень (ПОО-ХХХІІ)”, присвяченій пам'яті академіка В.С. Михалевича (Кацивелі, 2005); ІІІ-й міжнародній школі-семінарі “Теорія прийняття рішень” (Ужгород, 2006); Міжнародному симпозіумі “Питання оптимізації обчислень (ПОО-ХХХІІІ)”, присвяченому 50-річчю створення Інституту кібернетики ім. В.М. Глушкова НАН України (Кацивелі, 2007); ІV міжнародній школі-семінарі “Теорія прийняття рішень” (Ужгород, 2008); координаційній нараді “Питання оптимізації обчислень (ПОО-ХХХІV)” (Ужгород, 2008).

Публікації. Основні результати дисертаційної роботи опубліковані в 11-ти друкованих працях загальним обсягом 64 стор., із них п'ять надруковані у виданнях, які входять у перелік видань затверджених ВАК України та 6 наукових праць у збірниках матеріалів наукових форумів (конференцій, симпозіумів, шкіл-семінарів).

Структура та об'єм роботи. Дисертаційна робота складається із вступу, чотирьох розділів, висновків, списку використаних джерел із 65 найменувань та додатку (15 стор.), 9 таблиць по тексту. Повний обсяг дисертації становить 164 стор., з них 124 стор. основного тексту.

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

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

У першому розділі зроблено огляд літератури за темою дисертації.

У другому розділі розглянуті питання глобального наближеного розв'язування нелінійних операторних рівнянь, точності і обчислювальної складності розв'язування таких рівнянь, проведено порівняльний аналіз ітераційних методів МНС, ММН та ММП. Зокрема, у підрозділі 2.1 наведені та розв'язані декілька практичних задач, для математичного опису яких використовуються нелінійні функціональні рівняння. У підрозділі 2.2. розглянуто апроксимаційно-ітераційний метод розв'язування нелінійних операторних рівнянь в гільбертовому просторі , описаний в роботі М.Д. Бабича, який в дисертаційній роботі реалізовано на класі нелінійних інтегральних рівнянь зі степеневою нелінійністю та багатьма розв'язками.

Отже, нехай задане нелінійне операторне рівняння

, (1)

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

,

кожна з яких містить єдиний розв'язок рівняння (1) (елементи називаються центрами, а множина дійсних чисел -- радіусами цих куль). Для знаходження центрів , куль будується послідовність нелінійних рівнянь більш простої структури,

, , (2)

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

, , (3)

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

Теорема 2.6 Нехай у кулі , де один з елементів , а відповідне йому значення , виконуються умови

, , (4)

або , (5)

де , , , -- константи, що забезпечують виконання умов

(6)

(7)

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

. (8) При

, (9)

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

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

У таблиці 1 наведені величини , , , , , що характеризують ітераційні методи МНС, ММН та ММП, (через , , , позначені констант умов (4), (5)).

Таблиця 1

Метод
МНС
ММН
ММП

У теоретичному плані правомірність переходу від рівняння (1) до розв'язання рівняння (2) забезпечує теорема про розв'язність (2) (при довільному або достатньо великому ) за даними існування розв'язку (1) і збіжність методу переходу до рівнянь (2) та обернена теорема про розв'язність рівняння (1) за даними існування (при допустимому фіксованому ) розв'язку (2). Вказані теореми дають теоретичне обґрунтування та практичний апарат щодо відокремлення розв'язків (1) і обидві базуються на теоремі 2.6 Аналогічні їм теореми сформульовані в даній роботі для НІР зі степеневою нелінійністю. Отже, розв'язування рівняння (1) зводиться до побудови та наступного розв'язання послідовності апроксимаційних рівнянь (2) при певному допустимому значенні параметра апроксимації , доведенні відповідних теорем та проведенні апостеріорного аналізу отриманих розв'язків.

Часто задача розв'язування рівняння (1), яке, зокрема може характеризувати НІР, зводиться до розв'язування системи нелінійних скалярних рівнянь, для відокремлення і знаходження всіх ізольованих розв'язків якої можна застосувати алгоритм (у підрозділі 2.3 наведені основи даного алгоритму), а для їх уточнення -- ітераційні методи найскорішого спуску, мінімальних нев'язок, та мінімальних похибок.

У підрозділі 2.4 зроблено порівняльний аналіз ітераційних методів МНС, ММН та ММП.

Нехай задана система нелінійних скалярних рівнянь вигляду

, (10)

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

,

кожна з яких містить єдиний розв'язок рівняння (10), тобто справедлива теорема 2.6 існування єдиного розв'язку рівняння (10) та збіжності відповідного ітераційного методу (3), побудованого для оператора . Тоді в залежності від констант умов (4), (5), які для рівняння (10) позначені через , , , та співвідношень між ними справедливі теорема 2.7, яка характеризує можливість реалізації ітераційних методів МНС, ММН та ММП уточнення розв'язків СНСР і визначає область їх застосування та теорема 2.8, що визначає співвідношення між собою параметрів, які характеризують швидкості збіжності ММН та ММП.

Теорема 2.7 Нехай для методів найскорішого спуску, мінімальних нев'язок та мінімальних похибок величини , , та задовольняють наступним умовам

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

,

.

Теорема 2.8. Нехай виконана умова . Тоді, якщо , де

,

справедлива нерівність , а при умові має місце нерівність .

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

У розділі 3 реалізовані елементи загальної теорії наближених методів на класі нелінійних інтегральних рівнянь зі степеневою нелінійністю та багатьма розв'язками; одержані оцінки повної похибки і обчислювальної складності наближеного розв'язування вказаних рівнянь. У підрозділі 3.1 зроблена постановка задачі наближеного розв'язування НІР зі степеневою нелінійністю та багатьма розв'язками, застосовано метод вироджених ядер побудови для вихідного НІР послідовності апроксимаційних рівнянь.

Отже, нехай задано НІР вигляду

, , (11)

де -- шукана функція, , -- задані неперервні функції за всіма своїми аргументами в замкнутій області

.

В припущенні, що рівняння (11) має скінчену множину ізольованих точних розв'язків

,

розв'язування нелінійний функціональний рівняння

ставиться задача: знайти неперервні наближені розв'язки для всіх за допомогою побудови і наступного розв'язання НІР більш простої структури, які апроксимують рівняння (11). Послідовність апроксимаційних рівнянь для (11) побудована використовуючи метод вироджених ядер і має вигляд

, , (12)

, , (13)

, -- системи лінійно-незалежних функцій. Розв'язок рівняння (11) шукається у вигляді

, (14)

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

. (15)

Відокремлення розв'язків здійснюється шляхом побудови замкнених куль

, ,

кожна з яких містить один розв'язок. За елементи служать розв'язки рівняння (12) при допустимому фіксованому , які мають вигляд (14), а радіуси визначаються із достатніх умов локальної теореми існування розв'язку рівняння (11) та збіжності методу мінімальних нев'язок.

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

, (16)

, (17)

, (18)

, (19)

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

(20)

(21)

(22)

В лемах 3.1, 3.2, 3.3 відображена близькість операторів , ; , ; , та наведені оцінки норм операторів (16)-(19).

Лема 3.1 Нехай оператори і задані відповідно формулами (11), (12) та виконуються умови

(23)

(24)

де константи , а , при .

Тоді умова близькості операторів і на елементи виконується з функціоналом

(25)

для всякого нерівності (21) та (22) виконуються відповідно з функціоналами

(26)

(27)

та справедлива нерівність

(28)

(29)

а константи , визначаються із нерівності

.

Лема 3.2 Для оператора , визначеного формулою (16), справедливі оцінки

, , (30)

(31)

. (32)

Справедлива теорема (аналогічна доведеній в роботі М.Д. Бабича для рівняння (1)) про існування розв'язку рівняння (12) (при довільному або достатньо великому ) та збіжність методу переходу до рівнянь (12).

Теорема 3.1 Нехай -- один з розв'язків рівняння (11), оператори і задані формулами (11), (12) є двічі неперервно диференційовні за Фреше в кулі , їх похідні , , , мають вигляд (16)-(19); в кулі виконуються умови апроксимації операторів , , операторами , , з функціоналами , , , які відповідно мають вигляд (25)-(27); для оператора в кулі виконуються умови (28), (29), а для мають місце оцінки (30)-(32). Крім цього нехай виконуються умови (23)-(24). Тоді справедливі наступні твердження.

1. Існує така область де -- корінь рівняння що для всякого виконується нерівність

(33)

2. Для операторів , , , в кулі справедливі оцінки

; (34)

; (35)

(36)

. (37)

3. Для довільного , знайдеться таке , що при в нерівності (36) >0 та виконуються умови

(38)

(39)

4. При кожному із вказаних рівняння (12), має в кулі єдиний розв'язок , який відповідає розв'язку , до якого, починаючи з , збігається послідовність , побудована згідно методу мінімальних нев'язок для рівняння (12), причому швидкість збіжності характеризується нерівністю

(40)

5. Довільна послідовність розв'язків при збігається за нормою до розв'язку і справедлива оцінка

(41)

Позначимо , -- множину послідовностей розв'язків рівняння (12), що мають вигляд (14).

Лема 3.3. Для всіх , де -- один з розв'язків рівняння (12) виконується нерівність

(42)

з функціоналом

(43)

а для оператора виконуються умови

, , (44)

(45)

. (46)

Теорема 3.2. Нехай оператори , задані формулами (11), (12) є двічі неперервно диференційовні за Фреше в кулі , де -- один з розв'язків рівняння (12), який має вигляд (14). Похідні , мають вигляд (16)-(19). Крім того, нехай виконуються нерівності (42), (44) з функцiоналами (43), (45), (46) та умови (23), (24). Тоді справедливі наступні твердження.

1. В кулі при довільному виконуються нерівності (20)-(22), що характеризують близькість операторів ; ; з функціоналами , які відповідно мають вигляд (25)-(27).

2. Для операторiв в кулi мають місце оцінки

(47)

(48)

, (49)

, (50)

де , , забезпечують виконання нерівностей (42), (44) і мають відповідно вигляд (43), (45), (46).

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

(51)

(52)

4. Рiвняння (11) має в кулi , де єдиний розв'язок , який відповідає даному , до якого (починаючи з ), збігається послідовність , побудована згідно методу мінімальних нев'язок для оператора (11), причому має місце оцінка

(53)

5. Апостерiорна оцінка похибки, яка характеризує близькість відповідних розв'язків та рівнянь (11) і (12), визначається нерівністю

. (54)

У підрозділі 3.2 отримана оцінка повної похибки при наближеному розв'язуванні НІР (11) комбінованим методом відокремлення розв'язків та їх ітераційного уточнення методом мінімальних нев'язок (3) (при відповідному виборі і ). Оцінка повної похибки знайдена у вигляді

, (55)

де , -- точні розв'язки відповідно рівнянь (11), (12); -- наближений розв'язок рівняння (12), отриманий на -тій ітерації методу мінімальних нев'язок, побудованого для оператора (12) при умові, що всі обчислення виконуються точно; -- заокруглене значення до розрядів у мантисі числа. Доданки в правій частині нерівності (55) визначають відповідно неусувну похибку, похибку методу та похибку заокруглення. В розгорнутому вигляді (55) має вигляд

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

У підрозділі 3.3 зроблена оцінка обчислювальної складності наближеного розв'язування НІР (11) комбінованим методом відокремлення розв'язків та їх ітераційного уточнення ММН. Всі оцінки стосуються СНСР, до яких зводиться наближене розв'язування НІР (12), розв'язок якого шукають у вигляді (14). Загальна обчислювальна складність характеризується формулою

(56)

де -- обчислювальна складність алгоритма; -- число точок, які відкидаються на -й сітці, -- складність обчислення нев'язки; -- складність реалізації достатніх умов теореми існування і збіжності на всіх l розв'язках; -- обчислювальна складність ітераційного уточнення всіх l розв'язків ( -- складність виконання однієї ітерації, -- номер ітерації на якій досягається задана точність -го розв'язку НІР за нев'язкою).

У четвертому розділі на основі теоретичних положень, викладених в другому та третьому розділах роботи проведений обчислювальний експеримент щодо наближеного розв'язування нормальної СНАР третього порядку та НІР з кубічною нелінійністю. Зокрема, у підрозділі 4.1 знайдені всі ізольовані розв'язки СНСР використовуючи модифікований -алгоритм. Перевірені достатні умови існування і збіжності ітераційних методів МНС, ММН і ММП та твердження теорем 2.7, 2.8, знайдена апостеріорна оцінка похибки. В підрозділі 4.2 практично реалізовано процес відокремлення ізольованих розв'язків НІР вигляду

(57)

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

(58)

Розв'язок (58) шукається у вигляді полінома

.

Доведені пряма та обернена теореми існування, що теоретично обґрунтовують можливість переходу до розв'язання рівнянь (58). При значенні параметра апроксимації отримана еквівалентна (58) СНСР

(59)

В результаті наближеного розв'язання системи (59) -алгоритмом одержані три розв'язки, яким відповідають три аналітичні наближені розв'язки , рівняння (58) (при ) та отримані відрізки зміни радіусів куль єдиності кожного розв'язку , рівняння (57). Розв'язки , та інтервали зміни значень , що характеризують апостеріорні оцінки близькості та , тобто , наведені в таблиці 2.

Таблиця 2

Знайдена оцінка повної похибки наближеного розв'язування НІР комбінованим методом відокремлення розв'язків та їх ітераційного уточнення методом мінімальних нев'язок.

У висновках сформульовані основні результати роботи.

У додатку наведений вихідний текст комп'ютерної програми, написаної на мові Delphi, за допомогою якої здійснюється відокремлення розв'язків СНАТР модифікованим -алгоритмом та їх уточнення ітераційними методами МНС, ММН та ММП. Модифікація алгоритму полягає у тому, що всі величини, що входять в умови (4)-(7) обчислюються на кожному кроці у всіх невідбракованих точках -алгоритму. Це дозволяє (у випадку виконання умов (6), (7)) припинити процес відокремлення розв'язків та застосувати ітераційні методи МНС, ММН та ММП.

Висновки

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

Найбільш важливими науковими результатами, отриманими в дисертаційній роботі є такі:

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

· до розв'язування НІР зі степеневою нелінійністю застосована загальна теорія наближених методів;

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

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

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

· для відокремлення всіх ізольованих розв'язків СНСР, застосовано та модифіковано -алгоритм;

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

Всі етапи наближеного розв'язування даного класу нелінійних інтегральних рівнянь та знаходження оцінки повної похибки наближених розв'язків проілюстровано на прикладі НІР з кубічною нелінійністю.

Практично реалізовано процес відокремлення всіх ізольованих розв'язків нормальної СНСР третього порядку, перевірені достатні умови існування і збіжності ітераційних методів МНС, ММН і ММП та твердження теорем 2.7, 2.8, знайдена апостеріорна оцінка похибки.

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

1. Бабич М.Д. Про чисельне розв'язування нелiнiйних iнтегральних рiвнянь / М.Д. Бабич, Л.М. Буря // Науковий вiсник Ужгородського унiверситету. -- Сер. Математика i інформатика. -- 2002. -- вип.7. -- С. 16-20.

2. Бабич М.Д. Об итерационном уточнении решений системы нелинейных скалярных уравнений / М.Д. Бабич, Л.М. Буря // Компьютерная математика. -- 2004. -- вип.2. - С. 36-45.

3. Буря Л.М. Оцiнка точностi наближеного розв'язування одного класу нелiнiйних iнтегральних рiвнянь / Л.М. Буря // Науковий вісник Ужгородського університету. -- Сер. Математика i інформатика. -- 2006. -- вип.12-13. -- С. 39-54.

4. Мамай Л.М. Про наближене розв'язування нелiнiйних інтегральних рівнянь із степеневою нелінійністю / Л.М. Мамай // Науковий вісник Ужгородського університету. -- Сер. Математика i інформатика. -- 2008. -- вип.17. -- С. 116-131.

5. Бабич М.Д. О точности и вычислительной сложности приближенного решения нелинейных функциональных уравнений / М.Д. Бабич, Л.М. Буря // Управляющие системы и машины. --2008. -- №2. -- С. 13-21.

6. Буря Л.М. Про складність обчислень при розв'язуванні систем нелінійних скалярних рівнянь / Буря Л.М. // Теорія прийняття рішень: міжнародна школа-семінар, 7-12 жовтня 2002р.: праці школи-семінару. -- Ужгород, 2002. -- С. 14.

7. Буря Л.М. Про чисельне розв'язування систем нелінійних скалярних рівнянь / Буря Л.М. // Теорія прийняття рішень: II-а міжнародна школа-семінар, 27 вересня-2 жовтня 2004р.: праці школи-семінару. -- Ужгород, 2004. -- С. 13.

8. Бабич М.Д. Про один клас математичних моделей та їх обчислення / М.Д. Бабич, Л.М. Буря, О.М. Гецко // Питання оптимізації обчислень (ПОО-ХХХІІ): міжнар. конференція, присвячена пам'яті академіка В.С. Михалевича., 19-23 вересня 2005р.: праці міжнар. конференції. -- Київ, 2005. -- С. 30-31.

9. Буря Л.М. Про деякi оцiнки апроксимацiї / Буря Л.М. // Теорія прийняття рішень: III-а міжнародна школа-семінар, 2-7 жовтня 2006р.: праці школи-семінару. -- Ужгород, 2006. -- С. 14.

10. Буря Л.М. Про наближене розв'язування нелiнiйних iнтегральних рiвнянь та оцiнку повної похибки / Л.М. Буря // Питання оптимізації обчислень (ПОО-ХХХІІІ): міжнар. симпозiум, присвячений 50-рiччю створення Iнституту кiбернетики імені В.М. Глушкова НАН України., 23-28 вересня 2007р.: праці симпозіуму. -- Київ, 2007. -- С. 50-51.

11. Мамай (Буря) Л.М. Про точнiсть наближеного розв'язування нелiнiйних функцiональних рiвнянь / Мамай (Буря) Л.М. // Теорія прийняття рішень: IV міжнародна школа-семінар, 29 вересня - 4 жовтня 2008р.: праці школи-семінару. -- Ужгород, 2008. -- С. 117.

Анотація

Мамай Л.М. Точність та обчислювальна складність наближеного розв'язування нелінійних функціональних рівнянь. -- Рукопис.

Дисертація на здобуття наукового ступеня кандидата фізико-математичних наук за спеціальністю 01.05.02 -- математичне моделювання та обчислювальні методи. -- Інститут кібернетики імені В.М. Глушкова НАН України, Київ, 2009.

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

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

На основі отриманих теоретичних положень проведено чисельний експеримент щодо наближеного розв'язування нормальної СНАР третього порядку та нелінійного інтегрального рівняння з кубічною нелінійністю.

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

Abstract

Mamay L.M. The accuracy and computational complexity of the approximate solving of nonlinear functional equations. -- Manuscript.

Thesis for a candidate's degree in physical and mathematical sciences by speciality 01.05.02 -- mathematical modeling and numerical methods. -- V.M. Glushkov Institute of Cybernetics of National Academy of Sciences of Ukraine, Kyiv, 2009.

The dissertation is devoted to questions of the global approximate solving of nonlinear functional equations, specifically simultaneous nonlinear scalar equations (SNSE) and nonlinear integral equations with power nonlinearity. The evaluation of the accuracy and computing complexity of process of solving of such equations are studied.

In this paper was cited some nonlinear functional equations which are mathematical models of real physical processes. Elements of general theory of the approximate methods are realized for a class of nonlinear integral equations (NIE) with power nonlinearity for the first time. The evaluation of the accuracy and computational complexity of the combined method of separation of solutions of the NIE with power nonlinearity by algorithm and iterative refinement by minimal misclosures method are studied.

Characteristics of iteration methods of the minimal errors, minimal misclosures, fastest descent of separation of solutions of SNSE are investigated, also are specified domains of their efficient application. The theoretical research results are illustrated by specific examples.

Keywords: mathematical modeling, nonlinear functional equations, systems of the nonlinear algebraic and transcendental equations, nonlinear integral equations, isolated solutions, iterative methods, an error, accuracy, computing complexity.

Аннотация

Мамай Л.М. Точность и вычислительная сложность приближенного решения нелинейных функциональных уравнений. -- Рукопись.

Диссертация на соискание ученой степени кандидата физико-математических наук по специальности 01.05.02 -- математическое моделирование и вычислительные методы. -- Институт кибернетики имени В.М. Глушкова НАН Украины, Киев, 2009.

Диссертационная работа посвящена вопросам глобального приближенного решения нелинейных функциональных уравнений (НФУ), в частности нелинейных интегральных уравнений со степенной нелинейностью и систем нелинейных скалярных уравнений (СНСУ), точности и вычислительной сложности процесса решения таких уравнений, а также применению НФУ в качестве математических моделей реальных физических процессов.

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

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

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

Для нахождения всех изолированных решений СНСУ применено и модифицировано алгоритм, а для их уточнения -- итерационные методы минимальных ошибок (ММО), минимальных невязок (ММН) и наискорейшего спуска (МНС).

Произведен сравнительный анализ итерационных методов ММО, ММН, МНС уточнения решений систем нелинейных скалярных уравнений по скорости и области сходимости, а также определения для них областей наиболее эффективного применения.

Для данного класса НИУ в общем случае (для каждого приближенного решения) получены оценки всех видов погрешности (неустранимой, метода, округления и полной).

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

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

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

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

...