Convergência de métodos iterativos

Por método iterativo quero dizer um método que, partindo de um aproximação corrente, produz uma nova aproximação, na expectativa de que a sequência de aproximações convirja à solução do problema.

Quando o problema é resolver o sistema linear $Ax=b,$ a aproximação inicial deve ser um vetor $x^{0}.$ O que caracteriza o método iterativo é a forma como evoluímos a aproximação corrente para a nova aproximação. Isto é representado por uma função de iteração, denotada por $\phi:\mathbb{R}^n\rightarrow\mathbb{R}^n.$ Com isto, \begin{equation}\label{sl12-eq1} x^{(k+1)}=\phi(x^k), \quad k \ge 0. \end{equation}

Vamos nos concentrar no caso em que a função de iteração tem a seguinte forma \begin{equation}\label{sl12-eq2} \phi(x) = Bx+c, \end{equation} onde $B$ é uma matriz e $c$ um vetor, ambos fixos durante todo o processo. Métodos definidos desta forma são ditos métodos estacionários.

O método iterativo iteração após iteração melhora a aproximação atual. Se $x^*$ é a solução do sistema linear, nada mais há que melhorar, e portanto o esperado é que \begin{equation}\label{sl12-eq3} \phi(x^*) = x^*. \end{equation} Para a função $\phi,$ $x^*$ é dito um ponto fixo (lembre que já vimos isso antes, no estudo de equações não lineares, aqui e aqui). Todos os métodos iterativos precisam satisfazer essa propriedade, isto é, todas as funções de iteração precisam ter como ponto fixo a solução do sistema linear. Essa condição, apesar de necessária para a convergência do método, certamente não é suficiente. Considere o exemplo em que $B=I$ e $c=0.$ A função de iteração seria dada por $\phi(x)=Ix+0 = x.$ Claro que $\phi(x^*)=x^*,$ mas evidentemente essa função não tem a capacidade de gerar uma sequência que convirja a $x^*,$ quando começar em qualquer outro ponto.

Além da condição de ponto fixo, que outras condições serão necessárias para assegurar convergência? Vamos definir claramente o que entendemos por convergência. Se $x^k$ é a $k$-ésima aproximação, o vetor erro associado é definido como $e^k = x^k - x^*.$ Diremos que a sequência gerada pelo método é convergente se $$ \lim_{k\to\infty}\|e^k\| = 0, $$ onde $\|x\|$ representa alguma norma do vetor $x.$ Estamos acostumados com a norma euclidiana (ou norma dois), dada por $$ \|x\|_2 = \sqrt{x_1^2+x_2^2+\cdots+x_n^2}, $$ mas há infinitas outras opções que podemos usar, como por exemplo a norma 1, $$ \|x\|_1 = |x_1| +|x_2|+\cdots+|x_n|,$$ ou ainda a norma infinito, $$ \|x\|_\infty = \max\{|x_1|,|x_2|,\ldots,|x_n|\}.$$

Vejamos como relacionar o erro no passo $k,$ com o erro no passo anterior. \begin{align*} e^k & = x^k - x^* \\ & = \phi(x^{(k-1)}) - \phi (x^*) \\ & = (Bx^{(k-1)} +c) - (Bx^* + c) \\ & = B (x^{(k-1)} - x^*) \\ & = B e^{(k-1)}, \end{align*} onde usamos \eqref{sl12-eq1}, \eqref{sl12-eq2} e \eqref{sl12-eq3}. De forma análoga, o mesmo desenvolvimento pode ser feito para $e^{(k-1)}.$ Não é difícil ver que teremos $$ e^k = B^k e^{0}. $$ Como a convergência se avalia sobre a norma do erro, veja que $$ \|e^k\| = \|B^ke^{0}\| \le \|B^k\|\|e^{0}\|\le \|B\|^k \,\|e^{0}\|, $$ onde usamos duas propriedades para normas matriciais e vetoriais, a saber, $$ \|Mx\| \le \|M\| \|x\|, \quad \mbox{e} \quad \|M^k\| \le \|M\|^k. $$ onde $M$ é uma matriz quadrada e $x$ um vetor. Se quiser saber mais sobre normas para matrizes e estas propriedades, veja essa aula.

Finalmente chegamos ao resultado que procurávamos. Para que $\|e^k\|\rightarrow 0,$ bastará pedir que a matriz $B$ seja tal que $\|B\| \lt 1.$ Com isto teremos que $$ 0 \le \lim_{k\rightarrow \infty} \|e^k\| \le \lim_{k\rightarrow \infty} \|B\|^k \,\|e^{0}\| = 0,$$ uma vez que $\|B\|\lt 1.$ Em resumo, demostramos o seguinte resultado.

Teorema: Seja $x^*,$ ponto fixo de $\phi(x) = Bx+c,$ onde $B$ é uma matriz quadrada com $\|B\|\lt 1$ e $c$ um vetor, ambos fixos. Então, a sequência gerada pela iteração \eqref{sl12-eq1} converge para $x^*.$

Observe que o teorema não especifica a norma matricial. Basta que a matriz tenha alguma norma menor que 1, para que haja convergência nessa norma. Outro resultado (equivalência de normas em espaços de dimensão finita) garante que a convergência em uma norma implicará na convergência em todas as outras normas.

O que nos resta é traduzir este resultado geral para cada método iterativo particular, como os métodos de Gauss-Jacobi e Gauss-Seidel, identificando quem é a matriz $B$ e o vetor $c$ em cada um deles, e o que a condição $\|B\|\lt 1$ implica para cada método. Este será o assunto da próxima aula.

Referência

C.T. Kelley. Iterative Methods for Linear and Nonlinear Equations. SIAM. 1995.

1. Para o sistema linear $Ax=b,$ método iterativo de Richardson é definido por $B=(I-A)$ e $c=b,$ ou seja, a função de iteração é $\phi(x) = (I-A)x+b.$ Aplique o método de Richardson aos sistemas lineares abaixo.

1. $\left[\begin{array}{rr} 1.2 & 0.5 \\ 0.3 & 0.8 \end{array}\right]x = \left[\begin{array}{r}-2.6 \\ 0.7\end{array}\right]$
2. $\left[\begin{array}{rr} 1.5 & 1.0 \\ 0.2 & 1.4 \end{array}\right]x = \left[\begin{array}{r}-2.5 \\ 2.2\end{array}\right]$
3. $\left[\begin{array}{rr} 1.5 & 1.0 \\ 3.0 & 1.4 \end{array}\right]x = \begin{bmatrix}-2.5 \\ -6.2\end{bmatrix}$

O método produziu uma sequência convergente? A convergência depende da aproximação inicial? Tente quantificar a taxa de convergência.