Gaussi elimineerimine

Valige igas veerus juhtrida ning jälgige eliminatsiooni kulgu. Teise lähteülesande puhul määrab teie valik lõppvastuse. Kui valite juhtelemendiks üliväikese arvu, saate muutuja x väärtuseks 1 asemel 0.

Kolm reateisendust	$\begin{gathered}R_i\leftrightarrow R_j,\qquad R_i\to kR_i\ (k\neq0)\\R_i\to R_i+kR_j\end{gathered}$
Täpselt üks lahend, kui	$\operatorname{rank}A=\operatorname{rank}[A\,\|\,b]=n$

Näidisarvutus — Gaussi elimineerimine

Determinant	−1
Jääk	8,8818 × 10⁻¹⁶

Need on väärtused, mida kalkulaator lehe avamisel näitab. Muuda ülal mõnda sisendit, et need ümber arvutada.

Interaktiivse simulatsiooni laadimine...

Õppetund

Teooria — Gaussi elimineerimine232 sõna

Elimineerimine taandab süsteemi samaväärsele kolmnurkkujule, mille lahendi saab seejärel alt üles välja lugeda. Meetodi olulisus ei seisne pelgalt selle toimimises – toimivaid meetodeid on mitu. Otsustavaks saab hoopis see, mida selle rakendamine maksab, sest just arvutuskulukus määrab, millise algoritmi masin tegelikult valib.

Mida iga sümbol tähendab

n: tundmatute arv ja ühtlasi ainus tegur, millest arvutuskulukus sõltub.
pivot: kordaja, millega rida jagatakse. Algoritmi paika pandud tehete järjekord muudab protseduuri otsustevabaks; see aga, milline arv juhtelemendi kohale satub, tagab arvutuse töökindluse ujukomaarvudega töötamisel.

Eeldab: Eeldatakse ärakasutatava struktuurita tihedat süsteemi. Hõredate, lint- või sümmeetriliste süsteemide lahendamine on odavam ning õige spetsialiseeritud meetodi valik moodustabki arvutusliku lineaaralgebra põhiosa.
Ei kehti, kui: Arvutuskulu on kuupfunktsioon ja kuupfunktsioon on otsekui sein. n tundmatuga süsteemi elimineerimine nõuab ligikaudu n³/3 korrutamist ja sama palju liitmisi. Reaalsel elimineerimisel tehteid üle lugedes on juhul n = 100 tulemuseks 333 300 korrutamist hinnangulise 333 333 vastu. See astendaja toob endaga kaasa vääramatu karistuse süsteemi kasvu eest: tundmatute arvu kahekordistamine korrutab töömahu täpselt 8-ga. Seega vajab 100 tundmatut 333 300 korrutamist ja 200 tundmatut juba 2 666 600 korrutamist. Masin, mis lahendab tuhande tundmatuga süsteemi ühe sekundiga, vajab seega kahe tuhande jaoks kaheksat sekundit ning kahekümne tuhande tarvis ligikaudu kahte ja veerandit tundi. Selline see sein välja näebki. Just sel põhjusel ei ole arvutusliku lineaaralgebra kõige põnevam küsimus peaaegu kunagi selles, kuidas tihedat süsteemi lahendada, vaid hoopis selles, kuidas niisugusest süsteemist hoiduda.

Ülesanded täielikult lahendatud

2x + y − z = 8 lahendamine ja selle kulu täpsuses 7 sammu
Lahenda süsteem 2x + y − z = 8, −3x − y + 2z = −11, −2x + y + 2z = −3. Seejärel leia, millise lõivu nõudis elimineerimine täpsuselt.

Ava see ülesanne tööriistas
1. Kirjuta süsteem laiendatud maatriksina. Tähtedest pole siin mingit kasu. Jäta need ära ja säilita vaid veerud.
  
  $\begin{bmatrix} 2 & 1 & -1 & 8 \\ -3 & -1 & 2 & -11 \\ -2 & 1 & 2 & -3 \end{bmatrix}$
2. Vali juhtelemendiks esimese veeru suurim liige. Selleks on teise rea −3, mis tuleb nüüd üles vahetada. Iga reavahetus pöörab determinandi märki. Pea nende üle arvet.
  
  $R_1 \leftrightarrow R_2 \quad (|-3| > |2|)$
3. Nulli ülejäänud esimene veerg. Selleks lahuta ridadest juhtelemendi rea kordsed.
  
  $R_2 \to R_2 - \tfrac{2}{-3}R_1, \qquad R_3 \to R_3 - \tfrac{-2}{-3}R_1$
4. Korda sama protseduuri teise veeruga. Vaata seejärel alumist rida. Selles on järel vaid üks tundmatu ja selle väärtus.
  
  $R_2 \leftrightarrow R_3 \quad (\tfrac{5}{3} > \tfrac{1}{3}) \;\Rightarrow\; \tfrac{1}{5}z = -\tfrac{1}{5}$
5. Tee tagasiasendusi alt üles. Viimane rida annab z-i. Keskmine annab seejärel y-i ja kõige ülemisest saad x-i.
  
  $z = -1, \qquad y = 3, \qquad x = 2$
6. Determinandi saamiseks korruta juhtelemendid ja arvesta juurde kahe reavahetuse märk. Kontrolli lahendit algsete, mitte taandatud võrrandite kaudu.
  
  $\det = (-3)\left(\tfrac{5}{3}\right)\left(\tfrac{1}{5}\right)(-1)^2 = -1$
7. Jääk tuleb umbes 10⁻¹⁶, mis ei ole päris null. See on vältimatu ümardamisvea suurus. See ongi aus arv, mida näidata. Täielikku täpsust lubav vastus põhineb kas täisarvude aritmeetikal või pigistab lihtsalt silmad kinni. Muuda ilma juhtelemendi valikuta režiimis juhtkordaja väärtuseks 10⁻¹⁷. Seesama jääk saab kohe väärtuseks 1. See on nüüd juba täiest kõrist karjuv hoiatus.
  
  $\max_i |A_i x - b_i| \approx 9 \times 10^{-16}$
Vastus

x = 2, y = 3, z = −1, determinant −1. Umbes 10⁻¹⁶ suurune jääk näitabki, et arvutus on just nii täpne, kui ujukomaarvutus lubab. Lülita halvasti skaleeritud süsteemis juhtelemendi valik välja ja just see number ütleb sulle, et vastus on vale.
Determinant 0, kaks korda, tähendades kaht eri asja 7 sammu
Sellel eelseadistusel pole lahendit ja järgmisel on neid lõpmata palju, ning mõlemad trükivad determinandiks 0. Leia, mis neid tegelikult eristab, ja otsusta, mida parema poole muutmine üldse osta suudaks.

Ava see ülesanne tööriistas
Näita lahendust
1. Osaline juhtelemendi valik vaatab esimeses veerus alla suurima kordaja järele. Ta leiab alumisest reast 3, seega on esimene käik reavahetus.
  
  $\begin{bmatrix} 1 & 1 & 1 & 3 \\ 2 & 2 & 2 & 7 \\ 3 & 1 & 2 & 5 \end{bmatrix} \xrightarrow{\;R_1 \leftrightarrow R_3\;} \begin{bmatrix} 3 & 1 & 2 & 5 \\ 2 & 2 & 2 & 7 \\ 1 & 1 & 1 & 3 \end{bmatrix} \qquad (|3| > |2| > |1|)$
2. Nulli veerg: lahuta teisest reast ⅔ uuest esimesest reast ja kolmandast ⅓ sellest.
  
  $R_2 \to R_2 - \tfrac{2}{3}R_1, \quad R_3 \to R_3 - \tfrac{1}{3}R_1: \qquad \begin{bmatrix} 3 & 1 & 2 & 5 \\ 0 & \tfrac{4}{3} & \tfrac{2}{3} & \tfrac{11}{3} \\ 0 & \tfrac{2}{3} & \tfrac{1}{3} & \tfrac{4}{3} \end{bmatrix}$
3. Teises veerus asub 4/3 juba 2/3 kohal, seega vahetada pole midagi. Lahuta kolmandast reast pool teisest reast.
  
  $R_3 \to R_3 - \tfrac{1}{2}R_2: \qquad \begin{bmatrix} 3 & 1 & 2 & 5 \\ 0 & \tfrac{4}{3} & \tfrac{2}{3} & \tfrac{11}{3} \\ 0 & 0 & 0 & -\tfrac{1}{2} \end{bmatrix}$
4. Kolmas rida on nüüd vasakul tühi ja paremal on −½, mis loeb 0 = −½. Maha pandi ainult kaks juhtelementi, 3 ja 4/3, samas kui kolm tundmatut nõuavad kolme, ja puuduv juhtelement teeb korrutise nulliks.
  
  $\text{pivots } 3,\ \tfrac{4}{3} \ \text{— two, not three} \;\Longrightarrow\; \det A = 0, \qquad \text{last row: } 0 = -\tfrac{1}{2}$
5. Astak on see, mida determinant varjab. Kordajate maatriksil on kaks sõltumatut rida. Laiendatud maatriksil on neid kolm, sest see ülejäänud −½ on rida, mida miski taandada ei saa. Astak 2 astaku 3 vastu ongi see, mida „lahendit ei ole“ tähendab.
  
  $\operatorname{rank} A = 2 \;<\; \operatorname{rank}[A\,|\,b] = 3 \;\Longrightarrow\; \text{no solution}$
6. Eelseadistus Üks võrrand kolm korda teeb sama aritmeetika ja ütleb midagi muud. Iga rida on esimese kordne, seega on mõlemad astakud 1 ja determinant on jälle 0. Lahendihulgal on 3 − 1 = 2 vaba suunda: kogu tasand x + y + z = 3. Tööriist ütleb „lõpmata palju“, ütlemata, mitmes suunas.
  
  $\text{Infinitely many: } \operatorname{rank} A = \operatorname{rank}[A\,|\,b] = 1, \quad \det A = 0, \quad \dim = 3 - 1 = 2 \quad (x+y+z=3)$
7. Muuda üht arvu ja vaata, milline suurus liigub. Pane teise rea paremale poolele 7 asemel 6. Kordajate maatriks jääb puutumata, seega determinant ei võpata, kuid laiendatud astak langeb 2 peale ja vastuseks saab lahendite sirge, mitte lahendite puudumine.
  
  $b_2 = 7 \to 6: \quad \operatorname{rank}[A\,|\,b] = 2 = \operatorname{rank} A \;\Longrightarrow\; \dim = 3 - 2 = 1$
Vastus

Determinant teatab ainult seda, kas kordajate maatriksil on täielik juhtelementide komplekt. Ta ei vaata kunagi paremale poolele, ja just seepärast ei suuda ta neid kahte eelseadistust eristada, kaks astakut aga suudavad: lahendit ei ole, kui nad lahknevad, ja lahendihulga mõõde on 3 − astak, kui nad kokku langevad. Kui determinant on juba 0, ei osta ükski parem pool sulle üht ainsat vastust — sa saad kas mitte ühtegi või terve pere, ja b otsustabki ainult nende kahe vahel. Jäägikaart kustub sama põhjuse pärast, mille jaoks ta olemas on: jäägi jaoks on vaja lahendit, mille saaks võrranditesse tagasi panna.

$\dim = n - \operatorname{rank} A \ \text{ when } \operatorname{rank}[A|b] = \operatorname{rank} A; \qquad \det A = 0 \;\Longrightarrow\; \text{no } b \ \text{gives exactly one}$
Kolm võrrandit käsitsi 5 sammu
Lahenda x + y + z = 6, 2x − y + z = 3, x + 2y − z = 2.

Ava see ülesanne tööriistas
Näita lahendust
1. Kõrvalda teisest reast x: lahuta sellest kahekordne esimene rida.
  
  $R_2\to R_2-2R_1:\quad-3y-z=-9$
2. Kõrvalda kolmandast reast x: lahuta sellest esimene rida.
  
  $R_3\to R_3-R_1:\quad y-2z=-4$
3. Kõrvalda kolmandast reast y uue teise rea kolmandiku abil. Järele jääb vaid z.
  
  $\begin{gathered}R_3\to R_3+\tfrac13R_2\\-\tfrac73z=-7\ \Rightarrow\ z=3\end{gathered}$
4. Tee tagasiasendus: z teises reas annab y ning y ja z esimeses reas x-i.
  
  $y=2,\qquad x=6-2-3=1$
5. Kontrolli lahendit kahes võrrandis, mida viimati ei kasutanud.
  
  $2-2+3=3,\qquad1+4-3=2\ \checkmark$
Vastus

x = 1, y = 2, z = 3. Determinant on 7, seega on see lahend ainus.

$x=1,\quad y=2,\quad z=3$
Lõpmatult palju lahendeid parameetriga 4 sammu
Lahenda x + y + z = 3, x − y + z = 1, 2x + 2z = 4.
Näita lahendust
1. Lahuta teisest reast esimene: y = 1.
  
  $R_2\to R_2-R_1:\quad-2y=-2\ \Rightarrow\ y=1$
2. Lahuta kolmandast reast kahekordne esimene: tekib taas sama võrrand, nii et kolmas rida ei anna midagi juurde.
  
  $R_3\to R_3-2R_1:\quad-2y=-2$
3. Kolme tundmatu kohta on kaks sõltumatut rida ja vastuolu puudub: üks tundmatu jääb vabaks.
  
  $\operatorname{rank}A=\operatorname{rank}[A\,|\,b]=2<3$
4. Olgu z = t mis tahes arv. Esimene rida annab seejärel x-i.
  
  $z=t:\quad x=3-1-t=2-t$
Vastus

(x, y, z) = (2 − t, 1, t) iga t korral. t = 0 annab (2, 1, 0) ja t = 2 annab (0, 1, 2); mõlemad rahuldavad kõiki kolme võrrandit.

$(x,y,z)=(2-t,\ 1,\ t),\quad t\in\mathbb{R}$

Lisaülesanded, ainult vastustega

Lahenda x + y + z = 2, y + z = 1, z = −1.

Näita vastust

z = −1, y = 2, x = 1. Süsteem on juba kolmnurksel kujul, seega piisab vaid tagasiasendusest.

$z=-1,\quad y=2,\quad x=1$
Lahenda x + 2y + z = 4, 2x + y − z = −1, x − y + 2z = 7.

Näita vastust

x = 1, y = 0, z = 3.

$x=1,\quad y=0,\quad z=3$
Näita, et süsteemil x + y + z = 1, x + 2y + 3z = 2, 2x + 3y + 4z = 5 puudub lahend.

Näita vastust

Tehe R₃ − R₁ − R₂ annab vasakuks pooleks 0 ja paremaks 2, ent võrdus 0 = 2 on võimatu.

$R_3-R_1-R_2:\quad0=2$

Kaks tuttavat sammu järjestuses, mis eemaldab kõik valikud

Kahe võrrandi jaoks oli vaja üht sammu: lahutada ühe rea kordne teisest. Kolm võrrandit nõuavad seda sammu ja veel üht. Sammude loend nimetab mõlemat – reavahetust, et viia peaelemendiks sobiv arv, ja elimineerimist. Järjekord on paigas: nulli esimene veerg, seejärel teine, siis loe vastus alumiselt realt ja liigu ülespoole. Seda järgides ei pea kunagi nuputama, milline võrrand käsile võtta. See ongi erinevus mõistatuse ja protseduuri vahel, ning seepärast see skaleerubki: sama rutiini tuhande tundmatuga käitab endiselt iga inseneritarkvara maailmas, kuuskümmend aastat pärast seda, kui meetod endale nime sai.

Determinant on peaelementide korrutis

Jälgi elimineerimise käigus juhtelemente ja korruta need kõik omavahel. Iga reavahetuse järel muuda kordistise märki. See ongi determinant, mis ilmub välja juba niikuinii tehtud arvutustest. Enamik inimesi tutvub determinantidega hoopis algebraliste täiendite järgi arendamise kaudu. Tasub aga mõista, miks praktikas keegi neid sedasi ei arvuta. Kofaktorid nõuavad laias laastus n! tehet elimineerimise n³ vastu. 20 × 20 maatriksi puhul on see seega 2 × 10¹⁸ tehet 8000 vastu. Just see 10¹⁴-kordne erinevus määrab, kumba algoritmi arvuti päriselt jooksutab. Valem, mida õpilastele esimesena näidatakse, on täpselt see, mida ükski masin pole kunagi kasutanud.

Üksainus valik meetodis muudab vastust

Vajutage Peaelemendi valik välja. Juhtkordaja on 10⁻¹⁷. Algoritm jagab kuulekalt sellega ja annab x-i väärtuseks 0, kuigi tegelik vastus on 1. Midagi ei ole katki ja ühtegi reeglit pole rikutud. Väikese arvuga jagamine lihtsalt mitmekordistab iga varasemat ümardamisviga. Tagasiasenduse tipuks on viga õige vastuse täielikult alla neelanud. See on järsak, mitte nõlv. Kordajat kahandades annab 10⁻¹² veel neli õiget numbrikohta ja 10⁻¹⁵ kolm. Siis aga tagastab 10⁻¹⁶ väärtuse 2,22 ning 10⁻¹⁷ annab 0. Piir asub masinepsiloni juures. See on vahe arvu 1 ja järgmise arvu vahel, mida topelttäpsusega andmetüüp esitada suudab. Märkige see ruut. Nüüd jagab algoritm hoopis suurima saadaoleva arvuga ja iga selline olukord laheneb täpselt. Just seepärast ongi lehel jääkide kaart, mis asetab vastuse tagasi algsetesse võrranditesse. See on ainus viis eristada tegelikku lahendit pelgalt enesekindlast vastusest.

Õpitee

Tundmatu x leidmine miinusmärgist alates

Allikad (1)

Two centuries of the method being reinvented and misattributed, including how Gauss's name came to be on it: J. F. Grcar, "How ordinary elimination became Gaussian elimination." Historia Mathematica 38:2 (2011), 163–218.

7 Raven Roomi meeskond · Kontrollitud avaldatud allikate põhjal. Parandused on teretulnud.