Sistemas Lineares - Decomposição LU

Prévia do material em texto

CÁLCULO NUMÉRICO 
Rejane Izabel Lima Corrêa
Sistemas lineares: 
decomposição LU
Objetivos de aprendizagem
Ao final deste texto, você deve apresentar os seguintes aprendizados:
 � Definir o método da decomposição LU sem pivotamento e com 
pivotamento.
 � Reconhecer a importância do método na resolução de sistemas 
lineares, na obtenção de matrizes inversas e na avaliação de condi-
cionamento de sistemas. 
 � Aplicar esse método em problemas de engenharia.
Introdução
Sistemas lineares surgem com frequência em situações do cotidiano, e 
com mais frequência ainda em problemas de caráter técnico. A mode-
lagem de um problema em equações lineares é de extrema importân-
cia para a resolução e a obtenção da solução. As equações modeladas 
envolvendo as mesmas variáveis são agrupadas e definidas como um 
sistema de equações lineares.
Neste capítulo, você vai aprender a resolver um sistema linear com 
o método da decomposição LU sem pivotamento e com pivotamento, 
identificando quando e como deverá ser aplicada cada uma das técnicas.
Decomposição LU
Um sistema linear com n variáveis x1, x2, x3, ..., xn é um conjunto de m equações 
lineares:
onde aij e bj são constantes reais, para 1 ≤ i ≤ m e 1 ≤ j ≤ n.
Todo sistema linear pode ser reescrito como o produto matricial AX = B, 
onde:
 
é a matriz dos coeficientes; é a matriz das variáveis; e 
é a matriz das constantes.
A resolução de sistemas lineares pode ser obtida através de métodos nu-
méricos que são divididos em métodos diretos e métodos iterativos.
O método da decomposição LU é um dos métodos diretos, que são métodos 
que permitem obter a solução do sistema linear realizando um número finito de 
operações. Neste caso a solução é exata, a menos de erros de arredondamento, 
e é possível determinar o esforço computacional gasto para obter a solução. 
Sistemas lineares: decomposição LU2
Método da decomposição LU
Neste método, para a solução de um sistema linear usa-se o fato de que, nas 
condições necessárias, uma matriz quadrada pode ser decomposta como um 
produto de duas matrizes triangulares.
Considere o sistema linear Ax = B, onde A é uma matriz invertível (det(A) ≠ 0). 
Nessa condição, a matriz A pode ser decomposta como o produto A = LU, 
onde L é uma matriz triangular inferior e U é uma matriz triangular superior.
Teorema: se a matriz A é tal que det(A) ≠ 0, então existe uma única matriz 
triangular inferior L = [lij], onde lij = mij (multiplicadores do método de Gauss) 
e uma matriz triangular superior U = [uij], tal que A = LU (CONTE, 1965).
Podemos reescrever o teorema da seguinte forma: se o método da elimi-
nação de Gauss pode ser efetuado sobre a matriz A, então pode ser escrita 
por A = LU, onde L é uma matriz triangular inferior com lii = 1, e U é uma 
matriz triangular superior.
O teorema fornece um processo para construir as matrizes L e U. A matriz L 
é obtida pelos multiplicadores utilizados no processo da eliminação de Gauss, 
sendo que lii = 1, e a matriz L é a própria matriz triangular superior obtida no 
processo da decomposição de Gauss.
Nos links a seguir, você encontra exemplos sobre o método da eliminação de Gauss 
e da eliminação de Gauss com pivotamento.
https://qrgo.page.link/UU1U
https://qrgo.page.link/ukme
3Sistemas lineares: decomposição LU
Conhecer a decomposição LU de uma matriz facilita na resolução de um 
sistema linear. Para a solução do sistema linear Ax = B, fatoramos a matriz 
A = LU e obtemos o sistema:
LUx = B
Fazendo Ux = y, reescrevemos o sistema por Ly = B. Dessa forma, recaímos 
sobre dois sistemas lineares mais simples de resolver:
Ly = B
Ux = y
O primeiro sistema é simples pelo fato de ser um sistema triangular superior 
e, para determinar a solução, basta usar substituição sucessiva. Já o segundo 
sistema é triangular superior e, por retrossubstituição, determinamos a solução.
Resolvendo o primeiro sistema determinamos os valores do vetor y. Subs-
tituindo y no segundo sistema, determinamos os valores de x, que é o vetor 
solução do sistema.
A sequência de passos para o método da decomposição LU é a seguinte.
1. Decompor A = LU. Nessa etapa, as matrizes L e U são construídas 
simultaneamente. A cada processo do método da eliminação de Gauss 
estabelecemos uma linha de U e uma coluna de L.
2. Resolver o sistema linear Ly = B por substituição sucessiva.
3. Resolver o sistema linear Ux = y por retrossubstituição.
Tenha atenção ao método utilizado. Nesta etapa utilizamos o método da eliminação 
de Gauss, que é realizado sobre a matriz A sem trocas de linhas ou colunas. 
Sistemas lineares: decomposição LU4
De forma geral, para um sistema de ordem n:
 � A matriz triangular inferior 
onde:
lij = mij = 
aij
ajj
, se i > j;
lij = 1, se i = j;
lij = 0, se i < j.
 � A matriz triangular superior é a matriz 
 obtida no método da eliminação de Gauss sobre a matriz A.
Resolva o sistema linear:
Pelo método da decomposição LU.
a) Inicialmente montamos as matrizes relacionadas ao sistema: Ax = B.
b) Construção das matrizes triangulares L e U, a partir da matriz A.
Passo 1: determinar primeira coluna de L e primeira linha de U.
5Sistemas lineares: decomposição LU
Pivô da primeira coluna: a11 = 1. Zerar elementos da primeira coluna abaixo da 
diagonal principal:
Em seguida, determinamos os multiplicadores de cada linha abaixo do pivô e pro-
cedemos com o método de Gauss para zerar os elementos abaixo do pivô:
Passo 2: determinar segunda coluna de L e segunda linha de U.
Pivô da segunda coluna: a22 = 2. Zerar elementos da segunda coluna abaixo da 
diagonal principal:
Em seguida, determinamos os multiplicadores de cada linha abaixo do pivô e pro-
cedemos com o método de Gauss para zerar os elementos abaixo do pivô:
Passo 3: determinar a terceira coluna de L e terceira linha de U.
Pivô da terceira coluna: a33 = –12.
Nesse caso, a linha e a coluna das matrizes L e U, respectivamente, já estão definidas. 
Assim:
Sistemas lineares: decomposição LU6
c) Calcular a solução do sistema Ly = B.
Por substituição direta:
d) Calcular a solução do sistema Ux = y (e, por sua vez, a solução do sistema Ax = B). 
Por retrossubstituição:
A solução do sistema Ax = B é x = 
2
–1
3
.
7Sistemas lineares: decomposição LU
A vantagem do método da decomposição LU é que podemos alterar o vetor B, 
e não é necessário refazer os cálculos do método da eliminação de Gauss, pois 
efetuamos as operações somente sobre as linhas da matriz A.
Resolva o sistema linear:
Pelo método da decomposição LU.
a) Inicialmente montamos as matrizes relacionadas ao sistema: Ax = B. 
b) Construção das matrizes triangulares L e U, a partir da matriz A.
Observe que a matriz A é a mesma do exercício anterior. Nesse caso não é necessário 
refazer todos os passos para determinar as matrizes L e U, que já estão determinadas:
Assim, podemos passar para as próximas etapas de resolver os sistemas triangulares. 
Sistemas lineares: decomposição LU8
c) Calcular a solução do sistema Ly = B.
Por substituição direta:
d) Calcular a solução do sistema Ux = y (e, por sua vez, a solução do sistema Ax = B). 
Por retrossubstituição:
A solução do sistema Ax = B é x = 
1
0
2
.
9Sistemas lineares: decomposição LU
Algoritmo: determinar as matrizes L e U
Dado o sistema linear Ax = B, de n variáveis e n equações:
a) Definir a matriz [A], com n linhas e n colunas.
b) Construção das matrizes triangulares L = [lij] e U = [uij].
 ■ Para m = 1, ..., n – 1, faça:
 ■ Para j = m, m + 1, ..., n, faça:
 ■ Para i = m + 1, ..., n, faça:
 ■ Para m = n, faça:
Fonte: Arenales e Darezzo (2008).
Teste seus conhecimentos e o algoritmo anterior para programar o código apresentado 
para determinar as matrizes L e U de uma matriz quadrada inversível. Utilize o Matlab 
ou Scilab para fazer a implementação do código anterior e determinar solução de 
sistemas lineares pelo método do pivotamento parcial. 
Sistemas lineares: decomposição LU10
Para uma maior eficiência computacional, podemos construir as matrizesL e U em 
uma mesma matriz ao invés de montar matrizes separadas em cada passo do processo.
Considere o sistema linear trabalhado no primeiro exemplo:
Pelo método da decomposição LU, a cada etapa construímos uma matriz L e uma 
matriz U:
Poderíamos reescrever as duas matrizes em uma única, dada por:
Onde os elementos verdes são da matriz L e os elementos pretos da matriz U. Lem-
brando que L é triangular inferior com todos os elementos da diagonal principal iguais 
a 1. E U é uma matriz triangular superior.
A cada passo obteríamos as matrizes.
Passo 1: determinar primeira coluna e primeira linha de L/U.
Pivô da primeira coluna: a11 = 1. Zerar elementos da primeira coluna abaixo da 
diagonal principal:
11Sistemas lineares: decomposição LU
Em seguida, determinamos os multiplicadores de cada linha abaixo do pivô e pro-
cedemos com o método de Gauss para zerar os elementos abaixo do pivô:
Passo 2: determinar segunda coluna e segunda linha de L/U.
Pivô da segunda coluna: a22 = 2. Zerar elementos da segunda coluna abaixo da 
diagonal principal:
Em seguida, determinamos os multiplicadores de cada linha abaixo do pivô e pro-
cedemos com o método de Gauss para zerar os elementos abaixo do pivô:
Passo 3: determinar a terceira coluna de L e terceira linha de U.
Pivô da terceira coluna: a33 = –12.
Nesse caso, a linha e a coluna da matriz L/U já estão definidas. Assim:
E as matrizes L e U são:
Sistemas lineares: decomposição LU12
Resolva o sistema linear:
Pelo método da decomposição LU com três casas decimais.
a) Inicialmente montamos as matrizes relacionadas as sistema: Ax = B. 
b) Construção das matrizes triangulares L e U, a partir da matriz A.
Passo 1: determinar primeira coluna de L e primeira linha de U.
Pivô da primeira coluna: a11 = 0,42. Zerar elementos da primeira coluna abaixo da 
diagonal principal:
Em seguida, determinamos os multiplicadores de cada linha abaixo do pivô e pro-
cedemos com o método de Gauss para zerar os elementos abaixo do pivô:
13Sistemas lineares: decomposição LU
Passo 2: determinar segunda coluna de L e segunda linha de U.
Pivô da segunda coluna: a22 = 0,495. Zerar elementos da segunda coluna abaixo da 
diagonal principal:
Em seguida, determinamos os multiplicadores de cada linha abaixo do pivô e pro-
cedemos com o método de Gauss para zerar os elementos abaixo do pivô:
Passo 3: determinar a terceira coluna de L e terceira linha de U.
Pivô da terceira coluna: a33 = –12.
Nesse caso, a linha e a coluna das matrizes L e U, respectivamente, já estão definidas. 
Assim:
c) Calcular a solução do sistema Ly = B.
Por substituição direta:
Sistemas lineares: decomposição LU14
d) Calcular a solução do sistema Ux = y (e, por sua vez, a solução do sistema Ax = B). 
Por retrossubstituição:
A solução do sistema Ax = B é x = 
–20,005
0,989 
7,645 
.
Note que é possível verificarmos se a solução obtida está de acordo com o sistema 
linear. Nesse caso, basta fazer o produto Ax e verificar se o resultado será igual a B.
Decomposição LU com pivotamento
Nas operações elementares aplicadas sobre as linhas da matriz A no método 
de Gauss aparece a operação de divisão pelo pivô. Na maioria das operações 
de divisão são gerados erros de arredondamento que vão se acumulando ao 
longo das eliminações sucessivas. Outros problemas que observamos nesse 
método são o caso em que um dos pivôs é igual a zero (o que impossibilita 
a obtenção do multiplicador) ou o caso em que os multiplicadores assumem 
valores muito grandes (pivô próximo de zero). 
15Sistemas lineares: decomposição LU
Podemos associar o processo da decomposição LU a um processo de pivota-
mento parcial para evitar pivôs nulos (ou próximos de zero) e diminuir a perda 
de significação. Para aplicar a estratégia de pivotamento parcial ao Método 
da Decomposição LU, faz-se necessário armazenar um vetor de permutação 
P, que armazena a informação das trocas de linhas.
Nesse caso, continuamos com a decomposição A = LU e os sistemas trian-
gulares a serem resolvidos são:
Ly = B– e Ux = y
Onde B– é o vetor obtido do vetor B alterando a ordem das linhas de acordo 
com o vetor de permutação P. 
Resolva o sistema linear:
Pelo método da decomposição LU com pivotamento usando três dígitos significativos.
a) Inicialmente montamos as matrizes relacionadas ao sistema: Ax = B e o vetor P.
b) Construção das matrizes triangulares L e U, a partir da matriz A.
Passo 1: determinar primeira coluna de L e primeira linha de U.
Pivô da primeira coluna – elemento de maior valor absoluto: a11 = 0,448. Zerar 
elementos da primeira coluna abaixo da diagonal principal:
Sistemas lineares: decomposição LU16
Em seguida, determinamos os multiplicadores de cada linha abaixo do pivô e pro-
cedemos com o método de Gauss para zerar os elementos abaixo do pivô:
Passo 2: determinar segunda coluna de L e segunda linha de U.
Pivô da segunda coluna – elemento de maior valor absoluto: a32 = –1,559. Trocar linhas 
2 e 3 de posição e zerar elementos da segunda coluna abaixo da diagonal principal:
Em seguida, determinamos os multiplicadores de cada linha abaixo do pivô e pro-
cedemos com o método de Gauss para zerar os elementos abaixo do pivô:
Passo 3: determinar a terceira coluna de L e terceira linha de U.
Pivô da terceira coluna: a33 = –0,388.
Nesse caso, a linha e a coluna das matrizes L e U, respectivamente, já estão definidas. 
Assim:
17Sistemas lineares: decomposição LU
c) Calcular a solução do sistema Ly = B–.
Por substituição direta:
d) Calcular a solução do sistema Ux = y (e, por sua vez, a solução do sistema Ax = B). 
Por retrossubstituição:
A solução do sistema Ax = B é x = 
–1,389
 1,399
2,376
.
Sistemas lineares: decomposição LU18
Ao resolver um sistema linear por métodos diretos, é interessante adotar 
um método com o menor número possível de operações possíveis. Neste caso, 
o método de decomposição LU é o mais indicado. Apesar do número total de 
operações ser da mesma ordem que o método de Gauss, a decomposição LU 
acumula menos erros de arredondamento.
Outro fator importante que devemos considerar é que, em sistemas mal 
condicionados, isto é, sistemas nos quais uma pequena variação nos coefi-
cientes acarreta uma variação enorme na solução do sistema, o método de 
pivotamento torna-se imprescindível, pois a solução do sistema fica menos 
sensível a erros de arredondamento. 
Fatoração LU no cálculo da matriz inversa e 
condicionamento de sistemas
Se a é uma matriz quadrada tal que det(A) ≠ 0, então existe outra matriz A–1, 
com a mesma ordem de A, chamada inversa de a, para a qual AA– 1 = A– 1A = I.
Uma das melhores formas de determinar a inversa de uma matriz numeri-
camente é através do método da decomposição LU. Tal método fornece uma 
forma eficaz de determinar a solução de um sistema Ax = B, para diversos 
valores do vetor B.
Cálculo da matriz inversa por decomposição LU
Podemos utilizar a decomposição LU para determinar a inversa de uma matriz. 
Dada uma matriz , quadrada de ordem n, queremos determinar A– 1, tal que:
AA–1 = I
Seja A uma matriz quadrada de ordem n. Assim, temos:
19Sistemas lineares: decomposição LU
Podemos determinar a inversa de A com o auxílio da decomposição 
A = LU, resolvendo sistemas do tipo:
Axj = Ij, para j = 1, ..., n
onde: 
é a j-ésima coluna de A–1, e
é a j-ésima coluna de I. Com a decomposição, obtemos sistemas do tipo:
Axj = LUxj = Ij, para j = 1, ..., n
Gerando os sistemas:
Uxj = yj e Lyj = Ij
Como a matriz A é comum em todos os sistemas, com uma única aplicação 
da eliminação de Gauss conseguimos determinar os n vetores xj que formam 
a matriz inversa.
Sistemas lineares: decomposição LU20
Determine a inversa da matriz:
Pelo método da decomposição LU.
a) Determinar as matrizes triangulares L e U, a partir de A.
Passo 1: determinar primeira coluna de L e primeira linha de U.
Pivô da primeira coluna: a11 = 1. Zerar elementos da primeira coluna abaixo da 
diagonal principal:
Em seguida, determinamos os multiplicadores decada linha abaixo do pivô e pro-
cedemos com o método de Gauss para zerar os elementos abaixo do pivô:
Passo 2: determinar segunda coluna de L e segunda linha de U.
Pivô da segunda coluna: a22 = 3. Zerar elementos da segunda coluna abaixo da 
diagonal principal:
21Sistemas lineares: decomposição LU
Em seguida, determinamos os multiplicadores de cada linha abaixo do pivô e pro-
cedemos com o método de Gauss para zerar os elementos abaixo do pivô:
Passo 3: determinar a terceira coluna de L e terceira linha de U.
Pivô da terceira coluna: a33 = –2/3.
Nesse caso, a linha e a coluna das matrizes L e U, respectivamente, já estão definidas. 
Assim:
b) Calcular a solução dos sistemas Lyj = Ij e Uxj = yj para j = 1, 2, 3.
Para j = 1:
Por substituição direta:
Sistemas lineares: decomposição LU22
Por retrossubstituição:
Para j = 2:
Por substituição direta:
Por retrossubstituição:
Para j = 3:
23Sistemas lineares: decomposição LU
Por substituição direta:
Por retrossubstituição:
c) Montar a matriz inversa A–1.
Condicionamento de sistemas
A inversa de uma matriz tem muitas aplicações em áreas científicas e na 
engenharia. Além disso, a inversa também fornece formas de determinar se 
um sistema é mal condicionado. De acordo com Chapra (2013), existem três 
métodos para determinar se um sistema é mal condicionado, descritos a seguir.
1. Alterar a escala da matriz A de tal forma que o maior elemento de cada 
linha seja igual a 1. Inverta a matriz obtida. Se houver elementos em 
A–1 que sejam várias ordens de grandeza maiores que 1, é provável que 
o sistema seja mal condicionado.
2. Multiplique A–1 pela matriz A original. Verifique se a multiplicação obtida 
está próxima da matriz identidade. Se não, indica mau condicionamento.
3. Determine a inversa de A–1. Verifique se o resultado está próximo de 
A. Caso contrário, significa um sistema mal condicionado.
Sistemas lineares: decomposição LU24
Fatoração LU na engenharia
Muitos problemas em engenharia são baseados em leis de conservação, como, 
por exemplo, energia, massa, momento. Matematicamente, modelamos esses 
problemas com equações de continuidade ou de balanço. O princípio da con-
servação da massa pode ser usado, por exemplo, para formular um modelo 
para uma série de reatores químicos. Além de sistemas físicos, as equações 
lineares aparecem também em problemas matemáticos. 
Um dos princípios mais importantes na engenharia química é a conservação de massa. 
Considerando um sistema estável, isto é, onde todas as entradas de um material são 
iguais às saídas, vamos determinar as concentrações do sistema de reatores a seguir.
Q13 = 4
Q23 = 1 Q33 = 10
Q13 =2
Q12 = 3Q01 = 6
C01 = 10
c1 c2 c3
A quantidade de massa em cada reator pode ser obtida pelo produto da vazão Q 
(m³/min) pela concentração c (mg/m³).
A taxa na qual a massa escoa para dentro do reator 1 é:
Q01C01 + Q13C3 = 6 ∙ 10 + 2c3 = 60 + 2c3 mg/min
A taxa de saída é:
Q12c1 + Q13c1 = 3c1 + 4c1 = 7c1
Assim, como o sistema é estacionário,
60 + 2c3 = 7c1 → 7c1 – 2c3 = 60
Fazendo a mesma ideia para os outros dois reatores, temos o seguinte.
 � Reator 2: 3c1 = c2 → 3c1 – c2 = 0
 � Reator 3: 4c1 + c2 = 10c3 → 4c1 + c2 – 10c3 = 0
25Sistemas lineares: decomposição LU
Matrizes relacionadas ao sistema:
Pelo método da decomposição LU.
a) Determinar as matrizes triangulares L e U, a partir de A.
Passo 1: determinar primeira coluna de L e primeira linha de U.
Pivô da primeira coluna: a11 = 7. Zerar elementos da primeira coluna abaixo da 
diagonal principal:
Passo 2: determinar segunda coluna de L e segunda linha de U.
Pivô da segunda coluna: a22 = 3. Zerar elementos da segunda coluna abaixo da 
diagonal principal.
Sistemas lineares: decomposição LU26
Passo 3: determinar a terceira coluna de L e terceira linha de U.
Pivô da terceira coluna: a33 = –2/3. 
Nesse caso, a linha e a coluna das matrizes L e U, respectivamente, já estão definidas. 
Assim:
b) Calcular a solução dos sistemas Ly = B.
Por substituição direta:
c) Calcular a solução do sistema Ux = y.
Por retrossubstituição:
Assim a concentração nos reatores 1, 2 e 3, respectivamente, é c1 = 10,714 mg/m³, 
c2 = 32,168 mg/m³ e c3 = 7,5 mg/m³.
27Sistemas lineares: decomposição LU
ARENALES, S.; DAREZZO, A. Cálculo numérico: aprendizagem com apoio de software. 
São Paulo: Thomson Learning, 2008.
CHAPRA, S. C. Métodos numéricos aplicados com MATLAB para engenheiros e cientistas. 
3. ed. Porto Alegre: AMGH, 2013.
CONTE, S. D. Elementary numerical analysis. New York: MacGraw-Hill, 1965.
Leituras recomendadas
ANDRADE, D. Decomposição LU e Cholesky. Maringá, [201-?]. Disponível em: http://
www.dma.uem.br/kit/arquivos/arquivos_pdf/cholesky.pdf. Acesso em: 16 abr. 2019.
ANTON, H.; HORRES, C. Álgebra linear com aplicações. 10. ed. Porto Alegre: Bookman, 2012.
BARROSO, L. C. Cálculo numérico: com aplicações. 2. ed. São Paulo: Harbra, 1987.
CHAPRA, S. C.; CANALE, R. P. Métodos numéricos para engenharia. Porto Alegre: AMGH, 
2016.
DORNELLES FILHO, A. A. Fundamentos de cálculo numérico. Porto Alegre: Bookman, 2016.
LIPSCHUTZ, S.; LIPSON, M. Álgebra linear. 4. ed. Porto Alegre: Bookman, 2011. (Coleção 
Schaum).
SOUZA, M. J. F. Cálculo numérico: notas de aula. Ouro Preto, 2018. Disponível em: http://
www.decom.ufop.br/marcone/Disciplinas/CalculoNumerico/Sistemas.pdf. Acesso 
em: 16 abr. 2019.
WILKSON, J. H. Rounding erros in algebraic process. Englewood Clifss: Prentice Hall, 1963.
Sistemas lineares: decomposição LU28