Podemos encontrar a fatoração LU de A diretamente, usando simplesmente a definição de produto de matrizes. Esquemas deste tipo são conhecidos como esquemas compactos, e o equivalente à fatoração A=LU com L triangular inferior com diagonal unitária e U triangular superior é chamado de redução de Doolittle.
Supondo que a fatoração LU de A seja possível, de uma forma única,
a) multiplique a primeira linha de L pela j-ésima coluna de U e iguale a a1 j. Verifique que desta forma obtém-se o elemento u1 j;
b) repita o item (a), multiplicando agora a i-ésima linha de L pela primeira coluna de U, e igualando a a ai 1 será possível obter li 1;
c) use o mesmo raciocínio de (a) e (b) para deduzir que, se as (k-1) primeiras linhas de U e colunas de L já foram determinadas, então
ukj=akj-summ=1^k-1 lkm umj, j=k,(k+1), ldots, n
e
li k=(ai k-summ=1^k-1 li m um k) / uk k, i=(k+1), ldots, n ;
d) explique por que, se A é não singular, então U também o será, donde ukk neq 0, k=1, ldots, n ;
e) escreva um algoritmo para a fatoração LU de A usando a redução de Doolittle;
f) teste seu algoritmo, fatorando A e então resolvendo o sistema abaixo, sendo
A=(rrrr2 & 3 & 1 & 5 1 & 3.5 & 1 & 7.5 1.4 & 2.7 & 5.5 & 12 -2 & 1 & 3 & 28) e b=(r11 13 21.6 30)

Passo 1

O enunciado pede para derivar o método de Doolittle, que consiste em fatorar
A = LU
onde L é triangular inferior com diagonal unitária e U é triangular superior. Vamos usar a definição de produto de matrizes para obter expressões para os elementos de L e U, justificar não-singularidade de U, escrever o algoritmo e testar com o sistema dado.

Passo 2

Para i=1 e qualquer j, do produto A=LU temos
a1j = summ=1^n l1m,umj
Como l11=1 e l1m=0 para m>1, sobra
a1j = u1j
Logo
u1j = a1j

Passo 3

Para j=1 e qualquer i, do mesmo produto
ai1 = summ=1^n lim,um1
Aqui u11neq0 e um1=0 para m>1, então
ai1 = li1,u11,
isto é
li1 = ai1u11

Passo 4

Suponha que as primeiras k-1 linhas de U e colunas de L já estejam definidas. Para ukj com j>= k:
akj = summ=1^n lkm,umj = summ=1^k-1 lkm,umj + lkk,ukj,
e lkk=1 implica
ukj = akj - summ=1^k-1 lkm,umj, j=k,dots,n
Para lik com i>k:
aik = summ=1^n lim,umk = summ=1^k-1 lim,umk + lik,ukk,
logo
lik = aik - summ=1^k-1 lim,umkukk, i=k+1,dots,n

Passo 5

Se A é não singular, então det(A)neq0. Mas
det(A) = det(L),det(U),
e como det(L)=1 (diagonal unitária), segue det(U)neq0. Portanto todos ukkneq0.

Passo 6

Algoritmo (pseudocódigo) para k=1,dots,n:
¶ j=k até n: ukj = akj - summ=1^k-1 lkm,umj, ¶ i=k+1 até n: lik = aik - summ=1^k-1 lim,umkukk éé
No final teremos A=LU. Para resolver Ax=b fazemos primeiro Ly=b por substituição direta e depois Ux=y por retro-substituição.

Passo 7

Teste com
A= 2 & 3 & 1 & 5 1 & 3,5 & 1 & 7,5 1,4 & 2,7 & 5,5 & 12 -2 & 1 & 3 & 28 , b=111321,630
Aplicando o algoritmo obtemos
L= 1 & 0 & 0 & 0 0,5 & 1 & 0 & 0 0,7 & 0,3 & 1 & 0 -1 & 2 & 0,6451613 & 1 , U= 2 & 3 & 1 & 5 0 & 2 & 0,5 & 5 0 & 0 & 4,65 & 7 0 & 0 & 0 & 18,483871
Resolvendo Ly=b e em seguida Ux=y achamos
x = 1111

Resposta

a) u1j=a1j
b) li1=ai1/u11
c) ukj=akj-summ=1^k-1lkmumj, lik=l(aik-summ=1^k-1limumkr)/ukk
d) Como det(A)=det(L)det(U) e det(L)=1, se det(A)neq0 então det(U)neq0, logo ukkneq0.
e) Algoritmo Doolittle em loops para k=1 a n usando as fórmulas acima.
f) Fatoração de A L e U acima e solução x=(1,1,1,1)^T.

Exercícios relacionados