Численные методы
МЕТОДИ РОЗВ’ЯЗАННЯ СИСТЕМ ЛІНІЙНИХ АЛГЕБРАЇЧНИХ РІВНЯНЬ.
Розглянемо чисельні методи розв’язання систем лінійних алгебраїчних рівнянь
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 ,
................................