Mètodes Numèrics per a Sistemes Lineals: Directes i Iteratius

Mètodes Numèrics per a la Resolució de Sistemes Lineals

Mètode de Cramer

La solució del sistema $Ax=b$, mitjançant la regla de Cramer, es defineix com:

$$x_i = \frac{|A_i|}{|A|}, \quad 1 \le i \le n$$

On $|A|$ és el determinant de la matriu $A$, i $|A_i|$ és el determinant de la matriu obtinguda substituint la columna $i$ de $A$ pel vector $b$.

Si la matriu és d'ordre $n$, calen $n+1$ determinants d'ordre $n$ per a calcular el vector solució $x$. El nombre d'operacions és, com a mínim, de l'ordre de $n!n$.

Mètodes Directes

Són mètodes que ens proporcionen la solució exacta en un nombre finit d'operacions, si no fos pels errors d'arrodoniment acumulats i les possibles imprecisions en el coneixement inicial de $A$ i $b$.

Es consideren adients per a sistemes lineals no massa grans (típicament entre 100 i 500 equacions) i amb pocs elements nuls.

S'estudien dos mètodes principals i els seus derivats:

• Gauss
• Factorització LU (Descomposició)

Derivats inclouen: Gauss-Jordan i Cholesky.

Criteris per al Millor Algorisme

Per avaluar un algorisme, es consideren principalment dos factors:

• El temps emprat per obtenir la solució (mesurat en nombre d'operacions).
• Els errors d'arrodoniment del mètode de càlcul.

Mètode de Gauss

Les operacions permeses en el mètode de Gauss són:

• Multiplicar una fila per un nombre no nul.
• Substituir una fila per una combinació lineal de les altres.
• Permutar files i columnes del sistema.

Estratègies de Pivotament

El pivotament és crucial per gestionar els errors d'arrodoniment, especialment si el pivot del pas $k$ és zero o proper a zero.

Pivot Trivial (Si el pivot és zero)

Es busca la primera fila per sota de la fila $k$ que tingui un valor no nul, i s'intercanvien les dues files.

Pivot Parcial (Si el pivot és proper a zero)

S'agafa com a pivot l'element de més gran magnitud de tota la columna $k$ (a partir de la diagonal principal).

Pivot Parcial Escalat

S'agafa com a pivot l'element de la columna $k$ (o per sota de la diagonal principal) que té la grandària relativa més gran respecte dels altres elements de la fila.

Usos:

• El mètode de Gauss s'utilitza per a resoldre sistemes, calcular determinants i el rang de matrius.
• El mètode de Gauss-Jordan s'utilitza per a trobar matrius inverses.

Mètodes Compactes (Factoritzacions)

El tret principal d'aquests mètodes és treballar només amb la matriu $A$ i presentar-la com $A=BC$, on $B$ i $C$ són matrius més fàcils d'invertir o manipular.

Descomposicions habituals:

• $A=LU$: $L$ és triangular inferior i $U$ és triangular superior.
• $A=QR$: $Q$ és ortogonal i $R$ és triangular superior.
• $A = U\Sigma V^T$: $U$ i $V$ són ortogonals i $\Sigma$ és diagonal (Descomposició en Valors Singulars - SVD).

Mètodes Iteratius

Són mètodes que generen una successió de vectors convergent a la solució exacta. Aquesta convergència es produeix en un nombre finit d'operacions, si no fos pels errors d'arrodoniment acumulats i les possibles imprecisions en el coneixement inicial de $A$ i $b$.

Exemples: Jacobi i Gauss-Seidel.

Vector Residu i Condicionament

El vector residu $r(x^*)$ mesura com de bé una solució aproximada $x^*$ satisfà el sistema:

$$r(x^*) = b - Ax^*$$

El nombre de condició ($ ext{Cond}$) mesura el mal condicionament del sistema, mentre que $ ext{Rcond}$ (recíproc del nombre de condició) mesura el bon condicionament.

Conclusions

Els mètodes directes són adients per a matrius de mida no excessivament gran. Cal aplicar estratègies de pivotament per evitar que l'error d'arrodoniment creixi. Alguns sistemes són molt sensibles a aquests errors: els anomenats sistemes mal condicionats.