![Page 1: Factorización LU - CIMATjoaquin/cursos/mat251/clases/clase04b.pdf · Matrices triangulares inferiores(I) Consideremos el sistema Lx = b, donde L = 2 6 6 6 6 4 l11 0 0 l21 l22 0 ln1](https://reader033.vdocumento.com/reader033/viewer/2022060802/6086482f20b0962f1e77714e/html5/thumbnails/1.jpg)
Clase No. 4 (Parte 2):
Factorización LUMAT–251 Dr. Alonso Ramírez Manzanares
Depto. de MatemáticasUniv. de Guanajuatoe-mail: [email protected]: http://www.cimat.mx/salram/met_num/
Dr. Joaquín Peña AcevedoCIMAT A.C.e-mail: [email protected]
Joaquín Peña (CIMAT) Métodos Numéricos (MAT–251) 26.08.2013 1 / 10
![Page 2: Factorización LU - CIMATjoaquin/cursos/mat251/clases/clase04b.pdf · Matrices triangulares inferiores(I) Consideremos el sistema Lx = b, donde L = 2 6 6 6 6 4 l11 0 0 l21 l22 0 ln1](https://reader033.vdocumento.com/reader033/viewer/2022060802/6086482f20b0962f1e77714e/html5/thumbnails/2.jpg)
Matrices triangulares inferiores (I)
Consideremos el sistema
Lx = b, donde L =
l11 0 · · · 0l21 l22 · · · 0...
... · · ·...
ln1 ln2 · · · lnn
Proposición.
Sea L una matriz triangular inferior. El sistema Lx = b tiene solución si y sólosi los elementos de su diagonal son diferentes de cero.
Notemos que
l11x1 = b1l21x1 + l22x2 = b2
... =...
ln1x1 + ln2x2 + · · ·+ lnnxn = bn
Joaquín Peña (CIMAT) Métodos Numéricos (MAT–251) 26.08.2013 2 / 10
![Page 3: Factorización LU - CIMATjoaquin/cursos/mat251/clases/clase04b.pdf · Matrices triangulares inferiores(I) Consideremos el sistema Lx = b, donde L = 2 6 6 6 6 4 l11 0 0 l21 l22 0 ln1](https://reader033.vdocumento.com/reader033/viewer/2022060802/6086482f20b0962f1e77714e/html5/thumbnails/3.jpg)
Matrices triangulares inferiores (II)
Podemos calcular
x1 =b1
l11
Supongamos que tenemos calculadas x1,x2, ...,xi−1. Entonces
xi =1
lii
bi −
i−1∑
j=1
lijxj
• Como el sistema Lx = b tiene solución única para cada b, la matriz L esno singular.
• Al método de solución utilizado se le llama sustitución hacia adelante.
Joaquín Peña (CIMAT) Métodos Numéricos (MAT–251) 26.08.2013 3 / 10
![Page 4: Factorización LU - CIMATjoaquin/cursos/mat251/clases/clase04b.pdf · Matrices triangulares inferiores(I) Consideremos el sistema Lx = b, donde L = 2 6 6 6 6 4 l11 0 0 l21 l22 0 ln1](https://reader033.vdocumento.com/reader033/viewer/2022060802/6086482f20b0962f1e77714e/html5/thumbnails/4.jpg)
Eliminación Gaussiana vista como producto dematrices (I)
Sea A la matriz
A =
a11 a12 a13 a14a21 a22 a23 a24a31 a32 a33 a34a41 a42 a43 a44
,
y definamos
L1 =
1 0 0 0−l21 1 0 0−l31 0 1 0−l41 0 0 1
, li1 =ai1
a11, i = 2,3,4.
Entonces
L1A =
a11 a12 a13 a140 a′22 a′23 a′240 a′32 a′33 a′340 a′42 a′43 a′44
Joaquín Peña (CIMAT) Métodos Numéricos (MAT–251) 26.08.2013 4 / 10
![Page 5: Factorización LU - CIMATjoaquin/cursos/mat251/clases/clase04b.pdf · Matrices triangulares inferiores(I) Consideremos el sistema Lx = b, donde L = 2 6 6 6 6 4 l11 0 0 l21 l22 0 ln1](https://reader033.vdocumento.com/reader033/viewer/2022060802/6086482f20b0962f1e77714e/html5/thumbnails/5.jpg)
Eliminación Gaussiana vista como producto dematrices (II)Si definimos
L2 =
1 0 0 00 1 0 00 −l32 1 00 −l42 0 1
, li2 =a′i2a′22
, i = 3,4.
entonces L2L1A =
a11 a12 a13 a140 a′22 a′23 a′24
0 0 a′′33 a′′34
0 0 a′′43 a′′44
L3 =
1 0 0 00 1 0 00 0 1 00 0 −l43 1
=⇒ L3L2L1A =
a11 a12 a13 a140 a′22 a′23 a′24
0 0 a′′33 a′′34
0 0 0 a′′′44
con l43 = a′′43/a′′33.
Joaquín Peña (CIMAT) Métodos Numéricos (MAT–251) 26.08.2013 5 / 10
![Page 6: Factorización LU - CIMATjoaquin/cursos/mat251/clases/clase04b.pdf · Matrices triangulares inferiores(I) Consideremos el sistema Lx = b, donde L = 2 6 6 6 6 4 l11 0 0 l21 l22 0 ln1](https://reader033.vdocumento.com/reader033/viewer/2022060802/6086482f20b0962f1e77714e/html5/thumbnails/6.jpg)
Eliminación Gaussiana vista como producto dematrices (III)
• A las matrices Li se les llama matrices triangulares inferioreselementales.
• El proceso de eliminación Gaussiana es una reducción a una formatriangular por medio de matrices triangulares inferiores elementales.
En general, tenemos que
Ln−1 · · ·L2L1A =U
donde U es una matriz triangular superior.
Joaquín Peña (CIMAT) Métodos Numéricos (MAT–251) 26.08.2013 6 / 10
![Page 7: Factorización LU - CIMATjoaquin/cursos/mat251/clases/clase04b.pdf · Matrices triangulares inferiores(I) Consideremos el sistema Lx = b, donde L = 2 6 6 6 6 4 l11 0 0 l21 l22 0 ln1](https://reader033.vdocumento.com/reader033/viewer/2022060802/6086482f20b0962f1e77714e/html5/thumbnails/7.jpg)
Factorización LU
• Como los elementos de la diagonal de cada matriz Li es diferente decero, Li es no singular.
• El producto Ln−1 · · ·L2L1 es no singular, de modo que
Ln−1 · · ·L2L1 = L−1
• Tenemos entonces que
L−1A =U =⇒ A = LU
• La matriz L es triangular inferior,
L =
1 0 · · · 0 0l21 1 · · · 0 0l31 l32 · · · 0 0...
... · · ·...
...ln−1,1 ln−1,2 · · · 1 0ln1 ln2 · · · ln,n−1 1
Joaquín Peña (CIMAT) Métodos Numéricos (MAT–251) 26.08.2013 7 / 10
![Page 8: Factorización LU - CIMATjoaquin/cursos/mat251/clases/clase04b.pdf · Matrices triangulares inferiores(I) Consideremos el sistema Lx = b, donde L = 2 6 6 6 6 4 l11 0 0 l21 l22 0 ln1](https://reader033.vdocumento.com/reader033/viewer/2022060802/6086482f20b0962f1e77714e/html5/thumbnails/8.jpg)
Factorización LU
• Como los elementos de la diagonal de cada matriz Li es diferente decero, Li es no singular.
• El producto Ln−1 · · ·L2L1 es no singular, de modo que
Ln−1 · · ·L2L1 = L−1
• Tenemos entonces que
L−1A =U =⇒ A = LU
• La matriz L es triangular inferior,
L =
1 0 · · · 0 0l21 1 · · · 0 0l31 l32 · · · 0 0...
... · · ·...
...ln−1,1 ln−1,2 · · · 1 0ln1 ln2 · · · ln,n−1 1
Joaquín Peña (CIMAT) Métodos Numéricos (MAT–251) 26.08.2013 7 / 10
![Page 9: Factorización LU - CIMATjoaquin/cursos/mat251/clases/clase04b.pdf · Matrices triangulares inferiores(I) Consideremos el sistema Lx = b, donde L = 2 6 6 6 6 4 l11 0 0 l21 l22 0 ln1](https://reader033.vdocumento.com/reader033/viewer/2022060802/6086482f20b0962f1e77714e/html5/thumbnails/9.jpg)
Factorización LU
• Como los elementos de la diagonal de cada matriz Li es diferente decero, Li es no singular.
• El producto Ln−1 · · ·L2L1 es no singular, de modo que
Ln−1 · · ·L2L1 = L−1
• Tenemos entonces que
L−1A =U =⇒ A = LU
• La matriz L es triangular inferior,
L =
1 0 · · · 0 0l21 1 · · · 0 0l31 l32 · · · 0 0...
... · · ·...
...ln−1,1 ln−1,2 · · · 1 0ln1 ln2 · · · ln,n−1 1
Joaquín Peña (CIMAT) Métodos Numéricos (MAT–251) 26.08.2013 7 / 10
![Page 10: Factorización LU - CIMATjoaquin/cursos/mat251/clases/clase04b.pdf · Matrices triangulares inferiores(I) Consideremos el sistema Lx = b, donde L = 2 6 6 6 6 4 l11 0 0 l21 l22 0 ln1](https://reader033.vdocumento.com/reader033/viewer/2022060802/6086482f20b0962f1e77714e/html5/thumbnails/10.jpg)
Factorización LU
• Como los elementos de la diagonal de cada matriz Li es diferente decero, Li es no singular.
• El producto Ln−1 · · ·L2L1 es no singular, de modo que
Ln−1 · · ·L2L1 = L−1
• Tenemos entonces que
L−1A =U =⇒ A = LU
• La matriz L es triangular inferior,
L =
1 0 · · · 0 0l21 1 · · · 0 0l31 l32 · · · 0 0...
... · · ·...
...ln−1,1 ln−1,2 · · · 1 0ln1 ln2 · · · ln,n−1 1
Joaquín Peña (CIMAT) Métodos Numéricos (MAT–251) 26.08.2013 7 / 10
![Page 11: Factorización LU - CIMATjoaquin/cursos/mat251/clases/clase04b.pdf · Matrices triangulares inferiores(I) Consideremos el sistema Lx = b, donde L = 2 6 6 6 6 4 l11 0 0 l21 l22 0 ln1](https://reader033.vdocumento.com/reader033/viewer/2022060802/6086482f20b0962f1e77714e/html5/thumbnails/11.jpg)
Solución del sistema lineal de ecuaciones
De esta forma, el método de eliminación Gaussiana calcula ladescomposición LU de la matriz.
Supongamos que A tiene una factorización LU. Entonces para resolver
Ax = b
hacemos lo siguiente. Tenemos que
LUx = b
Definimos y =Ux y entonces resolvemos
Ly = b (usando sustitución hacia atrás)
Ux = y (usando sustitución hacia adelante)
Joaquín Peña (CIMAT) Métodos Numéricos (MAT–251) 26.08.2013 8 / 10
![Page 12: Factorización LU - CIMATjoaquin/cursos/mat251/clases/clase04b.pdf · Matrices triangulares inferiores(I) Consideremos el sistema Lx = b, donde L = 2 6 6 6 6 4 l11 0 0 l21 l22 0 ln1](https://reader033.vdocumento.com/reader033/viewer/2022060802/6086482f20b0962f1e77714e/html5/thumbnails/12.jpg)
Solución del sistema lineal de ecuaciones
De esta forma, el método de eliminación Gaussiana calcula ladescomposición LU de la matriz.
Supongamos que A tiene una factorización LU. Entonces para resolver
Ax = b
hacemos lo siguiente. Tenemos que
LUx = b
Definimos y =Ux y entonces resolvemos
Ly = b (usando sustitución hacia atrás)
Ux = y (usando sustitución hacia adelante)
Joaquín Peña (CIMAT) Métodos Numéricos (MAT–251) 26.08.2013 8 / 10
![Page 13: Factorización LU - CIMATjoaquin/cursos/mat251/clases/clase04b.pdf · Matrices triangulares inferiores(I) Consideremos el sistema Lx = b, donde L = 2 6 6 6 6 4 l11 0 0 l21 l22 0 ln1](https://reader033.vdocumento.com/reader033/viewer/2022060802/6086482f20b0962f1e77714e/html5/thumbnails/13.jpg)
Sobre la unicidad de la factorización LU
• Hay que notar que si D es una matriz diagonal no singular, entonces
A = LU = LDD−1U = (LD)(D−1U)
LD es triangular inferior y D−1U es triangular superior, por lo quepodemos tener varias descomposiciones.
• Hacemos el convenio de que por factorización LU nos referimos a lafactorización en la que la matriz L es triangular inferior y que loselementos de su diagonal son iguales a 1.
Proposición.
Si A es no singular y tiene una factorización LU, entonces la factorización esúnica.
Joaquín Peña (CIMAT) Métodos Numéricos (MAT–251) 26.08.2013 9 / 10
![Page 14: Factorización LU - CIMATjoaquin/cursos/mat251/clases/clase04b.pdf · Matrices triangulares inferiores(I) Consideremos el sistema Lx = b, donde L = 2 6 6 6 6 4 l11 0 0 l21 l22 0 ln1](https://reader033.vdocumento.com/reader033/viewer/2022060802/6086482f20b0962f1e77714e/html5/thumbnails/14.jpg)
Sobre la unicidad de la factorización LU
• Hay que notar que si D es una matriz diagonal no singular, entonces
A = LU = LDD−1U = (LD)(D−1U)
LD es triangular inferior y D−1U es triangular superior, por lo quepodemos tener varias descomposiciones.
• Hacemos el convenio de que por factorización LU nos referimos a lafactorización en la que la matriz L es triangular inferior y que loselementos de su diagonal son iguales a 1.
Proposición.
Si A es no singular y tiene una factorización LU, entonces la factorización esúnica.
Joaquín Peña (CIMAT) Métodos Numéricos (MAT–251) 26.08.2013 9 / 10
![Page 15: Factorización LU - CIMATjoaquin/cursos/mat251/clases/clase04b.pdf · Matrices triangulares inferiores(I) Consideremos el sistema Lx = b, donde L = 2 6 6 6 6 4 l11 0 0 l21 l22 0 ln1](https://reader033.vdocumento.com/reader033/viewer/2022060802/6086482f20b0962f1e77714e/html5/thumbnails/15.jpg)
Sobre la unicidad de la factorización LU
• Hay que notar que si D es una matriz diagonal no singular, entonces
A = LU = LDD−1U = (LD)(D−1U)
LD es triangular inferior y D−1U es triangular superior, por lo quepodemos tener varias descomposiciones.
• Hacemos el convenio de que por factorización LU nos referimos a lafactorización en la que la matriz L es triangular inferior y que loselementos de su diagonal son iguales a 1.
Proposición.
Si A es no singular y tiene una factorización LU, entonces la factorización esúnica.
Joaquín Peña (CIMAT) Métodos Numéricos (MAT–251) 26.08.2013 9 / 10
![Page 16: Factorización LU - CIMATjoaquin/cursos/mat251/clases/clase04b.pdf · Matrices triangulares inferiores(I) Consideremos el sistema Lx = b, donde L = 2 6 6 6 6 4 l11 0 0 l21 l22 0 ln1](https://reader033.vdocumento.com/reader033/viewer/2022060802/6086482f20b0962f1e77714e/html5/thumbnails/16.jpg)
Sobre la unicidad de la factorización LU
• Hay que notar que si D es una matriz diagonal no singular, entonces
A = LU = LDD−1U = (LD)(D−1U)
LD es triangular inferior y D−1U es triangular superior, por lo quepodemos tener varias descomposiciones.
• Hacemos el convenio de que por factorización LU nos referimos a lafactorización en la que la matriz L es triangular inferior y que loselementos de su diagonal son iguales a 1.
Proposición.
Si A es no singular y tiene una factorización LU, entonces la factorización esúnica.
Joaquín Peña (CIMAT) Métodos Numéricos (MAT–251) 26.08.2013 9 / 10
![Page 17: Factorización LU - CIMATjoaquin/cursos/mat251/clases/clase04b.pdf · Matrices triangulares inferiores(I) Consideremos el sistema Lx = b, donde L = 2 6 6 6 6 4 l11 0 0 l21 l22 0 ln1](https://reader033.vdocumento.com/reader033/viewer/2022060802/6086482f20b0962f1e77714e/html5/thumbnails/17.jpg)
Existencia de la factorización LU
Aun cuando A sea no singular, la matriz podría no tener una factorizaciónLU. Por ejemplo,
A =
�
0 11 0
�
Joaquín Peña (CIMAT) Métodos Numéricos (MAT–251) 26.08.2013 10 / 10