Exercicis d'àlgebra lineal numèrica

Els valors singulars. Per a una matriu diagonal amb entrades positives, els valors singulars són exactament aquestes entrades: $5$ i $2$.

El número de condició.

$\kappa_2(A) = \frac{\sigma_{\max}}{\sigma_{\min}} = \frac{5}{2} = 2.5$

Com es llegeix. Aquest número diu quant es poden amplificar els errors relatius de les dades en passar a la solució. Amb $2.5$ el problema està ben condicionat i amb prou feines es perden xifres.

El que no es pot fer. Cap algorisme no millora aquest número: és una propietat del problema. Si és gran, la informació senzillament no hi és, i el que cal és replantejar el model o regularitzar.

El cost de cada fase. Factoritzar costa de l'ordre de $n^{3}$ operacions. que per a $5$ són uns $125. Però un cop feta, resoldre amb un terme independent nou només costa dues substitucions triangulars, de l'ordre de

$n^{2} = 25$

La conseqüència pràctica. Si has de resoldre molts sistemes amb la mateixa matriu i termes independents diferents, factoritza un sol cop i reutilitza. La diferència és d'un factor $5$ per sistema.

I el que no s'ha de fer mai: calcular la matriu inversa i multiplicar. És unes tres vegades més car que factoritzar, és numèricament pitjor i no aporta res que la factorització no doni.

Pas 1 — la primera columna. De $L_{11}^{2} = 1$ surt $L_{11} = \sqrt{1} = 1$, i de $L_{21}L_{11} = 0$ surt $L_{21} = 0$.

Pas 2 — l'entrada diagonal. La condició sobre l'element $(2,2)$ és $L_{21}^{2} + L_{22}^{2} = 5$, o sigui

$L_{22} = \sqrt{5 - L_{21}^{2}} \approx 2.2361$

El test de definició positiva. Si la matriu no fos definida positiva, en aquest punt hauries d'arrelar un número negatiu i l'algorisme fallaria. Aquesta és, de fet, la manera estàndard de comprovar si una matriu simètrica és definida positiva: no es calculen els autovalors, s'intenta Cholesky i es mira si acaba.

El cost. Cholesky fa aproximadament la meitat del treball de LU i no necessita pivotatge, perquè l'estructura ja garanteix l'estabilitat.

La situació: Un sistema quadrat general amb matriu invertible.

La resposta és LU amb pivotatge, perquè és el mètode de propòsit general, i el pivotatge el fa estable a la pràctica.

El mapa complet.

• LU amb pivotatge: sistemes quadrats generals. Cost d'ordre $n^{3}$.
• Cholesky: simètriques definides positives. La meitat del treball i sense pivotatge.
• QR: mínims quadrats de rang complet, i ortonormalització estable.
• SVD: rang, condicionament, aproximació de rang baix i regularització. La més cara i la més informativa.

Un error freqüent: resoldre mínims quadrats amb les equacions normals. És correcte en aritmètica exacta, però eleva el condicionament al quadrat i pot perdre la meitat de les xifres per res.

Els valors singulars. Per a una matriu diagonal amb entrades positives, els valors singulars són exactament aquestes entrades: $100$ i $1$.

El número de condició.

$\kappa_2(A) = \frac{\sigma_{\max}}{\sigma_{\min}} = \frac{100}{1} = 100$

Com es llegeix. Aquest número diu quant es poden amplificar els errors relatius de les dades en passar a la solució. Amb $100$ es poden perdre unes 2 xifres significatives.

El que no es pot fer. Cap algorisme no millora aquest número: és una propietat del problema. Si és gran, la informació senzillament no hi és, i el que cal és replantejar el model o regularitzar.

El cost de cada fase. Factoritzar costa de l'ordre de $n^{3}$ operacions. que per a $8$ són uns $512. Però un cop feta, resoldre amb un terme independent nou només costa dues substitucions triangulars, de l'ordre de

$n^{2} = 64$

La conseqüència pràctica. Si has de resoldre molts sistemes amb la mateixa matriu i termes independents diferents, factoritza un sol cop i reutilitza. La diferència és d'un factor $8$ per sistema.

I el que no s'ha de fer mai: calcular la matriu inversa i multiplicar. És unes tres vegades més car que factoritzar, és numèricament pitjor i no aporta res que la factorització no doni.

Pas 1 — la primera columna. De $L_{11}^{2} = 1$ surt $L_{11} = \sqrt{1} = 1$, i de $L_{21}L_{11} = 0$ surt $L_{21} = 0$.

Pas 2 — l'entrada diagonal. La condició sobre l'element $(2,2)$ és $L_{21}^{2} + L_{22}^{2} = 10$, o sigui

$L_{22} = \sqrt{10 - L_{21}^{2}} \approx 3.1623$

El test de definició positiva. Si la matriu no fos definida positiva, en aquest punt hauries d'arrelar un número negatiu i l'algorisme fallaria. Aquesta és, de fet, la manera estàndard de comprovar si una matriu simètrica és definida positiva: no es calculen els autovalors, s'intenta Cholesky i es mira si acaba.

El cost. Cholesky fa aproximadament la meitat del treball de LU i no necessita pivotatge, perquè l'estructura ja garanteix l'estabilitat.

La situació: Un sistema amb matriu simètrica i definida positiva.

La resposta és Cholesky, perquè aprofita l'estructura i fa la meitat del treball, sense necessitat de pivotatge.

El mapa complet.

• LU amb pivotatge: sistemes quadrats generals. Cost d'ordre $n^{3}$.
• Cholesky: simètriques definides positives. La meitat del treball i sense pivotatge.
• QR: mínims quadrats de rang complet, i ortonormalització estable.
• SVD: rang, condicionament, aproximació de rang baix i regularització. La més cara i la més informativa.

Un error freqüent: resoldre mínims quadrats amb les equacions normals. És correcte en aritmètica exacta, però eleva el condicionament al quadrat i pot perdre la meitat de les xifres per res.

Els valors singulars. Per a una matriu diagonal amb entrades positives, els valors singulars són exactament aquestes entrades: $12$ i $3$.

El número de condició.

$\kappa_2(A) = \frac{\sigma_{\max}}{\sigma_{\min}} = \frac{12}{3} = 4$

Com es llegeix. Aquest número diu quant es poden amplificar els errors relatius de les dades en passar a la solució. Amb $4$ el problema està ben condicionat i amb prou feines es perden xifres.

El que no es pot fer. Cap algorisme no millora aquest número: és una propietat del problema. Si és gran, la informació senzillament no hi és, i el que cal és replantejar el model o regularitzar.

El cost de cada fase. Factoritzar costa de l'ordre de $n^{3}$ operacions. que per a $10$ són uns $1.000. Però un cop feta, resoldre amb un terme independent nou només costa dues substitucions triangulars, de l'ordre de

$n^{2} = 100$

La conseqüència pràctica. Si has de resoldre molts sistemes amb la mateixa matriu i termes independents diferents, factoritza un sol cop i reutilitza. La diferència és d'un factor $10$ per sistema.

I el que no s'ha de fer mai: calcular la matriu inversa i multiplicar. És unes tres vegades més car que factoritzar, és numèricament pitjor i no aporta res que la factorització no doni.