Vikipedio:Projekto matematiko/Gaŭsa elimino

El Vikipedio

Ĉi tiu artikolo montras stilajn aŭ/kaj gramatikajn aŭ/kaj strukturajn problemojn kaj bezonas poluradon por konformi al pli bona nivelo de kvalito. Post plibonigo movu la artikolon al
Gaŭsa elimino
(eble la nomo mem bezonas korekton) Se la ligo estas ruĝa, vi povas movi la artikolon. Se la ligo estas blua, la alia artikolo pri la temo jam ekzistas kaj tiun kaj ĉi tiun artikolon necasas kunigi.

En matematiko, Gaŭsa elimino aŭ Gaŭso–(Jordanio, Jordano, Jordan) elimino, nomis post Carl Friedrich Gauss kaj _Wilhelm_ (Jordanio, Jordano, Jordan) (multa estima Gaŭsa elimino kiel la antaŭa duono de la plenumi Gaŭso–(Jordanio, Jordano, Jordan) elimino), estas algoritmo en lineara algebro por (determinanta, difinanta) la solvaĵoj de sistemo de linearaj ekvacioj, por (determinanta, difinanta) la rango de matrico, kaj por kalkulanta la inverso de inversigebla kvadrata matrico. Kiam aplikis al matrico, Gaŭsa elimino produktas kio estas (nomita, vokis) "reduktita (linio, vico) _echelon_ (formo, formi)".

Enhavo

1 Historio
2 Cifereca analitiko
3 Ekzemplo
4 (Linio, Vico) _echelon_ kaj reduktis (linio, vico) _echelon_ (formo, formi)
5 Aliaj aplikoj
- 5.1 Trovanta la inverso de matrico
- 5.2 La ĝenerala algoritmo al komputi (rangoj, rangas) kaj (bazas, bazoj)
6 Ekstera (ligoj, ligas)

[redaktu] Historio

La maniero estas nomita post la matematikisto Carl Friedrich Gauss, sed la plaj frua (surscenigo, prezento) de ĝi povas troviĝi en la grava Ĉinia matematika teksto _Jiuzhang_ _suanshu_ aŭ La naŭ ĉapitroj de la matematika arto, (datis, rendevuita, daktilarbita, daktilujita, daktita) proksimume 150 B.C.E.

[redaktu] Cifereca analitiko

La komputa komplekseco de Gaŭsa elimino estas O(n³); tio estas, la nombro de (operacioj, operacias) postulita estas (proksimume) proporcie kun n³ se la matrica amplekso estas n × n.

Ĉi tiu algoritmo povas esti uzita sur komputilo por sistemoj kun miloj de ekvacioj kaj (nekonatoj, nekonatas). Ĝi estas, tamen, ciferece labila, almenaŭ sur malnormala (ekzemploj, ekzemplas); tio estas, (glitpunkta, glitkoma) eraroj _committed_ ĉie en la kalkulado estas akumulita kaj (majo, povas) rezulto en rezultoj malproksime de la (ĝusta, ĝustigi, korekti) solvaĵo. Por ĉi tiu kaŭzo kaj por kaŭzoj de ĝia _prohibitive_ kosti sur grandaj matricoj, ripetaj manieroj, ĝenerale bazita sur trovanta fiksa punkto de kuntira surĵeto (vidi Banaĥa fiksa punkta teoremo), estas ĝenerale (preferita, pliamita) por pli grandaj sistemoj; tie ankaŭ ekzisti specifaj manieroj por (eĉ, ebena, para) pli grandaj sistemoj kies koeficientoj sekvi regula ŝablono. Vidi sistemo de linearaj ekvacioj. Gaŭsa elimino estas, tamen, bona maniero por sistemoj de ekvacioj super kampo kie (kalkuladoj, kalkuladas, komputoj, komputas) estas akurata, kiel finiaj kampoj.

[redaktu] Ekzemplo

Supozi vi (bezoni, bezono, necesa) al trovi nombroj x, y, kaj z tia (tiu, ke, kiu) jeno tri ekvacioj estas ĉiuj samtempe vera:

2 x + y - z = 8

- 3 x - y + 2 z = - 11

- 2 x + y + 2 z = - 3

Ĉi tiu estas (nomita, vokis) sistemo de linearaj ekvacioj por la (nekonatoj, nekonatas) x, y, kaj z. Ili estas (nomita, vokis) lineara ĉar ĉiu (termo, membro, flanko, termino) estas ĉu konstanto aŭ estas konstanto (tempoj, tempas) sola (variablo, varianta) al la unua povo. La golo estas al (konverti, konverto) ĉi tiu sistemo al ekvivalento unu tiel ke ni povas facile legi for la solvaĵo. La (operacioj, operacias) al (konverti, konverto) (ekvaciaro, sistemo) al alia, dum ankoraŭ konfitanta la solvaĵoj estas kiel sekvas:

multipliki aŭ dividi ekvacio per ne-nula nombro
reŝaltilo du ekvacioj
adicii aŭ subtrahi (ne bezone entjero) multaj de unu ekvacio al alia unu

La strategio estas kiel sekvas: elimini x de ĉiuj sed la unua ekvacio, elimini y de ĉiuj sed la (sekundo, dua) ekvacio, kaj tiam elimini z de ĉiuj sed la tria ekvacio.

En nia ekzemplo, ni elimini x de la (sekundo, dua) ekvacio per adicianta 3/2 (tempoj, tempas) la unua ekvacio al la (sekundo, dua), kaj tiam ni elimini x de la tria ekvacio per adicianta la unua ekvacio al la tria. La rezulto estas:

2 x + y - z = 8

$\begin{matrix} \frac{1}{2} \end{matrix}y + \begin{matrix} \frac{1}{2} \end{matrix}z = 1$ ,

2 y + z = 5

Nun ni elimini y de la unua ekvacio per adicianta −2 (tempoj, tempas) la (sekundo, dua) ekvacio al la unua, kaj tiam ni elimini y de la tria ekvacio per adicianta −4 (tempoj, tempas) la (sekundo, dua) ekvacio al la tria:

2 x - 2 z = 6

$\begin{matrix} \frac{1}{2} \end{matrix}y + \begin{matrix} \frac{1}{2} \end{matrix}z = 1$ ,

- z = 1

Fine, ni elimini z de la unua ekvacio per adicianta −2 (tempoj, tempas) la tria ekvacio al la unua, kaj tiam ni elimini z de la (sekundo, dua) ekvacio per adicianta 0.5 (tempoj, tempas) la tria ekvacio al la (sekundo, dua):

2 x = 4

$\begin{matrix} \frac{1}{2} \end{matrix}y = \begin{matrix} \frac{3}{2} \end{matrix}$ ,

- z = 1

Ni povas nun legi for la solvaĵo per dividanta: x = 2, y = 3 kaj z = −1.

Ĉi tiu algoritmo (laboroj, laboras) ĝenerale, ankaŭ por pli grandaj sistemoj. Iam ĝi estas necesa al reŝaltilo du ekvacioj: ekzemple se y havis ne okazita en la (sekundo, dua) ekvacio post nia unua (ŝtupo, paŝi) pli supre, ni devus havi (vergita, reŝaltita) la (sekundo, dua) kaj tria ekvacio kaj tiam eliminis y de la unua ekvacio. Ĝi estas ebla (tiu, ke, kiu) la algoritmo prenas "_stuck_": ekzemple se y havis ne okazita en la (sekundo, dua) kaj la tria ekvacio post nia unua (ŝtupo, paŝi) pli supre. En ĉi tiu (kesto, okazo), la sistemo ne havi unika solvaĵo.

Kutime, en praktiko, unu ne alpaŝi la realaj sistemoj en (termoj, kondiĉoj, terminoj, termas, terminas) de ekvacioj sed anstataŭe (konstruas, faras) uzi de la koeficienta matrico (kiu estas ankaŭ taŭgi por komputilo (regoj, regas)), (do, tiel) farante ĉi tiu, nia originala sistemo devus tiam aspekti

$\begin{pmatrix} 2 & 1 & -1 & 8 \\ -3 & -1 & 2 & -11 \\ -2 & 1 & 2 & -3 \end{pmatrix}$

kaj en la fino ni estas (maldekstre, restita) kun

$\begin{pmatrix} 2 & 0 & 0 & 4 \\ 0 & 1/2 & 0 & 3/2 \\ 0 & 0 & -1 & 1 \end{pmatrix}$

aŭ, post dividanta la (linioj, vicoj, linias, vicas) per 2, 1/2 kaj −1, respektive:

$\begin{pmatrix} 1 & 0 & 0 & 2 \\ 0 & 1 & 0 & 3 \\ 0 & 0 & 1 & -1 \end{pmatrix}$

En ĉi tiu (kesto, okazo) ni apliki matrico (operacioj, operacias) ekvivalento al la ekvacio (operacioj, operacias), nome:

Multipliki aŭ dividi (linio, vico) per ne-nula valoro.
Reŝaltilo du (linioj, vicoj, linias, vicas).
Adicii aŭ subtrahi (ne bezone entjero) multaj de unu (linio, vico) al alia (linio, vico).

[redaktu] (Linio, Vico) _echelon_ kaj reduktis (linio, vico) _echelon_ (formo, formi)

Du specialaj ordigoj de matrico estas (nomita, vokis) (linio, vico) _echelon_ (formo, formi) kaj reduktis (linio, vico) _echelon_ (formo, formi). La (difinoj, difinas) de ĉi tiuj (termoj, kondiĉoj, terminoj, termas, terminas) dependas sur la unua ne-nulo (termo, membro, flanko, termino) en ĉiu (linio, vico), (nomita, vokis) la (vica, linia) kondukante koeficiento. Por matrico al furori (linio, vico) _echelon_ (formo, formi) (_REF_), ĉiu kondukante koeficiento devas egala 1. Plue la (linioj, vicoj, linias, vicas) devas esti aranĝita kiel sekvas. Kiel unu movas de la supro al la fundo de la matrico, la kondukante koeficientoj movi de la (maldekstre, restis) dekstren kaj fine (linioj, vicoj, linias, vicas) sen (ĉiu, iu) kondukante koeficiento aperi lasta. La fina matrico en la ekzemplo pli supre estas en (linio, vico) _echelon_ (formo, formi), kiel estas ĉi tiu matrico:

$\begin{pmatrix} 0 & 1 & 4 & 0 & -3 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 \\ \end{pmatrix}$

Matrico en _REF_ estas plui dirita al furori reduktita (linio, vico) _echelon_ (formo, formi) (_RREF_) se ĉiu kondukante koeficiento estas la nur ne-nulo (termo, koeficiento, elemento) en ĝia kolumno. La pli supre matrico estas ne en _RREF_ pro la −3 (termo, koeficiento, elemento). Se (tiu, ke, kiu) (termo, koeficiento, elemento) estis 0, la matrico devus furori _RREF_.

Gaŭsaj eliminaj kvantoj al nanta la matrico (operacioj, operacias) al ricevi matrico en _RREF_. Ĉiuj matricoj havi unika ekvivalenta matrico en _RREF_. Kiam solvanta lineara sistemo, iam estas ne solvaĵoj kaj iam estas multaj solvaĵoj. Kiu ajn estas la (kesto, okazo), konvertanta la fina matrica dorso enen ekvacioj (senvualigas, rivelas) la solvaĵoj (se (ĉiu, iu)) de la sistemo. Ekzemple, se la pli supre matrico prezentas sistemo en kvar (variabloj, variablas), la tria (linio, vico) korespondas al la ekvacio 0 = 1, (do, tiel) la matrico prezentas sistemo sen solvaĵoj.

(Ekvaciaro, Sistemo) estas nekonsekvenca (kio estas, ĝi havas ne solvaĵoj) se la _RREF_ de la pligrandigita matrico havas (linio, vico) kiu havas ĉiuj nuloj krom la lasta ero kiu estas ne-nulo (kio estas 0 0 0 ... 0 | a, kie a estas ne-nulo.)

Jena matrico en _RREF_ prezentas sistemo kun malfinie multaj solvaĵoj:

$\begin{pmatrix} 1 & 2/3 & 0 & 11 \\ 0 & 0 & 1 & 7 \\ \end{pmatrix}$

En ekvacio (formo, formi), ni havi x + (2/3)y = 11 kaj z = 7. Ĉiu valoro de y rendimenta malsama valoro de x.

Sistemo de linearaj ekvacioj estos havi malfinie multaj solvaĵoj se la matrico en _RREF_ (formo, formi) havas pli nekonato (variabloj, variablas) ol la tuteca nombro de (linioj, vicoj, linias, vicas) en _RREF_ kie ĉiu (linio, vico) havas almenaŭ ne-nulo (termo, koeficiento, elemento).

[redaktu] Aliaj aplikoj

[redaktu] Trovanta la inverso de matrico

Supozi A estas kvadrato n × n matrico kaj vi (bezoni, bezono, necesa) al kalkuli ĝia inverso. La n × n identa matrico estas pligrandigita dekstren de A, kiu produktas n × 2n matrico. Tiam vi (aperi, plenumi) la Gaŭsa elimina algoritmo sur (tiu, ke, kiu) matrico. Kiam la algoritmo _finishes_, la identa matrico estos aperi maldekstre; la inverso de A povas tiam troviĝi dekstren de la identa matrico.

Se la algoritmo prenas "_stuck_" kiel eksplikis pli supre, tiam A estas ne inversigebla.

En praktiko, inversiganta matrico estas malofte postulita. La plejparto de la tempo, unu estas (reale, reele) post la solvaĵo de aparta sistemo de linearaj ekvacioj.

[redaktu] La ĝenerala algoritmo al komputi (rangoj, rangas) kaj (bazas, bazoj)

La Gaŭsa elimina algoritmo povas esti aplikita al (ĉiu, iu) m × n matrico A. Se ni preni "_stuck_" en donita kolumno, ni movi al la venonta kolumno. En tiamaniere, ekzemple, (ĉiu, iu) 6 per 9 matrico povas esti konvertita al matrico (tiu, ke, kiu) havas reduktita (linio, vico) _echelon_ (formo, formi) ŝati

$\begin{pmatrix} 1 & * & 0 & 0 & * & * & 0 & * & 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 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{pmatrix}$

(la *'s estas ajnaj elementoj). Ĉi tiu _echelon_ matrico T enhavas riĉaĵo de informo pri A: la rango de A estas 5 ekde estas 5 ne-nulo (linioj, vicoj, linias, vicas) en T; la vektora spaco (naskis, generita) per la kolumnoj de A havas kiel bazo la unua, tria, kvara, sepa kaj (naŭto, naŭno) kolumno de A (la kolumnoj de la aĵoj en T), kaj la *'s diri vi kiel la aliaj kolumnoj de A povas esti skribita kiel linearaj kombinaĵoj de la bazaj kolumnoj.

La Gaŭsa elimino povas esti (aperita, plenumita) super (ĉiu, iu) kampo. La tri rudimenta (operacioj, operacias) uzita en la Gaŭsa elimino (multiplikante (linioj, vicoj, linias, vicas), (verganta, reŝaltanta) (linioj, vicoj, linias, vicas), kaj adicianta (obloj, oblas) de (linioj, vicoj, linias, vicas) al alia (linioj, vicoj, linias, vicas)) sumiĝi je multiplikante la originala matrico A kun inversigebla m × m matricoj de la (maldekstre, restis). En ĝenerala, ni povas diri:

Al ĉiu m × n matrico A super la kampo K tie ekzistas unike difinita inversigebla m × m matrico S kaj unike difinita reduktis (linio, vico)-_echelon_ matrico T tia (tiu, ke, kiu) A = St.

S estas la (produkto, produto) de la matricoj (korespondanta, respektiva) al la (linio, vico) (operacioj, operacias) (aperita, plenumita).

La formala algoritmo al komputi T de A sekvas. Ni skribi A[mi,j] por la (termo, koeficiento, elemento) en (linio, vico) mi, kolumno j en matrico A. La transformo estas (aperita, plenumita) "en loko", signifo (tiu, ke, kiu) la originala matrico A estas perdita kaj sukcese (anstataŭigita, anstataŭigis) per T. <antaŭ> mi=1 j=1 dum (mi ≤ m kaj j ≤ n) fari

# Trovi pivoti en kolumno j, startanta en (linio, vico) mi:
(maks, maksimuma)__val_ = A[mi,j]
(maks, maksimuma)__ind_ = mi
por k=mi+1 al m fari
_val_ = A[k,j]
se _abs_(_val_) > _abs_((maks, maksimuma)__val_) tiam
(maks, maksimuma)__val_ = _val_
(maks, maksimuma)__ind_ = k
fino_se
fino_por
se (maks, maksimuma)__val_ ≠ 0 tiam
reŝaltilo (linioj, vicoj, linias, vicas) mi kaj (maks, maksimuma)__ind_
dividi (linio, vico) mi per (maks, maksimuma)__val_
por u = 1 al m fari
se u ≠ mi tiam
subtrahi A[u,j] * (linio, vico) mi de (linio, vico) u
fino_se
fino_por
mi = mi + 1
fino_se
j = j + 1

fino_dum </antaŭ>

Ĉi tiu algoritmo diferencas malmulte de la unu diskutita pli frua, ĉar antaŭ eliminanta (variablo, varianta), ĝi unua interŝanĝas (linioj, vicoj, linias, vicas) al movi la (termo, koeficiento, elemento) kun la plej granda absoluta valoro al la "pivoti pozicio". Tia pivotanta proceduro plibonigas la cifereca stabileco de la algoritmo; iu (rikordaj kazoj, variantoj, variantas) estas ankaŭ en uzi.

(Tononomo, Noto, Noti) (tiu, ke, kiu) se la kampo estas la (reala, reela) aŭ kompleksaj nombroj kaj flosanta punkta aritmetiko estas en uzi, la komparo <tajpeska tiparo TTF>(maks, maksimuma)__val_ ≠ 0</tajpeska tiparo TTF> devus esti (anstataŭigita, anstataŭigis) per <tajpeska tiparo TTF>_abs_((maks, maksimuma)__val_) > ε</tajpeska tiparo TTF> por iu malgranda, maŝino-dependa konstanto <tajpeska tiparo TTF>ε</tajpeska tiparo TTF>, ekde ĝi estas malofte (ĝusta, ĝustigi, korekti) al kompari flosantaj punktaj nombroj al nulo.

[redaktu] Ekstera (ligoj, ligas)

Gaŭsa elimino kiel ĝava apleto je iu loka situo. Nur prenas naturaj koeficientoj.

Elŝutita el "http://eo.wikipedia.org../../../p/r/o/Vikipedio%7EProjekto_matematiko_Ga%C5%ADsa_elimino_543e.html"

Kategorioj: Artikoloj por polurado kaj movo | Cifereca lineara algebro