Catedra 06

Metodos de resolucion de ecuaciones lineales.


In [1]:
import scipy as sp
import scipy.linalg as alg

Algebra Lineal

$$ \begin{array}{ccc} a_{11}x_{1}+a_{12}x_{2}+\ldots+a_{1n}x_{n} & = & b_{1} \\ a_{21}x_{1}+a_{22}x_{2}+\ldots+a_{2n}x_{n} & = & b_{2} \\ & \vdots & \\ a_{n1}x_{1}+a_{n2}x_{2}+\ldots+a_{nn}x_{n} & = & b_{n} \\ \leftrightarrow & & \\ A\vec{X} = \vec{b} \end{array} $$$$ A = \left[\begin{array}{ccc} a_{11} & \dots & a_{1n} \\ \vdots & \ddots & \vdots \\ a_{n1} & \dots & a_{nn} \end{array}\right] $$

Para invertir la matriz $A$

$$ \begin{array}{c} A\vec{X} = \vec{b}\quad / A^{-1}\cdot \\ \vec{X} = A^{-1}\cdot\vec{b} \end{array} $$

Con $\vec{X}$ las incognitas.

Eliminacion de Gauss

Toma ventaja de cambios que se pueden hacer sin alterar el sistema.

  • Multiplicar una ecuacion (fila) por una constante $\lambda$.
  • Cambiar el orden de las ecuaciones.
  • Sumar dos ecuaciones (filas) multiplicadas por constante

Objetivo: transformar el sistema de ecuaciones en:

$$ \left[\begin{array}{cccc} 1 & a'_{12}& \ldots & a'_{1n} \\ 0 & 1 & \ldots & \vdots \\ 0 & 0 & \ddots & \vdots \\ 0 & 0 & 0 & 1 \end{array}\right] \cdot \left[\begin{array}{c} x_{1} \\ x_{2} \\ \vdots \\ x_{n} \end{array}\right] = \left[\begin{array}{c} b'_{1} \\ b'_{2} \\ \vdots \\ b'_{n} \end{array}\right] $$

Luego de transformar $A$ en triangular. $$ \begin{array}{ccccc} &x_{1}+ & a'_{12}x_{2}+\ldots+a'_{1n}x_{n} & = & b'_{1} \\ && x_{2}+a'_{23}x_{3} + \ldots + a'_{2n}x_{n} & = & b'_{2} \\ && \vdots & & & \\ & & x_{n} & = & b'_{n} \end{array} $$

Descomposicion LU o PLU

Idea: transformar $A\vec{X}=\vec{b}$ en dos problemas con matriz triangular.

$$A = L\cdot U$$

$L = $ lower, triangular inferior; $U = $ upper, triangular superior. Asi $$A\vec{X} = LU\vec{X} = \vec{b}$$ $$L\vec{Y} = \vec{b}$$

Nota: La descomposicion $LU$ no es unica. Por lo general, ademas se impone $l_{kk} = 1$ o $u_{kk} = 1$

Mas general es la descomposicion $A=PLU$, en donde $P$ es una matriz de permutaciones.

Optimizaciones tipicas:

  • A es tri-diagonal (o multi-diagonal).
  • A tiene pocos elementos (sparce matrix).

Ejemplo:

Se resolvera el problema $A\vec{X} = \vec{b}$ con $$ A = \left[\begin{array}{cccc} 0&1&1&-3 \\ -2&3&1&4 \\ 0&0&0&1 \\ 3&1&0&0 \end{array}\right] b = \left[\begin{array}{c} 3 \\ -2 \\ 5 \\ 1 \end{array}\right] $$


In [2]:
A = sp.array([[0,1,1,-3],
              [-2,3,1,4],
              [0,0,0, 1],
              [3,1,0,0]])

b = sp.array([3,-2,5,1])

alg.solve(A,b)


Out[2]:
array([  5.25, -14.75,  32.75,   5.  ])