Eliminacja Gaussa - Gaussian elimination

W matematyce eliminacja Gaussa , znana również jako redukcja wierszy , jest algorytmem rozwiązywania układów równań liniowych . Składa się z sekwencji operacji wykonywanych na odpowiedniej macierzy współczynników. Sposób ten może być również używany do obliczania stopień matrycy, z determinant o kwadratowej macierzy i odwrotność odwracania sygnału matrycy . Metoda została nazwana na cześć Carla Friedricha Gaussa (1777-1855), chociaż niektóre jej szczególne przypadki – aczkolwiek przedstawione bez dowodów – były znane chińskim matematykom już około 179 roku n.e.

Aby wykonać redukcję wierszy na macierzy, używa się sekwencji elementarnych operacji na wierszach, aby zmodyfikować macierz, aż lewy dolny róg macierzy zostanie wypełniony zerami, tak bardzo jak to możliwe. Istnieją trzy rodzaje podstawowych operacji na wierszach:

• Zamiana dwóch rzędów,
• Mnożenie wiersza przez liczbę niezerową,
• Dodanie wielokrotności jednego wiersza do drugiego.

Korzystając z tych operacji, macierz można zawsze przekształcić w górną macierz trójkątną , a właściwie taką, która jest w postaci schodkowej . Gdy wszystkie wiodące współczynniki (najbardziej od lewej niezerowy wpis w każdym wierszu) mają wartość 1, a każda kolumna zawierająca wiodący współczynnik ma zera w innym miejscu, mówi się, że macierz ma zredukowaną postać schodkową wiersza . Ta ostateczna forma jest wyjątkowa; innymi słowy, jest niezależny od sekwencji używanych operacji na wierszach. Na przykład w następującej sekwencji operacji na wierszach (gdzie dwie operacje elementarne na różnych wierszach są wykonywane w pierwszym i trzecim kroku), macierze trzecia i czwarta są macierzami w postaci schodkowej wierszy, a ostateczna macierz jest unikalnym wierszem zredukowanym forma eszelonowa.

${\ Displaystyle {\ zacznij {bmatrix} 1 i 3 i 1 i 9 \ \ 1 i 1 i 1 i 1 \ \ 3 i 11 i 5 i 35 \ koniec {bmatrix}} \ do {\ zacznij {bmatrix} 1 i 3 i 1 i 9 \ \ 0 i 2 i 2 i 2 i 8 \ \ 0 i 2 i 2 i 8 \ koniec {bmatrix} }\do {\begin{bmatrix}1&3&1&9\\0&-2&-2&-8\\0&0&0&0\end{bmatrix}}\do {\begin{bmatrix}1&0&-2&-3\\0&1&1&4\\0&0&0&0\end{ bmatryca}}}$

Używanie operacji na wierszach do konwersji macierzy na zredukowaną formę schodkową wierszy jest czasami nazywane eliminacją Gaussa-Jordana . W tym przypadku termin eliminacji Gaussa odnosi się do procesu, dopóki nie osiągnie górnej trójkątnej lub (niezredukowanej) postaci schodkowej. Ze względów obliczeniowych, przy rozwiązywaniu układów równań liniowych, czasami lepiej jest zatrzymać operacje na wierszach, zanim macierz zostanie całkowicie zredukowana.

Definicje i przykład algorytmu

Proces redukcji wierszy wykorzystuje elementarne operacje wierszowe i można go podzielić na dwie części. Pierwsza część (czasami nazywana eliminacją do przodu) sprowadza dany system do postaci schodkowej rzędowej , z której można stwierdzić, czy nie ma rozwiązań, rozwiązania jednoznaczne, czy nieskończenie wiele rozwiązań. Druga część (czasami nazywana substytucją zwrotną ) nadal używa operacji na wierszach, dopóki nie zostanie znalezione rozwiązanie; innymi słowy, ustawia macierz w zredukowanej postaci schodkowej wierszy.

Innym punktem widzenia, który okazuje się bardzo przydatny do analizy algorytmu, jest to, że redukcja wierszy powoduje rozkład macierzy macierzystej. Podstawowe operacje na wierszach mogą być postrzegane jako mnożenie po lewej stronie pierwotnej macierzy przez macierze elementarne . Alternatywnie, sekwencja operacji elementarnych, która redukuje pojedynczy wiersz, może być postrzegana jako mnożenie przez macierz Frobeniusa . Następnie pierwsza część algorytmu oblicza rozkład LU , podczas gdy druga część zapisuje oryginalną macierz jako iloczyn jednoznacznie określonej macierzy odwracalnej i jednoznacznie określonej zredukowanej macierzy schodkowej.

Operacje na wierszach

Istnieją trzy rodzaje podstawowych operacji na wierszach, które można wykonać na wierszach macierzy:

1. Zamień pozycje dwóch rzędów.
2. Pomnóż wiersz przez niezerowy skalar .
3. Dodaj do jednego wiersza skalarną wielokrotność drugiego.

Jeśli macierz jest powiązana z układem równań liniowych, to operacje te nie zmieniają zbioru rozwiązań. Dlatego, jeśli celem jest rozwiązanie układu równań liniowych, użycie tych operacji na wierszach może ułatwić zadanie.

Forma Eszelon

Dla każdego wiersza w macierzy, jeśli wiersz nie składa się tylko z zer, to skrajny lewy wpis niezerowy nazywany jest wiodącym współczynnikiem (lub przestawem ) tego wiersza. Jeśli więc dwa wiodące współczynniki znajdują się w tej samej kolumnie, wówczas operacja wierszowa typu 3 może zostać użyta do wyzerowania jednego z tych współczynników. Następnie za pomocą operacji zamiany wierszy można zawsze uporządkować wiersze tak, aby dla każdego wiersza niezerowego wiodący współczynnik znajdował się na prawo od wiodącego współczynnika wiersza powyżej. Jeśli tak jest, to mówi się, że macierz jest w postaci schodkowej wierszy . Tak więc dolna lewa część macierzy zawiera tylko zera, a wszystkie zerowe wiersze znajdują się poniżej wierszy niezerowych. Słowo „echelon” zostało tutaj użyte, ponieważ można z grubsza pomyśleć o uszeregowaniu rzędów według ich rozmiaru, przy czym największy znajduje się na górze, a najmniejszy na dole.

Na przykład poniższa macierz jest w formie schodkowej, a jej wiodące współczynniki są pokazane na czerwono:

${\displaystyle {\początek{bmatrix}0&\kolor {czerwony}{\mathbf {2}}&1&-1\\0&0&\kolor {czerwony}{\mathbf {3}}&1\\\0&0&0&0\koniec {bmatrix}} .}$

Jest w formie schodkowej, ponieważ wiersz zerowy znajduje się na dole, a wiodący współczynnik drugiego wiersza (w trzeciej kolumnie) znajduje się na prawo od wiodącego współczynnika pierwszego wiersza (w drugiej kolumnie).

Mówi się, że macierz jest w postaci schodkowej zredukowanej, jeśli ponadto wszystkie wiodące współczynniki są równe 1 (co można osiągnąć za pomocą operacji na wierszach elementarnych typu 2), a w każdej kolumnie zawierającej wiodący współczynnik wszystkie pozostałe wpisy w tej kolumnie są zerowe (co można osiągnąć za pomocą elementarnych operacji na wierszach typu 3).

Przykład algorytmu

Załóżmy, że celem jest znalezienie i opisanie zbioru rozwiązań następującego układu równań liniowych :

${\ Displaystyle {\ zacząć {wyrównany} {4} 2x i {} + {} i Y {} - {} i Z {} = {} i 8 i \ qquad (L_ {1}) \ \ 3 x {} - {} i Y { }+{}&2z&{}={}&-11&\qquad (L_{2})\\-2x&{}+{}&y&{}+{}&2z&{}={}&-3&\qquad (L_{ 3})\end{wyrównany}}}$

Poniższa tabela przedstawia proces redukcji wierszy zastosowany jednocześnie do układu równań i związanej z nim macierzy rozszerzonej . W praktyce zwykle nie zajmuje się systemami w kategoriach równań, ale zamiast tego wykorzystuje się macierz rozszerzoną, która jest bardziej odpowiednia do manipulacji komputerowych. Procedurę redukcji rzędów można podsumować następująco: usuń x ze wszystkich równań poniżej L ₁ , a następnie usuń y ze wszystkich równań poniżej L ₂ . To nada systemowi formę trójkąta . Następnie, stosując podstawienie wsteczne, można rozwiązać każdą niewiadomą.

Układ równań	Operacje na wierszach	Rozszerzona macierz
${\ Displaystyle {\ zacząć {wyrównany} {4} 2x i {} + {} i Y i {} - {} i z {} = {} i 8 i \ \ 3 x i {} - {} i y {} + {} i 2 Z i {} = {}&-11&\\-2x&{}+{}&y&{}+{}&2z&{}={}&-3&\end{alignedat}}}$		${\ Displaystyle \ lewo [{\ zacząć {tablica} {rrr | r} 2 i 1 i 1 i 8 \ \ 3 i 1 i 2 i 11 \ \ 2 i 1 i 2 i 3 \ koniec {tablica}} \ prawo]}$
${\ Displaystyle {\ zacząć {wyrównany} {4}2x i {} + {} i Y i {} - {} Z i {} = {} i 8 i \ \ & & {\ tfrac {1} {2}} Y i {} + {} &{\tfrac {1}{2}}z&{}={}&1&\\&&2lat&{}+{}&z&{}={}&\end{alignedat}}}$	${\ Displaystyle {\ zacząć {wyrównany} L_ {2} + {\ tfrac {3}{2}} L_ {1} i \ do L_ {2} \ \ L_ {3} + L_ {1} i \ do L_ {3}\end{wyrównany}}}$	${\ Displaystyle \ lewo [{\ zacząć {array} {rrr | r} 2 i 1 i 1 i 8 \ \ 0 i {\ Frac {1} {2}} i {\ Frac {1} {2}} i 1 \ \ 0 i 2 i 1 i 5 \ koniec {tablica}}\prawo]}$
${\ Displaystyle {\ zacząć {wyrównany} {4}2x i {} + {} i Y i {} - {} Z i {} = {} i 8 i \ \ & & {\ tfrac {1} {2}} Y i {} + {} &{\tfrac {1}{2}}z&{}={}&1&\\&&&&-z&{}={}&1&\end{alignedat}}}$	${\displaystyle L_{3}+-4L_{2}\do L_{3}}$	${\ Displaystyle \ lewo [{\ zacząć {array} {rrr | r} 2 i 1 i 1 i 8 \ \ 0 i {\ Frac {1} {2}} i {\ Frac {1} {2}} i 1 \ \ 0 i 0 i 1 i 1 \end{tablica}}\right]}$
Macierz jest teraz w formie schodkowej (zwanej również formą trójkątną)
${\ Displaystyle {\ zacząć {wyrównany} {4} 2 x i {} + {} i r i i {} = {} 7 i \ \ i i {\ tfrac {1}{2}} r i & & {} = {}{\ tfrac {3} {2}}&\\&&&{}-{}&z&{}={}1&\end{alignedat}}}$	${\ Displaystyle {\ zacząć {wyrównany} L_ {2} + {\ tfrac {1} {2}} L_ {3} i \ do L_ {2} \ \ L_ {1}-L_ {3} i \ do L_ {1}\end{wyrównany}}}$	${\ Displaystyle \ lewo [{\ zacząć {array} {rrr | r} 2 i 1 i 0 i 7 \\ 0 i {\ Frac {1} {2}} i 0 i {\ Frac {3}{2}} \\ 0 i 0 i 1 i 1 \ koniec { tablica}}\prawo]}$
${\ Displaystyle {\ zacząć {wyrównany} {4}2x i {} + {} i y& \ quad && {} = {} i 7 & \ \ & & y& \ quad && {} = {} i 3 & \ \ & & & \ quad & Z& {} = { }&-1&\end{wyrównany}}}$	${\displaystyle {\zaczynać{wyrównany}2L_{2}&\doL_{2}\\-L_{3}&\doL_{3}\koniec{wyrównany}}}$	${\ Displaystyle \ lewo [{\ rozpocząć {tablica} {rrr | r} 2 i 1 i 0 i 7 \ \ 0 i 1 i 0 i 3 \ \ 0 i 0 i 1 i 1 \ koniec {tablica}} \ po prawej]}$
${\ Displaystyle {\ zacząć {wyrównany} {4}x & \ quad && \ quad && {} = {} i 2 & \ \ & \ quad & y & \ quad && {} = {} i 3 & \ \ & \ quad & & \ quad & z& { }={}&-1&\end{alignedat}}}$	${\ Displaystyle {\ zacząć {wyrównany} L_ {1}-L_ {2} i \ do L_ {1} \ \ {\ tfrac {1} {2}} L_ {1} i \ do L_ {1} \ koniec {wyrównany}}}$	${\ Displaystyle \ lewo [{\ rozpocząć {tablica} {rrr | r} 1 i 0 i 0 i 2 \ \ 0 i 1 i 0 i 3 \ \ 0 i 0 i 1 i 1 \ koniec {tablica}} \ po prawej]}$

Druga kolumna opisuje, które operacje na wierszach zostały właśnie wykonane. Tak więc w pierwszym kroku x jest usuwane z L ₂ przez dodanie 3/2L ₁ do L ₂ . Następnie, x jest usuwany z L ₃ przez dodanie L ₁ do L ₃ . Te operacje na wierszach są oznaczone w tabeli jako

${\ Displaystyle {\ zacząć {wyrównany} L_ {2} + {\ tfrac {3} {2}} L_ {1} i \ do L_ {2} \ \ L_ {3} + L_ {1} i \ do L_{3}.\end{wyrównany}}}$

Po usunięciu y z trzeciego rzędu otrzymujemy układ równań liniowych w postaci trójkąta, a więc pierwsza część algorytmu jest kompletna. Z obliczeniowego punktu widzenia szybsze jest rozwiązywanie zmiennych w odwrotnej kolejności, proces znany jako zastępowanie wsteczne. Widzimy, że rozwiązaniem jest z = −1 , y = 3 i x = 2 . Jest więc unikalne rozwiązanie oryginalnego układu równań.

Zamiast zatrzymywać się, gdy macierz jest w formie schodkowej, można kontynuować, dopóki macierz nie będzie w formie schodkowej o zredukowanych wierszach, jak to ma miejsce w tabeli. Proces redukcji rzędu aż do zredukowania macierzy jest czasami określany jako eliminacja Gaussa-Jordana , aby odróżnić go od zatrzymania po osiągnięciu formy schodkowej.

Historia

Metoda eliminacji Gaussa od pojawi - aczkolwiek bez dowodu - w chińskiej tekst matematyczny Rozdział ósmy: prostokątne tablice z Dziewięć rozdziałów o sztuce Matematycznego . Jego zastosowanie jest zilustrowane w osiemnastu zadaniach, zawierających od dwóch do pięciu równań. Pierwsza wzmianka o księdze pod tym tytułem pochodzi z 179 r. n.e., ale jej fragmenty zostały napisane już około 150 r. p.n.e. Został skomentowany przez Liu Hui w III wieku.

Metoda w Europie wywodzi się z zapisków Izaaka Newtona . W 1670 napisał, że we wszystkich znanych mu książkach z algebry brakowało lekcji rozwiązywania równań równoczesnych, którą następnie dostarczył Newton. Cambridge University ostatecznie opublikował notatki jako Arithmetica Universalis w 1707 roku, długo po tym, jak Newton opuścił życie akademickie. Notatki były szeroko naśladowane, co sprawiło, że (obecnie nazywana) eliminacja Gaussa stała się standardową lekcją w podręcznikach algebry pod koniec XVIII wieku. Carl Friedrich Gauss w 1810 opracował notację symetrycznej eliminacji, która została przyjęta w XIX wieku przez profesjonalne komputery ręczne do rozwiązywania normalnych równań problemów najmniejszych kwadratów. Algorytm nauczany w szkole średniej został nazwany na cześć Gaussa dopiero w latach pięćdziesiątych w wyniku zamieszania w historii przedmiotu.

Niektórzy autorzy używają terminu eliminacja Gaussa, aby odnieść się tylko do procedury, dopóki macierz nie jest w formie schodkowej, a terminu eliminacji Gaussa-Jordana używają w odniesieniu do procedury, która kończy się w formie zredukowanej echelon. Nazwa jest używana, ponieważ jest to odmiana eliminacji Gaussa, opisana przez Wilhelma Jordana w 1888 roku. Jednak metoda ta pojawia się również w artykule Clasena opublikowanym w tym samym roku. Jordan i Clasen prawdopodobnie niezależnie odkryli eliminację Gaussa-Jordana.

Aplikacje

Historycznie pierwszym zastosowaniem metody redukcji rzędów jest rozwiązywanie układów równań liniowych . Oto kilka innych ważnych zastosowań algorytmu.

Wyznaczniki obliczeniowe

Aby wyjaśnić, w jaki sposób eliminacja Gaussa umożliwia obliczenie wyznacznika macierzy kwadratowej, musimy przypomnieć, jak podstawowe operacje na wierszach zmieniają wyznacznik:

• Zamiana dwóch wierszy mnoży wyznacznik przez −1
• Mnożenie wiersza przez niezerowy skalar mnoży wyznacznik przez ten sam skalar
• Dodanie do jednego wiersza wielokrotności skalarnej drugiego nie zmienia wyznacznika.

Jeśli eliminacja Gaussa zastosowana do macierzy kwadratowej A daje macierz schodkową B , niech d będzie iloczynem skalarów, przez które wyznacznik został pomnożony, stosując powyższe zasady. Wtedy wyznacznikiem A jest iloraz przez d iloczynu elementów przekątnej B :

${\ Displaystyle \ det (A) = {\ Frac {\ prod \ operatorname {diag} (B)} {d}}.}$

Obliczeniowo, dla macierzy n × n , ta metoda wymaga tylko operacji arytmetycznych O( n ³ ) , podczas gdy użycie wzoru Leibniza na wyznaczniki wymaga operacji O( n !) (liczba sum we wzorze), a rekurencyjne rozwinięcie Laplace'a wymaga O( 2 ⁿ ) operacje (liczba podwyznaczników do obliczenia, jeśli żaden nie jest liczony dwukrotnie). Nawet na najszybszych komputerach te dwie metody są niepraktyczne lub prawie niewykonalne dla n powyżej 20.

Znajdowanie odwrotności macierzy

Wariant eliminacji Gaussa o nazwie eliminacja Gaussa-Jordana może służyć do znajdowania odwrotności macierzy, jeśli istnieje. Jeśli A jest macierzą kwadratową n × n , to można użyć redukcji wierszy do obliczenia jej macierzy odwrotnej , jeśli istnieje. Po pierwsze, macierz jednostkowa n × n jest powiększana na prawo od A , tworząc macierz blokową n × 2 n [ A | ja ] . Teraz, stosując elementarne operacje na wierszach, znajdź zredukowaną postać schodkową tej macierzy n × 2 n . Macierz A jest odwracalna wtedy i tylko wtedy, gdy lewy blok można zredukować do macierzy jednostkowej I ; w tym przypadku prawym blokiem końcowej macierzy jest A- ¹ . Jeśli algorytm nie jest w stanie zredukować lewego bloku do I , to A nie jest odwracalne.

Rozważmy na przykład następującą macierz:

${\ Displaystyle A = {\ zacząć {bmatrix} 2 i -1 i 0 \ \ -1 i 2 i -1 \ \ 0 i -1 i 2 \ koniec {bmatrix}}.}$

Aby znaleźć odwrotność tej macierzy, bierzemy następującą macierz powiększoną o identyczność i redukujemy ją wierszem jako macierz 3 × 6:

${\ Displaystyle [A | I] = \ lewo [{\ zacząć {tablica} {ccc | CCC} 2 i 1 i 0 i 1 i 0 i 0 \ \ -1 i 2 i 1 i 0 i 1 i 0 \ \ 0 i 1 i 2 i 0 i 0 i 1 \ koniec {tablica}} \ prawo].}$

Wykonując operacje na wierszach, można sprawdzić, czy zredukowana forma schodkowa tej macierzy rozszerzonej jest

${\ Displaystyle [I | B] = \ lewo [{\ zacząć {tablica} {rrr | rrr} 1 i 0 i 0 i {\ Frac {3}{4}} i {\ Frac {1} {2}} i {\ Frac { 1}{4}}\\0&1&0&{\frac {1}{2}}&1&{\frac {1}{2}}\\0&0&1&{\frac {1}{4}}&{\frac {1} {2}}&{\frac {3}{4}}\end{array}}\right].}$

Można myśleć o każdej operacji na wierszu jako o lewym produkcie macierzy elementarnej . Oznaczając przez B iloczyn tych podstawowych macierzy, pokazaliśmy po lewej stronie, że BA = I , a zatem B = A ⁻¹ . Po prawej stronie zachowaliśmy zapis BI = B , o którym wiemy, że jest odwrotnością pożądaną. Ta procedura znajdowania odwrotności działa dla macierzy kwadratowych dowolnej wielkości.

Obliczanie rang i baz

Algorytm eliminacji Gaussa można zastosować do dowolnej macierzy m × n A . W ten sposób, na przykład, niektóre macierze 6 × 9 można przekształcić w macierz, która ma postać schodkową, taką jak

${\ Displaystyle T = {\ zacząć {bmatrix} a&*&*&*&*&*&*&*&*&*\\\0&0&b&*&*&*&*&*&*&*\\\0&0&0&c&*&*&*& *&*\\0&0&0&0&0&0&0&d&*&*\\0&0&0&0&0&0&0&0&e\\0&0&0&0&0&0&0&0&0&0\end{bmatrix}},}$

gdzie gwiazdki są wpisami arbitralnymi, a a , b , c , d , e są niezerowymi wpisami. Ten rzut macierz T zawiera mnóstwo informacji o A : the ranga od A wynosi 5, ponieważ istnieje niezerowe 5 rzędów w T ; miejsca wektora łączone przez kolumny A zawiera bazę składającą się z jego kolumnach 1, 3, 4, 7 i 9 (kolumny z a , b , c , d , e , w T ) oraz gwiazdy pokazują, w jaki sposób inne kolumny z A można zapisać jako kombinacje liniowe kolumn bazowych. Jest to konsekwencja rozdzielności iloczynu skalarnego w wyrażeniu odwzorowania liniowego jako macierzy .

Wszystko to dotyczy również zredukowanej formy schodkowej, która jest szczególnym formatem schodkowym.

Wydajność obliczeniowa

Liczba operacji arytmetycznych wymaganych do wykonania redukcji wierszy jest jednym ze sposobów pomiaru wydajności obliczeniowej algorytmu. Na przykład, aby rozwiązać układ n równań dla n niewiadomych, wykonując operacje na wierszach na macierzy, aż do uzyskania postaci schodkowej, a następnie rozwiązać dla każdej niewiadomej w odwrotnej kolejności, wymaga n ( n + 1)/2 dzieleń, (2 n ³ + 3 n ² - 5 n )/6 mnożenia i (2 n ³ + 3 n ² - 5 n )/6 odejmowania, co daje w sumie około 2 n ³ /3 operacji. Ma więc złożoność arytmetyczną O( n ³ ) ; zobacz notację Big O .

Ta złożoność arytmetyczna jest dobrą miarą czasu potrzebnego na całe obliczenie, gdy czas każdej operacji arytmetycznej jest w przybliżeniu stały. Dzieje się tak w przypadku, gdy współczynniki są reprezentowane przez liczby zmiennoprzecinkowe lub gdy należą do pola skończonego . Jeśli współczynniki są liczbami całkowitymi lub dokładnie przedstawionymi liczbami wymiernymi , wpisy pośrednie mogą rosnąć wykładniczo, więc złożoność bitowa jest wykładnicza. Istnieje jednak wariant eliminacji Gaussa, zwany algorytmem Bareiss , który unika tego wykładniczego wzrostu wpisów pośrednich i, przy tej samej złożoności arytmetycznej O( n ³ ) , ma nieco złożoność O( n ⁵ ) .

Algorytm ten może być używany na komputerze dla systemów z tysiącami równań i niewiadomych. Jednak koszty stają się zaporowe dla systemów z milionami równań. Te duże systemy są zazwyczaj rozwiązywane przy użyciu metod iteracyjnych . Istnieją specyficzne metody dla układów, których współczynniki są zgodne z regularnym wzorem (patrz układ równań liniowych ).

Aby umieścić macierz n × n w zredukowanej postaci schodkowej za pomocą operacji na wierszach, potrzeba n ³ operacji arytmetycznych, co stanowi około 50% więcej kroków obliczeniowych.

Jednym z możliwych problemów jest niestabilność liczbowa spowodowana możliwością dzielenia przez bardzo małe liczby. Jeśli na przykład wiodący współczynnik jednego z wierszy jest bardzo bliski zeru, to aby zmniejszyć macierz wierszy, należałoby podzielić przez tę liczbę. Oznacza to, że każdy błąd występujący dla liczby bliskiej zeru zostanie wzmocniony. Eliminacja Gaussa jest liczbowo stabilna dla macierzy diagonalnie dominujących lub dodatnio określonych . W przypadku ogólnych macierzy eliminacja Gaussa jest zwykle uważana za stabilną, gdy stosuje się częściowe obracanie , mimo że istnieją przykłady stabilnych macierzy, dla których jest ona niestabilna.

Uogólnienia

Eliminację Gaussa można przeprowadzić na dowolnym polu , nie tylko na liczbach rzeczywistych.

Algorytm Buchbergera jest uogólnieniem eliminacji Gaussa do układów równań wielomianowych . To uogólnienie w dużym stopniu zależy od pojęcia porządku jednomianowego . Wybór kolejności zmiennych jest już ukryty w eliminacji Gaussa, przejawiając się jako wybór pracy od lewej do prawej podczas wybierania pozycji obrotu.

Obliczenie rangi tensora rzędu większego niż 2 jest NP-trudne . Dlatego, jeśli P ≠ NP , nie może istnieć wielomianowy analog eliminacji Gaussa dla tensorów wyższego rzędu (macierze są macierzowymi reprezentacjami tensorów rzędu 2).

Pseudo kod

Jak wyjaśniono powyżej, eliminacja Gaussa przekształca daną macierz m × n A w macierz w postaci rzędowo-schodkowej .

W poniższym pseudokod , A[i, j]oznacza wpis macierzy A, w rzędzie ı i kolumnę j o indeksach od 1 w Przemiana odbywa się na miejscu , co oznacza, że pierwotny matrycy traci się na końcu są zastąpione przez jego postaci wiersz EXCELON.

h := 1 /* Initialization of the pivot row */
k := 1 /* Initialization of the pivot column */

while h ≤ m and k ≤ n
    /* Find the k-th pivot: */
    i_max := argmax (i = h ... m, abs(A[i, k]))
    if A[i_max, k] = 0
        /* No pivot in this column, pass to next column */
        k := k+1
    else
         swap rows(h, i_max)
         /* Do for all rows below pivot: */
         for i = h + 1 ... m:
             f := A[i, k] / A[h, k]
             /* Fill with zeros the lower part of pivot column: */
             A[i, k] := 0
             /* Do for all remaining elements in current row: */
             for j = k + 1 ... n:
                 A[i, j] := A[i, j] - A[h, j] * f
         /* Increase pivot row and column */
         h := h + 1
         k := k + 1

Algorytm ten różni się nieco od omawianego wcześniej, wybierając oś o największej wartości bezwzględnej . Taki częściowy obrót może być wymagany, jeżeli w miejscu obrotu wejście matrycy wynosi zero. W każdym razie wybranie największej możliwej wartości bezwzględnej osi poprawia stabilność numeryczną algorytmu, gdy do przedstawiania liczb używa się liczby zmiennoprzecinkowej .

Po zakończeniu tej procedury macierz będzie w postaci schodkowej i odpowiedni układ można rozwiązać przez podstawienie wsteczne .

Zobacz też

• Fangcheng (matematyka)

Bibliografia

Prace cytowane

• Atkinson, Kendall A. (1989), Wprowadzenie do analizy numerycznej (2nd ed.), New York: John Wiley & Sons , ISBN 978-0471624899.
• Bolcha, Guntera; Greinera, Stefana; de Meer, Hermann; Trivedi, Kishor S. (2006), Sieci kolejkowe i łańcuchy Markowa: modelowanie i ocena wydajności z aplikacjami informatyki (2nd ed.), Wiley-Interscience , ISBN 978-0-471-79156-0.
• Calinger, Ronald (1999), Kontekstowa historia matematyki , Prentice Hall , ISBN 978-0-02-318285-3.
• Farebrother, RW (1988), Liniowe obliczenia najmniejszych kwadratów , STATYSTYKA: Podręczniki i monografie, Marcel Dekker, ISBN 978-0-8247-7661-9.
• Lauritzen, Niels, Student Convexity: od Fouriera i Motzkina do Kuhna i Tuckera.
• Golub, Gene H .; Van Loan, Charles F. (1996), Obliczenia macierzy (3rd ed.), Johns Hopkins, ISBN 978-0-8018-5414-9.
• Grcar, Joseph F. (2011a), „Jak zwykła eliminacja stała się eliminacją Gaussa”, Historia Mathematica , 38 (2): 163–218, arXiv : 0907.2397 , doi : 10.1016/j.hm.2010.06.003
• Grcar, Joseph F. (2011b), "matematycy eliminacji Gaussa" (PDF) , Zawiadomienia Amerykańskiego Towarzystwa Matematycznego , 58 (6): 782-792
• Higham, Nicholas (2002), Dokładność i stabilność algorytmów numerycznych (2nd ed.), SIAM , ISBN 978-0-89871-521-7.
• Katz, Victor J. (2004), Historia matematyki , krótka wersja , Addison-Wesley , ISBN 978-0-321-1693-2.
• Kaw, Autar; Kalu, Egwu (2010). „Metody numeryczne z aplikacjami: Rozdział 04.06 Eliminacja Gaussa” (PDF) (1st ed.). Uniwersytet Południowej Florydy.
• Lipson, Marc; Lipschutz, Seymour (2001), zarys teorii Schauma i problemy algebry liniowej , New York: McGraw-Hill , s. 69-80, ISBN 978-0-07-136200-9.
• Prasa, WH; Teukolski SA; Vetterling, WT; Flannery, BP (2007), „Sekcja 2.2” , Przepisy numeryczne: The Art of Scientific Computing (3rd ed.), New York: Cambridge University Press, ISBN 978-0-521-88068-8

Zewnętrzne linki

• Interaktywne narzędzie dydaktyczne