Escreva um algoritmo que faça as seguintes tarefas:
i) calcula os menores principais de uma matriz
de ordem
.
ii) Verifica se
admite decomposição LU (usando o Teorema 2, p. 137 do Livro da Ruggiero e Lopes).
iii) Encontra a decomposição LU.
i) calcula os menores principais de uma matriz
ii) Verifica se
iii) Encontra a decomposição LU.
Passo 1
Beleza, o enunciado pede três coisas para uma matriz quadrada
de ordem
:
- calcular todos os menores principais (isto é, os determinantes das submatrizes que vão do canto superior esquerdo até a linha/coluna
, para ); - 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”; - 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
- Para cada
de 1 até :
a) Extraia a submatrizformada pelas primeiras linhas e primeiras colunas de .
b) Calculepor qualquer algoritmo de determinante (por exemplo, expansão de Laplace para pequenos ou eliminação de Gauss). - 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
.”
Pelo Teorema 2 do Ruggiero & Lopes:
“A matriz
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
e
(método de Doolittle)
Assumimos que todos os . Vamos construir:
Assumimos que todos os
-
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)
- Para
de 1 até :
a. Forme.
b. Calcule. - Se existir
, pare e diga “Não admite LU sem pivoteamento”. - Senão, inicialize
como matriz identidade e como matriz zero. - Para
de 1 até :
a. Parade até :
.
b. Parade até :
. - Retorne as matrizes
e .
Resposta
Segue o algoritmo que:
- calcula
para ; - checa se algum
(se sim, interrompe e diz que não tem LU); - senão, usa o método de Doolittle com as fórmulas acima para montar
(diagonal de 1’s) e .