Метад Гауса
Метад Гауса — класічны метад рашэння сістэмы лінейных алгебраічных ураўненняў (СЛАУ). Названы ў гонар нямецкага матэматыка Карла Фрыдрыха Гауса. Гэта метад паслядоўнага выключэння пераменных, калі з дапамогай элементарных пераўтварэнняў сістэма ураўненняў прыводзіцца да раўнасільнай сістэмы трохкутнага выгляду, з якой паслядоўна, пачынаючы з апошніх (па нумары), знаходзяцца ўсе зменныя сістэмы[1].
Гісторыя
Хоць у цяперашні час гэты метад паўсюдна называецца метадам Гауса, ён быў вядомы і да К. Ф. Гауса. Першае вядомае апісанне дадзенага метаду — у кітайскім трактаце «Матэматыка ў дзевяці кнігах».[2]
Апісанне метаду
Няхай зыходная сістэма выглядае наступным чынам:
{\displaystyle }
{\displaystyle }
{\displaystyle }
{\displaystyle }
{\displaystyle }
Тады, згодна з уласцівасці элементарных пераўтварэнняў над радкамі, асноўную матрыцу гэтай сістэмы можна прывесці да ступеньчатага выгляда (гэтыя ж пераўтварэнні трэба ўжываць да слупка свабодных членаў):
{
α
1
j
1
x
j
1
α
1
j
2
x
j
2
… +
α
1
j
r
x
j
r
… +
α
1
j
n
x
j
n
=
β
1
α
2
j
2
x
j
2
… +
α
2
j
r
x
j
r
… +
α
2
j
n
x
j
n
=
β
2
…
α
r
j
r
x
j
r
… +
α
r
j
n
x
j
n
=
β
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.,}
{\displaystyle }
Тады пераменныя
{\displaystyle }
Калі хоць бы адно лік
{\displaystyle }
{\displaystyle }
Хай
{\displaystyle }
{\displaystyle }
Перанясем свабодныя зменныя за знакі роўнасцей і падзелім кожнае з ураўненняў сістэмы на свой каэфіцыент пры самым левым
{\displaystyle }
{\displaystyle }
{\displaystyle }
{
x
j
1
α ^
1
j
2
x
j
2
… +
α ^
1
j
r
x
j
r
=
β ^
1
−
α ^
1
j
r + 1
x
j
r + 1
− … −
α ^
1
j
n
x
j
n
x
j
2
… +
α ^
2
j
r
x
j
r
=
β ^
2
−
α ^
2
j
r + 1
x
j
r + 1
− … −
α ^
2
j
n
x
j
n
…
x
j
r
=
β ^
r
−
α ^
r
j
r + 1
x
j
r + 1
− … −
α ^
r
j
n
x
j
n
,
β ^
i
=
β
i
α
i
j
i
,
α ^
i
j
k
=
α
i
j
k
α
i
j
i
( 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}}{\alpha _{ij_{i}}}},\quad {\widehat {\alpha }}_{ij_{k}}={\frac {\alpha _{ij_{k}}}{\alpha _{ij_{i}}}}\quad (2)}
дзе
{\displaystyle }
Калі свабодным пераменным сістэмы (2) надаваць усе магчымыя значэння і вырашаць новую сістэму адносна галоўных невядомых знізу ўверх (гэта значыць ад ніжняга ўраўненні да верхняга), то мы атрымаем усе рашэнні гэтай СЛАУ. Так як гэтая сістэма атрымана шляхам элементарных пераўтварэнняў над зыходнай сістэмай (1), то па тэарэме аб эквівалентнасці пры элементарных пераўтварэннях сістэмы (1) і (2) раўназначныя, то ёсць мноства іх рашэнняў супадаюць.
 |
Вынікі: 1: Калі ў сумеснай сістэме ўсе зменныя галоўныя, то такая сістэма з'яўляецца вызначанай. 2: Калі колькасць зменных у сістэме прэвасходзіць лік уравненій, то такая сістэма з'яўляецца альбо нявызначанай, альбо несумеснай. |
Крытэрый сумеснасці
Згаданая вышэй ўмова
{\displaystyle }
{\displaystyle }
Нагадаем, што рангам сумеснай сістэмы называецца ранг яе асноўнай матрыцы (альбо пашыранай, так як яны роўныя).
|
Тэарэма Кронекера — Капелі. Сістэма сумесна тады і толькі тады, калі ранг яе асноўнай матрыцы роўнырангу яе пашыранай матрыцы. Вынікі:
|
Алгарытм
Блок схема прадстаўлена на малюнку. Дадзены малюнак адаптаваны для напісання праграмы на мове С/С++, дзе a[0] слупок свабодных членаў.
Апісанне
Алгарытм рашэння СЛАУ метадам Гауса падзяляецца на два этапы.
- На першым этапе ажыццяўляецца так званы прамы ход, калі шляхам элементарных пераўтварэнняў над радкамі сістэму прыводзяць да ступеньчатай або трохкутнай форме, альбо азначаюць, што сістэма несумесная. А менавіта, сярод элементаў першага слупка матрыцы выбіраюць ненулявы, перамяшчаюць яго на крайняе верхняе становішча перастаноўкай радкоў і адымаюць атрыманы пасля перастаноўкі першы радок з астатніх радкоў, дамножыўшы яе на велічыню, роўную адносінах першага элемента кожнай з гэтых радкоў да першага элементу першай радкі, абнуляючы тым самым слупок пад ім. Пасля таго, як названыя пераўтварэнні былі здзейсненыя, першы радок і першы слупок у думках выкрэсліваюць і працягваюць пакуль не застанецца матрыца нулявога памеру. Калі на якой-небудзь з ітэрацый сярод элементаў першага слупка не знайшоўся ненулявы, то пераходзяць да наступнага слупка і праводзяць аналагічную аперацыю.
- На другім этапе ажыццяўляецца так званы зваротны ход, сутнасць якога заключаецца ў тым, каб выказаць усе атрыманыя базісныя зменныя праз нябазісныя і пабудаваць фундаментальную сістэму рашэнняў, альбо, калі ўсе зменныя з’яўляюцца базіснымі, то выказаць у лікавым выглядзе адзінае рашэнне сістэмы лінейных ураўненняў. Гэтая працэдура пачынаецца з апошняга ўраўнення, з якога выказваюць адпаведную базісную зменную (а яна там усяго адна) і падстаўляюць у папярэднія ўраўненні, і гэтак далей, паднімаючыся па «прыступках» наверх. Кожнай радку адпавядае роўна адна базісная пераменная, таму на кожным кроку, акрамя апошняга (самага верхняга), сітуацыя ў дакладнасці паўтарае выпадак апошняй радкі.
Метад Гауса патрабуе
{\displaystyle }
Гэты метад абапіраецца на:
|
Тэарэма (аб прывядзенні матрыц да ступенчатага выгляда). Любую матрыцу шляхам элементарных прэабразаванняў толькі над радкамі можна прывесці да ступенчатага выгляда. |
Найпросты выпадак
У найпростым выпадку алгарытм выглядае так:
{\displaystyle }
- Прамы ход:
( 2 ) → ( 2 ) − ( 1 ) ⋅ (
a
21
a
11
)
:
a
22
′
⋅
x
2
a
23
′
⋅
x
3
… +
a
2 n
′
⋅
x
n
=
b
2
′
( 3 ) → ( 3 ) − ( 1 ) ⋅ (
a
31
a
11
)
:
a
32
′
⋅
x
2
a
33
′
⋅
x
3
… +
a
3 n
′
⋅
x
n
=
b
3
′
…
( m ) → ( m ) − ( 1 ) ⋅ (
a
m 1
a
11
)
:
a
m 2
′
⋅
x
2
a
m 3
′
⋅
x
3
… +
a
m n
′
⋅
x
n
=
b
n
′
( 3 ) → ( 3 ) − ( 2 ) ⋅ (
a
32
′
a
22
′
)
:
a
33
′ ′
⋅
x
3
… +
a
3 n
′ ′
⋅
x
n
=
b
3
′ ′
…
( m ) → ( m ) − ( m − 1 ) ⋅ (
a
m , n − 1
( m − 2 )
a
m − 1 , n − 1
( m − 2 )
)
:
a
m m
( m − 1 )
⋅
x
m
… +
a
m n
( m − 1 )
⋅
x
n
=
b
m
( 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}}}
- Зваротны ход. З апошняга ненулявога ўраўнення выказваем базісную пераменную праз нябазісныя і падстаўляем у папярэднія ўраўненні. Паўтараючы гэтую працэдуру для ўсіх базісных пераменных, атрымліваем фундаментальнае рашэнне.
Прыклад
Пакажам, як метадам Гауса можна вырашыць наступную сістэму:
{\displaystyle }
{\displaystyle }
{\displaystyle }
{\displaystyle }
{\displaystyle }
{\displaystyle }
{\displaystyle }
{\displaystyle }
На другім этапе дазволім атрыманыя ўраўненні ў зваротным парадку. Маем:
{\displaystyle }
{\displaystyle }
{\displaystyle }
{\displaystyle }
{\displaystyle }
{\displaystyle }
У выпадку, калі лік ураўненняў ў сумеснай сістэме атрымаўся меншы за колькасць невядомых, то тады адказ будзе запісвацца ў выглядзе фундаментальнай сістэмы рашэнняў.
Прымяненне і мадыфікацыі
Акрамя аналітычнага рашэння СЛАУ, метад Гауса таксама ўжываецца для:
- знаходжання матрыцы, зваротнай да дадзенай (да матрыцы справа прыпісваецца адзінкавая такога ж памеру, што і зыходная:
{\displaystyle }
{\displaystyle }
{\displaystyle }
- вызначэння рангу матрыцы (паводле следства з тэарэмы Кронекера—Капеллі ранг матрыцы роўны ліку яе галоўных зменных);
- колькаснага рашэння СЛАУ у тэхнічных дадатках (для памяншэння хібнасці вылічэнняў выкарыстоўваецца Метад Гауса з вылучэннем галоўнага элемента, сутнасць якога заключана ў тым, каб на кожным кроку ў якасці галоўнай пераменнай выбіраць тую, пры якой сярод чарговых радкоў і слупкоў, якія засталіся пасля выкрэслівання, стаіць максімальны па модулю каэфіцыент).
Годнасці метаду
- Для матрыц абмежаванага памеру менш працаёмкі па параўнанні з іншымі метадамі.
- Дазваляе адназначна азначыць, сумесная сістэма або не, і калі сумесная, знайсці яе рашэнне.
- Дазваляе знайсці максімальны лік лінейна незалежных ураўненняў — ранг матрыцы сістэмы[4].
Устойлівасць метаду Гауса
Метад Гауса для дрэнна абумоўленых матрыц каэфіцыентаў з’яўляецца вылічальна няўстойлівым. Напрыклад, для матрыц Гільберта метад прыводзіць да вельмі вялікіх памылак нават пры невялікай памернасці гэтых матрыц. Паменшыць вылічальную памылку можна з дапамогай метаду Гауса з вылучэннем галоўнага элемента, які з’яўляецца ўмоўна устойлівым [5]. Шырокае прымяненне метаду Гауса звязана з тым, што дрэнна абумоўленыя матрыцы сустракаюцца на практыцы адносна рэдка.
Неаптымальнасць метаду Гауса
У 1969 годзе Штрасен даказаў, што вялікія матрыцы можна перамнажаць за час
O (
n
log
2
7
)
O (
n
2
,
81
)
{\displaystyle O(n^{\log _{2}{7}})=O(n^{2{,}81})}
Гл. таксама
Зноскі
- ↑ Н. Ш. Кремер, 2.3. «Метод Гаусса», стр. 44
- ↑ Grcar Joseph F. How ordinary elimination became Gaussian elimination // Historia Mathematica. — В. 2. — Т. 38. — DOI:10.1016/j.hm.2010.06.003 — arΧiv:0907.2397
- ↑ Такого расположения минора можно добиться перестановкой столбцов основной матрицы и соответствующей перенумерацией переменных.
- ↑ Н. Ш. Кремер, 2.4. «Система m линейных уравнений с n переменными», стр. 49
- ↑ УСТОЙЧИВОСТЬ И ТОЧНОСТЬ ПРЯМЫХ МЕТОДОВ(недаступная спасылка)
- ↑ Strassen V. Gaussian Elimination is not Optimal // Numer. Math / F. Brezzi — Springer Science+Business Media, 1969. — Vol. 13, Iss. 4. — P. 354–356. — ISSN 0029-599X; 0945-3245 — doi:10.1007/BF02165411
Літаратура
- Метад Гауса — артыкул з Матэматычнай энцыклапедыі
- Ильин В. А., Позняк Э. Г. Линейная алгебра: Учебник для вузов. — 6-е изд., стер. — М., 2004.
- Амосов А. А., Дубинский Ю. А., Копченова Н. П. Вычислительные методы для инженеров. — М.: Мир, 1998.
- Бахвалов Н. С., Жидков Н. П., Кобельков Г. Г. Численные методы. — 8-е изд. — М.: Лаборатория Базовых Знаний, 2000.
- Волков Е. А. Численные методы. — М.: Физматлит, 2003.
- Справочник по математике для научных работников и инженеров. — М.: Наука, 1970. — С. 575-576.
- Кремер Н. Ш., Путко Б. А., Тришин И. М., Фридман М. Н. Высшая математика для экономистов / Под ред. Н. Ш. Кремера. — 3-е изд. — М.: ЮНИТИ-ДАНА, 2007. — 479 с. — ISBN 5-238-00991-7.
Катэгорыя·Вікіпедыя·Артыкулы з непрацоўнымі спасылкамі
Катэгорыя·Карл Фрыдрых Гаус
Катэгорыя·Вікіпедыя·Артыкулы з крыніцамі з Вікідадзеных
Катэгорыя·Лінейная алгебра