Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
ЛЬВІВСЬКИЙ ДЕРЖАВНИЙ УНІВЕРСИТЕТ
імені ІВАНА ФРАНКА
Петрович
Роман Йосипович
УДК 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 був меншим за одиницю.Отже, дослідження умов збіжності методів ітеративного агрегування з теоретичного і практичного погляду є актуальною задачею.
Мета і задачі дослідження. Метою роботи є побудова на основі методики Б.А.Шувара багатократних агрегативно-ітеративних алгоритмів, побудова агрегативно-ітеративних аналогів ітераційних методів: методу послідовної верхньої релаксації, чебишевського методу, методу найшвидшого спуску, а також дослідження збіжності запропонованих алгоритмів.
Наукова новизна одержаних результатів. На основі теоретичних і експериментальних досліджень, проведених в дисертаційній роботі:
запропоновані і досліджені алгоритми розв’язання систем лінійних алгебраїчних рівнянь, названі багатократними агрегативно-ітеративними алгоритмами;
досліджена збіжність цих алгоритмів за припущень, які не містять вимог про знакосталість коефіцієнтів матриць і вільних членів;
встановлені умови збіжності ітераційного процесу можуть справджуватися і тоді, коли спектральний радіус відповідної матриці переходу методу більший за одиницю;
запропоновані і досліджені алгоритми, які поєднують ідеї агрегативно-ітеративних методів з іншими ітераційними методами (послідовної верхньої релаксації, найшвидшого спуску, чебишевським методом, методом простої ітерації);
для лінійних рівнянь в банаховому просторі досліджені аналоги багатократних агрегативно-ітеративних алгоритмів.
На захист виносяться такі результати:
Методика побудови алгоритмів багатократного ітеративного агрегування.
Методика побудови алгоритмів, що поєднують ітеративне агрегування з методами послідовної верхньої релаксації, чебишевським ітераційним методом, методом найшвидшого спуску, методом простої ітерації.
Результати про збіжність і оцінки похибок запропонованих агрегативнно-ітеративних алгоритмів.
Практичне значення одержаних результатів. Проаналізовано можливість побудови нових наближених методів ітераційного типу, які природним чином можна поєднувати з багатьма відомими наближеними методами, розширюючи можливості застосування таких методів. Одержані результати можна використати при дослідженні реальних процесів, математичні моделі яких описуються лінійними рівняннями.
Особистий внесок здобувача. Всі наукові результати, включені в дисертацію, одержані здобувачем особисто. У спільних публікаціях Б.А.Шувару належить постановка задачі і участь в обговоренні результатів.
Апробація результатів дисертації. Основні результати, одержані в дисертаційній роботі, доповідалися на семінарі "Числові методи для диференціальних і інтегральних рівнянь" (ДУ "Львівська політехніка"), на всеукраїнській науковій конференції "Розробка та застосування математичних методів в науково-технічних дослідженнях", присвяченій 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) пов'язують такі властивості:
Вектор є власним вектором матриці , що відповідає власному числу .
Якщо вектор є розв'язком системи лінійних алгебраїчних рівнянь
, (9)
то є розв'язком системи (1).
Якщо - розв'язок рівняння (9), то .
Якщо початкове наближення вибрано із множини , то всі наступні наближення (n=1,2,...), отримані за формулами (6), (7) також належать до множини .
Це означає, що за вибору початкового наближення із (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 запропонований агрегативно-ітеративний аналог методу найшвидшого спуску. Суть алгоритму можна пояснити наступним чином:
В просторі будується рівняння
, (44)
знайшовши розв'язок якого отримуємо і розв'язок рівняння (34).
2. Матриця побудована так, що є відомими її m () власних значень і відповідних їм власних векторів .
Будується множина початкових наближень
, (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. Петрович Р.Й., Шувар Б.А. Однопараметричний агрегативно-ітеративний алгоритм для систем лінійних алгебраїчних рівнянь // Вісник Державного університету "Львівська політехніка", сер. Прикладна математика. - Львів, 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
Дільниця оперативного друку ДУЛП