Зворотний хід гауса. Метод гауса чи чому діти не розуміють математику

Нехай дана система , ∆≠0. (1)
Метод Гауса– це метод послідовного виключенняневідомих.

Суть методу Гауса полягає у перетворенні (1) до системи з трикутною матрицею , з якої потім послідовно (зворотним ходом) виходять значення всіх невідомих. Розглянемо одну з обчислювальних схем. Ця схема називається схемою єдиного поділу. Отже, розглянемо цю схему. Нехай a11 ≠0 (провідний елемент) розділимо на a11 перше рівняння. Отримаємо
(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 є вірним.

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

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

Коефіцієнти а 11 22 … називають провідними елементами.
На кожному кроці передбачалося, що провідний елемент відрізняється від нуля. Якщо це не так, то як ведучий можна використовувати будь-який інший елемент, як би переставивши рівняння системи.

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

Метод Гауса призначений для вирішення систем лінійних рівнянь. Належить до прямих методів рішення.

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

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

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

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

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

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

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

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

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

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

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

x 1	x 2	x 3	B
1 / 1 = 1	2 / 1 = 2	-2 / 1 = -2	1 / 1 = 1

Роздільний елемент дорівнює (3).
На місці роздільного елемента отримуємо 1, а в самому стовпці записуємо нулі.
Решта всіх елементів матриці, включаючи елементи стовпця B, визначаються за правилом прямокутника.
Для цього вибираємо чотири числа, які розташовані у вершинах прямокутника і завжди включають роздільну здатність елемент РЕ.

x 1	x 2	x 3	B

0 / 3 = 0	3 / 3 = 1	1 / 3 = 0.33	4 / 3 = 1.33

Роздільний елемент дорівнює (-4).
На місці роздільного елемента отримуємо 1, а в самому стовпці записуємо нулі.
Решта всіх елементів матриці, включаючи елементи стовпця B, визначаються за правилом прямокутника.
Для цього вибираємо чотири числа, які розташовані у вершинах прямокутника і завжди включають роздільну здатність елемент РЕ.
Уявимо розрахунок кожного елемента у вигляді таблиці:

x 1	x 2	x 3	B


0 / -4 = 0	0 / -4 = 0	-4 / -4 = 1	-4 / -4 = 1

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

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

Метод Гауса реалізований багатьма мовами програмування, зокрема: Pascal, C++, php, Delphi, а також є реалізація методу Гауса в онлайн режимі.

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

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

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

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

Для пошуку приватного рішення диференціального рівняння спочатку знаходять похідні відповідного ступеня для записаного приватного рішення (y=f(A,B,C,D)), які підставляють вихідне рівняння. Далі, щоб знайти змінні A, B, C, Dскладається система рівнянь, що вирішується методом Гаусса.

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

У лінійному програмуванні, зокрема в симплекс-методі перетворення симплексной таблиці кожної ітерації використовується правило прямокутника, у якому використовується метод Жордано-Гаусса.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.

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

Про метод

При вирішенні системи лінійних рівнянь онлайн методомГауса виконуються такі кроки.

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

Щоб найкраще зрозуміти принцип роботи алгоритму Гауса онлайн, введіть будь-який приклад, виберіть "дуже докладне рішенняі подивіться його рішення онлайн.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

«Зворотний хід» методу Гауса – отримання рішення системи лінійних рівнянь алгебри (хід «знизу-вгору»). З останнього «нижнього» рівняння отримуємо одне перше рішення – невідому х 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.

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

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

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

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

Установа освіти «Білоруська державна

Сільськогосподарська академія»

Кафедра вищої математики

Методичні вказівки

з вивчення теми «Метод Гауса вирішення систем лінійних

рівнянь» студентами бухгалтерського факультету заочної формиздобуття освіти (НІСПО)

Гірки, 2013

Метод Гауса вирішення систем лінійних рівнянь

Еквівалентні системи рівнянь

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

1) перестановка будь-яких двох рівнянь системи;

2) множення обох частин будь-якого рівняння системи на відмінне від нуля число;

3) додаток до будь-якого рівняння іншого рівняння, помноженого на будь-яке число;

4) креслення рівняння, що з нулів, тобто. рівняння виду.

Гаусові винятки

Розглянемо систему mлінійних рівнянь з nневідомими:

Суть методу Гауса або методу послідовного виключення невідомих полягає у наступному.

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

При виконанні одного кроку гаусового виключення потрібно скористатися наступними правилами:

1) коефіцієнти та вільний член вирішального рівняння залишаються незмінними;

2) коефіцієнти роздільного стовпця, розташовані нижче роздільного коефіцієнта, звертаються в нулі;

3) усі інші коефіцієнти та вільні члени при виконанні першого кроку обчислюються за правилом прямокутника:

, де i=2,3,…,m; j=2,3,…,n.

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

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

Ступінчаста система

має трикутний вигляд і все (i=1,2,…,n). Така система має єдине рішення. Невідомі визначаються, починаючи з останнього рівняння (зворотний перебіг методу Гаусса).

Ступінчаста система має вигляд

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

Ступінчаста система виду

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

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

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

Рішення. Складемо розширену матрицю системи та виконаємо елементарні перетворення:

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