Головна
1. Основні поняття
2. Метод виключення Гаусса
3. Розкладання матриці на множники
4. Умови застосування методу Гаусса
Розділ 3. Методи розв'язування алгебраїчних рівнянь і систем алгебраїчних рівнянь

   До чисельних методів лінійної алгебри належать методи розв'язання систем лінійних алгебраїчних рівнянь, обернення матриць, обчислення визначників і знаходження власних значень і власних векторів матриць. Завдяки використанню локальної лінеаризації нелінійних залежностей переважна більшість задач обчислювальної математики зводиться до розв'язання систем лінійних алгебраїчних рівнянь. У лінійній алгебрі таку задачу називають першою основною задачею. До неї належать задачі обчислення визначників і обчислення елементів оберненої матриці. Іноді обчислення визначників і елементів оберненої матриці називають другою і третьою основними задачами лінійної алгебри.

   3.1. Основні поняття

   Нагадаємо основні поняття, що використовуються в цьому розділі. Систему лінійних алгебраїчних рівнянь подамо у такому вигляді:

     (3.1)

або

Систему лінійних алгебраїчних рівнянь часто записують у матричній формі

Ах = b,     (3.2)

де А - матриця коефіцієнтів системи, b — вектор вільних членів і х — вектор невідомих.
   Якщо матриця А неособлива, тобто її визначник не дорівнює нулю, система (3.1) має єдиний розв'язок. У лінійній алгебрі звичайно використовують спосіб розв'язання системи рівнянь (3.2), що заснований на обчисленні оберненої матриці А-1. Дійсно, якщо помножити обидві частини рівняння (3.2) на матрицю А-1, то розв'язок рівняння отримаємо у вигляді

x = А-1b.     (3.3)

   Елементи оберненої матриці можна обчислити за відомою формулою

де Aij алгебраїчне доповнення елемента aij матриці A і det А — визначник цієї матриці. Тоді для знаходження всіх її елементів потрібно знайти значення n2 визначників порядку n. Остання задача настільки трудомістка, що розв'язати її навіть для n = 10 дуже важко.
   Менш трудомістким є метод Крамера, у якому значення невідомих xi, i=1,2, ..., n можна отримати за допомогою формули

     (3.4)

де матриця Аi формується з матриці А заміною її і-го стовпця на стовпець вільних членів. Але для розв'язання системи лінійних алгебраїчних рівнянь з п невідомими у такий спосіб потрібно обчислити n+1 визначників порядку n, що за великого значення п також є дуже трудомісткою операцією, оскільки для розв'язання лінійної системи рівнянь з п невідомими буде потрібно nn! арифметичних операцій. Вже коли n=50, такий об'єм обчислень практично недоступний сучасним комп'ютерам. Далі ми розглянемо більш зручні для обчислень методи.
   Методи чисельного розв'язання системи рівнянь(3.1) діляться на дві групи: прямі та ітераційні. До першої групи належать наведені вище методи розв'язання систем лінійних алгебраїчних рівнянь. В прямих (або точних) методах кількість арифметичних дій, потрібних для отримання розв'язку х системи (3.1), є скінченним числом. Прикладом прямого методу є також метод Гаусса. Ітераційні методи полягають в тому, що розв'язок х системи (3.1) знаходять як границю послідовних наближень x(k), коли k -» оо, де k — номер ітерації.

   3.2. Метод виключення Гаусса

   Розв'язання системи лінійних алгебраїчних рівнянь методом Гаусса полягає її послідовному виключенні невідомих x1, x2, ..., xn із цієї системи. Припустимо, що визначник матриці А відмінний від нуля, що свідчить про те, що система (3.1) має єдиний розв'язок. Якщо a11 не дорівнює 0, то, поділивши перше рівняння (3.1) на a11, отримаємо:

     (3.5)

де

   Розглянемо решту рівнянь системи (3.1)

     (3.6)

і у кожному з них виключимо невідому x1, виконавши таку послідовність дій. Помножимо (3.5) на ai1 і віднімемо отримане рівняння від і-го рівняня системи (3.6).
   У результаті отримаємо таку систему рівнянь:

     (3.7)

   Тут позначено

     (3.8)

   У системі (3.7) невідома x1 є тільки в першому рівнянні, тому надалі достатньо мати справу зі скороченою системою рівнянь:

     (3.9)

   У такий спосіб здійснено перший крок методу Гаусса. Якщо a22(1) не дорівнює 0, то з системи (3.9) аналогічно можна виключити x2 і перейти до системи, яка еквівалетна (3.1). При цьому перше рівняння системи (3.7) залишиться без змін.
   Виключаючи послідовно в такий спосіб невідомі x3, x4, ... , xn, прийдемо остаточно до системи рівнянь, яка має такий вигляд:

     (3.10)

   У матриці цієї системи, що еквівалентна системі (3.1) всі елементи, які розташовані нижче головної діагоналі, дорівнюють нулю. Такі матриці називаються верхніми трикутними, на відміну від нижніх трикутних матриць, у яких дорівнюють нулю всі елементи, розташовані вище головної діагоналі.
   Перехід від системи (3.1) до системи (3.10) являє собою прямий хід методу Гаусса. Зворотний хід полягає в знаходженні невідомих x1, x2, ... , xn з системи (3.10). Це зробити дуже просто, оскільки матриця системи трикутна і за її допомогою можна послідовно, починаючи з xn знайти всі невідомі. Загальні формули зворотного ходу мають такий вигляд:

     (3.11)

   Тепер виведемо розрахункові формули прямого ходу. Припустимо, що виконані перші k - 1 кроків, тобто вже виключені змінні x1, x2, ..., xk-1. Тоді для виключення матимемо аналогічну (3.9) скорочену систему:

     (3.12)

   Нехай akk(k-1) не дорівнює 0. Поділивши обидві частини k-го рівняння на akk(k-1), отримаємо

     (3.13)

де

   Помножимо рівняння (3.13) на aik(k-1) і віднімемо отримане співвідношення з i-го рівняння скороченої системи (3.12) де i=k+1, k+2, ..., n. У результаті група рівнянь (3.12) набуде такого вигляду:

   Отже, під час прямого ходу методу Гаусса коефіцієнти системи рівнянь обчислюються за наведеними нижче формулами:

     (3.14)

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

     (3.15)

   Основним обмеженням методу є припущення про те, що всі елементи akk(k-1), на які проводиться ділення на кожному кроці методу, відмінні від нуля. Елемент akk(k-1) називається ведучим елементом на k-му кроці виключення. Слід мати на увазі, що навіть якщо якийсь ведучий елемент не дорівнює нулю, а просто близький до нього, в процесі обчислень може відбуватися значне накопичення похибок. Уникнути цього дозволяє метод Гаусса з вибором головного елемента. Ідея методу полягає в тому, щоб на черговому кроці виключати ту невідому, коефіцієнт за якої найбільший за модулем. Отже, ведучим елементом тут вибирається головний, тобто найбільший за модулем елемент матриці. Тим самим, якщо det A не дорівнює 0, то в процесі обчислень не відбуватиметься ділення на нуль.
   Для зменшення помилок округлювання чинять так. Серед елементів першого рядка akj(k-1) кожної проміжної матриці (3.12) вибирають найбільший за модулем елемент max модуль akj(k-1), j=k, k+1, ..., n і роблять цей елемент ведучим. Вказаний спосіб виключення називається методом Гаусса з вибором головного елемента по рядку. Він еквівалентний застосуванню звичайного методу Гаусса до системи, в якій на кожному кроці виключення проводиться відповідна перенумерація змінних.
   Заетоеовугтьсн також метод із вибором головного елемента по стовпцю (рис. 2.1, а). Він еквівалентний застосуванню звичайного методу Гаусса до системи, в якій на кожному кроці виключення проводиться відповідна перенумерація рівнянь.

     (3.16)

   Проте головний елемент можна вибрати і серед всіх елементів неперетвореної частини матриці:


Рис. 3.1 Вибір головного елемента: а - серед елементів стовпця матриці; б - серед елементів неперетвореної частини матриці

   Визначимо складність алгоритму, що реалізує метод Гаусса на однопроцесорній ЕОМ. Розглянемо задачу розв'язання системи лінійних рівнянь з р правими частинами:

Ax1 = b1, ..., Axp = bp
   На кожному k-му кроці кожного ходу Гаусса необхідно виконати (n-k) ділень, (n-k)(n-k+p+1) множень то додавань. Використовуючи формулу для ряду 12 + 22 + 32 +...+m2 = m(m+1)(2m+1)/6, отримаємо

   Під час зворотного ходу необхідно виконати n ділень та

множень і додавань, тому, коли р=1, маємо

     (3.17)

   Отже, для реалізації методу Гаусса потрібно близько n3/3 операцій множення. Це поліномний алгоритм, але навіть він для великої розмірності задачі ускладнює обчислювальний процес, про що свідчать дані табл. 2.1. У ній наведено тривалість прямого і зворотного ходів залежно від розмірності розв'язуваної системи рівнянь для комп'ютера з середньою швидкістю виконання операції ділення/множення 15 мкс.

   Алгоритм Гаусса є послідовним алгоритмом, орієнтованим на виконання на однопроцесорній ЕОМ.

   3.3. Розкладання матриці на множники

   Зв'язок методу Гаусса з розкладанням матриці на множники

   Алгоритм Гаусса можна компактно записати в матричних позначеннях. Він відповідає розкладанню матриці А на добуток більш простих матриць. Спочатку для наочності розглянемо систему Ах = b, що складається лише з трьох рівнянь:

     (3.18)

   Виключення невідомої x1 з двох останніх рівнянь системи (3.18) здійснюється виконанням таких операцій:

  • ділення першого рівняння на a11 не дорівнює 0;
  • віднімання перетвореного першого рівняння, помноженого на ai1 , від рівнянь i=2,3.
  •    Перша операція еквівалентна множенню системи рівнянь зліва на діагональну матрицю

    друга операція еквівалентна множенню зліва на матрицю

       Звідси випливає, що виключення x1 рівносильно множенню системи зліва на матрицю, яку називають елементарною нижньою трикутною матрицею.

       3.4. Умови застосування методу Гаусса

       Все сказане можна перенести і на системи рівнянь довільного порядку. Процес виключення можна записати за допомогою формули

    LnLn-1 ... L1Ax = LnLn-1 ... L1b,     (3.19)

    де елементарна нижня трикутна матриця Lk на k-му кроці має вигляд
         (3.20)

       Елементарна нижня трикутна матриця Lk здійснює виключення невідомої xk з рівнянь із номерами (k+1), (k+2), ..., n. Матриці Lk-1 існують і мають такий вигляд:

         (3.21)

       Очевидно, що матриці Lk існують, коли

    для кожного k=1,2 ,..., n. Остання умова буде виконана, якщо всі кутові мінори матриці A відмінні від нуля. Переконаємося в цьому. Позначемо через (модуль Am) кутовий мінор матриці А порядку m:

       Нехай Am, Lm, Um - матриці кутового мінору m-го порядку матриць A, L, U, тобто:

    Am = LmUm

       Оскільки

    то

    Отже,

    оскільки всі кутові мінори матриці А відмінні від нуля. Якщо хоча б один із кутових мінорів матриці А дорівнює нулю, то розглянутий вище LU-розклад неможливий. Це легко бачити на прикладі матриць другого порядку. Отже, метод Гаусса можна застосовувати тільки тоді, коли всі кутові мінори матриці А відмінні від нуля.
       Запис методу Гаусса у вигляді (3.19) детально зображує процес виключення. Тепер його можна реалізувати інакше. Нехай задані матриця А і вектор b. Спочатку проводиться розкладання А в добуток двох трикутних матриць, А = LU. Початкова система набуває вигляду LUx = b, її розв'язання рівносильно послідовному розв'язанню систем рівнянь

    Ly = b,     (3.22)
    Ux = y     (3.23)

    з трикутими матрицями, звідки й знаходять шуканий вектор х. Розкладання A = LU відповідає прямому ходу методу Гаусса, а розв'язання системи (3.22) - (3.23) - зворотному ходу.    Розглянутий алгоритм (3.19) приведення системи рівнянь до системи з верхньою трикутною формою ефективно реалізується на паралельних процесорах. Відомо, що систолічний алгоритм перемноження двох матриць розмірности nxn на SIMD-системі матричного типу реалізується за час, який дорівнює часу виконання n множень, n-1 додавань і 3(n-1) зсувів, тому зведення системи до вигляду

    тобто прямий хід методу Гаусса, може бути реалізовано виконанням 5n2 + n машинних операцій на матричному процесорі.