Escreva um algoritmo que faça as seguintes tarefas:
i) calcula os menores principais de uma matriz A de ordem n times n.
ii) Verifica se A admite decomposição LU (usando o Teorema 2, p. 137 do Livro da Ruggiero e Lopes).
iii) Encontra a decomposição LU.

Passo 1

Beleza, o enunciado pede três coisas para uma matriz quadrada de ordem :
  1. calcular todos os menores principais (isto é, os determinantes das submatrizes que vão do canto superior esquerdo até a linha/coluna , para );
  2. usar o Teorema 2 (Ruggiero & Lopes, p. 137) que diz que “ admite fatoração sem pivoteamento se, e só se, todos os menores principais são não nulos”;
  3. se der pra fatorar, encontrar concretamente as matrizes e .
Conteúdo envolvido: determinantes, menores principais e fatoração LU (método de Doolittle). A gente vai precisar entender como calcular determinantes de submatrizes e a regra recursiva do método Doolittle para obter e .

Passo 2

Calcular os menores principais
  1. Para cada de 1 até :
    a) Extraia a submatriz formada pelas primeiras linhas e primeiras colunas de .
    b) Calcule por qualquer algoritmo de determinante (por exemplo, expansão de Laplace para pequenos ou eliminação de Gauss).
  2. Guarde esses valores .
Explicação rápida: um “menor principal de ordem ” é só o determinante da matriz no canto de cima, tamanho .

Passo 3

Verificar condição de existência da LU
Pelo Teorema 2 do Ruggiero & Lopes:
“A matriz admite fatoração sem precisar trocar linhas (sem pivoteamento) se, e somente se, cada para todo .”
Então, depois de ter calculado , basta checar:
  • Se existe algum , a fatoração LU sem pivoteamento não é possível.
  • Se todos , podemos continuar e achar e .

Passo 4

Preparar para calcular Ui j = Ai j ;-; sumk=1^i-1 Li k,Uk j, e Lj i = 1Ui i;l(Aj i - sumk=1^i-1 Lj k,Uk ir) (método de Doolittle)
Assumimos que todos os . Vamos construir:
  • com 1’s na diagonal: .
  • com zeros abaixo da diagonal: para .
As fórmulas recursivas são, para e :
e, para :
Aqui usamos que (é garantido pelos ).

Passo 5

Montar o algoritmo completo (pseudocódigo)
  1. Para de 1 até :
    a. Forme .
    b. Calcule .
  2. Se existir , pare e diga “Não admite LU sem pivoteamento”.
  3. Senão, inicialize como matriz identidade e como matriz zero.
  4. Para de 1 até :
    a. Para de até :
    .
    b. Para de até :
    .
  5. Retorne as matrizes e .

Resposta

Segue o algoritmo que:
  1. calcula para ;
  2. checa se algum (se sim, interrompe e diz que não tem LU);
  3. senão, usa o método de Doolittle com as fórmulas acima para montar (diagonal de 1’s) e .

Exercícios relacionados