Метад Гауса

Метад Гауса — класічны метад рашэння сістэмы лінейных алгебраічных ураўненняў (СЛАУ). Названы ў гонар нямецкага матэматыка Карла Фрыдрыха Гауса. Гэта метад паслядоўнага выключэння пераменных, калі з дапамогай элементарных пераўтварэнняў сістэма ураўненняў прыводзіцца да раўнасільнай сістэмы трохкутнага выгляду, з якой паслядоўна, пачынаючы з апошніх (па нумары), знаходзяцца ўсе зменныя сістэмы.

Гісторыя

Хоць у цяперашні час гэты метад паўсюдна называецца метадам Гауса, ён быў вядомы і да К. Ф. Гауса. Першае вядомае апісанне дадзенага метаду — у кітайскім трактаце «Матэматыка ў дзевяці кнігах».

Апісанне метаду

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

${\displaystyle }$

Яе можна запісаць у матрычным выглядзе:

${\displaystyle }$

дзе

${\displaystyle }$

Матрыца ${\displaystyle }$ называецца асновай матрыцай сістэмы, ${\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 }$ — нумар радка):

$\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 }$

• Прамы ход:

${\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 }$);
• вызначэння рангу матрыцы (паводле следства з тэарэмы Кронекера—Капеллі ранг матрыцы роўны ліку яе галоўных зменных);
• колькаснага рашэння СЛАУ у тэхнічных дадатках (для памяншэння хібнасці вылічэнняў выкарыстоўваецца Метад Гауса з вылучэннем галоўнага элемента, сутнасць якога заключана ў тым, каб на кожным кроку ў якасці галоўнай пераменнай выбіраць тую, пры якой сярод чарговых радкоў і слупкоў, якія засталіся пасля выкрэслівання, стаіць максімальны па модулю каэфіцыент).

Годнасці метаду

• Для матрыц абмежаванага памеру менш працаёмкі па параўнанні з іншымі метадамі.
• Дазваляе адназначна азначыць, сумесная сістэма або не, і калі сумесная, знайсці яе рашэнне.
• Дазваляе знайсці максімальны лік лінейна незалежных ураўненняў — ранг матрыцы сістэмы.

Устойлівасць метаду Гауса

Метад Гауса для дрэнна абумоўленых матрыц каэфіцыентаў з'яўляецца вылічальна няўстойлівым. Напрыклад, для матрыц Гільберта метад прыводзіць да вельмі вялікіх памылак нават пры невялікай памернасці гэтых матрыц. Паменшыць вылічальную памылку можна з дапамогай метаду Гауса з вылучэннем галоўнага элемента, які з'яўляецца ўмоўна устойлівым . Шырокае прымяненне метаду Гауса звязана з тым, што дрэнна абумоўленыя матрыцы сустракаюцца на практыцы адносна рэдка.

Неаптымальнасць метаду Гауса

У 1969 годзе Штрасен даказаў, што вялікія матрыцы можна перамнажаць за час $O(n^{\log _{2}{7}})=O(n^{2{,}81})$. Адсюль вынікае, што зварот матрыц і рашэнне СЛАУ можна ажыццяўляць алгарытмамі асімптатычна больш хуткімі па парадку, чым метад Гауса. Такім чынам, для вялікіх СЛАУ метад Гауса не аптымальны па хуткасці.

Гл. таксама

• Лінейная алгебра
  • Метад Гауса—Жордана
  • Метад Крамера
  • Сістэма лінейных алгебраічных ураўненняў
  • Тэарэма Кронекера—Капеллі
  • Фундаментальная сістэма рашэнняў
  • Элементарныя пераўтварэнні матрыцы
• Метады аптымізацыі
  • Метад Гауса, аптымізацыя
  • Метад пакаардынатнага спуску (Гауса—Зейдэля)
• Лікавыя метады
  • Метад Гаўса - Зейдэля рашэння сістэмы лінейных ураўненняў
  • Метад Якабі

Літаратура

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