Գաուսի մեթոդ

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

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

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

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

$\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]$

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

Սահմանումներ և ալգորիթմի օրինակ

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

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

Շարքի գործողությունները

Տե՛ս նաև՝ Elementary matrix

Գոյություն ունեն երեք տեսակի տարրական անընդմեջ գործունեություններ, որոնք կարող են կատարվել շարքերում մի մատրիցով։

Type 1: փոխանակել դիրքերը երկու շարքերում.

Type 2: բազմապատկել շարքը սկալյար ոչ զրոյական-ով.

Type 3: ավելացնել մեկ սկալյար շարքը բազմապատկելով մեկ այլով.

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

Շարան կազմել ձևը

Հիմնական հոդված՝ Row echelon form

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

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

$\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]$

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

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

Ալգորիթմի օրինակ

Ենթադրենք մեր նպատակն է գտնել և նկարագրել հետևյալ գծային հավասարումների համակարգը։

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

Հետևյալ աղյուսակում շարքի նվազեցումն գործընթացը միաժամանակ դիմում է համակարգի հավասարումներին, և դրա հարակից մատրիցի մեծացմանը։ Գործնականում, մեկը սովորաբար չի զբաղվում համակարգերի հավասարումներով, փոխարեն օգտվում ենք լրացվել մատրիցից, որն ավելի հարմար է համակարգչային մանիպուլյացիաների համար։ Շարքի կրճատման կարգը կարող են փոփվել հետևյալ կերպ՝ վերացնել x-ը ստորև բոլոր հավասարումներում $L_{1}$, և հետո վերացնել y-ը ստորև բոլոր հավասարումներում $L_{2}$։ Դա դրվում է համակարգի մեջ եռանկյան ձևով։ Այնուհետև, օգտագործում են back-փոխարինումը, յուրաքանչյուր անհայտ լուծելու համար։

System of equations	Row operations	Augmented matrix
${\begin{alignedat}{7}2x&&\;+\;&&y&&\;-\;&&z&&\;=\;&&8&\\-3x&&\;-\;&&y&&\;+\;&&2z&&\;=\;&&-11&\\-2x&&\;+\;&&y&&\;+\;&&2z&&\;=\;&&-3&\end{alignedat}}$		$\left[{\begin{array}{ccc|c}2&1&-1&8\\-3&-1&2&-11\\-2&1&2&-3\end{array}}\right]$
${\begin{alignedat}{7}2x&&\;+&&y&&\;-&&\;z&&\;=\;&&8&\\&&&&{\frac {1}{2}}y&&\;+&&\;{\frac {1}{2}}z&&\;=\;&&1&\\&&&&2y&&\;+&&\;z&&\;=\;&&5&\end{alignedat}}$	$L_{2}+{\frac {3}{2}}L_{1}\rightarrow L_{2}$ $L_{3}+L_{1}\rightarrow L_{3}$	$\left[{\begin{array}{ccc|c}2&1&-1&8\\0&1/2&1/2&1\\0&2&1&5\end{array}}\right]$
${\begin{alignedat}{7}2x&&\;+&&y\;&&-&&\;z\;&&=\;&&8&\\&&&&{\frac {1}{2}}y\;&&+&&\;{\frac {1}{2}}z\;&&=\;&&1&\\&&&&&&&&\;-z\;&&\;=\;&&1&\end{alignedat}}$	$L_{3}+-4L_{2}\rightarrow L_{3}$	$\left[{\begin{array}{ccc|c}2&1&-1&8\\0&1/2&1/2&1\\0&0&-1&1\end{array}}\right]$
The matrix is now in echelon form (also called triangular form)
${\begin{alignedat}{7}2x&&\;+&&y\;&&&&\;\;&&=\;&&7&\\&&&&{\frac {1}{2}}y\;&&&&\;\;&&=\;&&3/2&\\&&&&&&&&\;-z\;&&\;=\;&&1&\end{alignedat}}$	$L_{2}+{\frac {1}{2}}L_{3}\rightarrow L_{2}$ $L_{1}-L_{3}\rightarrow L_{1}$	$\left[{\begin{array}{ccc|c}2&1&0&7\\0&1/2&0&3/2\\0&0&-1&1\end{array}}\right]$
${\begin{alignedat}{7}2x&&\;+&&y\;&&&&\;\;&&=\;&&7&\\&&&&y\;&&&&\;\;&&=\;&&3&\\&&&&&&&&\;z\;&&\;=\;&&-1&\end{alignedat}}$	$2L_{2}\rightarrow L_{2}$ $-L_{3}\rightarrow L_{3}$	$\left[{\begin{array}{ccc|c}2&1&0&7\\0&1&0&3\\0&0&1&-1\end{array}}\right]$
${\begin{alignedat}{7}x&&\;&&\;&&&&\;\;&&=\;&&2&\\&&&&y\;&&&&\;\;&&=\;&&3&\\&&&&&&&&\;z\;&&\;=\;&&-1&\end{alignedat}}$	$L_{1}-L_{2}\rightarrow L_{1}$ ${\frac {1}{2}}L_{1}\rightarrow L_{1}$	$\left[{\begin{array}{ccc|c}1&0&0&2\\0&1&0&3\\0&0&1&-1\end{array}}\right]$

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

$L_{2}+{\frac {3}{2}}L_{1}\rightarrow L_{2}$

$L_{3}+L_{1}\rightarrow L_{3}.$

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

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

Պատմություն

Գաուսի վերացման մեթոդը հայտնվում է կարևոր չինական մաթեմատիկական տեքստումԲաժին ութ Ուղղանկյուն դասավորության Մաթեմատիկական Արվեստի Ինը Գլուխներում։ Դրա օգտագործումը պահեստավորված տասնութ խնդիրներում երկուսից հինգ հավասարումներով։ Գրքի սույն վերնագրի առաջին հղումը նվիրվում է 179 CE, բայց դրա հատվածներ գրվել է ավելի վաղ մոտ 150 BCE. Այն մեկնաբանվել է Liu Hui-ի կողմից 3-րդ դարում։

Եվրոպայում մեթոդը բխում է Isaac Newton-ից. 1670-ին, նա գրել է, որ բոլոր հանրահաշիվի գրքերը, որ հայտնի են իրեն, չուներ դրա լուծման համար միաժամանակյա հավասարումներ, ինչպես Newton-ը այնուհետև մատակարարում։ Քեմբրիջի համալսարանը ի վերջո հրապարակել է նշումներ ինչպես Arithmetica Universalis-ին 1707-ին Newton ակադեմիական կյանքի ժամանակ։ Այն նշում է, որ լայնորեն ընդօրինակվել է, ընդօրինակել (այն, ինչ այժմ կոչվում է) Գաուսի մեթոդը ստանդարտ դաս հանրահաշիվ դասագրքերում 18-րդ դարի վերջից։ Կարլ Ֆրիդրիխ Գաուսը 1810-ին մշակել է սիմետրիկ վերացման նշումները, որը ընդունվել է 19-րդ դարում պրոֆեսիոնալ ձեռքի համակարգիչների կողմից, որոնք լուծում են քիչ քառակուսիների խնդիրները նորմալ հավասարումների միջոցով։ Իսկ ալգորիթմը, որը դասավանդվում է ավագ դպրոցում կոչվում է Գաուսի պատվին միայն 1950-ներից, արդյունքում առարկայի պատմության մեջ խառնաշփոթ է նկատվել։

Որոշ հեղինակներ օգտագործում են երկարաժամկետ Գաուսյան վերացումը անդրադառնաու համար միայն կարգից մինչև մատրիցը շարան կազմել ձևով, և օգտագործման ժամկետը Գաուս-Ջորդանի վերացման անդրադառնալու կարգին, որն ավարտվում է նվազեցվում էշելոն տեսքով։ Անունը օգտագործվում է, քանի որ դա Գաուսի վերացման տատանումներն են, նկարագրված է Վիլհոմ Ջորդանի կողմից 1887-ին։ Սակայն մեթոդը նույնպես հայտնվում է հոդվածում Clasen-ի կողմից հրապարակված նույն տարում։ Ջորդանը և Clasen-ը հավանաբար հայտնաբերել են Գաուս-Ջորդանի մեթոդը ինքնուրույն։

Ծրագրեր

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

Հաշվողական որոշիչ

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

• Փոխանակման որոշիչի երկու տողերը բազմապատկում ենք -1-ով
• Բազմապատկել շարքը ոչ զրոյական scalar որոշիչով նույն scalar-ով
• Ավելացնել մեկ սկալյար շարքը բազմապատկելով մեկ այլով։

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

Պետք է ընդգծել, որ n×n մատրիցը, այս մեթոդի կարիքների O(n³) թվաբանություն գործառնություններն են, մինչ տարրական մեթոդները, սովորաբար սովորեցնում են տարրական դասընթացները, անհրաժեշտ է O(2ⁿ)) կամ O(n!) գործառնություններին։ Սա ստիպում է նրանց լիովին անիրագործելի լինել, նույնիսկ ամենաարագ համակարգիչները, որքան n ≥ 10.

Գտնել մատրիցի հակառակը

Տե՛ս նաև՝ Invertible matrix

Գաուսյան վերացման մի տարբերակը կոչվում է Գաուս-Ջորդան վերացում, որը կարող է օգտագործվել գտնելու հակառակ մատրիցը, եթե այն գոյություն ունի։ Եթե A -ն n -ի n քառակուսի մատրից է, կարելի է օգտագործել շարքով նվազումը հաշվելով հակառակ մատրիցը, եթե այն գոյություն ունի։ Նախ, n -ի n պատկանելության մատրիցը լրացվել է A իրավունքվ, կազմելով n-ի 2n բլոկ մատրիցը [A | I]։ Այժմ կիրառման տարրական անընդմեջ գործողությունների միջոցով, գտնել արտոնյալ էշելոն ձևը սույն n -ի 2n մատրիցով։ Մատրից A-ն շրջվում է, եթե միայն այն դեպքում, եթե ձախ բլոկը կարող է կրճատվել մինչև ինքնության մատրից I այս դեպքում ճիշտ բլոկի վերջնական մատրիցը A ⁻¹ է։ Եթե ալգորիթմը չի կարող նվազեցնել I-ի ձախ բլոկը, ապա A -ն շրջելի չէ։

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

$A={\begin{bmatrix}2&-1&0\\-1&2&-1\\0&-1&2\end{bmatrix}}.$

Գտնել այս մատրիցի հակառակը, հետևյալ մատրիցը լրացվում է ինքնության կողմից, և տողը նվազեցնում է 3-ը 6 մատրիցով։

$[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].$

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

$[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].$

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

Հաշվողական կոչումները և հիմքերը

Գաուսի մեթոդը կարող է կիրառվել ցանկացած $m\times n$ matrix $A$. In this way, for example, some $6\times 9$ matrices can be transformed to a matrix that has a row echelon form like

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

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

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

Հաշվողական արդյունավետությունը

Թիվի թվաբանական գործողությունների համար անհրաժեշտ է կատարել շարքով նվազում ալգորիթմի ծանոթությունների հաշվողական արդյունավետության չափման միջոցով։ Օրինակ, լուծել n համակարգի հավասարումների n անհայտները կատարելով տողի գործառնությունների մատրիցով, մինչև շարան կազմել ձևով, ապա ապա լուծել յուրաքանչյուր անհայտ հակառակ հերթականությամբ, պահանջում է n(n-1) / 2 բաժանումներ, (2n³ + 3n² − 5n)/6 բազմապատկումներ, և (2n³ + 3n² − 5n)/6 հանումներ, ընդհանուրի համար մոտ 2n³ / 3 գործողություններ. Այսպիսով այն ունի թվաբանական բարդություն O(n³) see Big O notation։ Այս թվաբանական բարդությունը ժամանակի լավ միջոց է, անհրաժեշտ է ողջ հաշվարկի համար, երբ յուրաքանչյուր թվաբանական գործողության ժամանակը մոտավոր հաստատուն է։ Սա այն դեպքն է, երբ գործակիցները ներկայացված են լողացող կետերի համար կամ երբ նրանք պատկանում են վերջավոր դաշտի։ Եթե գործակիցները integer (թվեր) կամ ռացիոնալ թվեր են ներկայացված, միջանկյալ գրառում կարող է աճել էքսպոնենտալ մեծ, այնպես որ բիտի բարդությունը էքսպոնենտալ է. Սակայն կա Գաուսի վերացման մի տարբերակ, որը կոչվում է Bareiss ալգորիթմ, որը խուսափում է միջանկյալ մուտքերի էքսպոնենտալ աճին, և, նույն թվաբանական բարդությունը O(n³), ունի մի քիչ բարդությունը O(n⁵)։

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

Դնելով n -ի n մատրիցի մեջ տողի գործառնությունները նվազեցվում են էշելոն ձևով, անհրաժեշտ է $n^{3}$ թվաբանության գործողությունների համար, ինչը մոտ 50% - ով ավելի է հաշվարկում քայլերը։

Հնարավոր է խնդիրից մեկը թվային անկայունությունն է, պայմանավորված հնարավոր շատ փոքր համարներ բազանելով։ Եթե օրինակ, առաջատար գործակիցը շարքերից մեկում շատ մոտ է զրոյի, ապա անընդմեջ կրճատել մատրիցը մեկով անհրաժեշտ կլինի բաժանել այդ համարը, ուստի առաջատար գործակիցը 1 է։ Սա նշանակում է, որ թվում գոյություն ունեցող ցանկացած սխալ, որը մոտ է զրոյին կմեծացվի։ Գաուսյան վերացումը թվականորեն կայուն է շեղակի գերիշխող կամ դրական-կոնկրետ մատրիցների համար։ Ընդհանուր մատրիցների համար, Գաուսյան վերացումը սովորաբար համարվում է կայուն, երբ, օգտագործում ենք մասնակի առանցք, չնայած կան կայուն մատրիցների օրինակներ, որոնց համար դա անկայուն է.

Ընդհանրացումները

Գաուսի վերացումը կարող է իրականացնել ավելի քան որևէ այլ ոլորտում, ոչ միայն իրական թվերում։

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

Կեղծ կոդը

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

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

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

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

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

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

Ծանոթագրություններ

• Atkinson, Kendall A. (1989), An Introduction to Numerical Analysis (2nd ed.), New York: John Wiley & Sons, ISBN 978-0-471-50023-0.
• Bolch, Gunter; Greiner, Stefan; de Meer, Hermann; Trivedi, Kishor S. (2006), Queueing Networks and Markov Chains: Modeling and Performance Evaluation with Computer Science Applications (2nd ed.), Wiley-Interscience, ISBN 978-0-471-79156-0.
• Calinger, Ronald (1999), A Contextual History of Mathematics, Prentice Hall, ISBN 978-0-02-318285-3.
• Farebrother, R.W. (1988), Linear Least Squares Computations, STATISTICS: Textbooks and Monographs, Marcel Dekker, ISBN 978-0-8247-7661-9.
• Golub, Gene H.; Van Loan, Charles F. (1996), Matrix Computations (3rd ed.), Johns Hopkins, ISBN 978-0-8018-5414-9.
• Grcar, Joseph F. (2011a), «How ordinary elimination became Gaussian elimination», Historia Mathematica, 38 (2): 163–218, arXiv:0907.2397, doi:10.1016/j.hm.2010.06.003
• Grcar, Joseph F. (2011b), «Mathematicians of Gaussian elimination» (PDF), Notices of the American Mathematical Society, 58 (6): 782–792
• Higham, Nicholas (2002), Accuracy and Stability of Numerical Algorithms (2nd ed.), SIAM, ISBN 978-0-89871-521-7.
• Katz, Victor J. (2004), A History of Mathematics, Brief Version, Addison-Wesley, ISBN 978-0-321-16193-2.
• Kaw, Autar; Kalu, Egwu (2010). «Numerical Methods with Applications» (1st ed.)., Chapter 5 deals with Gaussian elimination.
• Lipson, Marc; Lipschutz, Seymour (2001), Schaum's outline of theory and problems of linear algebra, New York: McGraw-Hill, էջեր 69–80, ISBN 978-0-07-136200-9.
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), «Section 2.2», Numerical Recipes: The Art of Scientific Computing (3rd ed.), New York: Cambridge University Press, ISBN 978-0-521-88068-8, Արխիվացված է օրիգինալից 2012 թ․ մարտի 19-ին, Վերցված է 2013 թ․ հունիսի 1-ին

Արտաքին հղումներ

• WebApp descriptively solving systems of linear equations with Gaussian Elimination Արխիվացված 2011-04-25 archive.today
• A program that performs Gaussian elimination similarly to a human working on paper Արխիվացված 2014-02-19 Wayback Machine Exact solutions to systems with rational coefficients.
• Gaussian elimination Արխիվացված 2010-05-24 Wayback Machine www.math-linux.com.
• Gaussian elimination as java applet Արխիվացված 2006-08-12 Wayback Machine at some local site. Only takes natural coefficients.
• Gaussian elimination calculator with Linear Algebra tutorial.
• Gaussian elimination at Holistic Numerical Methods Institute
• LinearEquations.c Արխիվացված 2011-10-22 Wayback Machine Gaussian elimination implemented using C language
• Gauss–Jordan elimination Արխիվացված 2010-03-17 Wayback Machine Step by step solution of 3 equations with 3 unknowns using the All-Integer Echelon Method
• Gauss-Jordan Elimination calculator for n by m matrices, giving intermediate steps
• WildLinAlg13: Solving a system of linear equations ՅուԹյուբում provides a very clear, elementary presentation of the method of row reduction.