Considere o sistema de equações lineares a seguir:
\begin{cases}2 Q_{1}+0.5 Q_{2}+0.5 Q_{3} & =18 \\\\ 1 Q_{1}+6 Q_{2}+0.5 Q_{3} & =3 \\\\ 10 Q_{1}+6 Q_{2}+15 Q_{3} & =7\end{cases}
(a) Indique, através do uso dos critérios de convergência, para quais métodos iterativos o sistema acima converge.
(b) Partindo do vetor nulo, realize duas iterações do método iterativo de sua preferência. Calcule o erro relativo a cada iteração.

Passo 1

O enunciado dá o sistema linear
\begin{cases} 2 Q_{1}+0{,}5 Q_{2}+0{,}5 Q_{3}=18,\\[4pt] 1 Q_{1}+6 Q_{2}+0{,}5 Q_{3}=3,\\[4pt] 10 Q_{1}+6 Q_{2}+15 Q_{3}=7, \end{cases}
e pede duas coisas:
  1. indicar, usando critérios de convergência, para quais métodos iterativos o sistema converge;
  2. a partir do vetor nulo realizar duas iterações do método iterativo de minha preferência e calcular o erro relativo a cada iteração.
Informações relevantes fornecidas: os coeficientes da matriz do sistema e o vetor do lado direito \,[18,\;3,\;7]^{T}. A escolha do método para as iterações fica a meu critério (seguirei a justificativa nos passos seguintes).]

Passo 2

Conceitos/critério que vamos usar (explicação didática e simples):
  • Para um método iterativo linear (Jacobi, Gauss–Seidel, SOR) a convergência é equivalente a ter raio espectral da matriz de iteração menor que 1. O raio espectral de uma matriz B é \rho(B)=\max\{|\lambda|:\lambda\text{ é autovalor de }B\}é. Se \rho(B)<1, x^{(k+1)}=B x^{(k)}+c converge para a solução, qualquer que seja x^{(0)}.
  • Existem condições suficientes fáceis de verificar: se a matriz dos coeficientes é estritamente diagonalmente dominante por linhas (isto é, para cada linha i, |a_{ii}|>\sum_{j\ne i}|a_{ij}|), então Jacobi e Gauss–Seidel convergem. Porém esta condição é só suficiente, não necessária.
Vamos primeiro ver se a matriz é estritamente diagonalmente dominante por linhas. A matriz dos coeficientes é
A=\begin{pmatrix} 2 & 0{,}5 & 0{,}5\\[4pt] 1 & 6 & 0{,}5\\[4pt] 10 & 6 & 15 \end{pmatrix}.
Verificação linha a linha:
  • linha 1: |a_{11}|=2 e \sum_{j\ne1}|a_{1j}|=0{,}5+0{,}5=1, então 2>1 (estritamente dominante nessa linha);
  • linha 2: |a_{22}|=6 e \sum_{j\ne2}|a_{2j}|=1+0{,}5=1{,}5, então 6>1{,}5 (estritamente dominante);
  • linha 3: |a_{33}|=15 e \sum_{j\ne3}|a_{3j}|=10+6=16, então 15<16 (não é dominante nesta linha).
Portanto a condição de dominância estrita por linhas falha na linha 3, então não podemos concluir a convergência apenas por esse critério. Logo precisamos verificar o raio espectral das matrizes de iteração (critério necessário e suficiente). Vou calcular explicitamente as matrizes de iteração de Jacobi e de Gauss–Seidel e seus raios espectrais.]

Passo 3

Matriz de iteração de Jacobi (aula curta sobre procedimento): escrevemos A=D+R, onde D é a diagonal de A e R=A-D contém os elementos fora da diagonal. A iteração de Jacobi é
x^{(k+1)} = -D^{-1} R\, x^{(k)} + D^{-1} b,
então a matriz de iteração é B_{J}=-D^{-1}R.
Aqui
D=\operatorname{diag}(2,6,15),\qquad R=\begin{pmatrix} 0 & 0{,}5 & 0{,}5\\[4pt] 1 & 0 & 0{,}5\\[4pt] 10 & 6 & 0 \end{pmatrix}.
Logo (fazendo a multiplicação linha a linha)
B_{J}=-D^{-1}R= \begin{pmatrix} 0 & -\tfrac{1}{4} & -\tfrac{1}{4}\\[6pt] -\tfrac{1}{6} & 0 & -\tfrac{1}{12}\\[6pt] -\tfrac{2}{3} & -\tfrac{2}{5} & 0 \end{pmatrix}.
Para verificar a convergência precisamos do raio espectral \rho(B_{J}). O polinômio característico desse B_{J} (cálculo com frações para manter exatidão) é
\lambda^{3}-\frac{29}{120}\lambda+\frac{11}{360}=0,
ou multiplicando por 360,
360\lambda^{3}-87\lambda+11=0.
Resolvendo numericamente esse polinômio (procedimento explicado: testar sinais e refinar intervalos por bisseção/iteração) obtém-se três autovalores reais aproximados
\lambda_1\approx 0{,}137,\qquad \lambda_2\approx 0{,}408,\qquad \lambda_3\approx -0{,}545.
Portanto
\rho(B_{J})=\max\{|\lambda_i|\}\approx 0{,}545<1,
o que garante convergência do método de Jacobi para este sistema.]

Passo 4

Matriz de iteração de Gauss–Seidel (explicação prática): decompomos A=D+L+U com L a parte estritamente triangular inferior e U a estritamente superior. A iteração de Gauss–Seidel pode ser escrita
x^{(k+1)}=-(D+L)^{-1} U\, x^{(k)} + (D+L)^{-1} b,
logo a matriz de iteração é B_{GS}=-(D+L)^{-1}U. Para calcular B_{GS} é conveniente obter suas colunas resolvendo sistemas triangulares (cada coluna é -(D+L)^{-1} vezes a coluna correspondente de U).
Aqui
D+L=\begin{pmatrix} 2 & 0 & 0\\[4pt] 1 & 6 & 0\\[4pt] 10 & 6 & 15 \end{pmatrix},\qquad U=\begin{pmatrix} 0 & 0{,}5 & 0{,}5\\[4pt] 0 & 0 & 0{,}5\\[4pt] 0 & 0 & 0 \end{pmatrix}.
Resolvendo as colunas obtemos (trabalhando com frações exatas)
B_{GS}= \begin{pmatrix} 0 & -\tfrac{1}{4} & -\tfrac{1}{4}\\[6pt] 0 & \tfrac{1}{24} & -\tfrac{1}{24}\\[6pt] 0 & \tfrac{3}{20} & \tfrac{11}{60} \end{pmatrix}.
Note que a primeira coluna é nula porque a primeira coluna de U é nula. Por causa dessa estrutura, o cálculo do polinômio característico reduz-se ao cálculo dos autovalores do bloco 2\times2 inferior-direito:
C=\begin{pmatrix}\tfrac{1}{24} & -\tfrac{1}{24}\\[4pt]\tfrac{3}{20} & \tfrac{11}{60}\end{pmatrix}.
O determinante de C é \det\text{(C)}=\tfrac{1}{72} e a soma dos autovalores é \operatorname{tr}\text{(C)}=\tfrac{9}{40}. Como os autovalores desse 2\times2 são conjugados complexos (discriminante negativa), o módulo de cada um deles satisfaz
|\lambda|=\sqrt{\det\text{(C)}}=\sqrt{\tfrac{1}{72}}\approx 0{,}118535.
Além disso há o autovalor \lambda=0 (pela coluna nula), logo
\rho(B_{GS})\approx 0{,}118535<1.
Conclusão: Gauss–Seidel também converge (e com um fator de contração muito menor que o de Jacobi, o que significa geralmente convergência bem mais rápida).]

Passo 5

Resumo da conclusão teórica (antes de praticar): ambos os métodos Jacobi e Gauss–Seidel convergem, porque seus raios espectrais são menores que 1 ( \rho(B_J)\approx0{,}545 e \rho(B_{GS})\approx0{,}1185). Vou escolher Gauss–Seidel para as iterações praticadas porque converge mais rápido (menor \rho) — isso facilita ver redução do erro já em poucas iterações.

Passo 6

Cálculo da solução exata (preciso para medir erro relativo). Resolvendo o sistema por eliminação (passos com frações):
a partir de Q_{1}=9-\tfrac{1}{4}Q_{2}-\tfrac{1}{4}Q_{3}\) e substituindo nas outras equações obtemos o sistema reduzido \[\begin{cases} 23 Q_{2}+Q_{3}=-24,\\[4pt] 7 Q_{2}+25 Q_{3}=-166. \end{cases}
Resolvendo esse (2\times2] dá
Q_{2}=-\tfrac{217}{284}\approx -0{,}764084507,\qquad Q_{3}=-\tfrac{1825}{284}\approx -6{,}426056338.
Então
Q_{1}=9-\tfrac{1}{4}Q_{2}-\tfrac{1}{4}Q_{3}=\tfrac{6133}{568}\approx 10{,}797535211.
Portanto a solução exata é
x^{*}=\begin{pmatrix}\tfrac{6133}{568}\\[4pt]-\tfrac{217}{284}\\[4pt]-\tfrac{1825}{284}\end{pmatrix} \approx\begin{pmatrix}10{,}79753521\\[4pt]-0{,}76408451\\[4pt]-6{,}42605634\end{pmatrix}.]

Passo 7

Gauss–Seidel: fórmula de iteração componente a componente (explicação breve)
a cada iteração k atualizamos sequencialmente
\begin{aligned} Q_{1}^{(k+1)} &= \frac{1}{2}\Big(18-0{,}5\,Q_{2}^{(\text{uso})}-0{,}5\,Q_{3}^{(\text{uso})}\Big),\\[4pt] Q_{2}^{(k+1)} &= \frac{1}{6}\Big(3 -1\cdot Q_{1}^{(k+1)} -0{,}5\,Q_{3}^{(\text{uso})}\Big),\\[4pt] Q_{3}^{(k+1)} &= \frac{1}{15}\Big(7 -10\cdot Q_{1}^{(k+1)} -6\cdot Q_{2}^{(k+1)}\Big), \end{aligned}
onde “ Q^{(\text{uso})}” significa que, ao atualizar um componente, usamos os valores mais recentes disponíveis (Gauss–Seidel).
Começando de x^{(0)}=(0,0,0)^{T}:
Iteração 1:
  • Q_{1}^{(1)}=\tfrac{1}{2}(18-0-0)=9.
  • Q_{2}^{(1)}=\tfrac{1}{6}(3-9-0)=\tfrac{1}{6}(-6)=-1.
  • Q_{3}^{(1)}=\tfrac{1}{15}(7-10\cdot9-6\cdot(-1))=\tfrac{1}{15}(7-90+6)=\tfrac{-77}{15}\approx -5{,}13333333.
Logo
x^{(1)}=\begin{pmatrix}9\\[4pt]-1\\[4pt]-\tfrac{77}{15}\end{pmatrix} \approx\begin{pmatrix}9{,}000000\\[4pt]-1{,}000000\\[4pt]-5{,}133333\end{pmatrix}.
Erro relativo (definição e escolha de norma): vou usar a norma infinito para medir o erro relativo, ou seja
\text{erro relativo}=\frac{\|x^{(k)}-x^{*}\|_{\infty}}{\|x^{*}\|_{\infty}},
porque é fácil de calcular e é um padrão comum em análises de iteração. A norma infinito é \|v\|_{\infty}=\max_{i}|v_{i}|.
Cálculo para k=1:
  • diferença x^{(1)}-x^{*} tem componentes aproximados (-1{,}79753521,\,-0{,}23591549,\;1{,}29272300),
  • \|x^{(1)}-x^{*}\|_{\infty}\approx 1{,}79753521,
  • \|x^{*}\|_{\infty}=\max(|10{,}7975|,| -0{,}7641|,| -6{,}4261|)=10{,}79753521.
    Logo erro relativo após a 1ª iteração
\frac{1{,}79753521}{10{,}79753521}\approx 0{,}16647\quad(\approx 16{,}647\%).]

Passo 8

Iteração 2 (continuação Gauss–Seidel):
Usamos x^{(1)} para atualizar:
  • Q_{1}^{(2)}=\tfrac{1}{2}\big(18-0{,}5\cdot(-1)-0{,}5\cdot(-\tfrac{77}{15})\big) = \tfrac{1}{2}\big(18+0{,}5+\tfrac{77}{30}\big) =10{,}533333333.
  • Q_{2}^{(2)}=\tfrac{1}{6}\big(3 - Q_{1}^{(2)} -0{,}5\cdot Q_{3}^{(1)}\big) = \tfrac{1}{6}\big(3-10{,}53333333 -0{,}5\cdot(-5{,}13333333)\big) \approx -0{,}8277777777.
  • Q_{3}^{(2)}=\tfrac{1}{15}\big(7 -10\cdot Q_{1}^{(2)} -6\cdot Q_{2}^{(2)}\big) \approx -6{,}224444444.
Assim
x^{(2)}\approx\begin{pmatrix}10{,}53333333\\[4pt]-0{,}82777778\\[4pt]-6{,}22444444\end{pmatrix}.
Cálculo do erro relativo para k=2:
  • diferença x^{(2)}-x^{*} tem componentes aproximados (-0{,}26420188,\,-0{,}06369327,\;0{,}20161189),
  • \|x^{(2)}-x^{*}\|_{\infty}\approx 0{,}26420188,
  • \|x^{*}\|_{\infty} continua =10{,}79753521.
Logo o erro relativo após a 2ª iteração é
\frac{0{,}26420188}{10{,}79753521}\approx 0{,}02448\quad(\approx 2{,}448\%).]

Resposta

(a) O sistema converge tanto pelo método de Jacobi quanto pelo método de Gauss–Seidel (os raios espectrais são aproximadamente \rho(B_{J})\approx 0{,}545<1 e \rho(B_{GS})\approx 0{,}1185<1).
(b) Usando Gauss–Seidel com x^{(0)}=(0,0,0)^{T}:
x^{(1)}=\displaystyle\begin{pmatrix}9\\[4pt]-1\\[4pt]-\tfrac{77}{15}\end{pmatrix}\approx\begin{pmatrix}9{,}000000\\[4pt]-1{,}000000\\[4pt]-5{,}133333\end{pmatrix}, erro relativo \approx 0{,}16647.
x^{(2)}\approx\displaystyle\begin{pmatrix}10{,}53333333\\[4pt]-0{,}82777778\\[4pt]-6{,}22444444\end{pmatrix}, erro relativo \approx 0{,}02448.]

Exercícios relacionados