метод Гаусса

1. Історія
2. опис методу
3. Умова спільності
4. алгоритм
5. найпростіший випадок
6. приклад
7. Застосування і модифікації
8. переваги методу
9. Див. також
10. Примітки
11. література

метод Гаусса [1] - класичний метод вирішення системи лінійних алгебраїчних рівнянь (СЛАР). Це метод послідовного виключення змінних , Коли за допомогою елементарних перетворень система рівнянь приводиться до еквівалентної системі ступеневої (або трикутного) виду, з якої послідовно, починаючи з останніх (за номером) змінних, знаходяться всі інші змінні [2] .

Історія

Хоча в даний час даний метод повсюдно називається методом Гаусса, він був відомий і до К. Ф. Гаусса . Перше відоме опис даного методу - в китайському трактаті « Математика в дев'яти книгах », Складеному між I ст. до н.е. і II ст. н. е.

опис методу

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

матриця називається головного датчика системи, - стовпцем вільних членів.

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

При цьому будемо вважати, що базисний мінор (ненульовий мінор максимального порядку) основної матриці знаходиться у верхньому лівому куті, тобто в нього входять тільки коефіцієнти при змінних [3] .

тоді змінні називаються головними змінними. Всі інші називаються вільними.

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

нехай для будь-яких .

Перенесемо вільні змінні за знаки рівності і поділимо кожне з рівнянь системи на свій коефіцієнт при самому лівому ( , де - номер рядка):

,
де

Якщо вільним змінним системи (2) надавати всі можливі значення і вирішувати нову систему щодо головних невідомих знизу вгору (тобто від нижнього рівняння до верхнього), то ми отримаємо всі рішення цієї СЛАР . Так як ця система отримана шляхом елементарних перетворень над вихідною системою (1), то по теоремі про еквівалентність при елементарних перетвореннях системи (1) і (2) еквівалентні, тобто безлічі їх рішень збігаються.

1: Якщо в спільній системі всі змінні головні, то така система є певною.

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

Умова спільності

Згадане вище умова для всіх може бути сформульовано як необхідного і достатнього умови спільності:

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

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

наслідки:

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

алгоритм

опис

алгоритм рішення СЛАР методом Гаусса підрозділяється на два етапи.

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

Метод Гаусса вимагає порядку дій.

Цей метод спирається на:

найпростіший випадок

У найпростішому випадку алгоритм виглядає так:

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

приклад

Покажемо, як методом Гаусса можна вирішити наступну систему:

Обнулив коефіцієнти при у другій і третій рядках. Для цього віднімемо від них першу сходинку, помножену на і , Відповідно:

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

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

На другому етапі дозволимо отримані рівняння в зворотному порядку. маємо:

з третього; з другого, підставивши отримане з першого, підставивши отримані і .

Таким чином вихідна система вирішена.

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

Застосування і модифікації

Крім аналітичного рішення СЛАР , Метод Гаусса також застосовується для:

переваги методу

• Менш трудомісткий в порівнянні з іншими методами.
• Дозволяє однозначно встановити, сумісна система чи ні, і якщо сумісна, знайти її рішення.
• Дозволяє знайти максимальне число лінійно незалежних рівнянь - ранг матриці системи [4] .

Див. також

Лінійна алгебра

Методи оптимізації

Чисельні методи

Примітки

1. ↑ Гаусс, Карл Фрідріх ( 1777 - 1 855 ) - німецький математик , фізик і астроном
2. ↑ Н. Ш. Кремер, 2.3. «Метод Гаусса», стор. 44
3. ↑ Такого розташування мінору можна домогтися перестановкою стовпців основної матриці і відповідної Перенумерація змінних.
4. ↑ Н. Ш. Кремер, 2.4. «Система m лінійних рівнянь з n змінними», стор. 49

література

• Ільїн В. А., Позняк Е. Г. Лінійна алгебра: Підручник для вузів. - 6-е изд., Стер. - М.: ФИЗМАТЛИТ, 2004. - 280 с.
• Амосов А. А., Дубинський Ю. А., Копченова Н. П. Обчислювальні методи для інженерів. - М.: Світ, 1998..
• Бахвалов Н. С., Жидков Н.П., Кобельков Г. Г. Чисельні методи. - 8-е изд. - М.: Лабораторія Базових Знань, 2000..
• Волков Е. А. Чисельні методи. - М.: Физматлит, 2003.
• Корн Г., Корн Т. Довідник з математики для науковців та інженерів. - М.: Наука, 1970. - С. 575-576.
• Кремер Н. Ш., Путко Б. А., Тришин І. М., Фрідман М. Н. Вища математика для економістів / Под ред. Н. Ш. Кремера. - 3-е изд. - М.: ЮНИТИ-ДАНА, 2007. - 479 с. - ISBN 5-238-00991-7