Quanto aos métodos iterativos para solução de sistemas lineares, podemos afirmar que:
- Convergem apenas se a matriz dos coeficientes é estritamente diagonal dominante.
- São particularmente úteis quando a matriz dos coeficientes é esparsa;
- Convergem sempre que houver solução para o sistema linear;
- Produzem soluções exatas;
- Convergem apenas se a matriz dos coeficientes for bem condicionada;
Passo 1
O enunciado pede que avaliemos a veracidade das cinco afirmações sobre métodos iterativos para resolver sistemas lineares. As afirmações são (copiadas tal como foram dadas):
- Convergem apenas se a matriz dos coeficientes é estritamente diagonal dominante.
- São particularmente úteis quando a matriz dos coeficientes é esparsa.
- Convergem sempre que houver solução para o sistema linear.
- Produzem soluções exatas.
- Convergem apenas se a matriz dos coeficientes for bem condicionada.
O que é pedido: dizer quais dessas afirmações são verdadeiras e quais são falsas. Não há dados numéricos adicionais; trata-se de avaliar propriedades teóricas dos métodos iterativos.
Passo 2
Entender o critério de convergência geral dos métodos iterativos (a peça central da explicação).
- Um método iterativo linear escreve a iteração na forma de ponto fixo
onde
é a chamada matriz de iteração (depende do método escolhido, por exemplo Jacobi, Gauss–Seidel, SOR, etc.) e
é um vetor. Essa é a forma padrão de qualquer iteração linear.
- Teorema-chave (condição necessária e suficiente para convergência): a iteração converge para a solução do sistema para qualquer chute inicial
se, e somente se,
onde
é o raio espectral de
, isto é, o máximo dos módulos dos autovalores de
.
- Definição do raio espectral:
- Intuição: se
, potências de tendem a zero ( ) e a série geométrica convergente garante que a iteração aproxima a solução; se a iteração geralmente diverge ou não se estabiliza.
Vou usar isso sempre: convergência ⇔
. Agora mostro como isso se relaciona com cada afirmação.
Passo 3
Analisando a afirmação 1: “Convergem apenas se a matriz dos coeficientes é estritamente diagonal dominante.”
- Primeiro explico o que é estrita dominância diagonal por linhas: uma matriz
é estritamente diagonal dominante por linhas se, para todo ,
- Por que algumas pessoas pensam assim: para métodos simples como Jacobi e Gauss–Seidel existe um teorema clássico que diz que se
é estritamente diagonal dominante por linhas então tanto Jacobi quanto Gauss–Seidel convergem. Ou seja, a dominância diagonal é uma condição suficiente para convergência desses métodos. - Mas atenção importante (o ponto crítico): “apenas se” significa condição necessária. A dominância diagonal é SUFICIENTE, mas não NECESSÁRIA. Existem muitas matrizes que não são estritamente diagonalmente dominantes e, mesmo assim, métodos iterativos (p.ex. Gauss–Seidel ou métodos de Krylov) convergem.
- Exemplo/construção ilustrativa (contraexemplo de necessidade): considere uma matriz simétrica definida positiva que não seja estritamente diagonal dominante em todas as linhas; por exemplo
Aqui a primeira linha tem
e
, logo não é estritamente dominante na primeira linha. Ainda assim
é simétrica definida positiva (os menores principais são positivos) e sabe-se que Gauss–Seidel converge para qualquer sistema com
simétrica definida positiva. Portanto não é verdade que a convergência só ocorre quando há dominância estrita.
- Conclusão sobre a afirmação 1: falsa. (Dominância estrita é uma condição útil e simples de verificar que garante convergência para certos métodos, mas não é a única situação em que os métodos convergem.)]
Passo 4
Analisando a afirmação 2: “São particularmente úteis quando a matriz dos coeficientes é esparsa.”
- O que é matriz esparsa: matriz com a grande maioria dos elementos iguais a zero. Em problemas grandes (p.ex. discretizações de PDEs, malhas em engenharia) as matrizes têm
entradas não nulas em vez de . - Por que métodos iterativos são úteis para esparsidade:
- Cada iteração normalmente exige apenas produtos matriz-vetor
. Se for esparsa, esse produto custa proporcional ao número de entradas não nulas (nnz), que pode ser muito menor que . - Métodos diretos (LU, eliminação de Gauss) tendem a gerar preenchimento (“fill-in”) e a exigir memória e tempo grandes para matrizes muito grandes e esparsas; já os iterativos evitam esse preenchimento e só acessam as entradas não nulas.
- Métodos de Krylov (CG, GMRES, BiCGSTAB, etc.) são projetados para grandes sistemas esparsos e possuem ótimo custo por iteração e por armazenamento.
- Cada iteração normalmente exige apenas produtos matriz-vetor
- Conclusão sobre a afirmação 2: verdadeira. Iterativos são particularmente indicados para matrizes esparsas.
Passo 5
Analisando a afirmação 3: “Convergem sempre que houver solução para o sistema linear.”
- Ter solução (existência) do sistema
não implica nada automático sobre o raio espectral da matriz de iteração . Convergência depende de , que depende da decomposição escolhida (p.ex. Jacobi, Gauss–Seidel, SOR) e das propriedades de , não apenas da existência de solução. - Contraexemplo conceitual simples: podemos ter um sistema com solução única (matriz
invertível), mas escolher uma iteração cujo tem . Nesse caso, a iteração diverge apesar do sistema ter solução única. Por exemplo, se a diagonal de for muito pequena comparada aos termos fora da diagonal, a iteração de Jacobi pode ter e não convergir. - Portanto a existência de solução não garante convergência de um método iterativo específico.
- Conclusão sobre a afirmação 3: falsa.
Passo 6
Analisando a afirmação 4: “Produzem soluções exatas.”
- Em geral, métodos iterativos produzem aproximações sucessivas
que tendem à solução verdadeira quando convergem. Na prática usamos um critério de parada (resíduo pequeno, ou diferença entre iterações pequena) e aceitamos uma aproximação dentro de tolerância. - Observação técnica importante (caveat): alguns métodos de Krylov (por exemplo Conjugate Gradient para matrizes simétricas definidas positivas) têm a propriedade teórica de atingir a solução exata em, no máximo,
iterações em aritmética exata (onde é a dimensão do sistema), porque eles constroem subespaços de Krylov e a solução é alcançada em um subespaço de dimensão finita. Porém: - Isso é em aritmética exata (sem erros de arredondamento). Na prática, devido a erros numéricos de ponto flutuante, eles raramente retornam a solução exata em
passos e, mesmo que retornassem, isso pode ser impraticável para grande. - A grande maioria dos usos dos métodos iterativos visa aproximar a solução com custo menor do que um método direto, não obter “exatidão” no sentido de números exatos.
- Isso é em aritmética exata (sem erros de arredondamento). Na prática, devido a erros numéricos de ponto flutuante, eles raramente retornam a solução exata em
- Conclusão sobre a afirmação 4: em sentido geral é falsa (produzem aproximações). A afirmação seria enganosa sem o contexto do caso teórico especial; portanto consideramos a afirmação como falsa.
Passo 7
Analisando a afirmação 5: “Convergem apenas se a matriz dos coeficientes for bem condicionada.”
- O condicionamento (número de condição
para alguma norma) mede sensibilidade da solução a perturbacões nos dados; um grande indica que pequenas perturbações em ou erros de arredondamento podem causar grandes variações em . - Relação com métodos iterativos:
- O condicionamento afeta tipicamente a velocidade de convergência e a precisão alcançável: sistemas mal condicionados tendem a causar convergência mais lenta e maior sensibilidade a ruído/erros numéricos.
- Contudo, mal condicionamento não impede necessariamente convergência: dependendo do método e das propriedades da matriz de iteração
, pode-se ter mesmo com mal condicionada. Em suma, condicionamento influencia o desempenho (taxa de convergência e estabilidade numérica), mas não é uma condição necessária para convergência. - Além disso, técnicas de pré-condicionamento são precisamente usadas para melhorar o condicionamento efetivo visto pelo método iterativo e acelerar a convergência.
- Conclusão sobre a afirmação 5: falsa. A matriz não precisa ser “bem condicionada” para que exista convergência; porém bom condicionamento (ou pré-condicionamento) geralmente torna a convergência muito mais prática.
Passo 8
Resumo rápido e motivacional (pra você lembrar na hora da prova):
- Regra prática: verifique o raio espectral da matriz de iteração ou use condições suficientes conhecidas (dominância diagonal, simetria definida positiva, propriedades de M) para garantir convergência.
- Lembre que métodos iterativos são sua arma quando
é grande e esparsa; eles dão aproximações sucessivas e você controla a precisão com critério de parada. - Não confunda condições suficientes com necessárias: “apenas se” é quase sempre armadilha em questões teóricas.