Gaussin menetelmä

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

Gaussin menetelmä on klassinen menetelmä lineaaristen algebrallisten yhtälöiden (SLAE) ratkaisemiseksi. Nimetty saksalaisen matemaatikon Carl Friedrich Gaussin mukaan . Tämä on menetelmä muuttujien peräkkäiseen eliminointiin , kun alkeismuunnosten avulla yhtälöjärjestelmä pelkistetään vastaavaksi kolmiotyyppiseksi järjestelmäksi, josta kaikki järjestelmän muuttujat löydetään peräkkäin viimeisestä alkaen. (numeron mukaan) [1] .

Historia

Vaikka tätä menetelmää kutsutaan nykyään yleisesti Gaussin menetelmäksi, se tunnettiin ennen C. F. Gaussia. Ensimmäinen tunnettu kuvaus tästä menetelmästä on kiinalaisessa tutkielmassa Mathematics in Nine Books.

Menetelmän kuvaus

Anna alkuperäisen järjestelmän näyttää tältä:

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

Se voidaan kirjoittaa matriisimuodossa :

ax = b,

missä

A=\left({\begin{array}{ccc}a_{11}&\ldots &a_{1n}\\\lpisteet &&\\a_{m1}&\lpisteet &a_{mn}\end{array }}\oikea),\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)

Matriisia kutsutaan järjestelmän päämatriisiksi, vapaiden jäsenten sarakkeeksi. $A$ $b$

Sitten rivien yli tapahtuvien alkeismuunnosten ominaisuuden mukaan tämän järjestelmän päämatriisi voidaan pelkistää porrastettuun muotoon (samoja muunnoksia on sovellettava vapaiden jäsenten sarakkeeseen):

\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}\\&\lpisteet &\\\alpha _{rj_{r}}x_{j_{r}}+\lpisteet +\alpha _{rj_{n }}x_{j_{n}}&=&\beta _{r}\\0&=&\beta _{r+1}\\&\lpisteet &\\0&=&\beta _{m}\end {array}}\right.,

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

Tässä tapauksessa oletetaan, että päämatriisin perusmolli (ei-nolla- molli maksimiasteena) on vasemmassa yläkulmassa, eli se sisältää vain muuttujien kertoimet [2] . $x_{j_{1}},\ldots ,x_{j_{r}}$

Muuttujia kutsutaan sitten päämuuttujiksi . Kaikkia muita kutsutaan ilmaisiksi . $x_{j_{1}},\ldots ,x_{j_{r}}$

Jos ainakin yksi luku , jossa , niin tarkasteltava järjestelmä on epäjohdonmukainen , eli sillä ei ole yhtä ratkaisua. $\beta _{i}\neq 0$ $i > r$

Anna mille tahansa . $\beta _{i}=0$ $i > r$

Siirrämme vapaat muuttujat yhtäläisyysmerkkien ulkopuolelle ja jaamme jokaisen järjestelmän yhtälön sen kertoimella vasemmanpuoleisessa ( , missä on rivin numero): $x$ $\alpha _{ij_{i}},\,i=1,\ldots ,r$ $i$

\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-\ leveähattu{\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)){\ alfa_{ij_i}}\quad (2)

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

Jos järjestelmän (2) vapaille muuttujille annetaan kaikki mahdolliset arvot ja uusi järjestelmä ratkaistaan tärkeimpien tuntemattomien suhteen alhaalta ylöspäin (eli alemmasta yhtälöstä ylempään), niin saadaan kaikki tämän SLAE :n ratkaisut . Koska tämä järjestelmä on saatu alkuperäisen järjestelmän (1) alkeismuunnoksilla , niin alkeismuunnosten ekvivalenssilauseella järjestelmät (1) ja (2) ovat ekvivalentteja, eli niiden ratkaisujen joukot ovat samat.

Seuraukset:
1: Jos yhteisessä järjestelmässä kaikki muuttujat ovat pääasiallisia, niin tällainen järjestelmä on määrätty.

2: Jos järjestelmän muuttujien määrä ylittää yhtälöiden määrän, tällainen järjestelmä on joko epämääräinen tai epäjohdonmukainen.

Johdonmukaisuuskriteeri

Yllä oleva ehto kaikille voidaan muotoilla välttämättömäksi ja riittäväksi yhteensopivuuden ehdoksi: $\beta _{i}=0$ $i > r$

Muista, että yhteisjärjestelmän arvo on sen päämatriisin arvo (tai laajennettu, koska ne ovat yhtä suuret).

Kronecker-Capellin lause .
Järjestelmä on johdonmukainen silloin ja vain, jos sen päämatriisin järjestys on yhtä suuri kuin sen laajennetun matriisin arvo.

Seuraukset:

Päämuuttujien lukumäärä on yhtä suuri kuin järjestelmän arvo, eikä se riipu sen ratkaisusta.
Jos yhteensopivan järjestelmän arvo on yhtä suuri kuin tämän järjestelmän muuttujien lukumäärä, se määritellään.

Algoritmi

Lohkokaavio on esitetty kuvassa. Tämä kuva on sovitettu ohjelman kirjoittamiseen C / C ++ -kielellä, jossa a on lisätty matriisi, jonka viimeinen sarake on vapaiden jäsenten sarake. Rivien lukumäärä on n.

Kuvaus

Algoritmi SLAE :n ratkaisemiseksi Gaussin menetelmällä on jaettu kahteen vaiheeseen.

Ensimmäisessä vaiheessa suoritetaan ns. suora siirto, kun rivien yli suoritettujen alkeismuunnosten avulla järjestelmä saatetaan porrastettuun tai kolmiomaiseen muotoon tai todetaan järjestelmän epäjohdonmukaisuus. Tätä varten matriisin ensimmäisen sarakkeen elementtien joukosta valitaan nollasta poikkeava yksi, jonka sisältävä rivi siirretään ylimpään kohtaan, jolloin tämä rivi on ensimmäinen. Lisäksi kaikkien alla olevien rivien ensimmäisen sarakkeen nollasta poikkeavat elementit asetetaan nollaan vähentämällä ensimmäinen rivi kustakin rivistä kerrottuna näiden rivien ensimmäisen elementin suhteella ensimmäisen rivin ensimmäiseen elementtiin. Kun ilmoitetut muunnokset on tehty, ensimmäinen rivi ja ensimmäinen sarake yliviivataan ja jatketaan, kunnes jäljelle jää nollakokoinen matriisi. Jos joissakin iteraatioissa ensimmäisen sarakkeen elementtien joukosta ei löytynyt nollasta poikkeavaa ykköstä, siirry seuraavaan sarakkeeseen ja suorita samanlainen toimenpide.
Toisessa vaiheessa suoritetaan ns. käänteinen siirto, jonka ydin on ilmaista kaikki tuloksena olevat perusmuuttujat ei-perusmuuttujilla ja rakentaa perusratkaisujärjestelmä , tai jos kaikki muuttujat ovat perusmuuttujia, ilmaista sitten numeerisesti lineaarisen yhtälöjärjestelmän ainoa ratkaisu. Tämä menettely alkaa viimeisestä yhtälöstä, josta vastaava perusmuuttuja ilmaistaan (ja siellä on vain yksi) ja korvataan aiemmilla yhtälöillä ja niin edelleen "askeleita" ylöspäin. Jokainen rivi vastaa täsmälleen yhtä perusmuuttujaa, joten jokaisessa vaiheessa, paitsi viimeinen (ylimpänä), tilanne toistaa täsmälleen viimeisen rivin tapauksen.

Gaussin menetelmä vaatii aritmeettisia operaatioita. $O(n^{3})$

Tämä menetelmä perustuu:

Lause (matriisien pelkistämisestä porrastettuun muotoon).
Mikä tahansa matriisi alkeismuunnoksilla vain rivien yli voidaan pelkistää porrastettuun muotoon.

Yksinkertaisin tapaus

Yksinkertaisimmassa tapauksessa algoritmi näyttää tältä:

\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.

Suora siirto:

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

Käänteinen liike. Viimeisestä nollasta poikkeavasta yhtälöstä ilmaistaan perusmuuttuja ei-perusmuuttujalla ja korvaamme sen edellisillä yhtälöillä. Toistamalla tämä menettely kaikille perusmuuttujille, saadaan perusratkaisu.

Esimerkki

Osoitetaan, kuinka seuraava järjestelmä voidaan ratkaista Gaussin menetelmällä:

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

Aseta kertoimet nollaksi toisella ja kolmannella rivillä. Voit tehdä tämän lisäämällä niihin ensimmäisen rivin kerrottuna ja vastaavasti: $x$ $\textstyle {\frac {3}{2))$ $yksi$

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

Nyt nollaamme kertoimen kolmannella rivillä vähentämällä siitä toisen rivin kerrottuna : $y$ $neljä$

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

Tämän seurauksena pelkistimme alkuperäisen järjestelmän kolmiomaiseen muotoon , jolloin saatiin päätökseen algoritmin ensimmäinen vaihe.

Toisessa vaiheessa ratkaisemme saadut yhtälöt käänteisessä järjestyksessä. Meillä on:

z=-1

kolmannesta;

y=3

toisesta korvaamalla tuloksena oleva

z

x=2

ensimmäisestä korvaamalla saadut ja .

z

y

Näin alkuperäinen järjestelmä on ratkaistu.

Jos yhtälöiden lukumäärä yhteisjärjestelmässä osoittautui pienemmäksi kuin tuntemattomien lukumäärä, niin vastaus kirjoitetaan perusratkaisujärjestelmän muodossa .

Algoritmin toteutus C#-ohjelmointikielellä

nimiavaruus Gauss_Method { luokan matematiikkaa { /// <yhteenveto> /// Gaussin menetelmä (SLAE-liuos) /// </summary> /// <param name="Matrix">Alkuperäinen matriisi</param> /// <palauttaa></palauttaa> julkinen staattinen kaksois [] Gauss ( tupla [,] matriisi ) { int n = Matriisi . GetLength ( 0 ); //Alkuperäisen matriisin mitta (rivi) double [,] Matrix_Clone = uusi double [ n , n + 1 ]; //kaksinkertainen matriisi for ( int i = 0 ; i < n ; i ++) for ( int j = 0 ; j < n + 1 ; j ++) Matrix_Clone [ i , j ] = Matriisi [ i , j ]; // Siirto eteenpäin (vasemman alakulman nollaus) for ( int k = 0 ; k < n ; k ++) //k-rivin numero { for ( int i = 0 ; i < n + 1 ; i ++) //i-sarakkeen numero Matriisi_klooni [ k , i ] = Matriisi_klooni [ 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 { double K = Matriisi_klooni [ i , k ] / Matriisi_klooni [ k , k ]; //Kerroin for ( int j = 0 ; j < n + 1 ; j ++) //j-sarakkeen k:n jälkeen seuraavan rivin numero Matriisi_klooni [ i , j ] = Matriisi_klooni [ i , j ] - Matriisi_klooni [ 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 + 1 ; j ++) Matriisi [ i , j ] = Matriisi_klooni [ i , j ]; } // Siirto taaksepäin (oikean yläkulman nollaus) for ( int k = n - 1 ; k > - 1 ; k --) //k-rivin numero { for ( int i = n ; i > - 1 ; i --) //i-sarakkeen numero Matriisi_klooni [ k , i ] = Matriisi_klooni [ k , i ] / Matriisi [ k , k ]; for ( int i = k - 1 ; i > - 1 ; i --) //k:n jälkeen seuraavan rivin i-numero { double K = Matriisi_klooni [ i , k ] / Matriisi_klooni [ k , k ]; for ( int j = n ; j > - 1 ; j --) //j - sarakkeen numero k:n jälkeen seuraavan rivin Matriisi_klooni [ i , j ] = Matriisi_klooni [ i , j ] - Matriisi_klooni [ k , j ] * K ; } } // Erottele vastaukset yleisestä matriisista double [] Answer = uusi tupla [ n ]; for ( int i = 0 ; i < n ; i ++) Vastaus [ i ] = Matrix_Clone [ i , n ]; paluu Vastaus ; } } }

Sovellukset ja muutokset

SLAE : n analyyttisen ratkaisun lisäksi Gaussin menetelmää sovelletaan myös:

annetulle matriisille käänteisen matriisin löytäminen ( oikealla olevaan matriisiin osoitetaan alkuperäisen kokoinen yksikkömatriisi: , jonka jälkeen se pelkistetään identiteettimatriisin muotoon Gauss-Jordan menetelmällä ; kuten tuloksena alkuperäisen matriisin käänteisluku ilmestyy oikealle alkuperäisen identiteettimatriisin tilalle : ); ${\näyttötyyli [A|E]}$ $A$ $[E|A^{-1}]$
matriisin arvon määrittäminen ( Kronecker-Capellin lauseen mukaan matriisin arvo on yhtä suuri kuin sen päämuuttujien lukumäärä);
SLAE:n numeerinen ratkaisu teknisissä sovelluksissa (laskentavirheen vähentämiseksi pääelementin valinnassa käytetään Gauss-menetelmää, jonka ydin on valita jokaisessa vaiheessa päämuuttujaksi se, jossa rivien ja sarakkeiden joukosta poiston jälkeen jäljellä on suurin modulokerroin).

Menetelmän edut

Rajoitetun kokoisten matriisien tapauksessa se vie vähemmän aikaa verrattuna muihin menetelmiin.
Voit yksiselitteisesti määrittää, onko järjestelmä yhteensopiva vai ei, ja jos se on yhteensopiva, löytää ratkaisunsa.
Mahdollistaa lineaarisesti riippumattomien yhtälöiden maksimimäärän löytämisen - järjestelmän matriisin järjestyksen [3] .

Gaussin menetelmän vakaus

Gaussin menetelmä huonosti ehdollisille kerroinmatriiseille on laskennallisesti epävakaa . Esimerkiksi Hilbert-matriisien tapauksessa menetelmä johtaa erittäin suuriin virheisiin jopa näiden matriisien pienillä mitoilla. Laskentavirhettä voidaan pienentää Gaussin menetelmällä valitsemalla pääelementin, joka on ehdollisesti stabiili [4] . Gaussin menetelmän laaja käyttö johtuu siitä, että huonosti ehdolliset matriisit ovat käytännössä suhteellisen harvinaisia.

Gaussin menetelmän epäoptimaalisuus

Vuonna 1969 Strassen osoitti, että suuret matriisit voidaan kertoa ajassa [5] . Tämä tarkoittaa, että matriisin inversio ja SLAE-ratkaisu voidaan toteuttaa algoritmeilla, jotka ovat asymptoottisesti nopeampia kuin Gaussin menetelmä. Siten suurille SLAE:ille Gaussin menetelmä ei ole optimaalinen nopeuden suhteen. $O(n^{\log _{2}{7)))=O(n^{2{,}81})$

Katso myös

Muistiinpanot

↑ N. Sh. Kremer , 2.3. "Gaussin menetelmä", s. 44
↑ Tällainen mollijärjestely voidaan saada aikaan järjestämällä päämatriisin sarakkeet uudelleen ja numeroimalla muuttujat vastaavasti uudelleen.
↑ N. Sh. Kremer , 2.4. " M lineaarisen yhtälön järjestelmä n muuttujalla", s. 49
↑ SUORIEN MENETELMIEN VAKAUS JA TARKKUUS (linkki ei saavutettavissa)
↑ Strassen V. Gaussin eliminointi ei ole optimaalinen // Numero . Math / F. Brezzi - Springer Science + Business Media , 1969. - Voi. 13, Iss. 4. - P. 354-356. — ISSN 0029-599X ; 0945-3245 - doi:10.1007/BF02165411

Kirjallisuus

I. M. Vinogradov. Gaussin menetelmä // Matemaattinen tietosanakirja. - M.: Neuvostoliiton tietosanakirja . - 1977-1985. (Venäjän kieli)
Ilyin V. A., Poznyak E. G. Lineaarinen algebra: Oppikirja lukioille . - 6. painos, poistettu. - M. : FIZMATLIT, 2004. - 280 s.
Amosov A. A., Dubinsky Yu. A., Kopchenova N. P. Laskennalliset menetelmät insinööreille. - M .: Mir, 1998.
Bakhvalov N. S., Zhidkov N. P. , Kobelkov G. G. Numeeriset menetelmät. - 8. painos |paikka = M. |julkaisija = Basic Knowledge Laboratory |vuosi = 2000 |sivut = |isbn =}}
Volkov E. A. Numeeriset menetelmät. - M .: Fizmatlit, 2003.
Korn G., Korn T. Matematiikan käsikirja tutkijoille ja insinööreille. - M .: Nauka, 1970. - S. 575-576.
Kremer N. Sh., Putko B. A., Trishin I. M., Fridman M. N. Higher Mathematics for Economists / Toim. N. Sh. Kremer. - 3. painos - M .: UNITI-DANA, 2007. - 479 s. — ISBN 5-238-00991-7 .

Linkit

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

Sanakirjat ja tietosanakirjat	Suuri tanskalainen
Bibliografisissa luetteloissa	GND : 4156110-7

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