Численные методы

Численные методы

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

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

рівнянь

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) у розгорнутому вигляді:

а11x1+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.