метод Гаусса

1. Критерій спільності [ правити | правити код ]
2. алгоритм [ правити | правити код ]
3. опис [ правити | правити код ]
4. Найпростіший випадок [ правити | правити код ]
5. приклад [ правити | правити код ]

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

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

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

{A 11 x 1 + ... + a 1 nxn = b 1 ... am 1 x 1 + ... + amnxn = bm {\ displaystyle \ left \ {{\ begin {array} {lcr} a_ {11} x_ {1} + \ ldots + a_ {1n} x_ {n} & = & b_ {1} \\\ ldots && \\ a_ {m1} x_ {1} + \ ldots + a_ {mn} x_ {n} & = & b_ {m} \\\ end {array}} \ right.}

Її можна записати в матричному вигляді:

A x = b, {\ displaystyle Ax = b,}

де

A = (a 11 ... a 1 n ... a m 1 ... a m n), x = (x 1 ⋮ x n), b = (b 1 ⋮ b m). (1) {\ displaystyle A = \ left ({\ begin {array} {ccc} a_ {11} & \ ldots & a_ {1n} \\\ ldots && \\ a_ {m1} & \ ldots & a_ {mn} \ end {array}} \ right), \ quad x = \ left ({\ begin {array} {c} x_ {1} \\\ vdots \\ x_ {n} \ end {array}} \ right), \ quad b = \ left ({\ begin {array} {c} b_ {1} \\\ vdots \\ b_ {m} \ end {array}} \ right). \ quad (1)}

Матриця A {\ displaystyle A} називається головного датчика системи, b {\ displaystyle b} - стовпцем вільних членів.

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

{Α 1 j 1 xj 1 + α 1 j 2 xj 2 + ... + α 1 jrxjr + ... + α 1 jnxjn = β 1 α 2 j 2 xj 2 + ... + α 2 jrxjr + ... + α 2 jnxjn = β 2 ... α rjrxjr + ... + α rjnxjn = β r 0 = β r + 1 ... 0 = β m, {\ displaystyle \ left \ {{\ begin {array} {rcl} \ alpha _ {1j_ {1}} x_ { j_ {1}} + \ alpha _ {1j_ {2}} x_ {j_ {2}} + \ ldots + \ alpha _ {1j_ {r}} x_ {j_ {r}} + \ ldots + \ alpha _ { 1j_ {n}} x_ {j_ {n}} & = & \ beta _ {1} \\\ alpha _ {2j_ {2}} x_ {j_ {2}} + \ ldots + \ alpha _ {2j_ {r }} x_ {j_ {r}} + \ ldots + \ alpha _ {2j_ {n}} x_ {j_ {n}} & = & \ beta _ {2} \\ & \ ldots & \\\ alpha _ { rj_ {r}} x_ {j_ {r}} + \ ldots + \ alpha _ {rj_ {n}} x_ {j_ {n}} & = & \ beta _ {r} \\ 0 & = & \ beta _ { r + 1} \\ & \ ldots & \\ 0 & = & \ beta _ {m} \ end {array}} \ right.,}

де α 1 j 1, ..., α r j r ≠ 0. {\ displaystyle \ alpha _ {1j_ {1}}, \ ldots, \ alpha _ {rj_ {r}} \ neq 0.}

При цьому будемо вважати, що базисний мінор (ненульовий мінор максимального порядку) основної матриці знаходиться у верхньому лівому куті, тобто в нього входять тільки коефіцієнти при змінних x j 1, ..., x j r {\ displaystyle x_ {j_ {1}}, \ ldots, x_ {j_ {r}}} [3] .

Тоді змінні x j 1, ..., x j r {\ displaystyle x_ {j_ {1}}, \ ldots, x_ {j_ {r}}} називаються головними змінними. Всі інші називаються вільними.

Якщо хоча б одне число β i ≠ 0 {\ displaystyle \ beta _ {i} \ neq 0} , Де i> r {\ displaystyle i> r} , То розглянута система несовместна , Тобто у неї немає жодного рішення.

Нехай β i = 0 {\ displaystyle \ beta _ {i} = 0} для будь-яких i> r {\ displaystyle i> r} .

Перенесемо вільні змінні за знаки рівності і поділимо кожне з рівнянь системи на свій коефіцієнт при самому лівому x {\ displaystyle x} (Α i j i, i = 1, ..., r {\ displaystyle \ alpha _ {ij_ {i}}, \, i = 1, \ ldots, r} , Де i {\ displaystyle i} - номер рядка):

{Xj 1 + α ^ 1 j 2 xj 2 + ... + α ^ 1 jrxjr = β ^ 1 - α ^ 1 jr + 1 xjr + 1 - ... - α ^ 1 jnxjnxj 2 + ... + α ^ 2 jrxjr = β ^ 2 - α ^ 2 jr + 1 xjr + 1 - ... - α ^ 2 jnxjn ... xjr = β ^ r - α ^ rjr + 1 xjr + 1 - ... - α ^ rjnxjn, β ^ i = β i α iji, α ^ ijk = α ijk α iji (2) {\ displaystyle \ left \ {{\ begin {array} {rcc} x_ {j_ {1}} + {\ widehat {\ alpha}} _ {1j_ {2}} x_ {j_ {2}} + \ ldots + {\ widehat {\ alpha}} _ {1j_ {r}} x_ {j_ {r}} & = & {\ widehat {\ beta}} _ {1} - {\ widehat {\ alpha}} _ {1j_ {r + 1}} x_ {j_ {r + 1}} - \ ldots - {\ widehat {\ alpha}} _ {1j_ {n}} x_ {j_ {n}} \\ x_ {j_ {2}} + \ ldots + {\ widehat {\ alpha}} _ {2j_ {r}} x_ {j_ {r}} & = & {\ widehat {\ beta}} _ {2} - {\ widehat {\ alpha}} _ {2j_ {r + 1}} x_ {j_ {r + 1}} - \ ldots - {\ widehat {\ alpha}} _ {2j_ {n}} x_ {j_ { n}} \\ & \ ldots & \\ x_ {j_ {r}} & = & {\ widehat {\ beta}} _ {r} - {\ widehat {\ alpha}} _ {rj_ {r + 1} } x_ {j_ {r + 1}} - \ ldots - {\ widehat {\ alpha}} _ {rj_ {n}} x_ {j_ {n}} \\\ end {array}} \ right., \ qquad {\ widehat {\ beta}} _ {i} = {\ frac {\ beta _ {i}} {\ alph a _ {ij_ {i}}}}, \ quad {\ widehat {\ alpha}} _ {ij_ {k}} = {\ frac {\ alpha _ {ij_ {k}}} {\ alpha _ {ij_ { i}}}} \ quad (2)} ,

де i = 1, ..., r, k = i + 1, ..., n. {\ Displaystyle i = 1, \ ldots, r, \ quad k = i + 1, \ ldots, n.}

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

наслідки:

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

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

Критерій спільності [ правити | правити код ]

Згадане вище умова β i = 0 {\ displaystyle \ beta _ {i} = 0} для всіх i> r {\ displaystyle i> r} може бути сформульовано як необхідного і достатнього умови спільності:

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

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

наслідки:

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

алгоритм [ правити | правити код ]

Блок схема представлена ​​на малюнку. Даний малюнок адаптований для написання програми на мові С / С ++, де a - розширена матриця, останній рядок в якій - стовпець вільних членів. Кількість рядків - n.

опис [ правити | правити код ]

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

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

Метод Гаусса вимагає O (n 3) {\ displaystyle O (n ^ {3})} арифметичних операцій.

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

Найпростіший випадок [ правити | правити код ]

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

{A 11 ⋅ x 1 + a 12 ⋅ x 2 + ... + a 1 n ⋅ xn = b 1 (1) a 21 ⋅ x 1 + a 22 ⋅ x 2 + ... + a 2 n ⋅ xn = b 2 (2 ) ... am 1 ⋅ x 1 + am 2 ⋅ x 2 + ... + amn ⋅ xn = bm (m) {\ displaystyle \ left \ {{\ begin {array} {lcc} a_ {11} \ cdot x_ {1} + a_ {12} \ cdot x_ {2} + \ ldots + a_ {1n} \ cdot x_ {n} & = b_ {1} & (1) \\ a_ {21} \ cdot x_ {1} + a_ { 22} \ cdot x_ {2} + \ ldots + a_ {2n} \ cdot x_ {n} & = b_ {2} & (2) \\\ ldots && \\ a_ {m1} \ cdot x_ {1} + a_ {m2} \ cdot x_ {2} + \ ldots + a_ {mn} \ cdot x_ {n} & = b_ {m} & (m) \ end {array}} \ right.} (2) → (2) - (1) ⋅ (a 21 a 11): a 22 '⋅ x 2 + a 23' ⋅ x 3 + ... + a 2 n '⋅ xn = b 2' (3) → ( 3) - (1) ⋅ (a 31 a 11): a 32 '⋅ x 2 + a 33' ⋅ x 3 + ... + a 3 n '⋅ xn = b 3' ... (m) → (m) - ( 1) ⋅ (am 1 a 11): am 2 '⋅ x 2 + am 3' ⋅ x 3 + ... + amn '⋅ xn = bn' (3) → (3) - (2) ⋅ (a 32 'a 22 '): a 33' '⋅ x 3 + ... + a 3 n' '⋅ xn = b 3' '... (m) → (m) - (m - 1) ⋅ (am, n - 1 (m - 2) am - 1, n - 1 (m - 2)): amm (m - 1) ⋅ xm + ... + amn (m - 1) ⋅ xn = bm (m - 1) {\ displaystyle {\ begin {array } {ccc} (2) \ to (2) - (1) \ cdot ({\ frac {a_ {21}} {a_ {11}}}) &: & a_ {22} ^ {\ prime} \ cdot x_ {2} + a_ {23} ^ {\ prime} \ cdot x_ {3} + \ ldots + a_ {2n} ^ {\ prime} \ cdot x_ {n} = b_ {2} ^ {\ prime} \\ (3) \ to (3) - (1) \ cdot ({\ frac {a_ {31}} {a_ {11}}}) &: & a_ {32} ^ {\ prime} \ cdot x_ {2} + a_ {33} ^ {\ prime} \ cdot x_ {3} + \ ldots + a_ {3n} ^ {\ prime} \ cdot x_ {n} = b_ {3} ^ {\ Prime} \\\ ldots && \\ (m) \ to (m) - (1) \ cdot ({\ frac {a_ {m1}} {a_ {11}}}) &: & a_ {m2} ^ {\ prime} \ cdot x_ {2} + a_ {m3} ^ {\ prime} \ cdot x_ {3} + \ ldots + a_ {mn} ^ {\ prime} \ cdot x_ {n} = b_ {n } ^ {\ prime} \\ (3) \ to (3) - (2) \ cdot ({\ frac {a_ {32} ^ {\ prime}} {a_ {22} ^ {\ prime}}}) &: & a_ {33} ^ {\ prime \ prime} \ cdot x_ {3} + \ ldots + a_ {3n} ^ {\ prime \ prime} \ cdot x_ {n} = b_ {3} ^ {\ prime \ prime} \\\ ldots && \\ (m) \ to (m) - (m-1) \ cdot ({\ frac {a_ {m, n-1} ^ {(m-2)}} {a_ { m-1, n-1} ^ {(m-2)}}}) &: & a_ {mm} ^ {(m-1)} \ cdot x_ {m} + \ ldots + a_ {mn} ^ {( m-1)} \ cdot x_ {n} = b_ {m} ^ {(m-1)} \ end {array}}}

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

приклад [ правити | правити код ]

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

{2 x + yz = 8 - 3 x - y + 2 z = - 11 - 2 x + y + 2 z = - 3 {\ displaystyle \ left \ {{\ begin {array} {ccc} 2x + yz & = & 8 \\ - 3x-y + 2z & = & - 11 \\ - 2x + y + 2z & = & - 3 \ end {array}} \ right.}

Обнулив коефіцієнти при x {\ displaystyle x} у другій і третій рядках. Для цього додамо до них першу сходинку, помножену на 3 2 {\ displaystyle \ textstyle {\ frac {3} {2}}} і 1 {\ displaystyle 1} , Відповідно:

{2 x + yz = 8 1 2 y + 1 2 z = 1 2 y + z = 5 {\ displaystyle \ left \ {{\ begin {array} {rcc} 2x + yz & = & 8 \\ {\ frac {1} {2}} y + {\ frac {1} {2}} z & = & 1 \\ 2y + z & = & 5 \ end {array}} \ right.}

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

{2 x + yz = 8 1 2 y + 1 2 z = 1 - z = 1 {\ displaystyle \ left \ {{\ begin {array} {rcc} 2x + yz & = & 8 \\ {\ frac {1 } {2}} y + {\ frac {1} {2}} z & = & 1 \\ - z & = & 1 \\\ end {array}} \ right.}

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

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

z = - 1 {\ displaystyle z = -1} з третього; y = 3 {\ displaystyle y = 3} з другого, підставивши отримане z {\ displaystyle z} x = 2 {\ displaystyle x = 2} з першого, підставивши отримані z {\ displaystyle z} і y {\ displaystyle y} .

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

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

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

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

Метод Гаусса для погано обумовлених матриць коефіцієнтів є обчислювально нестійким . Наприклад, для матриць Гільберта метод призводить до дуже великих помилок навіть при невеликій розмірності цих матриць. Зменшити обчислювальну помилку можна за допомогою методу Гаусса з виділенням головного елемента, який є умовно стійким [5] . Широке застосування методу Гаусса пов'язано з тим, що погано обумовлені матриці зустрічаються на практиці відносно рідко.

В 1969 році Штрассен довів, що великі матриці можна перемножити за час O (n log 2 ⁡ 7) = O (n 2, 81) {\ displaystyle O (n ^ {\ log _ {2} {7}}) = O (n ^ { 2 {,} 81})} . [6] Звідси випливає, що звернення матриць і рішення СЛАР можна здійснювати алгоритмами асимптотично більш швидкими по порядку, ніж метод Гаусса. Таким чином, для великих СЛАР метод Гаусса не оптимальний за швидкістю.

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

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

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

1. ↑ Н. Ш. Кремер, 2.3. «Метод Гаусса», стор. 44
2. ↑ Grcar Joseph F. How ordinary elimination became Gaussian elimination // Historia Mathematica. - Т. 38, вип. 2. - С. 163-218. - DOI : 10.1016 / j.hm.2010.06.003 . - arXiv : 0907.2397 .
3. ↑ Такого розташування мінору можна домогтися перестановкою стовпців основної матриці і відповідної Перенумерація змінних.
4. ↑ Н. Ш. Кремер, 2.4. «Система m лінійних рівнянь з n змінними», стор. 49
5. ↑ СТАБІЛЬНІСТЬ ТА ТОЧНІСТЬ ПРЯМИХ МЕТОДІВ (Недоступна посилання)
6. ↑ Strassen V. Gaussian Elimination is not Optimal // Numer. Math - Springer Science + Business Media , 1969. - Vol. 13, Iss. 4. - P. 354-356. - ISSN 0029-599X ; 0945-3245 - doi: 10.1007 / BF02165411

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