Gauso eliminacija: tiesinių lygčių sprendimo metodas ir pavyzdžiai

Gauso eliminacija — aiškus žingsnis po žingsnio metodas tiesinių lygčių sprendimui su pavyzdžiais, matricų ešelonais ir praktiniais sprendimais.

Autorius: Leandro Alegsa

Matematikoje Gauso eliminacija (dar vadinama eilučių redukavimu) yra tiesinių lygčių sistemoms spręsti naudojamas metodas. Jis pavadintas garsaus vokiečių matematiko Karlo Frydricho Gauso (Carl Friedrich Gauss), kuris rašė apie šį metodą, vardu; metodas egzistavo ir buvo naudojamas ir anksčiau.

Kas yra Gauso eliminacija?

Gauso eliminacija – tai procedūra, kuri transformuoja tiesinių lygčių sistemą į paprastesnę formą naudojant elementarias eilučių operacijas. Paprastai pradžioje sudaroma papildyta matrica, kurioje kairėje pusėje yra koeficientų matrica, o paskutinėje stulpelyje – konstantos (dešinės pusės reikšmės). Tada taikomos eilučių operacijos tol, kol gaunama eilučių-echelonų forma arba jos redukuotas variantas.

Elementarios eilučių operacijos

  • 1 tipas: vienos eilutės sukeitimas su kita eilute;
  • 2 tipas: eilutės dauginimas iš nenulinio skaičiaus;
  • 3 tipas: vienos eilutės pridėjimas prie kitos (arba atimimas).

Eilučių-echelonų ir redukuota eilučių-echelonų formos

Matrica yra eilučių ešelono formos, kai kiekviena nenulinė eilutė prasideda kairiau nei tolimesnė nenulinė eilutė (t. y. skaitant iš kairės į dešinę kiekviena eilutė turi daugiau nulių prieš pirmą nenulinį elementą nei prieš tai buvusi eilutė). Redukuota eilučių-echelonų forma (RENF) papildomai reikalauja, kad kiekvienas pirmasis (pivot) nenulinis elementas būtų lygus 1 ir būtų vienintelis nenulinis elementas tame stulpelyje. Gauso eliminacija, kuria siekiama gauti pilnai redukuotą formą, dažnai vadinama Gauso–Jordano eliminacija.

Žingsniai sprendžiant tiesines sistemas

  1. Surašykite papildytą matricą iš lygčių koeficientų ir konstantų.
  2. Naudokite elementarias eilučių operacijas, kad pasiektumėte eilučių-echelonų formą (pivotų radimas ir eilutės supaprastinimas).
  3. Jei reikia, tęskite transformacijas iki redukuotos eilučių-echelonų formos.
  4. Jei matrica ešelono formoje, sprendimui rasti dažnai naudojama atgalinė pakaitinė (back substitution): iš paskutinės eilutės išreiškiama paskutinė nežinoma, tuomet pakaitoma aukštesnėse eilutėse.
  5. Nustatykite sprendinio tipą: vienareikšmis sprendinys, be sprendinių (nesuderinama sistema) arba begalybė sprendinių (laisvųjų kintamųjų atvejis).

Pavyzdys (3 lygtys, 3 nežinomieji)

Tarkime turime sistemą:

 x +  2y +  z =  4 2x +  y + 3z = 11 -x +  y + 2z =  2 

Sudarius papildytą matricą:

 [ 1  2  1 |  4 ] [ 2  1  3 | 11 ] [-1  1  2 |  2 ] 

1. Iš eilučių eliminuojame pirmojo stulpelio elementus po pivot (pirmame eilutės nariuje 1):

 R2 <- R2 - 2·R1  =>  [ 1  2   1 |  4 ]                       [ 0 -3   1 |  3 ] R3 <- R3 + R1     =>  [ 1  2   1 |  4 ]                       [ 0 -3   1 |  3 ]                       [ 0  3   3 |  6 ] 

2. Galime padalyti R2 iš -3 (padarome pivot lygų 1):

 R2 <- (-1/3)·R2  =>  [ 1  2   1 |  4 ]                        [ 0  1  -1/3 | -1 ]                        [ 0  3   3 |  6 ] 

3. Eliminuojame antrą stulpelį kitose eilutėse:

 R1 <- R1 - 2·R2  =>  [ 1  0  5/3 | 6 ] R3 <- R3 - 3·R2  =>  [ 0  0  4   | 9 ] 

4. Iš R3 randame z:

 4z = 9  => z = 9/4 = 2.25 

5. Grįždami aukštyn, randame y ir x:

 R2: y - (1/3)z = -1  => y = -1 + (1/3)·(9/4) = -1 + 3/4 = -1/4 = -0.25 R1: x + (5/3)z = 6   => x = 6 - (5/3)·(9/4) = 6 - (15/4) = 9/4 = 2.25 

Todėl sprendinys: x = 9/4, y = -1/4, z = 9/4.

Specialūs atvejai ir sprendinio pobūdis

  • Jei eilučių transformacijų metu gaunama eilutė [0 0 ... 0 | b] su b ≠ 0, sistema yra nesuderinama (neturi sprendinių).
  • Jei pivoto stulpelių skaičius (matricos rangas) mažesnis už nežinomųjų skaičių, tuomet yra begalybė sprendinių: kai kuriems kintamiesiems priskiriami laisvieji parametrai.
  • Jei ranga lygi nežinomųjų skaičiui ir nėra prieštaravimo eilučių, sistema turi vienareikšmį sprendinį.

Skaičiavimo dalykai ir skaitinis stabilumas

  • Gauso eliminacijos laiko sudėtingumas yra apytiksliai O(n^3) operacijų, kur n — lygčių (arba nežinomųjų) skaičius.
  • Praktikoje naudojama dalinė pivotų strategija (partial pivoting): keičiamos eilutės taip, kad pivotas būtų didžiausias (pagal moduli) iš galimų, kas pagerina skaitinį stabilumą.
  • Be to, yra pilnesnės pivotų strategijos (visuotinė pivotizacija), kurios reikalauja ir stulpelių keitimo, bet retai reikalingos paprastoms užduotims.

Gauso ir Gauso–Jordano privalumai

Gauso eliminacija yra aiški, sisteminė ir lengvai automatizuojama, todėl plačiai naudojama tiek rankiniams skaičiavimams (mažoms sistemoms), tiek kompiuterinėms bibliotekoms didesnėms problemoms. Gauso–Jordano metodas leidžia gauti tiesioginę redukuotą formą, iš kurios sprendinį (ar parametrus) galima perskaityti tiesiogiai be atgalinės pakaitinės, tačiau jis reikalauja daugiau skaičiavimų nei standartinė Gauso eliminacija su atgaline pakaitine.

Santrauka

Gauso eliminacija yra pagrindinis ir universaliai taikomas metodas sprendžiant tiesines lygtis: ji remiasi papildytos matricos kūrimu ir elementariomis eilučių operacijomis, leidžiančiomis nustatyti sprendinio egzistavimą ir pobūdį (vienareikšmis, be sprendinio arba begalybė sprendinių). Praktikoje svarbu atsižvelgti į pivotizaciją dėl skaitinio stabilumo ir įvertinti kainą — metodas turi apytiksliai kubinę laiko sudėtingumo augimą su sistemos dydžiu.

Pavyzdys

Tarkime, kad tikslas yra rasti šios tiesinių lygčių sistemos atsakymus.

2 x + y - z = 8 ( R 1 ) - 3 x - y + 2 z = - 11 ( R 2 ) - 2 x + y + 2 z = - 3 ( R 3 ) {\displaystyle {\begin{alignedat}{7}2x&&\;+\;&&y&&\;-\;&&z&&&\;=\;&&8&\qquad (R_{1})\\-3x&&\;-\;&&y&&\;+\;&&2z&&\;=\;&&-11&\qquad (R_{2})\\-2x&&\;+\;&&y&&\;+\;&&2z&&\;=\;&&-3&\qquad (R_{3})\end{alignedat}}} {\displaystyle {\begin{alignedat}{7}2x&&\;+\;&&y&&\;-\;&&z&&\;=\;&&8&\qquad (R_{1})\\-3x&&\;-\;&&y&&\;+\;&&2z&&\;=\;&&-11&\qquad (R_{2})\\-2x&&\;+\;&&y&&\;+\;&&2z&&\;=\;&&-3&\qquad (R_{3})\end{alignedat}}}

Pirmiausia sistemą reikia paversti papildyta matrica. Papildytoje matricoje kiekviena tiesinė lygtis tampa eilute. Vienoje papildytos matricos pusėje kiekvieno tiesinės lygties nario koeficientai tampa matricos skaičiais. Kitoje papildytos matricos pusėje yra pastovieji nariai, kuriems lygi kiekviena tiesinė lygtis. Šiai sistemai papildytoji matrica yra tokia:

[ 2 1 - 1 8 - 3 - 1 2 - 11 - 2 1 2 - 3 ] {\displaystyle \left[{\begin{array}{ccc|c}2&1&-1&8\-3&-1&2&-11\-2&1&2&3\end{array}}\right]} {\displaystyle \left[{\begin{array}{ccc|c}2&1&-1&8\\-3&-1&2&-11\\-2&1&2&-3\end{array}}\right]}

Tuomet, norint supaprastinti papildytą matricą, su ja galima atlikti eilutės operacijas. Toliau pateiktoje lentelėje parodytas lygčių sistemos ir papildytos matricos eilučių mažinimo procesas.

Lygčių sistema

Eilučių operacijos

Papildyta matrica

2 x + y - z = 8 - 3 x - y + 2 z = - 11 - 2 x + y + 2 z = - 3 {\displaystyle {\begin{alignedat}{7}2x&&\;+\;&&y&&&\;-\;&&z&&&\;=\;&&8&&\\-3x&&\;-\;&&y&&\;+\;&&2z&& \;=\;&&-11&\\-2x&&\;+\;&&y&&\;+\;&&2z&&\;=\;&&-3&\end{alignedat}}} {\displaystyle {\begin{alignedat}{7}2x&&\;+\;&&y&&\;-\;&&z&&\;=\;&&8&\\-3x&&\;-\;&&y&&\;+\;&&2z&&\;=\;&&-11&\\-2x&&\;+\;&&y&&\;+\;&&2z&&\;=\;&&-3&\end{alignedat}}}

[ 2 1 - 1 8 - 3 - 1 2 - 11 - 2 1 2 - 3 ] {\displaystyle \left[{\begin{array}{ccc|c}2&1&-1&8\-3&-1&2&-11\-2&1&2&3\end{array}}\right]} {\displaystyle \left[{\begin{array}{ccc|c}2&1&-1&8\\-3&-1&2&-11\\-2&1&2&-3\end{array}}\right]}

2 x + y - z = 8 1 2 y + 1 2 z = 1 2 y + z = 5 {\displaystyle {\begin{alignedat}{7}2x&&&\;+&&&y&&&\;-&&&\;z&&&\;=\;&&8&\\&&&&{\frac {1}{2}}y&&\;+&&\;{\frac {1}{2}}z&&\;=\;&&1&\\&&&&2y&&\;+&&\;z&&\;=\;&&5&\end{alignedat}}} {\displaystyle {\begin{alignedat}{7}2x&&\;+&&y&&\;-&&\;z&&\;=\;&&8&\\&&&&{\frac {1}{2}}y&&\;+&&\;{\frac {1}{2}}z&&\;=\;&&1&\\&&&&2y&&\;+&&\;z&&\;=\;&&5&\end{alignedat}}}

R 2 + 3 2 R 1 → R 2 {\displaystyle R_{2}+{\frac {3}{2}}R_{1}\rightarrow R_{2}}} {\displaystyle R_{2}+{\frac {3}{2}}R_{1}\rightarrow R_{2}}
R 3 + R 1 → R 3 {\displaystyle R_{3}+R_{1}\rightarrow R_{3}}
{\displaystyle R_{3}+R_{1}\rightarrow R_{3}}

[ 2 1 - 1 8 0 1 / 2 1 / 2 1 0 2 1 5 ] {\displaystyle \left[{\begin{array}{ccc|c}2&1&-1&8\0&1/2&1/2&1\0&2&1&5\end{array}}\right]} {\displaystyle \left[{\begin{array}{ccc|c}2&1&-1&8\\0&1/2&1/2&1\\0&2&1&5\end{array}}\right]}

2 x + y - z = 8 1 2 y + 1 2 z = 1 - z = 1 {\displaystyle {\begin{alignedat}{7}2x&&&\;+&&&y\;&&-&&&\;z\;&&=\;&&&8&\\&&&&{\frac {1}{2}}y\;&&+&&\;{\frac {1}{2}}z\;&&=\;&&1&\\&&&&&&&&\;-z\;& &\;=\;&&1&\end{alignedat}}} {\displaystyle {\begin{alignedat}{7}2x&&\;+&&y\;&&-&&\;z\;&&=\;&&8&\\&&&&{\frac {1}{2}}y\;&&+&&\;{\frac {1}{2}}z\;&&=\;&&1&\\&&&&&&&&\;-z\;&&\;=\;&&1&\end{alignedat}}}

R 3 + - 4 R 2 → R 3 {\displaystyle R_{3}+-4R_{2}\rightarrow R_{3}} {\displaystyle R_{3}+-4R_{2}\rightarrow R_{3}}

[ 2 1 - 1 8 0 1 / 2 1 / 2 1 0 0 0 - 1 1 ] {\displaystyle \left[{\begin{array}{ccc|c}2&1&-1&8\0&1/2&1/2&1\0&0&0&-1&1\end{array}}\right]} {\displaystyle \left[{\begin{array}{ccc|c}2&1&-1&8\\0&1/2&1/2&1\\0&0&-1&1\end{array}}\right]}

Dabar matrica yra eilučių ir ešelonų pavidalo. Ši forma dar vadinama trikampio forma.

Lygčių sistema

Eilučių operacijos

Papildyta matrica

2 x + y = 7 1 2 y = 3 / 2 - z = 1 {\displaystyle {\begin{alignedat}{7}2x&&&\;+&&y\;&&&&\;\;&&=\;&&7&\&&&&&&&{\frac {1}{2}}y\;&&&&\;\;&&=\;&&3/2&\\&&&&&&&&\;-z\;&&\;=\;&&1&\end{alignedat}}} {\displaystyle {\begin{alignedat}{7}2x&&\;+&&y\;&&&&\;\;&&=\;&&7&\\&&&&{\frac {1}{2}}y\;&&&&\;\;&&=\;&&3/2&\\&&&&&&&&\;-z\;&&\;=\;&&1&\end{alignedat}}}

R 2 + 1 2 R 3 → R 2 {\displaystyle R_{2}+{\frac {1}{2}}R_{3}\rightarrow R_{2}}} {\displaystyle R_{2}+{\frac {1}{2}}R_{3}\rightarrow R_{2}}
R 1 - R 3 → R 1 {\displaystyle R_{1}-R_{3}\rightarrow R_{1}}
{\displaystyle R_{1}-R_{3}\rightarrow R_{1}}

[ 2 1 1 0 7 0 1 / 2 0 3 / 2 0 0 - 1 1 ] {\displaystyle \left[{\begin{array}{ccc|c}2&1&0&7\0&1/2&0&3/2\0&0&0&1&1\end{array}}\right]} {\displaystyle \left[{\begin{array}{ccc|c}2&1&0&7\\0&1/2&0&3/2\\0&0&-1&1\end{array}}\right]}

2 x + y = 7 y = 3 z = - 1 {\displaystyle {\begin{alignedat}{7}2x&&&\;+&&y\;&&&&\;\;&&=\;&&7&\&&&&&&&y\;&&&&\;\;&&=\;&&3&\\&&&&&&&&\;z\;&&\;=\;&&-1&\end{alignedat}}} {\displaystyle {\begin{alignedat}{7}2x&&\;+&&y\;&&&&\;\;&&=\;&&7&\\&&&&y\;&&&&\;\;&&=\;&&3&\\&&&&&&&&\;z\;&&\;=\;&&-1&\end{alignedat}}}

2 R 2 → R 2 {\displaystyle 2R_{2}\rightarrow R_{2}} {\displaystyle 2R_{2}\rightarrow R_{2}}
R 3 → R 3 {\displaystyle -R_{3}\rightarrow R_{3}}
{\displaystyle -R_{3}\rightarrow R_{3}}

[ 2 1 1 0 7 0 1 0 3 0 0 0 1 - 1 ] {\displaystyle \left[{\begin{array}{ccc|c}2&1&0&7\0&1&0&3\0&0&0&1&1&-1\end{array}}\right]} {\displaystyle \left[{\begin{array}{ccc|c}2&1&0&7\\0&1&0&3\\0&0&1&-1\end{array}}\right]}

x = 2 y = 3 z = - 1 {\displaystyle {\begin{alignedat}{7}x&&&\;&&\;&&&&\;\;&&=\;&&2&\\&&&& y\;&&&&\;\;&&=\;&&3&\\&&&&&&&&\;z\;&&\;=\;&&-1&\end{alignedat}}} {\displaystyle {\begin{alignedat}{7}x&&\;&&\;&&&&\;\;&&=\;&&2&\\&&&&y\;&&&&\;\;&&=\;&&3&\\&&&&&&&&\;z\;&&\;=\;&&-1&\end{alignedat}}}

R 1 - R 2 → R 1 {\displaystyle R_{1}-R_{2}\rightarrow R_{1}} {\displaystyle R_{1}-R_{2}\rightarrow R_{1}}
1 2 R 1 → R 1 {\displaystyle {\frac {1}{2}}R_{1}\rightarrow R_{1}}
{\displaystyle {\frac {1}{2}}R_{1}\rightarrow R_{1}}

[ 1 0 0 0 2 0 1 0 3 0 0 0 1 - 1 ] {\displaystyle \left[{\begin{array}{ccc|c}1&0&0&0&2\0&1&0&3\0&0&0&1&1&-1\end{array}}\right]} {\displaystyle \left[{\begin{array}{ccc|c}1&0&0&2\\0&1&0&3\\0&0&1&-1\end{array}}\right]}

Dabar matrica yra redukuotos eilučių ir ešelonų formos. Skaitydami šią matricą sužinome, kad šios lygčių sistemos sprendiniai yra tada, kai x = 2, y = 3 ir z = -1.

Klausimai ir atsakymai

K: Kas yra Gauso eliminacija?


A: Gauso eliminacija yra matematikoje naudojamas tiesinių lygčių sistemų sprendimo metodas.

K: Kieno vardu jis pavadintas?


A: Pavadintas garsaus vokiečių matematiko Karlo Frydricho Gauso (Carl Friedrich Gauss), kuris rašė apie šį metodą, bet jo neišrado, vardu.

K: Kaip atliekama Gauso eliminacija?


A: Gauso eliminavimas atliekamas naudojant tiesinių lygčių sistemos narių koeficientus, kad būtų sukurta papildyta matrica. Tada matricai supaprastinti naudojamos elementarios eilutės operacijos.

Klausimas: Kokios trys eilučių operacijos naudojamos atliekant Gauso eliminavimą?


A: Trys eilučių operacijų rūšys, naudojamos Gauso eliminacijoje, yra šios: Vienos eilutės sukeitimas su kita eilute, eilutės dauginimas iš nenulinio skaičiaus ir eilutės pridėjimas arba atėmimas iš kitos eilutės.

K: Koks yra Gauso eliminavimo tikslas?


Atsakymas: Gauso eliminavimo tikslas - gauti matricą eilučių ešelono pavidalu.

K: Kas yra eilutės-echelono forma?


A: Jei matrica yra eilučių-echelonų formos, tai reiškia, kad skaitant iš kairės į dešinę, kiekviena eilutė prasideda su bent vienu nuliniu nariu daugiau nei eilutė virš jos.

K: Kas yra redukuotoji eilučių-echelonų forma?


Atsakymas: Sumažinta eilučių-echelonų forma reiškia, kad matrica yra eilučių-echelonų formos ir vienintelis nenulinis narys kiekvienoje eilutėje yra 1. Gauso eliminacija, sukurianti sumažintos eilučių-echelonų matricos rezultatą, kartais vadinama Gauso-Jordano eliminacija.


Ieškoti
AlegsaOnline.com - 2020 / 2025 - License CC3