Gauss-Jordan módszer

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. június 9-én felülvizsgált verziótól ; az ellenőrzések 2 szerkesztést igényelnek .

A Gauss-Jordan módszer (az ismeretlenek teljes kiküszöbölésének módszere) egy olyan módszer, amelyet lineáris algebrai egyenletrendszerek négyzetes rendszereinek megoldására , egy mátrix inverzének meghatározására , egy adott bázis vektor koordinátáinak vagy rangjának meghatározására használnak. egy mátrixból . A módszer a Gauss-módszer módosítása . C. F. Gaussról és Wilhelm Jordan német földmérőről és matematikusról nevezték el [1] .

Algoritmus

Válassza ki a mátrix első bal oldali oszlopát , amelynek legalább egy nullától eltérő értéke van.
Ha ebben az oszlopban a legfelső szám nulla, akkor változtassa meg a mátrix teljes első sorát a mátrix másik olyan sorával, ahol ebben az oszlopban nincs nulla.
Az első sor összes eleme a kiválasztott oszlop felső elemével van osztva.
A fennmaradó sorokból az első sort kivonjuk, megszorozzuk a megfelelő sor első elemével, hogy minden sor első eleme (az első kivételével) nulla legyen.
Ezután ugyanezt az eljárást az első sor és az első oszlop törlése után az eredeti mátrixból nyert mátrixszal hajtjuk végre.
Az eljárás egyszeri megismétlése után egy felső háromszög alakú mátrixot kapunk $n-1$
Vonja ki az utolsó előtti sorból az utolsó sort, megszorozva a megfelelő együtthatóval úgy, hogy a főátlón csak 1 maradjon az utolsó előtti sorban .
Ismételje meg az előző lépést a következő sorokhoz. Ennek eredményeként egy identitásmátrixot és egy szabad vektor helyett egy megoldást kapunk (az összes transzformációt el kell végezni vele).

Kibővített algoritmus egy mátrix inverzének megtalálásához

Adva legyen :

A={\begin{pmatrix}a_{11}&a_{12}&\cdots &a_{1n}\\a_{21}&a_{22}&\cdots &a_{2n}\\\vponts &\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}}

Előrelépés (a főátló alatti nullák képzésének algoritmusa)

Az A mátrix első sorát elosztjuk -vel, így kapjuk: , j az A mátrix egy oszlopa. $a_{11}$ $a_{1j}^1 = \frac{a_{1j} }{a_{11} }$
Megismételjük a lépéseket az I. mátrixra a következő képlet szerint: , s az I mátrix oszlopa $b_{1s}^1 = \frac{b_{1s} }{a_{11} }$

Kapunk:

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}

Az első oszlopban 0-t fogunk alkotni: $a_{2j}^{1}=a_{2j}-a_{1j}^{1}a_{21}\ ,\dots ,\ a_{nj}^{1}=a_{nj}-a_ {1j}^{1}a_{n1}$
Ismételjük meg az I. mátrix lépéseit a következő képletekkel: $b_{2s}^{1}=b_{2s}-b_{1s}^{1}a_{21}\ ,\dots ,\ b_{ns}^{1}=b_{ns}-b_ {1s}^{1}a_{n1}$

Kapunk:

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&\cpontok &0\\b_{21}^{1}&1&\cpontok &0\\\vpontok &\vpontok &\dpontok &\vpontok \\b_{n1}^{1} &0&\cdots &1\end{pmatrix}}

továbbra is hasonló műveleteket hajtunk végre a képletekkel: $a_{ij}^k=\frac{a_{ij}^k}{a_{ii} } \qquad a_{ij}^k=a_{ij}^{k-1}-a_{kj}^k a_ {ik}^{k-1}$

feltéve, hogy

k = 1 \jobbra n,i = k + 1 \jobbra n,j = 1 \jobbra n

Ismételjük meg az I. mátrix lépéseit a következő képletekkel: $b_{ik}^k=\frac{b_{ik}^k}{a_{ii} } \qquad b_{is}^k=b_{is}^{k-1}-b_{ks}^k a_ {ik}^{k-1}$

feltéve, hogy

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

Kapunk:

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 {pmátrix}

Fordított mozgás (algoritmus nullák képzésére a főátló felett)

A képletet használjuk: , feltéve, hogy $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$

Ismételjük meg a lépéseket az I mátrixra a következő képlet szerint: , feltéve, hogy $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$

Végül megkapjuk:

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

Példa

A következő egyenletrendszer megoldásához :

\left\{\begin{array}{ccccccl} a &+& b &+& c &=& 0\\ 4a &+& 2b &+& c &=& 1\\ 9a &+& 3b &+& c &=& 3 \end{tömb}\jobbra.

3 × 4-es mátrixba írjuk, ahol az utolsó oszlop egy szabad tag:

\begin{pmatrix} 1 & 1 & 1 \!& \vline &\! 0 \\ 4 & 2 & 1 \!& \vline &\! 1 \\ 9 & 3 & 1 \!& \vline &\! 3 \end{pmatrix}

Tegyük a következőket:

A 2. sorhoz adjuk hozzá: −4 × 1. sor.
A 3. sorhoz adjuk hozzá: −9 × 1. sor.

Kapunk:

\begin{pmatrix} 1 &\ 1 &\ 1 \!& \vline &\! 0 \\ 0 & -2 & -3 \!& \vline &\! 1 \\ 0 & -6 & -8 \!& \vline &\! 3 \end{pmatrix}

A 3. sorhoz adjuk hozzá: −3 × 2. sor.
A 2. sort elosztjuk -2-vel

\begin{pmatrix} 1 & 1 & 1 \!& \vline &\!\ 0 \\ 0 & 1 & {3 \over 2} \!& \vline &\! -{1 \over 2} \\ 0 & 0 & 1 \!& \vline &\!\ 0 \end{pmatrix}

Az 1. sorhoz adjuk hozzá: −1 × 3. sor.
A 2. sorhoz hozzáadjuk: −3/2 × 3. sor.

\begin{pmatrix} 1 & 1 & 0 \!& \vline &\!\ 0 \\ 0 & 1 & 0 \!& \vline &\! -{1 \over 2} \\ 0 & 0 & 1 \!& \vline &\!\ 0 \end{pmatrix}

Az 1. sorhoz adjuk hozzá: −1 × 2. sor.

\begin{pmatrix} 1 & 0 & 0 \!& \vline &\!\ {1 \over 2} \\ 0 & 1 & 0 \!& \vline &\! -{1 \over 2} \\ 0 & 0 & 1 \!& \vline &\!\ 0 \end{pmatrix}

A jobb oldali oszlopban a megoldást kapjuk:

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

Az algoritmus megvalósítása C# programozási nyelven

névtér Gauss_Jordan_Method { osztály matematika { /// <összefoglaló> Gauss-Jordan módszer (inverz mátrix) /// </summary> /// <param name="Matrix">Kezdeti mátrix</param> /// <returns></returns> nyilvános statikus kettős [,] GaussJordan ( double [,] Mátrix ) { int n = Mátrix . GetLength ( 0 ); //A kezdeti mátrix mérete double [,] xirtaM = new double [ n , n ]; //Identitásmátrix (kívánt inverz mátrix) for ( int i = 0 ; i < n ; i ++) xirtaM [ i , i ] = 1 ; double [,] Mátrix_Big = new double [ n , 2 * n ]; //A kezdeti mátrix és az azonosság összekapcsolásával kapott közös mátrix for ( int i = 0 ; i < n ; i ++) for ( int j = 0 ; j < n ; j ++) { Mátrix_Big [ i , j ] = Mátrix [ i , j ]; Mátrix_Big [ i , j + n ] = xirtaM [ i , j ]; } //Előrelépés (a bal alsó sarok nullázása) for ( int k = 0 ; k < n ; k ++) //k-sorszám { for ( int i = 0 ; i < 2 * n ; i ++) //i-oszlop száma Mátrix_Big [ k , i ] = Mátrix_Big [ k , i ] / Mátrix [ k , k ]; //A k-karakterlánc elosztása az első !=0 taggal, hogy eggyel konvertálja for ( int i = k + 1 ; i < n ; i ++) //a k után következő sor i-száma { double K = Mátrix_Big [ i , k ] / Matrix_Big [ k , k ]; //Együttható for ( int j = 0 ; j < 2 * n ; j ++) //j - a k után következő sor oszlopának száma Mátrix_Nagy [ i , j ] = Mátrix_Nagy [ i , j ] - Mátrix_Nagy [ k , j ] * K ; //Az első tag alatti mátrixelemek nullázása eggyé konvertálva } for ( int i = 0 ; i < n ; i ++) //Frissítés, a kezdeti mátrix módosítása for ( int j = 0 ; j < n ; j ++) Mátrix [ i , j ] = Mátrix_Big [ i , j ]; } //Visszamozgatás (a jobb felső sarok nullázása) for ( int k = n - 1 ; k > - 1 ; k -- ) //k sorszám { for ( int i = 2 * n - 1 ; i > - 1 ; i --) //i-oszlop száma Mátrix_Big [ k , i ] = Mátrix_Big [ k , i ] / Mátrix [ k , k ]; for ( int i = k - 1 ; i > - 1 ; i --) //a k után következő sor i-száma { double K = Mátrix_Big [ i , k ] / Matrix_Big [ k , k ]; for ( int j = 2 * n - 1 ; j > - 1 ; j --) //j - a k után következő sor oszlopszáma Mátrix_Nagy [ i , j ] = Mátrix_Nagy [ i , j ] - Mátrix_Nagy [ k , j ] * K ; } } //Elkülönül a közös mátrixtól for ( int i = 0 ; i < n ; i ++) for ( int j = 0 ; j < n ; j ++) xirtaM [ i , j ] = Mátrix_Big [ i , j + n ]; return xirtaM ; } } }

Jegyzetek

↑ A Jordan név „Jordánia” átírása hibás, de általánosan elfogadott, és a legtöbb orosz nyelvű forrásban megtalálható.

Irodalom

Atkinson, Kendall A. (1989), An Introduction to Numerical Analysis (2. kiadás), New York: John Wiley & Sons , ISBN 978-0471624899 .
Bolch, Gunter; Greiner, Stefan; de Meer, Hermann és Trivedi, Kishor S. (2006), Queuing Networks and Markov Chains: Modeling and Performance Evaluation with Computer Science Applications (2. kiadás), Wiley-Interscience , ISBN 978-0-471-79156-0 .
Calinger, Ronald (1999), A matematika kontextuális története , Prentice Hall , ISBN 978-0-02-318285-3 .
Farebrother, RW (1988), Linear Least Squares Computations , STATISZTIKA: Tankönyvek és monográfiák, Marcel Dekker, ISBN 978-0-8247-7661-9
Higham, Nicholas (2002), Accuracy and Stability of Numerical Algorithms (2. kiadás), SIAM , ISBN 978-0-89871-521-7 .
Katz, Victor J. (2004), A History of Mathematics, Brief Version , Addison-Wesley , ISBN 978-0-321-16193-2 .
Lipson, Marc & Lipschutz, Seymour (2001), Schaum vázlata a lineáris algebra elméletéről és problémáiról , New York: McGraw-Hill , p. 69–80, ISBN 978-0-07-136200-9 .
Press, W.H.; Teukolsky, SA; Vetterling, WT & Flannery, BP (2007), 2.2 . szakasz , Numerikus receptek: The Art of Scientific Computing (3. kiadás), New York: Cambridge University Press, ISBN 978-0-521-88068-8

Linkek

Algoritmus Gauss - Jordan eliminációjához Pythonban
Kaw, Autar; Kalu, Egwu Numerikus módszerek alkalmazásokkal: Fejezet 04.06 Gauss-elimináció . Dél-Floridai Egyetem (2010). (határozatlan)

Az SLAE megoldásának módszerei
Közvetlen módszerek	Mátrix módszer Gauss módszer Gauss-Jordan módszer Cramer módszer LU bomlás Cholesky-bomlás Sweep módszer
Iteratív módszerek	Jacobi módszer Gauss-Seidel módszer Iterációs módszer Relaxációs módszer Konjugált gradiens módszer Bikonjugált gradiens módszer Stabilizált bikonjugátum gradiens módszer
Tábornok	inverz mátrix Vetítési módszerek SLAE megoldására Előkondicionálás