Fatoração LU

Um processo de fatoração para resolução de um sistema linear consiste em decompor a matriz dos coeficientes em um produto de dois ou mais fatores e, em seguida, resolver uma sequência de sistemas lineares mais simples, para no final obter a solução do sistema original. Vamos utilizar um exemplo numérico para entender como funciona a fatoração LU.

Exemplo 1: Considere o seguinte sistema linear:

\left\lbrace \begin{array}{rrrrrrr} 1x_1 & - & 2x_2 & + & 1x_3 & = &-1 \\ 2x_1 & - & 3x_2 & + & 1x_3 & = & -3 \\ 1x_1 & + & 4x_2 & + & 2x_3 & = & 7 \end{array}\right.

Escrevendo o sistema em sua forma matricial, temos:

Ax = b \Leftrightarrow \left[ \begin{array}{rrr} 1 & -2 & 1 \\ 2 & -3 & 1 \\ 1 & 4 & 2 \end{array} \right]\; \left[ \begin{array}{r} x_1 \\ x_2 \\ x_3 \end{array} \right] = \left[ \begin{array}{r} -1 \\ -3 \\ 7 \end{array} \right]

Vamos aplicar a eliminação Gaussiana, sem estratégia de pivoteamento, trabalhando apenas com a matriz

A

dos coeficientes. Na primeira etapa os multiplicadores são:

m_{21} = \frac{2}{1} = 2, \;\;\;\;\;\; m_{31} = \frac{1}{1} = 1

pois desta forma eliminamos a incógnita

x_1

da equação 2, isto é, zeramos a entrada

a_{21} = 2

da matriz

A

, aplicando a operação elementar

l_2 \longleftarrow l_2 - 2l_1

e, eliminamos

x_1

da equação 3, isto é, zeramos a entrada

a_{31} = 1

da matriz

A

, aplicando a operação elementar

l_3 \longleftarrow l_3 - 1l_1

. As matrizes elementares relacionadas a estas operações, respectivamente, são:

E_1 = \left[ \begin{array}{rrr} 1 & 0 & 0 \\ -2 & 1 & 0 \\ 0 & 0 & 1 \end{array} \right], \;\;\;\;\;\; E_2 = \left[ \begin{array}{rrr} 1 & 0 & 0 \\ 0 & 1 & 0 \\ -1 & 0 & 1 \end{array} \right]

Sabemos que aplicar a sequência de operações elementares sobre a matriz

A

é o mesmo que multiplicá-la à esquerda pela matriz

E_1

e o resultado multiplicar à esquerda por

E_2

, isto é, no final da primeira etapa teremos:

A^{(1)} = E_2(E_1A) = \left[ \begin{array}{rrr} 1 & 0 & 0 \\ 0 & 1 & 0 \\ -1 & 0 & 1 \end{array} \right]\; \left( \left[ \begin{array}{rrr} 1 & 0 & 0 \\ -2 & 1 & 0 \\ 0 & 0 & 1 \end{array} \right]\; \left[ \begin{array}{rrr} 1 & -2 & 1 \\ 2 & -3 & 1 \\ 1 & 4 & 2 \end{array} \right] \right) =

= \left[ \begin{array}{rrr} 1 & 0 & 0 \\ 0 & 1 & 0 \\ -1 & 0 & 1 \end{array} \right] \;\left[ \begin{array}{rrr} 1 & -2 & 1 \\ 0 & 1 & -1 \\ 1 & 4 & 2 \end{array} \right] = \left[ \begin{array}{rrr} 1 & -2 & 1 \\ 0 & 1 & -1 \\ 0 & 6 & 1 \end{array} \right]

Na segunda etapa o multiplicador é:

m_{32} = \frac{6}{1} = 6

pois desta forma eliminamos a incógnita

x_2

da equação 3, isto é, zeramos a entrada

a_{32}

da matriz

A^{(1)}

, aplicando a operação elementar

l_3 \longleftarrow l_3 - 6l_2

. A matriz elementar relacionada a esta operação é:

E_3 = \left[ \begin{array}{rrr} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & -6 & 1 \end{array} \right]

Aplicar esta operação elementar sobre a matriz

A^{(1)}

é o mesmo que multiplicá-la à esquerda pela matriz

E_3

, isto é, no final da segunda etapa teremos:

A^{(2)} = E_3 A^{(1)} = \left[ \begin{array}{rrr} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & -6 & 1 \end{array} \right] \;\left[ \begin{array}{rrr} 1 & -2 & 1 \\ 0 & 1 & -1 \\ 0 & 6 & 1 \end{array} \right] = \left[ \begin{array}{rrr} 1 & -2 & 1 \\ 0 & 1 & -1 \\ 0 & 0 & 7 \end{array} \right]

onde

A^{(2)}

é triangular superior. Note que:

A^{(2)} = E_3A^{(1)} = E_3[E_2(E_1A)] = (E_3E_2E_1)A

Além disso, como

E_1, E_2

E_3

são matrizes elementares, as inversas:

E_1^{-1} = \left[ \begin{array}{rrr} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 0 & 0 & 1 \end{array} \right], \;\;\; E_2^{-1} = \left[ \begin{array}{rrr} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 1 \end{array} \right], \;\;\; E_3^{-1} = \left[ \begin{array}{rrr} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 6 & 1 \end{array} \right]

existem e também são matrizes elementares, que representam as operações elementares inversas. Ou seja,

(E_3E_2E_1)A = A^{(2)} \Leftrightarrow A = (E_3E_2E_1)^{-1}A^{(2)} \Leftrightarrow A = E_1^{-1}E_2^{-1}E_3^{-1}A^{(2)}

Chamando

U = A^{(2)}

L = E_1^{-1}E_2^{-1}E_3^{-1} = \left[ \begin{array}{rrr} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 0 & 0 & 1 \end{array} \right] \;\left[ \begin{array}{rrr} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 1 \end{array} \right]\; \left[ \begin{array}{rrr} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 6 & 1 \end{array} \right] = \left[ \begin{array}{rrr} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 1 & 6 & 1 \end{array} \right]

Então,

A = \left[ \begin{array}{rrr} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 1 & 6 & 1 \end{array} \right] \;\left[ \begin{array}{rrr} 1 & -2 & 1 \\ 0 & 1 & -1 \\ 0 & 0 & 7 \end{array} \right] = LU

Isto é, fatoramos a matriz A em duas matrizes triangulares L e U, sendo que o fator L é triangular inferior com diagonal unitária e seus elementos

l_{ij}

, para

i>j

, são os multiplicadores

m_{ij}

obtidos no processo de eliminação Gaussiana. O fator U é triangular superior e é a matriz obtida no final do processo de eliminação Gaussiana a partir da matriz A.

Teorema 1 (Fatoração LU): Dada uma matriz

A: n\times n

, seja

A_k

a matriz constituída das primeiras k linhas e colunas de

A

. Suponha que

det(A_k) \neq 0

, isto é,

A_k

é não singular, para

k = 1, 2, ..., n

. Então, existe uma única matriz triangular inferior L, com diagonal unitária, e uma única matriz triangular superior U tais que

LU = A

.

Demonstração: Como as submatrizes

A_k

A

são todas não singulares, isto é,

det(A_k) \neq 0

para

k = 1, ..., n

, sempre que necessário podemos permutar as linhas para obter pivôs não nulos no processo de eliminação Gaussiana. Assim, podemos aplicar a eliminação Gaussiana na matriz

A

até obtermos uma matriz U triangular superior. Isto é, existem matrizes elementares

E_1, ..., E_m

tais que:

(E_m...E_3E_2E_1)A = U

onde as matrizes

E_i

, para

i = 1, ..., m

, são as matrizes elementares que representam as operações elementares aplicadas sobre as linhas de

A

durante o processo. Logo, as matrizes inversas

E_1^{-1}, E_2^{-1}, ..., E_m^{-1}

existem e temos:

A = (E_m...E_3E_2E_1)^{-1}U \Leftrightarrow A = E_1^{-1} E_2^{-1} E_3^{-1} ... E_m^{-1} U

Chamando

L = E_1^{-1} E_2^{-1} E_3^{-1} ... E_m^{-1}

, temos portanto

A = LU

. Pelo modo como foi construído, o fator L é triangular inferior (do inglês Lower triangular) com diagonal unitária e seus elementos

l_{ij}

, para

i > j

, são os multiplicadores

m_{ij}

obtidos durante o processo de eliminação Gaussiana. E como já vimos, o fator U é a matriz triangular superior (do inglês Upper triangular) obtida no final do processo.

Voltar ao Topo.

Resolução de Sistemas Lineares Utilizando a Fatoração LU

Dado o sistema linear

Ax = b

e a fatoração LU de

A

, temos:

Ax = b \Leftrightarrow (LU)x = b \Leftrightarrow L(Ux) = b

Chamando

y = Ux

, podemos obter a solução do sistema original resolvendo os seguintes sistemas triangulares:

(i)

Ly = b

(ii)

Ux = y

O vetor

y

é o vetor constante obtido ao final do processo da eliminação de Gauss. De fato, considerando o sistema

Ly = b

temos que

y = L^{-1}b

. Mas

L = E_1^{-1} E_2^{-1} E_3^{-1} ... E_m^{-1} \Leftrightarrow L^{-1} = E_m...E_3E_2E_1

. Então,

y = (E_m...E_3E_2E_1)b

, o que corresponde a aplicar as mesmas operações elementares utilizadas para triangularizar

A

sobre o vetor

b

.

Exemplo 2: Considerando o sistema linear

Ax = b

do Exemplo 1 e a fatoração LU obtida:

A = LU = \left[ \begin{array}{rrr} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 1 & 6 & 1 \end{array} \right] \;\left[ \begin{array}{rrr} 1 & -2 & 1 \\ 0 & 1 & -1 \\ 0 & 0 & 7 \end{array} \right]

Vamos resolver o sistema

Ax = b \Leftrightarrow (LU)x = b

, resolvendo primeiro o sistema triangular inferior

Ly = b

e depois o sistema triangular superior

Ux = y

. Olhando para o primeiro sistema, temos:

Ly = b \Leftrightarrow \left[ \begin{array}{rrr} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 1 & 6 & 1 \end{array} \right] \;\left[ \begin{array}{r} y_1 \\ y_2 \\ y_3 \end{array} \right] = \left[ \begin{array}{r} -1 \\ -3 \\ 7 \end{array} \right] \Leftrightarrow \left\lbrace \begin{array}{rrrrrrr} 1y_1 & & & & & = & -1 \\ 2y_1 & + & 1y_2 & & & = & -3 \\ 1y_1 & + & 6y_2 & + & 1y_3 & = & 7 \end{array}\right.

Resolvendo esse sistema obtemos

y_1 = -1, y_2 = -1

y_3 = 14

. Agora, olhando para o segundo sistema, temos:

Ux = y \Leftrightarrow \left[ \begin{array}{rrr} 1 & -2 & 1 \\ 0 & 1 & -1 \\ 0 & 0 & 7 \end{array} \right] \;\left[ \begin{array}{r} x_1 \\ x_2 \\ x_3 \end{array} \right] = \left[ \begin{array}{r} -1 \\ -1 \\ 14 \end{array} \right] \Leftrightarrow \left\lbrace \begin{array}{rrrrrrr} 1x_1 & - & 2x_2 & + & 1x_3 & = & -1 \\ & & 1x_2 & - & 1x_3 & = & -1 \\ & & & & 7x_3 & = & 14 \end{array}\right.

Resolvendo esse sistema obtemos

x_1 = -1, x_2 = 1

x_3 = 2

, que é a solução do sistema original.

A grande vantagem da fatoração LU é que ela depende apenas da matriz

A

. Assim, precisamos obter apenas uma vez a fatoração LU de

A

e podemos resolver qualquer sistema que a tenha como matriz dos coeficientes, trocando apenas o vetor constante

b

.

Exemplo 3: Considere o seguinte sistema linear:

\left\lbrace \begin{array}{rrrrrrr} 1x_1 & - & 2x_2 & + & 1x_3 & = & -6 \\ 2x_1 & - & 3x_2 & + & 1x_3 & = & -8 \\ 1x_1 & + & 4x_2 & + & 2x_3 & = & 25 \end{array}\right.

Escrevendo o sistema em sua forma matricial:

Ax = b' \Leftrightarrow \left[ \begin{array}{rrr} 1 & -2 & 1 \\ 2 & -3 & 1 \\ 1 & 4 & 2 \end{array} \right]\; \left[ \begin{array}{r} x_1 \\ x_2 \\ x_3 \end{array} \right] = \left[ \begin{array}{r} -6 \\ -8 \\ 25 \end{array} \right]

Note que a matriz

A

dos coeficientes é a mesma do sistema linear do exemplo anterior e apenas mudamos o vetor

b

por

b'

. Assim, podemos usar a fatoração LU de

A

já obtida para resolver o sistema

(LU)x = b'

. Considerando primeiro o sistema triangular inferior , temos:

Ly = b' \Leftrightarrow \left[ \begin{array}{rrr} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 1 & 6 & 1 \end{array} \right]\; \left[ \begin{array}{r} y_1 \\ y_2 \\ y_3 \end{array} \right] = \left[ \begin{array}{r} -6 \\ -8 \\ 25 \end{array} \right] \Leftrightarrow \left\lbrace \begin{array}{rrrrrrr} 1y_1 & & & & & = & -6 \\ 2y_1 & + & 1y_2 & & & = & -8 \\ 1y_1 & + & 6y_2 & + & 1y_3 & = & 25 \end{array}\right.

Resolvendo esse sistema obtemos

y_1 = -6, y_2 = 4

y_3 = 7

. Considerando agora o sistema triangular superior

Ux = y

, temos:

Ux = y \Leftrightarrow \left[ \begin{array}{rrr} 1 & -2 & 1 \\ 0 & 1 & -1 \\ 0 & 0 & 7 \end{array} \right]\; \left[ \begin{array}{r} x_1 \\ x_2 \\ x_3 \end{array} \right] = \left[ \begin{array}{r} -6 \\ 4 \\ 7 \end{array} \right] \Leftrightarrow \left\lbrace \begin{array}{rrrrrrr} 1x_1 & - & 2x_2 & + & 1x_3 & = & -6 \\ & & 1x_2 & - & 1x_3 & = & 4 \\ & & & & 7x_3 & = & 7 \end{array}\right.

Resolvendo esse sistema obtemos

x_1 = 3, x_2 = 5

x_3 = 1

, que é a solução do sistema original.

Exemplo 4: Considere o seguinte sistema linear na forma matricial:

Ax = b \Leftrightarrow \left[ \begin{array}{rrr} 2 & 3 & 1 \\ 1 & 1 & 2 \\ 4 & 2 & 1 \end{array} \right] \;\left[ \begin{array}{r} x_1 \\ x_2 \\ x_3 \end{array} \right] = \left[ \begin{array}{r} 4 \\ 5 \\ 6 \end{array} \right]

Aplicando a eliminação de Gauss, sem estratégia de pivoteamento, para triangularizar

A

, temos:

Etapa 1: o pivô desta etapa é

a_{11}^{(0)} = a_{11} = 2

e os multiplicadores são:

m_{21} = \frac{a_{21}^{(0)}}{a_{11}^{(0)}} = \frac{1}{2}, \;\;\;\;\;\; m_{31} = \frac{a_{31}^{(0)}}{a_{11}^{(0)}} = \frac{4}{2} = 2

Então, aplicamos as operações elementares

l_2 \longleftarrow l_2 - m_{21}l_1

l_3 \longleftarrow l_3 - m_{31} l_1

sobre

A^{(0)}

, obtendo:

A^{(1)} = \left[ \begin{array}{rrr} 2 & 3 & 1 \\ 0 & -\frac{1}{2} & \frac{3}{2} \\ 0 & -4 & -1 \end{array} \right]

Uma vez que na etapa k o algoritmo da eliminação Gaussiana trabalha a partir da coluna k da matriz, e os elementos

a_{21}^{(1)}

a_{31}^{(1)}

são nulos, podemos armazenar os multiplicadores nestas posições. Assim,

A^{(1)} = \left[ \begin{array}{rrr} 2 & 3 & 1 \\ {\color{red} \frac{1}{2}} & -\frac{1}{2} & \frac{3}{2} \\ {\color{red} 2} & -4 & -1 \end{array} \right]

Etapa 2: o pivô agora é

a_{22}^{(1)} = -\frac{1}{2}

e o multiplicador é:

m_{32} = \frac{a_{32}^{(1)}}{a_{22}^{(1)}} = \frac{-4}{-\frac{1}{2}} = 8

Então, aplicamos a operação elementar

l_3 \longleftarrow l_3 - m_{32}l_3

sobre

A^{(1)}

. Como a entrada

a_{32}^{(1)}

será nula, armazenamos nela o multiplicador

m_{32}

. Assim:

A^{(2)} = \left[ \begin{array}{rrr} 2 & 3 & 1 \\ {\color{red} \frac{1}{2}}& -\frac{1}{2} & \frac{3}{2} \\ {\color{red} 2} & {\color{red} 8} & -13 \end{array} \right]

Portanto, temos armazenados na matriz

A^{(2)}

as informações dos fatores L e U, obtendo a fatoração:

A = \left[ \begin{array}{rrr} 1 & 0 & 0 \\ \frac{1}{2} & 1 & 0 \\ 2 & 8 & 1 \end{array} \right] \;\left[ \begin{array}{rrr} 2 & 3 & 1 \\ 0 & -\frac{1}{2} & \frac{3}{2} \\ 0 & 0 & -13 \end{array} \right] = LU

Vamos então resolver o sistema

(LU)x = b

. Considerando primeiro o sistema triangular inferior

Ly = b

, temos:

Ly = b \Leftrightarrow \left[ \begin{array}{rrr} 1 & 0 & 0 \\ \frac{1}{2} & 1 & 0 \\ 2 & 8 & 1 \end{array} \right] \;\left[ \begin{array}{r} y_1 \\ y_2 \\ y_3 \end{array} \right] = \left[ \begin{array}{r} 4 \\ 5 \\ 6 \end{array} \right] \Leftrightarrow \left\lbrace \begin{array}{rrrrrrr} 1y_1 & & & & & = & 4 \\ \frac{1}{2}y_1 & + & 1y_2 & & & = & 5 \\ 2y_1 & + & 8y_2 & + & 1y_3 & = & 6 \end{array}\right.

Resolvendo esse sistema obtemos

y_1 = 4, y_2 = 3

y_3 = -26

. Considerando agora o sistema triangular superior

Ux = y

, temos:

Ux = y \Leftrightarrow \left[ \begin{array}{rrr} 2 & 3 & 1 \\ 0 & -\frac{1}{2} & \frac{3}{2} \\ 0 & 0 & -13 \end{array} \right]\; \left[ \begin{array}{r} x_1 \\ x_2 \\ x_3 \end{array} \right] = \left[ \begin{array}{r} 4 \\ 3 \\ -26 \end{array} \right] \Leftrightarrow \left\lbrace \begin{array}{rrrrrrr} 2x_1 & + & 3x_2 & + & 1x_3 & = & 4 \\ & - & \frac{1}{2}x_2 & + & \frac{3}{2}x_3 & = & 3 \\ & & & - & 13x_3 & = & -26 \end{array}\right.

Resolvendo esse sistema obtemos

x_1 = 1, x_2 = 0

x_3 = 2

. Portanto, a solução do sistema original é

(x_1, x_2, x_3) = (1, 0, 2)

.

Voltar ao Topo.

Fatoração LU com Pivoteamento

Estudaremos a aplicação de uma estratégia de pivoteamento parcial à fatoração LU. O pivoteamento requer a permutação de linhas na matriz

A^{(k)}

no início da etapa k da eliminação Gaussiana, quando necessário. Neste caso, teremos que guardar estas trocas de linha, pois as mesmas permutações efetuadas em

A

deverão ser efetuadas sobre o vetor constante

b

, uma vez que permutar as linhas de

A

implica em permutar as equações do sistema

Ax = b

.

Definição: Uma matriz quadrada de ordem

n

é dita matriz de permutação se pode ser obtida da matriz identidade de ordem

n

permutando-se suas linhas (ou colunas).

Exemplo 5: Considere o sistema linear:

\left\lbrace \begin{array}{rrrrrrr} 0x_1 & + & 1x_2 & - & 2x_3 & = & 7 \\ 2x_1 & - & 2x_2 & + & 3x_3 & = & -10 \\ 1x_1 & + & 3x_2 & + & 1x_3 & = & 8 \end{array}\right.

Escrevendo-o em sua forma matricial, temos:

Ax = b \Leftrightarrow \left[ \begin{array}{rrr} 0 & 1 & -2 \\ 2 & -2 & 3 \\ 1 & 3 & 1 \end{array} \right] \;\left[ \begin{array}{r} x_1 \\ x_2 \\ x_3 \end{array} \right] = \left[ \begin{array}{r} 7 \\ -10 \\ 8 \end{array} \right]

Vamos aplicar a eliminação Gaussiana, com estratégia de pivoteamento parcial, para triangularizar a matriz

A

. No início da etapa k, escolheremos para pivô o maior elemento, em módulo, entre os coeficientes

a_{ik}^{(k-1)}

i = k, k+1, ..., n

.

Etapa 1: escolhemos como pivô desta etapa o maior elemento em módulo da coluna 1, que é

a_{21} = 2

. Assim, precisamos permutar as linhas 1 e 2 da matriz

A^{(0)} = A

. Para isso, basta aplicar sobre

A^{(0)}

a operação elementar

l_1 \longleftrightarrow l_2

, o que equivale a multiplicar

A^{(0)}

pela matriz de permutação:

P_1 = \left[ \begin{array}{rrr} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{array} \right]

obtendo:

\hat{A}^{(0)} = P_1A^{(0)} = \left[ \begin{array}{rrr} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{array} \right] \;\left[ \begin{array}{rrr} 0 & 1 & -2 \\ 2 & -2 & 3 \\ 1 & 3 & 1 \end{array} \right] = \left[ \begin{array}{rrr} 2 & -2 & 3 \\ 0 & 1 & -2 \\ 1 & 3 & 1 \end{array} \right]

Efetuamos então a eliminação normalmente em

\hat{A}^{(0)}

. Os multiplicadores são

m_{21} = 0

m_{31} = \frac{1}{2}

, e então o elemento

\hat{a}^{(0)}_{21}

já é nulo. Portanto, basta aplicarmos a operação elementar

l_3 \longleftarrow l_3 - m_{31}l_1

sobre

\hat{A}^{(0)}

, obtendo:

A^{(1)} = \left[ \begin{array}{rrr} 2 & -2 & 3 \\ {\color{red} 0} & 1 & -2 \\ {\color{red} \frac{1}{2}} & 4 & -\frac{1}{2} \end{array} \right]

Como as entradas

a^{(1)}_{21}

a^{(1)}_{31}

são nulas, armazenamos nelas os multiplicadores.

Etapa 2: escolhemos como pivô desta etapa o maior elemento em módulo da coluna 2, que é

a_{32} = 4

. Assim, precisamos permutar as linhas 2 e 3 da matriz

A^{(1)}

. Para isso, basta multiplicá-la pela matriz de permutação:

P_2 = \left[ \begin{array}{rrr} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{array} \right]

obtendo:

\hat{A}^{(1)} = P_2A^{(1)} = \left[ \begin{array}{rrr} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{array} \right] \;\left[ \begin{array}{rrr} 2 & -2 & 3 \\ {\color{red} 0} & 1 & -2 \\ {\color{red} \frac{1}{2}} & 4 & -\frac{1}{2} \end{array} \right] = \left[ \begin{array}{rrr} 2 & -2 & 3 \\ {\color{red} \frac{1}{2}} & 4 & -\frac{1}{2} \\ {\color{red} 0} & 1 & -2 \end{array} \right]

Efetuamos então a eliminação em

\hat{A}^{(1)}

. O multiplicador é

m_{32} = \frac{1}{4}

e aplicamos sobre

A

a operação elementar

l_3 \longleftarrow l_3 - m_{32}l_2

, obtendo:

A^{(2)} = \left[ \begin{array}{rrr} 2 & -2 & 3 \\ {\color{red} \frac{1}{2}} & 4 & -\frac{1}{2} \\ {\color{red} 0} & {\color{red} \frac{1}{4}} & -\frac{15}{8} \end{array} \right]

Portanto, os fatores L e U obtidos são:

L = \left[ \begin{array}{rrr} 1 & 0 & 0 \\ \frac{1}{2} & 1 & 0 \\ 0 & \frac{1}{4} & 1 \end{array} \right], \;\;\;\;\;\;\;\; U = \left[ \begin{array}{rrr} 2 & -2 & 3 \\ 0 & 4 & -\frac{1}{2} \\ 0 & 0 & -\frac{15}{8} \end{array} \right]

Mas esta é a fatoração LU de

\hat{A} = PA

, onde

P = P_2P_1

, isto é:

\hat{A} = PA = \left[ \begin{array}{rrr} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{array} \right]\; \left[ \begin{array}{rrr} 0 & 1 & -2 \\ 2 & -2 & 3 \\ 1 & 3 & 1 \end{array} \right] = \left[ \begin{array}{rrr} 2 & -2 & 3 \\ 1 & 3 & 1 \\ 0 & 1 & -2 \end{array} \right]

As mesmas permutações de linhas aplicadas sobre

A

deverão ser aplicadas sobre o vetor constante

b

do sistema. Seja então

\hat{b} = Pb

. O sistema linear

\hat{A}x = \hat{b}

é equivalente ao original e, como

PA = LU

, temos

PAx = Pb \Leftrightarrow (LU)x = Pb

. Assim, precisamos resolver os sistemas triangulares:

(i)

Ly = Pb

(ii)

Ux = y

para obter a solução do sistema original. Olhando para o primeiro sistema, temos:

Pb = \left[ \begin{array}{rrr} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{array} \right] \;\left[ \begin{array}{r} 7 \\ -10 \\ 8 \end{array} \right] = \left[ \begin{array}{r} -10 \\ 8 \\ 7 \end{array} \right]

e assim:

Ly = Pb \Leftrightarrow \left[ \begin{array}{rrr} 1 & 0 & 0 \\ \frac{1}{2} & 1 & 0 \\ 0 & \frac{1}{4} & 1 \end{array} \right] \;\left[ \begin{array}{r} y_1 \\ y_2 \\ y_3 \end{array} \right] = \left[ \begin{array}{r} -10 \\ 8 \\ 7 \end{array} \right] \Leftrightarrow \left\lbrace \begin{array}{rrrrrrr} 1y_1 & & & & & = & -10 \\ \frac{1}{2}y_1 & + & 1y_2 & & & = & 8 \\ & & \frac{1}{4}y_2 & + & 1y_3 & = & 7 \end{array}\right.

Resolvendo esse sistema obtemos

y_1 = -10, y_2 = 13

y_3 = \frac{15}{4}

. Olhando agora para o segundo sistema, temos:

Ux = y \Leftrightarrow \left[ \begin{array}{rrr} 2 & -2 & 3 \\ 0 & 4 & -\frac{1}{2} \\ 0 & 0 & -\frac{15}{8} \end{array} \right] \;\left[ \begin{array}{r} x_1 \\ x_2 \\ x_3 \end{array} \right] = \left[ \begin{array}{r} -10 \\ 13 \\ \frac{15}{4} \end{array} \right] \Leftrightarrow \left\lbrace \begin{array}{rrrrrrr} 2x_1 & - & 2x_2 & + & 3x_3 & = & -10\\ & & 4x_2 & - & \frac{1}{2}x_3 & = & 13 \\ & & & & -\frac{15}{8}x_3 & = & \frac{15}{4} \end{array}\right.

Resolvendo esse sistema obtemos

x_1 = 1, x_2 = 3

x_3 = -2

. Portanto, a solução do sistema original é

(x_1, x_2, x_3) = (1, 3, -2)

.

Considerando um sistema linear

Ax = b

geral, tal que

A

é não singular, então no início da etapa k do processo de eliminação Gaussiana existe pelo menos um elemento não nulo entre os coeficientes

a_{kk}^{(k-1)}, ..., a_{nk}^{(k-1)}

, de modo que podemos realizar uma troca de linhas em

A^{(k-1)}

e obter a matriz

\hat{A}^{(k-1)}

com elemento

\hat{a}^{(k-1)}_{kk}

não nulo. Desta forma, podemos realizar a eliminação e determinar unicamente os fatores L e U tais que

PA = LU

, onde

P = P_{(n-1)}P_{(n-2)}...P_1

e cada

P_k

é a matriz de permutação que representa a troca de linhas efetuada na etapa k.

As mesmas permutações de linha efetuadas em

A

deverão também ser efetuadas sobre o vetor constante

b

, obtendo assim o vetor

Pb

. Logo, teremos o seguinte sistema, equivalente ao original:

PAx = Pb \Leftrightarrow (LU)x = Pb

. Assim, precisamos resolver os sistemas triangulares:

Ly = Pb

Ux = y

para obter a solução do sistema original.

As permutações de linha realizadas na fatoração podem ser armazenadas em um vetor

p: n\times 1

, definido por

p(k) = i

se na etapa k a linha

i

da matriz original

A

for a linha que contêm o pivô.

Algoritmo (Resolução do sistema linear Ax = b através da fatoração LU com pivoteamento parcial): Considere o sistema linear

Ax = b

, com

A:n\times n

. As incógnitas

x_1, ..., x_n

podem ser obtidas através da fatoração LU com pivoteamento parcial, como no algoritmo a seguir. O vetor

p

representará as permutações realizadas durante a fatoração:
Algoritmo.

Voltar ao Topo.

Última Atualização: 02/02/2016.