Considere o sistema linear A \mathbf{x}=\mathbf{b}, com A uma matriz quadrada de ordem n=300. Suponha que, para um propósito específico, seja suficiente encontrar \hat{\mathbf{x}} tal que \left\|\hat{\mathbf{x}}-\mathbf{x}^{*}\right\|< 10^{-4}, onde \mathbf{x}^{*} é a solução exata do sistema linear.
(a) Qual o custo computacional de uma iteração do método de Jacobi? (Veja exercício 11.1).
(b) Sabendo que para a resolução do sistema linear por Eliminação de Gauss é necessário realizar da ordem de \frac{2}{3} n^{3} operações, até quantas iterações do método de Jacobi poderiam ser realizadas para estimar \hat{\mathbf{x}}, sem ultrapassar o custo completo da Eliminação de Gauss?
(c) Sabendo que no método de Jacobi \left\|\mathbf{x}^{(k)}-\mathbf{x}^{*}\right\| \leq \alpha^{k}\left\|\mathbf{x}^{(0)}-\mathbf{x}^{*}\right\|, onde \alpha é uma constante positiva relacionada à matriz A, e que o erro na aproximação inicial da solução do sistema linear era da ordem de 10^{2}, para que valores de \alpha poderemos garantir que o método de Jacobi vai produzir uma aproximação \mathbf{x}^{(k)} dentro da tolerância desejada e ainda assim ser mais barato que a Eliminação de Gauss?

Passo 1

Estamos resolvendo um sistema A\mathbf{x}=\mathbf{b} com A de ordem n=300 e queremos \hat{\mathbf{x}} tal que \|\hat{\mathbf{x}}-\mathbf{x}^*\|<10^{-4}. As perguntas são: (a) custo de uma iteração de Jacobi; (b) quantas iterações cabem no mesmo custo de eliminação de Gauss; (c) para que \alpha o método de Jacobi atinge a tolerância em no máximo esse número de iterações.

Passo 2

No método de Jacobi, em cada iteração precisamos calcular para cada componente i da aproximação
x_i^{(k+1)} =\frac{1}{a_{ii}}\Bigl(b_i-\sum_{j\neq i}a_{ij}\,x_j^{(k)}\Bigr).
Cada uma das n componentes exige cerca de n-1 multiplicações e n-1 subtrações, totalizando da ordem de 2n^2 operações de ponto flutuante. Portanto o custo é \mathcal{O}(n^2).

Passo 3

A eliminação de Gauss custa cerca de \tfrac{2}{3}n^3 operações. Se admitirmos até k iterações de Jacobi com custo total
k\cdot 2n^2 \;\le\;\frac{2}{3}n^3,
temos
k \le \frac{\tfrac{2}{3}n^3}{2n^2}=\frac{n}{3}=\frac{300}{3}=100.
Logo, são permitidas até 100 iterações de Jacobi antes de ultrapassar o custo da eliminação de Gauss.

Passo 4

Pelo enunciado,
\bigl\|\mathbf{x}^{(k)}-\mathbf{x}^*\bigr\|\le \alpha^k\bigl\|\mathbf{x}^{(0)}-\mathbf{x}^*\bigr\|,
com \|\mathbf{x}^{(0)}-\mathbf{x}^*\|\approx10^2. Para atingir \|\mathbf{x}^{(k)}-\mathbf{x}^*\|<10^{-4} basta
\alpha^k\cdot10^2<10^{-4} \quad\Longrightarrow\quad \alpha^k<10^{-6}.
Como só podemos usar até k=100 iterações, impomos
\alpha^{100}<10^{-6} \quad\Longrightarrow\quad 100\log_{10}\alpha<-6 \quad\Longrightarrow\quad \alpha<10^{-0,06}\approx0,87.

Resposta

(a) O custo de cada iteração de Jacobi é \mathcal{O}(n^2), aproximadamente 2n^2 operações.
(b) Cabe até 100 iterações de Jacobi sem ultrapassar o custo de eliminação de Gauss.
(c) Para que Jacobi alcance a tolerância desejada em no máximo 100 iterações, precisamos de \alpha<10^{-0,06}\approx0,87.

Exercícios relacionados