Gauss-Jordan kiesés

A matematika , pontosabban lineáris algebra , Gauss-Jordan elimináció , más néven Gauss pivot eljárás elnevezett Carl Friedrich Gauss és Wilhelm Jordan , egy algoritmus meghatározására megoldások egy egyenletrendszer lineáris , hogy meghatározza a rangsorban a mátrix vagy egy invertálható (négyzet) mátrix inverzének kiszámításához . Amikor Gauss-eliminációt alkalmazunk egy mátrixra, megkapjuk annak méretezett redukált alakját .

Történelem

Ezt a módszert a kínai matematikus , mivel legalább a I st  században AD. Erre utal a Jiuzhang suanshu ( A matematikai művészet kilenc fejezete ) című kínai könyv , amelynek a nyolcadik fejezetét képezi, "Fang cheng" (téglalap alakú elrendezés) címmel. A módszert tizennyolc gyakorlat segítségével mutatjuk be. 263- ban írt kommentárjában Liu Hui az apaságot Ts'ang Chang-nak, az ie II .  Századi kínai császár kancellárjának tulajdonítja .

Európában ezt a módszert fedeztek fel, és az adatokat modern formája a XIX th  században . 1810-ben Carl Friedrich Gauss a Pallas aszteroida mozgását tanulmányozó könyvben mutatta be a legkisebb négyzetek módszerét . E könyv 13. cikkében leír egy általános módszert a lineáris egyenletrendszer megoldására, amely a pivot módszer lényegét képezi. 1888-ban Wilhelm Jordan kiadott egy geodéziai könyvet, amely meghatározta ennek a módszernek a használatát, és kissé eltérő jelölést alkalmaz. Ennek a könyvnek köszönhető, hogy ez a módszer elterjedt egész nyugaton. Manapság Gauss-Jordan megszüntetése néven ismert, vagy Gauss pivotjának módszerével .

Algoritmus

Tevékenységek

A Gauss-Jordan algoritmus elemi soros műveletek felhasználásával állítja elő a mátrix redukált skálázott mátrixát . Háromféle elemi műveletet használnak:

• Kétsoros csere ;
• Szorzás egy sor egy nem nulla skaláris ;
• Egy sor többszörösének hozzáadása egy másik sorhoz.

Álkód

Legyen n × m dimenziójú A mátrix  ;

A Gauss-Jordan algoritmus a következő:

Gauss-Jordan r = 0 (r est l'indice de ligne du dernier pivot trouvé) Pour j de 1 jusqu'à m (j décrit tous les indices de colonnes) | Rechercher max(|A[i,j]|, r+1 ≤ i ≤ n). Noter k l'indice de ligne du maximum | (A[k,j] est le pivot) | Si A[k,j]≠0 alors (A[k,j] désigne la valeur de la ligne k et de la colonne j) | | r=r+1 (r désigne l'indice de la future ligne servant de pivot) | | Diviser la ligne k par A[k,j] (On normalise la ligne de pivot de façon que le pivot prenne la valeur 1) | | Si k≠r alors | | | Échanger les lignes k et r (On place la ligne du pivot en position r) | | Fin Si | | Pour i de 1 jusqu'à n (On simplifie les autres lignes) | | | Si i≠r alors | | | | Soustraire à la ligne i la ligne r multipliée par A[i,j] (de façon à annuler A[i,j]) | | | Fin Si | | Fin Pour | Fin Si Fin Pour Fin Gauss-Jordan

Példa.

A mátrixból indulunk ki

NÁL NÉL=(2-10-12-10-12){\ displaystyle \ mathrm {A} = {\ kezdés {pmatrix} 2 & -1 & 0 \\ - 1 & 2 & -1 \\ 0 & -1 & 2 \ end {pmatrix}}}

Ez egy valós mátrix, tehát az együttható modulusa az abszolút értéke.

• Első iteráció, j = 1 (és r = 0):
  • 1.1 lépés: a mátrix első oszlopában keressük az együtthatók abszolút értékeinek maximális értékét. 2-t ér, az (1, 1) helyen található, így k = 1,
  • 1.2.1. lépés: r = 1,
  • 1.2.2 lépés: r = k , nincs csere,
  • lépés 1.2.3: elosztjuk vonal 1 Egy (1, 1) = 2, azaz ,(1-1/20){\ displaystyle {\ begin {pmatrix} 1 & -1 / 2 & 0 \ end {pmatrix}}}
  • 1.2.4. lépés:
    • i = 2 vonal , A (2, 1) = -1; kiszámoljuk ,
      (-12-1)-(-1)×(1-1/20)=(03/2-1){\ displaystyle {\ begin {pmatrix} -1 & 2 & -1 \ end {pmatrix}} - (- 1) \ times {\ begin {pmatrix} 1 & -1 / 2 & 0 \ end {pmatrix}} = {\ begin {pmatrix} 0 & 3/2 & -1 \ end {pmatrix}}}
    • i = 3 sor , A (3, 1) = 0 van, tehát a sor nem módosul,
  • a mátrix ekkor  ;
    NÁL NÉL′=(1-1/2003/2-10-12){\ displaystyle \ mathrm {A} '= {\ begin {pmatrix} 1 & -1 / 2 & 0 \\ 0 & 3/2 & -1 \\ 0 & -1 & 2 \ end {pmatrix}}}
• második iteráció, j = 2 (és r = 1):
  • 2.1. lépés: a második oszlop 2–3. soraiban keressük a maximális értéket abszolút értékben. Ez 3/2, itt található: (2, 2),
  • 2.2.1. lépés: r = 2,
  • 2.2.2 lépés: r = k , nincs csere.
  • lépés 2.2.3: elosztjuk vonal 2 A „(2, 2) = 3/2, azaz ,(01-2/3){\ displaystyle {\ begin {pmatrix} 0 & 1 & -2 / 3 \ end {pmatrix}}}
  • 2.2.4. lépés:
    • i = 1 sor , van A '(1, 2) = -1/2; kiszámoljuk ,
      (1-1/20)-(-1/2)×(01-2/3)=(10-1/3){\ displaystyle {\ begin {pmatrix} 1 & -1 / 2 & 0 \ end {pmatrix}} - (- 1/2) \ times {\ begin {pmatrix} 0 & 1 & -2 / 3 \ end {pmatrix }} = {\ elején {pmatrix} 1 és 0 és -1 / 3 \ vége {pmatrix}}}
    • i = 3 vonal , van A '(3, 2) = -1; kiszámoljuk ,
      (0-12)-(-1)×(01-2/3)=(004/3){\ displaystyle {\ begin {pmatrix} 0 & -1 & 2 \ end {pmatrix}} - (- 1) \ times {\ begin {pmatrix} 0 & 1 & -2 / 3 \ end {pmatrix}} = { \ begin {pmatrix} 0 & 0 & 4/3 \ end {pmatrix}}}
  • a mátrix ekkor  ;
    NÁL NÉL″=(10-1/301-2/3004/3){\ displaystyle \ mathrm {A} '' = {\ begin {pmatrix} 1 & 0 & -1 / 3 \\ 0 & 1 & -2 / 3 \\ 0 & 0 & 4/3 \ end {pmatrix}} }
• harmadik iteráció, j = 3 (és r = 2):
  • 3.1. lépés: A harmadik oszlop, a harmadik sor forgása 4/3. Tehát k = 3
  • 3.2.1 lépés: r = k,
  • 3.2.2 lépés: nincs sor cserére,
  • 3.2.3. lépés: a 3. sort elosztjuk A '' (3, 3) = 4/3-val, ez lesz (001){\ displaystyle {\ begin {pmatrix} 0 & 0 & 1 \ end {pmatrix}}}
  • 3.2.4. lépés:
    • i = 1 vonal , van A '' (1, 3) = -1/3. Az utolsó lépés törli ezt az együtthatót.
    • i = 2 vonal , van A '' (2, 3) = -2/3. Az utolsó lépés törli ezt az együtthatót.
  • a mátrix ekkor méretarányosan redukálódik.
    NÁL NÉL‴=(100010001){\ displaystyle \ mathrm {A} '' '= {\ elején {pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \ end {pmatrix}}}

Numerikus stabilitás

Az algoritmus első szakasza, vagyis a legnagyobb csavarértékű sorcsere az algoritmus numerikus stabilitásának javítására irányul. Ez a lépés megpróbálja minimalizálni a kumulatív kerekítési hibákat, amelyek numerikus instabilitást okoznak. Ez a stratégia általában lehetővé teszi ezen instabilitás orvoslását, még ha ellenpéldákat is tudunk adni.

Algoritmikus összetettség

A Gauss-elimináció aszimptotikus algoritmikus bonyolultsága O ( n 3 ) ( Landau-jelölések ): n × n a mátrix mérete, és az elvégzendő utasítások száma arányos n 3- mal . Ez az algoritmus számítógépen használható olyan rendszerek számára, amelyekben több ezer ismeretlen és egyenlet található . Azonban, Strassen-algoritmus , amely O ( n 2,807 ) jobb a aszimptotikus algoritmikus bonyolultságát.

A Gauss-pivot algoritmikus bonyolultsága O ( n 3 ) marad, ha a mátrix ritka. Vegyünk egy olyan n × n mátrixot, amelynek csak k n bemenete nem nulla, de amelynek bemenetei rendszeresen oszlanak el a sorok és oszlopok között, majd a Gauss-féle pivot algoritmus során a nem nulla értékek átlagos számát egy a vonal k- ről 2k-ra, majd 3k- ról n- re megy . Ezért azt találjuk, hogy az utasítások száma az nn (n-1) / 2 nagyságrendű .

A négyzetmátrix inverzének kiszámítása

Gauss-Jordan elimináció lehet használni, hogy fordítsa a négyzetes mátrix , ha az invertálható . Ehhez létrehozunk egy mátrix n sorból és 2 n oszlopok által határos A mátrix által azonosító mátrix I n , amely létrehoz egy bővített mátrixot (a) jelöljük [A | I] . Ha a bemeneti mátrix megfordítható, akkor a kibővített mátrixra a Gauss-Jordan algoritmust alkalmazzák. A végső mátrix az [I | alakú A −1 ], és a kezdeti mátrix inverzét tartalmazza a jobb szakaszában.  

Példa

Tegyük fel a következő mátrixot:

NÁL NÉL=(2-10-12-10-12){\ displaystyle \ mathrm {A} = \ balra ({\ begin {array} {rrr} 2 & -1 & 0 \\ - 1 & 2 & -1 \\ 0 & -1 & 2 \ end {tömb}} \ jobb)}

Ennek a mátrixnak az inverz megtalálásához létre kell hoznunk a kibővített mátrixot [A | I] az alábbiak szerint:

[NÁL NÉL|én]=(2-10100-12-10100-12001){\ displaystyle [\ mathrm {A} | \ mathrm {I}] = \ balra ({\ begin {array} {rrr | rrr} 2 & -1 & 0 & 1 & 0 & 0 \\ - 1 & 2 & -1 & 0 & 1 & 0 \\ 0 & -1 & 2 & 0 & 0 & 1 \ end {tömb}} \ jobbra}}

A Gauss-Jordan algoritmus alkalmazásával a kibővített mátrixot a következő redukált méretarányban kapjuk meg:

[én|B]=(10034121401012112001141234){\ displaystyle [\ mathrm {I} | \ mathrm {B}] = \ balra ({\ begin {array} {rrr | rrr} 1 & 0 & 0 & {\ frac {3} {4}} & {\ frac {1} {2}} és {\ frac {1} {4}} \\ [3pt] 0 és 1 és 0 és {\ frac {1} {2}} és 1 és {\ frac {1} { 2}} \\ [3pt] 0 & 0 & 1 és {\ frac {1} {4}} és {\ frac {1} {2}} és {\ frac {3} {4}} \ end {tömb }} \ jobb)} Demonstráció

Mint korábban, az első pivot az első sorban van. A 2.2.3 lépésben az első sor lesz

(1-1/201/200){\ displaystyle \ left ({\ begin {array} {rrr | rrr} 1 & -1 / 2 & 0 & 1/2 & 0 & 0 \ end {tömb}} \ jobb)}

A 2.2.4. Lépés a következő lesz:

• i = 2 vonal, A (2, 1) = -1; kiszámoljuk  ;
  (-12-1010)-(-1)×(1-1/201/200)=(03/2-11/210){\ displaystyle ({\ begin {array} {rrr | rrr} -1 & 2 & -1 & 0 & 1 & 0 \ end {tömb}}) - (- 1) \ alkalommal ({\ begin {array} { rrr | rrr} 1 & -1 / 2 & 0 & 1/2 & 0 & 0 \ end {tömb}}) = ({\ elején {tömb} {rrr | rrr} 0 és 3/2 és -1 és 1 / 2 és 1 & 0 \ end {tömb}})}}
• i = 3 sor, van A (3, 1) = 0, a sor nincs módosítva.

Így van

(1-1/201/20003/2-11/2100-12001){\ displaystyle \ left ({\ begin {array} {rrr | rrr} 1 & -1 / 2 & 0 & 1/2 & 0 & 0 \\ 0 & 3/2 & -1 & 1/2 & 1 & 0 \\ 0 & -1 & 2 & 0 & 0 & 1 \ end {tömb}} \ jobbra}}

A második iterációhoz megfertőzzük a 2. és a 3. sort, és az új 2. sort elosztjuk 2-vel, vagyis a 2.2.3. Lépésben:

(1-1/201/2000-1/21001/203/2-11/210){\ displaystyle \ left ({\ begin {array} {rrr | rrr} 1 & -1 / 2 & 0 & 1/2 & 0 & 0 \\ 0 & -1 / 2 & 1 & 0 & 0 & 1 / 2 \\ 0 & 3/2 & -1 & 1/2 & 1 & 0 \ end {tömb}} \ jobbra}}

A 2.2.4 lépésben:

• i = 1 sor, van A (1, 3) = 0, a sor nincs módosítva;
• i = 3 vonal, A (3, 3) = -1; kiszámoljuk  ;
  (03/2-11/210)-(-1)×(0-1/21001/2)=(0101/211/2){\ displaystyle ({\ begin {array} {rrr | rrr} 0 & 3/2 & -1 & 1/2 & 1 & 0 \ end {tömb}}) - (- 1) \ alkalommal ({\ begin { tömb} {rrr | rrr} 0 & - 1/2 & 1 & 0 & 0 & 1/2 \ end {tömb}}) = ({\ elején {tömb} {rrr | rrr} 0 és 1 & 0 és 1 / 2 & 1 & 1/2 \ end {tömb}})}}

Így van

(1-1/201/2000-1/21001/20101/211/2){\ displaystyle \ left ({\ begin {array} {rrr | rrr} 1 & -1 / 2 & 0 & 1/2 & 0 & 0 \\ 0 & -1 / 2 & 1 & 0 & 0 & 1 / 2 \\ 0 & 1 & 0 & 1/2 & 1 & 1/2 \ end {tömb}} \ jobbra}}

A harmadik iterációhoz elosztjuk a 3. sort 1-gyel, a mátrix változatlan a 2.2.3 lépésben.

A 2.2.4 lépésben:

• i = 1 sor, van A (1, 2) = -1/2; kiszámoljuk  ;
  (1-1/201/200)-(-1/2)×(0101/211/2)=(1003/41/21/4){\ displaystyle ({\ begin {tömb} {rrr | rrr} 1 & -1 / 2 & 0 és 1/2 & 0 & 0 \ vége {tömb}}) - (- 1/2) \ alkalommal ({\ kezdete {tömb} {rrr | rrr} 0 és 1 és 0 és 1/2 és 1 és 1/2 \ vége {tömb}}) = ({\ elején {tömb} {rrr | rrr} 1 és 0 és 0 & 3/4 és 1/2 és 1/4 \ vége {tömb}})}
• i = 2 sor, A (2, 2) = -1/2; kiszámoljuk  ;
  (0-1/21001/2)-(-1/2)×(0101/211/2)=(0011/41/23/4){\ displaystyle ({\ begin {array} {rrr | rrr} 0 & -1 / 2 & 1 & 0 & 0 & 1/2 \ end {tömb}}) - (- 1/2) \ alkalommal ({\ kezdete {tömb} {rrr | rrr} 0 és 1 és 0 és 1/2 és 1 és 1/2 \ vége {tömb}}) = ({\ elején {tömb} {rrr | rrr} 0 és 0 és 1 & 1/4 és 1/2 és 3/4 \ vége {tömb}})}

Így van

(1003/41/21/40011/41/23/40101/211/2){\ displaystyle \ left ({\ begin {array} {rrr | rrr} 1 & 0 & 0 & 3/4 & 1/2 & 1/4 \\ 0 & 0 & 1 & 1/4 & 1/2 & 3/4 \\ 0 & 1 & 0 & 1/2 & 1 & 1/2 \ end {tömb}} \ jobbra}}.

A 2. és 3. sor végleges permutációja megadja

(1003/41/21/40101/211/20011/41/23/4){\ displaystyle \ left ({\ begin {array} {rrr | rrr} 1 & 0 & 0 & 3/4 & 1/2 & 1/4 \\ 0 & 1 & 0 & 1/2 & 1 & 1 / 2 \\ 0 & 0 & 1 & 1/4 & 1/2 & 3/4 \ end {tömb}} \ jobbra}}.

A mátrix bal oldali szakasza az identitásmátrix, amely azt bizonyítja, hogy A fordíthatatlan. A jobb oldali 3x3 szakasz, azaz a B mátrix az A inverze.

Általános eset

Végző elemi műveletet O a N sorok egy mátrix összegek megszorozzuk a bal oldalon a mátrixot (átfordítható) G s  : = O ( I n ).

Megjegyezve O 1 , ..., O s az elemi műveletet, amelyek az egyik végez a A , és a G s = O s ( I n ) a kapcsolódó elemi mátrixok, egy így végül, a bal oldali részén, a mátrix

énnem=(Os∘...∘O1)(NÁL NÉL)=Gs...G1NÁL NÉL{\ displaystyle \ mathrm {I} _ {n} = (O_ {s} \ circ \ ldots \ circ O_ {1}) (A) = G_ {s} \ ldots G_ {1} A}

a jobb oldali pedig a mátrixnál

B=(Os∘...∘O1)(énnem)=Gs...G1.{\ displaystyle B = (O_ {s} \ circ \ ldots \ circ O_ {1}) (\ mathrm {I} _ {n}) = G_ {s} \ ldots G_ {1}.}

Így, B jelentése nonsingular és BA = I n , így a B -1 = A és A -1 = B .

Megoldása a lineáris egyenletrendszer

Gauss-Jordan eliminációval megoldható az AX = B egyenletrendszer, ahol A egy r rangú n × m mátrix , B fix vektor és X az ismeretlen vektor. N sorból és m + 1 oszlopból álló táblázatot készítünk úgy, hogy az A mátrixot a B vektorral határoljuk. A mátrixot csökkentett méretarányban redukáljuk.

Ha az (A | B) -hez társított redukált skálázott mátrix pivotjai csak az első m oszlopokban helyezkednek el (ami mindig így van, ha r = n  ), és az oszlop indexük k 1 ,…, k r  , akkor az utolsó oszlop egy adott megoldást nyújt, amelyet úgy kapunk meg, hogy összes nulla tagját vesszük, kivéve azokat, amelyek a k i index vonalán helyezkednek el, és amelyekhez megadjuk az utolsó oszlop i egyenesén elhelyezkedő kifejezés értékét , i változik 1-től r-ig .

A rendszer általános megoldását úgy kapjuk meg, hogy ehhez az adott megoldáshoz hozzáadjuk az A kernel bármely elemét. Ezt úgy kapjuk meg, hogy tetszőleges értékeket adunk a k i-től eltérő sorindexben elhelyezkedő X együtthatóknak , és meghatározzuk a k i index vonalain elhelyezkedő együtthatók , hogy kielégítsék a rendszert (ami a mátrix méretarányos alakja miatt könnyű).

Ha az (A | B) -hez társított redukált skálázott mátrix utolsó pivotja az utolsó oszlopban van, akkor nincs megoldás.

Ha az A mátrix invertálható négyzet (más szóval, a rendszer Cramer), akkor az utolsó oszlopban megkapjuk a rendszer egyedi X megoldását.

Változat: az előző algoritmusban, ha egy skálázott (nem redukált) mátrix megszerzésére szorítkozunk, akkor magasabb háromszög mátrixot kapunk. Csak annyi marad, hogy "visszamegyünk", hogy megtaláljuk az X együtthatóinak értékeit.

1. példa (részletes)

Legyen a lineáris egyenletek rendszere:

{x-y+2z=5.3x+2y+z=10.2x-3y-2z=-10.{\ displaystyle \ left \ {{\ begin {array} {* {7} {c}} x & - & y & + & 2z & = & 5 \\ 3x & + & 2y & + & z & = & 10 \\ 2x & - & 3y & - & 2z & = & - 10 \ \\ end {tömb}} \ jobb.}

Megállapítjuk a megfelelő mátrixot:

(1-125.32110.2-3-2-10.){\ displaystyle \ left ({\ begin {tömb} {ccc | c} 1 & -1 & 2 & 5 \\ &&& \\ 3 & 2 & 1 & 10 \\ &&& \\ 2 & -3 & -2 & -10 \ end {tömb}} \ jobbra}}

Az 1. oszloppal kezdjük. A forgáspont az abszolút érték maximuma 1, 3 és 2, azaz 3 között:

(1-125.(3)2110.2-3-2-10.){\ displaystyle \ left ({\ begin {tömb} {ccc | c} 1 & -1 & 2 & 5 \\ &&& \\ (3) & 2 & 1 & 10 \\ &&& \\ 2 & -3 & - 2 és -10 \ end {tömb}} jobbra}}

Mivel ez a pivot nem nulla, elosztjuk a pivot-tal a vonalat, ahol található (azaz a 2. vonalat):

(1-125.(1)231310.32-3-2-10.){\ displaystyle \ left ({\ begin {array} {ccc | c} 1 & -1 & 2 & 5 \\ &&& \\ (1) & {\ frac {2} {3}} és {\ frac {1 } {3}} és {\ frac {10} {3}} \\ &&& \\ 2 & -3 & -2 & -10 \ end {tömb}} \ jobbra}}

1. és 2. sort cserélünk:

((1)231310.31-125.2-3-2-10.){\ displaystyle \ left ({\ begin {array} {ccc | c} (1) & {\ frac {2} {3}} és {\ frac {1} {3}} és {\ frac {10} { 3}} \\ &&& \\ 1 & -1 & 2 & 5 \\ &&& \\ 2 & -3 & -2 & -10 \ end {tömb}} \ jobbra}}

Most elemezzük a vonalakon kívüli vonalakat. A 2. sorban A (2, 1) = 1. Kiszámoljuk
(1-125.)-(1)×(1231310.3)=(0-5.35.35.3){\ displaystyle {\ begin {pmatrix} 1 & -1 & 2 & 5 \ end {pmatrix}} - (1) \ times {\ begin {pmatrix} 1 & {\ frac {2} {3}} & {\ frac {1} {3}} és {\ frac {10} {3}} \ end {pmatrix}} = {\ begin {pmatrix} 0 & - {\ frac {5} {3}} és {\ frac { 5} {3}} és {\ frac {5} {3}} \ end {pmatrix}}}

A 3. sorban A (3, 1) = 2. Kiszámítjuk
(2-3-2-10.)-(2)×(1231310.3)=(0-13.3-8.3-503){\ displaystyle {\ begin {pmatrix} 2 & -3 & -2 & -10 \ end {pmatrix}} - (2) \ times {\ begin {pmatrix} 1 & {\ frac {2} {3}} & {\ frac {1} {3}} és {\ frac {10} {3}} \ end {pmatrix}} = {\ begin {pmatrix} 0 & - {\ frac {13} {3}} & - { \ frac {8} {3}} & - {\ frac {50} {3}} \ end {pmatrix}}}

Az így kiszámított 2. és 3. sort helyettesítjük:

((1)231310.30-5.35.35.30-13.3-8.3-503){\ displaystyle \ left ({\ begin {array} {ccc | c} (1) & {\ frac {2} {3}} és {\ frac {1} {3}} és {\ frac {10} { 3}} \\ &&& \\ 0 & - {\ frac {5} {3}} és {\ frac {5} {3}} és {\ frac {5} {3}} \\ &&& \\ 0 & - {\ frac {13} {3}} és - {\ frac {8} {3}} és - {\ frac {50} {3}} \ end {tömb}} \ jobbra)}

Mi megy a 2 oszlop pivot a maximális abszolút értéke között és , nevezetesen  : -5.3{\ displaystyle - {\ frac {5} {3}}}-13.3{\ displaystyle - {\ frac {13} {3}}}-13.3{\ displaystyle - {\ frac {13} {3}}}

(1231310.30-5.35.35.30(-13.3)-8.3-503){\ displaystyle \ left ({\ begin {array} {ccc | c} 1 & {\ frac {2} {3}} és {\ frac {1} {3}} és {\ frac {10} {3} } \\ &&& \\ 0 & - {\ frac {5} {3}} és {\ frac {5} {3}} és {\ frac {5} {3}} \\ &&& \\ 0 és \ balra (- {\ frac {13} {3}} \ right) & - {\ frac {8} {3}} & - {\ frac {50} {3}} \ end {array}} \ right)}

Mivel ez a pivot nem nulla, elosztjuk a pivot-tal a vonalat, ahol található (azaz a 3. vonalat):

(1231310.30-5.35.35.30(1)8.13.5013.){\ displaystyle \ left ({\ begin {array} {ccc | c} 1 & {\ frac {2} {3}} és {\ frac {1} {3}} és {\ frac {10} {3} } \\ &&& \\ 0 & - {\ frac {5} {3}} és {\ frac {5} {3}} és {\ frac {5} {3}} \\ &&& \\ 0 & (1 ) és {\ frac {8} {13}} és {\ frac {50} {13}} \ end {tömb}} \ jobb)}

Cseréljük a 2. és 3. sort:

(1231310.30(1)8.13.5013.0-5.35.35.3){\ displaystyle \ left ({\ begin {array} {ccc | c} 1 & {\ frac {2} {3}} és {\ frac {1} {3}} és {\ frac {10} {3} } \\ &&& \\ 0 & (1) & {\ frac {8} {13}} és {\ frac {50} {13}} \\ &&& \\ 0 & - {\ frac {5} {3} } és {\ frac {5} {3}} és {\ frac {5} {3}} \ end {tömb}} \ jobbra)}

Most elemezzük a vonalakon kívüli vonalakat. Az 1. sorban A (1, 2) = van . Kiszámoljuk23{\ displaystyle {\ frac {2} {3}}}
(1231310.3)-(23)×(018.13.5013.)=(10-113.10.13.){\ displaystyle {\ begin {pmatrix} 1 & {\ frac {2} {3}} és {\ frac {1} {3}} és {\ frac {10} {3}} \ end {pmatrix}} - \ left (\ textstyle {\ frac {2} {3}} \ right) \ times {\ begin {pmatrix} 0 & 1 & {\ frac {8} {13}} & {\ frac {50} {13} } \ end {pmatrix}} = {\ begin {pmatrix} 1 & 0 & - {\ frac {1} {13}} és {\ frac {10} {13}} \ end {pmatrix}}}

A 3. sorban A (3, 2) = van . Kiszámoljuk-5.3{\ displaystyle - {\ frac {5} {3}}}
(0-5.35.35.3)-(-5.3)×(018.13.5013.)=(003513.10513.){\ displaystyle {\ begin {pmatrix} 0 & - {\ frac {5} {3}} és {\ frac {5} {3}} és {\ frac {5} {3}} \ end {pmatrix}} - \ left (- \ textstyle {\ frac {5} {3}} \ right) \ times {\ begin {pmatrix} 0 & 1 & {\ frac {8} {13}} & {\ frac {50} { 13}} \ end {pmatrix}} = {\ begin {pmatrix} 0 & 0 & {\ frac {35} {13}} és {\ frac {105} {13}} \ end {pmatrix}}}

Az így kiszámított 1. és 3. sort helyettesítjük:

(10-113.10.13.0(1)8.13.5013.003513.10513.){\ displaystyle \ left ({\ begin {array} {ccc | c} 1 & 0 & - {\ frac {1} {13}} és {\ frac {10} {13}} \\ &&& \\ 0 & (1) & {\ frac {8} {13}} és {\ frac {50} {13}} \\ &&& \\ 0 & 0 & {\ frac {35} {13}} és {\ frac {105 } {13}} \ end {tömb}} \ jobb)}

A 3. oszlopra megyünk. A forgáspont  : 3513.{\ displaystyle {\ frac {35} {13}}}

(10-113.10.13.018.13.5013.00(3513.)10513.){\ displaystyle \ left ({\ begin {array} {ccc | c} 1 & 0 & - {\ frac {1} {13}} és {\ frac {10} {13}} \\ &&& \\ 0 & 1 & {\ frac {8} {13}} és {\ frac {50} {13}} \\ &&& \\ 0 & 0 & \ balra ({\ frac {35} {13}} \ jobbra) és { \ frac {105} {13}} \ end {tömb}} \ jobbra}}

Mivel ez a pivot nem nulla, elosztjuk a pivot-tal a vonalat, ahol található (azaz a 3. vonalat):

(10-113.10.13.018.13.5013.00(1)3){\ displaystyle \ left ({\ begin {array} {ccc | c} 1 & 0 & - {\ frac {1} {13}} és {\ frac {10} {13}} \\ &&& \\ 0 & 1 & {\ frac {8} {13}} és {\ frac {50} {13}} \\ &&& \\ 0 & 0 & (1) és 3 \ end {tömb}} \ jobbra}}

Mivel ez az elfordulás már a 3. vonal, nem szükséges felcserélni a vonalakat.

Most elemezzük a vonalakon kívüli vonalakat. Az 1. sorban A (1, 3) = van . Kiszámoljuk-113.{\ displaystyle - {\ frac {1} {13}}}
(10-113.10.13.)-(-113.)×(0013)=(1001){\ displaystyle {\ begin {pmatrix} 1 & 0 & - {\ frac {1} {13}} & {\ frac {10} {13}} \ end {pmatrix}} - \ left (- \ textstyle {\ frac {1} {13}} \ right) \ times {\ begin {pmatrix} 0 & 0 & 1 & 3 \ end {pmatrix}} = {\ begin {pmatrix} 1 & 0 & 0 & 1 \ end {pmatrix }}}

A 2. sorban A (2, 3) = van . Kiszámoljuk8.13.{\ displaystyle {\ frac {8} {13}}}
(018.13.5013.)-(8.13.)×(0013)=(0102){\ displaystyle {\ begin {pmatrix} 0 & 1 & {\ frac {8} {13}} és {\ frac {50} {13}} \ end {pmatrix}} - \ left (\ textstyle {\ frac { 8} {13}} \ right) \ times {\ begin {pmatrix} 0 & 0 & 1 & 3 \ end {pmatrix}} = {\ begin {pmatrix} 0 & 1 & 0 & 2 \ end {pmatrix}} }

Az így kiszámított 1. és 2. sort helyettesítjük:

(100101020013){\ displaystyle \ left ({\ begin {tömb} {ccc | c} 1 & 0 & 0 & 1 \\ &&& \\ 0 & 1 & 0 & 2 \\ &&& \\ 0 & 0 & 1 & 3 \ end {tömb}} \ jobbra)}

A függőleges sávtól balra lévő összes oszlop feldolgozásra került. Csökkentett méretarányú mátrix jelenlétében vagyunk, az egyik oldalon az identitásmátrix, a másikon a változók értéke. Az egyenletrendszer megoldása tehát:

{x=1y=2z=3{\ displaystyle \ left \ {{\ begin {tömb} {ccc} x & = & 1 \\ y & = & 2 \\ z & = & 3 \\\ end {tömb}} \ jobb.}

2. példa

Legyen a lineáris egyenletek rendszere:

{x1+2x2+2x3-3x4+2x5.=32x1+4x2+x3-5.x5.=-6.4x1+8.x2+5.x3-6.x4-x5.=0-x1-2x2-x3+x4+x5.=1{\ displaystyle \ left \ {{\ begin {array} {* {11} {c}} x_ {1} & + & 2x_ {2} & + & 2x_ {3} & - & 3x_ {4} & + & 2x_ {5} & = & 3 \\ 2x_ {1} & + & 4x_ {2} & + & x_ {3} &&& - - & 5x_ {5} & = & - 6 \\ 4x_ {1} & + & 8x_ {2} & + & 5x_ {3} & - & 6x_ {4} & - & x_ {5} & = & 0 \\ - x_ {1} & - & 2x_ {2} & - & x_ {3} & + & x_ {4} & + & x_ {5} & = & 1 \ end {tömb}} \ jobb.}

A redukált skálázott mátrix társul az . (122-3232410-5.-6.48.5.-6.-10-1-2-1111){\ displaystyle \ left ({\ begin {tömb} {ccccc | c} 1 & 2 & 2 & -3 & 2 & 3 \\ 2 & 4 & 1 & 0 & -5 & -6 \\ 4 & 8 & 5 & ​​-6 & -1 & 0 \\ - 1 & -2 & -1 & 1 & 1 & 1 \ end {tömb}} \ jobbra}}(1201-4-5.001-234000000000000){\ displaystyle \ left ({\ begin {tömb} {ccccc | c} 1 & 2 & 0 & 1 & -4 & -5 & 5 \\ 0 & 0 & 1 & -2 & 3 & 4 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \ end {tömb}} \ jobbra}}

Az elfordulási pontok az 1. és 3. index oszlopaiban helyezkednek el. Ezért egy konkrét megoldás:, amely megfelel a vektornak: x1=-5.,x3=4,x2=x4=x5.=0{\ displaystyle x_ {1} = - 5, x_ {3} = 4, x_ {2} = x_ {4} = x_ {5} = 0}(-5.0400){\ displaystyle \ left ({\ begin {tömb} {ccc} -5 \\ 0 \\ 4 \\ 0 \\ 0 \ vége {tömb}} \ jobb)}

3. példa

Legyen a lineáris egyenletek rendszere:

{x1+2x2+2x3-3x4+2x5.=32x1+4x2+x3-5.x5.=-6.4x1+8.x2+5.x3-6.x4-x5.=0-x1-2x2-x3+x4+x5.=2{\ displaystyle \ left \ {{\ begin {array} {* {11} {c}} x_ {1} & + & 2x_ {2} & + & 2x_ {3} & - & 3x_ {4} & + & 2x_ {5} & = & 3 \\ 2x_ {1} & + & 4x_ {2} & + & x_ {3} &&& - & 5x_ {5} & = & - 6 \\ 4x_ {1} & + & 8x_ {2} & + & 5x_ {3} & - & 6x_ {4} & - & x_ {5} & = & 0 \\ - x_ {1} & - & 2x_ {2} & - & x_ {3} & + & x_ {4} & + & x_ {5} & = & 2 \ end {tömb}} \ jobb.}

A redukált skálázott mátrix társul az . (122-3232410-5.-6.48.5.-6.-10-1-2-1112){\ displaystyle \ left ({\ begin {tömb} {ccccc | c} 1 & 2 & 2 & -3 & 2 & 3 \\ 2 & 4 & 1 & 0 & -5 & -6 \\ 4 & 8 & 5 & ​​-6 & -1 & 0 \\ - 1 & -2 & -1 & 1 & 1 & 2 \ end {tömb}} \ jobbra}}(1201-40001-230000001000000){\ displaystyle \ left ({\ begin {tömb} {ccccc | c} 1 & 2 & 0 & 1 & -4 & 0 \\ 0 & 0 & 1 & -2 & 3 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 \ end {tömb}} \ jobbra}}

Nincs megoldás.

Meghatározó

Ez az algoritmus lehetővé teszi egy mátrix determinánsának kiszámítását is  :

det(NÁL NÉL)=(-1)o.∏j=⁡1nem(NÁL NÉL[k,j]){\ displaystyle \ det (A) = (- 1) ^ {p}. \ prod _ {j \ mathop {=} 1} ^ {n} (A [k, j])}

a p száma sorban permutációk, és a pivot lépésben feljegyzett j az algoritmus. NÁL NÉL[k,j]{\ displaystyle A [k, j]}

Ha az egyik pivot nulla, akkor a mátrix determinánsa nulla, és nem invertálható.

Példa

A mátrixból indulunk ki

NÁL NÉL=(2-100-12-12-1){\ displaystyle \ mathrm {A} = {\ kezdés {pmatrix} 2 & -1 & 0 \\ 0 & -1 & 2 \\ - 1 & 2 & -1 \ end {pmatrix}}}

Ez egy valós mátrix, tehát az együttható modulusa az abszolút értéke.

Az 1. oszlopban keressük a forgást:

((2)-100-12-12-1){\ displaystyle {\ begin {pmatrix} (2) & - 1 & 0 \\ 0 & -1 & 2 \\ - 1 & 2 & -1 \ end {pmatrix}}}

Az 1-es vonalat elosztjuk 2-vel, így 1-et kapunk az átlón:

(1-1/200-12-12-1){\ displaystyle {\ begin {pmatrix} 1 & -1 / 2 & 0 \\ 0 & -1 & 2 \\ - 1 & 2 & -1 \ end {pmatrix}}}

A 2. és a 3. sort az 1. vonallal végzett lineáris kombinációkkal módosítjuk, így az első oszlopban nullákat kapunk (kivéve az átlót):

(1-1/200-1203/2-1){\ displaystyle {\ begin {pmatrix} 1 & -1 / 2 & 0 \\ 0 & -1 & 2 \\ 0 & 3/2 & -1 \ end {pmatrix}}}

A csapot a 2. oszlopban keressük:

(1-1/200-120(3/2)-1){\ displaystyle {\ begin {pmatrix} 1 & -1 / 2 & 0 \\ 0 & -1 & 2 \\ 0 & (3/2) & - 1 \ end {pmatrix}}}

Cseréljük a 2. és 3. sort:

(1-1/200(3/2)-10-12){\ displaystyle {\ begin {pmatrix} 1 & -1 / 2 & 0 \\ 0 & (3/2) & - 1 \\ 0 & -1 & 2 \ end {pmatrix}}}

A 2. sort elosztjuk (3/2) -nel, így 1-t kapunk az átlón:

(1-1/2001-2/30-12){\ displaystyle {\ begin {pmatrix} 1 & -1 / 2 & 0 \\ 0 & 1 & -2 / 3 \\ 0 & -1 & 2 \ end {pmatrix}}}

Az 1. és a 3. sort a 2. vonallal végzett lineáris kombinációkkal módosítjuk, így a második oszlopban nullákat kapunk (kivéve az átlót):

(10-1/301-2/3004/3){\ displaystyle {\ begin {pmatrix} 1 & 0 & -1 / 3 \\ 0 & 1 & -2 / 3 \\ 0 & 0 & 4/3 \ end {pmatrix}}}

A 3. oszlopban keressük az elfordulást:

(10-1/301-2/300(4/3)){\ displaystyle {\ begin {pmatrix} 1 & 0 & -1 / 3 \\ 0 & 1 & -2 / 3 \\ 0 & 0 & (4/3) \ end {pmatrix}}}

A 3. sort elosztjuk (4/3) -kal, így 1-t kapunk az átlón:

(10-1/301-2/3001){\ displaystyle {\ begin {pmatrix} 1 & 0 & -1 / 3 \\ 0 & 1 & -2 / 3 \\ 0 & 0 & 1 \ end {pmatrix}}}

Az 1. és a 2. sort lineáris kombinációkkal módosítjuk a 3. sorral úgy, hogy nullákat kapjunk a harmadik oszlopban (kivéve az átlót), a mátrix ekkor:

(100010001){\ displaystyle {\ begin {pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \ end {pmatrix}}}

amelyet kicsinyítenek.

Ezért érdemes a mátrix meghatározója . (-1)1×2×32×43=-4{\ displaystyle (-1) ^ {1} \ szor 2-szer {\ frac {3} {2}} \ -szer {\ frac {4} {3}} = - 4}

Megjegyzések

1. Gauss 1810 .
2. Jordánia 1888 .
3. Althoen és McLaughlin 1987 .
4. Átdolgozása Cserpák 2014 , p.  30.
5. Lásd például Patrick Lascaux és Raymond Théodor megjegyzéseit: Matric numerikus elemzés a mérnök művészetére , t.  1: Közvetlen módszerek [ a kiadások részletei ], P.  228 .

Hivatkozások

• Steven C. Althoen és Renate McLaughlin , „  Gauss-Jordan Reduction: A Brief History  ”, Amer. Math. Hónap. , vol.  94,1987, P.  130-142.

• Robert A. Beezer , A Puget Sound Egyetem első tanfolyama a lineáris algebrában ,2014( online olvasás ).

• Carl Friedrich Gauss , Disquisitio de elementis ellipticis Palladis ,1810.

• Wilhelm Jordan , Handbuch der Vermessungskunde , vol.  1, Metzler,1888.

• Joseph-Louis Lagrange , torinói keverékek ,1759.

Kapcsolódó cikkek

• Méretezési algoritmus egy euklideszi gyűrűben
• LU bomlás
• QR bomlás
• Fourier-Motzkin elimináció , a módszer általánosítása lineáris egyenlőtlenségek rendszereire
• Koleszkás faktorizálás

Külső hivatkozás

Gaussian pivot módszer a math-linux.com oldalon