Gaŭsa eliminado

En lineara algebro, gaŭsa eliminado estas algoritmo por solvado de sistemo de linearaj ekvacioj, kalkulado de inverso de kvadrata matrico, aŭ trovado de rango de matrico.

Gaŭsa eliminado povas esti plenumata super ĉiu kampo, de ambaŭ reelaj kaj kompleksaj nombroj.

Solvado de sistemo de linearaj ekvacioj

Estu A matrico n×n, estu b kolumna vektoro de amplekso n. Necesas komputi kolumnan vektoron x tian ke Ax=b .

La fontaj datumoj por la algoritmo estas la matrico A kaj la vektoro b.

En la algoritmo rudimentaj liniaj operacioj (multiplikanto de linio je nombro, interŝanĝo de du linioj, adicio de unu linio multiplikita je nombro al la alia linio) estas uzataj por transformigi la matricon A kaj samtempe la vektoron b. Grava propraĵo de ĉiu rudimenta linia operacio estas ke ĝi ne ŝanĝas la solvaĵojn de la sistemoj de ekvacioj. Taŭge elektitaj rudimentaj liniaj operacioj plisimpligas la sistemon de ekvacioj ĝis fina formo Ix=b_f, kie I estas la identa matrico kaj vektoro b_f estas tio kio rezultas de la vektoro b post la rudimentaj liniaj operacioj. Tiam la solvaĵo estas simple x=b_f.

La procezo de gaŭsa eliminado enhavas du partojn. La unua parto, nomata kiel elimino antaŭen, konvertas la matricon A en supro-dekstran triangulan matricon. Aŭ ĝi povas finiĝas pro degenereco de la matrico (rango malpli granda ol amplekso de la matrico), indikante ke la sistemo ne havas solvaĵon por vektoro b de ĝenerala okazo.

La dua parto, nomata kiel rea anstataŭo, konvertas la matricon A plu en identan matricon.

Estu A[i, j] la elemento en linio i, kolumno j de matrico A. Estu b[i] la elemento i de vektoro b. La transformo estas plenumata "en loko", kio signifas ke la originalaj matrico A kaj vektoro b estas perdataj; matrico A estas fine anstataŭata per identa matrico I.

// parto 1 - elimino antaŭen
por i = 1 ... n
    // pivotado
    // trovi pivotan eron maxi en kolumno i, startante de linio i
    maxi = i
    por k = i+1 ... m
        se abs(A[k, i]) > abs(A[maxi, i])
            maxi = k
    // se la pivota ero estas nenula, do uzi la rudimentajn operaciojn, alie fini kun malsukceso
    se A[maxi, i] ≠ 0
        // interŝanĝi liniojn i kaj maxi
        por u = i ... n
            t = A[i, u], A[i, u] = A[maxi, u], A[maxi, u] = t
        t = b[i], b[i] = b[maxi], b[maxi] = t
        // nun A[i, i] estas enhavas la antaŭan valoron de A[maxi, i].
        // dividi ĉiun elementon en linio i per A[i, i]
        v = A[i, i]
        por u = i ... n
            A[i, u] = A[i, u] / v
        b[i] = b[i] / v
        // nun A[i, i] = 1
        // por ĉiu linio k sube de linio i, el linio k linion i multiplikitan per A[k, i]
        por k = i+1 ... m
            v = A[k, i]
            por u = i ... n
                A[k, u] = A[k, u] - A[i, u] * v
            b[k] = b[k] - b[i] * v
            // nun A[k, i] = 0
    alie
        fino // matrcio A estas ne inversigebla
// parto 2 - rea anstataŭo
por i = n ... 2 // i malpligrandiĝas
    por u = 1 ... i-1
        b[u] = b[u] - b[i] * A[u, i]
        A[u, i] = 0 // devus esti A[u, i] = A[u, i] - A[i, i] * A[u, i], kun tio ke nun A[i, i]=1 la rezulto estas 0

Fine, la responda vektoro x estas en la loko b.

Ĉi tiu algoritmo unue interŝanĝas liniojn por movi la elementon kun la plej granda absoluta valoro al la pivota pozicio A[i, i]. Ĉi tia pivotado plibonigas la cifereca stabileco de la algoritmo; iuj variantoj estas ankaŭ en uzi. En iuj okazoj pivotado ne estas nepre bezonata, tiam estas simple supozo ke maxi = i.

Notu, ke ĉi tie eroj de la vektoroj kaj matricoj estas indeksataj per valoroj 1 ... n, kvankam en komputilaj realigoj de algoritmo ofte estas uzata indeksado per valoroj 0 ... n-1.

Ekzemplo

Ĉi tio estas ekzemplo de uzo de gaŭsa eliminado por solvado de sistemo de 3 linearaj ekvacioj. La pivotado ne estas uzata.

Estu necese solvi jenan sistemon de linearaj ekvacioj:

${\displaystyle {\begin{aligned}2x&&+y&&-z&&=&&8\\-3x&&-y&&+2z&&=&&-11\\-2x&&+y&&+2z&&=&&-3\end{aligned}}}$

En matrica formo, la sistemo estas ${\displaystyle A{\begin{bmatrix}x\\y\\z\end{bmatrix}}=\mathbf {b} }$.

La A kaj b skribataj kune por videbleco estas:

${\displaystyle {\begin{bmatrix}A&\mathbf {b} \end{bmatrix}}={\begin{bmatrix}2&1&-1&8\\-3&-1&2&-11\\-2&1&2&-3\end{bmatrix}}}$

Post la unua paŝo (kun i=1) de la unua parto

${\displaystyle {\begin{aligned}x&&+&&{\tfrac {1}{2}}y&&-&&{\tfrac {1}{2}}z&&=&&4\\&&&&{\tfrac {1}{2}}y&&+&&{\tfrac {1}{2}}z&&=&&1\\&&&&2y&&+&&z&&=&&5\end{aligned}}}$

${\displaystyle {\begin{bmatrix}A&\mathbf {b} \end{bmatrix}}={\begin{bmatrix}1&{\frac {1}{2}}&-{\frac {1}{2}}&4\\0&{\frac {1}{2}}&{\frac {1}{2}}&1\\0&2&1&5\end{bmatrix}}}$

Post la dua paŝo (kun i=2) de la unua parto

${\displaystyle {\begin{aligned}x&&+&&{\tfrac {1}{2}}y&&-&&{\tfrac {1}{2}}z&&=&&4\\&&&&y&&+&&z&&=&&2\\&&&&&&-&&z&&=&&1\end{aligned}}}$

${\displaystyle {\begin{bmatrix}A&\mathbf {b} \end{bmatrix}}={\begin{bmatrix}1&{\frac {1}{2}}&-{\frac {1}{2}}&4\\0&1&1&2\\0&0&-1&1\end{bmatrix}}}$

Post la tria paŝo (kun i=3) de la unua parto

${\displaystyle {\begin{aligned}x&&+&&{\tfrac {1}{2}}y&&-&&{\tfrac {1}{2}}z&&=&&4\\&&&&y&&+&&z&&=&&2\\&&&&&&&&z&&=&&-1\end{aligned}}}$

${\displaystyle {\begin{bmatrix}A&\mathbf {b} \end{bmatrix}}={\begin{bmatrix}1&{\frac {1}{2}}&-{\frac {1}{2}}&4\\0&1&1&2\\0&0&1&-1\end{bmatrix}}}$

Ĉi tiu rezulto estas sistemo de linearaj ekvacioj en triangula formo.

La dua parto, rea anstataŭo, estas la solvado por nekonataj variabloj en la rea ordo.

Post la unua paŝo (kun i=3) de la dua parto:

${\displaystyle {\begin{aligned}x&&+&&{\tfrac {1}{2}}y&&&&&&=&&{\tfrac {7}{2}}\\&&&&y&&&&&&=&&3\\&&&&&&&&z&&=&&-1\end{aligned}}}$

${\displaystyle {\begin{bmatrix}A&\mathbf {b} \end{bmatrix}}={\begin{bmatrix}1&{\frac {1}{2}}&0&{\frac {7}{2}}\\0&1&0&3\\0&0&1&-1\end{bmatrix}}}$

Post la dua paŝo (kun i=2) de la dua parto:

${\displaystyle {\begin{aligned}x&&&&&&&&&&=&&2\\&&&&y&&&&&&=&&3\\&&&&&&&&z&&=&&-1\end{aligned}}}$

${\displaystyle {\begin{bmatrix}A&\mathbf {b} \end{bmatrix}}={\begin{bmatrix}1&0&0&2\\0&1&0&3\\0&0&1&-1\end{bmatrix}}}$

Tiel la respondo estas x=2, y=3, z=-1. La sistemo estas solvita.

Komputado de inverso de matrico

Gaŭsa eliminado povas esti uzata ankaŭ por komputado de inverso de matrico

Estu A n×n matrico kies inverson necesas kalkuli. Tiam n×n identa matrico estas algluata de dekstre al A, formante n×2n matricon, la blokan matricon W = [A, I]. Tra apliko de rudimentaj liniaj operacioj per la gaŭsa eliminada algoritmo, la maldekstra bloko de W estas reduktata al la identa matrico I, kaj post ĉi tio inverso de la fonta matrico A⁻¹ aperas en la dekstra bloko.

Por plenumi ĉi tion, eblas en la algoritmo pli supre priskribita ĉie anstataŭi vektoron b per matrico B de amplekso n×n, kaj ĉiujn operaciojn kun eroj de b anstataŭi per operacioj kun linioj de matrico B.

Se la algoritmo malsukcesas konverti la matricon A en triangulan formon do A estas ne inversigebla.

Komputado de rango de matrico

La gaŭsa eliminada algoritmo povas esti aplikata al ĉiu m×n ne nepre kvadrata matrico por komputado de ĝia rango. La algoritmo estas surbaze de propraĵo de ĉiu rudimenta linia operacio ke ĝi ne ŝanĝas la rangon de matrico. Fine la matrico rezultas en simpla formo, por kiu kalkulado de rango estas bagatela. Nur la unua parto, elimino antaŭen, estas necesa.

Estu A matrico m×n. Estu A[i, j] la elemento en linio i, kolumno j de matrico A. La transformo estas plenumata "en loko", kio signifas ke la originala matrico A estas perdata.

i = 1
j = 1
dum (i ≤ m kaj j ≤ n)
    // pivotado
    // trovi pivotan eron maxi en kolumno i, startante de linio i
    maxi := i
    por k = i+1 ... m
        se abs(A[k, j]) > abs(A[maxi, j])
            maxi = k
    // se la pivota ero estas nenula, do uzi la rudimentajn operaciojn, alie sekvi kun la sekva kolumno
    se A[maxi, j] ≠ 0
        // interŝanĝi liniojn i kaj maxi, sed ne ŝanĝi la valoro de i
        por u = j ... n
            t = A[i, u], A[i, u] = A[maxi, u], A[maxi, u] = t
        // nun A[i, j] estas enhavas la antaŭan valoron de A[maxi, j].
        // dividi ĉiun elementon en linio i per A[i, j]
        v = A[i, j]
        por u = j ... n
            A[i, u] = A[i, u] / v
        // nun A[i, j] = 1
        // por ĉiu linio k sube de linio i, el linio k linion i multiplikitan per A[k, j]
        por k = i+1 ... m
            v = A[k, j]
            por u = j ... n
               A[k, u] = A[k, u] - A[i, u] * v
            // nun A[k, j] = 0
        i = i + 1
    j = j + 1

La rango estas fine i-1. Ĝi estas la kvanto de eroj por kiuj estis farite A[i, j] = 1 en la fina formo de la matrico.

Tamen, la komparo A[maxi, j] ≠ 0 estas malbone konvena por kalkulado kun flosanta punkto, anstataue devas esti abs(A[maxi, j]) > t por iu valoro t, kiu devas esti iel elektita. Ĉi tio estas ĉar kvankam en iu okazo A[maxi, j] devus esti nulo, pro la rondigaj eraroj ĝi povas reale esti ne nulo. Pli kompetenta je ĉi tiu aspekto maniero de kalkulado de rango estas surbaze de singulara valora malkomponaĵo, kiu povas pli bone difine je kiu grado matrico estas proksima al havo pli malgrandan rangon.

Ekzemple, per la algorito iu 6×9 matrico estis konvertita al matrico de formo

${\displaystyle {\begin{bmatrix}1&*&*&*&*&*&*&*&*\\0&0&1&*&*&*&*&*&*\\0&0&0&1&*&*&*&*&*\\0&0&0&0&0&0&1&*&*\\0&0&0&0&0&0&0&0&1\\0&0&0&0&0&0&0&0&0\end{bmatrix}}}$

kie * estas ajnaj elementoj. Tiel ĝia rango estas 5, ĉar estas 5 ne-nulaj lineare sendependaj linioj.

Komplikeco

Gaŭsa eliminado por solvi sistemon de n ekvacioj por n nekonataj variabloj postulas n(n+1)/2 dividojn, (2n³+3n²-5n)/6 multiplikojn kaj (2n³+3n²-5n)/6 subtrahojn, ĉi tio entute estas proksimume 2n³/3 operacioj. Tiel ĝi havas tempan komplikecon O(n³).

Cifereca stabileco

Gaŭsa eliminado estas ciferece stabila por diagonale dominaj aŭ pozitive difinitaj matricoj. Por ĝeneralaj matricoj, gaŭsa eliminado estas kutime konsiderata kiel stabila en praktiko se uzi partan pivotadon kiel estas priskribite pli supre, eĉ kvankam estas ekzemploj por kiuj ĝi estas malstabila.

Algoritmo de Grassmann estas ciferece pli stabila varianto de Gaŭsa eliminado. La algoritmo evitas subtrahojn kaj tiel estas malpli senca al eraroj kaŭzataj per subtraho de du proksimume egalaj nombroj.

Ankoraŭ kompetentaj manieroj estas tiuj bazitaj sur singulara valora malkomponaĵo kaj pseŭdoinverso, kaj sur similaj la aliaj matricaj malkomponaĵoj.

Analizo

Alia punkto de vido, kiu estas utila en analizo de la algoritmo, estas ke gaŭsa eliminado komputas matrican malkomponaĵon. Ĉiu el la rudimentaj liniaj operacioj uzataj en gaŭsa eliminado povas esti konsiderata kiel multipliko kun certa inversigebla matrico de maldekstro. Tiel ĉiuj rudimentaj liniaj operacioj de la unua parto de la algoritmo kune estas multipliko de la fonta matrico A kun certa inversigebla matrico Z de maldekstro. Tiel la unua parto de la algoritmo komputas LU-malkomponaĵon, A=LU=Z⁻¹U, kie la U=ZA matrico estas supro-dekstra triangula matrico kiu rezultas de la fonta matrico A post la unua parto de la algoritmo. Se la algoritmo estas uzata en varianto por inversigo de la matrico, en la sama tempo en la loko de matrico B estas la matrico Z; kvankam la matrico L ne rezultas eksplicite.

Tensoroj de pli alta ordo

Gaŭsa eliminado ne estas ĝeneraligata en iu simpla maniero al tensoroj de pli alta ordo (matricoj estas tensoroj de ordo 2); eĉ komputado de rango de tensoro de ordo pli granda ol 2 estas malfacila problemo.

Historio

Gaŭsa eliminado estas nomita post Carl Friedrich Gauss.

La maniero de gaŭsa eliminado aperas en ĉapitro 8, Ortangulaj tabeloj, de grava ĉinia matematika teksto Jiuzhang suanshu aŭ La naŭ ĉapitroj pri la matematika arto. Ĝia uzo estas ilustrita en 18 problemoj, kun 2 ... 5 ekvacioj. La unua referenco al la libro per ĉi tiu titolo estas datita kiel de jaro 179, sed partoj de ĝi estis skribitaj je proksimume jaro 150 a.K.. Ĝi estis komentita de Liu Hui en la 3-a jarcento.

Tamen, la maniero estis inventita en Eŭropo sendepende de Carl Friedrich Gauss kiam li ellaboris la manieron de plej malgrandaj kvadratoj en lia eldonaĵo Teorio de moviĝo de ĉielaj korpoj de jaro 1809.

Vidu ankaŭ

• Sistemo de linearaj ekvacioj
• Matrica inversigo
• Rango de matrico
• Gaŭso-jordana elimino
• Cifereca stabileco
• Matrica malkomponaĵo
• LU-malkomponaĵo
• QR-malkomponaĵo
• Singulara valora malkomponaĵo
• Pseŭdoinverso
• Plej malgrandaj kvadratoj

Eksteraj ligiloj

• Eric W. Weisstein, Gaŭsa eliminado en MathWorld.
• Gaŭsa eliminado en PlanetMath.
• Programo kiu plenumas gaŭsan eliminadon, produktas akuratajn solvaĵojn por sistemoj kun racionalaj koeficientoj, ankaŭ kun kompleksaj racionalaj nombroj Arkivigite je 2014-02-19 per la retarkivo Wayback Machine
• Gaŭsa eliminado Arkivigite je 2010-05-24 per la retarkivo Wayback Machine
• Gaŭsa eliminado kiel java apleto Arkivigite je 2006-08-12 per la retarkivo Wayback Machine
• Gaŭsa eliminado
• Gaŭsa eliminado realigita en lingvo C Arkivigite je 2011-10-22 per la retarkivo Wayback Machine
• Gaŭsa eliminado Arkivigite je 2010-03-17 per la retarkivo Wayback Machine, paŝo-post-paŝa solvado de 3 ekvacioj