Метод гауса для вирішення матриць алгоритм приклади. Метод Гауса по-Віленкіну

Дві системи лінійних рівнянь називаються рівносильними, якщо безліч їх рішень збігається.

Елементарні перетворення системи рівнянь – це:

1. Викреслювання із системи тривіальних рівнянь, тобто. таких, у яких всі коефіцієнти дорівнюють нулю;
2. Розмноження будь-якого рівняння на число, відмінне від нуля;
3. Додавання до будь-якого i-го рівняння будь-якого j-то рівняння, помноженого на будь-яке число.

Змінна x i називається вільною, якщо ця змінна не є дозволеною, а вся система рівнянь є дозволеною.

Теорема. Елементарні перетворення переводять систему рівнянь на рівносильну.

Сенс методу Гауса полягає в тому, щоб перетворити вихідну систему рівнянь та отримати рівносильну дозволену або рівносильну несумісну систему.

Отже, метод Гауса складається з наступних кроків:

1. Розглянемо перше рівняння. Виберемо перший ненульовий коефіцієнт та розділимо все рівняння на нього. Отримаємо рівняння, яке деяка змінна x i входить з коефіцієнтом 1;
2. Віднімемо це рівняння з решти, множачи його на такі числа, щоб коефіцієнти при змінній x i в інших рівняннях обнулилися. Отримаємо систему, дозволену щодо змінної x i і рівносильну вихідної;
3. Якщо виникають тривіальні рівняння (рідко, але буває; наприклад, 0 = 0), викреслюємо їх із системи. У результаті рівнянь стає одне менше;
4. Повторюємо попередні кроки трохи більше n разів, де n - число рівнянь у системі. Щоразу вибираємо для «обробки» нову змінну. Якщо виникають суперечливі рівняння (наприклад, 0 = 8), то система несумісна.

В результаті через кілька кроків отримаємо або дозволену систему (можливо, з вільними змінними) або несумісну. Дозволені системи розпадаються на два випадки:

1. Число змінних дорівнює числу рівнянь. Виходить, система визначена;
2. Число змінних більше числарівнянь. Збираємо всі вільні змінні праворуч – отримуємо формули для дозволених змінних. Ці формули так і записуються у відповідь.

От і все! Система лінійних рівнянь вирішена! Це досить простий алгоритм і для його освоєння вам не обов'язково звертатися до репетитора вищої з математики. Розглянемо приклад:

Завдання. Розв'язати систему рівнянь:

Опис кроків:

1. Віднімаємо перше рівняння з другого та третього - отримаємо дозволену змінну x 1;
2. Помножуємо друге рівняння на (−1), а третє рівняння ділимо на (−3) – отримаємо два рівняння, у яких змінна x 2 входить із коефіцієнтом 1;
3. Додаємо друге рівняння до першого, та якщо з третього - віднімаємо. Отримаємо дозволену змінну x 2;
4. Нарешті, віднімаємо третє рівняння з першого - отримуємо дозволену змінну x 3;
5. Отримали дозволену систему, записуємо відповідь.

Загальне рішення спільної системи лінійних рівнянь – це нова система, рівносильна вихідної, у якій всі дозволені змінні виражені через вільні.

Коли може знадобитися загальне рішення? Якщо доводиться робити менше кроків, ніж k (k – це скільки всього рівнянь). Однак причин, з яких процес закінчується на певному кроці l< k , может быть две:

1. Після l-го кроку вийшла система, яка містить рівняння з номером (l + 1). Насправді, це добре, т.к. дозволена система все одно отримана – навіть на кілька кроків раніше.
2. Після l -го кроку отримали рівняння, у якому всі коефіцієнти при змінних дорівнюють нулю, а вільний коефіцієнт відмінний від нуля. Це суперечливе рівняння, отже, система несовместна.

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

Опис кроків:

1. Віднімаємо перше рівняння, помножене на 4, з другого. А також додаємо перше рівняння до третього - отримаємо дозволену змінну x 1;
2. Віднімаємо третє рівняння, помножене на 2, з другого – отримаємо суперечливе рівняння 0 = −5.

Отже, система несумісна, оскільки виявлено суперечливе рівняння.

Завдання. Дослідити спільність та знайти загальне рішення системи:

Опис кроків:

1. Віднімаємо перше рівняння з другого (попередньо помноживши на два) і третього - отримаємо дозволену змінну x 1;
2. Віднімаємо друге рівняння з третього. Оскільки всі коефіцієнти цих рівняннях збігаються, третє рівняння перетвориться на тривіальне. Заодно помножимо друге рівняння на (-1);
3. Віднімаємо з першого рівняння друге - отримаємо дозволену змінну x 2 . Вся система рівнянь тепер також дозволена;
4. Оскільки змінні x 3 і x 4 - вільні, переносимо їх праворуч, щоб висловити дозволені змінні. Це є відповідь.

Отже, система спільна та невизначена, оскільки є дві дозволені змінні (x 1 та x 2) та дві вільні (x 3 та x 4).

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

Нагадаємо, дві системи називаються еквівалентними (рівносильними), якщо множини їх рішень збігаються. Іншими словами, системи еквівалентні, якщо кожне рішення однієї з них є рішенням іншої та навпаки. Еквівалентні системи виходять при елементарні перетворення рівнянь системи:

множення обох частин рівняння на число відмінне від нуля;

додавання до деякого рівняння відповідних частин іншого рівняння, помножених на число відмінне від нуля;

перестановка двох рівнянь.

Нехай дана система рівнянь

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

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

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

Тут
– нові значення коефіцієнтів та вільних членів, які виходять після першого кроку.

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

,

де ,
,…,- Головні елементи системи
.

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

При зворотному ході із останнього рівняння перетвореної ступінчастої системи виражається перше невідоме через решту невідомих
, які називають вільними . Потім вираз змінної з останнього рівняння системи підставляється в передостаннє рівняння та з нього виражається змінна
. Аналогічним чином послідовно визначаються змінні
. Змінні
, виражені через вільні змінні, називаються базисними (Залежними). В результаті виходить загальне розв'язання системи лінійних рівнянь.

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

Технічно зручніше піддавати елементарним перетворенням не самі рівняння системи, а розширену матрицю системи

.

Метод Гауса - універсальний метод, який дозволяє вирішувати не лише квадратні, а й прямокутні системи, у яких кількість невідомих
не дорівнює числу рівнянь
.

Перевага цього методу полягає також у тому, що в процесі вирішення ми одночасно досліджуємо систему на спільність, оскільки, навівши розширену матрицю
до ступінчастого вигляду, легко визначити ранги матриці та розширеної матриці
та застосувати теорему Кронекера - Капеллі .

Приклад 2.1Методом Гауса вирішити систему

Рішення. Число рівнянь
та кількість невідомих
.

Складемо розширену матрицю системи, приписавши праворуч від матриці коефіцієнтів стовпець вільних членів .

Наведемо матрицю до трикутного вигляду; для цього отримуватимемо «0» нижче елементів, що стоять на головній діагоналі за допомогою елементарних перетворень.

Щоб отримати «0» у другій позиції першого стовпця, помножимо перший рядок на (-1) і додамо до другого рядка.

Це перетворення запишемо числом (-1) проти першого рядка і позначимо стрілкою, що йде від першого рядка до другого рядка.

Для отримання «0» у третій позиції першого стовпця, помножимо перший рядок на (-3) і додамо до третього рядка; покажемо цю дію за допомогою стрілки, що йде від першого рядка до третього.

.

В отриманій матриці, записаній другий у ланцюжку матриць, отримаємо «0» у другому стовпці третьої позиції. Для цього помножили другий рядок на (-4) і додали до третього. В отриманій матриці другий рядок помножимо на (-1), а третій - розділимо на (-8). Всі елементи цієї матриці, що лежать нижче за діагональні елементи - нулі.

Так як , система є спільною та певною.

Відповідна останній матриці система рівнянь має трикутний вигляд:

З останнього (третього) рівняння
. Підставимо у друге рівняння та отримаємо
.

Підставимо
і
у перше рівняння, знайдемо


.

Суть методу Гаусса полягає у перетворенні (1) до системи з трикутною матрицею , з якої потім послідовно (зворотним ходом) виходять значення всіх невідомих. Розглянемо одну з обчислювальних схем. Ця схема називається схемою єдиного поділу. Отже, розглянемо цю схему. Нехай a 11 ≠0 (провідний елемент) розділимо на a 11 перше рівняння. Отримаємо
(2)
Користуючись рівнянням (2), легко виключити невідомі x 1 з інших рівнянь системи (для цього достатньо від кожного рівняння відняти рівняння (2) попередньо помножене на відповідний коефіцієнт при x 1), тобто на першому кроці отримаємо
.
Іншими словами, на 1 кроці кожен елемент наступних рядків, починаючи з другого, дорівнює різниці між вихідним елементом та твором його «проекції» на перший стовпець і перший (перетворений) рядок.
Після цього залишивши перше рівняння у спокої, над іншими рівняннями системи, отриманої першому кроці, зробимо аналогічне перетворення: виберемо з них рівняння з провідним елементом і виключимо з його допомогою з інших рівнянь x 2 (крок 2).
Після n кроків замість (1) отримаємо рівносильну систему
(3)
Отже, першому етапі ми отримаємо трикутну систему (3). Цей етап називається прямим ходом.
На другому етапі (зворотний хід) ми знаходимо послідовно (3) значення x n , x n -1 , …, x 1 .
Позначимо отримане рішення за x0. Тоді різницю ε=b-A·x 0 називається нев'язкою.
Якщо ε=0, то знайдене рішення x0 є вірним.

Обчислення за методом Гауса виконуються у два етапи:

1. Перший етап називається прямим перебігом методу. У першому етапі вихідну систему перетворять до трикутному виду.
2. Другий етап називається зворотним ходом. З другого краю етапі вирішують трикутну систему, еквівалентну вихідної.

Призначення методу Гауса

Види методу Гауса

1. Класичний метод Гауса;
2. Модифікації методу Гауса. Однією з модифікацій методу Гаус є схема з вибором головного елемента. Особливістю методу Гауса з вибором головного елемента є така перестановка рівнянь, щоб на k-му кроці провідним елементом виявлявся найбільший за модулем елемент k-го стовпця.
3. Метод Жордано-Гаусса;

Приклад рішення методом Гауса
Вирішимо систему:

Для зручності обчислень поміняємо рядки місцями:

Помножимо 2-й рядок на (2). Додамо 3-й рядок до 2-го

Помножимо 2-й рядок на (-1). Додамо 2-ий рядок до 1-го

З першого рядка виражаємо x 3:
З 2-го рядка виражаємо x 2:
З 3-го рядка виражаємо x 1:

Приклад рішення методом Жордано-Гаусса
Цю ж СЛАУ вирішимо методом Жордано-Гаусса.

Послідовно вибиратимемо роздільну здатність елемент РЕ, який лежить на головній діагоналі матриці.
Роздільний елемент дорівнює (1).



НЕ = СЕ - (А * В) / РЕ
РЕ - роздільна здатність елемент (1), А і В - елементи матриці, що утворюють прямокутник з елементами СТЭ і РЕ.
Подаємо розрахунок кожного елемента у вигляді таблиці:

Реалізація методу Гауса

Використання методу Гауса

Застосування методу Гауса в теорії ігор

Застосування методу Гаусса під час вирішення диференціальних рівнянь

Застосування методу Жордано-Гаусса у лінійному програмуванні

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

Метод Гауса

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

1. Система має єдине рішення (визначник головної матриці системи не дорівнює нулю);
2. Система має безліч рішень;
3. Рішень немає, система несумісна.

Отже, ми маємо систему (нехай у неї буде одне рішення), і ми збираємося вирішувати її методом Гауса. Як це працює?

Метод Гауса складається з двох етапів – прямого та зворотного.

Прямий хід методу Гауса

Спочатку запишемо розширену матрицю системи. Для цього до головної матриці додаємо стовпець вільних членів.

Вся суть методу Гауса полягає в тому, щоб шляхом елементарних перетворень привести цю матрицю до ступінчастого (або як ще кажуть трикутного) виду. У такому вигляді під (або над) головною діагоналлю матриці мають бути одні нулі.

Що можна робити?

1. Можна переставляти рядки матриці місцями;
2. Якщо в матриці є однакові (або пропорційні) рядки, можна видалити їх усі, крім одного;
3. Можна множити чи ділити рядок на будь-яке число (крім нуля);
4. Нульові рядки видаляються;
5. Можна додавати до рядка рядок, помножений на число, відмінне від нуля.

Зворотний хід методу Гауса

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

Коли інтернет завжди під рукою, можна вирішити систему рівнянь методом Гауса онлайн.Достатньо лише вбити в онлайн-калькулятор коефіцієнти. Але погодьтеся, набагато приємніше усвідомлювати, що приклад вирішено не комп'ютерною програмою, а вашим власним мозком.

Приклад розв'язання системи рівнянь методом Гаус

А тепер – приклад, щоб усе стало наочно та зрозуміло. Нехай дана система лінійних рівнянь і потрібно вирішити її методом Гауса:

Спочатку запишемо розширену матрицю:

Тепер займемося перетвореннями. Пам'ятаємо, що нам потрібно досягти трикутного виду матриці. Помножимо 1-ий рядок на (3). Помножимо 2-й рядок на (-1). Додамо 2-й рядок до 1-го і отримаємо:

Потім помножимо 3-й рядок на (-1). Додамо 3-й рядок до 2-го:

Помножимо 1-ий рядок на (6). Помножимо 2-й рядок на (13). Додамо 2-ий рядок до 1-го:

Вуаля – система приведена до відповідного виду. Залишилось знайти невідомі:

Система в цьому прикладі має єдине рішення. Вирішення систем з безліччю рішень ми розглянемо в окремій статті. Можливо, спочатку Ви не знатимете, з чого почати перетворення матриці, але після відповідної практики наб'єте руку і клацатимете СЛАУ методом Гауса як горішки. А якщо Ви раптом зіткнетеся зі СЛАУ, яка виявиться надто міцним горішком, звертайтеся до наших авторів! Ви можете залишивши заявку в Заочнику. Разом ми вирішимо будь-яке завдання!

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

Ми знаємо, що система лінійних рівнянь алгебри може:

1) Не мати рішень (бути несумісний).
2) Мати безліч рішень.
3) Мати єдине рішення.

Як ми пам'ятаємо, правило Крамера і матричний метод непридатні в тих випадках, коли система має безліч рішень або несумісна. Метод Гауса – найбільш потужний та універсальний інструмент для знаходження вирішення будь-якої системи лінійних рівнянь, Котрий у кожному випадкуприведе нас до відповіді! Сам алгоритм методу у всіх трьох випадках працює однаково. Якщо в методах Крамера та матричному необхідні знання визначників, то для застосування методу Гауса необхідно знання лише арифметичних дій, що робить його доступним навіть для школярів початкових класів.

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

1) з трокиматриці можна, можливо переставлятимісцями.

2) якщо в матриці з'явилися (або є) пропорційні (як окремий випадок– однакові) рядки, то слід вилучитиз матриці всі ці рядки крім однієї.

3) якщо в матриці в ході перетворень з'явився нульовий рядок, то його слід також вилучити.

4) рядок матриці можна помножити (розділити)на будь-яке число, відмінне від нуля.

5) до рядка матриці можна додати інший рядок, помножений на число, відмінне від нуля.

У методі Гауса елементарні перетворення не змінюють розв'язання системи рівнянь.

Метод Гауса складається з двох етапів:

1. «Прямий хід» - за допомогою елементарних перетворень привести розширену матрицю системи лінійних рівнянь алгебри до «трикутного» ступінчастого вигляду: елементи розширеної матриці, розташовані нижче головної діагоналі, рівні нулю (хід «згори-вниз»). Наприклад, до такого виду:

Для цього виконаємо такі дії:

1) Нехай ми розглядаємо перше рівняння системи лінійних рівнянь алгебри і коефіцієнт при х 1 дорівнює К. Друге, третє і т.д. рівняння перетворимо наступним чином: кожне рівняння (коефіцієнти при невідомих, включаючи вільні члени) ділимо на коефіцієнт при невідомому х 1 , що стоїть у кожному рівнянні, і множимо на К. Після цього з другого рівняння (коефіцієнти при невідомих і вільні члени) віднімає Отримуємо при х 1 у другому рівнянні коефіцієнт 0. З третього перетвореного рівняння віднімаємо перше рівняння, так доки всі рівняння, крім першого, при невідомому х 1 не будуть мати коефіцієнт 0.

2) Переходимо до наступного рівняння. Нехай це буде друге рівняння і коефіцієнт при х 2 дорівнює М. З усіма «нижчими» рівняннями робимо так, як описано вище. Таким чином, під невідомої х 2 у всіх рівняннях будуть нулі.

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

1. « Зворотній хід» методу Гаусса - отримання рішення системи лінійних рівнянь алгебри (хід «знизу-вгору»). З останнього «нижнього» рівняння отримуємо одне перше рішення – невідоме х n . Для цього розв'язуємо елементарне рівняння А * х n = В. У прикладі, наведеному вище, х 3 = 4. Підставляємо знайдене значення «верхнє» наступне рівняння і вирішуємо його щодо наступної невідомої. Наприклад, х 2 – 4 = 1, тобто. х 2 = 5. І так доти, доки не знайдемо всі невідомі.

приклад.

Розв'яжемо систему лінійних рівнянь методом Гауса, як радять деякі автори:

Запишемо розширену матрицю системи та за допомогою елементарних перетворень наведемо її до ступінчастого вигляду:

Дивимося на ліву верхню сходинку. Там у нас має бути одиниця. Проблема у тому, що у першому стовпці одиниць немає взагалі, тому перестановкою рядків нічого не вирішити. У разі одиницю треба організувати з допомогою елементарного перетворення. Зазвичай це можна зробити кількома способами. Вчинимо так:
1 крок . До першого рядка додаємо другий рядок, помножений на -1. Тобто подумки помножили другий рядок на -1 і виконали додавання першого і другого рядка, при цьому другий рядок у нас не змінилася.

Тепер зліва вгорі "мінус один", що нас цілком влаштує. Хто хоче отримати +1, може виконати додаткову дію: помножити перший рядок на –1 (змінити знак).

2 крок . До другого рядка додали перший рядок, помножений на 5. До третього рядка додали перший рядок, помножений на 3.

3 крок . Перший рядок помножили на -1, в принципі це для краси. У третьому рядку також змінили знак і переставили її на друге місце, таким чином, на другому сходинці у нас з'явилася потрібна одиниця.

4 крок . До третього рядка додали другий рядок, помножений на 2.

5 крок . Третій рядок поділили на 3.

Ознакою, яка свідчить про помилку в обчисленнях (рідше – про друкарську помилку), є «поганий» нижній рядок. Тобто, якби в нас унизу вийшло щось на зразок (0 0 11 |23) , і, відповідно, 11x 3 = 23, x 3 = 23/11, то з великою часткою ймовірності можна стверджувати, що припущена помилка в ході елементарних перетворень.

Виконуємо зворотний хід, в оформленні прикладів часто не переписують саму систему, а рівняння "беруть прямо з наведеної матриці". Зворотний хід, нагадую, працює «знизу нагору». У цьому прикладі вийшов подарунок:

x 3 = 1
x 2 = 3
x 1 + x 2 – x 3 = 1, отже x 1 + 3 – 1 = 1, x 1 = –1

Відповідь: x 1 = -1, x 2 = 3, x 3 = 1

Вирішимо цю саму систему за запропонованим алгоритмом. Отримуємо

4 2 –1 1
5 3 –2 2
3 2 –3 0

Розділимо друге рівняння на 5, а третє – на 3. Отримаємо:

4 2 –1 1
1 0.6 –0.4 0.4
1 0.66 –1 0

Помножимо друге та третє рівняння на 4, отримаємо:

4 2 –1 1
4 2,4 –1.6 1.6
4 2.64 –4 0

Віднімемо з другого та третього рівнянь перше рівняння, маємо:

4 2 –1 1
0 0.4 –0.6 0.6
0 0.64 –3 –1

Розділимо третє рівняння на 0,64:

4 2 –1 1
0 0.4 –0.6 0.6
0 1 –4.6875 –1.5625

Помножимо третє рівняння на 0,4

4 2 –1 1
0 0.4 –0.6 0.6
0 0.4 –1.875 –0.625

Віднімемо з третього рівняння друге, отримаємо «ступінчасту» розширену матрицю:

4 2 –1 1
0 0.4 –0.6 0.6
0 0 –1.275 –1.225

Таким чином, так як у процесі обчислень накопичувалася похибка, отримуємо х3 = 0,96 або приблизно 1.

х 2 = 3 та х 1 = -1.

Вирішуючи таким чином, Ви ніколи не заплутаєтеся у обчисленнях і не зважаючи на похибки обчислень, отримаєте результат.

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

Бажаю успіхів! До зустрічі на заняттях! Репетитор Дмитро Айстраханов.

сайт, при повному або частковому копіюванні матеріалу посилання на першоджерело обов'язкове.