Métodos para matrices especiales. Descomposición de Cholesky MAT-251

Dr. Alonso Ramírez Manzanares CIMAT A.C. e-mail: [email protected] web: http://www.cimat.mx/~alram/met_num/

Dr. Joaquín Peña Acevedo CIMAT A.C. e-mail: [email protected]

Alonso Ramírez Manzanares Monday, August 31, 15

Métodos Numéricos

31.08.2015

Ventajas computacionales de las factorizaciones ... en segundos

Alonso Ramírez Manzanares Monday, August 31, 15

Métodos Numéricos

31.08.2015

Ventajas computacionales de las factorizaciones ... en segundos • ¿donde se usan factorizaciones en la vida real? ....

Alonso Ramírez Manzanares Monday, August 31, 15

Métodos Numéricos

31.08.2015

Ventajas computacionales de las factorizaciones ... en segundos • ¿donde se usan factorizaciones en la vida real? ....

Alonso Ramírez Manzanares Monday, August 31, 15

Métodos Numéricos

31.08.2015

Ventajas computacionales de las factorizaciones ... en segundos • ¿donde se usan factorizaciones en la vida real? ....

• Si hacemos una descomposición ( O(n3)), de tal forma que resolvemos el sistema Axi=bi para diferentes vectores bi.

Alonso Ramírez Manzanares Monday, August 31, 15

Métodos Numéricos

31.08.2015

Ventajas computacionales de las factorizaciones ... en segundos • ¿donde se usan factorizaciones en la vida real? ....

• Si hacemos una descomposición ( O(n3)), de tal forma que resolvemos el sistema Axi=bi para diferentes vectores bi. • Entonces la solución estará dada por el orden O(n2) en lugar de O(n3).

Alonso Ramírez Manzanares Monday, August 31, 15

Métodos Numéricos

31.08.2015

Ventajas computacionales de las factorizaciones ... en segundos • ¿donde se usan factorizaciones en la vida real? ....

• Si hacemos una descomposición ( O(n3)), de tal forma que resolvemos el sistema Axi=bi para diferentes vectores bi. • Entonces la solución estará dada por el orden O(n2) en lugar de O(n3). • Para sistemas de tamaño, digamos de 1000x1000

Alonso Ramírez Manzanares Monday, August 31, 15

Métodos Numéricos

31.08.2015

Ventajas computacionales de las factorizaciones ... en segundos • ¿donde se usan factorizaciones en la vida real? ....

• Si hacemos una descomposición ( O(n3)), de tal forma que resolvemos el sistema Axi=bi para diferentes vectores bi. • Entonces la solución estará dada por el orden O(n2) en lugar de O(n3). • Para sistemas de tamaño, digamos de 1000x1000 • 10002 = 1,000,000 = 0.001 * 1,000,000,000 = 0.001 * 1,0003

Alonso Ramírez Manzanares Monday, August 31, 15

Métodos Numéricos

31.08.2015

Matrices con diagonal estrictamente-dominante

Alonso Ramírez Manzanares Monday, August 31, 15

Métodos Numéricos

31.08.2015

2

Matrices con diagonal estrictamente-dominante • La definición de una matriz cuadrada estrictamente diagonal-dominante es la siguiente:

Alonso Ramírez Manzanares Monday, August 31, 15

Métodos Numéricos

31.08.2015

2

Matrices con diagonal estrictamente-dominante • La definición de una matriz cuadrada estrictamente diagonal-dominante es la siguiente:

Alonso Ramírez Manzanares Monday, August 31, 15

Métodos Numéricos

31.08.2015

2

Matrices con diagonal estrictamente-dominante • La definición de una matriz cuadrada estrictamente diagonal-dominante es la siguiente:

Alonso Ramírez Manzanares Monday, August 31, 15

Métodos Numéricos

31.08.2015

2

Matrices con diagonal estrictamente-dominante • La definición de una matriz cuadrada estrictamente diagonal-dominante es la siguiente:

• Nótese que dada una matriz estrictamente diagonal-dominante, su transpuesta no tiene por que serlo.

Alonso Ramírez Manzanares Monday, August 31, 15

Métodos Numéricos

31.08.2015

2

Matrices con diagonal estrictamente-dominante • La definición de una matriz cuadrada estrictamente diagonal-dominante es la siguiente:

• Nótese que dada una matriz estrictamente diagonal-dominante, su transpuesta no tiene por que serlo. • Una matriz estrictamente diagonal-dominante tiene inversa. Se puede aplicar eliminación Gaussiana sin necesidad de hacer intercambio de renglones, y los cálculos serán estables con respecto a los errores de redondeo. Alonso Ramírez Manzanares Monday, August 31, 15

Métodos Numéricos

31.08.2015

2

Una matriz estrictamente diagonal-dominante tiene inversa, demostración: • Prueba por contradicción: consideremos que es singular, entonces consideremos Ax=0, con solución x = (xi) que no es cero. Sea k un índice para el cual 0 < |xk| = max 1≤j≤n |xj|.

Alonso Ramírez Manzanares Monday, August 31, 15

Métodos Numéricos

31.08.2015

Una matriz estrictamente diagonal-dominante tiene inversa, demostración: • Prueba por contradicción: consideremos que es singular, entonces consideremos Ax=0, con solución x = (xi) que no es cero. Sea k un índice para el cual 0 < |xk| = max 1≤j≤n |xj|.

Alonso Ramírez Manzanares Monday, August 31, 15

Métodos Numéricos

31.08.2015

Matrices definidas positivas • Aquí trabajaremos con aquellas matrices cuadradas y simétricas tales que xTA x > 0 para todo vector x diferente de 0. Es decir que la matriz de tamaño 1x1 (escalar) resultante de la operación es positiva.

Alonso Ramírez Manzanares Monday, August 31, 15

Métodos Numéricos

31.08.2015

Matrices definidas positivas • Aquí trabajaremos con aquellas matrices cuadradas y simétricas tales que xTA x > 0 para todo vector x diferente de 0. • Ejemplo, una matriz positiva:

Alonso Ramírez Manzanares Monday, August 31, 15

Métodos Numéricos

31.08.2015

Matrices definidas positivas • Aquí trabajaremos con aquellas matrices cuadradas y simétricas tales que xTA x > 0 para todo vector x diferente de 0. • Ejemplo, una matriz positiva:

Alonso Ramírez Manzanares Monday, August 31, 15

Métodos Numéricos

31.08.2015

Matrices definidas positivas • Aquí trabajaremos con aquellas matrices cuadradas y simétricas tales que xTA x > 0 para todo vector x diferente de 0. • Ejemplo, una matriz positiva:

Alonso Ramírez Manzanares Monday, August 31, 15

Métodos Numéricos

31.08.2015

Matrices definidas positivas • Aquí trabajaremos con aquellas matrices cuadradas y simétricas tales que xTA x > 0 para todo vector x diferente de 0. • Ejemplo, una matriz positiva:

A esta forma se le llama forma cuadrática asociada a la matriz. Alonso Ramírez Manzanares Monday, August 31, 15

Métodos Numéricos

31.08.2015

Matrices definidas positivas • Una matriz no positiva pero que es definida positiva

Alonso Ramírez Manzanares Monday, August 31, 15

Métodos Numéricos

31.08.2015

Matrices definidas positivas • Una matriz no positiva pero que es definida positiva

Alonso Ramírez Manzanares Monday, August 31, 15

Métodos Numéricos

31.08.2015

Matrices definidas positivas • Una matriz no positiva pero que es definida positiva

La expresión solo puede ser cero cuando todos los xi son cero. Alonso Ramírez Manzanares Monday, August 31, 15

Métodos Numéricos

31.08.2015

Matrices definidas positivas • Las matrices positivas definidas aparecen mucho en problemas de CNyE, por ejemplo en las matrices de covarianza.

Alonso Ramírez Manzanares Monday, August 31, 15

Métodos Numéricos

31.08.2015

Matrices definida positiva

Alonso Ramírez Manzanares Monday, August 31, 15

Métodos Numéricos

31.08.2015

Matrices definida positiva • Propiedades de estas matrices:

Alonso Ramírez Manzanares Monday, August 31, 15

Métodos Numéricos

31.08.2015

Matrices definida positiva • Propiedades de estas matrices: • A es no singular.

Alonso Ramírez Manzanares Monday, August 31, 15

Métodos Numéricos

31.08.2015

Matrices definida positiva • Propiedades de estas matrices: • A es no singular. • Demostración por contradicción: Suponemos singularidad: Ax=0, para x diferente cero, entonces xTAx =0, lo cual contradice que A es definida positiva.

Alonso Ramírez Manzanares Monday, August 31, 15

Métodos Numéricos

31.08.2015

Matrices definida positiva • Propiedades de estas matrices: • A es no singular. • Demostración por contradicción: Suponemos singularidad: Ax=0, para x diferente cero, entonces xTAx =0, lo cual contradice que A es definida positiva. • aii > 0 para toda i=1,...,n, por lo tanto la traza es no negativa.

Alonso Ramírez Manzanares Monday, August 31, 15

Métodos Numéricos

31.08.2015

Matrices definida positiva • Propiedades de estas matrices: • A es no singular. • Demostración por contradicción: Suponemos singularidad: Ax=0, para x diferente cero, entonces xTAx =0, lo cual contradice que A es definida positiva. • aii > 0 para toda i=1,...,n, por lo tanto la traza es no negativa. • Demostración: Para una i cualquiera, definamos x = (xk) por xi = 1 y xj = 0, si j ≠ i. Entonces x ≠ 0, por lo que 0 < xTAx = aii.

Alonso Ramírez Manzanares Monday, August 31, 15

Métodos Numéricos

31.08.2015

Matrices definida positiva • Propiedades de estas matrices: • A es no singular. • Demostración por contradicción: Suponemos singularidad: Ax=0, para x diferente cero, entonces xTAx =0, lo cual contradice que A es definida positiva. • aii > 0 para toda i=1,...,n, por lo tanto la traza es no negativa. • Demostración: Para una i cualquiera, definamos x = (xk) por xi = 1 y xj = 0, si j ≠ i. Entonces x ≠ 0, por lo que 0 < xTAx = aii. • max i ≤ k,j ≤n |akj| ≤ max 1≤i≤n |aii|

Alonso Ramírez Manzanares Monday, August 31, 15

Métodos Numéricos

31.08.2015

Matrices definida positiva • Propiedades de estas matrices: • A es no singular. • Demostración por contradicción: Suponemos singularidad: Ax=0, para x diferente cero, entonces xTAx =0, lo cual contradice que A es definida positiva. • aii > 0 para toda i=1,...,n, por lo tanto la traza es no negativa. • Demostración: Para una i cualquiera, definamos x = (xk) por xi = 1 y xj = 0, si j ≠ i. Entonces x ≠ 0, por lo que 0 < xTAx = aii. • max i ≤ k,j ≤n |akj| ≤ max 1≤i≤n |aii| • Demostración: Tarea.

Alonso Ramírez Manzanares Monday, August 31, 15

Métodos Numéricos

31.08.2015

Matrices definida positiva • Propiedades de estas matrices: • A es no singular. • Demostración por contradicción: Suponemos singularidad: Ax=0, para x diferente cero, entonces xTAx =0, lo cual contradice que A es definida positiva. • aii > 0 para toda i=1,...,n, por lo tanto la traza es no negativa. • Demostración: Para una i cualquiera, definamos x = (xk) por xi = 1 y xj = 0, si j ≠ i. Entonces x ≠ 0, por lo que 0 < xTAx = aii. • max i ≤ k,j ≤n |akj| ≤ max 1≤i≤n |aii| • Demostración: Tarea. • aij2 < aiiajj para cada i ≠ j

Alonso Ramírez Manzanares Monday, August 31, 15

Métodos Numéricos

31.08.2015

Matrices definida positiva • Propiedades de estas matrices: • A es no singular. • Demostración por contradicción: Suponemos singularidad: Ax=0, para x diferente cero, entonces xTAx =0, lo cual contradice que A es definida positiva. • aii > 0 para toda i=1,...,n, por lo tanto la traza es no negativa. • Demostración: Para una i cualquiera, definamos x = (xk) por xi = 1 y xj = 0, si j ≠ i. Entonces x ≠ 0, por lo que 0 < xTAx = aii. • max i ≤ k,j ≤n |akj| ≤ max 1≤i≤n |aii| • Demostración: Tarea. • aij2 < aiiajj para cada i ≠ j • Demostración: Tarea. Alonso Ramírez Manzanares Monday, August 31, 15

Métodos Numéricos

31.08.2015

Matrices definida positiva • Propiedades de estas matrices (2): • Se puede aplicar eliminación Gaussiana si necesidad de intercambio de renglones. • Se puede factorizar en la forma L LT , donde L es una matriz triangular inferior con entradas positivas en la diagonal. • Se puede factorizar en la forma LDLT, donde L es una matriz triangular inferior con unos en la diagonal y D es una matriz diagonal con entradas positivas.

Alonso Ramírez Manzanares Monday, August 31, 15

Métodos Numéricos

31.08.2015

Descomposición (factorización) de Cholesky • André-Louis Cholesky (15 de Octubre de 1875 - 31 de Agosto de 1918). • Se factoriza A = L LT , donde L es una matriz triangular inferior con entradas positivas en la diagonal. • La descomposición es única,

Alonso Ramírez Manzanares Monday, August 31, 15

Métodos Numéricos

31.08.2015

Descomposición (factorización) de Cholesky • André-Louis Cholesky (15 de Octubre de 1875 - 31 de Agosto de 1918). • Se factoriza A = L LT , donde L es una matriz triangular inferior con entradas positivas en la diagonal. • La descomposición es única,

Alonso Ramírez Manzanares Monday, August 31, 15

Métodos Numéricos

31.08.2015

Descomposición (factorización) de Cholesky • Algoritmo

=

Alonso Ramírez Manzanares Monday, August 31, 15

... es simétrica...

Métodos Numéricos

31.08.2015

Descomposición (factorización) de Cholesky =

Alonso Ramírez Manzanares Monday, August 31, 15

... es simétrica...

Métodos Numéricos

31.08.2015

Descomposición (factorización) de Cholesky Es positivo

=

Alonso Ramírez Manzanares Monday, August 31, 15

... es simétrica...

Métodos Numéricos

31.08.2015

Descomposición (factorización) de Cholesky Es positivo

=

... es simétrica...

• De tal manera, que procedemos al cálculo columna por columna, y las entradas de L quedan como:

Alonso Ramírez Manzanares Monday, August 31, 15

Métodos Numéricos

31.08.2015

Descomposición (factorización) de Cholesky Es positivo

=

... es simétrica...

• De tal manera, que procedemos al cálculo columna por columna, y las entradas de L quedan como:

Alonso Ramírez Manzanares Monday, August 31, 15

Métodos Numéricos

31.08.2015

Descomposición (factorización) de Cholesky Es positivo

=

... es simétrica...

• De tal manera, que procedemos al cálculo columna por columna, y las entradas de L quedan como:

Alonso Ramírez Manzanares Monday, August 31, 15

Métodos Numéricos

31.08.2015

Descomposición (factorización) de Cholesky Es positivo

... es simétrica...

=

• De tal manera, que procedemos al cálculo columna por columna, y las entradas de L quedan como:

para i > j Alonso Ramírez Manzanares Monday, August 31, 15

Métodos Numéricos

31.08.2015

Descomposición (factorización) de Cholesky Es positivo

... es simétrica...

=

• De tal manera, que procedemos al cálculo columna por columna, y las entradas de L quedan como:

para i > j Alonso Ramírez Manzanares Monday, August 31, 15

Métodos Numéricos

31.08.2015

Una forma alternativa que evita calcular raices cuadradas

Alonso Ramírez Manzanares Monday, August 31, 15

Métodos Numéricos

31.08.2015

Una forma alternativa que evita calcular raices cuadradas

• De tal manera que L es una matriz triangular inferior con unos en la diagonal y D es una matriz diagonal con entradas positivas. • multiplicando las matrices tenemos

Alonso Ramírez Manzanares Monday, August 31, 15

Métodos Numéricos

31.08.2015

Una forma alternativa que evita calcular raices cuadradas

• De tal manera que L es una matriz triangular inferior con unos en la diagonal y D es una matriz diagonal con entradas positivas. • multiplicando las matrices tenemos

... es simétrica...

Alonso Ramírez Manzanares Monday, August 31, 15

Métodos Numéricos

31.08.2015

Una forma alternativa que evita calcular raices cuadradas

Alonso Ramírez Manzanares Monday, August 31, 15

Métodos Numéricos

31.08.2015

Una forma alternativa que evita calcular raices cuadradas

• Quedando las entradas definidas como:

Alonso Ramírez Manzanares Monday, August 31, 15

Métodos Numéricos

31.08.2015

Una forma alternativa que evita calcular raices cuadradas

• Quedando las entradas definidas como:

Alonso Ramírez Manzanares Monday, August 31, 15

Métodos Numéricos

31.08.2015

Una forma alternativa que evita calcular raices cuadradas

• Quedando las entradas definidas como:

De tal forma que, de nuevo, hacemos el cálculo columna por columna. Alonso Ramírez Manzanares Monday, August 31, 15

Métodos Numéricos

31.08.2015

Relación entre las 2 factorizaciones

• Las 2 factorizaciones LLT y LDLT (nótese que son diferentes L’s) se relacionan así:

Alonso Ramírez Manzanares Monday, August 31, 15

Métodos Numéricos

31.08.2015

Relación entre las 2 factorizaciones

• Las 2 factorizaciones LLT y LDLT (nótese que son diferentes L’s) se relacionan así:

Alonso Ramírez Manzanares Monday, August 31, 15

Métodos Numéricos

31.08.2015

Solución del SEL dada la factorización LLT

Alonso Ramírez Manzanares Monday, August 31, 15

Métodos Numéricos

31.08.2015

Solución del SEL dada la factorización LLT • Si tenemos Ax=b entonces usamos LLTx=b, • primero hacemos y = LTx y solucionamos Ly=b con sustitución hacia adelante, con:

• Luego solucionamos para x el sistema LTx = y con sustitución hacia atrás.

Alonso Ramírez Manzanares Monday, August 31, 15

Métodos Numéricos

31.08.2015

Solución del SEL dada la factorización LLT • Si tenemos Ax=b entonces usamos LLTx=b, • primero hacemos y = LTx y solucionamos Ly=b con sustitución hacia adelante, con:

• Luego solucionamos para x el sistema LTx = y con sustitución hacia atrás.

Alonso Ramírez Manzanares Monday, August 31, 15

Métodos Numéricos

31.08.2015

Solución del SEL dada la factorización LDLT

Alonso Ramírez Manzanares Monday, August 31, 15

Métodos Numéricos

31.08.2015

Solución del SEL dada la factorización LDLT • Si tenemos el sistema A x=b como LDLT x = b haciendo y = DLT x, y resolviendo para y el SEL Ly=b con sustitución hacia adelante.

Alonso Ramírez Manzanares Monday, August 31, 15

Métodos Numéricos

31.08.2015

Solución del SEL dada la factorización LDLT • Si tenemos el sistema A x=b como LDLT x = b haciendo y = DLT x, y resolviendo para y el SEL Ly=b con sustitución hacia adelante. • Luego usamos z = LTx de tal forma que resolvemos para z el SEL Dz=y. Pero D es diagonal, por lo que esto es muy fácil:

Alonso Ramírez Manzanares Monday, August 31, 15

Métodos Numéricos

31.08.2015

Solución del SEL dada la factorización LDLT • Si tenemos el sistema A x=b como LDLT x = b haciendo y = DLT x, y resolviendo para y el SEL Ly=b con sustitución hacia adelante. • Luego usamos z = LTx de tal forma que resolvemos para z el SEL Dz=y. Pero D es diagonal, por lo que esto es muy fácil:

Alonso Ramírez Manzanares Monday, August 31, 15

Métodos Numéricos

31.08.2015

Solución del SEL dada la factorización LDLT • Si tenemos el sistema A x=b como LDLT x = b haciendo y = DLT x, y resolviendo para y el SEL Ly=b con sustitución hacia adelante. • Luego usamos z = LTx de tal forma que resolvemos para z el SEL Dz=y. Pero D es diagonal, por lo que esto es muy fácil:

• Finalmente resolvemos LTx = z para x con sustitución hacia atrás y TERMINAMOS.

Alonso Ramírez Manzanares Monday, August 31, 15

Métodos Numéricos

31.08.2015

Solución del SEL dada la factorización LDLT • Si tenemos el sistema A x=b como LDLT x = b haciendo y = DLT x, y resolviendo para y el SEL Ly=b con sustitución hacia adelante. • Luego usamos z = LTx de tal forma que resolvemos para z el SEL Dz=y. Pero D es diagonal, por lo que esto es muy fácil:

• Finalmente resolvemos LTx = z para x con sustitución hacia atrás y TERMINAMOS.

Alonso Ramírez Manzanares Monday, August 31, 15

Métodos Numéricos

31.08.2015

Alonso Ramírez Manzanares Monday, August 31, 15

Métodos Numéricos

31.08.2015

Matrices bandadas • Una matriz de tamaño n x n se dice que es bandada si existen los numeros p y q enteros 1 < p , q < n, tal que aij = 0 para todo p ≤ j- i ó q ≤ i - j • p denota el número de diagonales arriba de la diagonal principal, incluyéndola. • q denota el número de diagonales abajo de la diagonal principal, incluyéndola. • Ejemplo con p = 3 y q = 2.

• El numero de diagonales es p+q-1.

Alonso Ramírez Manzanares Monday, August 31, 15

Métodos Numéricos

31.08.2015

Matrices tridiagonales • Un grupo muy famoso son las tridiagonales, es decir con p=q=2 •

Alonso Ramírez Manzanares Monday, August 31, 15

Métodos Numéricos

31.08.2015