Problema 5 Seja o sistema
\left[\begin{array}{ccc} 10 & -1 & 4 \\\\ 1 & 10 & 9 \\\\ 2 & -3 & -10 \end{array}\right]\left[\begin{array}{l} x_{1} \\\ x_{2} \\\ x_{3} \end{array}\right]=\left[\begin{array}{l} 5 \\\\ 2 \\\\ 9 \end{array}\right]
(a) Verifique quais dos métodos, Gauss-Jacobi e Gauss-Seidel, garante convergência.
(b) Utilizando um dos métodos que garante convergência, determinar a solução do sistema, com 3 iterações.
(c) Determinar a estimativa do erro.

Passo 1

O enunciado dá o sistema linear
\begin{pmatrix} 10 & -1 & 4\\[4pt] 1 & 10 & 9\\[4pt] 2 & -3 & -10 \end{pmatrix} \begin{pmatrix}x_1\\[4pt]x_2\\[4pt]x_3\end{pmatrix} = \begin{pmatrix}5\\[4pt]2\\[4pt]9\end{pmatrix},
e pede três coisas:
(a) Verificar quais dos métodos iterativos Gauss–Jacobi e Gauss–Seidel garantem convergência para este sistema.
(b) Usando um dos métodos que garante convergência, determinar a solução obtida após 3 iterações. (Vou usar a escolha padrão de chute inicial \mathbf{x}^{(0)}=(0,0,0)^\top, já que o enunciado não diz outro.)
(c) Determinar uma estimativa do erro (vou apresentar estimativas a priori e a posteriori e, para comparação, o erro real se for possível computá-lo).
As informações relevantes que temos são a matriz A e o vetor b acima; nada mais foi pedido explicitamente.]

Passo 2

Explicando os métodos (de forma prática e curta, para usar na prova).
  • Decompondo A em A=D+L+U, com D a diagonal, L a parte estritamente triangular inferior e U a parte estritamente triangular superior, as iterações são:
    • Gauss–Jacobi: \mathbf{x}^{(k+1)} = -D^{-1}(L+U)\,\mathbf{x}^{(k)} + D^{-1}\mathbf{b}.O operador iterativo é \displaystyle B_J = -D^{-1}(L+U).
    • Gauss–Seidel: \mathbf{x}^{(k+1)} = -(D+L)^{-1}U\,\mathbf{x}^{(k)} + (D+L)^{-1}\mathbf{b}.O operador iterativo é \displaystyle B_{GS}=-(D+L)^{-1}U.
Condição suficiente prática de convergência: se para alguma norma subordinada tivermos \|B\|<1 então a iteração converge (isto implica que o raio espectral \rho(B)<1). Vou usar a norma infinito (norma linha) porque facilita cálculos com somas de valores absolutos de linhas.
Calculemos D,L,U a partir de A:
D=\begin{pmatrix}10&0&0\\[4pt]0&10&0\\[4pt]0&0&-10\end{pmatrix},\quad L=\begin{pmatrix}0&0&0\\[4pt]1&0&0\\[4pt]2&-3&0\end{pmatrix},\quad U=\begin{pmatrix}0&-1&4\\[4pt]0&0&9\\[4pt]0&0&0\end{pmatrix}.]

Passo 3

Calcular B_J (Jacobi) e sua norma infinito.
Primeiro D^{-1}=\operatorname{diag}(1/10,\,1/10,\,-1/10). Então
B_J = -D^{-1}(L+U).
Compute linha a linha:
  • Linha 1 de L+U é (0,\,-1,\,4). Multiplicando por D^{-1} e trocando sinal: \text{linha 1 de }B_J = -\frac{1}{10}(0,\,-1,\,4) = (0,\;0{,}1,\;-0{,}4).
  • Linha 2 de L+U é (1,0,9). Logo \text{linha 2 de }B_J = -\frac{1}{10}(1,0,9)=(-0{,}1,\;0,\;-0{,}9).
  • Linha 3 de L+U é (2,-3,0). Como D_{33}=-10, temos fator -1/10 e então: \text{linha 3 de }B_J = -\Big(-\frac{1}{10}\Big)(2,-3,0)=(0{,}2,\;-0{,}3,\;0).
Portanto
B_J=\begin{pmatrix} 0 & 0{,}1 & -0{,}4\\[4pt] -0{,}1 & 0 & -0{,}9\\[4pt] 0{,}2 & -0{,}3 & 0 \end{pmatrix}.
Agora a norma infinito (máxima soma das absolutas nas linhas):
  • linha 1: 0+0{,}1+0{,}4=0{,}5,
  • linha 2: 0{,}1+0+0{,}9=1{,}0,
  • linha 3: 0{,}2+0{,}3+0=0{,}5.
Logo \|B_J\|_\infty = 1{,}0. Como \|B_J\|_\infty não é estritamente menor que 1, esse teste não garante convergência do método de Jacobi (é inconclusivo e, na prática, não podemos afirmar que Jacobi converge). Portanto Gauss–Jacobi não está garantido por este critério.]

Passo 4

Calcular [B_{GS}) e sua norma infinito (Gauss–Seidel).
B_{GS}=-(D+L)^{-1}U.
Note que D+L é triangular inferior:
D+L=\begin{pmatrix} 10 & 0 & 0\\[4pt] 1 & 10 & 0\\[4pt] 2 & -3 & -10 \end{pmatrix}.
Como D+L é triangular inferior, para calcular (D+L)^{-1}U resolvemos sistemas por substituição direta coluna a coluna de U. Colunas de U: u_1=(0,0,0)^\top, u_2=(-1,0,0)^\top, u_3=(4,9,0)^\top.
  • Coluna 1 de B_{GS}: -(D+L)^{-1}u_1 = \mathbf{0}.
  • Coluna 2 de B_{GS}: -(D+L)^{-1}u_2 = (D+L)^{-1}(1,0,0)^\top. Resolver \begin{cases} 10y_1 = 1 \Rightarrow y_1=0{,}1,\\[4pt] y_1 +10 y_2 = 0 \Rightarrow y_2 = -0{,}01,\\[4pt] 2y_1 -3y_2 -10 y_3 = 0 \Rightarrow y_3 = 0{,}023. \end{cases}Logo coluna 2 é (0{,}1,\,-0{,}01,\;0{,}023)^\top\]. - Coluna 3 de \[B_{GS}: -(D+L)^{-1}u_3 = -(D+L)^{-1}(4,9,0)^\top. Resolver \begin{cases} 10y_1 = -4 \Rightarrow y_1=-0{,}4,\\[4pt] y_1 +10 y_2 = -9 \Rightarrow y_2=-0{,}86,\\[4pt] 2y_1 -3y_2 -10 y_3 = 0 \Rightarrow y_3 = 0{,}178. \end{cases}Portanto coluna 3 é ((-0{,}4,,-0{,}86,;0{,}178)^\top].
Montando B_{GS}:
B_{GS}=\begin{pmatrix} 0 & 0{,}1 & -0{,}4\\[4pt] 0 & -0{,}01 & -0{,}86\\[4pt] 0 & 0{,}023 & 0{,}178 \end{pmatrix}.
Norma infinito (soma das absolutas por linha):
  • linha 1: 0+0{,}1+0{,}4=0{,}5,
  • linha 2: 0+0{,}01+0{,}86=0{,}87,
  • linha 3: 0+0{,}023+0{,}178=0{,}201.
Logo \|B_{GS}\|_\infty = 0{,}87<1. Como existe uma norma subordinada com \|B_{GS}\|<1, concluímos que o método de Gauss–Seidel garante convergência para este sistema. Resumo: Jacobi — não garantido; Gauss–Seidel — garantido.]

Passo 5

Preparando a iteração de Gauss–Seidel (fórmulas e chute inicial).
Das equações do sistema isolamos x_1,x_2,x_3:
\begin{aligned} 10x_1 - x_2 +4x_3 &= 5 \quad\Rightarrow\quad x_1 = \frac{5 + x_2 -4x_3}{10},\\[4pt] x_1 +10x_2 +9x_3 &= 2 \quad\Rightarrow\quad x_2 = \frac{2 - x_1 -9x_3}{10},\\[4pt] 2x_1 -3x_2 -10x_3 &= 9 \quad\Rightarrow\quad x_3 = \frac{-9 +2x_1 -3x_2}{10}. \end{aligned}
No Gauss–Seidel usamos as atualizações sequenciais (cada componente já usa os valores mais recentes). Tomo \mathbf{x}^{(0)}=(0,0,0)^\top.]

Passo 6

Iteração 1 (k=0 → k=1), calculando passo a passo com aritmética detalhada.
  • x_1^{(1)} = \dfrac{5 + x_2^{(0)} -4x_3^{(0)}}{10} = \dfrac{5 + 0 - 0}{10} = 0{,}5.
  • x_2^{(1)} = \dfrac{2 - x_1^{(1)} -9x_3^{(0)}}{10} = \dfrac{2 - 0{,}5 - 0}{10} = \dfrac{1{,}5}{10} = 0{,}15.
  • x_3^{(1)} = \dfrac{-9 +2x_1^{(1)} -3x_2^{(1)}}{10} = \dfrac{-9 +2\cdot 0{,}5 -3\cdot 0{,}15}{10} = \dfrac{-9 +1{,}0 -0{,}45}{10} = \dfrac{-8{,}45}{10} = -0{,}845.
Portanto
\mathbf{x}^{(1)} \approx (0{,}5,\;0{,}15,\;-0{,}845)^\top.

Passo 7

Iteração 2 (k=1 → k=2).
  • x_1^{(2)} = \dfrac{5 + x_2^{(1)} -4x_3^{(1)}}{10} = \dfrac{5 + 0{,}15 -4(-0{,}845)}{10} = \dfrac{5{,}15 +3{,}38}{10} = \dfrac{8{,}53}{10} = 0{,}853.
  • x_2^{(2)} = \dfrac{2 - x_1^{(2)} -9x_3^{(1)}}{10} = \dfrac{2 - 0{,}853 -9(-0{,}845)}{10} = \dfrac{1{,}147 +7{,}605}{10} = \dfrac{8{,}752}{10} = 0{,}8752.
  • x_3^{(2)} = \dfrac{-9 +2x_1^{(2)} -3x_2^{(2)}}{10} = \dfrac{-9 +2(0{,}853) -3(0{,}8752)}{10} = \dfrac{-9 +1{,}706 -2{,}6256}{10} = \dfrac{-9{,}9196}{10} = -0{,}99196.
Logo
\mathbf{x}^{(2)} \approx (0{,}853,\;0{,}8752,\;-0{,}99196)^\top.

Passo 8

Iteração 3 (k=2 → k=3).
  • x_1^{(3)} = \dfrac{5 + x_2^{(2)} -4x_3^{(2)}}{10} = \dfrac{5 + 0{,}8752 -4(-0{,}99196)}{10} = \dfrac{5{,}8752 +3{,}96784}{10} = \dfrac{9{,}84304}{10} = 0{,}984304.
  • x_2^{(3)} = \dfrac{2 - x_1^{(3)} -9x_3^{(2)}}{10} = \dfrac{2 - 0{,}984304 -9(-0{,}99196)}{10} = \dfrac{1{,}015696 +8{,}92764}{10} = \dfrac{9{,}943336}{10} = 0{,}9943336.
  • x_3^{(3)} = \dfrac{-9 +2x_1^{(3)} -3x_2^{(3)}}{10} = \dfrac{-9 +2(0{,}984304) -3(0{,}9943336)}{10}
\quad= \dfrac{-9 +1{,}968608 -2{,}9820008}{10} = \dfrac{-10{,}0133928}{10} \approx -1{,}00133928.
Assim, após 3 iterações:
\mathbf{x}^{(3)} \approx (0{,}984304,\;0{,}9943336,\;-1{,}0013393)^\top.

Passo 9

Estimativas do erro (a priori, a posteriori e erro real).
Primeiro recorde das desigualdades úteis:
  • Se \|B\|<1, então erro a priori com chute \mathbf{x}^{(0)} satisfaz \|\mathbf{e}^{(k)}\| \le \|B\|^k \|\mathbf{e}^{(0)}\|,onde \mathbf{e}^{(k)}=\mathbf{x}-\mathbf{x}^{(k)}.
  • Uma estimativa a posteriori prática é \|\mathbf{e}^{(k)}\| \le \frac{\|B\|}{1-\|B\|}\,\|\mathbf{x}^{(k)}-\mathbf{x}^{(k-1)}\|.
Usando a norma infinito já calculada \|B_{GS}\|_\infty=0{,}87:
(a) Estimativa a priori após 3 iterações, com chute \mathbf{x}^{(0)}=\mathbf{0}. O erro inicial \mathbf{e}^{(0)}=\mathbf{x}-\mathbf{x}^{(0)}=\mathbf{x}; não conhecemos \mathbf{x} em geral, mas se tomarmos \|\mathbf{e}^{(0)}\|_\infty\le 1 (ou calcularmos o real mais abaixo) obtemos:
\|\mathbf{e}^{(3)}\|_\infty \le \|B_{GS}\|_\infty^3 \|\mathbf{e}^{(0)}\|_\infty = 0{,}87^3 \|\mathbf{e}^{(0)}\|_\infty \approx 0{,}6585\cdot\|\mathbf{e}^{(0)}\|_\infty.
Com \|\mathbf{e}^{(0)}\|_\infty=1 isto dá \approx 0{,}6585.
(b) Estimativa a posteriori usando as diferenças entre iterados:
\mathbf{x}^{(3)}-\mathbf{x}^{(2)} \approx (0{,}984304-0{,}853,\;0{,}9943336-0{,}8752,\;-1{,}0013393-(-0{,}99196))
\quad\approx (0{,}131304,\;0{,}1191336,\;-0{,}0093793),
logo \|\mathbf{x}^{(3)}-\mathbf{x}^{(2)}\|_\infty \approx 0{,}131304. Assim
\|\mathbf{e}^{(3)}\|_\infty \le \frac{0{,}87}{1-0{,}87}\cdot 0{,}131304 = \frac{0{,}87}{0{,}13}\cdot 0{,}131304 \approx 6{,}6923077\cdot 0{,}131304 \approx 0{,}878.
(c) Erro real: aqui podemos verificar a solução exata diretamente (pouco esforço): tentar \mathbf{x}=(1,1,-1)^\top:
A\begin{pmatrix}1\\[4pt]1\\[4pt]-1\end{pmatrix} = \begin{pmatrix} 10-1-4\\[4pt] 1+10-9\\[4pt] 2-3+10 \end{pmatrix} = \begin{pmatrix}5\\[4pt]2\\[4pt]9\end{pmatrix},
então a solução exata é \mathbf{x}=(1,1,-1)^\top. O erro real após 3 iterações é
\mathbf{e}^{(3)}=\mathbf{x}-\mathbf{x}^{(3)} \approx (1-0{,}984304,\;1-0{,}9943336,\;-1-(-1{,}0013393))
\quad\approx (0{,}015696,\;0{,}0056664,\;0{,}0013393),
portanto
\|\mathbf{e}^{(3)}\|_\infty \approx 0{,}015696.
Comparando: a priori (com \|\mathbf{e}^{(0)}\|_\infty=1) deu \approx 0{,}6585 (muito frouxo); a posteriori deu \approx 0{,}878 (ainda frouxo); o erro real é \approx 0{,}0157, bem menor — isso é normal: as estimativas com norma são conservadoras.]

Resposta

(a) Apenas Gauss–Seidel garante convergência (Gauss–Jacobi não é garantido).
(b) Com Gauss–Seidel e \mathbf{x}^{(0)}=(0,0,0)^\top, após 3 iterações
\mathbf{x}^{(3)} \approx (0{,}984304,\;0{,}9943336,\;-1{,}0013393)^\top.
(c) Estimativas do erro (norma infinito):
\text{a priori: }\|\mathbf{e}^{(3)}\|_\infty \le 0{,}87^{3}\|\mathbf{e}^{(0)}\|_\infty \approx 0{,}6585\quad(\text{se }\|\mathbf{e}^{(0)}\|_\infty=1),
\text{a posteriori: }\|\mathbf{e}^{(3)}\|_\infty \le \frac{0{,}87}{1-0{,}87}\,\|\mathbf{x}^{(3)}-\mathbf{x}^{(2)}\|_\infty \approx 0{,}878,
\text{erro real: }\|\mathbf{e}^{(3)}\|_\infty \approx 0{,}015696.

Exercícios relacionados