Gauss-Jordan metode

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 9. juni 2021; checks kræver 2 redigeringer .

Gauss-Jordan- metoden (metode til fuldstændig eliminering af ukendte) er en metode, der bruges til at løse kvadratiske systemer af lineære algebraiske ligninger , finde det inverse af en matrix , finde koordinaterne for en vektor på en given basis eller finde rangordenen af en matrix . Metoden er en modifikation af Gauss-metoden . Opkaldt efter C. F. Gauss og den tyske landmåler og matematiker Wilhelm Jordan [1] .

Algoritme

Vælg den første venstre kolonne i matrixen , som har mindst én værdi, der ikke er nul.
Hvis det øverste tal i denne kolonne er nul, skal du ændre hele den første række af matricen med en anden række af matrixen, hvor der ikke er et nul i denne kolonne.
Alle elementer i den første række er divideret med det øverste element i den valgte kolonne.
Fra de resterende rækker trækkes den første række, ganget med det første element i den tilsvarende række, for at få det første element i hver række (undtagen den første) nul.
Dernæst udføres den samme procedure med matrixen opnået fra den originale matrix efter sletning af den første række og den første kolonne.
Efter at have gentaget denne procedure én gang, opnås en øvre trekantet matrix $n-1$
Træk den sidste række fra den næstsidste række ganget med den passende koefficient, så der kun er 1 på hoveddiagonalen tilbage i den næstsidste række .
Gentag det foregående trin for de efterfølgende linjer. Som et resultat opnås en identitetsmatrix og en opløsning i stedet for en fri vektor (det er nødvendigt at udføre alle de samme transformationer med det).

En udvidet algoritme til at finde det inverse af en matrix

Lad givet :

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

Fremadgående bevægelse (algoritme til dannelse af nuller under hoveddiagonalen)

Divider den første række af matrix A med , vi får: , j er en kolonne af matrix A. $a_{11}$ $a_{1j}^1 = \frac{a_{1j} }{a_{11} }$
Vi gentager trinene for matrix I ifølge formlen: s er en søjle af matrix 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 danner 0 i den første kolonne: $a_{2j}^{1}=a_{2j}-a_{1j}^{1}a_{21}\ ,\dots ,\ a_{nj}^{1}=a_{nj}-a_ {1j}^{1}a_{n1}$
Vi gentager trinene for matrix I ifølge formlerne: $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 med at udføre lignende operationer ved hjælp af formlerne: $a_{ij}^k=\frac{a_{ij}^k}{a_{ii} } \qquad a_{ij}^k=a_{ij}^{k-1}-a_{kj}^k a_ {ik}^{k-1}$

forudsat at

k = 1 \højrepil n,i = k + 1 \højrepil n,j = 1 \højrepil n

Vi gentager trinene for matrix I ifølge formlerne: $b_{ik}^k=\frac{b_{ik}^k}{a_{ii} } \qquad b_{is}^k=b_{is}^{k-1}-b_{ks}^k a_ {ik}^{k-1}$

forudsat at

k=1 \til n,\; i=k+1 \til n,\; s=1 \til 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}

Omvendt bevægelse (algoritme til dannelse af nuller over hoveddiagonalen)

Vi bruger formlen: , forudsat at $a_{ij}^{k-1}=a_{ij}^{k-1}-a_{ij}^k a_{ik}^i$ $k=n \til 1,\; i=1 \til k-1,\; j=1 \til n$

Vi gentager trinene for matrix I ifølge formlen: , forudsat at $b_{er}^{k-1}=b_{er}^{k-1}-b_{is}^k a_{ik}^i$ $k=n \til 1,\; i=1 \til k-1,\; s=1 \til n$

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

Eksempel

For at løse følgende ligningssystem :

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

Vi skriver det i form af en 3 × 4 matrix, hvor den sidste kolonne er et gratis medlem:

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

Lad os gøre følgende:

Til linje 2 tilføjes: −4 × Linje 1.
Til linje 3 tilføjes: −9 × Linje 1.

Vi får:

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

Til linje 3 tilføjes: −3 × Linje 2.
Række 2 divideres med −2

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

Til linje 1 tilføjes: −1 × Linje 3.
Til linje 2 tilføjer vi: −3/2 × Linje 3.

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

Til linje 1 tilføjes: −1 × Linje 2.

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

I højre kolonne får vi løsningen:

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

Implementering af algoritmen i C# programmeringssproget

navneområde Gauss_Jordan_Method { klasse matematik { /// <resumé> /// Gauss-Jordan metode (invers matrix) /// </resumé> /// <param name="Matrix">Initial matrix</param> /// <returns></returns> offentlig statisk dobbelt [,] GaussJordan ( dobbelt [,] Matrix ) { int n = Matrix . GetLength ( 0 ); //Dimension af den indledende matrix dobbelt [,] xirtaM = ny dobbelt [ n , n ]; //Identitetsmatrix (ønsket omvendt matrix) for ( int i = 0 ; i < n ; i ++) xirtaM [ i , i ] = 1 ; dobbelt [,] Matrix_Stor = ny dobbelt [ n , 2 * n ]; //Fælles matrix opnået ved at forbinde den oprindelige matrix og identiteten 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 ]; } //Flyt fremad (nulstilling af nederste venstre hjørne) for ( int k = 0 ; k < n ; k ++) //k-linjetal { for ( int i = 0 ; i < 2 * n ; i ++) //i-kolonnenummer Matrix_Big [ k , i ] = Matrix_Big [ k , i ] / Matrix [ k , k ]; //Dividering af k-strengen med det første medlem !=0 for at konvertere den til en for ( int i = k + 1 ; i < n ; i ++) //i-nummer på næste linje efter k { dobbelt K = Matrix_Big [ i , k ] / Matrix_Big [ k , k ]; //Koefficient for ( int j = 0 ; j < 2 * n ; j ++) //j-kolonnenummer på næste linje efter k Matrix_Big [ i , j ] = Matrix_Big [ i , j ] - Matrix_Big [ k , j ] * K ; //Nulstilling af matrixelementer under det første medlem konverteret til et } for ( int i = 0 ; i < n ; i ++) //Opdater, foretag ændringer til den indledende matrix for ( int j = 0 ; j < n ; j ++) Matrix [ i , j ] = Matrix_Big [ i , j ]; } //Omvendt flytning (nulstilling af øverste højre hjørne) for ( int k = n - 1 ; k > - 1 ; k --) //k-linjetal { for ( int i = 2 * n - 1 ; i > - 1 ; i --) //i-kolonnenummer Matrix_Big [ k , i ] = Matrix_Big [ k , i ] / Matrix [ k , k ]; for ( int i = k - 1 ; i > - 1 ; i --) //i-nummer på næste linje efter k { dobbelt K = Matrix_Big [ i , k ] / Matrix_Big [ k , k ]; for ( int j = 2 * n - 1 ; j > - 1 ; j --) //j-kolonnenummer på næste linje efter k Matrix_Big [ i , j ] = Matrix_Big [ i , j ] - Matrix_Big [ k , j ] * K ; } } //Separat fra den fælles matrix for ( int i = 0 ; i < n ; i ++) for ( int j = 0 ; j < n ; j ++) xirtaM [ i , j ] = Matrix_Big [ i , j + n ]; returnere xirtaM ; } } }

Noter

↑ Transskriptionen af navnet Jordan som "Jordan" er fejlagtig, men det er generelt accepteret og findes i de fleste russisksprogede kilder.

Litteratur

Atkinson, Kendall A. (1989), An Introduction to Numerical Analysis (2. udgave), 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. udgave), 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. udgave), 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 oversigt over teori og problemer med lineær algebra , New York: McGraw-Hill , s. 69–80, ISBN 978-0-07-136200-9 .
Press, W.H.; Teukolsky, SA; Vetterling, WT & Flannery, BP (2007), afsnit 2.2 , Numeriske opskrifter: The Art of Scientific Computing (3. udgave), New York: Cambridge University Press, ISBN 978-0-521-88068-8

Links

Algoritme for Gauss-Jordan-eliminering i Python
Kaw, Autar; Kalu, Egwu Numeriske metoder med applikationer: Kapitel 04.06 Gaussisk eliminering . University of South Florida (2010). (ubestemt)

Metoder til løsning af SLAE
Direkte metoder	Matrix metode Gauss metode Gauss-Jordan metode Cramer metode LU nedbrydning Kolesky nedbrydning Feje metode
Iterative metoder	Jacobi metode Gauss-Seidel metode Iterationsmetode Afslapningsmetode Konjugeret gradientmetode Bikonjugeret gradientmetode Stabiliseret bikonjugat gradientmetode
Generel	omvendt matrix Projektionsmetoder til løsning af SLAE Forkonditionering