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