dsdsd

Decomposi¸c˜ao LU e Cholesky
Prof. Doherty Andrade - DMA-UEM

Sum´ ario 1 Introdu¸c˜ ao 1

2 M´ etodo de Elimina¸c˜ ao de Gauss

1

3 Decomposi¸c˜ ao LU

2

4 O m´ etodo de Cholesky

5

5 O Algoritmo para a decomposi¸c˜ ao Cholesky

7

1

Introdu¸c˜ ao A decmposi¸ca˜o LU e a decomposi¸ca˜o de Cholesky s˜ao m´etodos diretos de resolu¸ca˜o de sistemas de equa¸c˜oes lineares Ax = b. O objetivo ´e decompor a matriz A como A = LU no caso da decomposi¸c˜ao LU, A = LLT no caso da decomposi¸ca˜o de Cholesky.
Antes de falarmos sobre a decomposi¸ca˜o LU e Cholesky precisamos relembrar o m´etodo de elimina¸ca˜o de Gauss. A decomposi¸ca˜o LU ´e uma conseq¨ uˆencia do m´etodo de elimina¸ca˜o de Gauss.Isto ´e, a decomposi¸ca˜o de
Cholesky ´e uma especializa¸c˜ao da decomposi¸ca˜o LU . Os m´etodos de decomposi¸ca˜o s˜ao importantes na resolu¸ca˜o de sistemas de equa¸co˜es lineares, como veremos a seguir. Veja (3.2) e (3.3).

2

M´ etodo de Elimina¸c˜ ao de Gauss

Este m´etodo ´e um m´etodo direto para resolver sistemas de equa¸co˜es lineares, consiste em tranformar a matriz ampliada do sistema em uma outra equiva1

lente que seja triangular superior. Para isto usa apenas opera¸c˜oes elementares sobre linhas da matriz.
Uma vez tendo o sistema na forma triangular superior, a solu¸c˜ao ´e obtida pela substitui¸c˜ao inversa.
Dado o sistema Bx = b, seja A a matriz ampliada do sistema. Em cada
(k)
passo k, vamos denotar por A(k) = (aij ) a matriz obtida ap´os este passo.
Os passos s˜ao os seguintes:
Passo 1: eliminar ak1 , k = 2, 3, . . . , n, obtendo A(1)
Passo 2: eliminar na matriz A(1) , ak2 , k = 3, 4, . . . , n.
Prosseguindo at´e atingir o passo (n − 1) cujo objetivo ´e eliminar an,n−1
(1) (2)
(n−1)
Os elementos a11 , a22 , a33 , . . . , ann s˜ao chamados de pivot e os n´ umeros (k−1)

mik =

aik

(k−1)

akk

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

(2.1)

s˜ao chamados de multiplicadores.
Existem dois problemas