Métodos Estacionários e de Relaxamento

Métodos iterativos estacionários resolvem um sistema linear dividindo a matriz e aplicando repetidamente uma regra de atualização fixa; os esquemas clássicos de Jacobi, Gauss-Seidel e relaxamento sucessivo são os exemplos fundamentais.

Definition

Um método iterativo estacionário é aquele cuja atualização aplica a mesma matriz de iteração a cada passo, derivada de uma divisão da matriz de coeficientes em uma parte facilmente invertível e um restante; a convergência é governada pelo raio espectral da matriz de iteração resultante.

Scope

Este tópico abrange o arcabouço de divisão de matrizes, as iterações de Jacobi e Gauss-Seidel, o relaxamento sucessivo e a escolha do parâmetro de relaxamento ótimo, o critério do raio espectral para convergência, e o papel que essas iterações simples desempenham hoje como suavizadores dentro de multigrelhas e como pré-condicionadores.

Core questions

• Como a divisão da matriz produz uma iteração de ponto fixo para o sistema linear?
• Como os métodos de Jacobi e Gauss-Seidel diferem, e por que Gauss-Seidel é geralmente mais rápido?
• Como o sobrerrelaxamento acelera a convergência, e como o parâmetro ótimo é escolhido?
• Sob quais condições na matriz essas iterações convergem?

Key theories

Divisão de matrizes e o critério do raio espectral

Escrever a matriz como uma parte facilmente invertível menos um restante define uma iteração estacionária cujo erro é multiplicado por uma matriz de iteração a cada passo; a iteração converge para cada estimativa inicial se e somente se o raio espectral dessa matriz de iteração for menor que um.

Relaxamento sucessivo

Ao exceder a correção de Gauss-Seidel com um fator de relaxamento, o relaxamento sucessivo pode reduzir grandemente o raio espectral; para certas matrizes estruturadas, um parâmetro de relaxamento ótimo é conhecido analiticamente e proporciona um aumento dramático na velocidade.

Mechanisms

O método de Jacobi atualiza todas as incógnitas simultaneamente usando apenas valores da varredura anterior, equivalente a separar a diagonal. Gauss-Seidel usa os valores mais recentemente atualizados dentro da mesma varredura, separando a parte triangular inferior, o que geralmente converge mais rapidamente. O relaxamento sucessivo forma uma média ponderada do valor antigo e da atualização de Gauss-Seidel governada por um parâmetro de relaxamento; escolher este parâmetro maior que um acelera a convergência para matrizes adequadas. A convergência para todos os três é garantida para classes como matrizes estritamente diagonalmente dominantes ou simétricas definidas positivas, e é quantificada pelo raio espectral da matriz de iteração.

Clinical relevance

Embora geralmente muito lentos para serem solucionadores autônomos competitivos para grandes sistemas, os métodos estacionários permanecem importantes como suavizadores no cerne de multigrelhas, como pré-condicionadores simples para métodos de Krylov e como blocos de construção facilmente paralelizados; Gauss-Seidel e Jacobi ponderado, em particular, são ubíquos dentro de solucionadores multinível modernos.

History

As iterações de Jacobi e Gauss-Seidel datam do século XIX, enquanto o relaxamento sucessivo e sua rigorosa teoria de convergência foram desenvolvidos por David Young e Richard Varga na década de 1950; embora mais tarde ofuscadas pelos métodos de Krylov e multigrelha como solucionadores primários, essas iterações foram revividas como componentes essenciais de esquemas multinível e pré-condicionados.

Key figures

• Carl Friedrich Gauss
• Philipp Ludwig von Seidel
• David M. Young
• Richard S. Varga

Seminal works

• saad2003
• varga2000

Frequently asked questions

Por que Gauss-Seidel é geralmente mais rápido que Jacobi?

Gauss-Seidel usa imediatamente os valores atualizados dentro da mesma varredura, então a informação se propaga mais rapidamente através das incógnitas, tipicamente reduzindo pela metade o número de iterações em comparação com Jacobi, que usa apenas valores da varredura anterior.

Se esses métodos são lentos, por que ainda são estudados?

Eles são excelentes suavizadores e pré-condicionadores simples. Dentro de multigrelhas, algumas varreduras de Gauss-Seidel ou Jacobi ponderado removem eficientemente o erro oscilatório, que é exatamente o papel que a multigrelha precisa, então essas iterações clássicas continuam vivas como componentes de solucionadores modernos rápidos.