Gausa eliminācija: definīcija un rindu reducēšana lineāru sistēmu risināšanā

Gausa eliminācija: skaidrojums, soli pa solim rindu reducēšana lineāru sistēmu risināšanai — metodes, piemēri un Gausa–Jordana pieeja saprotami un praktiski.

Autors: Leandro Alegsa

Matemātikā Gausa eliminācija (saukta arī par rindu reducēšanu) ir metode, ko izmanto lineāru vienādojumu sistēmu risināšanai. Tā ir nosaukta slavenā vācu matemātiķa Kārļa Frīdriha Gausa vārdā, kurš rakstīja par šo metodi, bet neizgudroja to.

Lai veiktu Gausa izslēgšanu, lineāro vienādojumu sistēmas locekļu koeficienti tiek izmantoti, lai izveidotu matricas veidu, ko sauc par papildinātu matricu. Tad matricas vienkāršošanai izmanto elementāras rindas operācijas. Izmanto šādus trīs rindu operāciju veidus:

1. tips: vienas rindas pārslēgšana ar citu rindu.

2. tips: rindas reizināšana ar skaitli, kas nav nulle.

3. tips: rindas pievienošana vai atņemšana no citas rindas.

Gausa eliminācijas mērķis ir iegūt matricu rindu-ekelonu formā. Ja matrica ir rindas-ekelona formā, tas nozīmē, ka, lasot no kreisās uz labo, katra rinda sākas ar vismaz vienu nulles locekli vairāk nekā rinda virs tās. Dažās Gausa eliminācijas definīcijās teikts, ka matricas rezultātam jābūt reducētā rindu-ekelona formā. Tas nozīmē, ka matrica ir rindas-ekelona formā un vienīgais nenulles loceklis katrā rindā ir 1. Gausa elimināciju, kas rada reducētas rindas-ekelona matricas rezultātu, dažreiz sauc par Gausa-Jordana elimināciju.

Kā Gausa eliminācija darbojas — soļi

  • 1) Veido papildināto matricu no sistēmas koeficientiem un brīvajiem locekļiem (ja vienādojumu labās puses). Parasti ieraksta šo matricu un īsteno rindas operācijas uz tās.
  • 2) Forward (uz priekšu) izslēgšana: izmantojot elementāras rindas operācijas, iegūst rindas-ekelona formu. Tas nozīmē izvēlēties "pivot" elementu katrā kolonnā (parasti uz diagonāles), padarīt to nenulles un iznīcināt (padarīt nulles) zem tā esošos elementus, izmantojot rindas pievienošanu/reizināšanu.
  • 3) Back substitution (atpakaļreizināšana): pēc tam, kad matrica ir triangulāra (rindas-ekelona), atrisina mainīgos, sākot no pēdējās rindas un virzoties uz augšu, izmantojot iegūtās vienādojumu rindas.
  • Gausa–Jordana variants: ja turpina iznīcināt arī virs pivotiem un normē pivotus uz 1, iegūst reducēto rindas-ekelona formu, kur risinājums ir izlasāms tieši no matricas bez papildus atpakaļreizināšanas.

Pivotēšana un skaitliskā stabilitāte

Praktiskā rēķināšanā pivotam var gadīties būt nulle vai ļoti mazai vērtībai, kas rada dalīšanas ar nulli vai lielas skaitliskās kļūdas. Lai to novērstu, izmanto:

  • Daļēju pivotēšanu — pirms operācijām atlasīt rindu ar lielāko absolūto vērtību tajā kolonnā un apmainīt rindas.
  • Pilnu pivotēšanu — var arī mainīt kolonnas (rindas un kolonnas apmaiņa), saglabājot reizināšanas faktorus un atbilstoši izsekojot mainīgos.

Risinājumu veidi

Atkarībā no matricas ranga un paplašinātās matricas ranga, sistēmai var būt:

  • Viens unikāls risinājums — ja ranga vienāds ar mainīgo skaitu.
  • Bez risinājuma (inkonsistence) — ja paplašinātās matricas rangs ir lielāks par koeficientu matricas rangu (radās rinda ar 0 ... 0 | b, kur b ≠ 0).
  • Beigu rezultātā bezgalīgi daudz risinājumu — ja rangs ir mazāks par mainīgo skaitu; tad daļa mainīgo kļūst par brīvajiem mainīgajiem, kurus var parametrizēt.

Skaitļošanas sarežģītība

Gausa eliminācijas algoritsma laika sarežģītība parasti ir O(n^3) (n — vienādojumu/mainīgo skaits) galvenokārt matrice operāciju dēļ. Atmiņas prasības pieaug kā O(n^2). Tāpēc liela apjoma sistēmām izmanto optimizētas metodes vai iteratīvas pieejas.

Simpls piemērs (ideja, ne pilns izklāsts)

Ņemam sistēmu:
x + 2y = 5
3x + 4y = 11

Augšējā rinda tiek izmantota kā pivot; iznīcinām 3x zem pivot, atņemot 3 reizes pirmo rindu no otrās: otrā rinda kļūst 0x − 2y = −4, tāpēc y = 2. Tad x = 5 − 2·2 = 1. Šis vienkāršais piemērs ilustrē forward izslēgšanu + back substitution koncepciju.

Praktiskā lietošana

Gausa eliminācija tiek plaši izmantota inženierzinātnēs, ekonomikā, fizikā un datorzinātnē — jebkur, kur nepieciešams risināt lineāras sistēmas. Risinot lielas sistēmas, bieži izmanto bibliotēkas ar stabilām pivotēšanas un optimizācijas stratēģijām (piem., LAPACK).

Padoms: eksperimentējot ar Gausa elimināciju, seko elementārajām rindas operācijām un pieraksti, kuras rindas tiek mainītas, lai varētu korekti atjaunot mainīgo indeksus, ja tiek izmantota kolonnu apmaiņa (pilna pivotēšana).

Piemērs

Pieņemsim, ka mērķis ir atrast atbildes uz šo lineāro vienādojumu sistēmu.

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

Vispirms sistēma jāpārvērš par papildinātu matricu. Paplašinātajā matricā katrs lineārais vienādojums kļūst par rindu. Paplašinātās matricas vienā pusē katra lineārā vienādojuma locekļa koeficienti kļūst par skaitļiem matricā. Paplašinātās matricas otrā pusē ir konstantie locekļi, kuriem ir vienāds katrs lineārais vienādojums. Šai sistēmai paplašinātā matrica ir šāda:

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

Pēc tam ar papildināto matricu var veikt rindu operācijas, lai to vienkāršotu. Tabulā ir parādīts rindu reducēšanas process vienādojumu sistēmai un papildinātajai matricai.

Vienādojumu sistēma

Rindu darbības

Paplašinātā 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 1 / 2 1 0 2 1 5 ] {\displaystyle \left[{\begin{array}{ccc|c}2&1&-1&8\0&1/2&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 1 / 2 1 0 0 - 1 1 ] {\displaystyle \left[{\begin{array}{ccc|c}2&1&-1&8\0&1/2&1/2&1/2&1\0&0&1&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]}

Matrica tagad ir rindu-ekelonu formā. To sauc arī par trīsstūrveida formu.

Vienādojumu sistēma

Rindu darbības

Paplašinātā 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 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&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]}

Matrica tagad ir reducētā rindu-ekelonu formā. Lasot šo matricu, mēs redzam, ka šīs vienādojumu sistēmas risinājumi ir tad, kad x = 2, y = 3 un z = -1.

Jautājumi un atbildes

J: Kas ir Gausa eliminācija?


A: Gausa eliminācija ir metode, ko izmanto matemātikā, lai atrisinātu lineāru vienādojumu sistēmas.

J: Kura vārdā tā ir nosaukta?


A: Tā ir nosaukta slavenā vācu matemātiķa Kārļa Frīdriha Gausa vārdā, kurš rakstīja par šo metodi, bet neizgudroja to.

J: Kā tiek veikta Gausa eliminācija?


A: Gausa elimināciju veic, izmantojot lineāro vienādojumu sistēmas locekļu koeficientus, lai izveidotu papildinātu matricu. Tad matricas vienkāršošanai izmanto elementāras rindas operācijas.

Kādi ir trīs rindu operāciju veidi, ko izmanto Gausa eliminācijā?


A: Gausa eliminācijā izmanto šādus trīs rindu operāciju veidus: Vienas rindas aizstāšana ar citu rindu, rindas reizināšana ar nenulles skaitli un rindas pievienošana vai atņemšana no citas rindas.

K: Kāds ir Gausa eliminācijas mērķis?


A: Gausa eliminācijas mērķis ir iegūt matricu rindas-ekelona formā.

J: Kas ir rindas un ešelona forma?


A: Ja matrica ir rindas-ekelona formā, tas nozīmē, ka, lasot no kreisās uz labo, katra rinda sākas ar vismaz vienu nulles locekli vairāk nekā rinda virs tās.

J: Kas ir reducētā rindu-ekelona forma?


A: Reducēta rindu-ekelona forma nozīmē, ka matrica ir rindu-ekelona formā un vienīgais nenulles loceklis katrā rindā ir 1. Gausa elimināciju, kas rada reducētas rindu-ekelona matricas rezultātu, dažreiz sauc par Gausa-Jordana elimināciju.


Meklēt
AlegsaOnline.com - 2020 / 2025 - License CC3