1. Система лінійних алгебраїчних рівнянь
1.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.2 Рішення системи лінійних алгебраїчних рівнянь
Рішенням системи рівнянь називається упорядкований набір чисел (значень змінних), при підстановці яких замість змінних кожне з рівнянь системи звертається у вірне рівність.
Рішенням системи називається n значень невідомих х1 = c1, x2 = c2, ..., xn = cn, при підстановці яких усі рівняння системи звертаються в вірні рівності. Усяке рішення системи можна записати у вигляді матриці-стовпця
Система рівнянь називається сумісною, якщо вона має хоча б одне рішення, і несумісною, якщо вона не має жодного рішення.
Спільна система називається визначеною, якщо вона має єдине рішення, і невизначеною, якщо вона має більше одного рішення. В останньому випадку кожне її рішення називається приватним рішенням системи. Сукупність усіх приватних рішень називається загальним рішенням.
Вирішити систему - це значить з'ясувати, совместна вона або несовместна. Якщо система совместна, знайти її спільне рішення.
Дві системи називаються еквівалентними (рівносильними), якщо вони мають одне і те ж загальне рішення. Іншими словами, системи еквівалентні, якщо кожне рішення однієї з них є рішенням іншого, і навпаки.
Перетворення, застосування якого перетворює систему в нову систему, еквівалентну вихідній, називається еквівалентним або рівносильним перетворенням. Прикладами еквівалентних перетворень можуть служити наступні перетворення: перестановка місцями двох рівнянь системи, перестановка місцями двох невідомих разом з коефіцієнтами у всіх рівнянь, множення обох частин якого рівняння системи на відмінне від нуля число.
Система лінійних рівнянь називається однорідною, якщо всі вільні члени дорівнюють нулю:
Однорідна система завжди сумісна, так як x1 = x2 = x3 = ... = xn = 0 є рішенням системи. Це рішення називається нульовим або тривіальним.
2. Метод виключення Гауса
2.1 Сутність методу виключення Гауса
Класичним методом розв'язання систем лінійних алгебраїчних рівнянь є метод послідовного виключення невідомих - метод Гаусса (його ще називають методом гауссових виключень). Це метод послідовного виключення змінних, коли за допомогою елементарних перетворень система рівнянь приводиться до рівносильній системі ступеневої (або трикутного) виду, з якого послідовно, починаючи з останніх (за номером) змінних, знаходяться всі інші змінні.
Процес рішення по методу Гауса складається з двох етапів: прямий і зворотний ходи.
1. Прямий хід.
На першому етапі здійснюється так званий прямий хід, коли шляхом елементарних перетворень над рядками систему призводять до ступінчастої або трикутної формі, або встановлюють, що система несумісна. А саме, серед елементів першого стовпця матриці вибирають ненульовий, переміщують його на крайнє верхнє положення перестановкою рядків і віднімають вийшла після перестановки перших рядок з решти рядків, домножити її на величину, рівну відносно першого елемента кожної з цих рядків до першого елемента першого рядка, обнуляючи тим самим стовпець під ним.
Після того, як зазначені перетворення були здійснені, перший рядок і перший стовпець подумки викреслюють і продовжують поки не залишиться матриця нульового розміру. Якщо на якийсь із ітерацій серед елементів першого стовпця не знайшовся ненульовий, то переходять до наступного стовпцю і проробляють аналогічну операцію.
На першому етапі (прямий хід) система приводиться до східчастого (зокрема, трикутникове) виду.
Наведена нижче система має ступінчастий вигляд:
,
де
Коефіцієнти aii називаються головними (провідними) елементами системи.
1-й крок.
Будемо вважати, що елемент (якщо a11 = 0, переставимо рядка матриці так, щоб a 11 не був рівний 0. Це завжди можливо, тому що в іншому випадку матриця містить нульовий стовпець, її визначник дорівнює нулю і система несовместна).
Перетворимо систему, виключивши невідоме х1 у всіх рівняннях, крім першого (використовуючи елементарні перетворення системи). Для цього помножимо обидві частини першого рівняння на і складемо почленно з другим рівнянням системи (або з другого рівняння почленно віднімемо перше, помножене на). Потім помножимо обидві частини першого рівняння на і складемо з третім рівнянням системи (або з третього почленно віднімемо перше, помножене на). Таким чином, послідовно множимо перший рядок на число і додаємо до i -й рядку, для i = 2, 3, ..., n.
Продовжуючи цей процес, отримаємо еквівалентну систему:
Тут - Нові значення коефіцієнтів при невідомих і вільні члени в останніх m-1 рівняннях системи, які визначаються формулами:
Таким чином, на першому кроці знищуються всі коефіцієнти, що лежать під першим провідним елементом a 11 0, на другому кроці знищуються елементи, що лежать під другим провідним елементом а 22 (1) (Якщо a 22 (1) 0) і т.д. Продовжуючи цей процес і далі, ми, нарешті, на (m-1) кроці наведемо вихідну систему до трикутної системі.
Якщо в процесі приведення системи до східчастого увазі з'являться нульові рівняння, тобто рівності виду 0 = 0, їх відкидають. Якщо ж з'явиться рівняння виду то це свідчить про несумісної системи.
На цьому прямий хід методу Гаусса закінчується.
2. Зворотний хід.
На другому етапі здійснюється так званий зворотний хід, суть якого полягає в тому, щоб висловити все що вийшли базисні змінні через небазисних і побудувати фундаментальну систему рішень, або, якщо всі змінні є базисними, то висловити в чисельному вигляді єдине рішення системи лінійних рівнянь.
Ця процедура починається з останнього рівняння, з якого виражають відповідну базисну змінну (вона в ньому всього одна) і підставляють в попередні рівняння, і так далі, піднімаючись по В«сходинкахВ» наверх.
Кожній строчці відповідає рівно одна базисна змінна, тому на кожному кроці, крім останнього (самого верхнього), ситуація в точності повторює випадок останнього рядка.
Примітка: на практиці зручніше працювати не з системою, а з розширеною її матрицею, виконуючи всі елементарні перетворення над її рядками. Зручно, щоб коефіцієнт a11 був рівний 1 (рівняння переставити місцями, або розділити обидві частини рівняння на a11).
2.2 Приклади розв'язання СЛАР методом Гауса
В даному ...
