МЕТОДИ РОЗВ’ЯЗАННЯ СИСТЕМ ЛІНІЙНИХ АЛГЕБРАЇЧНИХ РІВНЯНЬ.

Розглянемо чисельні методи розв’язання систем лінійних алгебраїчних
рівнянь
Ax=f T
(1)
де A — матриця m*m, x = ( x1, x2 , … ,xm ) — шуканий вектор,
Т
f =(f1, f2, … , fm) -заданий вектор.
Припускаємо, що [pic]та визначник матриці А відмінний від нуля, так
що існує єдиний розв’язок х. З курсу алгебри відомо, що систему (1)
можна розв’язати за формулами Крамера*. Для великих m цей спосіб практично
нереалізований тому, що потребує порядку m! aрифметичних дій. Тому широко
використовуються інші методи розв’язання, наприклад, метод Гаусса**, який
потребує [pic] дій.
Методи чисельного розв’язання системи (1) поділяються на дві групи:
-прямі методи;
-ітераційні методи.
У прямих (або точних) методах розв’язок x системи (1) відшукується за
скінченну кількість арифметичних дій. Внаслідок похибок заокруглення прямі
методи насправді не приводять до точного розв’язку системи (1) і назвати їх
точними можливо лише залишаючи осторонь похибки заокруглення.
Ітераційні методи (їх також називають методами послідовних наближень)
полягають у тому, що розв’язок x системи (1) відшукується як границя при
[pic] послідовних наближень [pic]де n- номер ітерації. Як
правило, за скінченну кількість ітерацій ця границя не досягається.
______________________

* Крамер Габрієль (1704-1752)- швейцарський математик.
** Гаус Карл Фридрих (1777-1855)- німецький математик, астроном,
фізик, геодезист, професор Гетінгенського університету.

МЕТОД ГАУССА .

Запишемо систему (1) у розгорнутому вигляді:
а11×1+a12x2+…+a1mxm=f1 ,

a21x1+a22x2+…+a2mxm =f2 ,
(2)
………………………………..
am1x1+am2x2+…+ammxm =fm .

Метод Гаусса розв’язання системи (2) полягає у послідовному вилученні
невідомих x1, x2, …, xm-1 з цієї системи.
Припустимо, що a11[pic]0 . Поділив перше рівняння на a11, одержимо
x1+c12x2 +…+c1m xm =y1 ,
(3)

де : c1j=a1j /a11 ; j=2,m ; y1=f1/a11 .
Розглянемо тепер рівняння системи (2), що залишилися

ai1x1+ai2x2+…+aimxm=fi ; i= 2,m .
(4)

Помножимо (3) на ai1 та віднімемо одержане рівняння з і-го
рівняння системи (4), i=2,m.
У результаті одержимо наступну систему рівнянь:

x1+c12x2+…+c1jxj+…+c1mxm =y1 ,

(1) (1) (1)
(1)
a22x2+… +a2jxj+…+a2mxm=f2 ,
……………………………………..
(5)
(1) (1) (1)
(1)
am2x2+…+amjxj+…+ammxm=fm .

Tут позначено:
(1) (1)
aij=aij-c1jai1; fi=fi -y1ai1; i,j=2,m .
(6)

Матриця системи (5) має вигляд:
[pic].
Матриці такої стуктури заведено позначати так:
[pic]

де хрестиками позначені ненульові елементи.
У системі (5) невідоме х міститься тільки в першому рівнянні, тому
у подальшому достатньо мати справу із скороченою системою рівнянь:
(1)
(1) (1) (1)
a22x2 +…+a2jxj +…+a2mxm =f2 ,

………………………………………. (7)
(1) (1)
(1) (1)
am2x2 +…+amjxj +…+ammxm =fm .

Тим самим ми здійснили перший крок методу Гаусса . Коли [pic], то з системи
(7) зовсім аналогічно можна вилучити невідоме x2 і прийти до системи,
еквівалентній (2),що має матрицю такої структури:
[pic]
При цьому перше рівняння системи (5) залишається без зміни.
Вилучая таким же чином невідомі х 3, х4 ,… ,x m-1 , приходимо остаточно
до системи рівнянь виду:
x1 +c12x2 +…+c1,m-1xm-1+c1mxm =y1,
x2 +…+c2,m-1xm-1+c2mxm =y2 ,

…………………………..
xm-1+cm-1,mxm=ym-1,
xm=ym
,

що еквівалентна початковій системі (2) .
Матриця цієї системи
[pic]
містить нулі усюди нижче головної діагоналі. Матриці такого виду
називаються верхніми трикутними матрицями. Нижньою трикутною матрицею
називається така матриця, у якої дорівнюють нулю усі елементи, що містяться
вище головної діагоналі.
Побудова системи (8) складає прямий хід методу Гаусса. Зворотнiй хід
полягає у відшуканні невідомих х1, … ,хm з системи (8). Тому що
матриця системи має трикутний вигляд, можна послідовно, починаючи з хm,
відшукати всі невідомі. Дійсно, xm=ym,
x m-1 =ym-1 -cm-1,m x m i т. д.
Загальні форми зворотнього ходу мають вигляд:
m

xi =yi — ( cijxj ; i=m-1,1; xm =ym .
(10)

j=i+1
При реалізації на ЕОМ прямого ходу методу Гаусса немає необхідності
діяти із змінними x1 ,x2 ,… ,xm. Досить вказати алгоритм,за яким
початкова матриця А перетворюється до трикутного вигляду (9), та вказати
відповідне перетворення правих частин системи.
Одержимо ці загальні формули.
Нехай вже здійснені перші к-1 кроків, тобто вже вилучені змінні
x1 , x2,…, xk-1 .
Тоді маємо систему:
x1+c12 x2 +…+c1,k-1xk-1+ c1kxk+….+c1mxm =y1 ,
x2 +…+c2,k-1xk-1+ c2kxk+….+c2mxm =y2 ,

……………………………………….
xk-1+ck-1,kxk+…+ck-1,mxm=yk-1
, (11)

(k-1) (k-1) (k-1)
akkxk+…+akmxm =fk ,

……………………….

(k-1) (k-1) (k-1)
amkxk+…+ammxm =fm .

Розглянемо К-те рівняння цієї системи:

(k-1) (k-1) (k-1)

akkxk+…+akmxm=fk ,

та припустимо, що [pic] . Поділивши обидві частини цього рівняння на
[pic] , одержимо

xk+ck,k+1xk+1+…+ckmxm=yk ,
(12)

(k-1) (k-1)
(k-1) (k-1)
де ckj=akj / akk ; j=k+1,m ; yk=fk / akk .

Далі помножимо рівняння (12) на [pic] та віднімемо одержане
співвідношення з i-го рівняння системи (11). У результаті остання група
рівнянь системи (11) набуває наступного вигляду:

x k+ck,k+1xk+1 +…+ ckmxm=yk,

(k) (k)
(k)
ak+1,k+1xk+1+…+ ak+1,mxm=fk+1,
…………………………………

(k)
(k) (k)
am,k+1xk+1+… + ammxm=fm ,

(k) (k-1) (k-1) (k)
(k-1) (k-1)
де: aij =aij — aikckj ; i,j=k+1,m ; fi= fi — aikyk ; i=k+1,m
.
Таким чином, у прямому ході методу Гаусса коефіцієнти рівнянь
перетворюються за наступним правилом

(0)
akj =akj ; k,j=1,m ;

(k-1) (k-1)
ckj=akj /akk ; j=k+1,m ; k=1,m ;
(13)

(k) (k-1) (k-1)
aij =aij — aikckj ; i,j=k+1,m ; k=1,m .
(14)

Обчислення правих частин системи (8) здійснюється за формулами:

(0) (k-1) (k-1)
fk=fk ; yk = fk / akk ; k=1,m ;
(15)

(k) (k-1) (k-1)

fi = fi — aikyk ; k=1,m .
(16)

Коефіціенти cij і праві частини yi ; i=1,m ; j=i+1,m зберігаються
у пам’яті ЕОМ і використовуються при здійсненні зворотнього ходу за
формулами (10).
Основним обмеженням методу є припущення, що усі елементи [pic] , на які
здійснюється ділення, відрізняються від нуля. Число [pic]називається
провідним елементом на К-му кроці вилучення. Навіть, якщо деякий провідний
елемент не дорівнює нулеві, а просто є близьким до нуля, в процесі
обчислень може мати місце нагромадження похибок. Вихід з цієї ситуації
полягає в тому, шо як провідний елемент вибирається не [pic] , а інше
число ( тобто на К-му кроці вилучається не xk, а інша змінна xj , [pic])
. Така стратегія вибору провідних елементів здійснюється в методі Гаусса з
вибором головного елементу, який буде розглянуто пізніш.
А тепер підрахуємо число арифметичних дій, що необхідні для
розв’язання системи за допомогою методу Гаусса. Оскільки виконання операцій
множення і ділення на ЕОМ потребує набагато більше часу, ніж виконання
додавання і віднімання, обмежимось підрахуванням числа множень і ділень.

1.Обчислення коефіцієнтів [pic] за формулами (13) потребує:
[pic](m-k)=1+2+…+(m-1)= [pic] ділень .
2.Обчислення усіх коефіцієнтів [pic] за формулами (14) потребує
[pic]
множень (тут ми використовуємо легко перевіряєму за індукцією рівність
[pic] ).
Таким чином, обчислення ненульових елементів [pic] трикутної матриці С
потребує
[pic]
операцій множення і ділення.
3.Обчислення правих частин yk за формулами (15) потребує m
ділень, а відшукання [pic] за формулами (16)
[pic]
множень. Разом, обчислення правих частин перетвореної системи (8) потребує
[pic]
дій множення і ділення.
Усього для реалізації прямого ходу методу Гаусса необхідно виконати
[pic]
дій.
4.Для реалізації зворотнього ходу методу Гаусса за формулами (10)
необхідно
[pic]
множень.
Всього, для реалізації методу Гаусса необхідно виконати
[pic]
дій множення і ділення, причому основний час витрачається на прямий хід.
Для великих m число дій множення і ділення у методі Гаусса близьке до
[pic] За витратами часу та необхідній машинній пам’яті метод Гаусса
придатний для розв’язання систем рівнянь (2) загального вигляду з кількістю
змінних m порядку 100.