ЛЬВІВСЬКИЙ ДЕРЖАВНИЙ УНІВЕРСИТЕТ
імені ІВАНА ФРАНКА

Петрович
Роман Йосипович

УДК 519.6

АГРЕГАТИВНО-ІТЕРАТИВНІ АЛГОРИТМИ
ДЛЯ ЛІНІЙНИХ РІВНЯНЬ
З ОБМЕЖЕНИМ

И ОПЕРАТОРАМИ

Спеціальність 01.01.07 - обчислювальна математика

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

ЛЬВІВ-1999

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

Робота виконана в Державному університеті "Львівська політехніка" Міністерства освіти України.

Науковий керівник - | д. ф.-м. н., проф. Слоньовський Роман Володимирович, Державний університет “Львівська політехніка“, професор кафедри прикладної математики.

Офіційні опоненти: | д. ф.-м. н., проф. Цегелик Григорій Григорійович, Львівський державний університет імені Івана Франка, завідувач кафедри обчислювальної математики;

д. ф.-м. н., проф., Сявавко Мар’ян Степанович, Львівський державний аграрний університет, завідувач кафедри економічної кібернетики.

Провідна установа: | Інститут кібернетики ім.В.М.Глушкова НАН України, відділ чисельного програмного забезпечення і розв’язування задач, м. Київ.

Захист відбудеться 21..жовтня........... 1999р. о .1520.... год. на засіданні спеціалізованої вченої ради Д 35.051.07 у Львівському державному університеті ім. І.Франка за адресою:

290602, м. Львів, вул.Університетська,1, ЛДУ, ауд. 377.

З дисертацією можна ознайомитись в науковій бібліотеці Львівського державного університету імені Івана Франка (вул. Драгоманова, 5).

Автореферат розісланий 18 вересня 1999р.

Вчений секретар спеціалізованої вченої ради | Микитюк Я.В.

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

Досліджені в дисертації алгоритми вписуються в клас методів ітеративного агрегування, які виникли в шістдесяті роки. Ці методи досліджували Л.М.Дудкін, Е.Б.Єршов, Б.А.Щенніков, Л.А.Хіздер, І.М.Ляшенко, М.В.Калініна, В.Я.Стеценко, А.А.Бабаджанян. Як для загальних багатопараметричних алгоритмів так і для однопараметричного варіанту методу ітеративного агрегувания для систем ліннійних рівнянь вигляду одним з основних обмежень, які фігурують в цих роботах, є вимога про знакосталість компонент матриці A та вектора b. Серед інших обмежень, які у цих дослідженнях гарантують збіжність методів, фігурує також вимога, щоб норма матриці A була меншою за 1/2 або й за 1/3. Для однопараметричного випадку М.А.Красносельским, Є.А.Ліфшицьом і А.В.Островським (див. Красносельский М.А., Лифшиц Е.А., Соболев А.В. Позитивные линейные системы. – М.: Наука, 1985.) отримано умови збіжності, які містять вимогу, щоб спектральний радіус матриці А був менший за одиницю при додатніх компонентах матриці A та вектора b. В тій же книжці зазначено, що на практиці однопараметричний варіант методу ітеративного агрегування “збігається й у ряді випадків, зокрема якщо спектральний радіус матриці системи A більший за одиницю. Для багатопараметричного варіанту методу умови збіжності невідомі“. В 1990-1995-х роках Б.А.Шуваром запропонована методика побудови і дослідження агрегативно-ітеративних методів, яка не вимагає знакосталості компонент матриці A і вектора b за припущень, які не обов’язково містять вимогу, щоб спектральний радіус матриці A був меншим за одиницю.Отже, дослідження умов збіжності методів ітеративного агрегування з теоретичного і практичного погляду є актуальною задачею.

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

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

-

-

-

-

-

На захист виносяться такі результати:

1.

1.

1.

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

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

Апробація результатів дисертації. Основні результати, одержані в дисертаційній роботі, доповідалися на семінарі "Числові методи для диференціальних і інтегральних рівнянь" (ДУ "Львівська політехніка"), на всеукраїнській науковій конференції "Розробка та застосування математичних методів в науково-технічних дослідженнях", присвяченій 70-річчю від дня народження професора П.С.Казімірського (5-7 жовтня 1995р.), на Другій Українській конференції з автоматичного керування "Автоматика-95" 26-30 вересня 1995р., на міжнародній науково-технічній конференції "Сучасні проблеми автоматизованої розробки і виробництва радіоелектронних засобів, застосування засобів зв'язку та підготовки інженерних кадрів" (27 лютого - 3 березня 1996р.), на Українській конференції "Моделирование и исследование устойчивости систем" 20-24 травня 1996р., Київ, на науковій конференції "Нелінійні проблеми аналізу" Івано-Франківськ, 1996.

Публікації. Результати, що включені до дисертації, опубліковані в 15 роботах, в тому числі у трьох статтях, які надруковані у виданнях, що входять в перелік ВАКу, одному препринті, трьох депонованих статтях, восьми тезах доповідей на конференціях.

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

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

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

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

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

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

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

, (1)

де (i,j=1,...,N) - квадратна матриця і . Вважаємо, що для власних чисел матриці A справджуються співвідношення

, . (2)

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

. (3)

Запровадимо нове невідоме і до системи (1) приєднаємо рівняння

. (4)

Запровадимо до розгляду множину

. (5)

Будуємо ітераційний процес

, (6)

, (7)

де , , . Ітераційний процес (6),(7) в просторі можна подати у вигляді

, (8)

де , , .

Позначимо , . Алгоритм (6), (7), матрицю переходу C та множину початкових наближень (5) пов'язують такі властивості:

1.

1.

, (9)

то є розв'язком системи (1).

1.

1.

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

Теорема 1. Нехай дійсна матриця має спектральне представлення і для її власних значень справджуються нерівності

,

Тоді, якщо початкове наближення вибране із множини (5), то ітераційний процес (6), (7) збігається до розв'язку системи (1),(4), причому

. (10)

Зв'язок між власними значеннями матриць A і C можна встановити, подавши C у вигляді

.

Теореми Бауера - Файка про спектр суми матриць дозволяють отримати наступну оцінку.

Теорема 2. Нехай для власних значень матриці A справджуються співвідношення (2), а ітераційні параметри у методі (6), (7) вибрані за формулами , . Якщо для векторів , і числа справджується нерівність

,

де , - діагональна матриця і початкове наближення вибране із множини (5), то агрегативно-ітеративний алгоритм (6), (7) збігається.

Власні значення матриці C , можна розглядати як збурені власні значення , матриці A. Згідно твердження теореми 1 збіжність алгоритму (6), (7) залежить від власного значення матриці C і не залежить від . Тому можна говорити, що однопараметричний агрегативно-ітеративний алгоритм (6), (7) усуває вплив найбільшого за величиною модуля власного значення матриці A на збіжність ітераційного процесу.

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

(11)

Вважаємо також заданими числа , (i=1,...m) і вектори (i=1,...,m) та (i=1, ...,m), для яких справджуються співвідношення

Матрицю A подамо у вигляді (3), де . Утворимо матрицю розміру , стовпцями якої є вектори (i=1,...,m), матрицю та матрицю розміру , стовпцями якої є вектори (i=1,...,m). Запровадимо нові невідомі ,...,. Позначивши , доповнимо систему (1) рівнянням

. (12)

Запровадимо до розгляду множину

. (13)

Запропоновано ітераційний процес

, (14)

, (15)

де - матриця розміру , a - матриця розміру , і . Ітераційний процес (14),(15) у просторі можна подати у вигляді

, (16)

де , , - вектор з нульовими компонентами,

. (17)

Теорема 3. Нехай матриця C має спектральне представлення

(18)

і для її власних чисел справджуються нерівності

,

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

. (19)

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

Теорема 4. Нехай у агрегативно-ітеративному алгоритмі (14), (15) параметри і вибрано

, , (20)

де - нульова матриця розміру , а матриця має спектральне представлення (18). Тоді, якщо спектральний радіус матриці

(21)

менший за одиницю, то ітераційний процес (14), (15) за умови вибору початкового наближення із (13) збігається.

Теорема 4 дає можливість оцінити , оскільки .

В підрозділі 2.3 досліджуються багатократні агрегативно-ітеративні алгоритми для систем вигляду (1), матриці яких мають кратні власні значення. Нехай матрицю A можна подати у вигляді

, (22)

- жорданова клітка розміру , , p - число жорданових кліток. Вважаємо відомими , - наближення до власних чисел матриці A, що відповідають жордановим кліткам , (i=1,...,k, k<p) матриці A у представленні (22). Крім того, вважаємо заданими вектори - деякі наближення до власних і кореневих векторів матриці A, що утворюють перших m стовпців матриці V у (22), а також вектори - наближення до векторів, що утворюють перші m рядків матриці у (22). Для векторів , (i,j=1,...,m) справджуються рівності . Через позначимо матрицю розміру , стовпцями якої є вектори (i=1,...,m), через - матрицю розміру , рядками якої є вектори , (i=1,...,m). Матрицю A подамо у вигляді (3), де , J - блочно-діагональна матриця розміру , утворена жордановими клітками . Запровадимо нові невідомі . Позначивши , доповнимо систему (1) рівнянням

. (23)

Запровадимо до розгляду множину

. (24)

Побудуємо ітераційний процес

, (25)

, (26)

де - матриця розміру , a - матриця розміру , i .

Ітераційний процес (25),(26) у просторі можна подати у вигляді

,

де, ,.

Теорема 5. Нехай для власних значень матриці C справджуються нерівності

,

Тоді, якщо початкове наближення вибране із множини (24), то ітераційний процес (25), (26) збігається до розв'язку системи (1),(23) і для кожного , , справджується оцінка

. (27)

В підрозділі 2.4 за допомогою схожої методики досліджуються багатократні агрегативно-ітеративні алгоритми, які дозволяють усунути вплив на збіжність ітераційного процесу комплексно-спряженої пари домінуючих власних значень, а також вплив кількох пар комплексно-спряжених власних значень матриці системи рівнянь (1). Розглядається випадок, коли дійсна матриця A має дійсні та комплексні власні значення. Тоді її можна подати у вигляді

(28)

- клітка розміру або . Якщо клітка є розміру, то вона містить дійсне власне число матриці A, якщо ж клітка є розміру , то, де - комплексні власні числа матриці A. Вважаємо відомими - наближення до власних чисел матриці A, що відповідають кліткам, (i=1,...,k, k<p) матриці A у представленні (28). Крім того, вважаємо заданими вектори - деякі наближення до векторів, що утворюють перших m стовпців матриці V у (28), а також вектори - наближення до векторів, що утворюють перші m рядків матриці у (28). Для векторів , (i,j=1,...,m) справджуються рівності. Через позначимо матрицю розміру, стовпцями якої є вектори (i=1,...,m), через - матрицю розміру, рядками якої є вектори, (i=1,...,m). Матрицю A подамо у вигляді (3), де, J - блочно-діагональна матриця розміру, утворена клітками. Запровадимо нові невідомі. Позначивши, доповнимо систему (1) рівнянням

. (29)

Запровадимо до розгляду множину

. (30)

Побудуємо ітераційний процес

, (31)

, (32)

де - матриця розміру , a - матриця розміру , i.

Ітераційний процес (31),(32) у просторі можна подати у вигляді

,

де, ,.

Теорема 6. Нехай для власних значень матриці C справджуються нерівності

Тоді, якщо початкове наближення вибране із множини (30), то ітераційний процес (31),(32) збігається до розв'язку системи (1),(29) і для кожного , , справджується оцінка

. (33)

В підрозділі 2.5 досліджується вплив похибок заокруглення на загальну похибку алгоритмів (6), (7) та (14), (15).

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

. (34)

Будь-який стаціонарний однокроковий ітераційний метод для системи (34) має вигляд

, (35)

де A - матриця переходу методу. Система рівнянь еквівалентна (34) в сенсі розв'язку. Шляхом застосування до неї алгоритмів, описаних в розділі 2, отримуються агрегативно - ітеративні аналоги відомих методів.

В підрозділі 3.1 побудований агрегативно - ітеративний аналог методу простої ітерації. Для системи лінійних алгебраїчних рівнянь (34), де B - позитивно визначена матриця розміру , , метод простої ітерації запишеться у вигляді (35), де , , M i m - оцінки найбільшого і найменшого власних значень матриці B, . Вважаємо заданими наближення до m власних чисел (i=1,...,m) і вектори (i=1,...,m) та (i=1,...,m), причому . Утворимо матрицю , а також матрицю розміру , стовпцями якої є вектори (i=1,...,m), матрицю , та матрицю розміру , стовпцями якої є (i=1,...,m). Застосувавши до (35) методику, описану в підрозділі 2.2 і вибравши ітераційні параметри (20), одержимо агрегативно-ітеративний аналог методу простої ітерації

, (36)

, (37)

де . Множина початкових наближень запишеться у вигляді

. (38)

Ітераційний процес (36),(37) у просторі можна подати у вигляді

, (39)

де , , .

Теорема 7. Якщо для власних чисел матриці C справджуються співвідношення , , то за умови вибору початкового наближення із множини (38) ітераційний процес (36), (37) збігається до розв'язку, і для кожного , , справджується оцінка

. (40)

Для випадку, коли матриця системи (34) є симетричною, отримані видозміни формули (36),(37) так, щоб перехідна матриця агрегативно-ітеративного алгоритму також була симетричною. Оцінка (40) у випадку реалізації симетричного варіанту алгоритму, набуває вигляду

. (41)

З (41) випливає така оцінка кількості ітерацій, необхідної для зменшення похибки в разів:

. (42)

Для звичайного методу простої ітерації замість (41) справджується оцінка

,

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

. (43)

В підрозділі 3.2 запропонований агрегативно-ітеративний аналог методу найшвидшого спуску. Суть алгоритму можна пояснити наступним чином:

1.

, (44)

знайшовши розв'язок якого отримуємо і розв'язок рівняння (34).

2. Матриця побудована так, що є відомими її m () власних значень і відповідних їм власних векторів .

3.

, (45)

де , - матриця розміру , стовпцями якої є (i=1,...,m).

4. До рівняння (44) застосовується метод найшвидшого спуску з вибором початкового наближення із множини (45).

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

, (46)

де i - відповідно мінімальне і максимальне власні числа матриці B, - початкове наближення.

Теорема 8. Нехай для рівняння (34) у просторі побудована система (44), де - симетрична позитивно визначена матриця, для власних значень якої справджується нерівності

,

, p+q=m. Якщо початкове наближення вибране із множини (45), то метод найшвидшого спуску, застосований до системи (44) у просторі , збігається до розв'язку , причому

.

Спосіб побудови матриці дозволяє в багатьох випадках зробити відношення більшим, ніж . Це забезпечує швидшу збіжність розглянутого тут алгоритму у порівнянні з методом найшвидшого спуску, застосованим до системи (34).

В підрозділі 3.3 запропонований агрегативно-ітеративний аналог чебишевського ітераційного методу. Використовуючи методику попереднього підрозділу побудуємо матрицю розміру і будемо розглядати систему лінійних алгебраїчних рівнянь (44). Для побудованої матриці відомі m власних значень а також m власних векторів , що їм відповідають. Утворимо матрицю , та матрицю розміру , стовпцями якої є (i=1,...,m). Запровадимо множину початкових наближень (45). Застосуємо до (44) чебишевський ітераційний метод з вибором початкових наближень із множини (45)

, , , (47)

де - певним чином вибраний корінь многочлена Чебишева.

Теорема 9. Нехай для власних чисел матриці справджуються співвідношення , , , p+q=m. Тоді агрегативно-ітеративний аналог чебишевського ітераційного методу (47) з вибором початкових наближень із множини початкових наближень (45) збігається до розв'язку і для похибки справджується оцінка

, (48)

де

, , , . (49)

Для кількості ітерацій справджується оцінка

, . (50)

В підрозділі 3.4 для систем лінійних алгебраїчних рівнянь (34) із симетричними і узгоджено впорядкованими матрицями запропонований агрегативно-ітеративний аналог методу послідовної верхньої релаксації. В матричному вигляді метод послідовної верхньої релаксації можна подати у вигляді

, (51)

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

Вважаємо заданими числа , (i=1,...,m) і вектори (i=1,...,m) та (i=1,...,m), причому . Утворимо матрицю , а також матрицю розміру , стовпцями якої є вектори (i=1,...,m), матрицю , та матрицю розміру , стовпцями якої є (i=1,...,m). Застосувавши до (51) результати підрозділу 2.2, одержимо агрегативно-ітеративний аналог методу послідовної верхньої релаксації

, (52)

, (53)

де . Множина початкових наближень приймає вигляд

(54)

Наведений один спосіб реалізації алгоритму (52),(53) з поетапним отриманням чисел , векторів та (i=1,...,m).

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

,

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

Тестовий приклад. Усталений розподіл температури в однорідній квадратній пластині зі сторонами довжини 1, на краях якої підтримуються постійні температури u=0 і u=1, задовольняє рівнянню Лапласа:

При кроку сітки рівному 1/33 розмірність отриманої системи рівнянь N=1024. Результати тестування наведені у таблицях 1-4. В першій лінійці кожної таблиці наводяться кількості ітерацій для відомих ітераційних методів (друга колонка) та для їх агрегативно-ітеративних аналогів певної кратності, вказаної у підзаголовку колонки (починаючи з третьої колонки). В наступній лінійці наводиться час в секундах, який виконувалась програма, що реалізувала відповідний алгоритм. В останній лінійці наводяться проценти, які складає час виконання агрегативно-ітеративного методу по відношенню до часу виконання його неагрегованого аналогу. Критерій припинення ітерацій та початкове наближення вибирались однаковими.

Таблиця 1
Результати розв'язування методом простої ітерації
та агрегативно-ітеративним аналогом методу простої ітерації |

Метод простих ітерацій | Агрегативно-ітеративний аналог методу простих ітерацій кратності m

m = 2 | m = 6 | m = 12 | m = 20 | m = 30

К-сть ітерацій | 316 | 111 | 98 | 53 | 48 | 31

Час виконання | 119,84 | 42,31 | 38,34 | 22,85 | 20,17 | 16,58

Процент | 100% | 35,3% | 32% | 19,1% | 16,9% | 13,8%

Таблиця 2
Результати розв'язування методом найшвидшого спуску та
агрегативно-ітеративним аналогом методу найшвидшого спуску |

Метод найшвидшого

спуску | Агрегативно-ітеративний аналог методу найшвидшого спуску кратності m

m = 2 | m = 4 | m = 12

К-сть ітерацій | 377 | 159 | 131 | 70

Час виконання | 280 | 128 | 117 | 79

Процент | 100% | 45,7% | 41,8% | 29,3%

Таблиця 3
Результати розв'язування чебишевським методом

та агрегативно-ітеративним аналогом чебишевського методу |

Чебишевський метод | Агрегативно-ітеративний аналог чебишевського методу кратності m

m = 2 | m = 4 | m = 12

К-сть ітерацій | 184 | 82 | 65 | 57

Час виконання | 69.37 | 44,57 | 30,64 | 38,28

Процент | 100% | 64,6% | 48,1% | 55,2%

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

Таблиця 4
Результати розв'язування методом послідовної верхньої релаксації та
агрегативно-ітеративним аналогом методу послідовної верхньої релаксації

| Метод ПВР | Агрегативно-ітеративний аналог методу ПВР кратності m

m = 1 | m = 2 | m = 3 | m = 6

К-сть ітерацій | 37 | 28 | 28 | 23 | 21

Час виконання | 14.94 | 12,19 | 12.58 | 10,71 | 10,8

Процент | 100% | 81,6% | 84,2% | 71,7% | 67,6%

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

, <1. (55)

Нехай задані , , , i=1,...m і справджуються співвідношення . Побудуємо проектори і подамо оператор A у вигляді (3), де . Запровадимо нові змінні ,,...,. Позначимо через вектор-стовпець . Позначимо через лінійний компактний оператор, що переводить довільний елемент в елемент за законом , і=1,...,m. Рівняння (1) занурюємо у ширший простір шляхом приєднання рівняння

. (56)

де , . Побудуємо лінійний компактний оператор , що переводить вектор в елемент за законом

, , i=1,...,m,

і оператор , для яких справджується .

Запровадимо до розгляду множину

. (57)

Запропоновано алгоритм

, (58)

. (59)

У просторі алгоритм (58), (59) можна подати у вигляді

,

де , , .

Теорема 10. Нехай лінійний компактний оператор має спектральне представлення

, (60)

- власні значення, - власні проектори оператора C і для його власних значень справджуються співвідношення

, <1. (61)

Тоді, якщо початкове наближення вибране з множини (57), то ітераційний процес (58), (59), збігається до розв'язку системи (1), (56), причому

, (62)

для всякого , і , де - розв'язок системи (1),(56).

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

Теорема 11. Нехай у агрегативно-ітеративному алгоритмі (58), (59) параметри і вибрано

, , (63)

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

, (64)

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

Теорема 11 дає можливість оцінити , оскільки .

ВИСНОВКИ

1.

1.

1.

1.

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

1. Петрович Р.Й., Шувар Б.А. Однопараметричний агрегативно-ітеративний алгоритм для систем лінійних алгебраїчних рівнянь // Вісник Державного університету "Львівська політехніка", сер. Прикладна математика. - Львів, 1996. - N 299. - С.180-183.

2. Петрович Р.Й. Параметризація методу найшвидшого спуску // Вісник Державного університету "Львівська політехніка", сер. Прикладна математика. - Львів, 1997. - N 320. - С.111-113.

3. Петрович Р.Й. Багатократний агрегативно-ітеративний алгоритм для систем лінійних алгебраїчних рівнянь // Вісник Державного університету "Львівська політехніка", сер. Прикладна математика. - Львів, 1996. - N 299. - С.183-185.

4. Петрович Р.Й. Про достатні умови збіжності деяких алгоритмів ітеративного агрегування. - Львів, 1996. - 43с. (Препр./ НАН України. І-нт прикл. проблем механіки і математики ім. Я.С.Підстригача; 3-96).

5. Петрович Р.Й., Шувар Б.А. Метод багатократного ітеративного агрегування для лінійних рівнянь з обмеженими операторами. // "Математика та психологія у педагогічній системі "Технічний університет". Збірник статей по матеріалах 1-ї Міжнародної науково-практичної конференції, Ч1. Одеса, 1996. - C.108-109.

6. Петрович Р.Й., Шувар Б.А. Агрегативно-ітеративні алгоритми для розв'язування рівнянь в банахових просторах // Всеукраїнська наукова конференція "Розробка та застосування математичних методів в науково-технічних дослідженнях" присвячена 70-річчю від дня народження професора П.С. Казімірського (5-7 жовтня 1995р) Тези доповідей Ч 3, Львів, 1995, C.142-143.

7. Петрович Р.Й. Метод багатократного ітеративного агрегування для систем лінійних алгебраїчних рівнянь // Українська конференція "Моделирование и исследование устойчивости систем". Тезисы докладов конференции.20-24 мая 1996г., Київ, 1996. - С.107.

Петрович Р.Й. Агрегативно-ітеративні алгоритми для лінійних рівнянь з обмеженими операторами. -- Рукопис.

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

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

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

Петрович Р.Й. Агрегативно-итеративные алгоритмы для линейных уравнений с ограниченными операторами. -- Рукопись.

Диссертация на соискание ученой степени кандидата физико-математических наук по специальности 01.01.07 -- вычислительная математика. -- Львовский государственный университет имени Ивана Франко, Львов, 1999.

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

Рассматриваемые в диссертации алгоритмы принадлежат к классу методов итеративного агрегирования, которые активно развивались начиная с шестидесятых годов. В работах Л.М.Дудкина, Е.Б.Ершова, Б.А.Щенникова, Л.А.Хиздера, И.Н.Ляшенка, М.В.Калининой, А.А.Бабаджаняна к системам уравнений в конечномерном пространстве

, (1)

решаемым предлагаемыми авторами вариантами метода итеративного агрегирования предъявлялись жесткие условия. В частности требовалось, чтобы матрица A имела неотрицательные коэффициенты а вектор b - неотрицательные компоненты. Однако в ряде работ, в частности в книге Красносельский М.А. Лифшиц Е.А., Соболев А.В. "Позитивные линейные системы" отмечалось, что на практике имеет место сходимость однопараметрического варианта метода итеративного агрегирования и в ряде других случаев, даже когда спектральный радиус матрицы системы A больше единицы а для многопараметрического варианта метода условия сходимости неизвестны.

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

Для исследования однопараметрического варианта метода итеративного агрегирования итерационный параметр был объединен с компонентами вектора и рассматривался итерационный процесс

(2)

в пространстве . Пусть - упорядоченные по величине модуля собственные значения матрицы A, - упорядоченные по величине модуля собственные значения матрицы C. Для однопараметрического варианта метода итеративного агрегирования получены условия сходимости, которые требуют, чтобы модуль собственного значения матрицы C был меньше единицы и не накладывают никаких ограничений на элементы матрицы A и компоненты вектора b. Собственные значения матрицы C , можно рассматривать, как возмущенные собственные значения , матрицы A. Поэтому можно говорить, что однопараметрический вариант метода итеративного агрегирования устраняет влияние на итерационный процесс максимального по абсолютной величине собственного значения матрицы A. Используя это свойство, были построены агрегативно-итеративные алгоритмы, которые устраняют влияние на итерационный процесс наибольших по модулю собственных значений матрицы A. Рассмотрены случаи, когда собственные значения действительны и различны, имеют присоединенные вектора, комплексно-сопряжены.

Описанная методика используется для построения агрегативно-итеративных аналогов известных итерационных методов решения систем линейных алгебраических уравнений вида

. (3)

Любой стационарный одношаговый итерационный метод для системы (3) имеет вид , где A - матрица перехода метода. Способ построения матрицы A при некоторых ограничениях, оговоренных в каждом конкретном методе, гарантирует, что спектральный радиус меньше за единицу. Система эквивалентна (3). Агрегативно-итеративные аналоги известных методов получаются путем применения к ней алгоритмов, описанных в разделе 2. Для построения агрегативно-итеративных аналогов нестационарных методов, в частности метода наискорейшего спуска и итерационного чебышевского метода, применялась несколько иная методика. Для системы уравнений (3) строилась система уравнений

, (4)

найдя решение которого можно легко получить решение (3). Матрица строилась таким образом, что для нее были известными m собственных значений и собственных векторов, что позволило построить множество начальных приближений с теми же свойствами, что и в случае стационарных итерационных методов. Соответствующий нестационарный алгоритм применялся к системе уравнений (4) с выбором начального приближения из построенного множества. Эффективность построенных агрегативно-итеративных аналогов известных итерационных методов показана на примерах шести тестовых задач. В каждой из них система линейных уравнений вида (3) была получена путём применения метода сеток к некоторой граничной задаче. Для каждого агрегативно-итеративного метода отмечалось меньшее количество итераций и меньшее время исполнения, чем для его неагрегированного аналога при прочих равных условиях.

Описанная методика была применена для построения агрегативно-итеративных алгоритмов нахождения приближенного решения линейного уравнения (1) в банаховом пространстве.

Ключевые слова: Итеративное агрегирование, итерационные методы, линейные уравнения, ограниченные линейные операторы.

Petrovych R.J. Aggregative-iterational algorithms for linear equations with bounded operators. -- Manuscript.

The thesis on search of the scientific degree of the candidate of Physical and Mathematical Sciences, speciality 01.01.07 -- numerical mathematics. -- Ivan Franko Lviv State University, Lviv, 1999.

In this thesis new iterative algorithms for the linear equations in finite-dimensional and Banach spaces called aggregative-iterational algorithms are constructed and investigated. Using a technique of construction of these algorithms, the aggregative-iterational analogues of some numerical methods, in particular of a successive overrelaxation method, method of steepest descent, Chebyshev iterative method, method of simple iterations are constructed. The conditions of convergence and estimations of error bounds are obtained.

Key words: Iterative aggregation, Iterative methods, linear equations, bounded linear operators.

Підписано до друку 6.09.99
Папір офсетний
Формат 60х84/16
Тираж 100 прим.
ДУЛП 290646 Львів-13, Ст.Бандери, 12
Дільниця оперативного друку ДУЛП