Многошаговые итерационные методы вариационного типа тема автореферата и диссертации по математике, 01.01.07 ВАК РФ

КШВСЬКИЙ УШВЕРСИТЕТ 1МЕН1 ТАРАСА ШЕВЧЕНКА

РГб ОД

На правах рукопису

О С гГ

ЖУК Петро Федорович

БАГАТ0КР0К0В1ГГЕРАЩЙШ МЕТОДИ ВАР1АЩЙНОГО ТИПУ

Спещалыисть 01.01.07 — обчислювальна математика

Автореферат

дисертацп на здобуття паукового ступеня доктора (}) I з и ко - м ате м ат и ч ни х наук

ДисертаЩею е рукопис.

Роботу виконано на кафедр1 чисельних методЦв математично'х ф1зики Ки1вського университету iMeHi Тараса Шевченка.

Науковий консультант: доктор фазико-математичних наук,

професор Макаров Володиыир Лестдович.

ОфШйт опонентк: 1. Член-кореспондент HAH Укра!ни,

доктор зико-математичнщ; наук, професор Шор Наум Зуселевич.

2. Доктор ф1зико-математшниг. наук, професор Лучка Антон Юр1кович.

3. Доктор ф1зико-математичних наук, професор Белов lOpiü Анатсшйович.

Пров1дна орган1зац1я: Московський державний ун!верситет

iMeHi М.В.Ломоносова.

Захист в1дбудеться "" 1,'L__1996 p.

о itf годин! на saciflaiiHi спещал1зовано1 ради Д 01.01.23 при Ктвському ун1верситет! iMeHi Тараса Шевчекка за адресом: 252127, и. КИ1В-127, проспект акад. Глушковг., 2, корп. 6, факультет кШериетики, ауд. 40 (тел. (044) 266-12-58-, факс: 266-12-48; E-mail:vpsheicchq.univ.kiev.ua).

3 дисертащею можна ознайомитись у GiöflioTeiu Кшвського ун1верситету iMeHi Тараса Шевченка.

Автореферат розiслано " F "_/У___1996 р.

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

ЗАГАЛЬНА ХАРАКТЕРИСТИКА ПРАЩ.

Актуальность проблемы 1терацшш методи вар1ащйного типу е одними з найбшын поширених метсдов наближеного розв'язку прикладних задач, що допускають вар^ацшну постановку. Найважлившшми прикладами таких задач е липйш задач1 (що зводяться до В1дшукання мМмуму квадратичного функцюнала), задач1 на власш значения самоспряжених лшшних оператор1в (розв'язок яких ргвносильний вщшуканню екстремумпв в1дно-шення Релея) та нелйийт задач! (що зводяться до безумовно! оптим1защ1 неквадратичних, зокрема опуклих, функцюналгв).

Ггеращйт методи вар1ац1йного типу здшснюготь пocлiдoвнy скшченном!рну оптийпзащю функцюнала екстремально! задачь Вони включають таю вщомй геерацшш процеси як методи най-швидгашого спуску, мппмальних ггерацш Ланцоша, спряжених град1ент1в та !х модифжацп.

На В1дмшу в!д Л1шйних ¡теращйних процеав, розв'язувальш оператори вар1ащйних метод1в нав1ть для лшшних задач мають досить складний нелшшний характер, а анал1тичш залежноеп п'ятого та наступних наближень вщ початкового е практично неозорими. Вказаш обставини суттево утруднюють теоретичний аиал1з реально! поведшки ¡теращйних метсдав вар1ащйного типу, що, в свою чергу, заважае 1х практичному застосуванню.

Трудной«, що виникають при практичному використанш вар1ацшних метсдов, а також шляхи !х подолання найбйтыл ч1тко вщслщжуються на приклад! метод1В Ланцоша та спряжених град1ен-пв. Так, дослщження, яи пров1в Ланцош на початку 50-х рогав. показали, що в межах точно! арифметики метод лмшмальних ¡терацШ е ефективним засобом розв'язання лшшних р1внянь та задач на власш значения. Однак, величини. що обчислюються пщ час ¡терування, можуть значно вщхилятися вщ

IX теоретичних аналопв, зокрема, заокругленнями порушуеться ортогональншть м1ж породжуваними векторами. Через це про метод Ланцоша склалася думка (що протрималася до 70-х рогав) як про нестойкий, такий , що не мае практичного значения.

3 початку 70-х рошв штерес до методу Ланцоша починае вщроджуватися завдяки працям Пежа, в яких виконано глибо-кий теоретичний та експериментальний анал1з реально'! (з вра-хуванням помилок заокруглення) поведшки методу та виявлеш причини його нестшкость Показано, що втрату ортогональност1 викликае зб1жтсть одного з вектор1в Р1тца, причому при про-довжент процесу вш немов "забувае", що вже знайшов власну пару 1 починае обчислювати II знову.

Подалыш дослвдження (C.C.Paige, С.Н.Оо1иЬ, В.К.Раг1еи, 1.Си11иш, Т.Етчсззоп, Н.й.МаиЫеБ, J.Yicheng, Б.К.Клт, Н.'УУогш-акси^к!, С.Писсанецки) спричинилися до створення досить стойких алгоритм!в методу Ланцоша як для частково!, так 1 для повно1 задач на власш значения. Незважаючи на досягнутий прогрес, теор1я методу Ланцоша далека ввд завершения, на що вказуе, зокрема, той факт, що анал1зуючи реальну швидгасть зб1жност1 цього методу, перевагу вщдають чисельним експериментам.

Аналогична ¡стор1я методу спряжених гpaдieнтiв, який запропонували на початку 50-х рогав Хестенс та Штифель для розв'язування систем лшШних р1внянь. Дей метод хоча 1 е 1терац'1йним, але зб1гаеться до точного розв'язку системи за скшченне число ¿теращй при вщсутносп помилок заокруглення. Ця властивкть та нескладна обчислювальна схема методу спряжених град1ент1в ввдразу ж привернули до нього увагу спеща-л1ст1Б з чисельного анал1зу. Однак широкого розповсюдження спочатку вш не отримав, осюльки були виявлеш випадки його чисельно! нестшкость яка призводить до розб1жност1 методу.

3 середини 60-х рошв цжавкть до методу спряжених град1снт!в вщроджуеться. По-перше, виявилася здатшсть методу до прискорення зб1жноеп стацюнарних ¡теращйних процеав (С.К.Годунов, Г.П.Прокопов, О.А.Самарський, е.С.Школаев, Г.ЬМарчук, Ю.О.Кузнецов, Л.Хейгеман. Д.Янг). По-друге, було до-сягнуто певного прогресу в розумшш реального обчислювального процесу. На основ1 чисельних експеримештв було показано (М.ЕпдеП, Th.Ginsburg, НЛи^Иаизег, E.Stiefel), що хоча теля п ¡терацш методу спряжених град1ент1в (п - хйршеть лшшно! системи) наближений розв'язок може значно вiдpiзнятиcя вщ точного, це не ввдбуваеться, якщо гальгасть ¡терацш перевищуе . п. При цьому рано чи п1зно настае момент, коли в1дхилення почне р!зко зменшуватися, 1 в кшцевому рахунку точтеть розв'язку буде визначатися числом обумовленноеп матрищ системи. Потрете, було пом1чено ( ,1.К.11е1с1, Р.СопсиБ, О.Оо1иЬ, О.ОЪеагу), що тд час розв'язування йткових р!внянь метод спряжених град1е-нтпв, як правило, зб1гаеться досить швидко, особливо з передобу-мовлювачем, причому гальысть необхщних для досягнення задано! точност1 ¡терац1й виявляеться значно меншога, шж лпршеть

I

системи.

Незважаючи на досягнутий прогрес, питания про вплив помилок заокруглення на поведшку методу спряжених град1ент1в у значнш М1р1 залишаеться вщкритим; в л1тератур1, як правило, анал1зують лише результати чисельних експеримент!в.

При побудов! чисельно стшких вар1ант1в методш Ланцоша та спряжених гpaдieнтiв часто використовують (особливо для нелшшних задач) процедуру вщновлення початкового ¡терацш-ного процесу (ЕЛолак, Б.Т.Поляк, Ф.П.Васильев, Г.ЬМарчук, Б.М. Пшеничний). Ця процедура полягае в тому, що в деят моменти (моменти вщновлення) ¡терацшний процес перериваеться, а пот1м

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

Утворений таким чином цикла чний процес називасться багатокроковим або Б-кроковим, якщо вщновлення вщбуваеться через кожи з (з > 1) иерацш. Так, вщновлюючи через кожш б ¿терацш метод Ланцоша (метод спряжених град!снт1в) отримуемо вщповщно Б-кроковий метод Ланцоша (Б-кроковий метод спряжених град1ент!в).

Багатокроков1 методи Ланцоша 1 спряжених градгатв вщносять до класу багатокрокових 1терацшних метод1в вар^а-цшного типу, початок вивченню якого покладено в працях Л.В.Канторовича. Л.В.Канторович запропонував для розв'язування лшшних операторних р1внянь Б-кроковий метод найшвидгашого спуску, (к+1)-ше наближення якого вибирають з умови мш1муму в1дпов1дного квадратичного функцюнала на Б-м1рному шдпростор! Крилова, породженому к-м наближенням.

Для лшшних задач э-кроковий метод найшвидгашого спуску -пено пов'язаний з к-кроковим методом спряжених град1ент!в: фактично Б-кроковий метод спряжених град1ент1в е ефективною схемою реал1зацп на ЕОМ Б-крокового методу найшвидгашого спуску (ГД.Марчук.,' Ю.О.Кузнецов). Аналопчно сгаввщносяться м1ж собою Б-кроковий метод найшвидгашого спуску, який запропонував М.Ш.Б1рман для задач на власш значения, та б-кроковий метод Ланцоша. Для нелшшних задач, однак, Б-кроков1 методи, що здшенгоють послщовну Б-м1рну оптим^защю функцюнала задач!, можуть значно вщр1знятис:я вщ Б-крокових методов, побудованих за допомогою процедури вщновлення.

При б=1 Б-кроковий метод називають однокроковим; прикладами однокрокових метод1в вар1ацшного типу е таю вщом1 ¡терацшш процеси, як метод найшвидгашого спуску, метод мш1мальних нев'язок та а-процеси (М.А.Красносельський,

С.Г.Крейн), метод мнимальних похибок (В.М.Фрщман), двошаров1 град1ентш методл (О.А.Самарський, С.С.Нжолаев).

1стормчно першим ¡терацшним методом вар1ацшного типу е метод найшвидюшого спуску, який запропонував Копп в 1847 рощ. Дослщженню, використанню та узагальненшо цього методу присвячеш роботи Р.Куранта, Л.В.Канторовича, Дж.Форсайта, М.Ш.Б1рмана, В.А.Самокиша, А.М.СЫгочузЫ, J.Crokett, М.АНтап, О.А.Самарського, Б.М.Пшеничного, Г.1.Марчука, е.С.Ншолаева, Ю.О.Кузнецова, Б.Т.Поляка. Ю.1.Люб!ча, Г.Д.Майстровського, В.Г.Приказчикова та шших автор!в.

Основним недолжом методу найшвидкшюго спуску е вщносно невисока швидюсть зб1жноеп, оссбливо для погано обумовлених задач. Причини тако! поведшки методу аналгзувалися на початку 50-х рогав Дж.Форсайтом та Т.Моцкдним. Вони вивчали асимптотичну поведшку методу найшвидкгшого спуску

ик_г = ик - ткгк , к = 0,1,...,

= Аик - f , тк = (гк , гк)/(Агк , гк),

при розв'язувант системи лшшних р1внянь Аи = £ з симет-ричною додатною матрицею А. На тдстав! чисельних ексгтеримотв вони висловили в 1951 рощ таке припущення: якщо ыо^по ф т0 Длк вс1х 1< 1 < п = °(||2к1)' К0ЛИ да, причому похибки методу найшвидгашого спуску 7.к — ик - и , к=0,1,..., наближаються за напрямом до площини ~1п , натягнуто! на вектори еь еп, коливаючись м1ж двома граничними напрямками (тут , \ = 1, ... , п, - коефщенти розкладу вектора гк за системою власних векториз {е;} матрищ А). 3 цього припущення, зокрема, випливае, що метод найшвидкшюго спуску е асимптотично лшшним, а ттерацшний процес, складений з двох його послщовних

¡терацш, - асимптотично стащонарним (така асимптотична поведшка методу найшвидшшого спуску дозволила Форсайту та Моцшну рекомендувати для його прискорення прийоми приско-рення лшШних и-еращйних процесш).

Доведения вказаного припущення було знайдене лише в 1959 рощ Н.Екейком за допомогою розвинуто! ним технши послщовних перетворень розподшу 1мов1рностей. Результат Екейка вказуе на глибокий зв'язок м1ж вар^ацшними методами з перюдичшш вщновленням та лшшними (зокрема, стащонарними) и-еращйними процесами.

Вивчення цього зв'язку продовжив Форсайт в 1968 рощ. BiH розглянув s-кроковий метод найшвидшшого спуску

uk+1 = uk + Yl'k) rk + y2(k) Ark + .. . + ys(k) A5"1 rk , k=0,l,...,

де rk = Auk - f, A - симетрична та додатна матридя, а 1терацшш параметри {y,(k\ i=l,...,s} вибирають з умови митмуму квадратичного функцшнала F(uk+1) = 0.5 (Auk+1, uk+1) - (ик_х, f). Основну увагу Форсайт придалив опису множини граничних напрямшв послщовносп град1ент1в rk, осюльки iHiiri асимптотичш характеристики методу можна знайти за допомогою uiei множини.

Позначимо через ук = гк/||гк| послвдовшсть нормованих град1ент1в, через R(y0) - множину граничних вектор1в послщовноеп ( Угк 1 к=0,1, ... }, а через Т - нелшшний оператор, визначений на частиш одинично! сфери простору сшвввдношенням ук+1 = Тук. Нехай, KpiM того, у0 = + ... + цеп (£, ф 0, ... , г| * 0) - розклад вектора у0 за системою власних вектор!в еь ... , еп матрищ А, ввдповщних р!зним власним значениям. Основним результатом Форсайта е твердження: якщо n > s, то

1) розклад будь-якого вектора у е R(y0) за системою вектор!в

еь ... , еп шстить не менше э+1 I не б1лыие 2э ненульових компонент;

2) якщо у е Щу0), то Т2у = у , тобто будь-який граничний вектор швар1антний за напрямом вщносно двох послщовних ¡терацш з-крокового методу найшвидюшого спуску;

3) множила Щу0) - континуум (тобто замкнена та зв'язна множина, що складаеться, можливо, з одте! точки).

Вщзначимо, що з результату Форсайта не випливають ш збЬкшсть послщовноеп { у2к , к=0,1, ... }, га асимптотична лшшшсть з-крокового методу найшвидтшого спуску. Остльки 1 те, 1 шше мають м!сце, зпдно з Екейком, для методу найшвидшшого спуску, виникае запитання: чи дШсно поведшка з-крокового методу так сильно вщр1зняеться вщ поведшки методу найшвидгашого спуску?

Спираючись на результата чисельних експеримент:в з 2-кроковим методом, Форсайт зробив висновок, що асимптотична поведшка з-крокового методу найшвидюшого спуску в дИ1Сност1 аналопчна асимптотичшй поведшщ методу найшвидгашого спуску. Вш висловив у 1968 рощ ппотезу: якщо п > э, то послщовшсть { у2к , к=0,1, ... } зб1гаеться .

Для скшченном1рних простор!в riпoтeзa Форсайта не доведена 1 не спростована до цього часу. Для нескшченномфних простор1в вона не в1рна, оскшьки послщовшсть { у2к , к=0,1, ... } може бути некомпактною ( див. §1.6 дисертащйно! роботи ).

Недосконалшть теоретичного анал1зу э-крокових ¡терацшних метод1в вар1ацшного типу не дозволяе використовувати в повнш .шр1 1х потенцшш можливост1, зокрема, застосовувати до них прийоми прискорення, розроблеш Д ж.Форсайтом, Т.Моцганим, О.А.Самарським, С.С.Нтолаевим, А.Ф.Заболоцькою та шшими авторами для однокрокових метод!в типу найшвидтшого спуску. Таким чином, дослщження поведшки (зокрема, асимптотично!)

s-крокових ггерацшних методов Bapiamiünoro типу е актуальною проблемою обчислювально! математики.

Bei 1терацп s-крокового методу здшснюються однотипово. У принциш можна побудувати ггерацшний процес, що являе собою комбшащю р1зних iTepayiteux методгв (таким ¡теращйний процес природно назвати комбшованим ).

Першим прикладом комбшованих 1терацшних метсдав Bapiauiiinoro типу с, мабуть, метод двоступшчатого град1€нтного спуску ( д. г. с. ), який запропонували в 1980 рощ В.В.Ермаков та М.М.Кал1тган для розв'язування систем лшшних р1внянь з додатною матрицею. Кожна непарна ¡теращя д. г. с. виконуеться за методом мннмальних нев'язок, а кожна парна - за методом найшвидгашого спуску.

Незважаючи на простоту конструкцп методу д. г. е., шяких теоретичних результате про його зб1жшсть, а тим бшьш про швидгасть зб1жност1, В.В.Срмаков i М.М.Калтан не отримали. На пвдетав) чисельних експеримент1в вони дшшли до висновку, що д. г. с. кращий за методи найшвидгашого спуску та м1шмальних нев'язок, взят: окремо, та його швидгасть наближаеться до швидкосп зб1уКност1 методу спряжених град1ент1В. Але С.П.Воскобойшков, Ю.В.Сешченков та ЬА.Цукерман в 1983 роц5 показали (знову ж таки за допомогою чисельних експеримента), що для несиметричних матриць д. г. е., взагал! кажучи, не ефективний.

Деяка протилежшеть висновгав наведених вище авторш вказуе на необхвдшетъ доповнення результатгв чисельних експе-риментсв теоретичними доелвдженнями. Трудноиц таких дослщ-жень виникають, зокрема, через те, що поведшка д. г. с. ¿стотно в!др1зняеться вщ поведшки метод1в, що його складають. Наприклад, чисельт експерименти показали, що метод д. г. с. навпъ для симетричних матриць не е асимптотично лшшним, i

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

Отже, досл!дження швидкоеп зб!жност! комбпшваних ¡тера-цшних метод!в Еар1ащйного типу е актуальною проблемою обчис-лювально! математики.

Осгальки не ¡снуе загально! схеми, яка б ластила валяю багатокроков1 ¡терацшш методи вар1ащйного типу, п!д цим термшом у дисертацшнШ пращ розум1емо тага вщом! ¡терацшш процеси, як s-кpoкoвi вар1ащйш методи розв'язування л!ншних операторних р1внянь, явш та неявш з-кроков1 методи найшвид-кплого спуску для задач на власш значения (що мютять э-кроковий метод Ланцоша), э-кроковий метод спряжених гра-д1ент1в Полака-Риб'сра для нел1шйних задач, а також комбшован! ¡теращйш методи вар1ащйного типу.

Метою дано/ роботи с:

1) побудова асимптотично! теорп з-крокових ¡терацшних метод1в вар1ащйного типу;

2) дослщження швидкост1 зб1жност1 комбшованих ¡теращйних метод1в вар1ащйного типу;

3) розробка на основ! асимптотично! теорп прийом1в при-скорення з-крокових ¡теращйних методов вар!ацшного типу.

Загальна методика дослщжень.

За основу дослщжень вз:ги методи теорп ¡терацшних процеав та теорп лшшних оператор1в в гшьбертовому простор!.

Наукова новизна резуль та Т1в:

• отримаш умови стабШзацп та непокращуваш оцшки швидкосп 301ЖН0Ст1 Б-крокового методу розв^язування лшШних операторних р1внянь та Б-крокового методу Ланцоша;

• дослвджена асимптотична поведгака п-ерацшних параметр1в Б-крокових метод1в вар1ацшного типу та доведено такий аналог гшотези Форсайта: якщо за даного початкового наближення Б-кроковий метод не стабь*пзуеться 1 не зб1гаеться суперлшшно, то юнують граничш ¡терацшш параметри методу по парних (непарних) iтepaцiяx. Отже, за вказаних умов, Б-кроковий метод е асимптотично лшшним. а гтерацшний процес, що складаеться з двох його посл1Довних 1терацш, - асимптотично стацюнарним;

> вивчеш асимптотичш напрями похибки Б-крокового методу вар1ащйного типу та отримаш аналоги результатш Екейка та Форсайта;

• визначеш штотт облает! значень асимптотичних швидкостей зб1жност1 Б-крокового вар1ацпшого методу розв'язування лшшних операторних ршнянь та Б-крокового методу Ланцоша;

• отримаш двосторонш оцшки осереднених швидкостей зб1жност] комбшованих ¡теращйних метод1в вар1ащйного типу.

В^рогщтсть результата випливае з 1х строгих математи-чних доведень.

Практична значимость роботи.

Результата дисертацп можуть бути використаш для тдвищення ефективност! э-крокових метод!в варгацшного типу (для прискорення !х зб1жност1, для формування критерии закшчення), а також для отримання додатково! шформацп про оператори задач! практично без додаткових обчислень. Кр1м того, розвинуту в робот! методику можна використовувати при дослщженш шших ¡терацшних методов вар1ащйного типу.

Апробащя роботи.

Основш результата доповдалися на III Республжансьюй конференци ''Вычислительная математика в современном научно-техническом прогрессе" (Кансв, 1982), на науковому семшар1 "Питання теорп р!зницевих схем" проф. В.Л.Макарова в Кшвському ушверситет] Тараса Шевченка, на науковому

семшар1 акад. О.А.Самарського в Московському ушверситет1 1м М.В. Ломоносова.

Публжацп.

Результати виконаних дослщжень надруковаш в 14 наукових статтях та тезах допов1дей.

Структура та об'ем роботи.

Дисертацгя складаеться з вступу, п'яти розд!л1в та додатку; вона мютить 265 сторшок машинописного тексту. Б1блюграф1я складаеться з 164 найменувань.

КОРОТКИЙ ЗМ1СТ РОБОТИ.

В роздш 1 вивчаються э-кроков1 перацшт методи вар1а-цшного типу розв'язування лшшних операторних р1внянь Аи = 1' в пльбертовому простора Означення та способи реал1зацп цих метод1в наведет в §1.1. Означення спираеться на загальну теорш ¡терацшних методов Самарського та охоплк>£ широкий клас ¿теращйних процеав, включаючи неявш з-кроков1 методи найшвидгашого спуску, спряжених град1ент1в, спряжених невязок, спряжених поправок та спряжених похибок. Однак, на вщмшу вщ теорп Самарського, оператори А, В, Б ¡терацшно! схеми не обов'язково обмежет; вщносно них припускаемо:

1) област! визначення , оператор1в А, В, Б щшьт в Н;

2) оператор Б самоспряжений та додатно визначений в Н;

3) область визначення , . оператора В"1 А ццльна в енергети-

в а

чному простор! Нп 1 V и. V £ А п Нс

а) В~хАи е Н0 , б) (В_1Аи, = (и, В^АуЬ ,

в) V, |и||* < (В"1 Аи, и)0 < У2||и£, 0< V, < у2.

Наведеш вище припущення виконуються, наприклад, якщо А та В - самоспряжен! додатно визначеш оператори з щшьними в Н областями визначення, причому ВА - (оператори А та В под1бш) 1 Б = А.

Для скшченном1рних простор1в ВА = = П^ ~ Х>в_, = Н, а

умови б), в), записан! у вигляд1 (БВ^Аи, V) = (и, БВ-1Ау), \'1(Би. и) < (БВ-1 Аи, и) < \'2(Ви, и) екв!валентш умовам самоспря-женого, у значенш Самарського, випадку: оператор БВ~'А самоспряжений та додатно визначений в Н, а V), - постшш енерге-тично1 екв1валентност] оператор1в Б та БВ_1А .

3 умови 3) випливае, що оператор В"1 А може бути розши-рений до обмеженого самоспряженого та додатно визначеного в енергетичному простор! Н0 оператора К. За означениям послщо-вш наближення з-крокового методу пов'язаш м1ж собою рекуре-нтним спшв1дношенням

= ик + Кгк + . .. + У£(к) К5 2к , к=0Д,...,

де и0 - довшьне початкове наближення з Нп , = ик - и, и - точний розв'язок р1вняння Аи = 1 (припускаемо, що и е Ни), а гаерацШш параметри { у/к', 1=1, ... , з } надають мш1мум квадра-

II *И2

точному функционалу Г(ик+1) = ик+1 - и .

Для чисельно! реал1зщп з-крокового методу в робот! наведеш формули тришарово! схеми та схеми з поправкою методу спряжених напрям1в з в1дновленням через б ¡терацш.

В §1.2 установлена тотожшсть

(2^2 - 2кЬ = ¡2к + 1||в > к=0,1,..., (1)

яка ввдграе важливу роль в анал1з1 з-крокового методу. За допомогою ще! тотожносп в §1.3 знайдена умова закшчення з-крокового методу за скшченну гальгасть ¡теращй (умова стабипзацп): якщо вектори г0, К;:ч, ... , К8гч лшшно залежш, то и.г = Щ — ... = и , ¡накше ик ф- и , к=0,1, ... . Цей результат дозволяв розглядати в подальшому тьтьки таю початков1 наближення, за яких вектори г0, Кг0, ... , К"г0 лшшно незалежш (множина таких г0 позначаеться через УС }. Вщзначимо, що для неквадратичних функцюналго простих умов стабш1зацп з-крокового методу, под!бних попередньому, взагал1 кажучи не ¡снуе (винятком е э-кроковий метод Ланцоша, який розглядаеться в другому роздьт!).

Тотожшсть (1) с також основною для досл1джень швидкост1 зб1Жност1 з-крокового методу, виконаних в §1.4. Швидгасть зб1жност1 з-крокового методу з початковим наближенням и0 характеризуеться послвдовшстю рк(и0) = |2к+1||в/||2к1о> к=0Д, ...

(величина рк(и0) визначае швидгасть спадання функцюнала, що ми«м1зуеться, на (к+1)-1й 1терацп). Втдносно ще! послщовност! доведено слвдуюче твердження.

Теорема 1.4.1. Якщо и0 - и е "2с, то послщовтсть рк(и0) монотонно не спада с та обмежена зверху, тобто

рк(и0) < рк-п(и0) < р3*(и0) < Рэ" < 1, к = 0,1, ... ,

де ps (u0) = шах 17is(t,u0) I, ps = max | ;:s(t) I, Z0 - множила tela tesp(K)

тонок росту функцп розподшу a0(t) = (Etz0, z0)D вектора z0 (E; - спектральна функция оператора К), 7ts(t,u0) та Tcs(t) - много-члени В1Д зм1нно11 степени s, яю найменш вщхиляються вщ нуля вщповщно на множит "La та спектр! sp(K.) оператора К.

Отже, для будь-якого наближення и0 s-кроковий метод зб1гаеться принайми! як геометрична прогрейя i3 знаменником рь (ис), причому 3i збмьшенням к1лькост1 ггеращй, швидгасть зб1Жност1 методу може лише зменшуватися.

Дал1 розглядаеться питания про точшсть одержаних в теорем! 1.4.1 оцшок швидкост! зб1жносп s-крокового методу.

Теорема 1.4.2. Якщо спектр оператора К лпстить бшьше, тж s точок, то для будь-якого е >0 icnyc початкове наближення и0(с) таке, що ps - е < pk(u0(e)) < ps , k=0, 1, ... ; якщо, до того ж, спектр оператора К складаеться тшьки 13 власних значень, то юнуе початкове наближення и0 таке, що

Pk(uo) = Ps'("o) = Ps*, k = 0,1.....

Отже, ощнка pk(u0) ä ps , k = 0, 1 , ... - непокрагцувана, а для onepaTopiB К з чисто точковим спектром - досяжна.

В §1.5 вивчасться асимптотична поведшка ¿терацшних па-раметр!в s-крокового методу. Доведено аналог гшотези Форсайта.

Теорема 1.5. Якщо u0 - u g 7t, то ¡снують граничш параметри s-крокового методу

у У = lim 7i2k+v), i = 1.....s; v = 0, 1,

k—>co -

як/ залежать вщ початкового наближення.

3 цього твердження випливае, зокрема, що s-кроковий метод е асимптотично лшшним, а ггеращйний процес, що складаеться з двох його послщовних ггерацдй, - асимптотично стащонарним. Отже, асимптотична поведшка s-крокового методу в пльбертовому

npocropi цшком аналопчна асимптотичшй поведшщ методу найшвидшшого спуску в сшнченном1рному npocTopi.

В §1,6 вивчена асимптотична поведшка нормованих похибок j'k = zk/j|zkj|D s-крокового методу. Параграф складаеться з трьох пупков. В першому отримаш аналоги результат1в Екейка та Форсайта в термшах функцш розподшу <pk = <pk(t) = (Etyk, yk)D вектор!в yk. Нехай

p(v'(t) = 1 + Tat + ... + 7 $ ts, v= 0, 1; q (t) = p(1)(t) p(0)( t) - p2, де yj = lim yfk+v), i = 1, ... , s; p = lim pk(u0). Кореш многочлешв

k—>oo

p^v)(t.), v = 0, 1, та q(t) дШсш та розмщеш на вщр1зку [vt, v2], Позначимо через % множину коретв многочлена q(t).

Нехай - множина граничних функщй послщовносп

k=0, 1 , ... } в1дносно поточково! зб1жноеп, а Ф = Ф0 и Ф,-множина граничних функхдй посл1довност1 { <pk, к = 0, 1 , ... }.

Лема 1.6.3. Будь-яка функц!я ф е Ф кусково стала та мае не менше, тж s+1 , та не бшьше, тж 2s, стрибтв, причому тэчки с трибк1 в належать множит "71 n So.

Отже, опис множини Ф зводиться до опису деяко! шдмно-жини скшченном1рного простору. А саме, нехай Хд< ... <^Nr -

впорядковаш елементи множини % г\ Z0- Позначимо через tri

множину неспадних на пром1жку ]-оо, дШсних функщй, через R^ - Ы-м1рний дШсний евклщовий npocTip i розглянемо вщобра-

ження Ш —>Rn , що задаеться формулою

= (Ч4Х1 + е) - v|/(Xi - е). - , V(Xn + G) " 1KXn - е)),

де число е > 0 вибираеться так, щоб штервали Д;(е) = (Хге< Xi+S [> i=l, ..., N, попарно не перетиналися . Воображения 7 встановлюе

взаемно однозначне стввдношення М1>к множиною Ф та його скшченном1рним образом V = -7Ф, причому гюсл1Д0вшсть {(рк., 1=1,2,...} поточково зб1гаеться до ф тод1 ! тьльки тод!, коли

послвдовшсть {5фк., 1=1,2,...} збхгаеться в простор! до ;/ф.

Позначимо через уе {0,1}, множину нев:д"емних розв'я-зюв (Ьх, ... , Ьк) системи лшшних р1внянь

Ц + ... + =-1, I = 0 , 3 = 1, 2, .... 3.

1=1

Покладемо V,. = ИФу , у = 0,1. Аналогом результату Форсайта с Теорема 1.6.1. Якщо и0 - и е ЪС, то

1. Будь-який вектор в V мае не менш, шж 5+1, У не бшьш, тж 2б ненульових компонент.

2. У,с№„ v = 0, 1.

3. Якщо послщовтсть {(рк;, \ = 1, 2, ... } поточково зо1гаеться до

функцп' ср е Ф, то до щс! ж функцп збпаеться поточково посл!довтсть {фк;+2, ! = 1, 2, ... } .

4. Множини V = 0, 1, с континууми (тобто, непорожт зв 'язт та замкнет в Т1к множини).

Узагальненням результату Екейка е Теорема 1.6.2. Якщо и0 - и ей', то послщовтсть { ф2к-у> к=0,1, ...}, V е {0, 1}, функцш розподшу нормованих похибок однокрокового методу поточкового зб^гаеться до кусково стало! функцп 31 стриб-ками в точках ул,

3 теореми 1.6.1, зокрема, випливае, що для будь-якого г > 0

тобто, нормоваш похибки з-крокового методу асимптотично ви-роджуються в тдпроепр (Ед1(е) + ... + ЕД[^(с))Нп.

В другому путсп §1.6 описана множина граничних вектор1в послщовност1 {ук, к = 0, 1, ... }.

Позначимо через ... < %п власш значения оператора К,

яга належать множит (хь - , Хм/- Нехай Н^ - власний тдпрост1р

оператора К, вщпоещний до власного значения Хд (1 = 1..... п).

Уо'- ортогональна проекщя вектора у0 на шдпроепр Н^, Ьп - лшшна оболонка, натягнута на вектори уд1', 1 = 1, ... , п, а Л - базис гадпростору Ьп , складений з ненульових вектор!в у(0''. Позначимо через V е {0, 1}, множину одиничних в Н0 векторов у е Ьп , що задовольняють р1вноеп

(КУУ)(К)у, УЬ =0, 1 = 1, 2,... , з.

Узагальненням 1 уточнениям результату Форсайта в тер-мшах граничних вектор)в е

Теорема 1.6.3. Якщо 91 * 0, то 1. 51 с Ьп I розклад будь-якото вектора з 91 за базисом ¿В мстить не менше, т'ж э+1, та не бшыне, тпж 2з ненульових компонент. 2.1Л,сУи v = 0, 1.

3. Якщо послщовяють {ук., \ = 1, 2, ... } збпаеться в Н0 , то в Нп зб/гаеться послщовтсть {ук.+2> ! = 1, 2, ... } / границ/ одна ков/.

4. Якщо пос.тпдовтстъ { ук, к = 0, 1, ... } компактна в Н0 , то мно-жини у , у=0Д, - континууми (тобто, непорожт зв'язт та замкнет в Нп множини).

Узагальненням результату Екейка е

Теорема 1.6.4. Якщо послщовтсть нормованих похибок {Ук- к=0,1, ...} однокрокового методу компактна в HD , то по-слщовност2 {угк-tv, к = 0, 1, ... }, v = 0, 1, зб!гаються в HD .

В третьому пункт! §1.6 отриманий критерш компактности noaniflOBHOCTi {yk, k = 0, 1, ... } за умови, що граничними точками множини In можуть бути лише числа v. = min Z0 , v = max L(l.

Теорема 1.6.5. Пехай граничними точками множини 2(1 можуть бути лише числа v,. v. Год/, якщо v„, v - власш значения оператора К, то послщовшсть {yk, к = 0, 1, ... } компактна в HD, ¡накше 91 = 0.

Теорему 1.6.5 можна застосувати до onepaTopiß К=аЕ+С, де а > 0. С - додатнш компактний самоспряжений оператор. Зокрема. якщо число 0 - точка спектра, але не власне значения оператора С, то icHye початкове наближення таке, що 94 = 0.

В TeopeMi 1.6.6 доведено, що для однокрокового методу наведений вище критерш компактное^ послщовност] ук в1рний i без припущення вщносно граничних точок множини So.

У §1.7 розглянуто випадок скшченном1рного простору. В п.1 описана множина X одиничних вектортв, швар1аытних за напрямком ввдносно двох послщовних 1терацш s-крокового методу. Показано, що множина Ц складаеться з граничних вектор1Е валяких послщовностей {ук, к=0Д, ... }; таким чином, у0 е тод] i тшьки тод1, коли посл1довност1 {y2k, k=0,l, ... }, {y2k+i, k=0, 1. ... }, {pk(u0), k=0,l, ... } постшш. Отримане зображення множини ЭС у вигляд1 об'еднання незл1ченно! сукупносл множин невщ'емних розв'язгав систем лшйних р!внянь.

У другому пункт1 §1.7 визначена ¡стотна область значень асимптотично! швидкост зб1жност1 s-крокового методу вщносно

Mipn Лебега. Пщ асимптотичною швидгастю зб!жност1 розумтемо таку функщю в1д початкового наближення :

V(uo) Л~1П P(U0)> U°._U* ** [ оо, u0 - и g 7С

до p(u0) = lim pk(u0). Доведена

к—>оо

Теорема 1.7.3. Якщо dim H > 2s+l, то

vrai inf V(u0) = - In pg, vrai sup V(u0) = - 0.5 in p'2S , H , H

де pi = шах I щ(Ь) ), 7T;(t) - многочлен степеня i, що найменш

tssp(K)

вщхиляеться вщ 0 на cneicTpi оператора К i тг,(0) = 1.

Отже, хоч функщя V(u0) необмежена, вона îctotho обмежена ввдюсно м1ри Лебега.

Теорема 1.7.3 дозволяе пор1внювати багатокроков1 методи м1ж собою. Точтше, нехай е > 0 i

ks(u0,s) = min { k i Jjuk - u*||d<s||u0 - u*||d}.

Будемо говорити, що з^кроковий метод з початковим наближен-ням и0 асимтотично ефектившший за з2-кроковий метод з початковим наближенням v0, якщо icHye e(u0,v0) > 0 таке, що для bcîx О < s < s(u0,v0) виконуеться нер1втсть Sjkgj (u0, s) < s2kg2 (v0, s).

3 теореми 1.7.3 випливае, що для майже bcîx (за м1рою Лебега) пар початкових наближень (u0, v0) 2з-кроковий метод асимптотично ефектившший за s-кроковий метод. Оск1льки кшькють арифметичних операцщ, що необхщш для двох ¿терацш s-крокового методу, практично дор1вшое кшькос-п арифметичних операцш при одшй перацп 2з-крокового методу, то для майже bcîx пар початкових наближень 2э-кроковий метод асимптотично ефектившший за s-кроковий метод i щодо обчислювальних витрат.

В наступних двох роздшах дисертацШшн роботи теор1я s-крокових и-еращйних методов вар1ацшного типу, що розроблена в

роздип I стосовно лишних операторных р1влянь, поширюеться на задач! про власш значения, яга зводяться до оптикпзацп вщношення Релея. Осгальки властивосп явних та неявних ¡терацшних метод!в обчислення власних значень ютотно В1др1з-няються 1 дослдакення неявних метод1в не зводиться до вивчення явних за допомогою лйпйних замш (що мае мюце для ¡терацшних метод1в розв'язування лшшних операторних ршнянь). то в дисертацп вивчення явних та неявних з-крокових методов обчислення власних значень проводиться окремо.

В роздш 2 дослщжуеться явний э-кроковий метод найшви-дгашого спуску (скорочено: Б-кроковий метод) при знаходженш меж; спектра лшшного обмеженого самоспряженого оператора А, що д1е в дшсному ильбертовому простор! Н. Осгальки вщшукання верхньо! меж1 М спектра оператора А, зводиться, за допомогою замши А на (-А), до ввдшукання нижньо! меж] ш, то ми обмежилися задачею мшЬпзацП вщношення Релея >.1 (и) = (Аи, и)/(и, и). Зазначимо, що до щс! ж задач! зводиться також в^дшукання нижньо! меж1 спектра пучка лшШних самосп-ряжених оператор1Б (К, Ь), де оператор Ъ додатно визначений, а оператор А = Ь_1К обмежений в енергетичному простор! Нь.

В §2.1 дано означення та вказаш деяга способи чисельно! реал1зацп з-крокового методу, зокрема за допомогою алгоритм}' Ланцоша (з-кроковий метод, реал1зований за допомогою алгоритму Ланцоша, часто називають Б-кроковим методом Ланцоша або методом Ланцоша з вщновленням). Послщовш наближення Б-крокового методу породжуються рекурентним сгпввщношенням

^ = £а|к)А'ик, к = 0,1,..., ¡=о

де ¡терацшш параметри {а-к\ 1 = 0, 1, ... , б} вибираються з умов (-1)5 а® > 0, |ик+1|| = 1 1 надають м1шмум функщоналу р (ик_1).

Нехай х0 = и0,

х^ = А5 хк + у<» А5"1 хк + ... + у(0к) хк, к = О, 1, , у(к) = а(к)/а(5к), 1=0, 1, ... , гк = Ахк - цкхк, Уцк = рк - ц^

В § 2.2 доведена основна енергетична тотожшсть

(2к+2, 2к) = |2к+1|]2 - УЦк(2к.2, Хк), к = 0, 1, ... , (2)

що вццграе таку ж важливу роль, як 1 тотожшсть (1) в першому роздш!.

Будемо говорити, що Б-кроковий метод з початковим набли-женням и0 стаб1л1зуеться, якщо для деякого номера к е {0, 1, ... } мае м1сце р1втсть \ук = Аик - ркик = 0, тобто 5-кроковий метод знаходить деяку власну пару оператора А за скшченне число п-ерацш.

За допомогою тотожноеп (2) в §2.3 знайдена умова стабтзацп з-крокового методу. Позначимо через 3 та Ш множини одиничних векторш и0, для яких вектори и0, Аи0, ... , А и0 ввдповщно лшшно залежш та лiнiйнo незалежш.

Теорема 2.3. Якщо и0 е 3, то = 0, ¡накше ик е , к=1,2,... .

3 теореми 2.3 випливае, що з-кроковий метод стабш1зуеться тод1 1 тшьки тод1, коли и0 е 3. Отримана умова стабийзаци щлком аналопчна умов! стабш1зацп э-крокового методу при розв'язуванш лшшного операторного р1вняння. 3 не!, зокрема, випливае, що, якщо власна пара оператора А не була знайдена за одну п'ерацно з-крокового методу, то вона не буде знайдена 1 на наступних ¡теращях.

Надал1 вщносно спектра оператора А г початкового набли-ження припускаемо, що

1) m>0, M=1 (це припущення не обмежуе загальноеп резуль-тат1в, але спрощуе запис);

2) m - 1зольована точка спектра, причому sp(A) с {ш} и [ш , 1], ш < m <1;

3) р0 < ш (це припущення забезпечуе зб1жшсть цк до ш ).

В §2.4 дослщжуеться швидюсть зо1жност1 s-крокового методу

при вказаних вище припущеннях.

Нехай Et - спектральна функщя оператора А, а стк = ak(t) =

= (EtxkJ xk) - функщя розподшу вектора хк.

Позначимо через Ек множину точок росту функцп сгк , що

належать в1др1зку fm , 1], а через тг5 (t, u0) многочлен В1д t степе-

ня s, що найменше вщхиляеться В1д нуля на множит Г0 i нормо-

ваний умовою 7cs (т, u0) = 1. Покладаемо

Ps (uo) = тах 1uo) I > = min Е0 , А." = шах 20. telo

Нехай Н(1) - власний шдпроепр оператора А, який вщповвдае власному значению т. Розкладаемо вектор и0 на ортогональш складов1 u0 = u0(1) + u0(2), u0(1) е H(I>, u0(2) X H(U i утворимо вектор Щ = uo(1) + Ps ("о) u0<2'.

Теорема 2.4.1. Якщо u0 е ?'i та Цд < m , то

Mi - m < I Ps(UQ)

Mo - ш

I |ü.

o|| /

<pl(u0)^i-\ _ Mo

(3)

3 оцшки (3) випливае, що

f^^pl(Uo)^ (4)

А., - Hj X. - ц0

Поатпдовне застосування nepiBHOCTi (4) дас

f^<p|k(u0)^, к = 1,2,., X. - цк X. - р0

тобто послщовюстЬ рк зб^гасться до ш принайми! 3i швидгастю геометрично! nporpecil ¡з знаменником р|(ио)- Ощнка (4)

непокращувана в тому розумшт, що коли р < sup ps (u0), то

U.)

M-i ~ m > р2 Цц ~ ш к. - Hj к- - Ро

для деякого початкового наближення и0 з р0 < m . Однак, якщо на початкове наближення накласти додатков1 обмеження, припустивши, наприклад, що значения р0 або фшсоване, то ощнка (4)

може бути полшшена. При цьому оцшка ——— <

N2

Ps(uo) 1

1 яка

iu

oil

п

До - m

випливае з HepinHocTi (3) залишаеться непокращуваною, Точшше, в § 2.4 доведена

Теорема 2.4.2. Пехай Н - скшченноьпркий npocrip. Якщо dim Н > s+2, то для будь-якого числа р. (ш < р < m ) ¡снус початкове наближення и0 (яке залежить вщ ц) таке, що pi = р /

/ л2 Ps("o)

р0 - m

В § 2.5 дослщжуеться асимптотична поведшка ¡теращйних параметров s-крокового методу. Доведене сл1дуюче твердження.

Теорема 2.5. Якщо u0 е i р0 < m , то iснують граничш iтеращйт параметра

а\ = lim ccj2k+v\ i = 0, 1, ... , s; v = 0, 1,

k—>oc

як] залежать вщ початкового наближення.

Таким чином, s-кроковий метод при дпшкпзацп вщношення Релея с, як i при мпш/пзацй квадратичного функцюнала, асимп-

тотично лшшним, а процес, складений з двох послщовних 1терацш з-крокового методу, - асимптотично стацюнарним.

В §2.6 вивчаеться асимптотична поведшка нормованих град1ент1в ук = 7к/||гк{| Б-крокового методу. Факт ¡снування граничних ¡терашйних параметров з-крокового методу дозволив в цьому параграф! поширити результата Екейка та Форсайта на випадок функцюнала Релея, заданого на пльбертовому простор!.

Структура § 2.6 аналопчна до структури § 1.6. В першому пункт1 отримаш аналоги результата Екейка та Форсайта в термшах функцш розпод1лу нормованих град!ент1в. В другому пушт отримаш аналоги вказаних результата в термшах граничних вектор!в послщовност1 нормованих град1ент1в, припускаючи, що ця послщовшсть компактна. В третьому пункт! знайден] умови компактносп поатдовноеп ук. Використовуючи щ умови, зокрема, повшстю розв'язане питания про зб1жшсть посл1довност1 нормованих град!ент!в однокрокового методу по парних (непарних) ¿терацшх.

Спираючись на результати досл1Ждень асимптотично! пове-дшки нормованих град^егтв з-крокового методу, в § 2.7 доведена

. I Ик+1 ~~ 111 , „ , ] Зб1ЖН1СТЬ ПОСЛ1ДОВНОСТ1 {—й-, к = 0,1,... ЯКЩО тшьки

I Рк - т )

и0 б и0(1) ф 0 (и0а) - ортогональна проекщя вектора и0 на власний тдпростзр Н(1) оператора А)..

Цей факт дозволив визначити асимптотичну швидккть зб1жност1 Б-крокового методу, як сл!дуючу функщю вщ початко-вого наближення:

^и0) =

0, и^ = 0,

-0.5 1п Ит - Ш , и1«1' * 0, и0

к->сс ^к - т

оо. и(о' * 0, и0 е 7С

Головним завданням §2.7 е вщшукання îctotho! (за Mipoio Лебега) области значень асимптотично! швидкост! збтжноет! s-крокового методу в сюнченном1рному npocTopi. Нехай H - скшченном1рний npocrip. Тод1

sp(A) = {?ц, ... , Xn}, m = 1, < ... <Хп = 1, Х2 = m". Позначимо через Ttj(t) многочлен степени i, що найменш В1дхи-лясться в1д нуля на множит - , та нормований умовою ^¡(Ài) = 1, а через р, = шах |я^Л:)-| - величину вщхилення. В §2.7

)=2, ... ,п 1

визначеш îctothî мшмум та максимум функцп V(u0) вщносно Mipn Лебега S, що задана на одиничшй сфер1 простору Н. Теорема 2.7.2. Якщоп > 2s+2, то

vrai infV(u0) — - in ps, vrai sup V(u0) = - 0.5 in p2S вщносно лебеговоi Mipn Э.

В po3fllni 3 вивчаеться неявний s-кроковий метод найшвид-Kiiuoro спуску (скорочено: s-кроковий метод) при знаходженш найменшого власного значения i в1Дповщного власного вектора узагальнено1 задач! на власш значения Mu = A.Lu в дшсному гшьбертовому npocTopi H. Припускаемо, що

а) оператори M: Dм -> H та L: 1\ —> H лшшш самоспряжет та додатно визначеш з ипльними в H областями визначення D^ i Di, причому j e D^ ;

б) будь-яка множина, обмежена в енергетичному npocTopi HJi( компактна в енергетичному npocTopi HL.

За цих припущень пучок оператор1в (M, L) мае чисто точковий спектр 0 < X] < Х2 < ... , а власш вектори утворюють ортогональний базис у просторах Нм та HL.

Вщшукання Âi та в1дповвдного власного вектора зводиться до

lu!';.

MiHiMi3au,iï узагальненого вщношення Релея ц(и) = :—~ на

№

простор! Нм. Для .упшкцзацп функщонала ц(и) заетосовуеться неявний г-кроковий метод (вдонтимо, що .\пшм1зац1я функщонала и(и) за допомогою явного з-крокового методу в нескшченномфному простор! не можлива, осгальки тод1 оператор не обмежений).

Неявний з-кроковий метод В1др1зняеться В1д явного тим, що використовуе допом!жний лнпйний самоспряжений 1 додатно визначений оператор В: I.\ -> Н, подгний до оператора М, тобто ТУц = 0}Л. Послщовш наближення неявного з-крокового методу утворюються за правилом:

£af>A'kuk, k = 0, 1, ... , (5)

1=0

де u0 - довшьний вектор з Z)M (|u0|L— 1), оператор Ak = В_1(М - pkL), pk = а и-ерацшш параметри {a-k\ i = 0, 1,

... , s} надають мшмуму норм1 ]|uk+1JM за умови Juk+1||L= 1.

В1дносно швидкост! збшшосп неявного s-крокового метода в § 3.2 доведена

Теорема 3.2. Якщо < Хг, то послщовтсть ;.ik, яга лородж-уеться %-кроковим методом, зб/гаеться до Х\ лринаймт зi швидюстю геометрично! nporpecii i для будь-якото к = 0, 1, ... мають мюце оцшки

цк+1 - < шах {0.5(цк - Х|) - 0.5Xh рк(цк - Xi)}, ^k ~ h IL _ „(Dil2 Mk ~

lluk - utl < ^-f-, |uk - u^||M< P- X.2 де pk=l-dkl dk ~ , = VW-^HÄ1

i2

Hl X2-Xl' " k Им Х2-Хг '

v2(l + 2qk)X1Xi '

ик(1) " ортогональна проекция в простор! Нь вектора ик на власний П1дпрост1р, вщповщний власному значению X.].

Бьльш детальне вивченнл послщовностг цк показуе, що поведшка 1терац:йного процесу (5) ¡стотно в1др1зняеться нав1ть в ск!нченном1рному простор! вщ поведшки ггерацШних процес!в, що досл1джувалися в попередшх розд1лах.

Так, для будь-якого номера к можна вказати оператори М, Ь, В та початкове наближення и0 тага, що и.к., ф >ч, цк= "К\. До того ж, виявилося, що для деяких початкових наближень цк * Хи к = О, 1,... , але посл1довшсть р.к зб!гаеться до /.) суперлшшно. Ц! обставини вимагали нових тдход1в до вивчення Е-крокового методу. В першу чергу необх!дно було описати можливу пове-дшку посл!довност! ик. Використовуючи апроксимащю функцю-нала ц(и) - допом!жним квадратичним функцюналом

Г (и) = ((М - Я]Ь)и, и), в §3.3 доведене слщуюче твердження:

Теорема 3.3. Нехай и0 - довшьне початкове наближення, а цк - послщовтсть, що породжуеться е-кроковим методом. Якщо ц0 < /.о, то:

1) або для деякого номера к цк = ,

2) або для будь-якого е > 0 Нт ———— = О,

3) або ¡с ну с границя Нт ———— > О

к->ю цк -

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

В §3.4 вивчена асимптотична поведшка !терацшних пара-метр!в э-крокового метода.

Теорема 3.4. Якщо послщовтсть (рк, ик) мае властивгсть майже лШйност!. то юнують гранична iтерацШш параметри а.У = lim aj2k+v), i = 0, 1.....s; v = 0, 1, от" = от1 = l,

к—юо

яш залежать вщ початкового наближення,

Позначимо wk = Akuk, А = B"l(M - XiL). В § 3.5 дослщ-жуеться асимтотична поведшка нормованих град!ент1в Ук = wk/||wkl!B припускаючи, що послщовшсть (дк, ик) мае влас-тивють майже лпшшость Отримаш аналоги результатов Екейка та Форсайта як в термшах функщй розподшу, так i в термшах граничних вектор1в послщовносп ук. Зокрема отримана оцшка

lim —— < шах | jcs(t) де 2 = sp(A)\{0}, rcs(t) - многочлен k-+Ki Pk — A.J t<=Z

степеня s, що найменше вщхиляеться вщ нуля на множит S та нормований умовою л:5(0) = 1.

Зазначимо, що результата роздшу 3 легко поширюються на випадок натвобмежених самоспряжених оператор1в М.

В розд!л1 4 дослщжуються s-Kp0K0Bi методи М1ШМ1зацп сильно опуклих функд1онал!в в гшьбертовому npocTopi.

Позначимо через F(u) дв!ч1 неперервно диференщйовний за Фреше сильно опуклий дгйсний функцюнал, заданий на дшсному ильбертовому npocTopi Н. Для вщщукашш точки мппмуму и функщонала F(u) використаемо s-кроковий метод спряжених rpaflieHTiB, кожна ¿теращя якого являс собою s крогав методу спряжених rpaflieHTiB Полака-Риб'ера. Перехщ ßifl k-ro наближення ulk) до ulk l), k = 0, 1 , ... , здшснюеться за обчислювальною схемою:

а) початкове присвоювання: u0(k) = u(k), h0(k) = g0(k) = -F'(u0(k)).

б) для i = 0, 1, ... , s-1 виконуються дп 1) - 4):

1) якщо g,<k) = 0, то покладемо л.(к| = 0, шакше число л.1

(к)

е точкою мипмуму функцп Р(и/к) + ХЬ/к)) В1д змшно! X;

2) покладемо и^^и/10 +

3) обчислимо й^1! = -Г'(и|к)]),

/„(к) _ „(к) (к) ч

(ёт ё; .61+1) „(к)

,, .....2 *

О,

4) покладаемо = + у,(к) Ь.'

ч (к+1)

в) покладаемо и*

(к) ч (к).

В §4.2 вивчений можливий характер зб1Жност! 5-крокового методу спряжених град1ент1в. Розвиваючи пщхщ розд1лу 3 показано, що цей метод може збн-атися або за скшченне число гаер а-цш, або суперлшшно, або майже лшшно. Точшше, припускаючи, що операторнозначна функщя Р"(и) задовольняс умов1 Лшшица, доведений такий результат:

Теорема 4.2. Нехай и0 - довтьне початкове наближення, а

(к!

и - посл1довн1сть, що породжуеться ъ-кроковим методом спряжених град1СНТ1в. Тод1

1) або для деякого номера к и(к) = и ;

2) або послщовност!

к = 0, 1, ..

обмежет;

3) або юнус границя

Щоб довести це твердження послщовшсть и'к> апроксимува-' лася послщовними наближеннями s-крокового методу, який застосовувався до квадратичного функцшнала

f(u) = 0.5 (А(и - и*), и - и*), де А = F"(u*). Позначимо через u(k,1) перше наближення s-крокового методу з початковим наближенням u(k), який застосовувався до функцюнала f(u). Доведена така оцшка (лема 4.2.2):

|u(k+1) _ u(k,i)|| < к |u(k, _ u-||2; k = 0, 1, ... , (7)

де число к: не залежмть вщ г/Ч Вектор u(k'l) можна подати у вигляд1

u(k,i) = u(k) + ¿a(k)AiZk; Zk = и(Ю . и-. (8)

i=l

g

Якщо dim Н < s, то вектори zk, Azk , .... A zk лшшно залежш, тому u(k'1! = u , к = 0, 1, .... 3 оцшки (7) випливае, що в цьому випадку послщовшсть ulk) збнаеться до и принаймш з квадратичною швидшстю. Це - вщомий результат Коена.

Шд ¡.терацшними параметрами s-крокового методу спряже-них град1«тв на k-iti п-ерацн будемо розулнти хоефщ!енти розкладу {a-k), i = 1, ... , s} вектора и(кд) за формулою (8). В § 4.3

доведене шнування граничних ¿терацШних паракетрш s-крокового

(к)

методу спряжених град1ентш при умов1, що послщовшсть и майже лшшна (тобто, ¡снуе границя (6)).

Теорема 4.3. Якщо послщовшсть и(к) майже лшшна, то iснують граничн! iтерацШт параметри

< = lim apk+v), i = 1, ... , s; v = 0, 1,

к->oo

як! залежать В1Д початкового наближення.

В §4.4 дослщжуеться асимптотична поведшка нормованих

похибок wk = 2к/|2к||, к = 0,1, ... , Б-крокового методу спряжених

(к! - •

град1снтщ у припущенш, що посл1довшсть и маиже лш1ина. Отримаш аналоги результатов Екейка та Форсайта як в терминах функщй розподшу, так 1 в термшах граничних вектор1в послщо-вност! Зокрема, показано, що

.(и^-ф-)

Пт , / —гтг - тах 1 I,

к—>оо

де л^) - многочлен степеня б, який найменш вщхилясться вщ нуля на спектр! оператора А та нормований умовою 71й(0) = 1.

Зазначимо, що обчислювальна схема Полака-Риб'ера, яка записана в енергетичному простор! Нв (В - лшШний самоспряжений та додат.чо визначений оператор в простор! Н), породжуе неявний э-кроковий метод спряжених град!снт!в, отже, результата розд!лу 4 в!рш ! для цього методу.

В роздьтп 5 вводиться поняття комб!нованих ¡терацшних метод!в вар1ащйного типу ! проводиться 1х теоретичний анал!з на основ! осереднених швидкостей зб!жност!.

Нехай А - лшшний самоспряжений обмежений оператор з границями спектра 0 < ш < М, що Д1е в дшсному пльбертовому простор! Н. Поашдовш наближення Б-крокового а-процесу до розв'язку и р1вняння Аи = { задаються формулою

= и(ка) + I: у !а)(4а))А;-Ча) - к = 0. 1, ... ¡=1

де а, з - вщповщно дшсне та натуральне числа, ида)- дов!льне початкове наближення, = Аи^ - I - нев'язка, а дшсш числа { у-™'^^'), 1 = 1, ... , э} вибираються з умови мш1муму величини

и1иА) = !К"Л - и*Ца+1 = (Авт1(и£Д - и), и£Д - и).

При э=1 отримуемо а-процес, при а = ОД - це э-кроков1 методи в1дпов1Дно найшвидккного спуску та мшимальних невязок

Зафжсуемо дв! гшслщовноеп: постдовшсть Б = (зь з2, ... ) натуральних чисел та посладовтсть дШсних чисел Л — (а,, (и, ... )

Пщ (Б, А) - комбшованим ¿терацШним методом вар1ащйного типу будемо розушти ¡терацшний процес, к-та ¡теращя якого здшснюеться за допомогою зк-крокового ак-процесу.

Зокрема, комбшований метод з Б = Б121 = (зь з2, в]., б,, ... ), Л = Лс2) = (аь ал, аь оц, ... ) (тобто, з посл1довностями пар ь~], оо та аь сь вщповщно) будемо називати двохступшчатим.

Нехай и0, и ... - ¡терацшна послщовшсть, породжена (Б, А) -методом, а гк = Аик - 1 Тод1

гк 13к - г0> К - 1, ... ,

де '4а>: Н->Н - нелшшний оператор, що задаеться формулою

Т^>2 = 2 + 1у1а,(2) А12.

¡=1

Величину

Кк = йк(АДЛД) = - -У—*-ЬЛк, к = 1, 2, ...

назвемо (за термшолопею Г.1. Марчука та Ю.О. Кузнецова) осе-редненою швидгастю зб1жност1 (Б, А)-методу за к ¡терацш, а величину

R„ = R„(A,S,A) = lim inf Rk(A,S,A,b)

к-» ос

назвемо осередненою асимтотичною швидшстю 3oi>KHûCTi. Тут

ÀeR, а )|Т||. = sup ||Tz||aâ-i ||z|_1 - норма оператора T. ' O.ZeH A^-1

В §5.2 отримаш непокращуваш оцшки знизу для Rk.

Теорема 5.2. Якщо inf Л > X, то (S, Л)-метод збп-асться i

Rk > - In (1 - ш/М), k = 1, 2, ... , оо.

Звщси, зокрема випливае, що (S, Л)-метод збшаеться прина-

ïîMHi 3i швидюстю геометрично! nporpeciï.

В §5.3 отримаш оцшки Rk. зверху для двостушнчатого методу

(S,2), Л(2)) в скшченном1рному простор!. Нехай Jts(t) = 1+ + ... +

+ Tcsts - многочлен степени s = st + s2, що найменш ввдхмляеться

вщ нуля на cneKTpi оператора A, a ps - величина ввдхилення.

Теорема 5.3. Якщо dim H > s, то V XeR

R2k < R„ < -s'1 In ps , k = 1, 2, ... (9)

Зокрема, для двостутнчатого градиентного спуску (б! = б2 = 1, = 1, а2 = 0, з = 2) маемо

И2к < Б,, < -0.5 1п р2. Оцшка (9) дозволяе пор1внювати двостушнчатий метод з з-кроковим методом. Нехай б = бх + э2, аеЯ . 3 теореми 1.4.1

випливае, що ||т|а)| < р5, тому (Тз°° П < , к = 1, 2, ... . Якщо

а На

п > б, то з теореми 1.4.2 випливае кнування вектора т. ф 0 такого,

що

fea))kzi = Ps||zj|Aa-l , k = 1, 2.....Тому при п > s

' IA11"1

(т«а,)к! = р| , к = 1, 2..........(10)

I ! а

Розглянемо Б-кроковий а-процес як комбшований метод з Б11' = (б, б, ... ), Д.(1) = (а, а, ... ); з р1вност1 (10) отримуемо, що

йк(А, Б11', Д(1), а) = Е^А, Б11', Да)) = -б"1 1п р5, к=1, 2, ... (11)

Пор1вшоючи оцшки (9), (11) можна зробити висновок про те, що б-кроковий метод з б — б: + э, кращий (з точки зору осереднених швидкостей зб1жност1) за двостушнчатий метод. Зокрема, двокроковий метод найшвидюшого спуску (або м1шма-льних нев'язок) кращий за двоступшчатий град1ентний спуск.

В додатку на конкретних прикладах показана можлив1сть використання асимптотичних властивостей Б-крокових метод1в для прискорення !х збЬкност!, а також при формуванш апостерюрних критерпв IX закшчення.

Шдсумки та основт результати робот.

В дисертащлн1й робот1 побудована асимптотична теорхя з-крокових 1теращ.йних метод1в вар1ащ.йного типу, досл!джена швидюсть зб1яшост1 комбхнованих 1терац:1йних метод1в вар1а-ц:шного типу, розроблен1 на основ1 асимптотично! теорхЛ при-йоми прискорекня 5-крокових метод1в вар1ац1иного типу.

Основнх результата роботи:

1. Отриман! умови стабШзацЗЛ та непокращуванх оценки швидкост! зб1лшостх з-крокового методу розв'язування лх-н1йних операторних рхвнянь та 5-крокового методу Ланцоша.

2. Дослдаена асимптотична поведхнка хтеравдйних па-раметр1в э-кроксвих методхв вархацхйного типу та доведено та-кий аналог гШотези Форсайта: якщо за даногс початкового наближення Б-кроковий метод не стабШзуеться 1 не зб1гаеться суперлх.н1йно, то 1снують граничнх хтерацхйнх параметри методу по парних (непарних) 1теращях. Отже, за вказаних умов, 5-кроковий метод е асимптотично лШйним, а хтерацхйний пронес, що складаеться з двох його послхдовних 1терац1й,- асимптотично стацхонарним.

о. Вивченх асимптотичш вапрями похибки Б-крокового методу вар1ац1йного типу та отримаш аналоги результайв Екейка та Форсайта.

4. Визначен1 хстотнх област1 значень асимптотичних швидкостей зб1лшосп г-крокового вар1ац!йного методу розв'язування лШйних операторних ргвнянь та 2-крокового методу Ланцоша.

5. Отриманх двосторонн! оЩнки осереднених швидкостей збхжностх комбхнованих хтеращйних метод1в вар1аихйного типу.

Основт результат дисертацИ опублжоват в працях.

1. Жук П.Ф. Об асимптотических свойствах метода наискорейшего спуска в задачах на собственные значения// Ж. вычисл. матем. и матем. физики. 1981. Т.21. №2. С.271-285.

2. Жук П.Ф. Асимптотические свойства s-шагового метода скорейшего спуска//Ж. вычисл. матем. и матем. физики. 1982. Т.22. №2. С.269-279.

3. Жук П.Ф. Об одной гипотезе Дж.Форсайта//Труды 3 Респ. конференции "Вычислительная математика в современном научно-техническом прогрессе", Канев, 1982. С.49

4. Жук П.Ф., Приказчиков В.Г. Эффективная оценка сходимости неявного итерационного метода в задачах на собственные зна-чения//Диффер. уравн. 1982. Т.18. №7. С.1197-1202.

5. Жук П.Ф., Бондаренко JI.H. Об одной гипотезе Дж.Форсайта // Математический сборник. 1983. Т.121. №4. С.435-453.

6. Жук П.Ф. Асимптотическая скорость сходимости метода наискорейшего спуска в задачах на собственные значения //Ж. вычисл. матем. и матем. физики. 1984. Т.24. №4. С.605-607.

7. Гаврилюк И.П., Жук П.Ф., Бондаренко JI.H. Решение нелинейной начально-краевой задачи для нелинейного параболического уравнения второго порядка методом сеток. / / Вычисл. и прикл. математика. Респуб. межвед. науч. сб. Киев. 1988. №65. С.34-46.

8. Бондаренко Л.Н., Жук П.Ф. Комбинированные итерационные методы вариационного типа / /Ж. вычисл. матем. и матем. физики. 1988. Т.28. №9. С.1283-1296.

9. Жук П.Ф. Асимптотическое поведение трехшагового метода скорейшего спуска // Депонировано в ВИНИТИ 17.10.91. № 4004-В91. 13 С.

10. Жук П.Ф. Асимптотическое поведение трехшагового метода скорейшего спуска // Ж. вычисл. матем. и матем. физики. 1992. Т.32. №3. С.477-478.

11. Жук П.Ф. Асимптотическое поведение s-шагового метода наискорейшего спуска в задачах на собственные значения в гильбертовом пространстве // Математический сборник. 1993. Т.184. №12. C.87-L22.

12. Жук П.Ф. Асимптотическое поведение s-шагового метода наискорейшего спуска при минимизации квадратичного функционала в гильбертовом пространстве// Ж. вычисл. матем. и матем. физики. 1995. Т.35. № 2. С.163-177.

13. Zhuk P.F. The asymptotic behaviour of the three-step method of steepest descent// Comput. Maths. Math. Phys. 1992. V.32. №3. P.419-420.

14. Zhuk P.F. The asymptotic behaviour of the s-step method of steepest descent for minimizing a quadratic functional in Hilbert space//Comput. Maths. Math. Phys. 1995. V.35. №2. P.127-137.

Особистий вклад Bci результата, що складають основний 3mict дисертацшно! роботи, отримаш автором самостшно. В публшащях, яга написаш в cnisaBTopcTBi, дисертантов1 належить:

в робот1 [4] - результата §1, в якому дослщжена асимпто-тична поведшка неявного методу найшвидгашого спуску; в робот1 [5] - yci результата, KpiM теореми з §1; в poooTi [7] - побудова та чисельна реал1защя скшченно -р13ницево1 схеми;

в po6oTi {8] - yci результата, KpiM легли 2.

Zhuk P.F. Multistep iterational methods of variation type. Thesis for a doctor's degree of physical ana mathematical sciences on speciality 01.01.07 - computational mathematics. Shevchenko Kiev University. Kiev, 1996.

The dissertation maintained studies multistep iterational methods of variation type. The results of research were published in 14 papers. The asymptotic theory of the s-step iterational methods of variation type in Hilbert space was created. The estimates of the rate of convergence of combination iterational methods of variation type were obtained.

Жук П.Ф. Многошаговые итерационные методы вариационного типа. Диссертация на соискание ученой степени доктора физико-математических наук по специальности 01.01.О? - вычислительная математика. Киевский университет имени Тараса Шевченко. Киев, 1996 г.

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

KjimoBi слова: 1терац1йн1 методи вар1ац!йного типу, швидюстъ 36ia®ocTi, асимптотачна повед1нка, фунгадонал, оператор, Пльбертовий npocTip, iTepauiHHi параметри, власн1 значения, базис, граничний вектор.