Matemática Numérica I

3 Métodos para Sistemas Lineares 3.4 Método do Gradiente 4 Métodos para Sistemas Não Lineares

Ajude a manter o site livre, gratuito e sem propagandas. Colabore!

3.5 Método do Gradiente Conjugado

O Método do Gradiente Conjugado é uma variação do Método do Gradiente (consulte Seção 3.4). Ambos são aplicáveis a sistemas lineares $A\boldsymbol{x}=\boldsymbol{b}$ , $A$ matriz positiva definida, e as iterações têm a forma

	$\displaystyle\boldsymbol{x}^{(0)}$	$\displaystyle=\text{aprox. inicial},$		(3.320)
	$\displaystyle\boldsymbol{x}^{(k+1)}$	$\displaystyle=\boldsymbol{x}^{(k)}+\alpha^{(k)}\boldsymbol{d}^{(k)}.$		(3.321)

onde $\boldsymbol{d}^{(k)}$ é o vetor direção na $k$ -ésima iterada. No Método do Gradiente, o vetor direção é $\boldsymbol{d}^{(k)}=\boldsymbol{r}^{(k)}:=\boldsymbol{b}-A\boldsymbol{x}^{(k)}$ . Aqui, as direções escolhidas são tomadas conjugadas duas-a-duas⁴¹⁴¹endnote: ⁴¹São ortogonais em relação ao produto interno induzido por $A$ , $<\boldsymbol{u},\boldsymbol{v}>_{A}:=\boldsymbol{u}\cdot A\boldsymbol{v}$ .. Isto nos leva a iteração do Método do Gradiente Conjugado:

$\displaystyle\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}% \boldsymbol{x}^{(0)}$	$\displaystyle\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}% =\text{aprox. inicial},$	(3.322)
$\displaystyle\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}% \boldsymbol{d}^{(0)}$	$\displaystyle\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}% =\boldsymbol{r}^{(0)},$	(3.323)
$\displaystyle\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}% \alpha^{(k)}$	$\displaystyle\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}% =\frac{\boldsymbol{r}^{(k)}\cdot\boldsymbol{r}^{(k)}}{\boldsymbol{d}^{(k)}% \cdot A\boldsymbol{d}^{(k)}},$	(3.324)
$\displaystyle\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}% \boldsymbol{x}^{(k+1)}$	$\displaystyle\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}% =\boldsymbol{x}^{(k)}+\alpha^{(k)}\boldsymbol{d}^{(k)},$	(3.325)
$\displaystyle\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}% \boldsymbol{r}^{(k+1)}$	$\displaystyle\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}% =\boldsymbol{r}^{(k)}-\alpha^{(k)}A\boldsymbol{d}^{(k)},$	(3.326)
$\displaystyle\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}% \beta^{(k)}$	$\displaystyle\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}% =\frac{\boldsymbol{r}^{(k+1)}\cdot\boldsymbol{r}^{(k+1)}}{\boldsymbol{r}^{(k)}% \boldsymbol{r}^{(k)}},$	(3.327)
$\displaystyle\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}% \boldsymbol{d}^{(k+1)}$	$\displaystyle\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}% =\boldsymbol{r}^{(k+1)}+\beta^{(k)}\boldsymbol{d}^{(k)},$	(3.328)

para $k=0,1,\ldots$ , e $\boldsymbol{r}^{(k)}:=\boldsymbol{b}-A\boldsymbol{x}^{(k)}$ .

Refer to caption — Figura 3.2: Iterações do Método do Gradiente Conjugado para sistemas lineares. Linha: $\|b-Ax\|$ . Pontos: $\boldsymbol{x}^{(k)}$ .

Observação 3.5.1.

(Convergência.) A menos de erros de arredondamento, o Método do Gradiente Conjugado converge em no máximo $n$ passos para a solução do sistema $A\boldsymbol{x}=\boldsymbol{b}$ , com $A$ matriz positiva definida $n\times n$ .

Exemplo 3.5.1.

Consideremos o sistema $Ax=b$ com

	$\displaystyle A$	$\displaystyle=\begin{bmatrix}2&-1&0&0\\ -1&2&-1&0\\ 0&-1&2&-1\\ 0&0&-1&2\end{bmatrix},$		(3.330)
	$\displaystyle b$	$\displaystyle=\begin{bmatrix}-3\\ 2\\ 2\\ -3\end{bmatrix}.$		(3.331)

Na Tabela 3.5 temos os resultados do emprego do método do gradiente conjugado com $\boldsymbol{x}^{(0)}=(0,0,0,0)$ .

Tabela 3.5: Resultados referentes ao Exemplo 3.5.1.

k	$\boldsymbol{x}^{(k)}$	$\\|\boldsymbol{b}-A\boldsymbol{x}^{(k)}\\|$
1	$(0,0,0,0)$	$5.1\mathrm{e}\!+\!00$
2	$(-1.1,0.8,0.8,-1.1)$	$1.5\mathrm{e}\!-\!01$
3	$(-1.0,1.0,1.0,-1.0)$	$2.0\mathrm{e}\!-\!15$

Código 11: mgc.py

⬇

1import numpy as np

2import numpy.linalg as npla

4def mgc(A, b, x0,

5 maxiter=100, atol=1.49e-8, rtol=1.49e-8):

7 n = b.size

8 x = x0.copy()

9 r = b - A@x

10 d = r.copy()

11 nr = npla.norm(r)

12 print(f'0: {x}, nr = {nr:.1e}')

13 info = -1

14 for k in range(maxiter):

15 rdr = np.dot(r, r)

16 Ad = A@d

17 alpha = rdr/np.dot(d,Ad)

18 x = x + alpha*d

20 r = r - alpha*Ad

21 beta = np.dot(r,r)/rdr

22 d = r + beta*d

24 nr = npla.norm(r)

25 print(f'{k+1}: {x}, nr = {nr:.1e}')

27 if (nr <= max(atol, rtol*npla.norm(b))):

28 info = 0

29 break

31 return x, info

33# matriz coefs

34A = np.array([[2., -1., 0., 0.],

35 [-1., 2., -1., 0.],

36 [0., -1., 2., -1.],

37 [0., 0., -1., 2.]])

38# vetor constante

39b = np.array([-3., 2., 2., -3.])

41# aprox. inicial

42x0 = np.zeros_like(b)

44x, info = mgc(A, b, x0)

3.5.1 Exercícios

E. 3.5.1.

Considere o sistema linear $A\boldsymbol{x}=\boldsymbol{b}$ com

	$\displaystyle A$	$\displaystyle=\begin{bmatrix}2&-1\\ -1&2\\ \end{bmatrix},$		(3.332)
	$\displaystyle b$	$\displaystyle=\begin{bmatrix}-7\\ 8\end{bmatrix}.$		(3.333)

Use o Método do Gradiente Conjugado com $\boldsymbol{x}^{(0)}=\boldsymbol{0}$ para computar a solução com tolerância

\|\boldsymbol{r}\|\leq\max\{\texttt{tol},\texttt{tol}\|\boldsymbol{b}\|\},

(3.334)

onde $\boldsymbol{r}$ é o resíduo do sistema e $\texttt{tol}=1.49\mathrm{e}\!-\!8$ . Quantas iterações são requeridas até a convergência?

Iterações: 2, $\boldsymbol{x}=(-2,3)$ .

E. 3.5.2.

Considere o sistema linear $A\boldsymbol{x}=\boldsymbol{b}$ com

	$\displaystyle A$	$\displaystyle=\begin{bmatrix}2&-1&1\\ -1&3&1\\ 1&1&4\end{bmatrix},$		(3.335)
	$\displaystyle b$	$\displaystyle=\begin{bmatrix}2\\ 0\\ -1\end{bmatrix}.$		(3.336)

Use o Método do Gradiente Conjugado com $\boldsymbol{x}^{(0)}=\boldsymbol{0}$ para computar a solução com tolerância

\|\boldsymbol{r}\|\leq\max\{\texttt{tol},\texttt{tol}\|\boldsymbol{b}\|\},

(3.337)

onde $\boldsymbol{r}$ é o resíduo do sistema e $\texttt{tol}=1.49\mathrm{e}\!-\!8$ . Quantas iterações são requeridas até a convergência?

Iterações: 3, $\boldsymbol{x}=(2,0,-1)$ .

E. 3.5.3.

Considere o sistema linear $A\boldsymbol{x}=\boldsymbol{b}$ com

	$\displaystyle A$	$\displaystyle=\begin{bmatrix}2&-1&0&0\\ -1&2&-1&0\\ 0&-1&2&-1\\ 0&0&-1&2\end{bmatrix},$		(3.338)
	$\displaystyle b$	$\displaystyle=\begin{bmatrix}5\\ -7\\ 6\\ -1\end{bmatrix}.$		(3.339)

Use o Método do Gradiente Conjugado com $\boldsymbol{x}^{(0)}=\boldsymbol{0}$ para computar a solução com tolerância

\|\boldsymbol{r}\|\leq\max\{\texttt{tol},\texttt{tol}\|\boldsymbol{b}\|\},

(3.340)

onde $\boldsymbol{r}$ é o resíduo do sistema e $\texttt{tol}=1.49\mathrm{e}\!-\!8$ .

$\boldsymbol{x}=\left(2.0,-1.0,3.0,1.0\right)$

E. 3.5.4.

Considere o sistema linear $A\boldsymbol{x}=\boldsymbol{b}$ com

	$\displaystyle A$	$\displaystyle=\begin{bmatrix}2&-1&1&0\\ -1&2&-1&0\\ 1&-1&3&-1\\ 0&0&-1&2\end{bmatrix},$		(3.341)
	$\displaystyle b$	$\displaystyle=\begin{bmatrix}-8\\ 9\\ -10\\ 5\end{bmatrix}.$		(3.342)

Use o Método do Gradiente Conjugado com $\boldsymbol{x}^{(0)}=\boldsymbol{0}$ para computar a solução com tolerância

\|\boldsymbol{r}\|\leq\max\{\texttt{tol},\texttt{tol}\|\boldsymbol{b}\|\},

(3.343)

onde $\boldsymbol{r}$ é o resíduo do sistema e $\texttt{tol}=1.49\mathrm{e}\!-\!8$ .

$\boldsymbol{x}=\left(-2.0,3.0,-1.0,2.0\right)$

E. 3.5.5.

Considere o problema de Laplace

	$\displaystyle-$	$\displaystyle u_{xx}=2,\quad 0<x<1,$		(3.344)
		$\displaystyle u(0)=u(1)=0.$		(3.345)

A discretização pelo Método das Diferenças Finitas em uma malha uniforme $x_{i}=ih$ , $i=0.1,\dotsc,n$ , $h=1/(n-1)$ , leva ao seguinte sistema linear

	$\displaystyle u_{1}=0$		(3.346)
	$\displaystyle-\frac{1}{h^{2}}u_{i-1}+\frac{2}{h^{2}}u_{i}-\frac{1}{h^{2}}u_{i+% 1}=2,$		(3.347)
	$\displaystyle u_{n}=0$		(3.348)

onde $u_{i}\approx u(x_{i})$ . Com $u^{(0)}=\boldsymbol{0}$ , aplique o Método do Gradiente Conjugado para computar a solução deste sistema quando $n=10,20,40,80$ . Quantas iterações são necessárias para obter-se a convergência do método com critério de convergência

\|\boldsymbol{r}\|\leq\texttt{tol},

(3.349)

onde, $\boldsymbol{r}:=\boldsymbol{b}-A\boldsymbol{x}$ é o resíduo e $\texttt{tol}=1e-4$ .

$n$	$k$
$10$	$4$
$20$	$9$
$40$	$19$
$80$	$39$
$160$	$79$

Envie seu comentário

Aproveito para agradecer a todas/os que de forma assídua ou esporádica contribuem enviando correções, sugestões e críticas!

Este texto é disponibilizado nos termos da Licença Creative Commons Atribuição-CompartilhaIgual 4.0 Internacional. Ícones e elementos gráficos podem estar sujeitos a condições adicionais.

Política de uso de dados

Política de uso de dados

Matemática Numérica I

3.5 Método do Gradiente Conjugado

Observação 3.5.1.

Exemplo 3.5.1.

3.5.1 Exercícios

E. 3.5.1.

E. 3.5.2.

E. 3.5.3.

E. 3.5.4.

E. 3.5.5.

Envie seu comentário