8. Система лінійних рівнянь та методи їх розв’язання: метод Гауса.

1. Поняття системи лінійних алгебраїчних рівнянь

Система рівнянь - це умова, що складається в одночасному виконанні декількох рівнянь щодо кількох змінних. Системою лінійних алгебраїчних рівнянь (далі - СЛАУ), яка містить m рівнянь і n невідомих, називається система виду:

де числа a _ij називаються коефіцієнтами системи, числа b _i - вільними членами, a _ij і b _i (i = 1, ..., m; b = 1, ..., n) є деякі відомі числа, а x _1, ..., x _n - невідомі. У позначенні коефіцієнтів a _ij перший індекс i позначає номер рівняння, а другий j - номер невідомого, при якому стоїть цей коефіцієнт. Підлягають знаходженню числа x _n. Таку систему зручно записувати в компактній матричній формі: AX = B. Тут А - матриця коефіцієнтів системи, звана основний матрицею;

 - Вектор-стовпець з невідомих xj.

 - Вектор-стовпець з вільних членів bi.

Твір матриць А * Х визначено, так як в матриці А стовпців стільки ж, скільки рядків в матриці Х (n штук).

Розширеної матрицею системи називається матриця A системи, доповнена стовпцем вільних членів

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

Процес рішення по методу Гаусса складається з двох етапів: прямий і зворотний ходи.

1. Прямий хід.

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

Після того, як зазначені перетворення були здійснені, перший рядок і перший стовпець подумки викреслюють і продовжують поки не залишиться матриця нульового розміру. Якщо на якийсь із ітерацій серед елементів першого стовпця не знайшовся ненульовий, то переходять до наступного колонку і проробляють аналогічну операцію.

На першому етапі (прямий хід) система приводиться до ступінчастому (зокрема, трикутного) виду.

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

 ,

де 

Коефіцієнти aii називаються головними (провідними) елементами системи.

1-й крок.

Будемо вважати, що елемент   (Якщо a11 = 0, переставимо рядка матриці так, щоб a ₁₁ не дорівнював 0. Це завжди можливо, тому що в противному випадку матриця містить нульовий стовпець, її визначник дорівнює нулю і система несовместна).

Перетворимо систему, виключивши невідоме х1 у всіх рівняннях, крім першого (використовуючи елементарні перетворення системи). Для цього помножимо обидві частини першого рівняння на   і складемо почленно з другим рівнянням системи (або з другого рівняння почленно віднімемо перше, помножене на   ). Потім помножимо обидві частини першого рівняння на   і складемо з третім рівнянням системи (або з третього почленно віднімемо перше, помножене на   ). Таким чином, послідовно множимо перший рядок на число   і додаємо до i-му рядку, для i = 2, 3, ..., n.

Продовжуючи цей процес, одержимо еквівалентну систему:

Тут     - Нові значення коефіцієнтів при невідомих і вільні члени в останніх m-1 рівняннях системи, які визначаються формулами:

Таким чином, на першому кроці знищуються всі коефіцієнти, що лежать під першим провідним елементом a ₁₁   0, на другому кроці знищуються елементи, що лежать під другим провідним елементом а ₂₂ ⁽¹⁾ (якщо a ₂₂ ⁽¹⁾   0) і т.д. Продовжуючи цей процес і далі, ми, нарешті, на (m-1) кроці наведемо вихідну систему до трикутної системі.

Якщо в процесі приведення системи до східчастого увазі з'являться нульові рівняння, тобто рівності виду 0 = 0, їх відкидають. Якщо ж з'явиться рівняння виду   то це свідчить про несумісної системи.

На цьому прямий хід методу Гаусса закінчується.

2. Зворотний хід.

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

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

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

Примітка: на практиці зручніше працювати не з системою, а з розширеною її матрицею, виконуючи всі елементарні перетворення над її рядками. Зручно, щоб коефіцієнт a11 дорівнював 1 (рівняння переставити місцями, або розділити обидві частини рівняння на a11).