Gauss-Jordanova metoda

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 9. června 2021; kontroly vyžadují 2 úpravy .

Gauss-Jordanova metoda (metoda úplné eliminace neznámých) je metoda, která se používá k řešení čtvercových soustav lineárních algebraických rovnic , nalezení inverze matice , nalezení souřadnic vektoru v dané bázi nebo zjištění pořadí matice . Metoda je modifikací Gaussovy metody . Pojmenováno po C. F. Gaussovi a německém geodetu a matematikovi Wilhelmu Jordanovi [1] .

Algoritmus

Vyberte první levý sloupec matice , který má alespoň jednu nenulovou hodnotu.
Pokud je nejvyšší číslo v tomto sloupci nula, změňte celý první řádek matice za jiný řádek matice, kde v tomto sloupci není žádná nula.
Všechny prvky prvního řádku jsou rozděleny horním prvkem vybraného sloupce.
Od zbývajících řádků se odečte první řádek, vynásobí se prvním prvkem odpovídajícího řádku, aby byl první prvek každého řádku (kromě prvního) nula.
Dále se stejný postup provede s maticí získanou z původní matice po smazání prvního řádku a prvního sloupce.
Po zopakování tohoto postupu jednou se získá horní trojúhelníková matice $n-1$
Od předposledního řádku odečtěte poslední řádek vynásobený příslušným koeficientem tak, aby v předposlední řadě zůstala pouze 1 na hlavní diagonále .
Opakujte předchozí krok pro další řádky. Výsledkem je matice identity a řešení na místě volného vektoru (je nutné s ním provádět všechny stejné transformace).

Rozšířený algoritmus pro nalezení inverzní matice

Nechat dáno :

A={\begin{pmatrix}a_{11}&a_{12}&\cdots &a_{1n}\\a_{21}&a_{22}&\cdots &a_{2n}\\\vdots &\vdots &\ddots &\vdots \\a_{n1}&a_{n2}&\cdots &a_{nn}\end{pmatrix}}\quad a_{11}\neq 0\quad I={\begin{pmatrix}1&0&\ cdots &0\\0&1&\cdots &0\\\vdots &\vdots &\ddots &\vdots \\0&0&\cdots &1\end{pmatrix}}

Pohyb vpřed (algoritmus pro tvorbu nul pod hlavní diagonálou)

Vydělte první řádek matice A číslem , dostaneme: , j je sloupec matice A. $a_{11}$ $a_{1j}^1 = \frac{a_{1j} }{a_{11} }$
Opakujeme kroky pro matici I podle vzorce: , s je sloupec matice I $b_{1s}^1 = \frac{b_{1s} }{a_{11} }$

Dostaneme:

A=\begin{pmatrix} 1 & a_{12}^1 & \cdots & a_{1n}^1 \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \ vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{nn} \end{pmatrix} \qquad I=\begin{pmatrix} b_{11}^1 & 0 & \ cdots & 0 \\ 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 \end{pmatrix}

V prvním sloupci vytvoříme 0: $a_{2j}^{1}=a_{2j}-a_{1j}^{1}a_{21}\ ,\tečky ,\ a_{nj}^{1}=a_{nj}-a_ {1j}^{1}a_{n1}$
Opakujeme kroky pro matici I podle vzorců: $b_{2s}^{1}=b_{2s}-b_{1s}^{1}a_{21}\ ,\tečky ,\ b_{ns}^{1}=b_{ns}-b_ {1s}^{1}a_{n1}$

Dostaneme:

A={\begin{pmatrix}1&a_{12}^{1}&\cdots &a_{1n}^{1}\\0&a_{22}^{1}&\cdots &a_{2n}^{1 }\\\vdots &\vdots &\ddots &\vdots \\0&a_{n2}^{1}&\cdots &a_{nn}^{1}\end{pmatrix}}\qquad I={\begin{pmatrix }b_{11}^{1}&0&\cdots &0\\b_{21}^{1}&1&\cdots &0\\\vdots &\vdots &\ddots &\vdots \\b_{n1}^{1} &0&\cdots &1\end{pmatrix}}

pokračujeme v provádění podobných operací pomocí vzorců: $a_{ij}^k=\frac{a_{ij}^k}{a_{ii} } \qquad a_{ij}^k=a_{ij}^{k-1}-a_{kj}^k a_ {ik}^{k-1}$

pokud

k = 1 \šipka doprava n,i = k + 1 \šipka doprava n,j = 1 \šipka doprava n

Opakujeme kroky pro matici I podle vzorců: $b_{ik}^k=\frac{b_{ik}^k}{a_{ii} } \qquad b_{is}^k=b_{is}^{k-1}-b_{ks}^k a_ {ik}^{k-1}$

pokud

k=1 \to n,\; i=k+1 \to n,\; s=1 \to n

Dostaneme:

A=\begin{pmatrix} 1 & a_{12}^1 & \cdots & a_{1n}^1 \\ 0 & 1 & \cdots & a_{2n}^2 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 \end{pmatrix} \qquad I=\begin{pmatrix} b_{11}^1 & 0 & \cdots & 0 \\ b_{21}^2 & b_ {22}^2 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ b_{n1}^n & b_{n2}^n & \cdots & b_{nn}^n \end {pmatrix}

Zpětný pohyb (algoritmus pro tvorbu nul přes hlavní diagonálu)

Používáme vzorec: , za předpokladu, že $a_{ij}^{k-1}=a_{ij}^{k-1}-a_{ij}^k a_{ik}^i$ $k=n \to 1,\; i=1 \to k-1,\; j=1 \to n$

Opakujeme kroky pro matici I podle vzorce: , za předpokladu, že $b_{is}^{k-1}=b_{is}^{k-1}-b_{is}^k a_{ik}^i$ $k=n \to 1,\; i=1 \to k-1,\; s=1 \to n$

Nakonec dostaneme:

$A=\begin{pmatrix} 1 & 0 & \cdots & 0 \\ 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 \end {pmatrix} \qquad I=A^{-1}$

Příklad

Chcete-li vyřešit následující soustavu rovnic :

\left\{\begin{array}{ccccccl} a &+& b &+& c &=& 0\\ 4a &+& 2b &+& c &=& 1\\ 9a &+& 3b &+& c &=& 3 \end{pole}\vpravo.

Zapíšeme jej ve tvaru matice 3 × 4, kde poslední sloupec je volný člen:

\begin{pmatrix} 1 & 1 & 1 \!& \vline &\! 0 \\ 4 & 2 & 1 \!& \vřádek &\! 1 \\ 9 & 3 & 1 \!& \vřádek &\! 3 \end{pmatrix}

Udělejme následující:

K řádku 2 přidejte: −4 × řádek 1.
K řádku 3 přidejte: −9 × Řádek 1.

Dostaneme:

\begin{pmatrix} 1 &\ 1 &\ 1 \!& \vřádek &\! 0 \\ 0 & -2 & -3 \!& \vřádek &\! 1 \\ 0 & -6 & -8 \!& \vřádek &\! 3 \end{pmatrix}

K řádku 3 přidejte: −3 × řádek 2.
Řádek 2 je dělen −2

\begin{pmatrix} 1 & 1 & 1 \!& \vřádek &\!\ 0 \\ 0 & 1 & {3 \over 2} \!& \vřádek &\! -{1 \over 2} \\ 0 & 0 & 1 \!& \vline &\!\ 0 \end{pmatrix}

K řádku 1 přidejte: −1 × řádek 3.
K řádku 2 přidáme: −3/2 × Řádek 3.

\begin{pmatrix} 1 & 1 & 0 \!& \vřádek &\!\ 0 \\ 0 & 1 & 0 \!& \vřádek &\! -{1 \over 2} \\ 0 & 0 & 1 \!& \vline &\!\ 0 \end{pmatrix}

K řádku 1 přidejte: −1 × řádek 2.

\begin{pmatrix} 1 & 0 & 0 \!& \vřádek &\!\ {1 \over 2} \\ 0 & 1 & 0 \!& \vřádek &\! -{1 \over 2} \\ 0 & 0 & 1 \!& \vline &\!\ 0 \end{pmatrix}

V pravém sloupci dostaneme řešení:

a = \frac{1}{2} \; ; \ b = -\frac{1}{2} \; ; \c=0

Implementace algoritmu v programovacím jazyce C#

jmenný prostor Gauss_Jordan_Method { třída Matematika { /// <shrnutí> /// Gauss-Jordanova metoda (inverzní matice) /// </summary> /// <param name="Matrix">Počáteční matice</param> /// <returns></returns> public static double [,] GaussJordan ( double [,] Matrix ) { int n = Matice . GetLength ( 0 ); //Rozměr počáteční matice double [,] xirtaM = new double [ n , n ]; //Matice identity (požadovaná inverzní matice) for ( int i = 0 ; i < n ; i ++) xirtaM [ i , i ] = 1 ; double [,] Matrix_Big = new double [ n , 2 * n ]; //Společná matice získaná spojením počáteční matice a identity for ( int i = 0 ; i < n ; i ++) for ( int j = 0 ; j < n ; j ++) { Matrix_Big [ i , j ] = Matrix [ i , j ]; Matrix_Big [ i , j + n ] = xirtaM [ i , j ]; } //Posun vpřed (vynulování levého dolního rohu) for ( int k = 0 ; k < n ; k ++) //číslo k-řádku { for ( int i = 0 ; i < 2 * n ; i ++) //číslo sloupce i Matrix_Big [ k , i ] = Matrix_Big [ k , i ] / Matrix [ k , k ]; //Dělení k-řetězce prvním členem !=0 pro převod na jeden for ( int i = k + 1 ; i < n ; i ++) //i-číslo dalšího řádku po k { double K = Matrix_Big [ i , k ] / Matrix_Big [ k , k ]; //Součinitel for ( int j = 0 ; j < 2 * n ; j ++) //číslo j-sloupce dalšího řádku po k Matrix_Big [ i , j ] = Matrix_Big [ i , j ] - Matrix_Big [ k , j ] * K ; //Nulování prvků matice pod prvním členem převedeno na jeden } for ( int i = 0 ; i < n ; i ++) //Aktualizovat, provést změny počáteční matice for ( int j = 0 ; j < n ; j ++) Matice [ i , j ] = Matice_Big [ i , j ]; } //Zpětný pohyb (vynulování pravého horního rohu) for ( int k = n - 1 ; k > - 1 ; k --) //číslo k-řádku { for ( int i = 2 * n - 1 ; i > - 1 ; i --) //číslo sloupce i Matrix_Big [ k , i ] = Matrix_Big [ k , i ] / Matrix [ k , k ]; for ( int i = k - 1 ; i > - 1 ; i --) //i-číslo dalšího řádku po k { double K = Matrix_Big [ i , k ] / Matrix_Big [ k , k ]; for ( int j = 2 * n - 1 ; j > - 1 ; j --) //číslo j-sloupce dalšího řádku po k Matrix_Big [ i , j ] = Matrix_Big [ i , j ] - Matrix_Big [ k , j ] * K ; } } //Oddělte od společné matice for ( int i = 0 ; i < n ; i ++) for ( int j = 0 ; j < n ; j ++) xirtaM [ i , j ] = Matrix_Big [ i , j + n ]; návrat xirtaM ; } } }

Poznámky

↑ Transkripce jména Jordánsko jako „Jordánsko“ je chybná, ale je obecně přijímána a nachází se ve většině ruskojazyčných zdrojů.

Literatura

Atkinson, Kendall A. (1989), Úvod do numerické analýzy (2. vydání), New York: John Wiley & Sons , ISBN 978-0471624899 .
Bolch, Gunter; Greiner, Stefan; de Meer, Hermann & Trivedi, Kishor S. (2006), Sítě řazení do fronty a Markovovy řetězce: Modelování a hodnocení výkonu s aplikacemi počítačových věd (2. vydání), Wiley-Interscience , ISBN 978-0-471-79156-0 .
Calinger, Ronald (1999), A Contextual History of Mathematics , Prentice Hall , ISBN 978-0-02-318285-3 .
Farebrother, RW (1988), Linear Least Squares Computations , STATISTICS: Učebnice a monografie, Marcel Dekker, ISBN 978-0-8247-7661-9
Higham, Nicholas (2002), Přesnost a stabilita numerických algoritmů (2. vydání), SIAM , ISBN 978-0-89871-521-7 .
Katz, Victor J. (2004), A History of Mathematics, Stručná verze , Addison-Wesley , ISBN 978-0-321-16193-2 .
Lipson, Marc & Lipschutz, Seymour (2001), Schaumův nástin teorie a problémů lineární algebry , New York: McGraw-Hill , str. 69–80, ISBN 978-0-07-136200-9 .
Press, W.H.; Teukolsky, SA; Vetterling, WT & Flannery, BP (2007), oddíl 2.2 , Numerické recepty: Umění vědeckého počítání (3. vydání), New York: Cambridge University Press, ISBN 978-0-521-88068-8

Odkazy

Algoritmus pro eliminaci Gauss-Jordan v Pythonu
Kaw, Autar; Kalu, Egwu Numerické metody s aplikacemi: Kapitola 04.06 Gaussova eliminace . University of South Florida (2010). (neurčitý)

Metody řešení SLAE
Přímé metody	Maticová metoda Gaussova metoda Gauss-Jordanova metoda Cramerova metoda LU rozklad Choleský rozklad Metoda zametání
Iterační metody	Jacobiho metoda Gauss-Seidelova metoda Iterační metoda Relaxační metoda Metoda konjugovaného gradientu Metoda bikonjugovaného gradientu Metoda stabilizovaného bikonjugátového gradientu
Všeobecné	inverzní matice Projekční metody pro řešení SLAE Předběžná úprava