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:
  1. Resolver o sistema linear por eliminação de Gauss.
  2. Resolver o mesmo sistema por fatoração LU.
  3. (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):
  1. 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 multiplicador m_{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}.
  2. Ao final fica uma matriz triangular superior U e um vetor c resultante das mesmas operações aplicadas a b.
  3. 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].
  • k=2: pivô a_{22}=\tfrac{1}{2}.
    • m_{32}=\dfrac{2}{1/2}=4. Atualiza linha 3: \text{L}_3 := \text{L}_3 - 4\text{L}_2 = [0,0,-1\mid 1].
Matriz triangular superior resultante:
U=\begin{pmatrix} 2 & 1 & -1\\[2pt] 0 & \tfrac{1}{2} & \tfrac{1}{2}\\[2pt] 0 & 0 & -1 \end{pmatrix},\qquad c=\begin{pmatrix}8\\[2pt]1\\[2pt]1\end{pmatrix}.
Substituição regressiva:
-1\cdot z = 1 \Rightarrow z=-1,
\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:
  1. Resolver L y = b por substituição progressiva.
  2. 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
L=\begin{pmatrix} 1 & 0 & 0\\[2pt] -\tfrac{3}{2} & 1 & 0\\[2pt] -1 & 4 & 1 \end{pmatrix},\qquad U=\begin{pmatrix} 2 & 1 & -1\\[2pt] 0 & \tfrac{1}{2} & \tfrac{1}{2}\\[2pt] 0 & 0 & -1 \end{pmatrix}.
Verifique que L U = A. Para resolver Ax=b:
  • 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):
  1. Quadrada: a fatoração LU e Cholesky exigem A quadrada ( n\times n).
  2. Estrutura de zeros (esparcidade): se A for esparsa (muitos zeros), algoritmos especializados e armazenamento esparso são importantes para reduzir custo e memória.
  3. Simetria: verifique se A = A^T. Se simétrica, métodos como Cholesky podem ser possíveis (ver passo seguinte).
  4. 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).
  5. 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.
  6. 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:
Para k=1,2,\dots,n:
  • Diagonal:
\ell_{kk} = \sqrt{\,a_{kk} - \sum_{s=1}^{k-1} \ell_{ks}^2\, }.
  • Subdiagonais (para i=k+1,\dots,n):
\ell_{ik} = \frac{1}{\ell_{kk}}\Bigl( a_{ik} - \sum_{s=1}^{k-1} \ell_{is}\ell_{ks}\Bigr).
Depois resolve-se L y = b (substituição progressiva) e L^T x = y (substituição regressiva).
Exemplo numérico (mostro um problema onde Cholesky vale): considere
A=\begin{pmatrix} 4 & 1 & 1\\[4pt] 1 & 3 & 0\\[4pt] 1 & 0 & 2 \end{pmatrix},\qquad b=\begin{pmatrix}6\\[2pt]5\\[2pt]5\end{pmatrix}.
Verificações rápidas:
  • A é simétrica.
  • 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.
Construção de L:
  • \ell_{11}=\sqrt{4}=2.
  • \ell_{21}=\dfrac{1}{2}=0{,}5,\quad \ell_{31}=\dfrac{1}{2}=0{,}5.
  • \ell_{22}=\sqrt{3-\ell_{21}^2}=\sqrt{3-0{,}25}=\sqrt{2{,}75}\approx1{,}658312.
  • \ell_{32}=\dfrac{a_{32}-\ell_{31}\ell_{21}}{\ell_{22}}=\dfrac{0 - 0{,}25}{1{,}658312}\approx -0{,}150756.
  • \ell_{33}=\sqrt{2-\ell_{31}^2-\ell_{32}^2}=\sqrt{2 - 0{,}25 - 0{,}022727\ldots}\approx\sqrt{1{,}727273}\approx1{,}314 (valores arredondados).
Portanto
L\approx \begin{pmatrix} 2 & 0 & 0\\[2pt] 0{,}5 & 1{,}658312 & 0\\[2pt] 0{,}5 & -0{,}150756 & 1{,}314 \end{pmatrix}.
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.
  1. 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.
  1. 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.
  1. 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):
  1. Identifique A e b.
  2. Verifique se A é quadrada e calcule algumas propriedades (simetria, diagonal dominante, sinal dos menores principais).
  3. 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.
  4. Se não for SPD, use LU com pivoteamento parcial; execute a eliminação e extraia L e U.
  5. 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.
  6. 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
\ell_{kk}=\sqrt{a_{kk}-\sum_{s=1}^{k-1}\ell_{ks}^2},\qquad \ell_{ik}=\frac{1}{\ell_{kk}}\Bigl(a_{ik}-\sum_{s=1}^{k-1}\ell_{is}\ell_{ks}\Bigr),
resolver L y=b e L^T x=y; os resultados coincidem (até erros de arredondamento) com LU quando aplicável.
(d) Comparação resumida:
  • Custo: LU/eliminação \sim \tfrac{2}{3}n^3 FLOPs; Cholesky \sim \tfrac{1}{3}n^3 FLOPs (mais eficiente para SPD).
  • Implementação: Gauss/LU são diretos, mas exigem pivoteamento para robustez; Cholesky é mais simples quando aplicável.
  • Estabilidade: LU com pivoteamento parcial é razoavelmente estável; Cholesky é estável para matrizes SPD; ambos sofrem se A estiver mal condicionado.

Exercícios relacionados