Метод Релаксації для розв'язку Слар

Вступ

 

Чисельний розв’язок системи  лінійних алгебраїчних рівнянь (СЛАР) - одне з найбільш часто зустрічаються  завдань у науково-технічних дослідженнях. Така задача виникає в математичній фізиці (чисельне рішення диференціальних  та інтегральних рівнянь), економіці, статистиці тощо. При цьому прикладні задачі часто потребують вирішення великих і надвеликих СЛАР з числом невідомих більше 1000. До таких СЛАР, наприклад, звертаються при чисельному розв’язанні двовимірних і особливо тривимірних задач математичної фізики, в яких умови фізичної і геометричної апроксимації двовимірної і тривимірної області потребують використання досить дрібної розрахункової сітки з великим числом розрахункових вузлів за лінійним розміром.

Існуючі бібліотеки програм  на мовах високого рівня, розроблені на основі, так званих, прямих методів розв'язування СЛАР, типу методу Гауса і його модифікацій. Число арифметичних операцій множення для чисельного розв'язання СЛАР розмірністю за допомогою прямого методу - . Кубічна залежність числа арифметичних операцій від розміру матриці СЛАР приводить при до нереально великого часу розв’язання навіть на найсучасніших ЕОМ. Крім того, час вирішення непропорційно зростає при використанні прямих методів у випадку з причини недостатності обсягу оперативної пам'яті для зберігання даних завдання.

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

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

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

У курсовій роботі розглянуто метод релаксації для рішення СЛАР.

 

Розділ 1. Теоретична основа методу релаксації

1.  Постановка задачі

 

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

    (1.1)

де  — невідомі, які потрібно визначити;

— коефіцієнти системи

— вільні члени системи.

(1.1) можна записати  у вигляді

     (1.2)

де

А - матриця розмірності ,

x=(x₁,x₂,...,x_n)^T- вектор розв’язків,

f=(f₁,f₂,...,f_n)^T - вектор правих частин.

Чисельні методи розв’язання даної системи прийнято розділяти на два класи: прямі  методи та ітераційні.

Прямими методами називаються  методи, що дозволяють отримати розв'язок системи рівнянь (1.1) за кінцеве число арифметичних операцій.

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

Суть ітераційних методів полягає в тому, що розв’язок системи (1.1) знаходиться як границя послідовних наближень x⁽ⁿ⁾ при n®¥, де n - номер ітерації. Застосування ітераційних методів вимагає завдання початкового значення невідомих х⁽⁰⁾ і точності обчислень e> 0. Обчислення проводяться до тих пір, поки не буде виконана оцінка

     (1.3)

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

Число ітерацій n=n(e), яке необхідно виконати для отримання заданої точності e, є основною оцінкою якості методу. З цього числа проводиться порівняння різних методів.

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

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

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

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

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

,    (1.4)

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

Завданням роботи є знаходження  з (1.1) за допомогою методу релаксації.

2. Теоретичні основи розв’язання  СЛАР

 

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

,    (1.5)

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

Для отримання  розрахункових формул (1.5) перепишемо у вигляді

  ,  (1.6)

або в покомпонентному  записі отримаємо

    (1.7)

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

,    (1.8)

    (1.9)

   (1.10)

   і т.д.

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

Розглянемо  ітераційні методи з постійним ітераційним  параметром, записані у вигляді

     (1.11)

Теорема 1. Нехай  А - симетрична позитивно визначена матриця, t > 0 і нехай виконано нерівність В-0,5tА>0. Тоді ітераційний метод (1.11) сходиться.

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

     (1.12)

Тоді метод  Якобі сходиться.

Наслідок 2. Нехай А - симетрична позитивно визначена матриця. Тоді метод верхніх релаксацій сходиться  за умови 0<w<2. Зокрема, метод Зейделя сходиться (w= 1).

Теорема 2. Ітераційний метод (1.11) сходиться при будь-якому  початковому наближенні тоді і тільки тоді, коли всі власні значення матриці   за модулем менше одиниці.

Теорема 3. Нехай А і  В - симетричні позитивно визначені  матриці, для яких справедливі нерівності , де g₁,g₂ - позитивні постійні, g₁>g₂. При ітераційний метод (1.11) збігається і для похибки справедливі оцінки

, i=0,1,...,   (1.13)

де

      (1.14)

      (1.15)

      (1.16)

       (1.17)

 

Наслідок 1. Якщо А^Т=А>0, то для методу простої ітерації

       (1.18)

при

   (1.20)

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

,     (1.21)

де

      (1.22)

      (1.23)

 

Наслідок 2. Для симетричної  матриці А і 

     (1.24)

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

  ,     (1.25)

де, . Часто зустрічаються завдання з погано обумовленою матрицею А, коли відношення велике. У цьому випадку число r₀ близько до одиниці, і метод простої ітерації сходиться повільно.

Оцінимо число  ітерацій n₀(e), яке потрібно для досягнення заданої точності e у випадку малих x, тобто для отримання оцінки

       (1.26)

З умови  отримуємо, що

,      (1.27)

і при малих x маємо

     (1.28)

Зауважимо, що як критерій збіжності ітераційного методу може використовуватися нев'язка, яка виходить при підстановці знайденого розв’язку в систему (1.2). Отже, можемо сказати, що метод релаксації є актуальним для використання при розв’язанні СЛАР.

3. Метод верхніх релаксацій

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

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

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

Основна обчислювальна  формула має вигляд

     (1.29)

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

     (1.30)

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

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

4. Похибка методу верхньої релаксації

Одне з основних питань застосування ітераційних методів пов'язаний з коректністю вибору точності методу e.

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

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

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

     (1.31)

Нехай коефіцієнти  і f_i задані з деякою відносною похибкою. Припустимо, що ітераційний метод сходиться, і нев'язка

      (1.32)

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

,      (1.33)

тут - модуль мінімального значення діагонального елемента . Звідси випливає, що похибка методу .

5. Метод блочної релаксації

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

     (1.34)

де

     (1.35)

    (1.36)

     (1.37)

Запишемо формулу  для блоків матриці  і блок-векторів і :

   (1.38)

Позначимо

   (1.39)

    (1.40)

Тоді, підставляючи (1.39) і (1.40) в (1.38) і помноживши зліва  на , для кожного блок-вектора одержуємо СЛАР:

      (1.41)

Рішення отриманих  систем (1.41) рекомендується виконувати з використанням факторизації матриці  , причому факторизацію слід виконувати 1 раз перед першою ітерацією.