Gauss 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 3. februar 2022; checks kræver 6 redigeringer .

Gauss-metoden er en klassisk metode til løsning af et system af lineære algebraiske ligninger (SLAE). Opkaldt efter den tyske matematiker Carl Friedrich Gauss . Dette er en metode til successiv eliminering af variable , når ligningssystemet ved hjælp af elementære transformationer reduceres til et ækvivalent system af en trekantet type, hvorfra alle systemets variable findes sekventielt, startende fra den sidste (efter nummer) [1] .

Historie

Selvom denne metode nu almindeligvis omtales som Gauss-metoden, var den kendt før C. F. Gauss. Den første kendte beskrivelse af denne metode er i den kinesiske afhandling Mathematics in Nine Books.

Beskrivelse af metoden

Lad det originale system se sådan ud:

\left\{{\begin{array}{lcr}a_{11}x_{1}+\ldots +a_{1n}x_{n}&=&b_{1}\\\ldots &&\\a_ {m1}x_{1}+\ldots +a_{mn}x_{n}&=&b_{m}\\\end{array}}\right.

Det kan skrives i matrixform :

akse = b,

hvor

A=\left({\begin{array}{ccc}a_{11}&\ldots &a_{1n}\\\ldots &&\\a_{m1}&\ldots &a_{mn}\end{array }}\right),\quad x=\left({\begin{array}{c}x_{1}\\\vdots \\x_{n}\end{array}}\right),\quad b= \left({\begin{array}{c}b_{1}\\\vdots \\b_{m}\end{array}}\right).\quad (1)

Matrixen kaldes systemets hovedmatrix, kolonnen af frie medlemmer. $EN$ $b$

Derefter, i henhold til egenskaben ved elementære transformationer over rækker, kan hovedmatrixen af dette system reduceres til en trinvis form (de samme transformationer skal anvendes på kolonnen af frie medlemmer):

\left\{{\begin{array}{rcl}\alpha _{1j_{1}}x_{j_{1}}+\alpha _{1j_{2}}x_{j_{2}}+ \ldots +\alpha _{1j_{r}}x_{j_{r}}+\ldots +\alpha _{1j_{n}}x_{j_{n}}&=&\beta _{1}\\ \alpha _{2j_{2}}x_{j_{2}}+\ldots +\alpha _{2j_{r}}x_{j_{r}}+\ldots +\alpha _{2j_{n}}x_ {j_{n}}&=&\beta _{2}\\&\ldots &\\\alpha _{rj_{r}}x_{j_{r}}+\ldots +\alpha _{rj_{n }}x_{j_{n}}&=&\beta _{r}\\0&=&\beta _{r+1}\\&\ldots &\\0&=&\beta _{m}\end {array}}\right.,

hvor $\alpha _{1j_{1}},\ldots ,\alpha _{rj_{r}}\neq 0.$

I dette tilfælde vil vi antage, at den grundlæggende mindre (ikke-nul mindre af maksimal orden) af hovedmatricen er i øverste venstre hjørne, det vil sige, at den kun inkluderer koefficienterne for variablerne [2] . $x_{j_{1}},\ldots ,x_{j_{r}}$

Variablerne kaldes så principielle variabler . Alle andre kaldes gratis . $x_{j_{1}},\ldots ,x_{j_{r}}$

Hvis mindst ét tal , hvor , så er det pågældende system inkonsekvent , dvs. det har ikke en enkelt løsning. $\beta _{i}\neq 0$ $i > r$

Lad for evt . $\beta _{i}=0$ $i > r$

Vi overfører de frie variable ud over lighedstegnene og dividerer hver af systemets ligninger med dens koefficient længst til venstre ( , hvor er rækkenummeret): $x$ $\alpha _{ij_{i}},\,i=1,\ldots ,r$ $jeg$

\left\{\begin{array}{rcc} x_{j_1}+\widehat{\alpha}_{1j_2}x_{j_2}+\ldots+\widehat{\alpha}_{1j_r}x_{j_r}&= & \widehat{\beta}_1-\widehat{\alpha}_{1j_{r+1}}x_{j_{r+1}}-\ldots- \widehat{\alpha}_{1j_n}x_{j_n } \\ x_{j_2}+\ldots+\widehat{\alpha}_{2j_r}x_{j_r}&=& \widehat{\beta}_2-\widehat{\alpha}_{2j_{r+1)) x_{j_{r+1}}-\ldots- \widehat{\alpha}_{2j_n}x_{j_n} \\ &\ldots& \\ x_{j_r}&=& \widehat{\beta}_r-\ widehat{\alpha}_{rj_{r+1}}x_{j_{r+1}}-\ldots- \widehat{\alpha}_{rj_n}x_{j_n} \\ \end{array}\right ., \qquad \widehat{\beta}_i=\frac{\beta_i}{\alpha_{ij_i)),\quad \widehat{\alpha}_{ij_k}=\frac{\alpha_{ij_k)){\ alpha_{ij_i}}\quad (2)

hvor $i=1,\ldots ,r,\quad k=i+1,\ldots ,n.$

Hvis de frie variable i system (2) får alle mulige værdier, og det nye system løses med hensyn til de vigtigste ukendte fra bunden og op (det vil sige fra den nederste ligning til den øverste), så får vi alle løsninger af denne SLAE . Da dette system blev opnået ved elementære transformationer over det oprindelige system (1), så ved ækvivalenssætningen under elementære transformationer, er systemerne (1) og (2) ækvivalente, det vil sige, at mængderne af deres løsninger falder sammen.

Konsekvenser:
1: Hvis alle variable i et fælles system er principielle, så er et sådant system bestemt.

2: Hvis antallet af variable i systemet overstiger antallet af ligninger, så er et sådant system enten ubestemt eller inkonsistent.

Konsistenskriterium

Ovenstående betingelse for alle kan formuleres som en nødvendig og tilstrækkelig betingelse for kompatibilitet: $\beta _{i}=0$ $i > r$

Husk på, at rangen af et fælles system er rangeringen af dets hovedmatrix (eller udvidet, da de er ens).

Kronecker-Capelli teorem .
Et system er konsistent, hvis og kun hvis rangen af dets hovedmatrix er lig med rangeringen af dets udvidede matrix.

Konsekvenser:

Antallet af hovedvariable er lig med systemets rangorden og afhænger ikke af dets løsning.
Hvis rangen af et kompatibelt system er lig med antallet af variabler i dette system, så er det defineret.

Algoritme

Blokdiagrammet er vist på figuren. Denne figur er tilpasset til at skrive et program i C/C++, hvor a er en udvidet matrix, hvor den sidste kolonne er en kolonne med frie medlemmer. Antallet af linjer er n.

Beskrivelse

Algoritmen til løsning af SLAE ved Gauss-metoden er opdelt i to trin.

I det første trin udføres den såkaldte direkte bevægelse, når systemet ved hjælp af elementære transformationer over rækker bringes til en trinformet eller trekantet form , eller det konstateres, at systemet er inkonsekvent. For at gøre dette, blandt elementerne i den første kolonne i matrixen, vælges en ikke-nul, rækken, der indeholder den, flyttes til den øverste position, hvilket gør denne række til den første. Yderligere sættes ikke-nul-elementer i den første kolonne af alle underliggende rækker til nul ved at trække den første række fra hver række ganget med forholdet mellem det første element i disse rækker og det første element i den første række. Efter at de angivne transformationer er blevet foretaget, streges den første række og den første kolonne mentalt ud og fortsættes, indtil der er en nul-størrelse matrix tilbage. Hvis der ved nogle af iterationerne blandt elementerne i den første kolonne ikke blev fundet en ikke-nul, så gå til den næste kolonne og udfør en lignende operation.
På anden fase udføres det såkaldte omvendte træk, hvis essens er at udtrykke alle de resulterende grundvariabler i form af ikke-grundlæggende og opbygge et grundlæggende system af løsninger , eller, hvis alle variabler er grundlæggende, så udtryk numerisk den eneste løsning til systemet af lineære ligninger. Denne procedure begynder med den sidste ligning, hvorfra den tilsvarende grundvariabel udtrykkes (og der er kun én der) og substitueres i de foregående ligninger, og så videre, og går op ad "trinene". Hver linje svarer til nøjagtig én grundlæggende variabel, så ved hvert trin, bortset fra det sidste (øverst), gentager situationen nøjagtigt tilfældet med den sidste linje.

Gauss-metoden kræver aritmetiske operationer. $O(n^{3})$

Denne metode er afhængig af:

Sætning (om reduktion af matricer til en trinvis form).
Enhver matrix ved elementære transformationer kun over rækker kan reduceres til en trinvis form.

Det enkleste tilfælde

I det enkleste tilfælde ser algoritmen sådan ud:

\left\{\begin{array}{lcc} a_{11} \cdot x_1 + a_{12} \cdot x_2 + \ldots + a_{1n} \cdot x_n & = b_1 & (1) \\ a_{21 } \cdot x_1 + a_{22} \cdot x_2 + \ldots + a_{2n} \cdot x_n & = b_2 & (2) \\ \ldots & & \\ a_{m1} \cdot x_1 + a_{m2} \cdot x_2 + \ldots + a_{mn} \cdot x_n & = b_m & (m) \end{array}\right.

Direkte flytning:

\begin{array}{ccc} (2)\to (2)-(1) \cdot ( \frac {a_{21}}{a_{11}}) &:& a_{22}^{\prime} \cdot x_2 + a_{23}^{\prime} \cdot x_3 + \ldots + a_{2n}^{\prime} \cdot x_n = b_2^{\prime} \\ (3)\to (3)- (1) \cdot ( \frac {a_{31}}{a_{11))) &:& a_{32}^{\prime} \cdot x_2 + a_{33}^{\prime} \cdot x_3 + \ldots + a_{3n}^{\prime} \cdot x_n = b_3^{\prime} \\ \ldots & & \\ (m)\to (m)-(1) \cdot ( \frac {a_{ m1)){a_{11))) &:& a_{m2}^{\prime} \cdot x_2 + a_{m3}^{\prime} \cdot x_3 + \ldots + a_{mn}^{\prime } \cdot x_n = b_n^{\prime} \\ (3)\to (3)-(2) \cdot ( \frac {a_{32}^{\prime)){a_{22}^{\prime ))) &:& a_{33}^{\prime\prime} \cdot x_3 + \ldots + a_{3n}^{\prime\prime} \cdot x_n = b_3^{\prime\prime} \\ \ ldots & & \\ (m)\to (m)-(m-1) \cdot ( \frac {a_{m,n-1}^{(m-2)}}{a_{m-1,n -1}^{(m-2)}}) &:& a_{mm}^{(m-1)} \cdot x_m + \ldots + a_{mn}^{(m-1)} \cdot x_n = b_m^{(m-1)} \end{array}

Omvendt bevægelse. Fra den sidste ligning, der ikke er nul, udtrykker vi den grundlæggende variabel i form af ikke-grundlæggende og erstatter den med de foregående ligninger. Ved at gentage denne procedure for alle grundlæggende variable får vi den grundlæggende løsning.

Eksempel

Lad os vise, hvordan følgende system kan løses ved Gauss-metoden:

\left\{\begin{array}{ccc}2x + y - z &=& 8 \\ -3x - y + 2z &=& -11 \\ -2x + y + 2z &=& -3 \end{ array}\right.

Indstil koefficienterne til nul i anden og tredje række. For at gøre dette skal du tilføje den første linje til dem, ganget med henholdsvis og : $x$ $\textstyle {\frac {3}{2))$ $en$

\left\{\begin{array}{rcc} 2x + y - z &=& 8 \\ \frac{1}{2}y + \frac{1}{2}z &=& 1 \\ 2y + z &=& 5 \end{array}\right.

Nu nulstiller vi koefficienten til i tredje række og trækker den anden række fra den ganget med : $y$ $fire$

\left\{\begin{array}{rcc} 2x + y - z &=& 8 \\ \frac{1}{2} y + \frac{1}{2} z &=& 1 \\ -z &=& 1 \\ \end{array}\right.

Som et resultat reducerede vi det oprindelige system til en trekantet form , og fuldførte dermed den første fase af algoritmen.

På andet trin løser vi de opnåede ligninger i omvendt rækkefølge. Vi har:

z=-1

fra den tredje;

y=3

fra den anden, erstatte den resulterende

z

x=2

fra den første, erstatte de opnåede og .

z

y

Dermed er det oprindelige system løst.

Hvis antallet af ligninger i det fælles system viste sig at være mindre end antallet af ukendte, vil svaret blive skrevet i form af et grundlæggende system af løsninger .

Implementering af algoritmen i C# programmeringssproget

navneområde Gauss_Method { klasse matematik { /// <resumé> /// Gauss-metoden (SLAE-løsning) /// </resumé> /// <param name="Matrix">Initial matrix</param> /// <returns></returns> offentlig statisk dobbelt [] Gauss ( dobbelt [,] Matrix ) { int n = Matrix . GetLength ( 0 ); //Dimension af den indledende matrix (række) dobbelt [,] Matrix_Klon = ny dobbelt [ n , n + 1 ]; //dobbeltmatrix for ( int i = 0 ; i < n ; i ++) for ( int j = 0 ; j < n + 1 ; j ++) Matrix_Clone [ i , j ] = Matrix [ i , j ]; // Flyt fremad (nulstilling af nederste venstre hjørne) for ( int k = 0 ; k < n ; k ++) //k-linjetal { for ( int i = 0 ; i < n + 1 ; i ++) //i-kolonnenummer Matrix_Clone [ k , i ] = Matrix_Clone [ 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_Klon [ i , k ] / Matrix_Klon [ k , k ]; //Koefficient for ( int j = 0 ; j < n + 1 ; j ++) //j-kolonnenummer på næste linje efter k Matrix_Clone [ i , j ] = Matrix_Clone [ i , j ] - Matrix_Clone [ 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 + 1 ; j ++) Matrix [ i , j ] = Matrix_Klon [ i , j ]; } // Flyt omvendt (nulstilling af øverste højre hjørne) for ( int k = n - 1 ; k > - 1 ; k --) //k-linjetal { for ( int i = n ; i > - 1 ; i --) //i-kolonnenummer Matrix_Clone [ k , i ] = Matrix_Clone [ k , i ] / Matrix [ k , k ]; for ( int i = k - 1 ; i > - 1 ; i --) //i-nummer på næste linje efter k { dobbelt K = Matrix_Klon [ i , k ] / Matrix_Klon [ k , k ]; for ( int j = n ; j > - 1 ; j --) //j-kolonnenummer på næste linje efter k Matrix_Clone [ i , j ] = Matrix_Clone [ i , j ] - Matrix_Clone [ k , j ] * K ; } } // Adskil svar fra den generelle matrix dobbelt [] Svar = ny dobbelt [ n ]; for ( int i = 0 ; i < n ; i ++) Svar [ i ] = Matrix_Klon [ i , n ]; returnere Svar ; } } }

Applikationer og ændringer

Ud over den analytiske løsning af SLAE anvendes Gauss-metoden også til:

at finde en matrix invers til den givne (en enhedsmatrix af samme størrelse som den oprindelige er tildelt matricen til højre: , hvorefter den reduceres til form af en identitetsmatrix ved Gauss-Jordan-metoden ; som et resultat, det omvendte af den oprindelige matrix vises til højre i stedet for den oprindelige identitetsmatrix : ); $[A|E]$ $EN$ $[E|A^{-1}]$
bestemmelse af rangeringen af en matrix (i henhold til konsekvensen af Kronecker-Capelli-sætningen er rangeringen af en matrix lig med antallet af dens hovedvariable);
numerisk løsning af SLAE i tekniske applikationer (for at reducere regnefejlen bruges Gauss-metoden ved udvælgelsen af hovedelementet, hvis essens er at vælge ved hvert trin som hovedvariabel den, hvor blandt rækkerne og kolonnerne tilbage efter sletning, er der den maksimale modulo-koefficient).

Fordele ved metoden

For matricer af begrænset størrelse er det mindre tidskrævende sammenlignet med andre metoder.
Giver dig mulighed for utvetydigt at bestemme, om systemet er kompatibelt eller ej, og om det er kompatibelt, for at finde dets løsning.
Giver dig mulighed for at finde det maksimale antal lineært uafhængige ligninger - rangeringen af systemets matrix [3] .

Gauss-metodens stabilitet

Gauss -metoden for dårligt konditionerede koefficientmatricer er beregningsmæssigt ustabil . For eksempel fører metoden for Hilbert-matricer til meget store fejl selv for små dimensioner af disse matricer. Du kan reducere beregningsfejlen ved hjælp af Gauss-metoden med valget af hovedelementet, som er betinget stabilt [4] . Den udbredte brug af Gauss-metoden skyldes, at dårligt konditionerede matricer er relativt sjældne i praksis.

Ikke-optimalitet af den Gaussiske metode

I 1969 beviste Strassen , at store matricer kan ganges i tid [5] . Dette indebærer, at matrixinversion og SLAE-løsning kan implementeres af algoritmer, der er asymptotisk hurtigere i rækkefølge end Gauss-metoden. For store SLAE'er er Gauss-metoden således ikke optimal med hensyn til hastighed. $O(n^{\log _{2}{7)))=O(n^{2{,}81})$

Se også

Noter

↑ N. Sh. Kremer , 2.3. "Gauss-metoden", s. 44
↑ Et sådant arrangement af minor kan opnås ved at omarrangere kolonnerne i hovedmatricen og tilsvarende omnummerere variablerne.
↑ N. Sh. Kremer , 2.4. "System af m lineære ligninger med n variable", s. 49
↑ STABILITET OG NØJAGTIGHED AF DIREKTE METODER (utilgængeligt link)
↑ Strassen V. Gaussisk eliminering er ikke optimal // Antal . Math / F. Brezzi - Springer Science + Business Media , 1969. - Vol. 13, Iss. 4. - S. 354-356. — ISSN 0029-599X ; 0945-3245 - doi:10.1007/BF02165411

Litteratur

I. M. Vinogradov. Gauss-metoden // Mathematical Encyclopedia. — M.: Sovjetisk Encyklopædi . - 1977-1985. (Russisk)
Ilyin V. A., Poznyak E. G. Lineær Algebra: En lærebog for gymnasier . - 6. udg., slettet. - M. : FIZMATLIT, 2004. - 280 s.
Amosov A. A., Dubinsky Yu. A., Kopchenova N. P. Beregningsmetoder for ingeniører. — M .: Mir, 1998.
Bakhvalov N. S., Zhidkov N. P. , Kobelkov G. G. Numeriske metoder. - 8. udg. |sted = M. |udgiver = Basic Knowledge Laboratory |år = 2000 |sider = |isbn =}}
Volkov E. A. Numeriske metoder. — M .: Fizmatlit, 2003.
Korn G., Korn T. Håndbog i matematik for videnskabsmænd og ingeniører. - M . : Nauka, 1970. - S. 575-576.
Kremer N. Sh., Putko B. A., Trishin I. M., Fridman M. N. Højere matematik for økonomer / Udg. N. Sh. Kremer. - 3. udg. - M. : UNITI-DANA, 2007. - 479 s. — ISBN 5-238-00991-7 .

Links

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

Ordbøger og encyklopædier	Flot dansk
I bibliografiske kataloger	GND : 4156110-7

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