Resolver o sistema linear utilizando métodos exatos estudados na disciplina, como:
eliminação de Gauss;
fatoração LU.
Em seguida, responda:
(a) Observe a estrutura da matriz de coeficientes obtida. Quais características você consegue identificar?
(b) Com base nessas características, investigue se é possível aplicar a decomposição de Cholesky ao sistema. Dica: A decomposição de Cholesky pode ser aplicada a matrizes que possuem propriedades específicas. Investigue se a matriz obtida neste problema satisfaz tais propriedades.
(c) Caso seja possível, implemente o método de Cholesky e compare os resultados com os métodos anteriores.
(d) Compare os métodos em termos de:
custo computacional;
facilidade de implementação;
estabilidade numérica.
Passo 1
O enunciado pede que se resolva um sistema linear por métodos exatos (eliminação de Gauss e fatoração LU) e, em seguida, responda às questões (a)–(d) sobre a estrutura da matriz, possibilidade de usar Cholesky, implementação do método (se aplicável) e comparação entre métodos.
Informações fornecidas no enunciado do usuário:
Pedido genérico para aplicar os métodos citados ao “sistema linear”.
Não foi fornecida nenhuma matriz de coeficientes A nem vetor termo independente b.
Perguntas que o enunciado faz:
Resolver o sistema linear por eliminação de Gauss.
Resolver o mesmo sistema por fatoração LU.
(a) Observar e descrever características da matriz de coeficientes obtida.
(b) Verificar se a decomposição de Cholesky é aplicável.
(c) Se aplicável, implementar Cholesky e comparar resultados.
(d) Comparar métodos em custo computacional, facilidade de implementação e estabilidade numérica.
Observação importante: não há dados numéricos do sistema. Por isso não é possível fornecer a solução numérica do seu sistema específico. A partir do próximo passo eu vou:
ensinar passo a passo como aplicar eliminação de Gauss e fatoração LU de maneira que você consiga aplicar direto ao seu sistema na prova;
mostrar como inspecionar a matriz para decidir sobre Cholesky;
demonstrar Cholesky em um exemplo onde ela é aplicável;
comparar os métodos teoricamente (custos, implementação, estabilidade).
Passo 2
A ideia da eliminação de Gauss (passo a passo) — conceito e algoritmo prático.
O que é: eliminação de Gauss transforma o sistema
A x = b
num sistema triangular superior [U x = c) por operações elementares em linhas, e depois resolve por substituição regressiva.
Notação e significado:
A é a matriz quadrada de coeficientes de ordem n.
x é o vetor incógnita \;x=(x_1,\dots,x_n)^T.
b é o vetor de termos independentes.
Algoritmo (forma direta, sem pivoteamento):
Para cada coluna k=1,2,\dots,n-1:
a. Escolher pivô a_{kk}. Se a_{kk}=0 deve-se pivotear (trocar linhas) — caso contrário divisão por zero.
b. Para cada linha i=k+1,\dots,n calcular o multiplicadorm_{ik}=\frac{a_{ik}}{a_{kk}}.c. Atualizar a linha i por\text{linha}_i := \text{linha}_i - m_{ik}\cdot \text{linha}_k,o que zera a entrada a_{ik}.
Ao final fica uma matriz triangular superior U e um vetor c resultante das mesmas operações aplicadas a b.
Resolver U x = c por substituição regressiva: começar em x_n e subir.
Dica importante (estabilidade): na prática usa-se pivoteamento parcial: trocar, antes de eliminar na coluna k, a linha k com a linha abaixo que tem o maior valor absoluto na coluna k. Isso evita divisões por números muito pequenos e melhora a estabilidade numérica.
Exemplo ilustrativo (para aprender a aplicar): considere o sistema
\begin{cases} 2x + y - z = 8,\\[4pt] -3x - y + 2z = -11,\\[4pt] -2x + y + 2z = -3. \end{cases}
Vou mostrar a eliminação (você pode reproduzir com seu sistema):
k=1\]: pivô \(a_{11}=2.
m_{21}=\dfrac{-3}{2}=-\tfrac{3}{2}. Atualiza linha 2:\text{L}_2 := \text{L}_2 - m_{21}\text{L}_1 = \text{L}_2 + \tfrac{3}{2}\text{L}_1que dá \text{L}_2=[0,\tfrac{1}{2},\tfrac{1}{2}\mid 1].
m_{31}=\dfrac{-2}{2}=-1. Atualiza linha 3:\text{L}_3 := \text{L}_3 - m_{31}\text{L}_1 = \text{L}_3 + \text{L}_1que dá \text{L}_3=[0,2,1\mid 5].
\tfrac{1}{2}y + \tfrac{1}{2}z = 1 \Rightarrow y = 2 - z = 3,
2x + y - z = 8 \Rightarrow 2x + 3 -(-1) = 8 \Rightarrow x=2.
Resultado do exemplo: x=2,\;y=3,\;z=-1.
Esse procedimento é exatamente o que você deve aplicar à sua matriz na prova, obedecendo a regras de pivoteamento se necessário.]
Passo 3
Fatoração LU — conceito, fórmula e como usar para resolver.
O que é: fatorizar A como produto
A = L U,
onde L é triangular inferior com diagonais unitárias (ou não, dependendo da convenção) e U é triangular superior. Uma vez que A=LU, resolver Ax=b se faz em duas etapas:
Resolver L y = b por substituição progressiva.
Resolver U x = y por substituição regressiva.
Relação com eliminação de Gauss: os multiplicadores usados na eliminação formam as subdiagonais de L; o resultado final da eliminação é U. Quando não houve trocas de linhas, a eliminação direta fornece L e U.
Como construir L e U (método de Doolittle — L com diagonais 1):
Para k=1,\dots,n:
Para j=k,\dots,n calcule u_{kj} = a_{kj} - \sum_{s=1}^{k-1} l_{ks}u_{sj}.
Para i=k+1,\dots,n calcule l_{ik} = \dfrac{1}{u_{kk}}\bigl(a_{ik} - \sum_{s=1}^{k-1} l_{is}u_{sk}\bigr).
Definir l_{kk}=1.
Aplicando ao mesmo exemplo do Passo 2 os multiplicadores que já tínhamos:
Multiplicadores usados: m_{21}=-\tfrac{3}{2},\; m_{31}=-1,\; m_{32}=4.
Assim
Primeiro L y = b por substituição direta (progressiva) para obter y.
Depois U x = y por substituição regressiva.
Vantagens práticas:
Se for preciso resolver A x = b para vários vetores b diferentes, fatorizar A=LU uma vez e reutilizar L e U é muito eficiente.
Em códigos usa-se pivotamento (LU com permutação P: P A = L U) para garantir existência da fatoração sem divisão por zero.]
Passo 4
Como inspecionar a matriz de coeficientes (resposta à parte (a) do enunciado).
Quando você obtiver a matriz A na prova, verifique estas características (cada item com significado prático):
Quadrada: a fatoração LU e Cholesky exigem A quadrada (n\times n).
Estrutura de zeros (esparcidade): se A for esparsa (muitos zeros), algoritmos especializados e armazenamento esparso são importantes para reduzir custo e memória.
Simetria: verifique se A = A^T. Se simétrica, métodos como Cholesky podem ser possíveis (ver passo seguinte).
Definitude: verifique se A é definida positiva (necessária para Cholesky). Testes práticos:
Teste dos menores principais (leading principal minors): todos os determinantes das submatrizes principais A_k (até k=n) devem ser positivos:\det(A_1)>0,\quad \det(A_2)>0,\quad\ldots,\quad\det(A_n)>0.
Ou testar se para todo vetor não nulo x vale x^T A x > 0 (mais teórico).
Condicionamento e estabilidade numérica: calcule (ou estime) o número de condição \kappa(A)=\|A\|\|A^{-1}\|. Matriz mal condicionada torna os métodos sensíveis a erros de arredondamento.
Diagonal dominante: se A é estritamente diagonal dominante por linhas (ou colunas), a eliminação tende a ser estável; além disso garante invertibilidade.
Conclusão prática para (a): descreva na prova as características que você identificou entre os itens acima. Elas guiarão a escolha do método (por exemplo: simétrica e definida positiva → Cholesky; esparsa e tridiagonal → métodos diretos especializados).
Passo 5
Quando é possível aplicar a decomposição de Cholesky — resposta à parte (b).
Condição necessária e suficiente (prática):
A deve ser simétrica: A=A^T.
A deve ser definida positiva: para todo vetor x\neq 0, x^T A x > 0.
Formas práticas de verificar na prova:
Verificar simetria explicitamente: comparar elementos a_{ij} e a_{ji}.
Verificar positividade dos menores principais: calcular determinantes dos blocos A_1,\dots,A_n e conferir que são positivos (teste direto para pequenas dimensões).
Se A for pequena (por ex. 2\times2 ou 3\times3), calcular \det(A_k) é direto. Para matrizes maiores pode-se verificar via tentativa de Cholesky: se durante a construção surge um termo a ser igual à raiz quadrada de um número não positivo, então não é SPD.
Se A satisfaz essas propriedades, existe L triangular inferior com entradas reais tais que
A = L L^T.
Passo 6
Implementação do método de Cholesky (passo a passo com fórmulas) — isto responde à parte (c), mostrando como fazer na prova.
Para uma matriz simétrica definida positiva A de ordem n, os elementos de L são dados por:
Menores principais: \det([4])=4>0, \det\!\begin{pmatrix}4&1\\[2pt]1&3\end{pmatrix}=11>0, \det(A)=19>0. Logo A é definida positiva → Cholesky aplicável.
Resolver L y = b por progressiva e depois L^T x = y dará a solução x (os cálculos numéricos seguem simples substituições — você pode reproduzir na prova com ordem de cálculo indicado).
Comparação com LU no mesmo caso: se A é SPD, a fatoração LU sem pivoteamento existe e Cholesky produz L com metade da carga computacional e com garantias de estabilidade melhores (para SPD). Os resultados numéricos são equivalentes até erros de arredondamento.]
Passo 7
Comparação dos métodos — resposta à parte (d): custo, implementação e estabilidade.
Custo computacional (ordem de complexidade em número de operações reais — FLOPs, para matrizes densas n\times n):
Eliminação de Gauss / fatoração LU (sem considerar reaproveitamento): ordem principal de \dfrac{2}{3}n^3 operações aritméticas para obter U (ou L e U). Depois, cada substituição (forward/back) custa \mathcal{O}(n^2).
Fatoração Cholesky (para A SPD): cerca de \dfrac{1}{3}n^3 operações (aproximadamente metade do custo da LU), mais \mathcal{O}(n^2) para as substituições.
Se for preciso resolver para muitos vetores b, o custo da fatoração (LU ou Cholesky) se paga porque a solução de cada novo b requer só \mathcal{O}(n^2) operações.
Facilidade de implementação:
Eliminação de Gauss: conceito simples, fácil de codificar; porém requer cuidado com pivoteamento e com atualizações in-place.
Fatoração LU: ligeiramente mais estrutural (armazenar L e U), porém é direta quando a implementação aproveita os mesmos passos da eliminação. Requer tratamento de pivoteamento (permutações) para robustez.
Cholesky: ainda mais simples quando aplicável (apenas metade das operações e sem necessidade de pivoteamento em princípio); porém exige que a matriz seja SPD, então precisa de verificação prévia.
Estabilidade numérica:
Eliminação de Gauss sem pivoteamento pode ser numericamente instável (divisões por pivôs pequenos amplificam erros). Na prática usa-se pivoteamento parcial; LU com pivotamento parcial (PA=LU) é geralmente estável para muitas aplicações.
Cholesky é numericamente estável para matrizes SPD (e não requer pivoteamento). Em termos práticos, para uma SPD bem condicionada, Cholesky costuma ser mais preciso e eficiente.
Matrizes mal condicionadas (alto \kappa(A)) tornam qualquer método sensível a erros de arredondamento; mesmo Cholesky sofre, pois \kappa é intrínseco à matriz.
Observações práticas e recomendações:
Se A é simétrica e definida positiva → usar Cholesky: é o método preferido (mais rápido, estável).
Se A é geral (não simétrica) → usar LU com pivoteamento parcial.
Se A é esparsa com estrutura especial (tridiagonal, banda estreita), use métodos diretos especializados que exploram a esparsidade (por ex. algoritmo de Thomas para tridiagonais).
Sempre verifique condicionamento e, se necessário, use escalamento e/ou aritmética de maior precisão.
Passo 8
Passo final prático para você aplicar na prova (resumo de ações):
Identifique A e b.
Verifique se A é quadrada e calcule algumas propriedades (simetria, diagonal dominante, sinal dos menores principais).
Se A for simétrica e todos os menores principais positivos, use Cholesky: escreva as fórmulas de construção de L e resolva L y=b, L^T x = y.
Se não for SPD, use LU com pivoteamento parcial; execute a eliminação e extraia L e U.
Em qualquer método, documente os multiplicadores, mostre as operações elementares (na prova o examinador quer ver os passos) e resolva por substituição.
Comente sobre estabilidade: indique se fez pivoteamento e se o sistema parece bem ou mal condicionado.
Resposta
Não é possível calcular a solução numérica porque o sistema linear (matriz A e vetor b) não foi fornecido.
(a) Para identificar características da matriz, verificar se A é quadrada, esparsa ou densa, simétrica (A=A^T), diagonalmente dominante, e se os menores principais são positivos (para testar definição positiva).
(b) A decomposição de Cholesky pode ser aplicada somente se A for simétrica e definida positiva; teste prático: verificar simetria e os menores principais positivos (ou tentar fatorar e verificar se todas as diagonais de L são reais positivos).
(c) Se A for SPD, implementar Cholesky com as fórmulas