Mètode de reducció de Gauss

De Viquipèdia

Nota: L'article necessita algunes millores en el seu format:
(Cal retirar la plantilla un cop millorat l'article) Pot necessitar retocs en; negretes, enllaços, capçaleres, imatges, categories, interwikis, ... L'estil està en 1a persona. La definició és massa tècnica per a no iniciats en el càlcul matricial. Candidat a viquillibres? --Bestiasonica (discussió) 20:59, 29 maig 2008 (CEST)

El mètode de reducció de Gauss és un procediment sistemàtic de substitució matemàtica de $r$ vectors d'una certa base de $E$ pels $r$ vectors de $\mathcal{C}$ independents, per tal d'aconseguir una nova base de $E$ i les expressions dels $k - r$ vectors que queden a $\mathcal{C}$ en aquesta nova base. El fet que tal substitució sigui possible en tots els casos està garantida pel teorema de substitució de Steinitz.

Sigui:

$\mathcal{C} = \left\{u_{1}, u_{2}, \ldots, u_{k}\right\} \,,\quad j>k\,,\ j\neq r$

un conjunt de $k$ vectors no nuls d'un espai vectorial $E$ de dimensió $n$ . Aquest conjunt conté un subconjunt maximal de $r$ ( $0 < r \leq k$ ) vectors independents.

Taula de continguts

1 Les transformacions elementals i la seva justificació
- 1.1 Normalització d'una fila
- 1.2 Reducció de les altres files amb la fila pivot
2 Exemple pràctic
3 Usos principals del mètode
4 Variants: Gauss vs. Gauss-Jordan
5 Implementació en codi Java
6 Implementacions externes
7 Enllaços externs

[edita] Les transformacions elementals i la seva justificació

Sigui

$\mathcal{B} = \left\{e_{1}, \ldots, e_{n}\right\} \,,\quad j>k\,,\ j\neq r$

una base de $E$ i siguin

$\begin{align} u_{1} &= \lambda_{1}^{1} e_{1} + \lambda_{1}^{2} e_{2} + \cdots + \lambda_{1}^{n} e_{n} \\ u_{2} &= \lambda_{2}^{1} e_{1} + \lambda_{2}^{2} e_{2} + \cdots + \lambda_{2}^{n} e_{n} \\ \vdots & \vdots \\ u_{k} &= \lambda_{k}^{1} e_{1} + \lambda_{k}^{2} e_{2} + \cdots + \lambda_{k}^{n} e_{n} \\ \end{align}$

Les expressions dels vectors del conjunt $\mathcal{C}$ en aquesta base. Hom sol disposar les components d'aquests vectors en una matriu de $k$ columnes, en què cada columna conté les components d'un dels vectors:

$\begin{pmatrix} \lambda_{1}^{1} & \lambda_{2}^{1} & \ldots & \lambda_{k}^{1} \\ \lambda_{1}^{2} & \lambda_{2}^{2} & \ldots & \lambda_{k}^{2} \\ \vdots & \vdots & \vdots\,\vdots\,\vdots & \vdots \\ \lambda_{1}^{n} & \lambda_{2}^{n} & \ldots & \lambda_{k}^{n} \end{pmatrix}$

Naturalment, permutar dues columnes d'aquesta matriu és permutar els corresponents vectors del conjunt $\mathcal{C}$ , mentre que permutar-ne dues files correspon a permutar els corresponents vectors de la base $\mathcal{B}$ . A part d'aquestes dues transformacions trivials, el mètode de reducció consisteix en l'aplicació sistemàtica i ordenada d'aquestes altres dues transformacions, dites transformacions elementals:

[edita] Normalització d'una fila

Considerem el vector $u i$ , pel qual la component $\lambda_{i}^{j}$ , que és a la fila $j$ i a la columna $i$ , no és nula. La fila $j$ , que conté totes les components dels vectors corresponents al vector $e j$ de la base, s'anomena la fila pivot després de dividir tots els seus elements per $\lambda_{i}^{j}$ :

$\begin{pmatrix} \lambda_{1}^{1} & \lambda_{2}^{1} & \ldots & \lambda_{i-1}^{1} & \lambda_{i}^{1} & \lambda_{i+1}^{1} & \ldots & \lambda_{k}^{1} \\ \lambda_{1}^{2} & \lambda_{2}^{2} & \ldots & \lambda_{i-1}^{2} & \lambda_{i}^{2} & \lambda_{i+1}^{2} & \ldots & \lambda_{k}^{2} \\ \vdots & \vdots & \vdots\,\vdots\,\vdots & \vdots & \vdots & \vdots & \vdots\,\vdots\,\vdots & \vdots \\ \lambda_{1}^{j-1} & \lambda_{2}^{j-1} & \ldots & \lambda_{i-1}^{j-1} & \lambda_{i}^{j-1} & \lambda_{i+1}^{j-1} & \ldots & \lambda_{k}^{j-1} \\ \frac{\lambda_{1}^{j}}{\lambda_{i}^{j}} & \frac{\lambda_{2}^{j}}{\lambda_{i}^{j}} & \ldots & \frac{\lambda_{i-1}^{j}}{\lambda_{i}^{j}} & \frac{\lambda_{i}^{j}}{\lambda_{i}^{j}} & \frac{\lambda_{i+1}^{j}}{\lambda_{i}^{j}} & \ldots & \frac{\lambda_{k}^{j}}{\lambda_{i}^{j}} \\ \lambda_{1}^{j+1} & \lambda_{2}^{j+1} & \ldots & \lambda_{i-1}^{j+1} & \lambda_{i}^{j+1} & \lambda_{i+1}^{j+1} & \ldots & \lambda_{k}^{j+1} \\ \vdots & \vdots & \vdots\,\vdots\,\vdots & \vdots & \vdots & \vdots & \vdots\,\vdots\,\vdots & \vdots \\ \lambda_{1}^{n} & \lambda_{2}^{n} & \ldots & \lambda_{i-1}^{n} & \lambda_{i}^{n} & \lambda_{i+1}^{n} & \ldots & \lambda_{k}^{n} \\ \end{pmatrix} = \begin{pmatrix} \lambda_{1}^{1} & \lambda_{2}^{1} & \ldots & \lambda_{i-1}^{1} & \lambda_{i}^{1} & \lambda_{i+1}^{1} & \ldots & \lambda_{k}^{1} \\ \lambda_{1}^{2} & \lambda_{2}^{2} & \ldots & \lambda_{i-1}^{2} & \lambda_{i}^{2} & \lambda_{i+1}^{2} & \ldots & \lambda_{k}^{2} \\ \vdots & \vdots & \vdots\,\vdots\,\vdots & \vdots & \vdots & \vdots & \vdots\,\vdots\,\vdots & \vdots \\ \lambda_{1}^{j-1} & \lambda_{2}^{j-1} & \ldots & \lambda_{i-1}^{j-1} & \lambda_{i}^{j-1} & \lambda_{i+1}^{j-1} & \ldots & \lambda_{k}^{j-1} \\ \mu_{1}^{j} & \mu_{2}^{j} & \ldots & \mu_{i-1}^{j} & 1 & \mu_{i+1}^{j} & \ldots & \mu_{k}^{j} \\ \lambda_{1}^{j+1} & \lambda_{2}^{j+1} & \ldots & \lambda_{i-1}^{j+1} & \lambda_{i}^{j+1} & \lambda_{i+1}^{j+1} & \ldots & \lambda_{k}^{j+1} \\ \vdots & \vdots & \vdots\,\vdots\,\vdots & \vdots & \vdots & \vdots & \vdots\,\vdots\,\vdots & \vdots \\ \lambda_{1}^{n} & \lambda_{2}^{n} & \ldots & \lambda_{i-1}^{n} & \lambda_{i}^{n} & \lambda_{i+1}^{n} & \ldots & \lambda_{k}^{n} \\ \end{pmatrix}$

Aleshores, els vectors de $\mathcal{C}$ , és a dir, les columnes de la matriu, queden expressats en la nova base

$\mathcal{B}_{i}^{j} = \left\{e_{1}, \ldots, e_{j-1}, \lambda_{i}^{j} e_{j}, e_{j+1}, \ldots, e_{n}\right\}$

que és la base

$\mathcal{B}_{i}^{j} = \mathcal{B} \backslash \left\{e_{j}\right\} \cup \left\{\lambda_{i}^{j} e_{j}\right\}$

resultat de substituir el vector $e j$ pel vector $\lambda_{i}^{j} e_{j}$ .

[edita] Reducció de les altres files amb la fila pivot

Es tracta ara de substituir cadascuna de les files per la suma de la fila pivot multiplicada per l'oposat de l'element de la fila que s'està substituint que és a la columna on hi ha l' $1$ obtingut en el pas anterior amb la fila que s'està substituint: si la fila pivot era la fila $j$ i volem reduir la fila $s$ ( $s \neq j$ , naturalment!) les operacions a fer sobre aquesta fila $s$ són:

$\lambda_{1}^{s} - \lambda_{i}^{s} \mu_{1}^{j} \,, \quad \lambda_{2}^{s} - \lambda_{i}^{s} \mu_{2}^{j} \,, \quad \ldots \,, \quad \lambda_{k}^{s} - \lambda_{i}^{s} \mu_{k}^{j}$

i, just en la columna $i$ , el resultat és un zero:

$\lambda_{i}^{s} - \lambda_{i}^{s} \mu_{i}^{j} = \lambda_{i}^{s} - \lambda_{i}^{s} \cdot 1 = 0$

perquè, a la fila $i$ , la fila pivot, $\mu_{i}^{j} = \frac{\lambda_{i}^{j}}{\lambda_{i}^{j}} = 1$ .

Després de fer això amb les $n - 1$ files que no són la fila pivot, la matriu queda amb aquest aspecte:

$\begin{pmatrix} \mu_{1}^{1} & \mu_{2}^{1} & \ldots & \mu_{i-1}^{1} & 0 & \mu_{i+1}^{1} & \ldots & \mu_{k}^{1} \\ \mu_{1}^{2} & \mu_{2}^{2} & \ldots & \mu_{i-1}^{2} & 0 & \mu_{i+1}^{2} & \ldots & \mu_{k}^{2} \\ \vdots & \vdots & \vdots\,\vdots\,\vdots & \vdots & \vdots & \vdots & \vdots\,\vdots\,\vdots & \vdots \\ \mu_{1}^{j-1} & \mu_{2}^{j-1} & \ldots & \mu_{i-1}^{j-1} & 0 & \mu_{i+1}^{j-1} & \ldots & \mu_{k}^{j-1} \\ \mu_{1}^{j} & \mu_{2}^{j} & \ldots & \mu_{i-1}^{j} & 1 & \mu_{i+1}^{j} & \ldots & \mu_{k}^{j} \\ \mu_{1}^{j+1} & \mu_{2}^{j+1} & \ldots & \mu_{i-1}^{j+1} & 0 & \mu_{i+1}^{j+1} & \ldots & \mu_{k}^{j+1} \\ \vdots & \vdots & \vdots\,\vdots\,\vdots & \vdots & \vdots & \vdots & \vdots\,\vdots\,\vdots & \vdots \\ \mu_{1}^{n} & \mu_{2}^{n} & \ldots & \mu_{i-1}^{n} & 0 & \mu_{i+1}^{n} & \ldots & \mu_{k}^{n} \\ \end{pmatrix}$

Si s'analitza quin vector hi ha ara a una columna qualsevol: la columna $t$ :

$\begin{align} \mu_{t}^{1} e_1 + & \mu_{t}^{2} e_2 + \cdots + \mu_{t}^{j-1} e_{j-1} + \mu_{t}^{j} u_{i} + \mu_{t}^{j+1} e_{j+1} + \cdots + \mu_{t}^{n} e_{n} = \\ & = \left(\lambda_{t}^{1} - \lambda_{i}^{1} \mu_{t}^{j}\right) e_1 + \left(\lambda_{t}^{2} - \lambda_{i}^{2} \mu_{t}^{j}\right) e_2 + \cdots + \left(\lambda_{t}^{j-1} - \lambda_{i}^{j-1} \mu_{t}^{j}\right) e_{j-1} + \\ & \quad + \mu_{t}^{j} u_{i} + \left(\lambda_{t}^{j+1} - \lambda_{i}^{j+1} \mu_{t}^{j}\right) e_{j+1} + \cdots + \left(\lambda_{t}^{n} - \lambda_{i}^{n} \mu_{t}^{j}\right) e_n = \\ & = \lambda_{t}^{1} e_1 + \lambda_{t}^{2} e_2 + \cdots + \lambda_{t}^{j-1} e_{j-1} + \lambda_{t}^{j+1} e_{j+1} + \cdots + \lambda_{t}^{n} e_n + \\ & \quad + \mu_{t}^{j} u_{i} - \lambda_{i}^{1} \mu_{t}^{j} e_1 - \lambda_{i}^{2} \mu_{t}^{j} e_2 - \cdots - \lambda_{i}^{j-1} \mu_{t}^{j} e_{j-1} - \lambda_{i}^{j+1} \mu_{t}^{j} e_{j+1} - \cdots - \lambda_{i}^{n} \mu_{t}^{j} e_n \\ \end{align}$

però, com que,

$u_{i} = \lambda_{i}^{1} e_{1} + \lambda_{i}^{2} e_{2} + \cdots + \lambda_{i}^{j-1} e_{j-1} + \lambda_{i}^{j} e_{j} + \lambda_{i}^{j+1} e_{j+1} + \cdots + \lambda_{i}^{n} e_{n}$

resulta

$\begin{align} \mu_{t}^{j} u_{i} - \lambda_{i}^{1} \mu_{t}^{j} e_1 - & \lambda_{i}^{2} \mu_{t}^{j} e_2 - \cdots - \lambda_{i}^{j-1} \mu_{t}^{j} e_{j-1} - \lambda_{i}^{j+1} \mu_{t}^{j} e_{j+1} - \cdots - \lambda_{i}^{n} \mu_{t}^{j} e_n = \\ & = \mu_{t}^{j} \lambda_{i}^{j} e_{j} = \frac{\lambda_{t}^{j}}{\lambda_{i}^{j}} \, \lambda_{i}^{j} e_{j} = \lambda_{t}^{j} e_{j} \end{align}$

i, finalment,

$\begin{align} \mu_{t}^{1} e_1 &+ \mu_{t}^{2} e_2 + \cdots + \mu_{t}^{j-1} e_{j-1} + \mu_{t}^{j} u_{i} + \mu_{t}^{j+1} e_{j+1} + \cdots + \mu_{t}^{n} e_{n} = \\ &= \lambda_{t}^{1} e_1 + \lambda_{t}^{2} e_2 + \cdots + \lambda_{t}^{j-1} e_{j-1} + \lambda_{t}^{j} e_{j} + \lambda_{t}^{j+1} e_{j+1} + \cdots + \lambda_{t}^{n} e_n = u_{t} \end{align}$

és a dir, el mateix vector que ja hi havia en aquesta columna, però ara expressat en la base

$\mathcal{BR}_{i}^{j} = \left\{e_{1}, \ldots, e_{j-1}, u_{i}, e_{j+1}, \ldots, e_{n}\right\}$

que és la base

$\mathcal{BR}_{i}^{j} = \mathcal{B} \backslash \left\{e_{j}\right\} \cup \left\{u_{i}\right\}$

resultat de substituir el vector $e j$ pel vector $u i$ .

Així, doncs, escollir una fila, $j$ , normalitzar-la tot dividint-la per l'element (que ha de ser no nul) de la seva columna $i$ per usar-la com a fila pivot i després reduir les altres files té com a resultat que tots els vectors (les columnes) quedin expressats en una nova base, obtinguda de l'antiga per substitució del seu vector $j$ -èssim pel vector representat a la columna $i$ .

[edita] Exemple pràctic

A la pràctica no cal amoinar-se per quins canvis de base s'estan produint. Només cal saber que, després del procés complet, tindrem ben distingits els $r$ vectors linealment independents del conjunt $\mathcal{C}$ i l'expressió dels $k - r$ que queden com a combinació lineal dels $r$ vectors independents. Vegem-ne un exemple:

Considerem els cinc vectors

$u_{1} = \begin{pmatrix} 5 \\ 3 \\ 2 \\ 1 \\ \end{pmatrix} \,,\quad u_{2} = \begin{pmatrix} -1 \\ 4 \\ 1 \\ 3 \\ \end{pmatrix} \,,\quad u_{3} = \begin{pmatrix} 11 \\ 2 \\ 3 \\ -1 \\ \end{pmatrix} \,,\quad u_{4} = \begin{pmatrix} 6 \\ 2 \\ -1 \\ -2 \\ \end{pmatrix} \,,\quad u_{5} = \begin{pmatrix} 3 \\ 8 \\ 6 \\ 7 \\ \end{pmatrix}$

que disposarem en la matriu de quatre files (la dimensió de l'espai al qual pertanyen) i cinc columnes (el nombre de vectors que hi ha):

$\begin{pmatrix} 5 & -1 & 11 & 6 & 3 \\ 3 & 4 & 2 & 2 & 8 \\ 2 & 1 & 3 & -1 & 6 \\ 1 & 3 & -1 & -2 & 7 \\ \end{pmatrix}$

Comencem per la primera columna (pel vector $u 1$ ) i podem escollir per normalitzar i ser fila pivot qualsevol de les files en les que en la primera columna no hi hagi un zero. En el nostre cas, podem escollir-ne qualsevol, pero agafarem la quarta, perquè l'element de la fila 4 i columna 1 ja val 1 i no cal normalitzar.

Com que estem en la primera de les reduccions, posem aquesta fila, la fila pivot, com a primera fila, permutant-la amb la primera:

$\begin{pmatrix} 1 & 3 & -1 & -2 & 7 \\ 3 & 4 & 2 & 2 & 8 \\ 2 & 1 & 3 & -1 & 6 \\ 5 & -1 & 11 & 6 & 3 \\ \end{pmatrix}$

i ara reduim les altres tres files. Per reduir la segona, cal sumar-li la fila pivot multiplicada per $- 3$ , que és l'oposat de l'element d'aquesta segona fila a la columna 1:

$\begin{matrix} + \\ \\ \end{matrix} \; \begin{matrix} 3 &\quad& 4 &\quad& 2 &\quad& 2 &\quad& 8 \\ -3 \cdot 1 &\quad& -3 \cdot 3 &\quad& -3 \cdot (-1) &\quad& -3 \cdot (-2) &\quad& -3 \cdot 7 \\ \hline 0 &\quad& -5 &\quad& 5 &\quad& 8 &\quad& -13 \\ \end{matrix}$

Per reduir la tercera, cal sumar-li la fila pivot multiplicada per $- 2$ , que és l'oposat de l'element d'aquesta tercera fila a la columna 1:

$\begin{matrix} + \\ \\ \end{matrix} \; \begin{matrix} 2 &\quad& 1 &\quad& 3 &\quad& -1 &\quad& 6 \\ -2 \cdot 1 &\quad& -2 \cdot 3 &\quad& -2 \cdot (-1) &\quad& -2 \cdot (-2) &\quad& -2 \cdot 7 \\ \hline 0 &\quad& -5 &\quad& 5 &\quad& 3 &\quad& -8 \\ \end{matrix}$

I, per reduir la quarta, cal sumar-li la fila pivot multiplicada per $- 5$ , que és l'oposat de l'element d'aquesta quarta fila a la columna 1:

$\begin{matrix} + \\ \\ \end{matrix} \; \begin{matrix} 5 &\quad& -1 &\quad& 11 &\quad& 6 &\quad& 3 \\ -5 \cdot 1 &\quad& -5 \cdot 3 &\quad& -5 \cdot (-1) &\quad& -5 \cdot (-2) &\quad& -5 \cdot 7 \\ \hline 0 &\quad& -16 &\quad& 16 &\quad& 16 &\quad& -32 \\ \end{matrix}$

i la matriu, després d'aquesta primera reducció, queda

$\begin{pmatrix} 1 & 3 & -1 & -2 & 7 \\ 0 & -5 & 5 & 8 & -13 \\ 0 & -5 & 5 & 3 & -8 \\ 0 & -16 & 16 & 16 & -32 \\ \end{pmatrix}$

Ara anem per la segona reducció. Prenem la segona columna (la del vector $u 2$ ) i podem escollir per normalitzar i ser fila pivot qualsevol de les tres files que encara no han actuat com a pivot (això n'exclou la primera) en les que en la segona columna no hi hagi un zero. En el nostre cas, podem escollir-ne qualsevol, pero agafarem la quarta, perquè la normalització, que és dividir-la per $- 16$ serà senzilla.

Com que estem en la segona de les reduccions, posem aquesta fila, la fila pivot, ja normalitzada, com a segona fila, permutant-la amb la segona:

$\begin{pmatrix} 1 & 3 & -1 & -2 & 7 \\ 0 & 1 & -1 & -1 & 2 \\ 0 & -5 & 5 & 3 & -8 \\ 0 & -5 & 5 & 8 & -13 \\ \end{pmatrix}$

i ara reduim les altres tres. Per reduir la primera fila, cal sumar-li la fila pivot multiplicada per $- 3$ , que és l'oposat de l'element d'aquesta primera fila a la columna 2:

$\begin{matrix} + \\ \\ \end{matrix} \; \begin{matrix} 1 &\quad& 3 &\quad& -1 &\quad& -2 &\quad& 7 \\ -3 \cdot 0 &\quad& -3 \cdot 1 &\quad& -3 \cdot (-1) &\quad& -3 \cdot (-1) &\quad& -3 \cdot 2 \\ \hline 1 &\quad& 0 &\quad& 2 &\quad& 1 &\quad& 1 \\ \end{matrix}$

Per reduir la tercera, cal sumar-li la fila pivot multiplicada per $5$ , que és l'oposat de l'element d'aquesta tercera fila a la columna 2:

$\begin{matrix} + \\ \\ \end{matrix} \; \begin{matrix} 0 &\quad& -5 &\quad& 5 &\quad& 3 &\quad& -8 \\ 5 \cdot 0 &\quad& 5 \cdot 1 &\quad& 5 \cdot (-1) &\quad& 5 \cdot (-1) &\quad& 5 \cdot 2 \\ \hline 0 &\quad& 0 &\quad& 0 &\quad& -2 &\quad& 2 \\ \end{matrix}$

I, per reduir la quarta, cal sumar-li la fila pivot multiplicada per $5$ , que és l'oposat de l'element d'aquesta quarta fila a la columna 2:

$\begin{matrix} + \\ \\ \end{matrix} \; \begin{matrix} 0 &\quad& -5 &\quad& 5 &\quad& 8 &\quad& -13 \\ 5 \cdot 0 &\quad& 5 \cdot 1 &\quad& 5 \cdot (-1) &\quad& 5 \cdot (-1) &\quad& 5 \cdot 2 \\ \hline 0 &\quad& 0 &\quad& 0 &\quad& 3 &\quad& -3 \\ \end{matrix}$

i, acabada la segona reducció, la matriu queda

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

Comencem la tercera reducció: ens fixem en la tercera columna (la del vector $u 3$ ) i podem escollir per normalitzar i ser fila pivot qualsevol de les dues files que encara no han actuat com a pivot (això n'exclou la primera i la segona) en les que en la tercera columna no hi hagi un zero. Però no podem fer-ho, perquè en aquesta tercera columna, després de la segona fila ja tot són zeros. Aleshores, cal passar a la quarta columna i escollir una fila per a esdevenir el nou pivot. Com que l'element de la quarta columna (la del vector $u 4$ ) i fila tercera no és zero, podem prendre aquesta tercera fila com a pivot. La normalitzem i, com que estem a la tercera reducció i ja està al tercer lloc no cal fer permutacions de files ara. La matriu ha quedat així:

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

i, després de, amb el mateix mètode que les reduccions anteriors, reduir les altres tres files, obtenim

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

Ara ja no hi ha cas per a una quarta reducció, perquè a totes les columnes que queden, després de la tercera fila ja tot són zeros: el procés, doncs, ha acabat.

El que n'hem obtingut és l'expressió dels vectors $u 1$ , $u 2$ , $u 3$ , $u 4$ i $u 5$ en una nova base, i és aquesta:

$u_{1} = \begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \\ \end{pmatrix} \,,\quad u_{2} = \begin{pmatrix} 0 \\ 1 \\ 0 \\ 0 \\ \end{pmatrix} \,,\quad u_{3} = \begin{pmatrix} 2 \\ -1 \\ 0 \\ 0 \\ \end{pmatrix} \,,\quad u_{4} = \begin{pmatrix} 0 \\ 0 \\ 1 \\ 0 \\ \end{pmatrix} \,,\quad u_{5} = \begin{pmatrix} 2 \\ 1 \\ -1 \\ 0 \\ \end{pmatrix}$

on ara és clar que els vectors $u 1$ , $u 2$ i $u 4$ són linealment independents, i que

$u_{3} = 2 u_{1} - u_{2} \,,\quad u_{5} = 2 u_{1} + u_{2} - u_{4}$

que era l'objectiu a aconseguir.

[edita] Usos principals del mètode

A part la determinació de quins vectors d'un conjunt són linealment independents i com s'espressen els altres en funció d'aquests que ja s'ha descrit, el mètode de reducció de Gauss es fa servir per a

Càlcul del rang d'un conjunt de vectors o d'una matriu.

Càlcul de les solucions de sistemes d'equacions lineals.

Càlcul de la matriu inversa, si en té, d'una matriu donada.

Càlcul del determinant d'una matriu.

[edita] Variants: Gauss vs. Gauss-Jordan

Si només cal calcular el rang d'un conjunt de vectors o d'una matriu, aleshores es pot seguir el procés tot ometent la reducció de les files que són per damunt de la fila pivot. El resultat és, aleshores, una matriu triangular superior. Per exemple, la reducció de la matriu

$\begin{pmatrix} 5 & -1 & 11 & 6 & 3 \\ 3 & 4 & 2 & 2 & 8 \\ 2 & 1 & 3 & -1 & 6 \\ 1 & 3 & -1 & -2 & 7 \\ \end{pmatrix}$

de l'exemple feta així donaria com a matriu reduïda

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

en la qual, segueix ben manifesta la independència lineal dels vectors $u 1$ , $u 2$ i $u 4$ , però les relacions

$u_{3} = 2 u_{1} - u_{2} \,,\quad u_{5} = 2 u_{1} + u_{2} - u_{4}$

no són evidents a cop d'ull. El procés, fet així, en els països de parla anglesa, se sol conèixer com a Gauss elimination, mentre que el procediment complet, en aquests ambients, és Gauss-Jordan elimination.

[edita] Implementació en codi Java

La classe següent implementa el mètode de reducció de Gauss per a matrius de nombres reals, quadrades o no. Els comentaris n'il·lustren la funcionalitat.

/**
 * La classe ReduccioDeGauss conté els mètodes
 * necessaris per reduir pel mètode de Gauss
 * qualsevol matriu, quadrada o no, de nombres
 * reals.
 *
 * L'únic mètode accessible és
 * <code>imprimeixLaMatriu</code> que, ajudat dels
 * altres mètodes, fa tot el procés.
 *
 * @author Brill
 * @version 2007/08/28
 */
public final class ReduccioDeGauss {
        
    /**
     * Reducció pel mètode de Gauss
     * qualsevol matriu, quadrada o no, de nombres
     * reals.
     *
     * @param matriu la matriu a reduir. Les submatrius són les files.
     * @param tolerancia el mínim valor més avall del qual es considera igual a zero.
     */
    public static double[][] redueixLaMatriu (double[][] matriu,double tolerancia) {
        // Càlcul del nombre de files i de columnes
        int numFiles=matriu.length;
        int numColumnes=matriu[0].length;
        // Inicialització del comptador de reduccions
        int columnaPivot=0;
            for (int i=0;i<numFiles;i++) {
                    // Ja no queden més columnes?
                    if (!(i+columnaPivot<numColumnes)) {
                         break;
                    }
                    // Cerca del la següent columna per fer la següent reducció
                    while (aLaColumnaTotsSonZero(matriu,i,i+columnaPivot,tolerancia)) {
                        columnaPivot++;
                            // Ja no queden més columnes?
                            if (!(i+columnaPivot<numColumnes)) {
                                break;
                            }
                    }
                    // Encara queden columnes?
                    if (i+columnaPivot<numColumnes) {
                        // Sí. Busca l'entrada a la columna amb el valor més gran
                        // per agafar la fila corresponent com a pivot. Això es fa
                        // per minimitzar l'error d'arrodoniment.
                        int maximValorALaFila=buscaElMaximValorALaColumna(matriu,i,i+columnaPivot);
                            // Si la fila actual no és la que conté aquesta entrada
                            // de valor màxim, permutar-la amb la que sí el conté
                            if (i!=maximValorALaFila) {
                                matriu=permutaFiles(matriu,i,maximValorALaFila);
                            }
                        // Normalització de la fila pivot  
                        matriu=normalitzaElPivot(matriu,i,i+columnaPivot);
                        // Reduccio de les altres files
                        matriu=redueixLesAltres(matriu,i,i+columnaPivot);
                    } else {
                        break;
                    }
            }
        // Arrodoniment de les entrades més petites que la tolerància
        // al valor zero i resultat
        return arrodoneixLaMatriu(matriu,tolerancia);
    }

    /**
     * Pemutació de dues files
     *
     * @param matriu la matriu a la que se le permuten dues files.
     * @param filaU l'índex d'una de les files a permutar
     * @param filaDos l'índex de l'altra fila a permutar
     */
    private static double[][] permutaFiles (double[][] matriu,int filaU,int filaDos) {
        // Càlcul del nombre de columnes
        int numColumnes=matriu[0].length;
        // El dipòsit intermedi
        double[] diposit=new double[numColumnes];
            // Intercanvi columna a columna
            for (int j=0;j<numColumnes;j++) {
                diposit[j]=matriu[filaU][j];
                matriu[filaU][j]=matriu[filaDos][j];
                matriu[filaDos][j]=diposit[j];
            }
        // Resultat
        return matriu;
    }

    /**
     * Cerca d'elements no nuls en una columna a partir d'una fila fins el final
     *
     * @param matriu la matriu on es fa la cerca
     * @param filaInicial la fila on es comença la cerca
     * @param columna la columna on es fa la cerca
     * @param tolerancia el mínim valor més avall del qual es considera igual a zero.
     */
    private static boolean aLaColumnaTotsSonZero (double[][] matriu,int filaInicial,int columna,double tolerancia) {
        // Inicialització
        boolean aAquestaColumnaTotsSonZero=true;
        // Càlcul del nombre de files
        int numFiles=matriu.length;
            // Comprovació que tots els elements són zero
            for (int i=filaInicial;i<numFiles;i++) {
                aAquestaColumnaTotsSonZero=aAquestaColumnaTotsSonZero&&(Math.abs(matriu[i][columna])<tolerancia);
            }
        // Resultat
        return aAquestaColumnaTotsSonZero;  
    }

    /**
     * Cerca de l'element més gran en una columna a partir d'una certa fila fins el final
     *
     * @param matriu la matriu on es fa la cerca
     * @param filaInicial la fila on es comença la cerca
     * @param columna la columna on es fa la cerca
     */
    private static int buscaElMaximValorALaColumna (double[][] matriu,int filaInicial,int columna) {
        // Càlcul del nombre de files
        int numFiles=matriu.length;
        // Valor inicial de comparació
        int valorMaxim=filaInicial;
            // Cerca dins la columna
            for (int i=filaInicial;i<numFiles;i++) {
                // Valor per a comparació
                double _value=Math.abs(matriu[i][columna]);
                    // És més gran que el que ja tenia?
                    if (_value>Math.abs(matriu[valorMaxim][columna])) {
                        // Sí: nou valor per a comparació
                        valorMaxim=i;
                    }
            }
        // Resultat  
        return valorMaxim;
    }

    /**
     * Normalització de la fila pivot.
     *
     * @param matriu la matriu on es fa la normalització
     * @param filaPivot la fila que es normalitza
     * @param columnaPivot la columna de la qual es treu el valor per normalitzar
     */
    private static double[][] normalitzaElPivot (double[][] matriu,int filaPivot,int columnaPivot) {
        // Càlcul del nombre de columnes
        int numColumnes=matriu[0].length;
        // El valor normalitzador
        double normalitzador=matriu[filaPivot][columnaPivot];
        // El valor normalitzat
        matriu[filaPivot][columnaPivot]=1.0;
            // Normalització dels altres valors
            for (int j=columnaPivot+1;j<numColumnes;j++) {
                matriu[filaPivot][j]=matriu[filaPivot][j]/normalitzador;
            }
        // Resultat  
        return matriu;
    }

    /**
     * Reducció de les altres files.
     *
     * @param matriu la matriu on es fa la reducció
     * @param filaPivot la fila pivot que es fa servir
     * @param columnaPivot la columna de la qual, de cada fila, es treuen els valors per reduir-les
     */
    private static double[][] redueixLesAltres (double[][] matriu,int filaPivot,int columnaPivot) {
        // Càlcul del nombre de files i de columnes
        int numFiles=matriu.length;
        int numColumnes=matriu[0].length;
            // Reducció files
            for (int i=0;i<numFiles;i++) {
                    // No és la fila pivot
                    if (i!=filaPivot) {
                        // El valor per fer la reducció
                        double _value=matriu[i][columnaPivot];
                        // El primer valor reduït
                        matriu[i][columnaPivot]=0.0;
                            // Reducció de la fila
                            for (int j=columnaPivot+1;j<numColumnes;j++) {
                                matriu[i][j]=matriu[i][j]-_value*matriu[filaPivot][j];
                            }
                    }
            }
        // Resultat  
        return matriu;
    }

    /**
     * Arrodoniment a zero dels valors massa petits.
     *
     * @param matriu la matriu a arrodonir
     * @param tolerancia el mínim valor més avall del qual es fa igual a zero.
     */
    private static double[][] arrodoneixLaMatriu (double[][] matriu,double tolerancia) {
        // Càlcul del nombre de files i de columnes
        int numFiles=matriu.length;
        int numColumnes=matriu[0].length;
            // Examen de cadascun dels elements de la matriu
            for (int i=0;i<numFiles;i++) {
                    for (int j=0;j<numColumnes;j++) {
                            // Aquest valor és més petit que la tolerància?
                            if (Math.abs(matriu[i][j])<tolerancia) {
                                // Sí: fes-lo igual a zero
                                matriu[i][j]=0.0;
                            }
                    }
           }
        // Resultat  
        return matriu;
    }

}

[edita] Implementacions externes

[edita] Enllaços externs

Categories: Àlgebra | Matrius

Categoria oculta: Viquipèdia:Articles a millorar el format

See also ebooksgratis.com: no banners, no cookies, totally FREE.