AnnGabrieli

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

Կատարել շարքի նվազեցում մատրիցայով, մեկը կիրառում է տարրական անընդմեջ գործողությունների հաջորդականությունը՝ փոխելու համար մատրիցը մինչև մատրիցի ստորին ձախ ձեռքի անկյունը լցվելի զրոներվ, որքան հնարավոր է. Գոյություն ունեն երեք տեսակի տարրական անընդմեջ գործունեություններ: 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]$

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

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

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

Մեկ այլ տեսակետ, որը պարզվում է շատ օգտակար է ալգորիթմը վերլուծելու համար, որը բուն մատրիցը մատրիցի տարրալուծումով oկրճատում է. Տարրական տող գործողությունները կարող են դիտվել որպես բազմապատկում բնօրինակ մատրիցը ձախ կողմըտարրական մատրիցների կողմից. Այնուհետեւ ալգորիթմի առաջին մասը հաշվում է մի 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 × n մատրիցի A-ն բացառիկ է որպես արդյունքի շրջում m × 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, որոնք համակարգիչնեի բաղկացուցիչ մասերի առանձնահատկություններն են օգտագործում և մատրիցի կառուցվածքով ինքնաբերաբար ընտրում է լավագույն ալգորիթմը.

References

• 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.). [1]. {{cite web}}: External link in |publisher= (օգնություն); Missing or empty |url= (օգնություն), 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

External links

• WebApp descriptively solving systems of linear equations with Gaussian Elimination
• A program that performs Gaussian elimination similarly to a human working on paper Exact solutions to systems with rational coefficients.
• Gaussian elimination www.math-linux.com.
• Gaussian elimination as java applet at some local site. Only takes natural coefficients.
• Gaussian elimination calculator with Linear Algebra tutorial.
• Gaussian elimination at Holistic Numerical Methods Institute
• LinearEquations.c Gaussian elimination implemented using C language
• Gauss–Jordan elimination 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.