Dada uma aproximação inicial ${𝒙}^0$, o método de Jacobi é o método de relaxação que consiste nas iterações

para $k=\mathrm{0,1,2},\mathrm{\cdots },n_{\text{itmax}}$, onde $n_{\text{itmax}}$ é o número máximo de iterações permitido.

Dada uma aproximação inicial ${𝒙}^0$, o método de Gauss-Seidel é o método de relaxação que consiste nas iterações

para $k=\mathrm{0,1,2},\mathrm{\cdots },n_{\text{itmax}}$, onde $n_{\text{itmax}}$ é o número máximo de iterações permitido.

Dada uma aproximação inicial ${𝒙}^{(0)}$, os métodos de Jacobi e de Gauss-Seidel têm ambos a forma iterada

proveniente de uma decomposição (do tipo splitting) da matriz $A$, i.e.

De fato, $M=D$ para o método de Jacobi e $M=D-L$ para o método de Gauss-Seidel.

A ideia do método de Sobre-Relaxação de Gauss-Seidel (SOR) é introduzir um fator de relaxação $\omega >0$ na iteração acima, baseada na decomposição

o que leva às iterações do método SOR

para $k=\mathrm{0,1,2},\mathrm{\cdots },n_{\text{itmax}}$, onde $n_{\text{itmax}}$ é o número máximo de iterações permitido.

Dada uma aproximação inicial ${𝒙}^{(0)}$, o método de Sobre-Relaxação de Gauss-Seidel Simétrico (SSOR) é o método de relaxação que consiste nas iterações

para $k=\mathrm{0,1,2},\mathrm{\cdots },n_{\text{itmax}}$, onde $n_{\text{itmax}}$ é o número máximo de iterações permitido.

Dada a decomposição da matriz

para algum método de relaxação, temos que a iteração

pode ser escrita como

onde $G=M^{-1}N$ e $𝒄=M^{-1}𝒃$ são chamados de matriz e vetor de iteração, respectivamente. Por exemplo, para o método de Jacobi, temos

e, para o método de Gauss-Seidel, temos

A iteração (1.100) pode ser vista como uma iteração de ponto fixo para resolver o sistema linear

Observando que

vemos que o sistema é equivalente ao sistema original $A𝒙=𝒃$ precondicionado à esquerda por $M$, i.e.

As precondicionadoras de Jacobi (JA), Gauss-Seidel (GS), SOR e SSOR são, portanto, respectivamente

Como observado anteriormente, os métodos de relaxação podem ser escritos na forma

onde $G=M^{-1}N$ e $𝒄=M^{-1}𝒃$ são a matriz e o vetor de iteração do método obtido a partir de uma decomposição $A=M-N$.

Vamos analisar alguns aspectos sobre a convergência das iterações (1.110).

1. a)

   Se a iteração (1.110) converge para qualquer aproximação inicial ${𝒙}^{(0)}$, então, converge para a solução do sistema linear original $A𝒙=𝒃$?

   Se a iteração (1.110) converge, então, existe ${𝒙}^{(k)}\to {𝒙}^{\ast }$ é tal que

   $${𝒙}^{\ast }=G{𝒙}^{\ast }+𝒄.$$

   (1.111)

   Assim, temos

   $$(I-G){𝒙}^{\ast }=𝒄.$$

   (1.112)

   Como $I-G=M^{-1}A$ e $𝒄=M^{-1}𝒃$, temos

   $$M^{-1}A{𝒙}^{\ast }=M^{-1}𝒃,$$

   (1.113)

   o que implica que $A{𝒙}^{\ast }=𝒃$, ou seja, ${𝒙}^{\ast }$ é a solução do sistema linear original.

2. b)

   Sobre quais condições a iteração (1.110) converge para qualquer aproximação inicial ${𝒙}^{(0)}$?

   Pode-se mostrar que a iteração (1.110) converge para qualquer aproximação inicial ${𝒙}^{(0)}$, se $(I-G)$ for não singular e o raio espectral de $G$ for estritamente menor que 1, i.e. . Outro importante resultado é uma consequência do teorema de Gershgorin¹⁴¹⁴endnote: ¹⁴Semyon Aronovich Gershgorin, 1901 - 1933, matemático russo-soviético. Fonte: Wikipedia.. Temos que os métodos de Jacobi e de Gauss-Seidel convergem para qualquer aproximação inicial ${𝒙}^{(0)}$, se $A$ for estritamente diagonal dominante, i.e. se

   $$|a_{ii}|>\sum _{\begin{array}{c}j=1\\ j\ne i\end{array}}^n|a_{ij}|,$$

   (1.114)

   para todo $i=\mathrm{1,2},\mathrm{\cdots },n$. Ainda, se $A$ for simétrica positiva definida e , então, o método SOR converge para qualquer aproximação inicial ${𝒙}^{(0)}$.

3. c)

   Quando a iteração (1.110) converge, qual é a taxa de convergência?

   Do fato dos métodos de relaxação serem iterações de ponto fixo (1.110), temos que a taxa de convergência é linear e dada por

   	$\Vert {𝒙}^{k+1}-{𝒙}^k\Vert \le \Vert G\Vert \Vert {𝒙}^k-{𝒙}^{k-1}\Vert$		(1.115)
   	$\le \parallel G{\parallel }^k\parallel {𝒙}^1-{𝒙}^0\parallel .$		(1.116)

   Lembrando que $\rho (G)\le \Vert G\Vert$ para qualquer norma natural, temos que a taxa de convergência é governada por $\rho (G)$, i.e.

   $$\Vert {𝒙}^{k+1}-{𝒙}^k\Vert ⪅\rho {(G)}^k\Vert {𝒙}^1-{𝒙}^0\Vert .$$

   (1.117)