←предыдущая следующая→
1 2
МЕТОДИ РОЗВ’ЯЗАННЯ СИСТЕМ ЛІНІЙНИХ АЛГЕБРАЇЧНИХ РІВНЯНЬ.
Розглянемо чисельні методи розв’язання систем лінійних алгеб-раїчних рівнянь
Ax=f T (1)
де A - матриця m*m, x = ( x1, x2 , ... ,xm ) - шуканий вектор,
Т
f =(f1, f2, ... , fm) -заданий вектор.
Припускаємо, що та визначник матриці А відмінний від нуля, так що існує єдиний розв’язок х. З курсу алгебри відомо, що систему (1) можна розв’язати за формулами Крамера*. Для великих m цей спосіб практично нереалізований тому, що потре-бує порядку m! aрифметичних дій. Тому широко використовуються інші методи розв’язання, наприклад, метод Гаусса**, який потре-бує дій.
Методи чисельного розв’язання системи (1) поділяються на дві групи:
-прямі методи;
-ітераційні методи.
У прямих (або точних) методах розв’язок x системи (1) від-шукується за скінченну кількість арифметичних дій. Внаслідок по-хибок заокруглення прямі методи насправді не приводять до точ-ного розв’язку системи (1) і назвати їх точними можливо лише за-лишаючи осторонь похибки заокруглення.
Ітераційні методи (їх також називають методами послідовних наближень) полягають у тому, що розв’язок x системи (1) відшу-кується як границя при послідовних наближень де n- номер ітерації. Як правило, за скінченну кількість ітера-цій ця границя не досягається.
______________________
* Крамер Габрієль (1704-1752)- швейцарський математик.
** Гаус Карл Фридрих (1777-1855)- німецький математик, астро-ном, фізик, геодезист, професор Гетінгенського університету.
МЕТОД ГАУССА .
Запишемо систему (1) у розгорнутому вигляді:
а11x1+a12x2+...+a1mxm=f1 ,
a21x1+a22x2+...+a2mxm =f2 , (2)
......................................
am1x1+am2x2+...+ammxm =fm .
Метод Гаусса розв’язання системи (2) полягає у послідовному вилученні невідомих x1, x2, ..., xm-1 з цієї системи.
Припустимо, що a11 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) має вигляд:
.
Матриці такої стуктури заведено позначати так:
де хрестиками позначені ненульові елементи.
У системі (5) невідоме х міститься тільки в першому рівнян-ні, тому у подальшому достатньо мати справу із скороченою сис-темою рівнянь:
(1) (1) (1) (1)
a22x2 +...+a2jxj +...+a2mxm =f2 ,
.............................................. (7)
(1) (1) (1) (1)
am2x2 +...+amjxj +...+ammxm =fm .
Тим самим ми здійснили перший крок методу Гаусса . Коли , то з системи (7) зовсім аналогічно можна вилучити не-відоме x2 і прийти до системи, еквівалентній (2),що має матрицю такої структури:
При цьому перше рівняння системи (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) .
Матриця цієї системи
містить нулі усюди нижче головної діагоналі. Матриці такого виду на-зиваються верхніми трикутними матрицями. Нижньою трикутною мат-рицею називається така матриця, у якої дорівнюють нулю усі елемен-ти, що містяться вище головної діагоналі.
Побудова системи (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 ,
та припустимо, що . Поділивши обидві частини цього рівнян-ня на , одержимо
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) на та віднімемо одержане співвідношення з i-го рівняння системи (11). У результаті остання гру-па рівнянь системи (11) набуває наступного вигляду:
x k+ck,k+1xk+1 +...+ ckmxm=yk,
←предыдущая следующая→
1 2