Розв’язування систем лінійних алгебраїчних рівнянь (СЛАР)

 

Розглянемо систему вигляду

     (3.1)

Її матричний вигляд

АХ= В.                              (3.2 )

Тут А – {[ ], (i,j= ) } - матриця системи,

B =  ,          X =  - вектори-стовпці.

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

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

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

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

Розглянемо більш детально ці дві різні групи підходів до розв’язання СЛАР.

 

Метод Гауcа

 

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

 с₁₁x₁ + c₁₂x₂ + …              + c_1nx_n = d₁

0 + c₂₂x₂ + …              + c_2nx_n = d₂

   ................................................                       (3.3)

0 + …      0+ c_n-1,n-1x_n-1 + c_n-1,nx_n = d_n-1

0 + 0 +                     +0 + c_nnx_n = d_n

Тоді з останнього рівняння відразу визначаємо  . Підставляючи його в попереднє рівняння, знаходимо x_n-1 і т.д. Загальні формули для отримання розв’язку мають вигляд

  (3.4)

При обчисленнях за формулами (3.4) треба буде виконати приблизно 1/2n² арифметичних дій. Зведення системи (3.1) до вигляду (3.3) можна виконати, послідовно заміняючи рядки матриці системи їх лінійними комбінаціями. Перше рівняння не змінюється. Віднімемо з другого рівняння системи (3.1) перше, помножене на таке число, щоб звернувся в нуль коефіцієнт при x₁. Потім у такий самий спосіб віднімемо перше рівняння з третього, четвертого і т.д. Таким чином обнуляються всі коефіцієнти першого стовпця, що лежать нижче головної діагоналі. Потім за допомогою другого рівняння виключимо з третього, четвертого і т.д. рівнянь коефіцієнти другого стовпця. Послідовно продовжуючи цей процес, виключимо з матриці всі коефіцієнти, що лежать нижче головної діагоналі.

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

                 (3.5)

Помножимо k -й рядок на число

                          (3.6)

і віднімемо від m -го рядка. Перший ненульовий елемент цього рядка звернеться в нуль, а інші зміняться за формулами

              (3.7)

.

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

Після виконання всіх циклів утвориться  система, матриця якої має трикутний вигляд. Її легко розв’язати зворотним ходом за формулами (3.4).

Виключення за формулами (3.7) не можна проводити, якщо в ході розрахунків на головній діагоналі виявиться нульовий елемент  Але в першому стовпці проміжної системи (3.5) всі елементи не можуть бути нулями: це означало б, що detA=0. Перестановкою рядків можна перемістити ненульовий елемент на головну діагональ і продовжити розрахунки.

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

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

Для зворотного ходу за формулами (3.4) число арифметичних операцій дорівнює

Загальні обчислювальні витрати методу Гауса становлять

, тобто .

Зауваження 1. Якщо елементи будь-якого рядка матриці системи в результаті перетворень стали дорівнювати нулю, то СЛАР – несумісна, оскільки не виконуються умови теореми Кронекера-Капеллі.

Зауваження 2. Якщо елементи будь-якого рядка матриці системи і права частина в результаті перетворень стали дорівнювати нулю, то СЛАР сумісна, але має безліч розв ’ язків, які можна отримати за допомогою методу Гауса для СЛАР порядку , де  - ранг матриці заданої СЛАР.