Гаусова елиминација

Гаусова елиминација, такође позната као редна редукција, алгоритам је у линеарној алгебри за решавање система линеарних једначина. Он се обично се схвата као низ операција које се изводе на одговарајућој матрици коефицијената. Ова метода се такође може користити за налажене ранга матрице, за израчунавање детерминанте матрице и за израчунавање инверзибилне квадратне матрице. Метода је добила име по Карлу Фридриху Гаусу (1777-1855), мада је кинеским математичарима била позната још 179. године.

Да би се извршила редна редукција на матрици, користи се низ елементарних редних операција да би се матрица модификовала све док се доњи леви угао матрице не испуни нулама, што је више могуће. Постоје три типа елементарних редних операција:

• Замена два реда,
• Множење реда ненултим бројем,
• Додавање умношка једног реда на други ред.

Помоћу ових операција, матрица се увек може трансформисати у горњу троугласту матрицу, и заправо ону која је у облику редног ешалона. Након што су сви водећи коефицијенти (најлевљи ненулти елементи у сваком реду) 1, и свака колона која садржи водећи коефицијент има нуле на другим местима, каже се да је матрица у облику редукованог редног ешелона. Овај завршни облик је јединствен; другим речима, он је независан од секвенце кориштених редних операција. На пример, у следећем низу редних операција (где вишеструке елементарне операције могу да буду извршене у сваком кораку), трећа и четврта матрица су у редној ешалонској форми, а коначна матрица је јединствена редукована редна ешелонска форма.

$\left[{\begin{array}{rrr|r}1&3&1&9\\1&1&-1&1\\3&11&5&35\end{array}}\right]\to \left[{\begin{array}{rrr|r}1&3&1&9\\0&-2&-2&-8\\0&2&2&8\end{array}}\right]\to \left[{\begin{array}{rrr|r}1&3&1&9\\0&-2&-2&-8\\0&0&0&0\end{array}}\right]\to \left[{\begin{array}{rrr|r}1&0&-2&-3\\0&1&1&4\\0&0&0&0\end{array}}\right]$

Коришћење редних операција за конвертовање матрице у редуковану редну ешалонску форму се понекад назива Гаус–Џордановом елиминацијом. Поједини аутори користе термин Гаусова елиминација као назив процеса којим се формира горња троугаона форма, или (нередукована) редна ешалонска форма. Из рачунских разлога, при решавању система линеарних једначина, понекад је пожељно зауставити редне операције пре него што се матрица потпуно редукује.

Дефиниције и примери алгоритма

Процес редукције редова користи елементарне операције над редовима и може се поделити у два дела. Први део (који се понекад назива елиминација према напред) своди дати систем на редну ешалонску форму, из чега се може знати да ли нема решења, постоји јединствено решење или бесконачно много решења. Други део (који се понекад назива повратна замена) наставља да користи операције над редовима док се не нађе решење; другим речима, матрица се ставља у облик редукованог редног ешелона.

Једно другачије гледиште, која се испоставило као врло корисно за анализу алгоритма, јесте да редукција редова ствара матричну декомпозицију оригиналне матрице. Елементарне операције над редовима могу се посматрати као множење на левој страни оригиналне матрице елементарним матрицама. Алтернативно, низ елементарних операција које редукују појединачни ред могу се посматрати као множење Фробенијусовом матрицом. Тада први део алгоритма израчунава ЛУ декомпозицију, док други део исписује оригиналну матрицу као производ јединствено утврђене инвертибилне матрице и јединствено одређене матрице редукованог ешелона реда.

Ешелонска форма

Главни чланак: Редна ешалонска форма

За сваки ред матрице, ако се ред не састоји само од нула, тада се најлевљи елемент који није нула назива водећим коефицијентом (или пивотом) тог реда. Дакле, ако су два водећа коефицијента у истој колони, тада се редна операција типа 3 може користити да се један од тих коефицијената претвори у нулу. Затим, помоћу операције замене редова, редови се могу поређати тако да је за сваки ненулти ред, водећи коефицијент десно од водећег коефицијента претходног реда. Ако је то случај, каже се да је матрица у облику редног ешалона. Доњи леви део матрице садржи само нуле, и сви нулти редови су испод ненултих редова. Овде се користи реч „ешалон” јер се може сматрати да су редови рангирани по њиховој величини, при чему је највећи на врху, а најмањи на дну.

На пример, следећа матрица је у облику редног ешалона, и њени водећи коефицијенти су приказани црвеном бојом:

${\begin{bmatrix}0&\color {red}{\mathbf {2} }&1&-1\\0&0&\color {red}{\mathbf {3} }&1\\0&0&0&0\end{bmatrix}}.$

Она је у ешалонском је облику зато што је нулти ред на дну, а водећи коефицијент другог реда (у трећој колони) је десно од водећег коефицијента првог реда (у другој колони).

За матрицу се каже да је у облику редукованог редног ешалона ако су сви водећи коефицијенти једнаки 1 (што се може постићи коришћењем елементарних редних операција типа 2) и у свакој колони која садржи водећи коефицијент сви остали елементи су једнаки нули (што се може постићи коришћењем елементарних редних операција типа 3).

Примери алгоритма

Претпоставимо да је циљ да се пронађе и опише скуп решења за следећи систем линеарних једначина:

${\begin{alignedat}{4}2x&{}+{}&y&{}-{}&z&{}={}&8&\qquad (L_{1})\\-3x&{}-{}&y&{}+{}&2z&{}={}&-11&\qquad (L_{2})\\-2x&{}+{}&y&{}+{}&2z&{}={}&-3&\qquad (L_{3})\end{alignedat}}$

Доња табела представља поступак редне редукције који се симултано примјењује на систем једначина и придружену допуњену матрицу. У пракси се обично не ради са системима у смислу једначина, већ се користи допуњена матрица, која је погоднија за рачунарске манипулације. Поступак редне редукције може се сумирати на следећи начин: уклонити x из свих једначина испод L₁, а затим елиминисати y из свих једначина испод L₂. Овим се систем доводи у троугласти облик. Затим се помоћу повратне супституције може решити свака непозната.

Систем једначина	Редне операције	Допуњена матрица
${\begin{alignedat}{4}2x&{}+{}&y&{}-{}&z&{}={}&8&\\-3x&{}-{}&y&{}+{}&2z&{}={}&-11&\\-2x&{}+{}&y&{}+{}&2z&{}={}&-3&\end{alignedat}}$		$\left[{\begin{array}{rrr|r}2&1&-1&8\\-3&-1&2&-11\\-2&1&2&-3\end{array}}\right]$
${\begin{alignedat}{4}2x&{}+{}&y&{}-{}&z&{}={}&8&\\&&{\tfrac {1}{2}}y&{}+{}&{\tfrac {1}{2}}z&{}={}&1&\\&&2y&{}+{}&z&{}={}&5&\end{alignedat}}$	${\begin{aligned}L_{2}+{\tfrac {3}{2}}L_{1}&\to L_{2}\\L_{3}+L_{1}&\to L_{3}\end{aligned}}$	$\left[{\begin{array}{rrr|r}2&1&-1&8\\0&{\frac {1}{2}}&{\frac {1}{2}}&1\\0&2&1&5\end{array}}\right]$
${\begin{alignedat}{4}2x&{}+{}&y&{}-{}&z&{}={}&8&\\&&{\tfrac {1}{2}}y&{}+{}&{\tfrac {1}{2}}z&{}={}&1&\\&&&&-z&{}={}&1&\end{alignedat}}$	$L_{3}+-4L_{2}\to L_{3}$	$\left[{\begin{array}{rrr|r}2&1&-1&8\\0&{\frac {1}{2}}&{\frac {1}{2}}&1\\0&0&-1&1\end{array}}\right]$
Матрица је сад у ешалонској форми (која је исто тако позната као троугаона форма)
${\begin{alignedat}{4}2x&{}+{}&y&&&{}={}7&\\&&{\tfrac {1}{2}}y&&&{}={}{\tfrac {3}{2}}&\\&&&{}-{}&z&{}={}1&\end{alignedat}}$	${\begin{aligned}L_{2}+{\tfrac {1}{2}}L_{3}&\to L_{2}\\L_{1}-L_{3}&\to L_{1}\end{aligned}}$	$\left[{\begin{array}{rrr|r}2&1&0&7\\0&{\frac {1}{2}}&0&{\frac {3}{2}}\\0&0&-1&1\end{array}}\right]$
${\begin{alignedat}{4}2x&{}+{}&y&\quad &&{}={}&7&\\&&y&\quad &&{}={}&3&\\&&&\quad &z&{}={}&-1&\end{alignedat}}$	${\begin{aligned}2L_{2}&\to L_{2}\\-L_{3}&\to L_{3}\end{aligned}}$	$\left[{\begin{array}{rrr|r}2&1&0&7\\0&1&0&3\\0&0&1&-1\end{array}}\right]$
${\begin{alignedat}{4}x&\quad &&\quad &&{}={}&2&\\&\quad &y&\quad &&{}={}&3&\\&\quad &&\quad &z&{}={}&-1&\end{alignedat}}$	${\begin{aligned}L_{1}-L_{2}&\to L_{1}\\{\tfrac {1}{2}}L_{1}&\to L_{1}\end{aligned}}$	$\left[{\begin{array}{rrr|r}1&0&0&2\\0&1&0&3\\0&0&1&-1\end{array}}\right]$

Друга колона описује које су редне операције извршене. У првом кораку је x елиминисано из L₂ додавањем 3/2L₁ на L₂. Затим је x елиминисано из L₃ додавање L₁ на L₃. Ове редне операције су означене у табели као

${\begin{aligned}L_{2}+{\tfrac {3}{2}}L_{1}&\to L_{2},\\L_{3}+L_{1}&\to L_{3}.\end{aligned}}$

Након што је y елиминисано из трећег реда, резултат је систем линеарних једначина троугластог облика, те је тако први део алгоритма окончан. Са рачунарске тачке гледишта, брже је решити променљиве у реверзном редоследу, користећи процес познат као повратна супституција. Може се видети да је решење з = −1, y = 3, и x = 2. У овом случају постоји јединствено решење оригиналног система једначина.

Уместо заустављања након формирања ешалонске форме матрице, могло би се наставити све док матрица не буде у облику редукованог редног ешелона, као што је то учињено у табели. Процес редне редукције док се не формира редукована матрица, понекад се назива и Гаус-Џордановом елиминацијом, да би се разликовао од заустављања након постизања ешалонске форме.

Литература

• Аткинсон, Кендалл А. (1989), Ан Интродуцтион то Нумерицал Аналyсис (2нд изд.), Неw Yорк: Јохн Wилеy & Сонс, ИСБН 978-0471624899 .
• Болцх, Гунтер; Греинер, Стефан; де Меер, Херманн; Триведи, Кисхор С. (2006), Qуеуеинг Нетwоркс анд Марков Цхаинс: Моделинг анд Перформанце Евалуатион wитх Цомпутер Сциенце Апплицатионс (2нд изд.), Wилеy-Интерсциенце, ИСБН 978-0-471-79156-0 .
• Цалингер, Роналд (1999), А Цонтеxтуал Хисторy оф Матхематицс, Прентице Халл, ИСБН 978-0-02-318285-3 .
• Фаребротхер, Р.W. (1988), Линеар Леаст Сqуарес Цомпутатионс, СТАТИСТИЦС: Теxтбоокс анд Монограпхс, Марцел Деккер, ИСБН 978-0-8247-7661-9 .
• Лауритзен, Ниелс, Ундерградуате Цонвеxитy: Фром Фоуриер анд Мотзкин то Кухн анд Туцкер .
• Голуб, Гене Х.; Ван Лоан, Цхарлес Ф. (1996), Матриx Цомпутатионс (3рд изд.), Јохнс Хопкинс, ИСБН 978-0-8018-5414-9 .
• Грцар, Јосепх Ф. (2011а), „Хоw ординарy елиминатион бецаме Гауссиан елиминатион”, Хисториа Матхематица, 38 (2): 163—218, арXив:0907.2397 , дои:10.1016/ј.хм.2010.06.003 
• Грцар, Јосепх Ф. (2011б), „Матхематицианс оф Гауссиан елиминатион” (ПДФ), Нотицес оф тхе Америцан Матхематицал Социетy, 58 (6): 782—792 
• Хигхам, Ницхолас (2002), Аццурацy анд Стабилитy оф Нумерицал Алгоритхмс (2нд изд.), СИАМ, ИСБН 978-0-89871-521-7 .
• Катз, Вицтор Ј. (2004), А Хисторy оф Матхематицс, Бриеф Версион, Аддисон-Wеслеy, ИСБН 978-0-321-16193-2 .
• Каw, Аутар; Калу, Егwу (2010). „Нумерицал Метходс wитх Апплицатионс: Цхаптер 04.06 Гауссиан Елиминатион” (ПДФ) (1ст изд.). Университy оф Соутх Флорида. 
• Липсон, Марц; Липсцхутз, Сеyмоур (2001), Сцхаум'с оутлине оф тхеорy анд проблемс оф линеар алгебра, Неw Yорк: МцГраw-Хилл, стр. 69—80, ИСБН 978-0-07-136200-9 .
• Пресс, WХ; Теуколскy, СА; Веттерлинг, WТ; Фланнерy, БП (2007), „Сецтион 2.2”, Нумерицал Реципес: Тхе Арт оф Сциентифиц Цомпутинг (3рд изд.), Неw Yорк: Цамбридге Университy Пресс, ИСБН 978-0-521-88068-8, Архивирано из оригинала 19. 03. 2012. г., Приступљено 22. 08. 2019 
• Бунцх, Јамес Р.; Хопцрофт, Јохн (1974), „Триангулар фацторизатион анд инверсион бy фаст матриx мултиплицатион”, Матхематицс оф Цомпутатион, 28 (125): 231—236, ИССН 0025-5718, ЈСТОР 2005828, дои:10.2307/2005828 .
• Цормен, Тхомас Х.; Леисерсон, Цхарлес Е.; Ривест, Роналд L.; Стеин, Цлиффорд (2001), Интродуцтион то Алгоритхмс, МИТ Пресс анд МцГраw-Хилл, ИСБН 978-0-262-03293-3 .
• Хорн, Рогер А.; Јохнсон, Цхарлес Р. (1985), Матриx Аналyсис, Цамбридге Университy Пресс, ИСБН 978-0-521-38632-6 . Сее Сецтион 3.5. Н − 1
• Хоусехолдер, Алстон С. (1975), Тхе Тхеорy оф Матрицес ин Нумерицал Аналyсис, Неw Yорк: Довер Публицатионс, МР 0378371 .
• Окунев, Павел; Јохнсон, Цхарлес Р. (1997), Нецессарy Анд Суффициент Цондитионс Фор Еxистенце оф тхе ЛУ Фацторизатион оф ан Арбитрарy Матриx, арXив:матх.НА/0506382  .
• Пооле, Давид (2006), Линеар Алгебра: А Модерн Интродуцтион (2нд изд.), Цанада: Тхомсон Броокс/Цоле, ИСБН 978-0-534-99845-5 .
• Трефетхен, Ллоyд Н.; Бау, Давид (1997), Нумерицал линеар алгебра, Пхиладелпхиа: Социетy фор Индустриал анд Апплиед Матхематицс, ИСБН 978-0-89871-361-9 .

Спољашње везе

• Gaussian Elimination