Gauss-Jordan menetelmä

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 9.6.2021 tarkistetusta versiosta . tarkastukset vaativat 2 muokkausta .

Gauss-Jordan -menetelmä (tuntemattomien täydellisen eliminoinnin menetelmä) on menetelmä, jota käytetään lineaaristen algebrallisten yhtälöiden neliöjärjestelmien ratkaisemiseen , matriisin käänteisarvon löytämiseen, vektorin koordinaattien löytämiseen tietyssä kannassa tai järjestyksen löytämiseen. matriisista . Menetelmä on muunnos Gaussin menetelmästä . Nimetty C. F. Gaussin ja saksalaisen maanmittarin ja matemaatikon Wilhelm Jordanin mukaan [1] .

Algoritmi

Valitse matriisin ensimmäinen vasen sarake , jossa on vähintään yksi nollasta poikkeava arvo.
Jos tämän sarakkeen ylin luku on nolla, muuta matriisin koko ensimmäinen rivi toisella matriisin rivillä, jossa tässä sarakkeessa ei ole nollaa.
Kaikki ensimmäisen rivin elementit jaetaan valitun sarakkeen ylimmällä elementillä.
Jäljelle jäävistä riveistä vähennetään ensimmäinen rivi, joka kerrotaan vastaavan rivin ensimmäisellä elementillä, jotta jokaisen rivin (lukuun ottamatta ensimmäistä) ensimmäinen elementti saadaan nollaksi.
Seuraavaksi sama toimenpide suoritetaan alkuperäisestä matriisista saadulle matriisille ensimmäisen rivin ja ensimmäisen sarakkeen poistamisen jälkeen.
Kun tämä toimenpide on toistettu kerran, saadaan ylempi kolmiomatriisi $n-1$
Vähennä toiseksi viimeisestä rivistä viimeinen rivi kerrottuna sopivalla kertoimella, niin että vain 1 päälävistäjästä jää toiseksi viimeiselle riville .
Toista edellinen vaihe seuraaville riveille. Tuloksena saadaan identiteettimatriisi ja ratkaisu vapaan vektorin tilalle (on tarpeen suorittaa kaikki samat muunnokset sen kanssa).

Laajennettu algoritmi matriisin käänteisarvon löytämiseksi

Anna annettu :

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

Siirto eteenpäin (algoritmi nollien muodostamiseksi päädiagonaalin alle)

Jaetaan matriisin A ensimmäinen rivi luvulla, saadaan: , j on matriisin A sarake. $a_{11}$ $a_{1j}^1 = \frac{a_{1j} }{a_{11} }$
Toistamme vaiheet matriisille I kaavan mukaan: , s on matriisin I sarake $b_{1s}^1 = \frac{b_{1s} }{a_{11} }$

Saamme:

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}

Muodostamme 0 ensimmäiseen sarakkeeseen: $a_{2j}^{1}=a_{2j}-a_{1j}^{1}a_{21}\ ,\dots ,\ a_{nj}^{1}=a_{nj}-a_ {1j}^{1}a_{n1}$
Toistamme vaiheet matriisille I kaavojen mukaisesti: $b_{2s}^{1}=b_{2s}-b_{1s}^{1}a_{21}\ ,\dots ,\ b_{ns}^{1}=b_{ns}-b_ {1s}^{1}a_{n1}$

Saamme:

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&\cpisteet &0\\b_{21}^{1}&1&\cpisteet &0\\\vpisteet &\vpisteet &\dpisteet &\vpisteet \\b_{n1}^{1} &0&\cdots &1\end{pmatrix}}

jatkamme vastaavien toimintojen suorittamista kaavoilla: $a_{ij}^k=\frac{a_{ij}^k}{a_{ii} } \qquad a_{ij}^k=a_{ij}^{k-1}-a_{kj}^k a_ {ik}^{k-1}$

edellyttäen että

k = 1 \ oikea nuoli n, i = k + 1 \ oikea nuoli n, j = 1 \ oikea nuoli n

Toistamme vaiheet matriisille I kaavojen mukaisesti: $b_{ik}^k=\frac{b_{ik}^k}{a_{ii} } \qquad b_{is}^k=b_{is}^{k-1}-b_{ks}^k a_ {ik}^{k-1}$

edellyttäen että

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

Saamme:

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}

Käänteinen liike (algoritmi nollien muodostukselle päädiagonaalin yli)

Käytämme kaavaa: , edellyttäen että $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 \-n$

Toistamme vaiheet matriisille I kaavan mukaan: , edellyttäen, että $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$

Lopulta saamme:

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

Esimerkki

Seuraavan yhtälöjärjestelmän ratkaisemiseksi :

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

Kirjoitamme sen 3 × 4 -matriisin muodossa, jossa viimeinen sarake on vapaa jäsen:

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

Toimitaan seuraavasti:

Lisää riville 2: −4 × rivi 1.
Lisää riville 3: −9 × rivi 1.

Saamme:

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

Lisää riville 3: −3 × rivi 2.
Rivi 2 jaetaan −2:lla

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

Lisää riville 1: −1 × rivi 3.
Riville 2 lisätään: −3/2 × rivi 3.

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

Lisää riville 1: −1 × rivi 2.

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

Oikeassa sarakkeessa saamme ratkaisun:

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

Algoritmin toteutus C#-ohjelmointikielellä

nimiavaruus Gauss_Jordan_Method { luokan matematiikkaa { /// <yhteenveto> /// Gauss-Jordan-menetelmä (käänteismatriisi) /// </summary> /// <param name="Matrix">Alkuperäinen matriisi</param> /// <palauttaa></palauttaa> julkinen staattinen tupla [,] GaussJordan ( double [,] Matrix ) { int n = Matriisi . GetLength ( 0 ); //Alkuperäisen matriisin mitat double [,] xirtaM = uusi tupla [ n , n ]; //Identiteettimatriisi (toivottu käänteimatriisi) for ( int i = 0 ; i < n ; i ++) xirtaM [ i , i ] = 1 ; double [,] Matrix_Big = uusi tupla [ n , 2 * n ]; //Yhteinen matriisi, joka saadaan yhdistämällä alkumatriisi ja identiteetti for ( int i = 0 ; i < n ; i ++) for ( int j = 0 ; j < n ; j ++) { Matriisi_Big [ i , j ] = Matriisi [ i , j ]; Matriisi_Suuri [ i , j + n ] = xirtaM [ i , j ]; } //Siirto eteenpäin (vasemman alakulman nollaus) for ( int k = 0 ; k < n ; k ++) //k-rivin numero { for ( int i = 0 ; i < 2 * n ; i ++) //i-sarakkeen numero Matriisi_iso [ k , i ] = Matriisi_Suuri [ k , i ] / Matriisi [ k , k ]; //K-merkkijonon jakaminen ensimmäisellä jäsenellä !=0 sen muuntamiseksi yhdeksi for ( int i = k + 1 ; i < n ; i ++) //k:n jälkeen seuraavan rivin i-numero { kaksinkertainen K = Matriisi_Suuri [ i , k ] / Matriisi_Suuri [ k , k ]; //Kerroin for ( int j = 0 ; j < 2 * n ; j ++) //j-sarakkeen numero k:n jälkeen seuraavan rivin Matriisi_Suuri [ i , j ] = Matriisi_Suuri [ i , j ] - Matriisi_Iso [ k , j ] * K ; //Matriisielementtien nollaus ensimmäisen jäsenen alapuolella muutettuna yhdeksi } for ( int i = 0 ; i < n ; i ++) //Päivitä, tee muutoksia alkuperäiseen matriisiin for ( int j = 0 ; j < n ; j ++) Matriisi [ i , j ] = Matriisi_Suuri [ i , j ]; } //Käänteinen siirto (oikean yläkulman nollaus) for ( int k = n - 1 ; k > - 1 ; k --) //k-rivin numero { for ( int i = 2 * n - 1 ; i > - 1 ; i --) //i-sarakkeen numero Matriisi_iso [ k , i ] = Matriisi_Suuri [ k , i ] / Matriisi [ k , k ]; for ( int i = k - 1 ; i > - 1 ; i --) //k:n jälkeen seuraavan rivin i-numero { kaksinkertainen K = Matriisi_Suuri [ i , k ] / Matriisi_Suuri [ k , k ]; for ( int j = 2 * n - 1 ; j > - 1 ; j --) //j - sarakkeen numero k:n jälkeen seuraavan rivin Matriisi_Suuri [ i , j ] = Matriisi_Suuri [ i , j ] - Matriisi_Iso [ k , j ] * K ; } } //Ero yhteisestä matriisista for ( int i = 0 ; i < n ; i ++) for ( int j = 0 ; j < n ; j ++) xirtaM [ i , j ] = Matriisi_Suuri [ i , j + n ]; paluu xirtaM ; } } }

Muistiinpanot

↑ Jordanian nimen transkriptio "Jordaniksi" on virheellinen, mutta se on yleisesti hyväksytty ja löytyy useimmista venäjänkielisistä lähteistä.

Kirjallisuus

Atkinson, Kendall A. (1989), An Introduction to Numerical Analysis (2. painos), New York: John Wiley & Sons , ISBN 978-0471624899 .
Bolch, Gunter; Greiner, Stefan; de Meer, Hermann & Trivedi, Kishor S. (2006), Queuing Networks and Markov Chains: Modeling and Performance Evaluation with Computer Science Applications (2. painos), 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 , TILASTOTIEDOT: Oppikirjat ja monografiat, Marcel Dekker, ISBN 978-0-8247-7661-9
Higham, Nicholas (2002), Accuracy and Stability of Numerical Algorithms (2. painos), SIAM , ISBN 978-0-89871-521-7 .
Katz, Victor J. (2004), A History of Mathematics, lyhyt versio , Addison-Wesley , ISBN 978-0-321-16193-2 .
Lipson, Marc & Lipschutz, Seymour (2001), Schaumin pääpiirteet lineaarisen algebran teoriasta ja ongelmista , New York: McGraw-Hill , s. 69–80, ISBN 978-0-07-136200-9 .
Press, W.H.; Teukolsky, SA; Vetterling, WT & Flannery, BP (2007), osio 2.2 , numeeriset reseptit: The Art of Scientific Computing (3. painos), New York: Cambridge University Press, ISBN 978-0-521-88068-8

Linkit

Algoritmi Gauss - Jordan eliminaatiolle Pythonissa
Kaw, Autar; Kalu, Egwu Numeeriset menetelmät sovelluksilla: Luku 04.06 Gaussin eliminointi . Etelä-Floridan yliopisto (2010). (määrätön)

Menetelmät SLAE :n ratkaisemiseksi
Suorat menetelmät	Matriisimenetelmä Gaussin menetelmä Gauss-Jordan menetelmä Cramer menetelmä LU:n hajoaminen Cholesky-hajoaminen Lakaisumenetelmä
Iteratiiviset menetelmät	Jacobin menetelmä Gauss-Seidelin menetelmä Iterointimenetelmä Rentoutumismenetelmä Konjugaattigradienttimenetelmä Bikonjugaattigradienttimenetelmä Stabiloitu bikonjugaattigradienttimenetelmä
Kenraali	käänteinen matriisi Projektiomenetelmät SLAE:n ratkaisemiseen Esikäsittely