En muchas aplicaciones de ingeniería, cuando se resuelve $Ax = b$ la matriz $A \in \mathbb{R}^{N \times N}$ no cambia, mientras que el vector de la derecha $b$ sigue cambiando.
Un ejemplo típico es cuando se resuelve una ecuación diferencial parcial para diferentes funciones de forzamiento. Para estas diferentes funciones de forzamiento, el mallado suele ser el mismo. La matriz $A$ sólo depende de los parámetros de la malla y, por lo tanto, no cambia para las diferentes funciones de forzamiento. Sin embargo, el vector del lado derecho $b$ cambios para cada una de las funciones de forzamiento.
Otro ejemplo es cuando se resuelve un problema dependiente del tiempo, en el que las incógnitas evolucionan con el tiempo. También en este caso, si el paso del tiempo es constante a través de diferentes instantes de tiempo, entonces de nuevo la matriz $A$ permanece sin cambios y el único vector del lado derecho $b$ cambia en cada paso de tiempo.
La idea clave para resolver utilizando el $LU$ (para el caso, cualquier factorización) es desacoplar la fase de factorización (generalmente costosa desde el punto de vista computacional) del actual fase de resolución. La fase de factorización sólo necesita la matriz $A$ , mientras que el actual La fase de resolución hace uso de la forma factorizada de $A$ y el lado derecho para resolver el sistema lineal. Por lo tanto, una vez que tenemos la factorización, podemos hacer uso de la forma factorizada de $A$ para resolver los diferentes lados derechos con un coste computacional relativamente moderado.
El coste de la factorización de la matriz $A$ en $LU$ es $\mathcal{O}(N^3)$ . Una vez que se tiene esta factorización, el coste de resolver, es decir, el coste de resolver $LUx = b$ es sólo $\mathcal{O}(N^2)$ ya que el coste de resolver un sistema triangular escala como $\mathcal{O}(N^2)$ .
(Tenga en cuenta que para resolver $LUx = b$ , primero se resuelve $Ly = b$ y luego $Ux = y$ . Resolver $Ly = b$ y $Ux=y$ costes $\mathcal{O}(N^2).$ )
Por lo tanto, si usted tiene ' $r$ ' vectores del lado derecho $\{b_1,b_2,\ldots,b_r\}$ Una vez que tenga el $LU$ factorización de la matriz $A$ el coste total para resolver $$Ax_1 = b_1, Ax_2 = b_2 , \ldots, Ax_r = b_r$$ escalas como $\mathcal{O}(N^3 + rN^2)$ .
Por otro lado, si se hace la eliminación de Gauss por separado para cada vector del lado derecho $b_j$ entonces el coste total escala como $\mathcal{O}(rN^3)$ ya que cada eliminación de Gauss cuesta independientemente $\mathcal{O}(N^3)$ .
Sin embargo, cuando la gente dice eliminación de Gauss, suele referirse a $LU$ descomposición y no al método de resolver cada lado derecho de forma completamente independiente.
