4.7 Métodos iterativos para sistemas lineares

---

Na seção anterior, tratamos de métodos diretos para a resolução de sistemas lineares. Em um método direto (por exemplo, solução via fatoração LU) obtemos uma aproximação da solução depois de realizarmos um número finito de operações (só teremos a solução ao final do processo).

Veremos nessa seção dois métodos iterativos básicos para obter uma aproximação para a solução de um sistema linear. Geralmente em um método iterativo, iniciamos com uma aproximação para a solução (que pode ser ruim) e vamos melhorando essa aproximação através de sucessivas iterações.

4.7.1 Método de Jacobi

---

O método de Jacobi pode ser obtido a partir do sistema linear $$\begin{array}{rcll}{a}_{11}{x}_1+a_{12}{x}_2+\cdots +a_{1n}{x}_n& =& y_1& \text{(4.181)}\\ a_{21}{x}_1+a_{22}{x}_2+\cdots +a_{2n}{x}_n& =& y_2& \text{(4.182)}\\ & ⋮& & \text{(4.183)}\\ a_{n1}{x}_1+a_{n2}{x}_2+\cdots +a_{nn}{x}_n& =& y_n& \text{(4.184)}\end{array}$$

Isolando o elemento $x_1$ da primeira equação temos

$$x_1^{\left(k+1\right)}=\frac{y_1-\left(a_{12}{x}_2^{\left(k\right)}+\cdots +a_{1n}{x}_n^{\left(k\right)}\right)}{a_{11}}$$

(4.185)

Note que utilizaremos os elementos $x_i^{\left(k\right)}$ da iteração $k$ (a direita da equação) para estimar o elemento $x_1$ da próxima iteração.

Da mesma forma, isolando o elemento $x_i$ de cada equação $i$, para todo $i=2,...,n$ podemos construir a iteração $$\begin{array}{rcll}{x}_1^{\left(k+1\right)}& =& \frac{y_1-\left(a_{12}{x}_2^{\left(k\right)}+\cdots +a_{1n}{x}_n^{\left(k\right)}\right)}{a_{11}}& \text{(4.186)}\\ x_2^{\left(k+1\right)}& =& \frac{y_2-\left(a_{21}{x}_1^{\left(k\right)}+a_{23}{x}_3^{\left(k\right)}+\cdots +a_{2n}{x}_n^{\left(k\right)}\right)}{a_{22}}& \text{(4.187)}\\ & ⋮& & \text{(4.188)}\\ x_n^{\left(k+1\right)}& =& \frac{y_2-\left(a_{n1}{x}_1^{\left(k\right)}+\cdots +a_{n,n-2}{x}_{n-2}^{\left(k\right)}+a_{n,n-1}{x}_{n-1}^{\left(k\right)}\right)}{a_{nn}}& \text{(4.189)}\end{array}$$

Em notação mais compacta, o método de Jacobi consiste na iteração $$\begin{array}{rcll}{x}^{\left(1\right)}& =& \text{aproximação inicial}& \text{(4.190)}\\ x_i^{\left(k+1\right)}& =& \left(y_i-\sum _{\begin{array}{c}j=1\\ j\ne i\end{array}}^n{a}_{ij}{x}_j^{\left(k\right)}\right)∕a_{ii}& \text{(4.191)}\end{array}$$

Código GNU Octave: Método de Jacobi

---

4.7.2 Método de Gauss-Seidel

---

Assim, como no método de Jacobi, no método de Gauss-Seidel também isolamos o elemento $x_i$ da equação $i$. Porém perceba que a equação para $x_2^{\left(k+1\right)}$ depende de $x_1^{\left(k\right)}$ na iteração $k$. Intuitivamente podemos pensar em usar $x_1^{\left(k+1\right)}$ que acabou de ser calculado e temos

$$x_2^{\left(k+1\right)}=\frac{y_2-\left(a_{21}{x}_1^{\left(k+1\right)}+a_{23}{x}_3^{\left(k\right)}+\cdots +a_{2n}{x}_n^{\left(k\right)}\right)}{a_{22}}$$

(4.201)

Aplicando esse raciocínio, podemos construir o método de Gauss-Seidel como $$\begin{array}{rcll}{x}_1^{\left(k+1\right)}& =& \frac{y_1-\left(a_{12}{x}_2^{\left(k\right)}+\cdots +a_{1n}{x}_n^{\left(k\right)}\right)}{a_{11}}& \text{(4.202)}\\ x_2^{\left(k+1\right)}& =& \frac{y_2-\left(a_{21}{x}_1^{\left(k+1\right)}+a_{23}{x}_3^{\left(k\right)}+\cdots +a_{2n}{x}_n^{\left(k\right)}\right)}{a_{22}}& \text{(4.203)}\\ & ⋮& & \text{(4.204)}\\ x_n^{\left(k+1\right)}& =& \frac{y_2-\left(a_{n1}{x}_1^{\left(k+1\right)}+\cdots +a_{n\left(n-1\right)}{x}_{n-1}^{\left(k+1\right)}\right)}{a_{nn}}& \text{(4.205)}\end{array}$$

Em notação mais compacta, o método de Gauss-Seidel consiste na iteração: $$\begin{array}{rcll}{x}^{\left(1\right)}& =& \text{aproximação inicial}& \text{(4.206)}\\ x_i^{\left(k+1\right)}& =& \frac{y_i-\sum _{j=1}^{i-1}{a}_{ij}{x}_j^{\left(k+1\right)}-\sum _{j=i+1}^n{a}_{ij}{x}_j^{\left(k\right)}}{a_{ii}}& \text{(4.207)}\end{array}$$

Código GNU Octave: Método de Gauss-Seidel

---

4.7.3 Análise de convergência

---

Nesta seção, analisamos a convergência de métodos iterativos para solução de sistema lineares. Para tanto, consideramos um sistema linear $Ax=b$, onde $A={\left[a_{i,j}\right]}_{i,j=1}^{n,n}$ é a matriz (real) dos coeficientes, $b={\left(a_j\right)}_{j=1}^n$ é um vetor dos termos constantes e $x={\left(x_j\right)}_{j=1}^n$ é o vetor incógnita. No decorrer, assumimos que $A$ é uma matriz não singular.

Geralmente, métodos iterativos são construídos como uma iteração de ponto fixo. No caso de um sistema linear, reescreve-se a equação matricial em um problema de ponto fixo equivalente, isto é:

$$Ax=b\iff x=Tx+c,$$

(4.216)

onde $T={\left[t_{i,j}\right]}_{i,j=1}^{n,n}$ é chamada de matriz da iteração e $c={\left(c_j\right)}_{j=1}^n$ de vetor da iteração. Construídos a matriz $T$ e o vetor $c$, o método iterativo consiste em computar a iteração:

$$x^{\left(k+1\right)}=T{x}^{\left(k\right)}+c,n\ge 1,$$

(4.217)

onde $x^{\left(1\right)}$ é uma aproximação inicial dada.

A fim de construirmos as matrizes e os vetores de iteração do método de Jacobi e de Gauss-Seidel, decompomos a matriz $A$ da seguinte forma:

$$A=L+D+U,$$

(4.218)

onde $D$ é a matriz diagonal $D=diag\left(a_{11},a_{22},\dots ,a_{nn}\right)$, isto é:

$$D:=\left[\begin{array}{ccccc}\hfill a_{11}\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill \cdots \hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill a_{22}\hfill & \hfill 0\hfill & \hfill \cdots \hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill a_{33}\hfill & \hfill \cdots \hfill & \hfill 0\hfill \\ \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill \ddots \hfill & \hfill ⋮\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill \cdots \hfill & \hfill a_{nn}\hfill \end{array}\right],$$

(4.219)

e, respectivamente, $L$ e $U$ são as seguintes matrizes triangular inferior e superior:

$$L:=\left[\begin{array}{ccccc}\hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill \cdots \hfill & \hfill 0\hfill \\ \hfill a_{21}\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill \cdots \hfill & \hfill 0\hfill \\ \hfill a_{31}\hfill & \hfill a_{32}\hfill & \hfill 0\hfill & \hfill \cdots \hfill & \hfill 0\hfill \\ \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill \ddots \hfill & \hfill ⋮\hfill \\ \hfill a_{n1}\hfill & \hfill a_{n2}\hfill & \hfill a_{n3}\hfill & \hfill \cdots \hfill & \hfill 0\hfill \end{array}\right],U:=\left[\begin{array}{ccccc}\hfill 0\hfill & \hfill a_{12}\hfill & \hfill a_{13}\hfill & \hfill \cdots \hfill & \hfill a_{1n}\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill a_{23}\hfill & \hfill \cdots \hfill & \hfill a_{2n}\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill \cdots \hfill & \hfill a_{3n}\hfill \\ \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill \ddots \hfill & \hfill ⋮\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill \cdots \hfill & \hfill 0\hfill \end{array}\right].$$

(4.220)

Solução. A forma matricial deste sistema é $Ax=b$, onde:

$$A=\left[\begin{array}{ccc}\hfill 3\hfill & \hfill 1\hfill & \hfill -1\hfill \\ \hfill -1\hfill & \hfill -4\hfill & \hfill 1\hfill \\ \hfill 1\hfill & \hfill -2\hfill & \hfill -5\hfill \end{array}\right],x=\left[\begin{array}{c}\hfill x_1\hfill \\ \hfill x_2\hfill \\ \hfill x_3\hfill \end{array}\right]\text{e}b=\left[\begin{array}{c}\hfill 2\hfill \\ \hfill -10\hfill \\ \hfill 10\hfill \end{array}\right].$$

(4.224)

A decomposição da matriz $A$ nas matrizes $L$ triangular inferior, $D$ diagonal e $U$ triangular superior é:

$$\underset{A}{\underbrace{\left[\begin{array}{ccc}\hfill 3\hfill & \hfill 1\hfill & \hfill -1\hfill \\ \hfill -1\hfill & \hfill -4\hfill & \hfill 1\hfill \\ \hfill 1\hfill & \hfill -2\hfill & \hfill -5\hfill \end{array}\right]}}=\underset{L}{\underbrace{\left[\begin{array}{ccc}\hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill -1\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 1\hfill & \hfill -2\hfill & \hfill 0\hfill \end{array}\right]}}+\underset{D}{\underbrace{\left[\begin{array}{ccc}\hfill 3\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill -4\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill -5\hfill \end{array}\right]}}+\underset{U}{\underbrace{\left[\begin{array}{ccc}\hfill 0\hfill & \hfill 1\hfill & \hfill -1\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill \end{array}\right]}}.$$

(4.225)

Iteração de Jacobi

---

Vamos, agora, usar a decomposição discutida acima para construir a matriz de iteração $T_J$ e o vetor de iteração $c_J$ associado ao método de Jacobi. Neste caso, temos: $$\begin{array}{rcll}Ax=b& \iff & \left(L+D+U\right)x=b& \text{(4.226)}\\ & \iff & Dx=-\left(L+U\right)x+b& \text{(4.227)}\\ & \iff & x=\underset{=:T_J}{\underbrace{-D^{-1}\left(L+U\right)}}x+\underset{=:c_J}{\underbrace{D^{-1}b}}.& \text{(4.228)}\end{array}$$

Ou seja, a iteração do método de Jacobi escrita na forma matricial é:

$$x^{\left(k+1\right)}=T_J{x}^{\left(k\right)}+c_J,k\ge 1,$$

(4.229)

com $x^{\left(1\right)}$ uma aproximação inicial dada, sendo $T_J:=-D^{-1}\left(L+U\right)$ a matriz de iteração e $c_J=D^{-1}b$ o vetor da iteração.

Solução. A matriz de iteração é dada por:

$$T_J:=-D^{-1}\left(L+U\right)=-\underset{D^{-1}}{\underbrace{\left[\begin{array}{ccc}\hfill \frac{1}{3}\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill -\frac{1}{4}\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill -\frac{1}{5}\hfill \end{array}\right]}}\underset{\left(L+U\right)}{\underbrace{\left[\begin{array}{ccc}\hfill 0\hfill & \hfill 1\hfill & \hfill -1\hfill \\ \hfill -1\hfill & \hfill 0\hfill & \hfill 1\hfill \\ \hfill 1\hfill & \hfill 2\hfill & \hfill 0\hfill \end{array}\right]}}=\left[\begin{array}{ccc}\hfill 0\hfill & \hfill -\frac{1}{3}\hfill & \hfill \frac{1}{3}\hfill \\ \hfill -\frac{1}{4}\hfill & \hfill 0\hfill & \hfill \frac{1}{4}\hfill \\ \hfill \frac{1}{5}\hfill & \hfill \frac{2}{5}\hfill & \hfill 0\hfill \end{array}\right].$$

(4.230)

O vetor da iteração de Jacobi é:

$$c_J:=D^{-1}b=\underset{D^{-1}}{\underbrace{\left[\begin{array}{ccc}\hfill \frac{1}{3}\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill -\frac{1}{4}\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill -\frac{1}{5}\hfill \end{array}\right]}}\underset{b}{\underbrace{\left[\begin{array}{c}\hfill 2\hfill \\ \hfill -10\hfill \\ \hfill 10\hfill \end{array}\right]}}=\left[\begin{array}{c}\hfill \frac{2}{3}\hfill \\ \hfill \frac{5}{2}\hfill \\ \hfill -2\hfill \end{array}\right].$$

(4.231)

Iteração de Gauss-Seidel

---

A forma matricial da iteração do método de Gauss-Seidel também pode ser construída com base na decomposição $A=L+D+U$. Para tando, fazemos: $$\begin{array}{rcll}Ax=b& \iff & \left(L+D+U\right)x=b& \text{(4.232)}\\ & \iff & \left(L+D\right)x=-Ux+b& \text{(4.233)}\\ & \iff & x=\underset{=:T_G}{\underbrace{-{\left(L+D\right)}^{-1}U}}x+\underset{=:c_G}{\underbrace{{\left(L+D\right)}^{-1}b}}& \text{(4.234)}\end{array}$$

Ou seja, a iteração do método de Gauss-Seidel escrita na forma matricial é:

$$x^{\left(k+1\right)}=T_G{x}^{\left(k\right)}+c_G,k\ge 1,$$

(4.235)

com $x^{\left(1\right)}$ uma aproximação inicial dada, sendo $T_G:=-{\left(L+D\right)}^{-1}U$ a matriz de iteração e $c_J={\left(L+D\right)}^{-1}b$ o vetor da iteração.

Solução. A matriz de iteração é dada por:

$$T_G=-{\left(L+D\right)}^{-1}U=-\underset{{\left(L+D\right)}^{-1}}{\underbrace{{\left[\begin{array}{ccc}\hfill 3\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill -1\hfill & \hfill -4\hfill & \hfill 0\hfill \\ \hfill 1\hfill & \hfill -2\hfill & \hfill -5\hfill \end{array}\right]}^{-1}}}\underset{U}{\underbrace{\left[\begin{array}{ccc}\hfill 0\hfill & \hfill 1\hfill & \hfill -1\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill \end{array}\right]}}=\left[\begin{array}{ccc}\hfill 0\hfill & \hfill -\frac{1}{3}\hfill & \hfill \frac{1}{3}\hfill \\ \hfill 0\hfill & \hfill \frac{1}{12}\hfill & \hfill \frac{1}{6}\hfill \\ \hfill 0\hfill & \hfill -\frac{1}{10}\hfill & \hfill 0\hfill \end{array}\right].$$

(4.236)

O vetor da iteração de Gauss-Seidel é:

$$c_G:={\left(L+D\right)}^{-1}b=\underset{{\left(L+D\right)}^{-1}}{\underbrace{{\left[\begin{array}{ccc}\hfill 3\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill -1\hfill & \hfill -4\hfill & \hfill 0\hfill \\ \hfill 1\hfill & \hfill -2\hfill & \hfill -5\hfill \end{array}\right]}^{-1}}}\underset{b}{\underbrace{\left[\begin{array}{c}\hfill 2\hfill \\ \hfill -10\hfill \\ \hfill 10\hfill \end{array}\right]}}=\left[\begin{array}{c}\hfill \frac{2}{3}\hfill \\ \hfill \frac{7}{3}\hfill \\ \hfill -\frac{28}{10}\hfill \end{array}\right].$$

(4.237)

Condições de convergência

---

Aqui, vamos discutir condições necessárias e suficientes para a convergência de métodos iterativos. Isto é, dado um sistema $Ax=b$ e uma iteração:

$$x^{\left(k+1\right)}=T{x}^{\left(k\right)}+c,k\ge 1,$$

(4.238)

$x^{\left(1\right)}$ dado, estabelecemos condições nas quais $x^{\left(k\right)}\to x^{\ast }$, onde $x^{\ast }$ é a solução do sistema dado, isto é, $x^{\ast }=T{x}^{\ast }+c$ ou, equivalentemente, $A{x}^{\ast }=b$.

Solução. Do Teorema 4.7.1, vemos que é necessário e suficiente que $\rho \left(T_J\right)<1$ e $\rho \left(T_G\right)<1$. Computando estes raios espectrais, obtemos $\rho \left(T_J\right)\approx 0,32$ e $\rho \left(T_G\right)\approx 0,13$. Isto mostra que ambos os métodos serão convergentes.

Condição suficiente

---

Uma condição suficiente porém não necessária para que os métodos de Gauss-Seidel e Jacobi convirjam é a que a matriz seja estritamente diagonal dominante.

Se conhecermos a solução exata $x$ do problema, podemos calcular o erro relativo em cada iteração como:

$$\frac{\parallel x-x^{\left(k\right)}\parallel }{∥x∥}.$$

(4.259)

Em geral não temos $x$, entretanto podemos estimar o vetor resíduo $r^{\left(k\right)}=b-A\widetilde{x^{\left(k\right)}}$. Note que quando o erro tende a zero, o resíduo também tende a zero.

Exercícios

---