Gauss-Jordan-metoden

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 9 juni 2021; kontroller kräver 2 redigeringar .

Gauss-Jordan- metoden (metod för fullständig eliminering av okända) är en metod som används för att lösa kvadratiska system av linjära algebraiska ekvationer , hitta inversen av en matris , hitta koordinaterna för en vektor i en given bas , eller hitta rangordningen av en matris . Metoden är en modifiering av Gaussmetoden . Uppkallad efter C. F. Gauss och den tyske lantmätaren och matematikern Wilhelm Jordan [1] .

Algoritm

Välj den första vänstra kolumnen i matrisen , som har minst ett värde som inte är noll.
Om det översta talet i denna kolumn är noll, ändra då hela den första raden i matrisen med en annan rad i matrisen där det inte finns någon noll i denna kolumn.
Alla element i den första raden delas med det översta elementet i den valda kolumnen.
Från de återstående raderna subtraheras den första raden, multiplicerad med det första elementet i motsvarande rad, för att få det första elementet i varje rad (förutom den första) noll.
Därefter utförs samma procedur med matrisen som erhålls från den ursprungliga matrisen efter att den första raden och den första kolumnen tagits bort.
Efter att ha upprepat denna procedur en gång erhålls en övre triangulär matris $n-1$
Subtrahera från den näst sista raden den sista raden, multiplicerad med lämplig koefficient, så att endast 1 på huvuddiagonalen återstår i den näst sista raden .
Upprepa föregående steg för efterföljande rader. Som ett resultat erhålls en identitetsmatris och en lösning i stället för en fri vektor (det är nödvändigt att utföra alla samma transformationer med den).

En utökad algoritm för att hitta inversen av en matris

Låt ges :

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

Flytta framåt (algoritm för bildandet av nollor under huvuddiagonalen)

Dividera den första raden i matris A med , vi får: , j är en kolumn i matris A. $a_{11}$ $a_{1j}^1 = \frac{a_{1j} }{a_{11} }$
Vi upprepar stegen för matris I, enligt formeln: s är en kolumn av matris I $b_{1s}^1 = \frac{b_{1s} }{a_{11} }$

Vi får:

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}

Vi kommer att bilda 0 i den första kolumnen: $a_{2j}^{1}=a_{2j}-a_{1j}^{1}a_{21}\ ,\dots ,\ a_{nj}^{1}=a_{nj}-a_ {1j}^{1}a_{n1}$
Vi upprepar stegen för matris I, enligt formlerna: $b_{2s}^{1}=b_{2s}-b_{1s}^{1}a_{21}\ ,\dots ,\ b_{ns}^{1}=b_{ns}-b_ {1s}^{1}a_{n1}$

Vi får:

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

vi fortsätter att utföra liknande operationer med formlerna: $a_{ij}^k=\frac{a_{ij}^k}{a_{ii} } \qquad a_{ij}^k=a_{ij}^{k-1}-a_{kj}^k a_ {ik}^{k-1}$

förutsatt att

k = 1 \högerpil n,i = k + 1 \högerpil n,j = 1 \högerpil n

Vi upprepar stegen för matris I, enligt formlerna: $b_{ik}^k=\frac{b_{ik}^k}{a_{ii} } \qquad b_{is}^k=b_{is}^{k-1}-b_{ks}^k a_ {ik}^{k-1}$

förutsatt att

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

Vi får:

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}

Flytta bakåt (algoritm för bildandet av nollor över huvuddiagonalen)

Vi använder formeln: , förutsatt att $a_{ij}^{k-1}=a_{ij}^{k-1}-a_{ij}^k a_{ik}^i$ $k=n \till 1,\; i=1 \till k-1,\; j=1 \till n$

Vi upprepar stegen för matrisen I, enligt formeln: , förutsatt att $b_{is}^{k-1}=b_{is}^{k-1}-b_{is}^k a_{ik}^i$ $k=n \till 1,\; i=1 \till k-1,\; s=1 \till n$

Äntligen får vi:

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

Exempel

För att lösa följande ekvationssystem :

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

Vi skriver det i form av en 3 × 4 matris, där den sista kolumnen är en gratis medlem:

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

Låt oss göra följande:

Till rad 2 lägg till: −4 × Rad 1.
Till rad 3 lägg till: −9 × Rad 1.

Vi får:

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

Till rad 3 lägg till: −3 × Rad 2.
Rad 2 delas med −2

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

Till rad 1 lägg till: −1 × Rad 3.
Till rad 2 lägger vi till: −3/2 × Rad 3.

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

Till rad 1 lägg till: −1 × Rad 2.

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

I högerspalten får vi lösningen:

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

Implementering av algoritmen i programmeringsspråket C#

namnutrymme Gauss_Jordan_Method { klass matematik { /// <sammanfattning> /// Gauss-Jordan-metoden (invers matris) /// </sammanfattning> /// <param name="Matrix">Initial matris</param> /// <returns></returns> offentlig statisk dubbel [,] GaussJordan ( dubbel [,] Matrix ) { int n = Matris . GetLength ( 0 ); //Dimension av den initiala matrisen dubbel [,] xirtaM = ny dubbel [ n , n ]; //Identitetsmatris (önskad invers matris) för ( int i = 0 ; i < n ; i ++) xirtaM [ i , i ] = 1 ; dubbel [,] Matrix_Big = ny dubbel [ n , 2 * n ]; //Gemensam matris erhållen genom att sammanfoga den initiala matrisen och identiteten för ( int i = 0 ; i < n ; i ++) för ( int j = 0 ; j < n ; j ++) { Matrix_Big [ i , j ] = Matrix [ i , j ]; Matrix_Big [ i , j + n ] = xirtaM [ i , j ]; } //Flytta framåt (nollställa det nedre vänstra hörnet) för ( int k = 0 ; k < n ; k ++) //k-linjenummer { för ( int i = 0 ; i < 2 * n ; i ++) //i-kolumnnummer Matrix_Big [ k , i ] = Matrix_Big [ k , i ] / Matrix [ k , k ]; //Dela k-strängen med den första medlemmen !=0 för att konvertera den till en för ( int i = k + 1 ; i < n ; i ++) //i-talet på nästa rad efter k { dubbel K = Matrix_Big [ i , k ] / Matrix_Big [ k , k ]; //Koefficient för ( int j = 0 ; j < 2 * n ; j ++) //j-kolumnnummer för nästa rad efter k Matrix_Big [ i , j ] = Matrix_Big [ i , j ] - Matrix_Big [ k , j ] * K ; //Nollställning av matriselement under den första medlemmen omvandlas till ett } for ( int i = 0 ; i < n ; i ++) //Uppdatera, gör ändringar i den initiala matrisen för ( int j = 0 ; j < n ; j ++) Matrix [ i , j ] = Matrix_Big [ i , j ]; } // Flytta bakåt (nollställa det övre högra hörnet) för ( int k = n - 1 ; k > - 1 ; k --) //k-linjenummer { för ( int i = 2 * n - 1 ; i > - 1 ; i --) //i-kolumnnummer Matrix_Big [ k , i ] = Matrix_Big [ k , i ] / Matrix [ k , k ]; för ( int i = k - 1 ; i > - 1 ; i --) //i-numret på nästa rad efter k { dubbel K = Matrix_Big [ i , k ] / Matrix_Big [ k , k ]; för ( int j = 2 * n - 1 ; j > - 1 ; j --) //j-kolumnnummer på nästa rad efter k Matrix_Big [ i , j ] = Matrix_Big [ i , j ] - Matrix_Big [ k , j ] * K ; } } //Separera från den gemensamma matrisen för ( int i = 0 ; i < n ; i ++) för ( int j = 0 ; j < n ; j ++) xirtaM [ i , j ] = Matrix_Big [ i , j + n ]; returnera xirtaM ; } } }

Anteckningar

↑ Transkriptionen av namnet Jordan som "Jordanien" är felaktig, men det är allmänt accepterat och finns i de flesta ryskspråkiga källor.

Litteratur

Atkinson, Kendall A. (1989), An Introduction to Numerical Analysis (2nd ed.), 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 (2nd ed.), 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: Textbooks and Monographs, Marcel Dekker, ISBN 978-0-8247-7661-9
Higham, Nicholas (2002), Accuracy and Stability of Numerical Algorithms (2:a upplagan), 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), Schaums översikt över teori och problem med linjär algebra , New York: McGraw-Hill , sid. 69–80, ISBN 978-0-07-136200-9 .
Press, W.H.; Teukolsky, SA; Vetterling, WT & Flannery, BP (2007), Avsnitt 2.2 , Numeriska recept: The Art of Scientific Computing (3:e upplagan), New York: Cambridge University Press, ISBN 978-0-521-88068-8

Länkar

Algoritm för eliminering av Gauss-Jordan i Python
Kaw, Autar; Kalu, Egwu Numeriska metoder med tillämpningar: Kapitel 04.06 Gaussisk eliminering . University of South Florida (2010). (obestämd)

Metoder för att lösa SLAE
Direkta metoder	Matrismetod Gauss metod Gauss-Jordan-metoden Cramer metod LU-nedbrytning Cholesky nedbrytning Sopa metod
Iterativa metoder	Jacobi metod Gauss-Seidel-metoden Iterationsmetod Avslappningsmetod Konjugerad gradientmetod Bikonjugerad gradientmetod Stabiliserad bikonjugatgradientmetod
Allmän	invers matris Projektionsmetoder för att lösa SLAE Förkonditionering