Quais as condições para um sistema Ax=b ter decomposição LU.

Passo 1

Beleza, o enunciado tá perguntando: “Quais as condições para um sistema ter decomposição LU?”
Conteúdo: decomposição LU (ou fatoração LU), que é uma forma de escrever a matriz como o produto de uma matriz triangular inferior e uma triangular superior .
O que precisamos: entender o processo de eliminação de Gauss, o papel dos “pivôs” e a teoria dos determinantes das submatrizes principais (leading principal minors).

Passo 2

Primeiro, o que é decomposição LU?
A ideia é achar duas matrizes:
L = 1 & 0 & cdots & 0 ell21 & 1 & cdots & 0 vdots & vdots & ddots & vdots elln1 & elln2 & cdots & 1 , U = u11 & u12 & cdots & u1n 0 & u22 & cdots & u2n vdots & vdots & ddots & vdots 0 & 0 & cdots & unn ,
de modo que
A = L,U
O motivo disso é que, ao aplicar eliminação de Gauss em sem trocar linhas, você vai “zerando” baixo da diagonal e guardando esses fatores de eliminação em .

Passo 3

Qual pedra no sapato impede essa fatoração?
Resposta: se em algum passo de Gauss o pivô (que é o elemento da diagonal na linha atual) for zero, não dá pra prosseguir sem trocar linhas. Como a fatoração LU clássica não faz permuta de linhas, precisamos garantir que nenhum desses pivôs seja zero.

Passo 4

Como traduzir isso em condição prática?
No k-ésimo passo de eliminação, o pivô é o elemento ukk = detl(A1:k,,1:kr)detl(A1:k-1,,1:k-1r), de detl(A1:k,,1:kr) neq 0 para todo k=1,2,dots,n . Teoria dos determinantes mostra que
onde é a submatriz formada pelas primeiras linhas e colunas de .
Para não dividir por zero, precisamos de

Resposta

Um sistema detl(A1:k,,1:kr)neq 0 para k=1,2,dots,n (com quadrada de ordem ) admite fatoração LU sem trocar linhas se, e somente se, todos os determinantes das submatrizes principais forem não nulos:

Exercícios relacionados