4.4 Fatoração LU

---

Considere um sistema linear $Ax=b$, onde a matriz $A$ é densa⁵ . A fim de resolver o sistema, podemos fatorar a matriz $A$ como o produto de uma matriz $L$ triangular inferior e uma matriz $U$ triangular superior, ou seja, $A=LU$.

Sendo assim, o sistema pode ser reescrito da seguinte forma: $$\begin{array}{rcll}Ax& =& b& \text{(4.77)}\\ \left(LU\right)x& =& b& \text{(4.78)}\\ L\left(Ux\right)& =& b& \text{(4.79)}\\ Ly=b& \text{ e }& Ux=y& \text{(4.80)}\end{array}$$

Isto significa que, ao invés de resolvermos o sistema original, podemos resolver o sistema triangular inferior $Ly=b$ e, então, o sistema triangular superior $Ux=y$, o qual nos fornece a solução de $Ax=b$.

A matriz $U$ da fatoração⁶ $LU$ é a matriz obtida ao final do escalonamento da matriz $A$.

A matriz $L$ é construída a partir da matriz identidade $I$, ao longo do escalonamento de A. Os elementos da matriz $L$ são os múltiplos do primeiro elemento da linha de $A$ a ser zerado dividido pelo pivô acima na mesma coluna.

Por exemplo, para zerar o primeiro elemento da segunda linha de $A$, calculamos

$$L_{21}=A_{21}∕A_{11}$$

(4.81)

e fazemos

$$A_{2,:}\Leftarrow A_{2,:}-L_{21}{A}_{1,:}$$

(4.82)

Note que denotamos $A_{i,:}$ para nos referenciarmos a linha $i$ de $A$. Da mesma forma, se necessário usaremos $A_{:,j}$ para nos referenciarmos a coluna $j$ de $A$.

Para zerar o primeiro elemento da terceira linha de $A$, temos

$$L_{31}=A_{31}∕A_{11}$$

(4.83)

e fazemos

$$A_{3,:}\Leftarrow A_{3,:}-L_{31}{A}_{1,:}$$

(4.84)

até chegarmos ao último elemento da primeira coluna de $A$.

Repetimos o processo para as próximas colunas, escalonando a matriz $A$ e coletando os elementos $L_{ij}$ abaixo da diagonal⁷ .

Solução. Começamos fatorando a matriz $A$ dos coeficientes deste sistema: $$\begin{array}{rcll}A=\left[\begin{array}{ccc}\hfill 1\hfill & \hfill 1\hfill & \hfill 1\hfill \\ \hfill 2\hfill & \hfill 1\hfill & \hfill -1\hfill \\ \hfill 2\hfill & \hfill -1\hfill & \hfill 1\hfill \end{array}\right].& =& \underset{I_{3,3}}{\underbrace{\left[\begin{array}{ccc}\hfill 1\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 1\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill \end{array}\right]}}\underset{A}{\underbrace{\left[\begin{array}{ccc}\hfill 1\hfill & \hfill 1\hfill & \hfill 1\hfill \\ \hfill 2\hfill & \hfill 1\hfill & \hfill -1\hfill \\ \hfill 2\hfill & \hfill -1\hfill & \hfill 1\hfill \end{array}\right]}}& \text{(4.86)}\\ & =& \left[\begin{array}{ccc}\hfill 1\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 2\hfill & \hfill 1\hfill & \hfill 0\hfill \\ \hfill 2\hfill & \hfill 0\hfill & \hfill 1\hfill \end{array}\right]\left[\begin{array}{ccc}\hfill 1\hfill & \hfill 1\hfill & \hfill 1\hfill \\ \hfill 0\hfill & \hfill -1\hfill & \hfill -3\hfill \\ \hfill 0\hfill & \hfill -3\hfill & \hfill -1\hfill \end{array}\right]& \text{(4.87)}\\ & =& \underset{L}{\underbrace{\left[\begin{array}{ccc}\hfill 1\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 2\hfill & \hfill 1\hfill & \hfill 0\hfill \\ \hfill 2\hfill & \hfill 3\hfill & \hfill 1\hfill \end{array}\right]}}\underset{U}{\underbrace{\left[\begin{array}{ccc}\hfill 1\hfill & \hfill 1\hfill & \hfill 1\hfill \\ \hfill 0\hfill & \hfill -1\hfill & \hfill -3\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 8\hfill \end{array}\right]}}& \text{(4.88)}\\ & & & \text{(4.89)}\end{array}$$

Completada a fatoração LU, resolvemos, primeiramente, o sistema $Ly=b$:

$$\begin{array}{cc}\begin{array}{rl}{y}_1& =-2\\ 2y_1+y_2& =1\\ 2y_1+3y_2+y_3& =3\end{array}& \end{array}$$

(4.90)

o qual no fornece $y_1=-2$, $y_2=5$ e $y_3=-8$. Por fim, obtemos a solução resolvendo o sistema $Ux=y$:

$$\begin{array}{cc}\begin{array}{rl}{x}_1+x_2+x_3& =-2\\ -x_2-3x_3& =5\\ 8x_3& =-8\end{array}& \end{array}$$

(4.91)

o qual fornece $x_3=-1$, $x_2=-2$ e $x_1=1$.

4.4.1 Código Scilab: Fatoração LU

---

No Scilab, podemos implementar o algoritmo para fatoração $LU$ da seguinte forma:

Custo computacional

---

Podemos analisar o custo computacional, reduzindo o problema em problemas menores.

Na linha 4, iniciamos com $j=1$. Desta forma $i$ varia de $2$ até $n$ na linha 5.

A linha 6 terá sempre 1 flop.

A linha 7, com $j=1$ tem um bloco de tamanho 2:n contabilizando $n-1$ flops do produto e $n-1$ flops da subtração.

Nas linhas 6-8 são feitas $\left(2\left(n-1\right)+1\right)=2n-1$ flops independente do valor de $i$. Como $i$ varia de $2$ até $n$, teremos que o bloco é repetido $n-1$ vezes, ou seja, o custo das linhas 5-9 é

$$\left(n-1\right)\times \left(2\left(n-1\right)+1\right)=2{\left(n-1\right)}^2+\left(n-1\right)$$

(4.92)

Voltamos a linha 4 quando $j=2$. Das linhas 6-8 teremos $n-2$ flops (o bloco terá um elemento a menos) que será repetido $n-2$ vezes, pois i=3:n, ou seja,

$$\left(n-2\right)\times \left(2\left(n-2\right)+1\right)=2{\left(n-2\right)}^2+\left(n-2\right)$$

(4.93)

Para $j=3$, temos $2{\left(n-3\right)}^2+\left(n-3\right)$.

Para $j=n-2$, temos $2{\left(2\right)}^2+2$.

Finalmente, para $j=n-1$, temos $2\cdot 1^2+1$.

Somando todos esses custos, temos $$\begin{array}{rcll}\left(n-1\right)+2{\left(n-1\right)}^2& +& \left(n-2\right)+2{\left(n-2\right)}^2+...+\left(2\right)+2{\left(2\right)}^2+1+2\cdot 1& \text{(4.94)}\\ & =& \sum _{k=1}^{n-1}2k^2+k& \text{(4.95)}\\ & =& 2\sum _{k=1}^{n-1}{k}^2+\sum _{k=1}^{n-1}k& \text{(4.96)}\\ & =& 2\frac{\left(n-1\right)n\left(2n-1\right)}{6}+\frac{n\left(n-1\right)}{2}& \text{(4.97)}\\ & =& \frac{2n^3}{3}-\frac{n^2}{2}-\frac{n}{6}\text{ flops}.& \text{(4.98)}\end{array}$$

4.4.2 Custo computacional para resolver um sistema linear usando fatoração LU

---

Para calcularmos o custo computacional de um algoritmo completo, uma estratégia é separar o algoritmo em partes menores, mais fáceis de analisar.

Para resolver o sistema, devemos primeiro fatorar a matriz $A$ nas matrizes $L$ e $U$. Vimos que o custo é

$$\frac{2n^3}{3}-\frac{n^2}{2}-\frac{n}{6}\text{ flops}.$$

(4.99)

Depois devemos resolver os sistemas $Ly=b$ e $Ux=y$. O custo de resolver os dois sistemas é (devemos contar duas vezes)

$$2n^2\text{ flops}.$$

(4.100)

Somando esses $3$ custos, temos que o custo para resolver um sistema linear usando fatoração $LU$ é

$$\frac{2n^3}{3}+\frac{3n^2}{2}-\frac{n}{6}\text{ flops}.$$

(4.101)

Quando $n$ cresce, prevalessem os termos de mais alta ordem, ou seja,

$$\mathcal{O}\left(\frac{2n^3}{3}+\frac{3n^2}{2}-\frac{n}{6}\right)=\mathcal{O}\left(\frac{2n^3}{3}+\frac{3n^2}{2}\right)=\mathcal{O}\left(\frac{2n^3}{3}\right)$$

(4.102)

4.4.3 Custo para resolver m sistemas lineares

---

Devemos apenas multiplicar $m$ pelo custo de resolver um sistema linear usando fatoração $LU$, ou seja, o custo será

$$m\left(\frac{2n^3}{3}+\frac{3n^2}{2}-\frac{n}{6}\right)=\frac{2m{n}^3}{3}+\frac{3m{n}^2}{2}-\frac{mn}{6}$$

(4.103)

e com $m=n$ temos

$$\frac{2n^4}{3}+\frac{3n^3}{2}-\frac{n^2}{6}.$$

(4.104)

Porém, se estivermos resolvendo $n$ sistemas com a mesma matriz $A$ (e diferente lado direito $b$ para cada sistema) podemos fazer a fatoração LU uma única vez e contar apenas o custo de resolver os sistemas triangulares obtidos.

Custo para fatoração LU de $A$: $\frac{2n^3}{3}-\frac{n^2}{2}-\frac{n}{6}$.

Custo para resolver $m$ sistemas triangulares inferiores: $m{n}^2$.

Custo para resolver $m$ sistemas triangulares superiores: $m{n}^2$.

Somando esses custos obtemos

$$\frac{2n^3}{3}-\frac{n^2}{2}-\frac{n}{6}+2m{n}^2$$

(4.105)

que quando $m=n$ obtemos

$$\frac{8n^3}{3}-\frac{n^2}{2}-\frac{n}{6}\text{ flops}.$$

(4.106)

4.4.4 Custo para calcular a matriz inversa de $A$

---

Como vemos em Álgebra Linear, um método para obter a matriz $A^{-1}$ é realizar o escalonamento da matriz $\left[A|I\right]$ onde $I$ é a matriz identidade. Ao terminar o escalonamento, o bloco do lado direito conterá $A^{-1}$.

Isto é equivalente a resolver $n$ sistemas lineares com a mesma matriz $A$ e os vetores da base canônica $e_i={\left[0,...,0,1,0,....0\right]}^T$ tal que

$$A{x}_i=e_i,i=1:n$$

(4.107)

onde $x_i$ serão as colunas da matriz $A$ inversa, já que $AX=I$.

O custo para resolver esses $n$ sistemas lineares foi calculado na seção anterior como

$$\frac{8n^3}{3}-\frac{n^2}{2}-\frac{n}{6}.$$

(4.108)