O Método SOR (Successive Over-Relaxation)
O método SOR é uma técnica iterativa para resolver sistemas lineares da forma \(A\mathbf{x} = \mathbf{b}\), onde \(A\) é uma matriz \(n \times n\) e \(\mathbf{x}, \mathbf{b} \in \mathbb{R}^n\). É uma extensão do método de Gauss-Seidel que introduz um parâmetro de relaxação \(\omega\) para acelerar a convergência.
Dada a decomposição \(A = D - L - U\), onde:
• \(D\) = matriz diagonal de \(A\)
• \(-L\) = parte triangular inferior estrita
• \(-U\) = parte triangular superior estrita
Formulação do Método
A iteração do SOR é dada por:
\((D - \omega L)\mathbf{x}^{(k+1)} = [(1-\omega)D + \omega U]\mathbf{x}^{(k)} + \omega\mathbf{b}\)
Em forma componente a componente:
\(x_i^{(k+1)} = (1-\omega)x_i^{(k)} + \frac{\omega}{a_{ii}} \left( b_i - \sum_{j=1}^{i-1} a_{ij}x_j^{(k+1)} - \sum_{j=i+1}^{n} a_{ij}x_j^{(k)} \right)\)
📚 Teorema de Convergência (Kahan, 1958)
Se o método SOR converge para algum \(\mathbf{x}^*\) independente da aproximação inicial \(\mathbf{x}^{(0)}\), então necessariamente:
\(0 < \omega < 2\)
Esta é uma condição necessária para convergência.
Corolário: Se \(A\) é estritamente diagonal dominante por linhas, então o método SOR converge para todo \(\omega\) tal que \(0 <\omega \leq 1.\)
Interpretação do Parâmetro ω
O parâmetro ω controla o nível de relaxação:
- ω = 1: Recupera o método de Gauss-Seidel puro
- 1 < ω < 2: Sobrerrelaxação (acelera convergência quando Gauss-Seidel é lento)
- 0 < ω < 1: Sub-relaxação (estabiliza iterações divergentes)
📝 Algoritmo SOR
- Escolha aproximação inicial \(\mathbf{x}^{(0)}\) (padrão: vetor nulo)
- Para k = 0, 1, 2, ... até convergência:
- Para i = 1 até n:
- Calcule soma1 = \(\sum_{j=1}^{i-1} a_{ij}x_j^{(k+1)}\)
- Calcule soma2 = \(\sum_{j=i+1}^{n} a_{ij}x_j^{(k)}\)
- \(x_i^{(k+1)} = (1-\omega)x_i^{(k)} + \frac{\omega}{a_{ii}}(b_i - \text{soma1} - \text{soma2})\)
- Critério de parada: \(\|\mathbf{x}^{(k+1)} - \mathbf{x}^{(k)}\|_\infty < \varepsilon\)
Valor Ótimo de ω
Para matrizes tridiagonais simétricas definidas positivas, o valor ótimo que minimiza o raio espectral é:
\(\omega_{\text{opt}} = \frac{2}{1 + \sqrt{1 - \rho(J)^2}}\)
onde \(\rho(J)\) é o raio espectral do método de Jacobi associado.
💡 Dicas Práticas
1. Para sistemas com dominância diagonal, ω ≈ 1.2–1.5 geralmente funciona bem
2. Teste diferentes valores de ω para encontrar o que dá convergência mais rápida
3. Valores muito próximos de 2 podem causar instabilidade
4. Sempre verifique se \(|1-\omega| < 1\) para garantir possibilidade de convergência
5. A aproximação inicial pode ser qualquer vetor; por praticidade, geralmente usa-se o vetor nulo