/p>
Віднімаючи другий рядок з усіх наступних з підходящими множниками, отримуємо 0 у всіх елементах, що стоять під a (2),
Потім у частині матриці, що не включає першу і другу рядки і останній стовпець, знову шукаємо ненульовий елемент a (3) і, переставляючи рядки і стовпці, поміщаємо його на позицію (3,3) і т. д. Продовживши нашу процедуру, ми перетворимо вихідну матрицю до матриці, що має трапецієподібну форму: на головній діагоналі у такої матриці стоять ненульові елементи, а під головною діагоналлю - нулі. Наша процедура зупиниться, коли 1) ми дійдемо до дна матриці, або 2) буде неможливо знайти ненульовий елемент серед залишилися рядків, тобто залишилися рядки містять лише нулі (винятком може бути останній стовпець). На цьому прямий хід методу Гаусса закінчується. Його результатом є перетворена матриця.
. Зворотний хід методу Гаусса. Розглянемо уважно побудовану на попередньому кроці матрицю. Кожен рядок побудованої матриці представляє рівняння, яке однозначно по ній відновлюється. Таким чином, слід вирішити систему рівнянь, відповідну матриці, побудованої в результаті прямого ходу методу Гаусса. Можливі наступні ситуації:
а) Вона містить рядки, що складаються з нулів, за винятком елементів останнього стовпця, які не рівні нулю,
? ? 0. Так само кожна така рядок матриці відповідає рівнянню, в даному випадку - рівняння з нульовими коефіцієнтами, в правій частині якого коштує не нуль. Таким чином, в цьому випадку вихідна система рівнянь несовместна.
б) Підсумкова матриця містить повністю нульові рядки. Такі рядки відповідають тривіальному рівнянню 0=0, їх можна викреслити. Далі, r, число ненульових елементів на головній діагоналі одно рангу матриці коефіцієнтів вихідної системи рівнянь. При цьому можливі 2 ситуації:
· r=n - ранг матриці дорівнює числу невідомих. Це ситуація теореми Крамера, коли існує тільки одне рішення системи рівнянь. За побудованої матриці відновлюють систему рівнянь, яку вирішують знизу вгору. При цьому на кожному кроці рівняння тривіально.
· r lt; n. У цьому випадку слід невідомі з номерами, більшими r, покласти рівними довільним константам (тобто написати рівності xr + 1 =?, Xr + 2 =?, ..., Xn =?, Причому?,?, ... ,? можуть брати довільні значення), підставити ці значення в побудовану систему рівнянь і вирішувати ці рівняння знизу вгору. При цьому ми отримаємо набір рішень, що залежить від n? R вільних параметрів -? ,? , ...,?.
. 3.5 Детермінант матриць
Для квадратної матриці порядку n вводиться важлива для неї характеристика, звана детерминантом (іноді вживається назва визначник). Це число, яке за певним досить складного правилу зіставляється матриці. Для визначника матриці A={Aik} застосовують такі позначення:
де прямі дужки відрізняють визначник від матриці (при позначенні якої використовують круглі дужки). Число n при цьому називають також і порядком визначника.
Про числа A11, A22, ..., Ann кажуть, що вони стоять на головній діагоналі матриці (і, відповідно, визначника).
Ми будемо визначати поняття визначника матриці послідовно по порядку n. Розглянемо спочатку матрицю порядку 1, яка містить єдиний елемент (є 1 рядок і 1 стовпець). Для такої матриці визначник покладається рівним значенню її елемента.
Для матриці порядку 2,
Детермінант задається співвідношенням:
. 3.6 Робота зі слабко заповненими матрицями
У слабо заповнених матрицях більшість елементів дорівнюють нулю. Це дозволяє нам розглянути алгоритми зі складно організованими даними, що використовують не тільки масиви, а й списки і структури.
Слабо заповнену матрицю будемо зберігати у вигляді масиву з n елементів. Залежно від того, як ми хочемо зберігати матрицю - по рядках або по стовпцях, параметр n задаватиме число рядків або число стовпців матриці, і кожен елемент масиву задає відповідно рядок або стовпець слабо заповненою матриці. Кожен елемент цього масиву являє собою список структур. Кожна структура зберігає два числа - значення ненульового елементу і його індекс в рядку, або в стовпці.
Якщо перемножуючими матриці A і B заповнені на 10%, то таке подання матриць дозволяє приблизно в 5 разів скоротити необхідну для їх зберігання пам'ять. Істотно скоротиться і час множення матриць, оскільки всі дії будуть виконуватися тільки над ненульовими елементами.
Припустимо, що нулі рівномірно розподілені в слабо заповненою матриці. Нехай p - імовірність того, що елемент такої матриці не дор...
