Київський національний університет

імені Тараса Шевченка

Б а р т і ш М и х а й л о Я р о с л а в о в и ч

У Д К 519.6

МЕТОДИ ТИПУ НЬЮТОНА ДЛЯ РОЗВ’ЯЗУВАННЯ НЕЛІНІЙНИХ

ОПЕРАТОРНИХ РІВНЯНЬ І ЗАДАЧ НА ЕКСТРЕМУМ

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

А В Т О Р Е Ф Е Р А Т

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

доктора фізико-математичних наук

Київ - 2003

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

Робота виконана на кафедрі теорії оптимальних процесів

факультету прикладної математики та інформатики

Львівського національного університету імені Івана Франка

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

професор Лучка Антон Юрійович

Інститут математики НАН України,

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

доктор фізико-математичних наук,

професор Ляшенко Ігор Миколайович

Київський національний університет

імені Тараса Шевченка, завідувач кафедри;

доктор фізико-математичних наук,

професор Слоньовський Роман Володимирович

Національний університет

“Львівська політехніка”.

Провідна організація – Інститут кібернетики імені В. М. Глушкова

НАН України м. Київ, відділ оптимізації

керованих процесів.

Захист відбудеться “27“ листопада 2003 р. о 14.00 на засіданні

спеціалізованої вченої ради Д 26. 001. 09 Київського національного

університету імені Тараса Шевченка за адресою

03127, м. Київ, проспект Глушкова, 2, корп.6, факультет кібернетики,

ауд 40. (Тел. 259-04-24, факс 259-70-44. e-mail: .

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

Київського національного університету імені Тараса Шевченка

за адресою:

01033, м. Київ, вул. Володимирська, 58.

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

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

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальність теми. Успіхи в розвитку обчислювальної техніки в 50-60 роках ХХ століття наклали свій відбиток на прикладну математику, предметом вивчення якої є методи одержання розв’язку різного роду задач у вигляді числового (точного, або наближеного) результату. Важливу роль у дослідженні проблеми відводиться математичному моделюванню, що полягає в побудові певних рівнянь досліджуваних явищ чи процесів з наступним визначенням шуканих величин. Перший крок загального процесу отримання розв’язку проблеми, яку досліджуємо полягає в побудові математичної моделі. На другому кроці необхідно вибрати метод числового розв’язування задачі, що полягає в перетворенні математичного представлення задачі до вигляду зручного для використання обчислювальної техніки, спрощення моделі, обгрунтування методу з тією або іншою ступінню повноти (дослідження стійкості обчислень, можливості отримання розв’язку з необхідною точністю, оцінка похибки і т.д.)

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

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

Поява суперкомп’ютерів дає нові можливості для моделювання крупномаштабних задач і проведення обчислювального експерименту у фундаментальних і прикладних дослідженнях. Це дало можливість широкого використання нелінійних моделей для опису того або іншого реального процесу. Проблеми побудови нелінійних моделей і їхнього математичного дослідження на сучасному етапі стали надзвичайно актуальними в економіці, техніці, екології, механіці, при розв’язуванні задач керування тощо. Тут необхідно відзначити роботи М.М. Мойсеєва, О.М. Гудзя, В. С. Михалевича, О.О. Самарського, Л.В. Канторовича, В.В. Скопецького, Я.М. Григоренка, М.В. Лурьє, Я.С.Підстригача, І.М. Ляшенка, В.Т. Грінченка і інших.

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

У даній праці основна увага зосереджена на другому кроці дослідження реального процесу, а саме, на розробці і дослідженні ефективних методів розв’язування нелінійних операторних рівнянь і задач на екстремум. Найбільш поширеними методами розв’язування нелінійних задач є ітераційні методи. Ідеї функціонального аналізу не тільки дозволили суттєво змінити погляд на чисельні методи, а привели до розробки принципово нових обчислювальних схем і дали можливість розглядати ітераційні методи з досить загальної точки зору. В загальній теорії наближених методів відомі багаточисельні фундаментальні результати: це класичні праці Л.В.Канторовича, дослідження проекційних методів, які беруть початок з робіт М. М. Боголюбова, М. М. Келдиша, М. В. Крилова, Г. В. Петрова, Ю.М. Митропольського, С. Г. Міхліна, Ю.Д. Соколова, дослідження А.М.Тихонова по розв’язуванню некоректних задач та інші.

Одними із широко використовуваних ітераційних методів розв’язування нелінійних операторних рівнянь є методи типу Ньютона. Дослідженню і застосуванню методу Ньютона, його різницевих аналогів, модифікацій, методів типу Ньютона присвячена велика кількість робіт, бібліографія нараховує тисячі назв. Відзначимо лише деяких авторів, це праці Г. М. Вайнікко, Л. Коллатца, О. М. Островського, В. Є. Шаманського, Дж. Трауба, М.А. Красносельського, П. П. Забрейка, Р. Беллмана, Р. Калаби, В.А. Курчатова, М. К. Гавуріна, Ф.П. Васильєва і його учнів, С. Ю. Ульма і його учнів, В. Рейнболдта, Д. Ортеги, Р. Шнабеля, М. Альтмана, В. М. Вержбицького, Й. Шредера, Й. Шмідта, Дж. Денніса, О.С. Сергеєва, Г. Клейнміхеля, А. Ю. Лучки, М.С. Курпеля, Т.І. Коган, Б.А. Бельтюкова і його учнів, В. Птака, Б.М. Пшеничного, Ю.М. Даніліна, В.М.Чернишенка і його учнів, Р. А. Шафієва, Р. Тапіа, В. Петришина, І.П. Мисовських, В. Вернера, І. І. Жечева та інші. Перелік праць в цьому напрямку досить великий.

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

Зв’язок роботи з науковими програмами. Робота виконана в рамках наукової тематики кафедри теорії оптимальних процесів Львівського національного університету імені Івана Франка, а саме:

1) тема “Числові методи розв’язування нелінійних функціональних рівнянь і задач на екстремум” (виконувалась згідно програми комплексних досліджень ВНЗ Мінвузу УРСР по проблемі “Моделювання і оптимізація складних процесів керування”, ВНТІЦ інв. № 02860031048.

2) тема По 615Б “Методи розв’язування екстремальних задач і їх застосування”, реєстраційний номер 0193V041432.

3) тема По 783Б “Розробка і дослідження ітераційних методів розв’язування нелінійних функціональних рівнянь і задач на екстремум”, реєстраційний номер 0196V017368.

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

Сформульована мета обумовлює наступні взаємопов’язані задачі досліджень:

- побудова нових чисельних методів розв’язування нелінійних операторних рівнянь і задач на екстремум;

- побудова параметричної модифікації методів і розробка рекомендацій по вибору параметра при розв’язуванні конкретної задачі;

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

- розробка рекомендацій по застосуванню нових методів до розв’язування задач практики;

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

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

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

- розроблено цілісну теорію побудови і дослідження ітераційних методів типу Ньютона та типу Рунге і їх різницевих аналогів для розв’язування нелінійних операторних рівнянь,

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

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

-побудовано прискорений метод Ньютона, який є новим диференціальним аналогом методу Стеффенсена, показано його переваги стосовно класичного методу Ньютона при розв’язуванні окремих класів задач,

-використано ідею методу Гаусса-Ньютона і запропоновано нову модифікацію методу з порядком збіжності 1+* для розв’язування задач про найменші квадрати,

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

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

-дано рекомендації по застосуванню методів типу Гаусса-Ньютона для розв’язування систем нелінійних рівнянь і нерівностей,

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

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

Методичні та теоретичні результати дисертаційної роботи були застосовані в нормативному курсі з методів оптимізації, а також в спеціальних курсах з чисельних методів, які читаються студентам факультету прикладної математики та інформатики ЛНУ ім. Івана Франка.

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

Особистий внесок здобувача. В дисертаційній роботі містяться основні результати, які отримані самостійно і опубліковані в 13 наукових працях,

та в 30 роботах у співавторстві. У спільних роботах [13-33, 37, 38, 41] з

аспірантами та співшукачами (Щербина Ю. М., Сеньо П. С., Роман Л. Л., Шахно С.М., Чипурко А.І.) автору належить постановка задачі, побудова та математичне обгрунтування основних алгоритмів, аналіз результатів. В роботах [8-12, 42, 43] Огірку І.В., Роман Л.Л., Фарату В.М., Чипурку А.І, Ломіковському В.О. належить проведення чисельного експерименту та аналіз результатів, студентам Гут Н.П., Мельник А.В. та науковому співробітнику Николайчук Л.В. - написання і налагодження програм для ЕОМ.

Публікації. Результати дисертації опубліковані у 45 статтях у наукових журналах і збірниках наукових праць та більш ніж у 30 тезах конференцій; з них 33 статті опубліковані у фахових виданнях ВАК України, серед яких 7 одноосібних праць.

Структура та об’єм роботи. Дисертаційна робота складається із вступу, основної частини з шести розділів, загальних висновків та списку використаних джерел з 231 найменування. Загальний обсяг дисертації становить 284 с., основний зміст викладено на 260 сторінках.

ОСНОВНИЙ ЗМІСТ РОБОТИ

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

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

У другому розділі розглянуто загальну методику побудови методів типу Ньютона для розв’язування нелінійного операторного рівняння

* (2.1)

де Р - оператор, що переводить простір типу Банаха Х у простір типу Банаха У. В загальному такі методи можна записати у вигляді

* n=0,1,2,…; *. (2.2)

При цьому справедлива

Теорема 2. 1. Нехай:

для початкового наближення *X існує оператор

*

причому

*

2) початкове наближення * вибране так, що виконується умова

*

3) для *

виконується оцінка

*

4) оператор * на кожному кроці ітераційного процесу, задовольняє умови

*

*

де

*, * *;

5) *

*

Тоді рівняння (2.1) має розв'язок *, який можна знайти за формулою (2.2), при цьому *, і виконується оцінка:

*. (2.3)

Використовуючи дану теорему, легко отримати оцінки для методів Ньютона, дотичних гіпербол, Чебишева, запропонованого Т.І. Коган і інших методів, які запропоновані в роботі і досліджуються нижче. Також в даному розділі для розв’язування рівнянь (2.1) запропоновано методи типу Рунге. При побудові таких методів використано ідею методу Рунге-Кутта розв’язування задачі Коші для звичайних диференціальних рівнянь

У третьому розділі розглянуто збурені аналоги відповідних методів. Нехай для розв'язування рівняння (2.1) маємо ітераційний процес (2.2), який приймемо за основу. Разом з (2.2) розглянемо новий ітераційний процес

Теорема 3.1. Нехай:

виконуються умови 1)-4) теореми 2.1, де

*

*

має місце оцінка (3.2);

*

4) *

5) *,

де *

Тоді послідовність *, визначена за формулою (3.1), збігається до границі *, що є розв'язком рівняння (2.1), при цьому справедлива оцінка

*, (3.3)

а порядок збіжності алгоритму (4.1) не менше *.

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

Використовуючи результати теореми 3.1, можна побудувати деякі ітераційні методи розв'язування рівняння (2.1) при умові, що за основні методи будемо вибирати методи типу Ньютона з розділу 2, оператор Р необхідну кількість раз диференційовний за Фреше.

Аналогічно можна показати, що методи, запропоновані і розглянуті в [2, 3, 34], коли послідовність * визначається відповідно за формулами

і їх різницеві аналоги є також збуреними аналогами методу дотичних

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

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

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

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

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

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

Метод (4.3) пізніше, як новий, був розглянутий в роботах П. Лаазонена, В. Вернера, С.С. Волокитіна.. Однак перше повідомлення про даний метод і більш повне дослідження методу і його різницевого аналогу зроблено в роботах [30-33, 35] раніше, ніж це зробив В. Вернер (1979-1984 роки). Трудомісткість однієї ітерації по (4.3) і інші характеристики методу (4.3) і методу Ньютона практично однакові, в той же час порядок збіжності запропонованого методу вищий (1 + *), що робить його привабливим для практиків.

Поряд з методом (4.3) можна розглядати його різницевий аналог

Треба відзначити, що точність обчислень Р(х*) в процесі реалізації алгоритму повинна бути на один порядок вищою, ніж точність обчислень Р(x*.

Крім цього, для розв’язування задачі (2.1) побудовано і досліджено рекурсивні ітераційні формули.

Теорема 4.1. Нехай *(x) і Ф(x) породжують ітераційні алгоритми порядку p і * відповідно, і оператор * можна представити у вигляді

*(x)=x-F(x)P(x)

крім того

Q(x)= Ф(x) - H(x) P(Ф(x)) , (4.8)

і справедлива оцінка

*

P(x) диференційовний в деякому околі *, причому

*

Тоді оператор Q(x) породжує ітераційну формулу порядку

q= min(p*, l+*.*

Використовуючи дану теорему, в роботі побудовано рекурсивні алгоритми з довільною глибиною рекурсії.

Як показали дослідження, представляють інтерес алгоритми:

-метод з глибиною рекурсії t на базі модифікації методу з [3]

-метод з глибиною рекурсії t на базі методів типу Рунге [16], а саме:

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

Отже, значення оптимального p можна обчислити уже апріорі .

Крім цього, розглянуто рекурсивний алгоритм на базі методу з порядком збіжності * і його різницевий аналог.

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

*=* (4.16) У випадку

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

Достатні умови збіжності послідовності {*}, визначеної за формулою (4.19), до розв'язку рівняння (4.16) отримано в праці [27]. При цьому показано, що при * порядок збіжності методу дорівнює * а в інших випадках не нижче 2.

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

* (5.1)

де *. Нехай * є розв’язком задачі (5.1), тобто *. У даному випадку задача (5.1) еквівалентна задачі:

* (5.2)

Для розв’язування задачі (5.2), коли *, розглянуто алгоритми, ітераційна формула яких має вигляд

Алгоритми (5.3) та (5.4) можна застосовувати для розв’язування систем нелінійних рівнянь та нерівностей.

Означення 5.1. * назвемо *- розв’язком системи (5.1), якщо виконується умова *, де *- достатньо мале число.

У цьому випадку справедливе твердження: якщо система рівнянь і нерівностей (5.5) має розв’язок, то існує таке достатньо велике число *, що система рівнянь (5.6) буде мати *- розв’язок. При цьому для довільного * достатньо покласти *. Використовуючи цю ідею, можна застосувати вище розглянуті методи до розв’язування задач типу (5.5).

У даному розділі розглянуто також задачу мінімізації

*.** (5.7)

Як показує практика, для розвязування задачі (5.7) можна застосувати методи, які розглянуті вище. При цьому переваги, які властиві даним методам при розв’язуванні операторних рівнянь, залишаються в силі і при розв’язуванні задачі (5.7) (*). Однак, враховуючи специфіку задачі (5.7), доцільно розглянути модифікації вищенаведених методів, або зробити певні уточнення при використанні відповідної модифікації.

На практиці, при розв’язуванні задачі (5.7) досить ефективно працюють

квазіньютонівські методи. Ідея даних методів полягає в заміні матриці *деяким наближеним значенням *. При побудові матриці *використовуємо лише інформацію про значення похідної для функції f(x) в одній точці. Для квазіньютонівських методів властива надлінійна збіжність, суттєво менша трудомісткість однієї ітерації в порівнянні з методом Ньютона. В роботі, використовуючи ідею побудови квазіньютонівських методів, різницевих аналогів методів з порядком збіжності * та прискореного методу Ньютона, для розв’язування задачі (5.7) запропоновано нові модифікації квазіньютонівських методів. Теоретичні аспекти методів (5.13), аналогічні таким же аспектам, як для класичних квазіньютонівських методів. Проведено значні чисельні експерименти для порівняння запропонованих модифікацій з класичними квазіньютонівськими методами.

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

Результати, отримані у шостому розділі носять характер числових експериментів. Для підтвердження достовірності теоретичних досліджень проведених в попередніх розділах, розв’язано низку тестових задач, а також конкретних задач механіки.

ОСНОВНІ РЕЗУЛЬТАТИ РОБОТИ ТА ВИСНОВКИ

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

Основними результатами дослідження є такі:

1. Запропоновано цілісну теорію побудови і дослідження ітераційних методів із надлінійним порядком збіжності (методи типу Ньютона та методи типу Рунге).

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

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

3. Досліджено новий ітераційний метод розв’язування нелінійних операторних рівнянь з порядком збіжності *. Показано його ефективність у сенсі кількості обчислень у порівнянні з методом Ньютона (у випадку одного рівняння індекси ефективності відповідно рівні *). Поряд з цим проведено достатньо повне дослідження різницевого аналогу запропонованого методу.

4. Запропоновано і досліджено нову модифікацію методу Ньютона, яка для відповідного класу задач ефективніша за метод Ньютона, практично побудовано новий диференціальний аналог методу Стеффенсена.

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

6. Запропоновано та досліджено загальну параметричну формулу модифікацій методу Гаусса-Ньютона. Сформульовано умови збіжності та отримано оцінки швидкості збіжності для модифікацій та їх різницевого аналогу у випадку задач з нульовою та ненульовою нев’язками. Досліджено вплив числового параметра на збіжність процесів. Важливим результатом є те, що при відповідному виборі параметрів ми отримуємо метод з порядком збіжності *, де * є порядок збіжності допоміжного оператора. Досліджено модифікацію методу Гаусса-Ньютона з порядком збіжності *.

7. Введено поняття *- розв’язку системи нелінійних рівнянь і дано рекомендації по застосуванню методів типу Гаусса-Ньютона для розв’язування систем нелінійних рівнянь та нерівностей.

8. Для розв’язування задач мінімізації запропоновано нові алгоритми, які досить успішно працюють у випадку мінімізації функцій типу яру.

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

10. Результати дисертації можуть знайти застосування при розв’язуванні практичних задач, математична модель яких описується

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

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

Бартіш М.Я. Ефективність методів типу Ньютона // Вісник ЛДУ. Сер. мех.-мат. випуск 7. -1972. - С. 41-47.

Бартиш М.Я Об одном классе итерационных методов со сходимостью третьего порядка //Cб. Вычисл. и прикл. матем.- К.: Вища школа -1972. -Т. 16. -С. 134-139.

Бартіш М.Я. Про деякі рекурсивні ітераційні методи розв’язування нелінійних операторних рівнянь // ДАН УРСР. -1978. - № 11. -С. 963-965.

Бартіш М.Я. Деякі методи розв’язування нелінійних операторних рівнянь // Вісник ЛДУ. Сер. Теорет. та прикл. матем. -1976. -Вип. 11. -C. 58-62.

Бартіш М.Я. Про один клас методів типу Ньютона розв’язування задач на екстремум // Вісник ЛДУ. Сер. мех.-мат. Задачі прикладної матем. і мех. -1988. -Вип. 24. -С. 3-5.

Бартіш М.Я. Про методи типу Ньютона розв’язування нелінійних функціональних рівнянь і задач на екстремум // Вісник ЛДУ. Cер. мех.-мат.. -1998. -Вип.50. -C. 3-6.

Бартіш М.Я. Про один метод розв’язування систем нелінійних алгебраїчних рівнянь з надлінійною швидкістю збіжності // Вісник ЛДУ. Сер. мех.-мат. – 1985. –Вип. 23. – С. 3-7.

Бартіш М.Я., Ломіковський В.О., Шахно С.М., Чипурко А. І Чисельне дослідження деяких алгоритмів розв’язування нелінійних рівнянь // Вісник ЛДУ. Сер. мех.-мат. – 1995. –Вип. 41. – С. 3-8.

Бартіш М.Я., Николайчук О.В., Чипурко А.І. Про деякі різницеві модифікації методу Гаусса-Ньютона для нелінійної задачі найменших квадратів з малою нормою нев’язки // Вісник ЛДУ. Cер. мех.-мат. -1999. -Вип. 52. -C.3-8.

Бартиш М.Я., Огирко И.В., Роман Л.Л. Решение методом типа Ньютона

-Канторовича нелинейной задачи термоупругости для гибкой оболочки с температурной зависимостью характеристик материала //Матем. методы и физ.-мех. поля. Львов: -1983. -Вып. 18. -С. 93-95.

Бартиш М.Я., Огирко И.В., Роман Л.Л. Об одном методе расчета гибких пологих оболочек, находящихся в температурном поле. //Матем. методы и физ.-мех. поля. Львов: -1983. - Вып. 17. -С.71-73.

Бартиш М.Я., Огирко И.В., Фарат В.М. Решение двумерного нелинейного уравнения теплопроводности методом Ньютона-Канторовича // Мат. методы и физ.- мех. поля. Львов: -1986. -Вып.23. - С. 23-26.

Бартіш М.Я. Роман Л.Л. Застосування методів типу Ньютона-Канторовича у нелінійних задачах //Вісник ЛДУ. Cер. мех.-мат. -1982. - Вип.19. -C. 11-13.

Бартіш М.Я., Роман Л.Л. Про один рекурсивний метод розв’язування нелінійних функціональних рівнянь // Вісн. ЛДУ. Сер. мех.-мат. -1986. -Вип. 26. -С. 3-7.

Бартіш М.Я., Сеньо П.С. Про методи типу Рунге розв’язування нелінійних операторних рівнянь //ДАН УРСР. Сер. А. -1972. - № 9. -С. 771-775.

Бартиш М.Я., Сеньо П.С. Рекурсивные итерационные процессы типа Рунге //.Cб. Вычисл. и прикл. матем. - К.: изд-во "Вища школа". -1979. -Т. 39. -С. 149-154.

Бартиш М.Я., Сеньо П.С. О методе Рунге решения нелинейных операторных уравнений третьего и четвертого порядка сходимости // Cб. Вычисл. и прикл. матем- К.: изд-во "Вища школа". -1976. -Т. 28. - С. 85-93.

Бартиш М.Я., Сеньо П.С., Щербина Ю.Н. Итерационно-разностный метод для решения нелинейных операторных уравнений. // Cб. Вычисл. и прикл. матем. - К.: изд-во "Вища школа". -1976. - Вып. 29. -C.50-55.

Бартіш М.Я., Чипурко А.І. Про застосування модифікацій методу Гаусса-Ньютона //. Вісник ЛНУ. Cер. Прикладна матем. та інформатика, -2000. Вип. 1 С. 3-7.

Бартіш М.Я., Чипурко А.І. Дослідження одного рекурсивного методу розв’язування задачі про найменші квадрати //Вісник ЛДУ. Сер. Мех.- мат., - 1997. Вип. 46. С. 68-72.

Бартіш М.Я. Чипурко А. І. Про один метод розв’язування задачі про найменші квадрати //Волинський матем. вісник. –1995.- 2.-С.9-11.

Бартіш М.Я. Чипурко А. І. Дослідження одного методу розв’язування задачі про найменші квадрати //Волинський матем. вісник. –1997.- 4.-С.10-13.

Бартіш М.Я., Чипурко А.І. Про одну модифікацію методу Гаусса-Ньютона. //Математичні студії. Львів: - 1998. - Т.10. - №1. -С. 85-92.

Бартиш М.Я., Шахно С.М. О методе Ньютона с ускоренной сходимостью // Вестн. Киев. ун-та. Моделирование и оптимизация слож. систем. -1987. - Вып. 6. - C. 62-66.

Бартіш М.Я., Шахно С.М. Про деякі модифікації методу Ньютона і їх застосування до розв’язування задач газової динаміки // Вісн. ЛДУ. Сер. мех.-мат. –1982. -вип. 19. - С. 11-13.

Бартіш М.Я., Шахно С.М. Деякі методи розв’язування нелінійної задачі найменших квадратів // Вісник ЛДУ. Cер. мех.мат. - 1993. - вип.39. -C.3-7.

Бартиш М.Я., Шахно С.М. Исследование параметрических итерационных процессов для решения нелинейных уравнений. // Проблемы управления и информатики. –1997. -.№ 2. - С.22-30.

Бартиш М.Я., Шахно С.М. Конечно-разностные методы решения

нелинейной задачи теплопроводности //Мат. методы и физ.-мех. поля. Львов: -1987. - Вып.25. -С. 25-28.

Бартіш М.Я., Шахно С.М., Чипурко А.І. Про одну модифікацію методу Гаусса-Ньютона. // Вісник ЛДУ. Cер.мех.-мат. -1995. -Вип.42. - C. 35-38.

Бартіш М.Я., Щербина Ю.М. Про один різницевий метод розв’язування нелінійних операторних рівнянь. // ДАН УРСР. Cер. А. - 1972. - №7. -С.579-582.

Бартіш М.Я., Щербина Ю.М. Ітераційні методи розв’язування нелінійних функціональних рівнянь і екстремальних задач // Вісн. ЛДУ. Сер. мех.-мат. -1991. -Вип. 35. - С. 3-11.

Бартиш М.Я., Щербина Ю.Н. Об одном итерационном процессе решения нелинейного операторного уравнения // Cб. Вычисл. и прикл. матем. –К.: - ”Вища школа”–1972. -вып. 16. - С. 115-121.

Бартиш М.Я., Щербина Ю.Н. Исследование условной сходимости и оценки полной погрешности одного итерационного разностного метода для решения нелинейных операторных уравнений. //Cб. Вычисл. и прикл. матем. –К.: - Вища школа –1976. -вып. 28. -С. .3-9.

Бартиш М.Я. Об одном классе итерационных процессов типа Ньютона // Сиб. матем. ж. -1972. -Т.13. - № 3. - С. 703-707.

Бартиш М.Я. Об одном классе методов типа Ньютона // Вестн. МГУ. Вычисл. матем. и киб. -1987. - Сер. 15. - №2. -С.16-20.

Бартиш М.Я. Возмущенные аналоги методов типа Ньютона-Канторовича // Мат. cборник.- К.: Наукова думка. -1976. - C. 59-62.

Бартиш М.Я., Щербина Ю.Н. Итерационные формулы, полученные с помощью рекурсій //Мат. сборник. К. Наукова думка. -1976. -C. 50-53.

Bartish M.Ya., Shachno S.M. On the Iterative Steffensen Type Methods // Zeitschrift fr Angewandte Mathematik und Mechanik. Berlin. -1996.- V.76. - №1. P. 351-352.

Бартиш М.Я Об эффективности методов типа Ньютона решения нелинейных функциональных уравнений. //Сб. Численные методы и оптимизация. – Таллинн, Валгус: -1988. - С. 21-28.

Бартиш М.Я. О методах типа Ньютона-Канторовича // Ред. Сиб.матем. ж. -1973. - Т.14. -№4. –904с. Деп.. в ВИНИТИ 17.2.73г., №5653-73.

Бартіш М.Я., Чипурко А.І. Про методи типу Гаусса-Ньютона у випадку задач з малою нев’язкою // Праці міжнародної конференції з управління “АВТОМАТИКА –2000” – 2000. С.50-54.

Бартіш М.Я., Гут Н. П., Мельник А.В. Про деякі модифікації квазіньютонівських методів //Тези міжнародної конф. “Обчислювальна та прикдадна математика”- К. 2002. - С.11.

Бартіш М.Я., Мельник А.В., Николайчук Л. В. Ще раз про квазіньютонівські методи //Тези ІХ Всеукр. наукової конф. “Сучасні проблеми прикладної математики та інформатики” – Львів 2002. – С. 4-5.

Бартіш М.Я. Методи типу Ньютона для розв’язування нелінійних операторних рівнянь та задач на екстремум. – Рукопис.

Дисертація на здобуття наукового ступеня доктора фізико-математичних наук по спеціальності 01.05.02 - математичне моделювання та обчислювальні методи - Київський національний університет імені Тараса Шевченка, Київ, 2003.

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

Запропоновано нову модифікацію методу Ньютона (прискорений метод Ньютона), яка для певного класу задач ефективніша за метод Ньютона, фактично запропоновано і досліджено новий диференціальний аналог методу Стеффенсена. Розроблено цілісну теорію побудови методів типу Ньютона. Дано рекомендації по чисельній реалізації методів із збереженням допустимого (теоретичного) порядку збіжності.

Запропоновано нові модифікації методу Гаусса-Ньютона розв’язування задач найменших квадратів. Дано рекомендації по застосуванню методів

типу Гаусса-Ньютона до розв’язування систем рівнянь і нерівностей. Запропоновано нові модифікації квазіньютонівських методів, які покращують обчислювальні характеристики квазіньютонівських методів, а також запропоновано нові модифікації методу Ньютона, які можна застосовувати при розв’язуванні задач мінімізації у випадку функцій типу яру.

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

Bartish M.Ya. Newton like methods for solving nonlinear functional equations and extremum problems. - Manuscript.

The thesis for obtaining a scientific degree of doctor of physical and mathematical sciences in speciality 01.05.02 - mathematical modeling and computing methods - Kiev Taras Shevchenko national university, Kiev, 2003.

The work is dedicated to construction of effective algorithms for solving nonlinear equations and optimization problems. A new iterative method with the order of convergence * for solving nonlinear equations and its difference analogue is presented. Also a class of recursive methods is offered and an algorithm of choice of effective method in the sense of amount of evaluations for solving a concrete problem is given. A new modification of Newton method, which is more effective for a specific class of problems, is proposed. A complete theory of construction of Newton like methods is developed.

Recommendations for numerical realization of methods with preservation of theoretical order of convergence are given. New modifications of a Gauss-Newton method for solving least squares problems are offered. Recommendations for applications of Gauss-Newton like methods for solving the systems of equations and inequalities are presented. New modifications of quasi-Newton methods which improve computing performances of classical quasi-Newton methods are presented

Key words: iterative methods, order of convergence, recursive algorithms, functional equation, extremum problems.

Бартиш М. Я. Методы типа Ньютона для решения нелинейных операторных уравнений и задач на экстремум. – Рукопись.

Диссертация на соискание научной степени доктора физико-математических наук по специальности 01.05.02 – математическое моделирование и вычислительные методы –Киевский национальный университет имени Тараса Шевченко, Киев, 2003.

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

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

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

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

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

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

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

Разработана и математически обоснована новая модификация метода Ньютона,