Система лінійних алгебраїчних рівнянь
Поняття системи лінійних алгебраїчних рівнянь
Система рівнянь - це умова, що складається в одночасному виконанні декількох рівнянь щодо кількох змінних. Системою лінійних алгебраїчних рівнянь (далі - СЛАУ), яка містить 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 системи, доповнена стовпцем вільних членів
Рішення системи лінійних алгебраїчних рівнянь
Рішенням системи рівнянь називається упорядкований набір чисел (значень змінних), при підстановці яких замість змінних кожне з рівнянь системи звертається у вірне рівність.
Рішенням системи називається n значень невідомих х1 = c1, x2 = c2, ..., xn = cn, при підстановці яких всі рівняння системи звертаються в вірні рівності. Будь-яке рішення системи можна записати у вигляді матриці-стовпця
Система рівнянь називається сумісною, якщо вона має хоча б одне рішення, і несумісною, якщо вона не має жодного рішення.
Спільна система називається визначеною, якщо вона має єдине рішення, і невизначеною, якщо вона має більше одного рішення. В останньому випадку кожна її рішення називається приватним рішенням системи. Сукупність усіх приватних рішень називається загальним рішенням.
Вирішити систему - це значить з'ясувати, совместна вона чи несовместна. Якщо система сумісна, знайти її спільне рішення.
Дві системи називаються еквівалентними (рівносильними), якщо вони мають одне і те ж спільне рішення. Іншими словами, системи еквівалентні, якщо кожне рішення однієї з них є рішенням інший, і навпаки.
Перетворення, застосування якого перетворює систему в нову систему, еквівалентну вихідній, називається еквівалентним або рівносильним перетворенням. Прикладами еквівалентних перетворень можуть бути такі перетворення: перестановка місцями двох рівнянь системи, перестановка місцями двох невідомих разом з коефіцієнтами у всіх рівнянь, множення обох частин будь-якого рівняння системи на відмінне від нуля число.
Система лінійних рівнянь називається однорідною, якщо всі вільні члени дорівнюють нулю:
Однорідна система завжди сумісна, тому що x1 = x2 = x3 = ... = xn = 0 є рішенням системи. Це рішення називається нульовим або тривіальним.
Метод виключення Гауса
2.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, їх відкидають. Якщо ж з'явиться рівняння виду то це свідчить про несумісної системи.
На цьому прямий хід методу Гаусса закінчується.
Зворотний хід.
На другому етапі здійснюється так званий зворотний хід, суть якого полягає в тому, щоб висловити все отримані базисні змінні через небазисних і побудувати фундаментальну систему рішень, або, якщо всі змінні є базисними, то висловити в чисельному вигляді єдине рішення системи лінійних рівнянь.
Ця процедура починається з останнього рівняння, з якого висловлюють відповідну базисну змінну (вона в ньому всього одна) і підставляють в попередні рівняння, і так далі, піднімаючись по «сходинках» наверх.
Кожному рядку відповідає рівно одна базисна змінна, тому на кожному кроці, крім останнього (самого верхнього), ситуація в точності повторює випадок останнього рядка.
Примітка: на практиці зручніше працювати не з системою, а з розширеною її матрицею, виконуючи всі елементарні перетворення над її рядками. Зручно, щоб коефіцієнт a11 дорівнював 1 (рівняння переставити місцями, або розділити обидві частини рівняння на a11).
Приклади розв'язання СЛАР методом Гауса
У даному розділі на трьох різних прикладах покажемо, як методом Гаусса можна вирішити СЛАУ.
Приклад 1. Вирішити СЛАУ 3-го порядку.
Обнулив коефіцієнти при у другій і третій рядках. Для цього домножити їх на 2 / 3 і 1 відповідно і складемо з першим рядком:
Тепер обнулив коефіцієнт при в третьому рядку, домножити другий рядок на 6 і віднімаючи з неї третю:
В результаті ми привели вихідну систему до трикутного вигляду, тим самим закінчивши перший етап алгоритму.
На другому етапі дозволимо отримані рівняння в зворотному порядку. Маємо:
з третього;
з другого, підставивши отримане
;
з першого, підставивши отримані
і
.
У випадку, якщо число рівнянь у спільній системі вийшло менше числа невідомих, то тоді відповідь буде записуватися у вигляді фундаментальної системи рішень.
Приклад 2. Вирішити невизначену СЛАУ 4-го порядку:
В результаті елементарних перетворень над розширеною матрицею системи
вихідна система звелася до ступінчастою, де кількість рівнянь менше, ніж кількість невідомих:
Тому спільне рішення системи: x2 = 5x4-13x3-3; x1 = 5x4-8x3-1. Якщо покласти, наприклад, що x3 = 0, x4 = 0, то знайдемо одне з приватних рішень цієї системи x1 =- 1, x2 =- 3, x3 = 0, x4 = 0.
Приклад 3. Вирішити СЛАУ четвертого порядку.
Умова:
х1 - 2х2 - х3 + х4 = 1
х1 - 8х2 - 2х3 - 3х4 = -2
2х1 + 2х2 - х3 + 7х4 = 7
х1 + х2 + 2х3 + х4 = 1
Перепишемо систему лінійних алгебраїчних рівнянь в матричну форму. Вийде матриця 4х5, ліворуч від розділової лінії стоять коефіцієнти при змінних, а справа стоять вільні члени.
1 -2 -1 1 | 1
1 -8 -2 -3 | -2
2 лютого -1 7 | 7
1 1 2 1 | 1
Проведемо наступні дії:
з другого рядка віднімемо перший рядок (c трок 2 - рядок 1);
з третього рядка віднімемо перший рядок, помножену на 2 (c трок 3-2 х рядок 1)
з четвертого рядка віднімемо перший рядок (c трок 4 - рядок 1). Отримаємо:
1 -2 -1 1 | 1
0 -6 -1 -4 | -3
0 6 1 5 | 5
0 3 3 0 | 0
Проведемо наступні дії:
до третьої рядку додамо другий рядок (рядок 3 + рядок 2);
четвертий рядок поділимо на 3 (рядок 4 = рядок 4 / 3). Отримаємо:
1 -2 -1 1 | 1
0 -6 -1 -4 | -3
0 0 0 1 | 2
0 1 1 0 | 0
Проведемо наступні дії:
четвертий рядок поставимо на місце другого рядка;
третій рядок поставимо на місце четвертого рядка;
другий рядок поставимо на місце третього рядка. Отримаємо:
1 -2 -1 1 | 1
0 1 1 0 | 0
0 -6 -1 -4 | -3
0 0 0 1 | 2
До третьому рядку додамо другий рядок, помножену на 6 (рядок 3 + 6 × рядок 2). Отримаємо:
1 -2 -1 1 | 1
0 1 1 0 | 0
0 0 5 -4 | -3
0 0 0 1 | 2
Проведемо наступні дії:
до третьої рядку додамо четверту, помножену на 4 (строка3 + 4 × строка4);
з першого рядка віднімемо четвертий рядок (рядок 1 - рядок 4);
третій рядок поділимо на 5 (рядок 3 = рядок 3 / 5). Отримаємо:
1 -2 -1 1 | 1
0 1 1 0 | 0
0 0 1 0 | 1
0 0 0 1 | 2
Проведемо наступні дії:
з другого рядка віднімемо третій рядок (рядок 2 - рядок 3);
до першого рядка додамо третій рядок (рядок 1 + рядок 3). Отримаємо:
1 -2 0 0 | 0
0 1 0 0 | -1
0 0 1 0 | 1
0 0 0 1 | 2
До першої рядку додамо другий рядок, помноженої на 2 (рядок 1 + 2 × рядок 2). Отримаємо:
1 0 0 0 | -2
0 1 0 0 | -1
0 0 1 0 | 1
0 0 0 1 | 2
У лівій частині матриці по головній діагоналі залишилися одні одиниці. У правому стовпчику отримуємо рішення:
х 1 = -2
х 2 = -1
х 3 = 1
х 4 = 2
Переваги та недоліки методу Гаусса
Отже, метод Гаусса застосуємо до будь-якій системі лінійних рівнянь, він ідеально підходить для вирішення систем, що містять більше трьох лінійних рівнянь. Метод Гаусса рішення СЛАР з числовими коефіцієнтами в силу простоти і однотипності виконуваних операцій придатний для рахунку на електронно-обчислювальних машинах.
Переваги методу:
менш трудомісткий порівняно з іншими методами;
дозволяє однозначно встановити, совместна система чи ні, і якщо сумісна, знайти її рішення;
дозволяє знайти максимальне число лінійно незалежних рівнянь - ранг матриці системи.
Істотним недоліком цього методу є неможливість сформулювати умови спільності і визначеності системи залежно від значень коефіцієнтів і вільних членів. З іншого боку, навіть у випадку певної системи цей метод не дозволяє знайти загальні формули, що виражають рішення системи через її коефіцієнти і вільні члени, які необхідно мати при теоретичних дослідженнях.
Крім аналітичного рішення СЛАР, метод Гаусса також застосовується для:
знаходження матриці, оберненої до даної (до матриці справа приписується одинична такого ж розміру, що і початкова: , Після чого
приводиться до вигляду одиничної матриці методом Гауса-Жордана; в результаті на місці початкової одиничної матриці справа виявляється зворотна до вихідної матриця:
);
визначення рангу матриці (згідно слідству з теореми Кронекера-Капеллі ранг матриці дорівнює числу її головних змінних);
чисельного рішення СЛАР в обчислювальній техніці (зважаючи похибки обчислень використовується Метод Гаусса з виділенням головного елемента, суть якого полягає в тому, щоб на кожному кроці в якості головної змінної вибирати ту, при якій серед залишилися після викреслювання чергових рядків і стовпців варто максимальний по модулю коефіцієнт ).
Існують і інші методи рішення і дослідження систем лінійних рівнянь, які позбавлені зазначених недоліків. Ці методи засновані на теорії матриць і визначників.
Список джерел
Кремер Н.Ш., Путко Б.А. Вища математика для економістів. - М.: Учеб. посібник, 1998.
Курош А.Г. Курс вищої алгебри. - М.: Учеб. посібник, 1968.
Довідник з математики для економістів. Під ред. В.І. Єрмакова / / Инфра-М, Москва - 2009.