Sistemes Lineals, Gauss i Factorització LU — Àlgebra UdG

I 0 flashcards i 5 preguntes més al document.

Text del document

APUNTS ÀLGEBRA Grau en Enginyeria Informàtica Universitat de Girona AprenAI 2026-2027 Apunts complets d'Àlgebra (UdG): eliminació de Gauss, Teorema de Rouché-Frobenius, pivotatge amb escalat, factorització PA=LU i condicionament de sistemes.

APREN.AI Índex Sistemes d'equacions lineals 1 Conceptes bàsics i notació matricial Equacions lineals i sistemes generals Classificació i sistemes homogenis Representació matricial i multiplicitat de solucions Sistemes equivalents i transformacions elementals 2 Resolució per Gauss i Teorema de Rouché-Frobenius Mètode d'eliminació de Gauss Classificació de variables i substitució enrere Teorema de Rouché-Frobenius i discussió de sistemes Mètodes numèrics directes 3 Errors d'arrodoneixement i pivotatge parcial amb escalat El problema de l'aritmètica finita en el mètode de Gauss Pèrdua d'unicitat i solucions espúries Pivotatge parcial clàssic i la seva limitació Pivotatge parcial amb escalat Algorisme pas a pas en una matriu 4x4 4 Factorització LU i PA=LU Fonament de la descomposició LU Factorització PA = LU i resolució de sistemes Factorització amb pivotatge parcial i escalat integrat Exemple complet pas a pas en dimensió 4 Comparació de precisió: amb pivotatge versus sense pivotatge 5 Condicionament de sistemes lineals Sensibilitat davant pertorbacions: concepte de mal condicionament El determinant com a fals indicador de condicionament Interpretació geomètrica: àrea del paral·lelogram El nombre de condició i cotes d'error 6 Formulari Sistemes d'equacions lineals i Teorema de Rouché-Frobenius Mètodes numèrics: Pivotatge parcial amb escalat Factorització LU i PA = LU Condicionament de sistemes lineals Errors típics Sistemes Lineals, Gauss i Factorització LU — Àlgebra UdG 1 Solucions de les preguntes de repàs Aquests apunts poden contenir errors o omissions.

Són un material de suport i no substitueixen el temari oficial ni el professorat: contrasta la informació important. Sistemes Lineals, Gauss i Factorització LU — Àlgebra UdG 2 1 Conceptes bàsics i notació matricial EN ACABAR SABRÀS Distingir una equació lineal d'una no lineal. Formular un sistema d'equacions lineals en la seva representació matricial A·X = B. Classificar un sistema segons el nombre de solucions i interpretar-lo geomètricament. Aplicar transformacions elementals per files mantenint l'equivalència del sistema. PENSA-HI ABANS DE LLEGIR 1 Pot un sistema d'equacions lineals tenir exactament dues solucions diferents?

L'estudi dels sistemes d'equacions lineals constitueix la base de l'àlgebra lineal i del càlcul numèric aplicat a l'enginyeria i a les ciències. Conèixer la seva estructura algebraica, el llenguatge matricial i el comportament del seu conjunt de solucions permet resoldre problemes complexos mitjançant mètodes sistemàtics.

ESQUEMA Estructura del tema de Sistemes Lineals Sistemes d'equacions lineals 1 Conceptes bàsics i notació matricial 2 Resolució per Gauss i Teorema de Rouché-Frobenius Fonaments i Notació Equacions lineals, notació matricial i tipus de sistemes Transformacions elementals Operacions per files per mantenir equivalència Sistemes Homogenis Compatibilitat i solució trivial Mètodes clàssics Resolució per Gauss i Teorema de Rouché-Frobenius Càlcul numèric directe Factorització LU, pivotatge i anàlisi d'errors Sistemes Lineals, Gauss i Factorització LU — Àlgebra UdG 3 Equacions lineals i sistemes generals Una equació lineal amb incògnites és una expressió algebraica de primer grau que té la forma següent: En aquesta igualtat, els valors reben el nom de coeficients, mentre que s'anomena terme independent.

Totes les incògnites apareixen elevades a la potència 1, sense multiplicar-se entre elles ni formar part de funcions no lineals. EXEMPLE L'expressió és una equació lineal amb tres variables. En canvi, no són equacions lineals: (la variable està elevada al quadrat). (hi intervé una funció trigonomètrica i un terme quadràtic). (apareixen incògnites al denominador). Un sistema d'equacions lineals està format per un conjunt de equacions lineals que involucren incògnites comunes: Una solució del sistema és una assignació de valors numèrics que satisfà totes i cadascuna de les equacions alhora. COMPROVA-HO 2 Per què l'equació x·y + z = 1 no és una equació lineal?

Classificació i sistemes homogenis Atesa la quantitat de solucions que admeten, els sistemes lineals es divideixen en tres categories: Sistema incompatible (SI): no admet cap solució. Sistema compatible determinat (SCD): disposa d'exactament una única solució. Sistema compatible indeterminat (SCI): té infinites solucions. Tipus de sistema Nombre de solucions Interpretació geomètrica en el pla (2x2) Incompatible (SI) Cap solució Rectes paral·leles no coincidents (sense tall) Compatible determinat (SCD) Solució única Rectes secants (es tallen en un únic punt) Compatible indeterminat (SCI) Infinites solucions Rectes coincidents (la mateixa recta) n x , x , …

, x 1 2 n a x + 1 1 a x + 2 2 + a x = n n b a , … , a 1 n R b R 3x 2y + z = 4 x + 2 1 = 0 x sinx + y = 2 0 = y+z x 2 m n a x + a x + + a x = b 1,1 1 1,2 2 1,n n 1 a x + a x + + a x = b 2,1 1 2,2 2 2,n n 2 … a x + a x + + a x = b m,1 1 m,2 2 m,n n m x = 1 s , x = 1 2 s , … , x = 2 n s n m Sistemes Lineals, Gauss i Factorització LU — Àlgebra UdG 4 Un cas d'especial rellevància és el sistema homogeni, caracteritzat pel fet que tots els seus termes independents són nuls: . DEFINICIÓ Tot sistema lineal homogeni és sempre compatible, ja que sempre té, com a mínim, la solució trivial nul·la: . En el pla cartesià, cada equació amb dues variables descriu una recta.

Per exemple, el sistema format per i té com a solució única el punt . En canvi, el sistema amb equacions i descriu dues rectes amb la mateixa pendent però diferent ordenada; en ser paral·leles i no tallar-se mai, el sistema és incompatible. COMPROVA-HO 3 Pot un sistema d'equacions lineals homogeni ser incompatible? Representació matricial i multiplicitat de solucions Podem compactar el sistema agrupant els coeficients en una matriu , anomenada matriu del sistema o matriu de coeficients, les incògnites en un vector columna i els termes independents en un vector columna : Així, el sistema s'expressa mitjançant l'equació matricial A X = B.

Quan s'afegeix la columna de termes independents a la dreta de la matriu de coeficients, s'obté la matriu ampliada, denotada com . Una propietat fonamental dels sistemes lineals és que mai no poden tenir un nombre finit de solucions més gran que 1 (com ara exactament dues o tres solucions). Si en tenen més d'una, automàticament en tenen infinites. DEFINICIÓ Siguin i dues solucions diferents del sistema . Aleshores, qualsevol combinació afí de la forma amb és també una solució del sistema.

La demostració d'aquest fet és directa gràcies a la linealitat del producte matricial: Com que el paràmetre pot prendre qualsevol dels infinits valors de la recta real , el conjunt de solucions esdevé immediatament infinit (sistema compatible indeterminat). COMPROVA-HO 4 Si X i X són dues solucions diferents de A·X = B, quant val A·(X - X )? b = 1 b = 2 = b = m 0 x = 1 0, x = 2 0, … , x = n 0 2x y = 3 x y = 1 (x, y) = (2, 1) 2x y = 3 2x y = 1 A Rm×n X Rn×1 B Rm×1 A = , X = a 1,1 a 2,1 a m,1 a 1,2 a 2,2 a m,2 … … …

a 1,n a 2,n a m,n , B = x 1 x 2 x n b 1 b 2 b m (A B) X 1 X 2 A X = B X = X + 1 α(X 2 X ) 1 α R A(X + 1 α(X 2 X )) = 1 AX + 1 α(AX 2 AX ) = 1 B + α(B B) = B + α 0 = B α R Sistemes Lineals, Gauss i Factorització LU — Àlgebra UdG 5 Sistemes equivalents i transformacions elementals Dos sistemes d'equacions lineals s'anomenen equivalents si posseeixen exactament el mateix conjunt de solucions. Per resoldre un sistema, l'objectiu consisteix a transformar-lo en un altre d'equivalent més fàcil de resoldre.

Les operacions que mantenen inalterades les solucions d'un sistema s'anomenen transformacions elementals per files sobre la matriu ampliada : ERROR FREQÜENT No s'han d'aplicar mai combinacions lineals entre columnes de la matriu per resoldre sistemes. Les operacions permeses són exclusivament sobre les files. L'única transformació per columnes admissible és l'intercanvi de columnes de la matriu , però exigeix reordenar de manera equivalent les incògnites corresponents del vector per no alterar el resultat.

L'aplicació successiva d'aquestes operacions elementals constitueix la base del mètode de resolució esglaonada (vegeu «Sistemes d'equacions lineals — Resolució per Gauss i Teorema de Rouché- Frobenius»). IDEES CLAU Una equació lineal només conté sumes de variables de primer grau multiplicades per coeficients reals. Els sistemes lineals es classifiquen en Incompatibles (cap solució), Compatibles Determinats (solució única) o Compatibles Indeterminats (infinites solucions). Tot sistema homogeni ( ) és compatible perquè conté sempre la solució trivial nul·la. Si un sistema lineal té dues solucions diferents, conté automàticament infinites solucions mitjançant la recta .

Les transformacions elementals per files mantenen l'equivalència del sistema sense alterar-ne les solucions. COMPROVA EL QUE HAS APRÈS 5. Per què un sistema d'equacions lineals mai pot tenir exactament 2 solucions? 6. Quina condició ha de complir l'escalar pel qual es multiplica una fila en una transformació elemental? SISTEMES D'EQUACIONS LINEALS (A B) Intercanvi de files: canviar l'ordre de dues equacions o files ( ). 1 f i f j Escalat no nul: multiplicar una fila per una constant no nul·la ( , amb ). 2 λ R f i λf i λ = 0 Suma d'un múltiple d'una altra fila: substituir la fila pel resultat de sumar-li la fila multiplicada per un escalar ( ).

3 i j f i f + i λf j A A X B = 0 X = X + 1 α(X 2 X ) 1 Sistemes Lineals, Gauss i Factorització LU — Àlgebra UdG 6 2 Resolució per Gauss i Teorema de Rouché-Frobenius EN ACABAR SABRÀS Aplicar l'eliminació de Gauss per files sobre la matriu ampliada per esglaonar-la. Classificar un sistema d'equacions lineals mitjançant el Teorema de Rouché-Frobenius. Identificar les variables determinades i lliures per resoldre sistemes per substitució enrere. Discutir l'existència de solucions d'un sistema lineal dependent de paràmetres. PENSA-HI ABANS DE LLEGIR 7 Com podem saber immediatament si un sistema té solució observant només les files de la matriu esglaonada?

Mètode d'eliminació de Gauss El mètode de Gauss és un procediment sistemàtic per transformar un sistema d'equacions lineals en un sistema equivalent esglaonat mitjançant operacions elementals per files aplicades sobre la matriu ampliada (vegeu «Sistemes d'equacions lineals — Conceptes bàsics i notació matricial»). L'objectiu és simplificar l'estructura de les equacions per determinar si existeix solució i calcular-la fàcilment. Les operacions permeses sobre les files són: intercanviar dues files entre si, multiplicar una fila sencera per un escalar no nul , o substituir una fila sumant-li un múltiple d'una altra fila.

En el mètode estàndard no s'apliquen operacions generals per columnes; l'única excepció permesa és la permutació de columnes, la qual altera l'ordre de les incògnites associades. El procediment d'esglaonament es desenvolupa seguint aquesta seqüència: CRITERI DE COMPATIBILITAT PER FILES Si en esglaonar apareix una fila on tots els coeficients de la matriu de coeficients són nuls però el terme independent és no nul, és a dir, una relació de la forma amb , el sistema és incompatible i no té solució. En canvi, si cap fila condueix a una contradicció d'aquest tipus, el sistema és compatible.

λ = 0 Esglaonar la matriu: S'apliquen transformacions elementals per files a la matriu ampliada fins a aconseguir una forma esglaonada superior. 1 Suprimir files nul·les: Si apareixen files compostes íntegrament per zeros tant a la part de coeficients com al terme independent ( ), s'eliminen en tractar-se d'equacions redundants. 2 0 = 0 Avaluar la compatibilitat: S'inspecciona la darrera fila no nul·la obtinguda per identificar si el sistema admet solucions. 3 0 = b b = 0 Sistemes Lineals, Gauss i Factorització LU — Àlgebra UdG 7 COMPROVA-HO 8 Quina interpretació algebraica té obtenir una fila de la forma (0 0 0 " 5) en esglaonar la matriu ampliada?

Classificació de variables i substitució enrere Un cop verificat que el sistema és compatible, s'analitzen les columnes de la matriu de coeficients esglaonada per classificar les incògnites: Variables determinades: Són aquelles incògnites que es troben en una columna que conté un pivot (el primer element no nul d'una fila). Variables lliures o indeterminades: Són aquelles incògnites situades en columnes sense pivot. Aquestes variables es converteixen en paràmetres als quals es pot assignar qualsevol valor real arbitrari. El nombre de variables lliures defineix el grau de llibertat del sistema.

Si totes les variables tenen pivot associat, el sistema és compatible determinat i compta amb solució única. En canvi, si existeix com a mínim una variable lliure, el sistema és compatible indeterminat i posseeix infinites solucions expressades en funció de tants paràmetres com graus de llibertat tingui. Per obtenir la solució explícita s'utilitza la substitució enrere: s'aïlla la variable determinada de l'última equació útil en funció dels paràmetres i es van substituint recursivament aquests valors cap amunt en les equacions precedents.

Sistemes Lineals, Gauss i Factorització LU — Àlgebra UdG 8 EXEMPLE: RESOLUCIÓ D'UN SISTEMA INDETERMINAT Resolem el següent sistema lineal: Formem la matriu ampliada i fem zeros sota la primera columna mitjançant i : Intercanviem les files segona i tercera ( ): A continuació, per facilitar l'esglaonament dels pivots, reordenem columnes permutant la posició de les columnes: . Això canvia l'ordre de les variables de a : Els pivots se situen a les tres primeres columnes, que corresponen a , i (variables determinades). Les incògnites i no tenen pivot i actuen com a variables lliures (2 graus de llibertat). Resolem per substitució enrere: Tercera fila: Segona fila: .

Com que , obtenim Primera fila: ERROR FREQÜENT Quan s'intercanvien columnes per facilitar l'esglaonament de la matriu, l'ordre del vector d'incògnites canvia directament. Si s'intercanvien columnes sense actualitzar la posició de les variables corresponents en la fase de substitució enrere, les relacions finals quedaran assignades a incògnites equivocades, invalidant completament el resultat. COMPROVA-HO 9 Quants graus de llibertat té un sistema de 5 incògnites la matriu de coeficients esglaonada del qual té exactament 3 pivots?

x + y 2z + t + 3u = 1 2x y + 2z + 2t + 6u = 2 3x + 2y 4z 3t 9u = 3 f 2 f 2 2f 1 f 3 f 3 3f 1 1 2 3 1 1 2 2 2 4 1 2 3 3 6 9 1 2 3 1 0 0 1 3 1 2 6 2 1 0 6 3 0 18 1 0 0 f 2 f 3 1 0 0 1 1 3 2 2 6 1 6 0 3 18 0 1 0 0 c , c 2 3 c , c 4 5 (x, y, z, t, u) (x, t, u, y, z) 1 0 0 1 6 0 3 18 0 1 1 3 2 2 6 1 0 0 x t y z u 3y + 6z = 0 y = 2z 6t 18u y + 2z = 0 y + 2z = 0 6t 18u = 0 t = 3u x + t + 3u + y 2z = 1 x + ( 3u) + 3u + (2z) 2z = 1 x = 1 Sistemes Lineals, Gauss i Factorització LU — Àlgebra UdG 9 Teorema de Rouché-Frobenius i discussió de sistemes El Teorema de Rouché-Frobenius proporciona una condició necessària i suficient per determinar l'existència i quantitat de solucions d'un sistema lineal de equacions amb incògnites a partir del rang matricial de la matriu de coeficients i de la matriu ampliada .

ENUNCIAT DEL TEOREMA DE ROUCHÉ-FROBENIUS Sigui un sistema amb incògnites: El sistema és incompatible (sense solució) si i només si . El sistema és compatible si i només si . Dins dels sistemes compatibles: Si r = n (el rang iguala el nombre d'incògnites), el sistema és compatible determinat (solució única). Si r < n, el sistema és compatible indeterminat amb variables determinades i n - r graus de llibertat (variables lliures).

Condició de rangs Classificació del sistema Tipus de solució Graus de llibertat Incompatible Cap solució No aplica Compatible Determinat Solució única 0 Compatible Indeterminat Infinites solucions ESQUEMA Classificació segons Rouché- Frobenius m n A A B AX = B n rang(A) < rang(A B) rang(A) = rang(A B) = r r rang(A) < rang(A B) rang(A) = rang(A B) = n rang(A) = rang(A B) = r < n n r rang(A) < rang(A"B) Incompatible: cap solució rang(A) = rang(A"B) = r Sistema compatible r = n Determinat: solució única r < n Indeterminat: n - r paràmetres Sistemes Lineals, Gauss i Factorització LU — Àlgebra UdG 10 EXEMPLE: DISCUSSIÓ AMB PARÀMETRES Considerem el sistema lineal següent en funció dels paràmetres i : Formem la matriu ampliada i apliquem Gauss mitjançant i : Intercanviem les files 2 i 3 ( ) per esglaonar: S'observa que la matriu de coeficients té de manera independent dels paràmetres, ja que té dues files no nul·les.

La discussió depèn exclusivament de la darrera fila: Si : La darrera fila té coeficients nuls però terme independent no nul ( ). Per tant, . Com que , el sistema és incompatible per a qualsevol valor de . Si : La darrera fila és nul·la en la seva totalitat. Llavors . Atès que el nombre d'incògnites és , tenim . El sistema és compatible indeterminat amb grau de llibertat per a qualsevol valor de . Substituint i resolent per substitució enrere, triem com a paràmetre lliure: Segona fila: Primera fila: COMPROVA-HO 10 Què passa en un sistema si rang(A) = 2 i rang(A"B) = 3 en termes d'equacions?

α β 2x + y + z = 2α 4x + 2y + 2z = 3α 6x + 2y + 3z = 2β A B f 2 f 2 2f 1 f 3 f 3 3f 1 2 4 6 1 2 2 1 2 3 2α 3α 2β 2 0 0 1 0 1 1 0 0 2α α 2β 6α f 2 f 3 2 0 0 1 1 0 1 0 0 2α 2β 6α α rang(A) = 2 α = 0 α = 0 rang(A B) = 3 rang(A) = 2 < 3 = rang(A B) β α = 0 rang(A) = rang(A B) = 2 n = 3 r < n 3 2 = 1 β α = 0 z y = 2β y = 2β 2x + ( 2β) + z = 0 x = ( z + 2 1 2β) Sistemes Lineals, Gauss i Factorització LU — Àlgebra UdG 11 IDEES CLAU L'eliminació de Gauss utilitza transformacions elementals per files per portar la matriu ampliada a forma esglaonada superior. Una fila esglaonada de la forma amb indica directament que el sistema és incompatible.

El Teorema de Rouché-Frobenius estableix la compatibilitat si i només si . Si un sistema és compatible i té , és indeterminat i conté exactament graus de llibertat associats a les columnes sense pivot. Intercanviar columnes durant l'esglaonament implica reordenar les incògnites del sistema abans de fer la substitució enrere. COMPROVA EL QUE HAS APRÈS 11. En quina circumstància un sistema compatible té solució única segons Rouché-Frobenius? 12. Com s'identifiquen quines incògnites són paràmetres lliures en una matriu esglaonada? Test Encercla la resposta correcta. Les solucions són al final. 13. Quin dels següents termes impedeix que una expressió sigui una equació lineal? 14.

Què podem assegurar d'un sistema lineal homogeni? 15. Com es representen en el pla les equacions d'un sistema 2x2 incompatible? 16. Quina conseqüència té intercanviar dues columnes de la matriu de coeficients A?

0 = b b = 0 rang(A) = rang(A B) r < n n r Més de tres incògnites a) Un coeficient fraccionari b) Un producte de dues incògnites c) Un terme independent negatiu d) Sempre és compatible a) Sempre té solució única b) És incompatible si té més incògnites c) No admet solucions no nul·les d) Dues rectes que es tallen a) Dues rectes perpendiculars b) Dues rectes coincidents c) Dues rectes paral·leles no coincidents d) Canvia l'ordre de les variables a) Modifica el conjunt de solucions b) Fa que el sistema esdevingui incompatible c) Canvia el signe del terme independent d) Sistemes Lineals, Gauss i Factorització LU — Àlgebra UdG 12 17. Un sistema té 4 incògnites i rang(A) = rang(A"B) = 3.

Quina és la seva classificació? 18. Què implica obtenir una fila esglaonada amb zeros llevat de l'últim terme independent? 19. Què cal fer si s'intercanvien dues columnes en aplicar el mètode de Gauss? 20. Segons Rouché-Frobenius, quan és incompatible un sistema lineal?

Compatible indeterminat amb 1 grau de llibertat a) Compatible indeterminat amb 3 graus de llibertat b) Compatible determinat c) Incompatible d) El sistema té infinites solucions a) Cal tornar a començar per columnes b) El sistema és incompatible c) Apareix una variable lliure nova d) Permutar les mateixes files per compensar a) Reassignar la posició de les variables associades b) Multiplicar la matriu per -1 c) Canviar el signe del terme independent d) Quan rang(A) és inferior a rang(A"B) a) Quan el rang és menor que el nombre d'incògnites b) Quan el nombre d'equacions supera el d'incògnites c) Quan totes les equacions tenen terme no nul d) Sistemes Lineals, Gauss i Factorització LU — Àlgebra UdG 13 3 Errors d'arrodoneixement i pivotatge parcial amb escalat EN ACABAR SABRÀS Identificar com l'aritmètica finita propaga errors d'arrodoniment en l'eliminació gaussiana.

Calcular els factors d'escalat de fila sumant els mòduls dels seus coeficients. Seleccionar la fila pivot adequada utilitzant el criteri del quocient màxim relatiu. Executar l'algorisme de Gauss amb pivotatge parcial escalat en un sistema pas a pas. PENSA-HI ABANS DE LLEGIR 21 Per què un ordinador pot fallar resolent un sistema senzill de dues equacions que a mà resolguem en un segon? Quan s'executa l'eliminació gaussiana en un ordinador, les operacions no es fan amb precisió infinita, sinó mitjançant una aritmètica finita de precisió limitada.

En aquest context, cada divisió o operació elemental genera petits errors d'arrodoniment que poden acumular-se i distorsionar greument el resultat final, fins al punt de produir solucions numèriques totalment incorrectes.

ESQUEMA Mètodes numèrics directes Mètodes numèrics directes 3 Errors d'arrodoneixement i pivotatge parcial amb escalat 4 Factorització LU i PA=LU 5 Condicionament de sistemes lineals Errors numèrics i pivotatge Errors d'arrodoneixement i pivotatge escalat Factorització de matrius Descomposició LU i factorització PA=LU Condicionament de sistemes Sensibilitat i nombre de condició Sistemes Lineals, Gauss i Factorització LU — Àlgebra UdG 14 El problema de l'aritmètica finita en el mètode de Gauss Durant el mètode de Gauss (vegeu «Sistemes d'equacions lineals — Resolució per Gauss i Teorema de Rouché-Frobenius»), dividir una fila per un pivot excessivament petit genera multiplicadors gegants.

Si sumem nombres de magnituds molt diferents en una màquina amb dígits limitats, els dígits menys significatius es perden completament. EXEMPLE: PÈRDUA DE PRECISIÓ AMB 8 DÍGITS Considerem el sistema següent resolt amb precisió de 8 dígits: Si prenem com a pivot, hem de dividir la primera equació per i sumar-la a la segona. El nou coeficient de a la segona fila passa a ser: A causa del límit de 8 dígits, el terme 4 queda totalment absorbit. El terme independent esdevé . Així obtenim . Substituint a la primera equació, resulta . No obstant això, en verificar aquests valors a la segona equació original: La solució ha fallat de manera estrepitosa.

En canvi, si simplement intercanviem les dues equacions abans de començar: Sumem a la segona fila la primera multiplicada per . El coeficient de serà . El sistema triangular resultant dona directament i, per tant, . Aquesta aproximació coincideix de manera excel·lent amb la solució exacta ( , ). COMPROVA-HO 22 Per quina raó dividir per un coeficient molt proper a zero deteriora el càlcul numèric? Pèrdua d'unicitat i solucions espúries El perill no rau únicament a desviar el valor de les incògnites: els errors d'arrodoneixement poden destruir la unicitat de la solució d'un sistema compatible determinat o fins i tot simular una indeterminació inexistent.

{ 10 x + y = 0,1234 8 x + 4y = 0 10 8 10 8 y 4 + = 10 8 1 4 + 10 = 8 100000004 108 0,1234 108 y = 0,1234 x = 0 0 + 4(0,1234) = 0,4936 = 0 { x + 4y = 0 10 x + y = 0,1234 8 10 8 y 1 + 4 10 = 8 1,00000004 1 y = 0,1234 x = 4y = 0,4936 x 0,49359998 y 0,123399995 Sistemes Lineals, Gauss i Factorització LU — Àlgebra UdG 15 EXEMPLE: PÈRDUA D'UNICITAT AMB 3 DÍGITS Treballant amb una aritmètica limitada a 3 dígits, estudiem el sistema: Si apliquem Gauss sumant a la segona fila la primera multiplicada per , s'obté: El coeficient de no s'ha anul·lat per culpa de l'arrodoniment. Si ignorem aquest residu i forcem el zero, arribem a i .

Si intercanviem les files des del començament: El factor multiplicador és ara . Fent l'operació obtenim la segona fila . El mètode diagnostica erròniament infinites solucions, quan en realitat la solució exacta única és i . Pivotatge parcial clàssic i la seva limitació Per reduir al mínim la magnitud dels multiplicadors i evitar divisions catastròfiques, cal escollir estratègicament la posició del pivot mitjançant una permutació de files.

DEFINICIÓ El pivotatge parcial consisteix a seleccionar a cada etapa com a pivot el coeficient de màxima magnitud absoluta situat sobre o sota la diagonal principal dins de la mateixa columna: Tot i ser una eina útil, el pivotatge parcial absolut és vulnerable als canvis d'escala de les equacions individuals (a través de transformacions elementals, vegeu «Sistemes d'equacions lineals — Conceptes bàsics i notació matricial»). Si multipliquem tota una fila per una constant gran, els seus coeficients augmenten sense alterar la solució matemàtica, però enganyen el criteri de selecció absolut.

Per exemple, observem aquests tres sistemes d'equacions equivalents: En el primer cas, el pivotatge parcial absolut triaria . En el segon es decantaria per la segona fila amb , mentre que en el tercer triaria la primera fila amb . Perquè la decisió sigui immune a reescalats arbitraris de files, cal una mesura relativa. { 0,196x + 3,14y = 4,14 0,344x + 5,51y = 7,27 = 0,196 0,344 1,755102...

1,76 { 0,196x + 3,14y = 4,14 0,001x 0,02y = 0,02 x y = 1 x 5,10 { 0,344x + 5,51y = 7,27 0,196x + 3,14y = 4,14 0,344 0,196 0,570 0,000x + 0,00y = 0 x = 82 y = 3,8 k a = kk a i=k,…,n max ik { 10x + 5y = 8 3x + 6y = 3 { 10x + 5y = 8 30x + 60y = 30 { x + 0,5y = 0,8 0,5x + y = 0,5 a = 11 10 a = 21 30 a = 11 1 Sistemes Lineals, Gauss i Factorització LU — Àlgebra UdG 16 COMPROVA-HO 23 Quina feblesa presenta el pivotatge parcial si no s'aplica cap tipus d'escalat? Pivotatge parcial amb escalat Per fer comparables els coeficients de diferents files, s'introdueix un factor d'escalat de fila.

Aquest factor mesura la mida global de l'equació a través de la suma dels valors absoluts de tots els seus coeficients: DEFINICIÓ El pivotatge parcial amb escalat tria a l'etapa com a fila pivot aquella que maximitza el coeficient relatiu respecte a la seva fila: Un cop localitzada aquesta fila, s'intercanvia amb la fila de la matriu ampliada abans de procedir a fer zeros sota la diagonal. ERROR FREQÜENT No inclogueu el terme independent en la suma d'escalat . La suma es calcula exclusivament sobre les columnes de la matriu de coeficients del sistema, mai sobre la columna ampliada.

Algorisme pas a pas en una matriu 4x4 A continuació es detalla la resolució completa d'un sistema lineal representat per la seva matriu ampliada : L'eliminació s'executa seguint aquests passos ordenats: Fila ( ) Coeficient ( ) Suma de la fila ( ) Quocient d'escalat 1 1,0 2 2,0 a j=1 n ij k i k max a j=1 n ij a ik k a j=1 n ij n M M = 1,0 2,0 6,0 4,0 2,0 3,0 2,0 3,0 3,0 4,0 4,0 7,0 1,0 8,0 2,0 1,0 3,0 5,0 7,0 2,0 Tria del primer pivot (columna 1): Calculem el quocient relatiu de cada fila candidata: 1 i a i1 a ij 1,0 + 2,0 + 3,0 + 1,0 = 7,0 7,0 1,0 0,14286 2,0 + 3,0 + 4,0 + 8,0 = 17,0 17,0 2,0 0,11765 Sistemes Lineals, Gauss i Factorització LU — Àlgebra UdG 17 Fila ( ) Coeficient ( ) Suma de la fila ( ) Quocient d'escalat 3 6,0 4 4,0 El màxim s'assoleix a la fila 3.

Intercanviem les files 1 i 3 i fem zeros a la primera columna: Fila ( ) Coeficient ( ) Suma restant ( ) Quocient d'escalat 2 2,3333 3 1,6667 4 1,6667 El valor relatiu més alt correspon a la fila 3 (0,35715). Intercanviem les files 2 i 3, i fem zeros a la columna 2: Fila ( ) Càlcul del quocient relatiu Valor 3 4 El màxim es troba clarament a la fila 4.

Intercanviem les files 3 i 4, i eliminem el terme de la columna 3 sota el pivot: Un cop la matriu és triangular superior, apliquem la substitució enrere (vegeu «Sistemes d'equacions lineals — Resolució per Gauss i Teorema de Rouché-Frobenius») per obtenir el vector solució final: i a i1 a ij 6,0 + 2,0 + 4,0 + 2,0 = 14,0 14,0 6,0 0,42857 4,0 + 3,0 + 7,0 + 1,0 = 15,0 15,0 4,0 0,26667 6,0000 0 0 0 2,0000 2,3333 1,6667 1,6667 4,0000 2,6667 2,3333 4,3333 2,0000 7,3333 0,6667 0,3333 7,0000 2,6667 1,8333 2,6667 Tria del segon pivot (columna 2): Avaluem les files restants (de la 2 a la 4): 1 i a i2 a j=2 4 ij 2,3333 + 2,6667 + 7,3333 = 12,3333 12,3333 2,3333 0,18919 1,6667 + 2,3333 + 0,6667 = 4,6667 4,6667 1,6667 0,35715 1,6667 + 4,3333 + 0,3333 = 6,3333 6,3333 1,6667 0,26316 6,0000 0 0 0 2,0000 1,6667 0 0 4,0000 2,3333 0,5999 2,0000 2,0000 0,6667 6,4000 0,9999 7,0000 1,8333 0,1001 4,5000 Tria del tercer pivot (columna 3): Avaluem les files 3 i 4: 1 i 0,5999+6,4000 0,5999 0,085701 2,0000+ 0,9999 2,0000 0,66667 6,0000 0 0 0 2,0000 1,6667 0 0 4,0000 2,3333 2,0000 0 2,0000 0,6667 0,9999 6,1001 7,0000 1,8333 4,5000 1,2497 (x , x , x , x ) = 1 2 3 4 (1,3115, 4,4753, 2,3525, 0,20487) Sistemes Lineals, Gauss i Factorització LU — Àlgebra UdG 18 COMPROVA-HO 24 En el pas 2 de l'exemple 4x4, per què es tria la fila amb coeficient 1,6667 en lloc de la que té 2,3333?

IDEES CLAU L'aritmètica de precisió finita introdueix errors d'arrodoniment que es poden amplificar durant les eliminacions. Dividir per nombres propers a zero genera multiplicadors gegants capaços d'esborrar informació rellevant d'altres files. El pivotatge parcial absolut busca el coeficient de màxim valor absolut dins la columna per estabilitzar el càlcul. El pivotatge parcial amb escalat divideix el candidat a pivot per la suma dels valors absoluts de la fila per evitar distorsions per canvis d'unitats o factors d'escala. COMPROVA EL QUE HAS APRÈS 25. Com es defineix matemàticament el factor d'escalat que s'utilitza a cada fila? 26.

Quin criteri exacte s'utilitza per escollir la fila pivot a l'etapa amb pivotatge escalat? MÈTODES NUMÈRICS DIRECTES 4 Factorització LU i PA=LU EN ACABAR SABRÀS Determinar les condicions dels menors principals per a l'existència de la factorització LU. Executar la factorització PA = LU aplicant el pivotatge parcial amb escalat. Resoldre un sistema lineal d'equacions mitjançant les dues etapes de substitució triangular. Avaluar numèricament l'efecte del pivotatge sobre el residu del sistema. PENSA-HI ABANS DE LLEGIR 27 Per què val la pena descompondre una matriu A en dues matrius triangulars L i U en lloc de resoldre directament el sistema per eliminació de Gauss?

Fonament de la descomposició LU La factorització LU és una tècnica fonamental de l'àlgebra lineal numèrica que descompon una matriu quadrada en el producte de dues matrius: una matriu triangular inferior i una matriu triangular superior . Aquesta transformació equival a dur a terme l'eliminació gaussiana sobre sense actuar k A L U A Sistemes Lineals, Gauss i Factorització LU — Àlgebra UdG 19 directament sobre el vector de termes independents. DEFINICIÓ DE LES MATRIUS L I U Matriu (Lower): matriu triangular inferior que té 1s a la diagonal principal ( per a ) i que emmagatzema a sota de la diagonal els coeficients multiplicadors utilitzats en cada pas de l'eliminació.

Matriu (Upper): matriu triangular superior que resulta directament d'esglaonar la matriu mitjançant operacions elementals per files. Formalment, els coeficients de cadascuna de les matrius resultants s'expressen com: No totes les matrius permeten una descomposició directa sense reordenar les files. La condició matemàtica precisa estableix que una matriu admet una factorització única (amb ) si i només si tots els seus menors principals són no singulars, és a dir, per a tot , on és la submatriu d'ordre formada per la intersecció de les primeres files i columnes d'origen. EXEMPLE DE FACTORITZACIÓ LU SENSE INTERCANVI DE FILES Considerem la següent matriu quadrada d'ordre 3: L l = ii 1 i = 1, …

, n m = ik a kk (k 1) a ik (k 1) U A l = ik u = m = ik a kk (k 1) a ik (k 1) 0 i k i < k kj { 0 a kj (k) k > j k j A = LU A A = LU l = ii 1 det(A ) = k 0 k = 1, … , n A k k × k k A = 4 2 1 9 4 2 2 4 2 Primer pas d'eliminació: el pivot és . Calculem els multiplicadors i . Fem les operacions i : 1 a = 11 4 m = 21 = 4 2 0,5 m = 31 = 4 1 0,25 f 2 f 2 0,5f 1 f 3 f 3 ( 0,25)f 1 4 0 0 9 0,5 0,25 2 3 2,5 Segon pas d'eliminació: el pivot és ara . El multiplicador per anul·lar la posició sota d'ell és .

Fem : 2 a = 22 0,5 m = 32 = 0,5 0,25 0,5 f 3 f 3 ( 0,5)f 2 U = 4 0 0 9 0,5 0 2 3 4 Construcció de : situem 1s a la diagonal i els multiplicadors trobats sota d'ella: 3 L L = 1 0,5 0,25 0 1 0,5 0 0 1 Sistemes Lineals, Gauss i Factorització LU — Àlgebra UdG 20 COMPROVA-HO 28 Quina condició necessiten els menors principals Ak d'una matriu A per garantir que existeixi la descomposició A = LU exacta amb uns a la diagonal de L? Factorització PA = LU i resolució de sistemes Quan durant l'eliminació s'obté un zero a la posició del pivot, o quan cal aplicar estratègies de selecció per mitigar els errors numèrics, cal intercanviar files.

Tota matriu quadrada invertible admet una descomposició de la forma , on és una matriu de permutació (una matriu identitat amb les seves files reordenades segons els intercanvis fets durant el procés). Aquesta formulació és especialment potent a la pràctica: permet resoldre un sistema lineal d'equacions en dues fases consecutives que només requereixen substitucions triangulars. PROCÉS Procediment de resolució amb factorització PA = LU 1 Factorització PA = LU Descomposició de la matriu amb pivotatge parcial i escalat integrat. 2 Permutació Pb Reordenació del vector b aplicant la matriu de permutació P. 3 Substitució directa Resolució del sistema triangular inferior Ly = Pb per obtenir y.

4 Substitució enrere Resolució del sistema triangular superior Ux = y per obtenir x. PER RECORDAR-HO La factorització és molt eficient quan s'ha de resoldre repetidament el mateix sistema amb la matriu fixa però múltiples vectors distints. La part computacionalment costosa de descomposició només s'executa una sola vegada, i cada resolució posterior només requereix substitucions ràpides sobre i . COMPROVA-HO 29 Per què la factorització PA = LU és computacionalment preferible al mètode de Gauss convencional quan es resolen molts sistemes amb la mateixa matriu A? A P A = LU P Ax = b Reordenació del terme independent: es multiplica el vector per la matriu de permutació, calculant el vector .

Això aplica a exactament els mateixos canvis de fila que s'han fet sobre . 1 b P b b A Substitució directa ( ): es resol el sistema triangular inferior per trobar la incògnita intermèdia començant per la primera component i descendint. 2 Ly = P b y Substitució enrere ( ): es resol el sistema triangular superior començant per la darrera variable i pujant, obtenint així el vector solució final .

3 Ux = y x P A = LU A b L U Sistemes Lineals, Gauss i Factorització LU — Àlgebra UdG 21 Factorització amb pivotatge parcial i escalat integrat Per evitar inestabilitats numèriques i amplificació d'errors en aritmètica finita, s'incorpora la tècnica de pivotatge parcial amb escalat (vegeu «Mètodes numèrics directes — Errors d'arrodoneixement i pivotatge parcial amb escalat»). En cada etapa , el candidat a pivot s'escull comparant el valor absolut de l'element de la columna amb el factor d'escalat de la seva fila, calculat com la suma dels valors absoluts dels seus elements: .

L'índex seleccionat correspon al màxim quocient relatiu: Quan s'efectua un intercanvi de les files i , l'operació s'ha de reflectir en: Les files i de la matriu que s'està triangulant. Les files i de la matriu de permutació . Les columnes ja calculades (posicions a l'esquerra de la columna activa) de la matriu . ERROR FREQÜENT Un dels errors més habituals en implementar manualment consisteix a oblidar intercanviar els elements ja emmagatzemats a la matriu quan es fa un pivotatge de files en etapes avançades. Si s'intercanvien les files i d' i de , els multiplicadors i prèviament calculats a (per a ) també han d'intercanviar-se.

Exemple complet pas a pas en dimensió 4 Resolem el següent sistema aplicant factorització amb pivotatge parcial escalat: Iniciem amb i . Etapa 1: Elecció del primer pivot Dividim el mòdul de cada element de la primera columna per la suma de la seva fila en valor absolut. Els quocients obtinguts són: El valor relatiu màxim és 0,518, que correspon a la fila 2. Triem com a pivot l'element 14,6 i intercanviem les files 1 i 2 a les matrius i .

Posteriorment anul·lem els elements de la columna 1 calculant els multiplicadors , i , que s'incorporen a la primera columna de : k a j=1 n ij i k max a j=1 n ij a ik r s r s A r s P L P A = LU L i k A P m ij m kj L j < k Ax = b P A = LU = 1,17 14,6 0 14,7 2,11 0,128 98,5 0,123 99,9 12,5 90,9 12,8 1,02 1,00 1,00 1,00 x 1 x 2 x 3 x 4 1,12 4,34 2,55 4,12 P = I L = I 0,0113 (f ), 0,518 (f ), 0 (f ), 0,514 (f ) 1 2 3 4 A P m = 21 = 14,6 1,17 0,0801 m = 31 0 m = 41 = 14,6 14,7 1,01 L Sistemes Lineals, Gauss i Factorització LU — Àlgebra UdG 22 Etapa 2: Elecció del segon pivot Avaluem els candidats de la segona columna per a les files 2, 3 i 4.

Els valors escalats resulten: El màxim és 0,518 a la fila 3 ( ). Intercanviem les files 2 i 3 a , i a la primera columna de . Després fem zeros sota el pivot calculant i : Etapa 3: Elecció del tercer pivot Comparem les files 3 i 4 per a la columna 3. Els valors un cop escalats són 0,991 i 1,00. Donat que la fila 4 presenta la proporció superior, triem el pivot a la fila 4 (-25,2) i intercanviem les files 3 i 4 a , a i a les dues primeres columnes de . Finalment fem zero l'element restant calculant , amb el qual s'obté i es completa : Resolució per etapes Multipliquem el vector per la permutació acumulada : Resolem per substitució directa, trobant .

Tot seguit resolem per substitució enrere: Comparació de precisió: amb pivotatge versus sense pivotatge Si avaluem la consistència del resultat substituint la solució obtinguda al sistema original , comprovem la magnitud del residu generat respecte al terme original : A = , P = 14,6 0 0 0 0,128 2,12 98,5 0,252 12,5 101,0 90,9 25,4 1,00 1,10 1,00 0,01 , L = 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 1 1 0,0801 0 1,01 0 0 0 0 0 0 0 0 0 0 0 0 0,0204 (f ), 0,518 (f ), 0,00981 (f ) 2 3 4 a = 32 98,5 A P L m = 32 = 98,5 2,12 0,0215 m = 42 = 98,5 0,252 0,00256 A = , L = 14,6 0 0 0 0,128 98,5 0 0 12,5 90,9 99,1 25,2 1,00 1,00 1,08 0,00744 1 0 0,0801 1,01 0 1 0,0215 0,00256 0 0 0 0 0 0 0 0 A P L m = 43 = 25,2 99,1 3,93 U L U = , L = 14,6 0 0 0 0,128 98,5 0 0 12,5 90,9 25,2 0 1,00 1,00 0,00744 1,05 1 0 1,01 0,0801 0 1 0,00256 0,0215 0 0 1 3,93 0 0 0 1 b P P b = = 0 0 0 1 1 0 0 0 0 1 0 0 0 0 1 0 1,12 4,34 2,55 4,12 4,34 2,55 4,12 1,12 Ly = P b y = (4,34, 2,55, 0,27, 1,78)T Ux = y x = 0,404 0,0190 0,0112 1,70 x Ax b Sistemes Lineals, Gauss i Factorització LU — Àlgebra UdG 23 Mètode emprat Solució trobada Vector recalculat Vector exacte Factorització amb pivotatge i escalat Factorització directa sense pivotatge Quan s'omet el pivotatge, els errors d'arrodoniment es propaguen lliurement: les components del terme independent recalculat difereixen de forma notable (per exemple, 4,42 davant de 4,34 i 2,38 davant de 2,55).

En canvi, el pivotatge parcial amb escalat manté els valors extraordinàriament propers als originals (amb només una desviació mínima a l'última component de 4,10 enfront de 4,12). COMPROVA-HO 30 Quina discrepància pràctica es detecta en recalcular Ax quan no s'aplica pivotatge enfront de quan sí que s'aplica? IDEES CLAU La factorització desglossa en una matriu triangular inferior (amb uns a la diagonal i multiplicadors a sota) i una triangular superior . La factorització sense intercanvis requereix que tots els menors principals compleixin . Tota matriu invertible admet , on registra les permutacions de files dutes a terme durant el procés.

Un sistema es resol ràpidament resolent dos sistemes triangulars consecutius: i posteriorment . El pivotatge parcial amb escalat tria el pivot maximitzant el quocient relatiu respecte a la suma de la fila, evitant l'acumulació destructiva d'errors d'arrodoniment. COMPROVA EL QUE HAS APRÈS 31. Quins elements concrets conformen la matriu triangular inferior obtinguda mitjançant eliminació gaussiana? 32. Què cal fer amb la matriu quan s'intercanvien dues files a causa del pivotatge durant la factorització ?

MÈTODES NUMÈRICS DIRECTES 5 Condicionament de sistemes lineals x Ax b (0,404, 0,0190, 0,0112, 1,70)T 1,12 4,34 2,55 4,10 1,12 4,34 2,55 4,12 (0,419, 0,0174, 0,0132, 1,87)T 1,12 4,42 2,38 4,12 1,12 4,34 2,55 4,12 A L U A = LU det(A ) = k 0 P A = LU P Ax = b Ly = P b Ux = y L L P A = LU Sistemes Lineals, Gauss i Factorització LU — Àlgebra UdG 24 EN ACABAR SABRÀS Definir el concepte de sistema mal condicionat segons la seva resposta a pertorbacions. Explicar per què el determinant de la matriu no és un criteri fiable de condicionament. Calcular l'àrea del paral·lelogram de vectors directors normalitzats en sistemes 2x2. Aplicar la fórmula del nombre de condició k(A) a les fites d'error relatiu.

PENSA-HI ABANS DE LLEGIR 33 Un determinant molt proper a zero significa sempre que el sistema lineal patirà problemes numèrics greus? Sensibilitat davant pertorbacions: concepte de mal condicionament En el càlcul numèric, certs sistemes lineals presenten una enorme vulnerabilitat davant les imprecisions pròpies de l'aritmètica finita o dels mesuraments experimentals. Fins i tot emprant estratègies com el pivotatge parcial amb escalat (vegeu «Mètodes numèrics directes — Errors d'arrodoneixement i pivotatge parcial amb escalat»), la solució obtinguda pot diferir completament de la solució teòrica exacta.

Aquesta dificultat no prové del mètode algorítmic emprat, sinó de la mateixa naturalesa matemàtica del problema plantejat. DEFINICIÓ Un sistema d'equacions lineals rep el nom de sistema mal condicionat quan modificacions mínimes en les dades d'entrada (coeficients de la matriu o termes independents) desencadenen canvis de gran magnitud en el vector solució. Per entendre l'abast d'aquest comportament, considerem dos sistemes lineals gairebé idèntics. En el primer cas, tenim: La resolució d'aquest sistema proporciona com a solució exacta i .

Si ara introduïm una pertorbació molt petita en l'element , canviant el seu valor en una mil·lèsima, passem al sistema pertorbat: Aquesta petita alteració representa una disminució de només el 0,1 % en el coeficient. Malgrat això, les noves solucions passen a ser i La resposta del sistema ha variat aproximadament un 11 %, amplificant l'error inicial en més de dos ordres de magnitud. Aquest fenomen d'amplificació descontrolada és el tret distintiu d'un sistema mal condicionat. = ( 1 1 1 0,99 ) ( x y ) ( 1 0 ) x = 99 y = 100 a 22 = ( 1 1 1 0,991 ) ( x y ) ( 1 0 ) x = 110,11 … y = 111,11 …

Sistemes Lineals, Gauss i Factorització LU — Àlgebra UdG 25 COMPROVA-HO 34 Què caracteritza la resposta d'un sistema mal condicionat davant petites variacions en les dades inicials? El determinant com a fals indicador de condicionament Una temptació habitual consisteix a creure que el determinant de la matriu de coeficients permet detectar el mal condicionament. En el primer exemple analitzat, la matriu original té determinant i la pertorbada . Podríem inferir que el fet de tenir un determinant molt proper a zero n'és la causa. No obstant això, aquesta conclusió és falsa. Analitzem un segon escenari format pel sistema següent: La solució immediata d'aquest sistema és i .

Si apliquem exactament la mateixa pertorbació relativa del 0,1 % al coeficient : Obtenim com a nova solució i En aquesta ocasió, la solució ha experimentat una variació de tot just el 0,1 %, exactament en la mateixa proporció que la pertorbació d'entrada. El sistema és, per tant, ben condicionat. Sistema Valor de Pertorbació en Variació de la solució Estat del sistema Primer parell 0,01 0,1 % Aproximadament 11 % Mal condicionat Segon parell 0,001 0,1 % 0,1 % (proporcional) Ben condicionat Com es pot comprovar a la taula comparativa, els determinants del segon parell són i , és a dir, un ordre de magnitud inferiors als del primer parell.

Tot i tenir un determinant molt més proper a zero, el segon sistema és completament estable. El determinant no constitueix un criteri fiable per diagnosticar el condicionament d'una matriu. ERROR FREQÜENT Assumir que un determinant petit implica necessàriament que el sistema està mal condicionat. El determinant depèn de l'escala global de les equacions (multiplicar files per escalars canvia el determinant sense alterar les rectes), de manera que un valor pròxim a zero pot correspondre perfectament a un sistema ben condicionat. COMPROVA-HO 35 Per què un valor de det(A) proper a zero no demostra que un sistema estigui mal condicionat?

det(A) = 0,01 det(A ) = 0,009 = ( 0,1 0 0 0,01 ) ( x y ) ( 1 1 ) x = 10 y = 100 a 22 = ( 0,1 0 0 0,01001 ) ( x y ) ( 1 1 ) x = 10 y = 99,90 … det(A) a 22 det(A) = 0,001 det(A ) = 0,001001 Sistemes Lineals, Gauss i Factorització LU — Àlgebra UdG 26 Interpretació geomètrica: àrea del paral·lelogram Una anàlisi visual ofereix una explicació intuïtiva del fenomen. En un sistema de dues equacions amb dues incògnites: Cadascuna de les files representa una recta en el pla real: i . La solució del sistema correspon a la intersecció d'ambdues rectes. En el primer exemple, les rectes són gairebé paral·leles.

Un lleu desplaçament o canvi de pendent en una d'elles mou el punt de tall a una posició molt allunyada. En canvi, en el segon exemple, les rectes són estrictament perpendiculars; un petit gir amb prou feines pertorba el punt d'intersecció.

Per quantificar aquest fet geomètric de forma invariant a l'escala, es construeixen els vectors directors unitaris i de cadascuna de les rectes, normalitzats de manera que la seva component dominant tingui mòdul unitari: Escollint el sentit de tal que l'angle entre ambdós vectors verifiqui , l'àrea A del paral·lelogram format per aquests vectors directors és igual a: Aquesta àrea mesura directament la independència geomètrica de les equacions: Si , les rectes són properes a l'ortogonalitat i el sistema està ben condicionat. Si , les rectes són pràcticament paral·leles i el sistema està mal condicionat.

En el primer exemple numèric s'obté (àrea reduïda, mal condicionat), mentre que en el segon cas resulta (àrea màxima, ben condicionat). Aquest criteri es generalitza a dimensions superiors definint l'àrea normalitzada com el quocient entre el determinant i el producte de les normes infinites de cada fila: = ( a 11 a 21 a 12 a 22 ) ( x y ) ( b 1 b 2 ) r : 1 a x + 11 a y = 12 b1 r : 2 a x + 21 a y = 22 b2 v 1 v 2 v = 1 , ( max( a , a ) 11 12 a 12 max( a , a ) 11 12 a 11 ) v = 2 , ( max( a , a ) 21 22 a 22 max( a , a ) 21 22 a 21 ) v 2 θ π/2 A = = max( a , a ) max( a , a ) 11 12 21 22 a a a a 11 22 12 21 max( a , a ) max( a , a ) 11 12 21 22 det(A) A 1 A 0 A = 0,01 A = 1 n × n A = max( a , …

, a ) i=1 n i1 in det(A) Sistemes Lineals, Gauss i Factorització LU — Àlgebra UdG 27 ESQUEMA Condicionament geomètric en sistemes 2x2 COMPROVA-HO 36 Quina relació geomètrica hi ha entre l'angle de dues rectes i el condicionament del sistema 2x2 corresponent? El nombre de condició i cotes d'error Per abordar el condicionament de forma rigorosa i aplicable a qualsevol dimensió matricial s'utilitza una mesura analítica basada en normes matricials subordinades. DEFINICIÓ Donada una matriu quadrada , el nombre de condició es defineix formalment com: El nombre de condició actua com un factor d'amplificació de l'error relatiu.

Com més gran és el valor de , més inestable és el sistema davant d'imprecisions numèriques. Aquesta propietat es plasma en dues fites superiors fonamentals que acoten la propagació dels errors. En primer lloc, si el vector de termes independents pateix una pertorbació , l'error relatiu en la solució resultant queda delimitat per: En segon lloc, si la pertorbació es produeix en els coeficients de la matriu , generant una variació , la cota superior de l'error relatiu obeeix a l'expressió: Aquestes desigualtats demostren que un nombre de condició elevat pot provocar que una pertorbació residual en les dades contamini greument la precisió final del càlcul.

Disposició geomètrica Posició relativa de les rectes Quasi paral·leles Angle petit entre vectors directors Àrea A propera a 0 Sistema mal condicionat Perpendiculars Angle proper a 90 graus Àrea A propera a 1 Sistema ben condicionat A k(A) k(A) = { A A , 1 , si A s no singular e ˊ si A s singular e ˊ k(A) Δb Δx x Δx k(A) b Δb A ΔA x + Δx Δx k(A) A ΔA Sistemes Lineals, Gauss i Factorització LU — Àlgebra UdG 28 COMPROVA-HO 37 Si una matriu és singular, quin és el valor del seu nombre de condició k(A)? IDEES CLAU Un sistema mal condicionat és aquell on pertorbacions minúscules en les dades inicials provoquen errors de gran magnitud en la solució.

El determinant d'una matriu no és una mesura vàlida ni fiable de condicionament numèric. Geomètricament en dimensió 2, les rectes quasi paral·leles generen una àrea normalitzada propera a zero i representen mal condicionament. Les rectes perpendiculars tenen una àrea de paral·lelogram igual a 1 i representen sistemes òptimament condicionats. El nombre de condició k(A) mesura la màxima amplificació teòrica de l'error relatiu tant per pertorbacions en b com en A. COMPROVA EL QUE HAS APRÈS 38. Com es calcula l'àrea normalitzada A del paral·lelogram en un sistema 2x2? 39. Quina fita relaciona la pertorbació del terme independent amb l'error relatiu en la solució?

Test Encercla la resposta correcta. Les solucions són al final. 40. Quin és el risc principal d'utilitzar un pivot extremadament petit en Gauss? 41. Per quin motiu el pivotatge parcial clàssic sense escalar pot escollir una fila incorrecta? 42. Com es calcula el denominador del quocient del pivotatge parcial amb escalat?

Augmentar automàticament el nombre de solucions a) Obtenir multiplicadors gegants que eclipsen coeficients b) Convertir la matriu del sistema en no invertible c) Fer que el determinant canviï de signe espontàniament d) Exclou sempre els termes que són negatius a) No permet mai fer intercanvi de files b) Només serveix per a sistemes de dues equacions c) És sensible a la multiplicació d'equacions per constants d) Sumant la fila incloent el terme independent a) Sumant els elements de la columna b) Multiplicant tots els coeficients de la matriu c) Sumant els valors absoluts de la fila d) Sistemes Lineals, Gauss i Factorització LU — Àlgebra UdG 29 43.

Què succeeix en aritmètica finita si no es pivota adequadament en sistemes determinats? 44. Quina condició garanteix l'existència i unicitat de la factorització A = LU sense permutacions? 45. Quin és el primer pas en resoldre Ax = b un cop obtinguda la factorització PA = LU? 46. Com es tria el pivot akk en el pivotatge parcial amb escalat? 47. Quina diferència s'observa al terme independent recalculat Ax si no s'utilitza pivotatge? 48. Com es comporta un sistema mal condicionat? 49. Per què el determinant no és un bon indicador?

La matriu triangular obtinguda és sempre exacta a) Es pot diagnosticar falsament una indeterminació b) Tots els termes independents s'anul·len c) El rang de la matriu sempre es duplica d) Tots els elements de la diagonal no nuls a) det(A) = 0 i traça positiva b) Matriu simètrica amb valors propis positius c) det(Ak) 0 per a tots els menors principals d) Resoldre Ux = Pb per substitució directa a) Efectuar la substitució enrere a Ly = b b) Calcular la inversa de la matriu U c) Resoldre Ly = Pb per substitució directa d) La suma més gran dels elements de la columna a) El coeficient amb menor mòdul de la columna b) L'element de la diagonal principal sense modificar c) Maximitzant el quocient "aik" / sum"aij" sobre i >= k d) Es produeix un residu notable respecte a b a) La solució x sempre divergeix a infinit b) El vector Ax és exactament nul c) No hi ha cap diferència respecte al pivotatge d) No admet cap tipus de pivotatge.

a) Té infinites solucions de rang màxim. b) El seu determinant és estrictament zero. c) Petits canvis inicials provoquen grans variacions. d) Només es calcula per a matrius rectangulars. a) Sempre és negatiu en sistemes inestables. b) No està definit per a matrius invertibles. c) Depèn de l'escala dels coeficients matricials. d) Sistemes Lineals, Gauss i Factorització LU — Àlgebra UdG 30 50. Què indica una àrea del paral·lelogram propera a 1 en el pla? 51. Quin és el nombre de condició d'una matriu singular?

6 Formulari Sistemes d'equacions lineals i Teorema de Rouché-Frobenius Fórmula o procediment Significat dels símbols Quan s'aplica (coeficients), (incògnites), (termes independents) Formulació matricial compacta d'un sistema lineal de equacions amb incògnites. : solucions diferents del sistema; : paràmetre real lliure Generació d'infinites solucions en sistemes lineals amb més d'una solució. Matriu ampliada Esglaonament per files Eliminació de files nul·les Detecció de pivots i paràmetres Substitució enrere Operacions elementals per files: , ( ), Resolució analítica exacta d'un sistema lineal mitjançant eliminació gaussiana.

: SI : SCD : SCI : nombre d'incògnites; : rang de la matriu de coeficients; : graus de llibertat (paràmetres lliures) Discussió i classificació de l'existència i quantitat de solucions (Teorema de Rouché-Frobenius). Rectes quasi paral·leles i mal condicionades. a) Matriu singular sense solució única. b) Error d'arrodoneixement superior al 100%. c) Rectes properes a perpendiculars i bon condicionament.

d) El seu propi determinant a) U b) Zero c) Infinit d) A X = B A Rm×n X Rn×1 B Rm×1 m n X = X + 1 α(X 2 X ), α 1 R X , X 1 2 α (A B) (0 = 0) f i f j λf i λ = 0 f + i λf j rang(A) < rang(A B) rang(A) = rang(A B) = n rang(A) = rang(A B) = r < n n r n r Sistemes Lineals, Gauss i Factorització LU — Àlgebra UdG 31 Mètodes numèrics: Pivotatge parcial amb escalat Fórmula o procediment Significat dels símbols Quan s'aplica : factor d'escala de la fila ; : coeficients de la matriu del sistema Mesurar la magnitud relativa de cada equació sense incloure el terme independent.

Fila pivot tal que : índex de l'etapa (columna activa); : files candidates a pivot Selecció de la fila pivot abans d'anul·lar una columna per minimitzar errors d'arrodoniment. Factorització LU i PA = LU Fórmula o procediment Significat dels símbols Quan s'aplica amb , , : triangular inferior amb 1s a la diagonal; : triangular superior (esglaonada de Gauss) Descomposició directa quan tots els menors principals compleixen . Resoldre (substitució directa) Resoldre (substitució enrere) : matriu de permutacions acumulades; : vector auxiliar; : solució final Resolució de sistemes amb pivotatge o amb múltiples vectors .

Condicionament de sistemes lineals Fórmula o procediment Significat dels símbols Quan s'aplica : àrea del paral·lelogram format pels vectors directors unitaris de les rectes Diagnòstic geomètric de condicionament en sistemes 2x2 ( ben condicionat; mal condicionat). Quocient entre el determinant i el producte de les normes infinites de cada fila Extensió del criteri geomètric de condicionament a sistemes . (si no singular), (singular) : nombre de condició; : norma matricial subordinada Mesura analítica de la sensibilitat i amplificació de l'error en un sistema lineal.

: pertorbació del terme independent; : error generat a la solució Cota superior de l'error relatiu en la solució davant variacions en . : pertorbació a la matriu de coeficients Cota superior de l'error relatiu davant variacions als coeficients de la matriu .

s = i a j=1 n ij s i i a ij p = s p a pk max i k a j=1 n ij a ik k i k A = LU l = ii 1 l = ik m = ik a kk (k 1) a ik (k 1) u = kj a kj (k) L U det(A ) = k 0 P A = LU Ly = P b U x = y P y x Ax = b b A = par max( a , a ) max( a , a ) 11 12 21 22 det(A) A par 1 0 A = par max a i=1 n 1 j n ij det(A) n × n k(A) = A A 1 k(A) = k(A) x Δx k(A) b Δb Δb Δx b x+Δx Δx k(A) A ΔA ΔA A Sistemes Lineals, Gauss i Factorització LU — Àlgebra UdG 32 Errors típics Incloure el terme independent en l'escalat: El sumatori s'ha de calcular únicament sobre les columnes de la matriu de coeficients .

Oblidar permutar la matriu L: En la factorització , en intercanviar dues files per pivotatge cal intercanviar immediatament les columnes prèviament calculades de la matriu . Confondre determinants petits amb mal condicionament: Un determinant proper a zero pot provenir d'un simple factor d'escala; cal utilitzar l'àrea normalitzada o el nombre de condició . Ometre la reordenació de variables: Si es permuten columnes durant l'eliminació gaussiana, cal actualitzar l'ordre del vector d'incògnites abans de fer la substitució enrere. a ij A P A = LU L k(A) Sistemes Lineals, Gauss i Factorització LU — Àlgebra UdG 33 Solucions de les preguntes de repàs 1.

No; la combinació afí de dues solucions diferents demostra que, si n'hi ha més d'una, automàticament n'hi ha infinites. 2. Perquè conté un producte de dues incògnites (x·y), fet que li atorga grau 2 i trenca la linealitat. 3. No, mai pot ser incompatible perquè el vector de zeros sempre verifica totes les equacions (solució trivial). 4. Val 0, ja que per linealitat A·X - A·X = B - B = 0. Per tant, la diferència és solució del sistema homogeni associat. 5. Perquè si té dues solucions diferents i , la combinació genera una nova solució per a cada valor real de , fent que en tingui infinites. 6.

L'escalar ha de ser necessàriament diferent de zero ( ); en cas contrari, s'eliminaria la informació de l'equació i es perdria l'equivalència. 7. Comprovant si apareix alguna fila amb tots els coeficients iguals a zero però amb un terme independent diferent de zero (0 = b), cosa que delata que el sistema és incompatible. 8. Representa l'equació 0 = 5, una contradicció matemàtica impossible de satisfer. Per tant, el sistema és incompatible i manca completament de solució. 9. Té 5 - 3 = 2 graus de llibertat, ja que hi ha 2 columnes sense pivot que actuaran com a variables lliures o paràmetres. 10.

Significa que en esglaonar s'obté una fila de tipus 0 = b amb b no nul, generant una contradicció lògica que fa que el sistema no tingui cap solució. 11. Quan el rang de la matriu de coeficients coincideix amb el rang de la matriu ampliada i aquest és exactament igual al nombre d'incògnites ( ). 12. Són les incògnites associades a les columnes de la matriu de coeficients que no contenen cap pivot. 13. c) Un producte de dues incògnites. El producte de dues incògnites té grau dos i trenca la linealitat de l'expressió. 14. a) Sempre és compatible. Com que el vector format exclusivament per zeros sempre el verifica, és com a mínim compatible. 15. d) Dues rectes paral·leles no coincidents.

En no tenir cap punt en comú, les dues rectes han de ser paral·leles i diferents. 16. a) Canvia l'ordre de les variables. Cada columna correspon a una incògnita; si s'intercanvien, cal reordenar el vector d'incògnites associat. 17. a) Compatible indeterminat amb 1 grau de llibertat. Com que els rangs són iguals és compatible, i amb 4 incògnites té 4 - 3 = 1 grau de llibertat. 18. c) El sistema és incompatible. Aquesta fila tradueix l'equació 0 = b amb b no nul, que és una contradicció sense solució. 19. b) Reassignar la posició de les variables associades. Cada columna correspon a una incògnita concreta; en moure columnes s'ha de reordenar el vector d'incògnites. 20.

a) Quan rang(A) és inferior a rang(A"B). El sistema no té solució si i només si rang(A) < rang(A"B). 21. Perquè la màquina treballa amb un nombre limitat de dígits; si divideix per un nombre diminut, el resultat gegant fa que la suma absorbeixi i elimini els altres nombres de l'equació. X 1 X 2 X + 1 α(X 2 X ) 1 α λ = 0 rang(A) = rang(A B) = n Sistemes Lineals, Gauss i Factorització LU — Àlgebra UdG 34 22. Perquè produeix multiplicadors molt grans. En sumar-los a altres files amb aritmètica de precisió finita, els coeficients originals queden eclipsats i s'esborra la informació que contenien. 23. Que depèn de les unitats o factors d'escala de cada fila: multiplicar una equació per…