4. Методи розв’язання системи лінійних рівнянь

4.1 Метод Крамера

Метод Крамера— спосіб розв'язання квадратних систем лінійних алгебраїчних рівнянь із ненульовим визначником основної матриці (при цьому для таких рівнянь розв'язок існує і є єдиним). Метод було створено Габріелем Крамером у 1750 році.

Опис методу:

Для системи лінійних рівнянь з невідомими (над довільним полем)

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

(i-й стовпчик матриці системи замінюється стовпчиком вільних членів). Іншим чином правило Крамера формулюється так: для будь-яких коефіцієнтів c₁, c₂, …, c_n виконується рівність:

У такій формі формула Крамера справедлива без припущення, що не рівне нулю, не треба навіть, аби коефіцієнти системи були елементами цілісного кільця (визначник системи навіть може бути дільником нуля у кільці коефіцієнтів). Також можна вважати, що або набори та , або набір складаються не з елементів кільця коефіцієнтів системи, а деякого модуля над цим кільцем. В такому вигляді формула Крамера використовується, наприклад, при доведенні формули для визначника Грама і Леми Накаями.

4.2 Метод Гауса

Метод Гаусса - класичний метод рішення системи лінійних алгебраїчних рівнянь (СЛАР). Це метод послідовного виключення змінних, коли за допомогою елементарних перетворень система рівнянь приводиться до рівносильній системі трикутного виду, з якої послідовно, починаючи з останніх (за номером) змінних, знаходяться всі інші змінні.

Опис методу: Нехай вихідна система виглядає наступним чином

Матриця A називається основний матрицею системи, b - стовпцем вільних членів.

Тоді відповідно до властивості елементарних перетворень над рядками основну матрицю цієї системи можна привести до східчастого увазі (ці ж перетворення потрібно застосовувати до колонки вільних членів):

При цьому будемо вважати, що базисний мінор (ненульовий мінор максимального порядку) основної матриці знаходиться у верхньому лівому куті, тобто в нього входять лише коефіцієнти при змінних

Тоді змінні називаються головними змінними. Всі інші називаються вільними.

Якщо хоча б одне число , де , то розглянута система несумісна, тобто у неї немає жодного рішення.

Нехай для будь-яких

Перенесемо вільні змінні за знаки рівностей і поділимо кожне з рівнянь системи на свій коефіцієнт при самому лівому ( , де  — номер рядка):

де

Якщо вільним змінним системи (2) надавати всі можливі значення і вирішувати нову систему відносно головних невідомих знизу вгору (тобто від нижнього рівняння до верхнього), то ми отримаємо всі рішення цієї СЛАР. Так як ця система отримана шляхом елементарних перетворень над вихідною системою (1), то по теоремі про еквівалентність при елементарних перетвореннях системи (1) і (2) еквівалентні, тобто безлічі їх рішень збігаються.

Алгоритм методу: Алгоритм розв'язання СЛАР методом Гауса підрозділяється на два етапи: 1)    На першому етапі здійснюється так званий прямий хід, коли шляхом елементарних перетворень над рядками систему призводять до ступінчастою або трикутній формі, або встановлюють, що система несумісна. А саме, серед елементів першого стовпця матриці вибирають ненульовий, переміщують його на крайнє верхнє положення перестановкою рядків і віднімають вийшла після перестановки перший рядок з інших рядків, Домножимо її на величину, рівну відношенню першого елемента кожної з цих рядків до першого елемента першого рядка, обнуляючи тим самим стовпець під ним. Після того, як зазначені перетворення були здійснені, перший рядок і перший стовпець подумки викреслюють і продовжують поки не залишиться матриця нульового розміру. Якщо на якийсь із ітерацій серед елементів першого стовпця не знайшов ненульовий, то переходять до наступного колонку і проробляють аналогічну операцію.

2)    На другому етапі здійснюється так званий зворотний хід, суть якого полягає в тому, щоб висловити все отримані базисні змінні через небазисні і побудувати фундаментальну систему рішень, або, якщо всі змінні є базисними, то виразити в чисельному вигляді єдине рішення системи лінійних рівнянь. Ця процедура починається з останнього рівняння, з якого висловлюють відповідну базисну змінну (а вона там всього одна) і підставляють в попередні рівняння, і так далі, піднімаючись по «сходинках» наверх. Кожному рядку відповідає рівно одна базисна змінна, тому на кожному кроці, крім останнього (самого верхнього), ситуація в точності повторює випадок останнього рядка.