Դիտել Գաուսի մեթոդ էջի վիքիկոդը

{{վիքիֆիկացում}}
[[Գծային հանրահաշիվ|Գծային հանրահաշվի]], '''Գաուսի մեթոդը''' (հայտնի է նաև '''շարքի նվազեցում''') [[ալգորիթմ]] է [[գծային հավասարումներ]] լուծելու համար։ Դա սովորաբար հասկացվում է որպես գործողությունների հաջորդականություն կապված [[մատրից (մաթեմատիկա)|մատրիցի]] գործակիցների հետ։ Այս մեթոդը կարող է օգտագործվել նաև գտնելու [[Կոչումը (գծային հանրահաշիվ)|կոչումը]] մատրիցով, հաշվարկելու [[որոշիչը]] մատրիցով, և [[շրջել մատրիցով]]։ Մեթոդը կոչվում է [[Կառլ Գաուս]]ի անունով, սակայն մինչև Գաուսն արդեն իսկ հայտնի էր։

Մատրիցում շարքի նվազեցում կատարելու համար պետք է կիրառել [[տարրական ձևափոխություններ]]ի հաջորդականություն՝ փոխելով մատրիցը մինչև մատրիցի ստորին ձախ անկյունը լցվի զրոներվ, որքան հնարավոր է։ Գոյություն ունեն երեք տեսակի տարրական ձևափոխություններ․

# գումարել մի տողի բազմապատիկը մեկ այլ տողի,
# բազմապատկել տողը ոչ զրոյական իրական թվով,
# տեղերով փոխել երկու տողեր։

Օգտագործելով այդ ձևափոխություններ՝ մատրիցը միշտ կարող է վերակազմավորվել [[եռանկյուն մատրից|վերին եռանկյուն մատրից]]ի։ Երբ բոլոր առաջատար գործակիցները (ձախից առաջին ոչ զրոյական տարրը յուրաքանչյուր տողում) 1 են, և ամեն առաջատար գործակից պարունակող սյունակում այլ տարրերը զրո են, ապա մատրիցը պետք է [[նվազեցվի անընդմեջ շարան կազմել ձևով]]։ Այս վերջնական ձևը եզակի է, այլ կերպ ասած, այն անկախ է շարքի գործունեությունների հաջորդականությամբ օգտագործվողների համար։ Օրինակ, հետևյալ շարքի գործունեությունների հաջորդականությունը (որտեղ մի քանի տարրական գործողություններ կարող է կատարվել յուրաքանչյուր քայլափոխին), իսկ երրորդ և չորրորդ մատրիցներն են նրանք, ում շարքը շարան կազմել ձևով է, իսկ վերջնական մատրիցը միակն է նվազեցված շարքի շարան կազմել ձևով.

:<math>\left[\begin{array}{rrr|r}
1 & 3 & 1 & 9 \\
1 & 1 & -1 & 1 \\
3 & 11 & 5 & 35
\end{array}\right]\to
\left[\begin{array}{rrr|r}
1 & 3 & 1 & 9 \\
0 & -2 & -2 & -8 \\
0 & 2 & 2 & 8
\end{array}\right]\to
\left[\begin{array}{rrr|r}
1 & 3 & 1 & 9 \\
0 & -2 & -2 & -8 \\
0 & 0 & 0 & 0
\end{array}\right]\to
\left[\begin{array}{rrr|r}
1 & 0 & -2 & -3 \\
0 & 1 & 1 & 4 \\
0 & 0 & 0 & 0
\end{array}\right] </math>

Օգտագործելով շարքի գործողությունները՝ փոխարկելով մի մատրիցը նվազեցված տողի շարան կազմել ձևով, երբեմն անվանում են '''Գաուս–Ջորդանի մեթոդ'''։ Որոշ հեղինակներ օգտագործում են Գաուսի մեթոդը՝ անդրադառնալու համար գործընթացին, մինչև այն հասնի է իր վերին եռանկյան, կամ (ոչ-նվազեցված) տողի շարան կազմել ձևին։ Հաշվողական պատճառների համար, երբ համակարգերի գծային հավասարումները լուծում են, երբեմն նախընտրելի է դադարեցնել անընդմեջ գործունեությունը մինչև մատրիցի ամբողջությամբ նվազելը։

== Սահմանումներ և ալգորիթմի օրինակ ==
Անընդմեջ նվազման գործընթացը օգտագործում է [[տարրական անընդմեջ գործողություններ]], և կարելի է բաժանել երկու մասի։ Առաջին մասը (երբեմն կոչվում է Փոխանցման Մեթոդ) նվազեցնում է տվյալ համակարգը ''անընդմեջ շարան կազմել ձևով'', որից կարելի է ասել, թե չկան լուծումներ, յուրահատուկ լուծում, կամ անսահման շատ լուծումներ։ Երկրորդ մասը (երբեմն կոչվում է [[Եռանկյուն մատրից#փոխանցում և ետ փոխարինում|ետ փոխարինում]]) շարունակում է՝ օգտագործելով անընդմեջ գործունեությունը, մինչև լուծումը գտնելը, այլ կերպ ասած, այն դնում է մատրիցը ''նվազեցված'' անընդմեջ շարան կազմել ձևով։

Մեկ այլ տեսակետ, որը պարզվում է շատ օգտակար է ալգորիթմը վերլուծելու համար, որը բուն մատրիցը [[մատրիցի տարրալուծումով]] կրճատում է։ Տարրական տող գործողությունները կարող են դիտվել որպես բազմապատկում բնօրինակ մատրիցը ձախ կողմը[[տարրական մատրիցի|տարրական մատրիցների]] կողմից։ Այնուհետև ալգորիթմի առաջին մասը հաշվում է մի [[LU կազմալուծում]], իսկ երկրորդ մասը գրում է օրիգինալ մատրիցը որպես բացառիկ մի ապրանքը հաշված մատրիցով և բացառիկ որոշված նվազեցված շարքը շարան կազմել մատրիցով։

=== Շարքի գործողությունները ===
{{see also|Elementary matrix}}

Գոյություն ունեն երեք տեսակի '''տարրական անընդմեջ գործունեություններ''', որոնք կարող են կատարվել շարքերում մի մատրիցով։
:'''Type 1''': փոխանակել դիրքերը երկու շարքերում.
:'''Type 2''': բազմապատկել շարքը [[սկալյար (մաթեմատիկա)|սկալյար]] ոչ զրոյական-ով.
:'''Type 3''': ավելացնել մեկ սկալյար շարքը բազմապատկելով մեկ այլով.

Եթե մատրիցը կապված է համակարգի գծային հավասարումների հետ, ապա այդ գործողությունները դեռ չեն փոխել լուծումը։ Հետևաբար, եթե մեկի նպատակն է լուծել համակարգի գծային հավասարումները, ապա օգտագործելով այդ անընդմեջ գործողությունները կարող ենք խնդիրը հեշտ լուծել։

=== Շարան կազմել ձևը ===
{{main|Row echelon form}}
Մատրիցի յուրաքանչյուր տողում, եթե շարքը կազմված է ոչ միայն զրոներից, ապա ձախ ոչ զրոյական մուտքը կոչվում է այդ շարքի ''[[առաջատար գործակից]]'' (կամ '' առանցք'')։ Այնպես որ, եթե երկու առաջատար գործակիցներ նույն սյունակում են, ապա տողի գործունեության 3 տեսակը (տես [[#Տողի գործունեություն|վերը]]) կարող է օգտագործվել որպես այդ գործակիցներից որևէ զրոյի մեկի հետ։ Այնուհետև շարքում օգտագործելով փոխանակել գործողությունը, կարելի է միշտ էլ պատվիրել շարքերը, այնպես որ յուրաքանչյուրը ոչ զրոյական շարք է, առաջատար գործակիցը առաջատար գործակցի շարքի աջ մասում է նշված։Սա այն դեպքն է, երբ մատրիցը պետք է' '''տողի Շարան կազմել ձևով''' լինի T. Այնպես որ, մատրիցի ստորին ձախ մասը պարունակում է միայն զրոներ, և բոլոր ստորև զրոյական շարքերում ոչ զրոյական տող են. "Շարան կազմել" բառը օգտագործվում է այստեղ, որովհետև կարելի է ենթադրել, որ շարքերը զբաղեցնում են իրենց չափը, ինչպես ամենախոշորը վերևում, այնպես էլ ամենափոքրը ներքևում։

Օրինակ, հետևյալ մատրիցը շարան կազմել ձևով է, և դրա առաջատար գործակիցները նշված են կարմիրով.

:<math>\left[ \begin{array}{cccc} 0&\color{red}{\mathbf{2}}&1&-1 \\ 0&0&\color{red}{\mathbf{3}}&1 \\ 0&0&0&0 \end{array} \right]</math>

Այն շարան կազմել ձևով է, քանի որ զրոյական տող է ներքևի մասում, իսկ առաջատար գործակիցը երկրորդ տողում (երրորդ սյունակում), աջ առաջատար գործակցի առաջին շարքում (երկրորդ սյունակում)։

Մատրիցը պետք է '''նվազեցվի տողի շարան կազմել ձևով''', եթե առաջատար գործակիցներից բոլորը հավասար են 1 (որին կարող է հասնել օգտագործելով տարրական շարք գործունեության 2 տեսակը), իսկ ամեն սյունակում նշվում է առաջատար գործակիցը, բոլոր մյուս գրառումները այդ սյունակում զրո են (որին կարող է հասնել օգտագործելով տարրական շարք գործունեության 3 տեսակը)։

=== Ալգորիթմի օրինակ ===
Ենթադրենք մեր նպատակն է գտնել և նկարագրել հետևյալ [[գծային հավասարումների համակարգը]]։
:<math>\begin{alignat}{7}
2x &&\; + \;&& y       &&\; - \;&& z &&\; = \;&& 8 & \qquad (L_1) \\
-3x &&\; - \;&& y       &&\; + \;&& 2z &&\; = \;&& -11 & \qquad (L_2) \\
-2x &&\; + \;&& y &&\; +\;&& 2z &&\; = \;&& -3 & \qquad (L_3)
\end{alignat}</math>

Հետևյալ աղյուսակում շարքի նվազեցումն գործընթացը միաժամանակ դիմում է համակարգի հավասարումներին, և դրա հարակից [[մատրիցի մեծացմանը]]։ Գործնականում, մեկը սովորաբար չի զբաղվում համակարգերի հավասարումներով, փոխարեն օգտվում ենք լրացվել մատրիցից, որն ավելի հարմար է համակարգչային մանիպուլյացիաների համար։ Շարքի կրճատման կարգը կարող են փոփվել հետևյալ կերպ՝ վերացնել ''x''-ը ստորև բոլոր հավասարումներում <math>L_1</math>, և հետո վերացնել ''y''-ը ստորև բոլոր հավասարումներում <math>L_2</math>։ Դա դրվում է համակարգի մեջ [[եռանկյան ձևով]]։ Այնուհետև, օգտագործում են back-փոխարինումը, յուրաքանչյուր անհայտ լուծելու համար։

{| style="width: 700px" border="1"
|-
!System of equations !! Row operations !! Augmented matrix
|- align="center"
| <math>\begin{alignat}{7}
2x &&\; + \;&& y       &&\; - \;&& z &&\; = \;&& 8 & \\
-3x &&\; - \;&& y       &&\; + \;&& 2z &&\; = \;&& -11 & \\
-2x &&\; + \;&& y &&\; +\;&& 2z &&\; = \;&& -3 & 
\end{alignat}</math> || || <math>
\left[ \begin{array}{ccc|c}
2 & 1 & -1 & 8 \\
-3 & -1 & 2 & -11 \\
-2 & 1 & 2 & -3
\end{array} \right]
</math>
|- align="center"
| <math>\begin{alignat}{7}
2x &&\; + && y &&\; - &&\; z &&\; = \;&& 8 & \\
&& && \frac{1}{2}y &&\; + &&\; \frac{1}{2}z &&\; = \;&& 1 & \\
&& && 2y &&\; + &&\; z &&\; = \;&& 5 & 
\end{alignat}</math> || <math>L_2 + \frac{3}{2}L_1 \rightarrow L_2</math> <br/> <math>L_3 + L_1 \rightarrow L_3</math> ||
<math>\left[ \begin{array}{ccc|c}
2 & 1 & -1 & 8 \\
0 & 1/2 & 1/2 & 1 \\
0 & 2 & 1 & 5
\end{array} \right]</math>
|- align="center"
| <math>\begin{alignat}{7}
2x &&\; + && y \;&& - &&\; z \;&& = \;&& 8 & \\
&& && \frac{1}{2}y \;&& + &&\; \frac{1}{2}z \;&& = \;&& 1 & \\
&& && && &&\; -z \;&&\; = \;&& 1 & 
\end{alignat}</math> || <math>L_3 + -4L_2 \rightarrow L_3</math> || <math>\left[ \begin{array}{ccc|c}
2 & 1 & -1 & 8 \\
0 & 1/2 & 1/2 & 1 \\
0 & 0 & -1 & 1
\end{array} \right] </math>
|-
| colspan=3 align="center"| The matrix is now in echelon form (also called triangular form)
|- align="center"
| <math>\begin{alignat}{7}
2x &&\; + && y \;&& &&\; \;&& = \;&& 7 & \\
&& && \frac{1}{2}y \;&& &&\; \;&& = \;&& 3/2 & \\
&& && && &&\; -z \;&&\; = \;&& 1 & 
\end{alignat}</math> || <math>L_2+\frac{1}{2}L_3 \rightarrow L_2</math> <br/> <math>L_1 - L_3 \rightarrow L_1 </math> || <math>\left[ \begin{array}{ccc|c}
2 & 1 & 0 & 7 \\
0 & 1/2 & 0 & 3/2 \\
0 & 0 & -1 & 1
\end{array} \right] </math>
|- align="center"
| <math>\begin{alignat}{7}
2x &&\; + && y \;&& &&\; \;&& = \;&& 7 & \\
&& && y \;&& &&\; \;&& = \;&& 3 & \\
&& && && &&\; z \;&&\; = \;&& -1 & 
\end{alignat}</math> || <math>2L_2 \rightarrow L_2</math> <br/> <math>-L_3 \rightarrow L_3 </math> || <math>\left[ \begin{array}{ccc|c}
2 & 1 & 0 & 7 \\
0 & 1 & 0 & 3 \\
0 & 0 & 1 & -1
\end{array} \right] </math>
|- align="center"
| <math>\begin{alignat}{7}
x &&\; && \;&& &&\; \;&& = \;&& 2 & \\
&& && y \;&& &&\; \;&& = \;&& 3 & \\
&& && && &&\; z \;&&\; = \;&& -1 & 
\end{alignat}</math> || <math>L_1 - L_2 \rightarrow L_1</math> <br/> <math>\frac{1}{2}L_1 \rightarrow L_1 </math> || <math>\left[ \begin{array}{ccc|c}
1 & 0 & 0 & 2 \\
0 & 1 & 0 & 3 \\
0 & 0 & 1 & -1
\end{array} \right] </math>
|}

Երկրորդ սյունակը բնութագրում է տողի գործունեությունը, որը պարզապես կատարվել է։ Այնպես որ, առաջին քայլը, ''x'' -ը վերացվի <math>L_2</math> ավելացնելօվ <math>\begin{matrix}\frac{3}{2}\end{matrix} L_1</math> <math>L_2</math> -ին։ Հաջորդ ''x'' -ը վերացվի <math>L_3</math> ավելացնելով <math>L_1</math> -ը <math>L_3</math> -ին։ Այս տողի գործողություններն անվանել է աղյուսակից, ինչպես

:<math>L_2 + \frac{3}{2}L_1 \rightarrow L_2</math>
:<math>L_3 + L_1 \rightarrow L_3.</math>

Երբ ''y'' -ը նույնպես վերացվում է երրորդ տողից, արդյունքը գծային հավասարումների համակարգն է եռանկյան ձևով, և ուստի ալգորիթմի առաջին մասը ավարտված է։ Հաշվողական տեսանկյունից, դա ավելի արագ լուծվում է փոփոխականների հակառակ հերթականությամբ, մի գործընթաց, որը հայտնի է որպես back-փոխարինման միջոց։ Մեկը տեսնում է լուծումը {{nowrap|z {{=}} -1}}, {{nowrap|y {{=}} 3}}, և {{nowrap|x {{=}} 2}}։ Այսպես այն այս հոդվածի բուն համակարգի հավասարումների եզակի լուծումն է։

Մատրիցը շարան կազմել ձևով լինելու դեպքում կանգնեցնու փոխարեն, կարելի էր շարունակել մինչև մատրիցը ''նվազեցվի'' տողի շարամ կազմել ձևով, ինչպես դա արվում է աղյուսակում։ Շարքը կրճատվում է մինչև մատրիցը նվազեցվում է, երբեմն կոչվում է '''Գաուս-Ջորդանի մեթոդ''', այն դադարեցվում է շարան կազմել ձևին հասնելուց հետո։

== Պատմություն ==
Գաուսի վերացման մեթոդը հայտնվում է կարևոր չինական մաթեմատիկական տեքստում[[Rod calculus#գծային հավասարումների սիստեմ|Բաժին ութ ''Ուղղանկյուն դասավորության'']] ''[[Մաթեմատիկական Արվեստի Ինը Գլուխներում]]''։ Դրա օգտագործումը պահեստավորված տասնութ խնդիրներում երկուսից հինգ հավասարումներով։ Գրքի սույն վերնագրի առաջին հղումը նվիրվում է 179 CE, բայց դրա հատվածներ գրվել է ավելի վաղ մոտ 150 BCE.<ref>{{harvtxt|Calinger|1999}}, pp. 234–236</ref><ref name="princeton">{{Cite book |author1=Timothy Gowers |url=https://archive.org/details/princetoncompani0000unse_i8p7 |title=The Princeton Companion to Mathematics |author2=June Barrow-Green |author3=Imre Leader |date=2008 թ․ սեպտեմբերի 8 |publisher=Princeton University Press |isbn=978-0-691-11880-2 |page=[https://archive.org/details/princetoncompani0000unse_i8p7/page/607 607]}}</ref> Այն մեկնաբանվել է [[Liu Hui]]-ի կողմից 3-րդ դարում։

Եվրոպայում մեթոդը բխում է [[Isaac Newton]]-ից.<ref>{{harvtxt|Grcar|2011a}}, pp. 169-172</ref><ref>{{harvtxt|Grcar|2011b}}, pp. 783-785</ref> 1670-ին, նա գրել է, որ բոլոր հանրահաշիվի գրքերը, որ հայտնի են իրեն, չուներ դրա լուծման համար միաժամանակյա հավասարումներ, ինչպես Newton-ը այնուհետև մատակարարում։ Քեմբրիջի համալսարանը ի վերջո հրապարակել է նշումներ ինչպես ''Arithmetica Universalis''-ին 1707-ին Newton ակադեմիական կյանքի ժամանակ։ Այն նշում է, որ լայնորեն ընդօրինակվել է, ընդօրինակել (այն, ինչ այժմ կոչվում է) Գաուսի մեթոդը ստանդարտ դաս հանրահաշիվ դասագրքերում 18-րդ դարի վերջից։ [[Կարլ Ֆրիդրիխ Գաուսը]] 1810-ին մշակել է սիմետրիկ վերացման նշումները, որը ընդունվել է 19-րդ դարում պրոֆեսիոնալ ձեռքի համակարգիչների կողմից, որոնք լուծում են քիչ քառակուսիների խնդիրները նորմալ հավասարումների միջոցով։ Իսկ ալգորիթմը, որը դասավանդվում է ավագ դպրոցում կոչվում է Գաուսի պատվին միայն 1950-ներից, արդյունքում առարկայի պատմության մեջ խառնաշփոթ է նկատվել։

Որոշ հեղինակներ օգտագործում են երկարաժամկետ ''Գաուսյան վերացումը'' անդրադառնաու համար միայն կարգից մինչև մատրիցը շարան կազմել ձևով, և օգտագործման ժամկետը '''Գաուս-Ջորդանի վերացման''' անդրադառնալու կարգին, որն ավարտվում է նվազեցվում էշելոն տեսքով։ Անունը օգտագործվում է, քանի որ դա Գաուսի վերացման տատանումներն են, նկարագրված է [[Վիլհեմ Ջորդանի (geodesist)|Վիլհոմ Ջորդանի]] կողմից 1887-ին։ Սակայն մեթոդը նույնպես հայտնվում է հոդվածում Clasen-ի կողմից հրապարակված նույն տարում։ Ջորդանը և Clasen-ը հավանաբար հայտնաբերել են Գաուս-Ջորդանի մեթոդը ինքնուրույն<ref>{{Citation |last1=Althoen |first1=Steven C. |title=Gauss–Jordan reduction: a brief history |journal=[[American Mathematical Monthly|The American Mathematical Monthly]] |volume=94 |issue=2 |pages=130–142 |year=1987 |publisher=Mathematical Association of America |doi=10.2307/2322413 |issn=0002-9890 |jstor=2322413 |last2=McLaughlin |first2=Renate}}</ref>։

== Ծրագրեր ==
Պատմականորեն տողի հաղթահարման մեթոդի առաջին դիմումը [[գծային հավասարումների համակարգերը]] լուծելու համար է։ Ահա որոշ այլ կարևոր ալգորիթմի ծրագրեր։

=== Հաշվողական որոշիչ ===
Բացատրել, թե ինչպես Գաուսի մեթոդը թույլ է տալիս հաշվարկել որոշիչը քառակուսի մատրիցով, մենք պետք է հիշենք, թե ինչպես է տարրական տողի գործողությունները փոխում որոշիչը։
* Փոխանակման որոշիչի երկու տողերը բազմապատկում ենք -1-ով
* Բազմապատկել շարքը ոչ զրոյական scalar որոշիչով նույն scalar-ով
* Ավելացնել մեկ սկալյար շարքը բազմապատկելով մեկ այլով։

Եթե Գաուսի վերացումը դիմում է քառակուսի մատրիցով, ''A'' արտադրում է անընդմեջ շարան կազմել մատրից ''B'' -ով, նշենք ''d'' սկալյար արդյունք է, որով որոշիչը բազմապատկվում է, օգտագործելով վերևի կանոնները.
Այնուհետև ''A'' որոշիչը քանորդ է ''d'' ապրանքի վերաբերյալ տարրերի ''B'' անկյունագիծը.

Պետք է ընդգծել, որ ''n''×''n'' մատրիցը, այս մեթոդի կարիքների [[O notation|''O''(''n''<sup>3</sup>)]] թվաբանություն գործառնություններն են, մինչ տարրական մեթոդները, սովորաբար սովորեցնում են տարրական դասընթացները, անհրաժեշտ է ''O''(2<sup>''n''</sup>)) կամ ''O''(''n''!) գործառնություններին։ Սա ստիպում է նրանց լիովին անիրագործելի լինել, նույնիսկ ամենաարագ համակարգիչները, որքան ''n'' ≥ 10.

=== Գտնել մատրիցի հակառակը ===
{{see also|Invertible matrix}}
Գաուսյան վերացման մի տարբերակը կոչվում է Գաուս-Ջորդան վերացում, որը կարող է օգտագործվել գտնելու հակառակ մատրիցը, եթե այն գոյություն ունի։ Եթե ''A'' -ն ''n'' -ի ''n'' քառակուսի մատրից է, կարելի է օգտագործել շարքով նվազումը հաշվելով [[հակառակ մատրիցը]], եթե այն գոյություն ունի։ Նախ, ''n'' -ի ''n'' [[պատկանելության մատրիցը]] լրացվել է ''A'' իրավունքվ, կազմելով ''n''-ի 2''n'' [[բլոկ մատրիցը]] [''A'' | ''I'']։ Այժմ կիրառման տարրական անընդմեջ գործողությունների միջոցով, գտնել արտոնյալ էշելոն ձևը սույն ''n'' -ի ''2n'' մատրիցով։ Մատրից ''A''-ն շրջվում է, եթե միայն այն դեպքում, եթե ձախ բլոկը կարող է կրճատվել մինչև ինքնության մատրից ''I'' այս դեպքում ճիշտ բլոկի վերջնական մատրիցը ''A'' <sup> −1</sup> է։ Եթե ալգորիթմը չի կարող նվազեցնել ''I''-ի ձախ բլոկը, ապա ''A'' -ն շրջելի չէ։

Օրինակ, քննարկենք հետևյալ մատրիցը

:<math> A =
\begin{bmatrix}
2 & -1 & 0 \\
-1 & 2 & -1 \\
0 & -1 & 2
\end{bmatrix}.
</math>

Գտնել այս մատրիցի հակառակը, հետևյալ մատրիցը լրացվում է ինքնության կողմից, և տողը նվազեցնում է 3-ը 6 մատրիցով։
:<math> [ A | I ] = 
\left[ \begin{array}{rrr|rrr}
2 & -1 & 0 & 1 & 0 & 0\\
-1 & 2 & -1 & 0 & 1 & 0\\
0 & -1 & 2 & 0 & 0 & 1
\end{array} \right].
</math>

Ըստ տողի գործողությունների կատարման, կարելի է ստուգել, որ կրճատվել է լրացված մատրիցի շարան կազմել ձևի վիճաբանությունը։

:<math> [ I | B ] = 
\left[ \begin{array}{rrr|rrr}
1 & 0 & 0 & \frac{3}{4} & \frac{1}{2} & \frac{1}{4}\\[3pt]
0 & 1 & 0 & \frac{1}{2} & 1 & \frac{1}{2}\\[3pt]
0 & 0 & 1 & \frac{1}{4} & \frac{1}{2} & \frac{3}{4}
\end{array} \right].
</math>

Ձախ մատրիցը ինքնություն է, որը ցույց է տալիս ''A''-ի շրջվելը. 3-ի 3 մատրիցը աջ մասում, ''B''-ն, ''A'' -ի հակառակն է։ Այս գործընթացը գտնելու համար կատարվում է հակառակ աշխատանքները քառակուսի մատրիցի ցանկացած չափով։

=== Հաշվողական կոչումները և հիմքերը ===
Գաուսի մեթոդը կարող է կիրառվել ցանկացած <math>m \times n</math> matrix <math>A</math>. In this way, for example, some <math>6 \times 9</math> matrices can be transformed to a matrix that has a row echelon form like
:<math> T=
\begin{bmatrix}
a & * & * & *& * & * & * & * & * \\
0 & 0 & b & * & * & * & * & * & * \\
0 & 0 & 0 & c & * & * & * & * & * \\
0 & 0 & 0 & 0 & 0 & 0 & d & * & * \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & e \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0
\end{bmatrix}
</math>

որտեղ *s կամայական մուտքեր են և ''a, b, c, d, e'' ոչ զրոյական գրառումներ։ Այս էշելոն մատրիցը <math>T</math> պարունակում է հարուստ տեղեկություններ <math>A</math>։ <math>A</math> [[մատրիցի կոչումը|կոչումը]] 5 է, քանի որ կան 5 ոչ զրոյական տողեր <math>T</math> -ում [[վեկտորի տարածքը]] ձգվում է <math>A</math> սյուների կողմից ունի հիմք բաղկացած առաջին, երրորդ, չորրորդ, յոթերորդ և իններորդ սյունակներ <math>A</math> ( ''a, b, c, d, e'' սյունակներից <math>T</math> -ում), և *s պատմում է Ձեզ, թե ինչպես է այլ <math>A</math> սյունակները կարելի է գրել նաև հիմքերի սյուների գծային զուգորդումներով։ Սա հետևանք է տարածելու [[dot ապրանքը]] գծային քարտեզի արտահայտությամբ [[Գծային քարտեզ#մատրիցներ|որպես մատրից]]։

Այս ամենը վերաբերում է նաև արտոնյալ տողի շարան կազմել ձևին, որը, մասնավորապես, տեղի շարան կազմել ձևն է։

== Հաշվողական արդյունավետությունը ==
Թիվի թվաբանական գործողությունների համար անհրաժեշտ է կատարել շարքով նվազում ալգորիթմի ծանոթությունների հաշվողական արդյունավետության չափման միջոցով։ Օրինակ, լուծել ''n'' համակարգի հավասարումների ''n'' անհայտները կատարելով տողի գործառնությունների մատրիցով, մինչև շարան կազմել ձևով, ապա ապա լուծել յուրաքանչյուր անհայտ հակառակ հերթականությամբ, պահանջում է ''n''(''n''-1) / 2 բաժանումներ, (2''n''<sup>3</sup> + 3''n''<sup>2</sup> − 5''n'')/6 բազմապատկումներ, և (2''n''<sup>3</sup> + 3''n''<sup>2</sup> − 5''n'')/6 հանումներ<ref>{{harvtxt|Farebrother|1988}}, p. 12</ref>, ընդհանուրի համար մոտ 2''n''<sup>3</sup> / 3 գործողություններ. Այսպիսով այն ունի [[Թվաբանական#Թվաբանական գործողությունների|թվաբանական]] բարդություն O(''n''<sup>3</sup>) see [[Big O notation]]։ Այս թվաբանական բարդությունը ժամանակի լավ միջոց է, անհրաժեշտ է ողջ հաշվարկի համար, երբ յուրաքանչյուր թվաբանական գործողության ժամանակը մոտավոր հաստատուն է։ Սա այն դեպքն է, երբ գործակիցները ներկայացված են [[լողացող կետերի համար]] կամ երբ նրանք պատկանում են [[վերջավոր դաշտի]]։ Եթե գործակիցները [[integer (թվեր)]] կամ [[ռացիոնալ թվեր]] են ներկայացված, միջանկյալ գրառում կարող է աճել էքսպոնենտալ մեծ, այնպես որ [[բիտի բարդությունը]] էքսպոնենտալ է.<ref>{{Cite conference |last1=Fang |first1=Xin Gui |last2=Havas |first2=George |year=1997 |title=On the worst-case complexity of integer Gaussian elimination |url=http://itee.uq.edu.au/~havas/fh97.pdf |conference=ISSAC '97 |location=Kihei, Maui, Hawaii, United States |publisher=ACM |pages=28–31 |doi=10.1145/258726.258740 |isbn=0-89791-875-4 |book-title=Proceedings of the 1997 international symposium on Symbolic and algebraic computation}}{{Չաշխատող արտաքին հղում|bot=InternetArchiveBot }}</ref>
Սակայն կա Գաուսի վերացման մի տարբերակ, որը կոչվում է [[Bareiss ալգորիթմ]], որը խուսափում է միջանկյալ մուտքերի էքսպոնենտալ աճին, և, նույն թվաբանական բարդությունը O(''n''<sup>3</sup>), ունի մի քիչ բարդությունը O(''n''<sup>5</sup>)։

Այս ալգորիթմը կարող է օգտագործվել համակարգչի համակարգերի համար հազարավոր հավասարումների և անհայտների հետ։ Սակայն գինը դառնում է արգելքային համակարգերի համար միլիոնավոր հավասարումների հետ։ Այս խոշոր համակարգերը հիմնականում լուծվում են օգտագործելով [[iterative եղանակը]]։ Հատուկ մեթոդներ կան համակարգերի համար, որոնց գործակիցները հետևում են հերթական օրինակին (տես [[գծային հավասարումների համակարգ]])։.

Դնելով ''n'' -ի ''n'' մատրիցի մեջ տողի գործառնությունները նվազեցվում են էշելոն ձևով, անհրաժեշտ է <math>n^3</math> թվաբանության գործողությունների համար, ինչը մոտ 50% - ով ավելի է հաշվարկում քայլերը<ref>J. B. Fraleigh and R. A. Beauregard, Linear Algebra. Addison-Wesley Publishing Company, 1995, Chapter 10</ref>։

Հնարավոր է խնդիրից մեկը [[թվային կայունությունն է|թվային անկայունությունն է]], պայմանավորված հնարավոր շատ փոքր համարներ բազանելով։ Եթե օրինակ, առաջատար գործակիցը շարքերից մեկում շատ մոտ է զրոյի, ապա անընդմեջ կրճատել մատրիցը մեկով անհրաժեշտ կլինի բաժանել այդ համարը, ուստի առաջատար գործակիցը 1 է։ Սա նշանակում է, որ թվում գոյություն ունեցող ցանկացած սխալ, որը մոտ է զրոյին կմեծացվի։ Գաուսյան վերացումը թվականորեն կայուն է [[շեղակի գերիշխող]] կամ [[Դրական-որոշակի մատրիցի|դրական-կոնկրետ]] մատրիցների համար։ Ընդհանուր մատրիցների համար, Գաուսյան վերացումը սովորաբար համարվում է կայուն, երբ, օգտագործում ենք [[առանցքի տարր#մասնակի եւ ամբողջական առանցք|մասնակի առանցք]], չնայած կան կայուն մատրիցների օրինակներ, որոնց համար դա անկայուն է.<ref>{{harvtxt|Golub|Van Loan|1996}}, §3.4.6</ref>

=== Ընդհանրացումները ===
Գաուսի վերացումը կարող է իրականացնել ավելի քան որևէ այլ [[ոլորտում (մաթեմատիկա)|ոլորտում]], ոչ միայն իրական թվերում։

Գաուսյան վերացումը չի ընդհանրացնել որևէ պարզ միջոցի բարձրագույն կարգի [[tensors]] (մատրիցներ են [[զանգվածի տվյալների կառուցվածքը|զանգվածի]] ներկայացուցչությունները գործում են 2 tensors) նույնիսկ համակարգչային tensor կոչումը կարգը ավելի է, քան 2 դժվար խնդիրը։

== Կեղծ կոդը ==
Ինչպես բացատրեց վերևում, Գաուսյան վերացումը գրում է տվյալ ''m'' &times ''n'' մատրիցի ''A''-ն բացառիկ է որպես արդյունքի շրջում ''m'' &times ''m'' matrix ''S'' և տողի-էշելոն մատրիցը ''T''։ Այստեղ, ''S''-ի մատրիցների արտադրանքը համապատասխան գործառնությունների շարքում։

Պաշտոնական ալգորիթմ են հաշվարկել <math>T</math> from <math>A</math> հետևյալները։ Մենք գրում ենք <math>A[i, j]</math> այս շարքում մտնելու համար <math>i</math>, սյունակ <math>j</math> մատրիցում <math>A</math> 1-ով լինելով առաջին ինդեքս։ Տրանսֆորմացիան իրականացվում է "տեղում", ինչը նշանակում է, որ բնօրինակ մատրիցը <math>A</math> կորել է և հետևողականորեն փոխարինվում է <math>T</math> կողմից։

<code>
 '''for''' k = 1 ... m:
  ''Find pivot for column k:''
  i_max := [[argmax]] (i = k ... m, abs(A[i, k]))
  '''if''' A[i_max, k] = 0
   '''error''' "Matrix is singular!"
  '''swap rows'''(k, i_max)
  ''Do for all rows below pivot:''
  '''for''' i = k + 1 ... m:
   ''Do for all remaining elements in current row:''
   '''for''' j = k + 1 ... n:
    A[i, j] := A[i, j] - A[k, j] * (A[i, k] / A[k, k])
   ''Fill lower triangular matrix with zeros:''
   A[i, k] := 0
</code>

Այս ալգորիթմը մի փոքր տարբերվում է այն մեկից ավելի վաղ քննարկված է, քանի որ նախքան փոփոխականի վերացմանը, այն առաջին փոխանակում է տողերը տեղափոխելով մուտքի հետ ամենամեծ [[բացարձակ արժեքը]] "առանցք դիրքորոշման"։ Նման "մասնակի դիրքորոշումը" բարելավում է ալգորիթմի թվային կայունությունը (տես նաև [[առանցքի տարր]]) որոշ տարբերակներ են նաև օգտագործվում։

Սույն կարգի ավարտից հետո լրացված մատրիցը կլինի [[տողի-էշելոն ձևով]] և կարող է լուծվել փոխարինման միջոցով։

Ժամանակակից համակարգիչներում, Գաուսյան վերացումը միշտ չէ ամենաարագ ալգորիթմը հաշվարկելու շարքը էշելոն մատրիցով t ժամանակակից համակարգիչներ։ Կան [[գրադարան(computing)|համակարգչի գրադարաններ]], ինչպես [[BLAS]], որոնք [[համակարգիչնեի բաղկացուցիչ մասերի]] առանձնահատկություններն են օգտագործում և մատրիցի կառուցվածքով ինքնաբերաբար ընտրում է լավագույն ալգորիթմը։

== Նշումներ ==
{{Ծանցանկ}}

== Ծանոթագրություններ ==
* {{Citation |last1=Atkinson |first1=Kendall A. |title=An Introduction to Numerical Analysis |year=1989 |edition=2nd |location=New York |publisher=[[John Wiley & Sons]] |isbn=978-0-471-50023-0}}.
* {{Citation |last1=Bolch |first1=Gunter |title=Queueing Networks and Markov Chains: Modeling and Performance Evaluation with Computer Science Applications |year=2006 |edition=2nd |publisher=[[Wiley-Interscience]] |isbn=978-0-471-79156-0 |last2=Greiner |first2=Stefan |last3=de Meer |first3=Hermann |last4=Trivedi |first4=Kishor S.}}.
* {{Citation |last1=Calinger |first1=Ronald |title=A Contextual History of Mathematics |year=1999 |publisher=[[Prentice Hall]] |isbn=978-0-02-318285-3}}.
* {{Citation |last1=Farebrother |first1=R.W. |title=Linear Least Squares Computations |year=1988 |series=STATISTICS: Textbooks and Monographs |publisher=Marcel Dekker |isbn=978-0-8247-7661-9}}.
* {{Citation |last1=Golub |first1=Gene H. |title=Matrix Computations |year=1996 |edition=3rd |publisher=Johns Hopkins |isbn=978-0-8018-5414-9 |last2=Van Loan |first2=Charles F. |author1-link=Gene H. Golub |author2-link=Charles F. Van Loan}}.
* {{Citation |last=Grcar |first=Joseph F. |title=How ordinary elimination became Gaussian elimination |journal=Historia Mathematica |volume=38 |issue=2 |pages=163–218 |year=2011a |arxiv=0907.2397 |doi=10.1016/j.hm.2010.06.003}}
* {{Citation |last=Grcar |first=Joseph F. |title=Mathematicians of Gaussian elimination |journal=Notices of the American Mathematical Society |volume=58 |issue=6 |pages=782–792 |year=2011b |url=http://www.ams.org/notices/201106/rtx110600782p.pdf}}
* {{Citation |last1=Higham |first1=Nicholas |title=Accuracy and Stability of Numerical Algorithms |year=2002 |edition=2nd |publisher=[[Society for Industrial and Applied Mathematics|SIAM]] |isbn=978-0-89871-521-7 |author1-link=Nicholas Higham}}.
* {{Citation |last1=Katz |first1=Victor J. |title=A History of Mathematics, Brief Version |year=2004 |publisher=[[Addison-Wesley]] |isbn=978-0-321-16193-2}}.
* {{Cite web |last1=Kaw |first1=Autar |last2=Kalu |first2=Egwu |year=2010 |title=Numerical Methods with Applications |url=http://www.autarkaw.com |edition=1st}}, Chapter 5 deals with Gaussian elimination.
* {{Citation |last1=Lipson |first1=Marc |title=Schaum's outline of theory and problems of linear algebra |pages=69–80 |year=2001 |location=New York |publisher=[[McGraw-Hill]] |isbn=978-0-07-136200-9 |last2=Lipschutz |first2=Seymour}}.
* {{Citation |last1=Press |first1=WH |title=Numerical Recipes: The Art of Scientific Computing |year=2007 |url-status=dead |chapter=Section 2.2 |chapter-url=http://apps.nrbook.com/empanel/index.html?pg=46 |edition=3rd |publication-place=New York |publisher=Cambridge University Press |isbn=978-0-521-88068-8 |last2=Teukolsky |first2=SA |last3=Vetterling |first3=WT |last4=Flannery |first4=BP |accessdate=2013 թ․ հունիսի 1 |archivedate=2012 թ․ մարտի 19 |archiveurl=https://web.archive.org/web/20120319193237/http://apps.nrbook.com/empanel/index.html?pg=46}}

== Արտաքին հղումներ ==
{{wikibooks
|1= Linear Algebra
|2= Gauss' Method
|3= Gaussian elimination}}
* [http://sole.ooz.ie WebApp descriptively solving systems of linear equations with Gaussian Elimination] {{Webarchive|url=https://archive.today/20110425223706/http://sole.ooz.ie/ |date=2011-04-25 }}
* [http://marekrychlik.com/cgi-bin/gauss.cgi A program that performs Gaussian elimination similarly to a human working on paper] {{Webarchive|url=https://web.archive.org/web/20140219162950/http://marekrychlik.com/cgi-bin/gauss.cgi |date=2014-02-19 }} Exact solutions to systems with rational coefficients.
* [http://www.math-linux.com/spip.php?article53 Gaussian elimination] {{Webarchive|url=https://web.archive.org/web/20100524164649/http://www.math-linux.com/spip.php?article53 |date=2010-05-24 }} www.math-linux.com.
* [http://www25.brinkster.com/denshade/GaussElimination.html Gaussian elimination as java applet] {{Webarchive|url=https://web.archive.org/web/20060812215904/http://www25.brinkster.com/denshade/GaussElimination.html |date=2006-08-12 }} at some local site. Only takes natural coefficients.
* [http://people.revoledu.com/kardi/tutorial/LinearAlgebra/RREF.html#RREF Gaussian elimination calculator] with Linear Algebra tutorial.
* [http://numericalmethods.eng.usf.edu/topics/gaussian_elimination.html Gaussian elimination] at [http://numericalmethods.eng.usf.edu Holistic Numerical Methods Institute]
* [http://www.hlevkin.com/default.html#numalg LinearEquations.c] {{Webarchive|url=https://web.archive.org/web/20111022215040/http://www.hlevkin.com/default.html#numalg |date=2011-10-22 }} Gaussian elimination implemented using C language
* [http://www.math.iupui.edu/~momran/m118/chapter6.htm Gauss–Jordan elimination] {{Webarchive|url=https://web.archive.org/web/20100317150740/http://www.math.iupui.edu/~momran/m118/chapter6.htm |date=2010-03-17 }} Step by step solution of 3 equations with 3 unknowns using the All-Integer Echelon Method
* [http://www.idomaths.com/gauss_jordan.php Gauss-Jordan Elimination calculator for ''n'' by ''m'' matrices, giving intermediate steps]
* {{YouTube|id=u-AhI4gNB_E|title=WildLinAlg13: Solving a system of linear equations}} provides a very clear, elementary presentation of the method of row reduction.

[[Կատեգորիա:Գծային հանրահաշիվ]]