| | | |

Matemática Numérica I

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𝒙=𝒃, A matriz positiva definida, e as iterações têm a forma

𝒙(0) =aprox. inicial, (3.320)
𝒙(k+1) =𝒙(k)+α(k)𝒅(k). (3.321)

onde 𝒅(k) é o vetor direção na k-ésima iterada. No Método do Gradiente, o vetor direção é 𝒅(k)=𝒓(k):=𝒃A𝒙(k). Aqui, as direções escolhidas são tomadas conjugadas duas-a-duas4141endnote: 41São ortogonais em relação ao produto interno induzido por A, <𝒖,𝒗>A:=𝒖A𝒗.. Isto nos leva a iteração do Método do Gradiente Conjugado:

𝒙(0) =aprox. inicial, (3.322)
𝒅(0) =𝒓(0), (3.323)
α(k) =𝒓(k)𝒓(k)𝒅(k)A𝒅(k), (3.324)
𝒙(k+1) =𝒙(k)+α(k)𝒅(k), (3.325)
𝒓(k+1) =𝒓(k)α(k)A𝒅(k), (3.326)
β(k) =𝒓(k+1)𝒓(k+1)𝒓(k)𝒓(k), (3.327)
𝒅(k+1) =𝒓(k+1)+β(k)𝒅(k), (3.328)

para k=0,1,, e 𝒓(k):=𝒃A𝒙(k).

Refer to caption
Figura 3.2: Iterações do Método do Gradiente Conjugado para sistemas lineares. Linha: bAx. Pontos: 𝒙(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𝒙=𝒃, com A matriz positiva definida n×n.

Exemplo 3.5.1.

Consideremos o sistema Ax=b com

A =[2100121001210012], (3.330)
b =[3223]. (3.331)

Na Tabela 3.5 temos os resultados do emprego do método do gradiente conjugado com 𝒙(0)=(0,0,0,0).

Tabela 3.5: Resultados referentes ao Exemplo 3.5.1.
k 𝒙(k) 𝒃A𝒙(k)
1 (0,0,0,0) 5.1e+00
2 (1.1,0.8,0.8,1.1) 1.5e01
3 (1.0,1.0,1.0,1.0) 2.0e15
Código 11: mgc.py
1import numpy as np
2import numpy.linalg as npla
3
4def mgc(A, b, x0,
5 maxiter=100, atol=1.49e-8, rtol=1.49e-8):
6
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
19
20 r = r - alpha*Ad
21 beta = np.dot(r,r)/rdr
22 d = r + beta*d
23
24 nr = npla.norm(r)
25 print(f'{k+1}: {x}, nr = {nr:.1e}')
26
27 if (nr <= max(atol, rtol*npla.norm(b))):
28 info = 0
29 break
30
31 return x, info
32
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.])
40
41# aprox. inicial
42x0 = np.zeros_like(b)
43
44x, info = mgc(A, b, x0)

3.5.1 Exercícios

E. 3.5.1.

Considere o sistema linear A𝒙=𝒃 com

A =[2112], (3.332)
b =[78]. (3.333)

Use o Método do Gradiente Conjugado com 𝒙(0)=𝟎 para computar a solução com tolerância

𝒓max{tol,tol𝒃}, (3.334)

onde 𝒓 é o resíduo do sistema e tol=1.49e8. Quantas iterações são requeridas até a convergência?

Resposta 0.

Iterações: 2, 𝒙=(2,3).

E. 3.5.2.

Considere o sistema linear A𝒙=𝒃 com

A =[211131114], (3.335)
b =[201]. (3.336)

Use o Método do Gradiente Conjugado com 𝒙(0)=𝟎 para computar a solução com tolerância

𝒓max{tol,tol𝒃}, (3.337)

onde 𝒓 é o resíduo do sistema e tol=1.49e8. Quantas iterações são requeridas até a convergência?

Resposta 0.

Iterações: 3, 𝒙=(2,0,1).

E. 3.5.3.

Considere o sistema linear A𝒙=𝒃 com

A =[2100121001210012], (3.338)
b =[5761]. (3.339)

Use o Método do Gradiente Conjugado com 𝒙(0)=𝟎 para computar a solução com tolerância

𝒓max{tol,tol𝒃}, (3.340)

onde 𝒓 é o resíduo do sistema e tol=1.49e8.

Resposta 0.

𝒙=(2.0,1.0,3.0,1.0)

E. 3.5.4.

Considere o sistema linear A𝒙=𝒃 com

A =[2110121011310012], (3.341)
b =[89105]. (3.342)

Use o Método do Gradiente Conjugado com 𝒙(0)=𝟎 para computar a solução com tolerância

𝒓max{tol,tol𝒃}, (3.343)

onde 𝒓 é o resíduo do sistema e tol=1.49e8.

Resposta 0.

𝒙=(2.0,3.0,1.0,2.0)

E. 3.5.5.

Considere o problema de Laplace

uxx=2,0<x<1, (3.344)
u(0)=u(1)=0. (3.345)

A discretização pelo Método das Diferenças Finitas em uma malha uniforme xi=ih, i=0.1,,n, h=1/(n1), leva ao seguinte sistema linear

u1=0 (3.346)
1h2ui1+2h2ui1h2ui+1=2, (3.347)
un=0 (3.348)

onde uiu(xi). Com u(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

𝒓tol, (3.349)

onde, 𝒓:=𝒃A𝒙 é o resíduo e tol=1e4.

Resposta 0.
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!

Opcional. Preencha seu nome para que eu possa lhe contatar.
Opcional. Preencha seu e-mail para que eu possa lhe contatar.
As informações preenchidas são enviadas por e-mail para o desenvolvedor do site e tratadas de forma privada. Consulte a política de uso de dados para mais informações.

Licença Creative Commons
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.

Matemática Numérica I

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𝒙=𝒃, A matriz positiva definida, e as iterações têm a forma

𝒙(0) =aprox. inicial, (3.320)
𝒙(k+1) =𝒙(k)+α(k)𝒅(k). (3.321)

onde 𝒅(k) é o vetor direção na k-ésima iterada. No Método do Gradiente, o vetor direção é 𝒅(k)=𝒓(k):=𝒃A𝒙(k). Aqui, as direções escolhidas são tomadas conjugadas duas-a-duas4141endnote: 41São ortogonais em relação ao produto interno induzido por A, <𝒖,𝒗>A:=𝒖A𝒗.. Isto nos leva a iteração do Método do Gradiente Conjugado:

𝒙(0) =aprox. inicial, (3.322)
𝒅(0) =𝒓(0), (3.323)
α(k) =𝒓(k)𝒓(k)𝒅(k)A𝒅(k), (3.324)
𝒙(k+1) =𝒙(k)+α(k)𝒅(k), (3.325)
𝒓(k+1) =𝒓(k)α(k)A𝒅(k), (3.326)
β(k) =𝒓(k+1)𝒓(k+1)𝒓(k)𝒓(k), (3.327)
𝒅(k+1) =𝒓(k+1)+β(k)𝒅(k), (3.328)

para k=0,1,, e 𝒓(k):=𝒃A𝒙(k).

Refer to caption
Figura 3.2: Iterações do Método do Gradiente Conjugado para sistemas lineares. Linha: bAx. Pontos: 𝒙(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𝒙=𝒃, com A matriz positiva definida n×n.

Exemplo 3.5.1.

Consideremos o sistema Ax=b com

A =[2100121001210012], (3.330)
b =[3223]. (3.331)

Na Tabela 3.5 temos os resultados do emprego do método do gradiente conjugado com 𝒙(0)=(0,0,0,0).

Tabela 3.5: Resultados referentes ao Exemplo 3.5.1.
k 𝒙(k) 𝒃A𝒙(k)
1 (0,0,0,0) 5.1e+00
2 (1.1,0.8,0.8,1.1) 1.5e01
3 (1.0,1.0,1.0,1.0) 2.0e15
Código 11: mgc.py
1import numpy as np
2import numpy.linalg as npla
3
4def mgc(A, b, x0,
5 maxiter=100, atol=1.49e-8, rtol=1.49e-8):
6
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
19
20 r = r - alpha*Ad
21 beta = np.dot(r,r)/rdr
22 d = r + beta*d
23
24 nr = npla.norm(r)
25 print(f'{k+1}: {x}, nr = {nr:.1e}')
26
27 if (nr <= max(atol, rtol*npla.norm(b))):
28 info = 0
29 break
30
31 return x, info
32
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.])
40
41# aprox. inicial
42x0 = np.zeros_like(b)
43
44x, info = mgc(A, b, x0)

3.5.1 Exercícios

E. 3.5.1.

Considere o sistema linear A𝒙=𝒃 com

A =[2112], (3.332)
b =[78]. (3.333)

Use o Método do Gradiente Conjugado com 𝒙(0)=𝟎 para computar a solução com tolerância

𝒓max{tol,tol𝒃}, (3.334)

onde 𝒓 é o resíduo do sistema e tol=1.49e8. Quantas iterações são requeridas até a convergência?

Resposta 0.

Iterações: 2, 𝒙=(2,3).

E. 3.5.2.

Considere o sistema linear A𝒙=𝒃 com

A =[211131114], (3.335)
b =[201]. (3.336)

Use o Método do Gradiente Conjugado com 𝒙(0)=𝟎 para computar a solução com tolerância

𝒓max{tol,tol𝒃}, (3.337)

onde 𝒓 é o resíduo do sistema e tol=1.49e8. Quantas iterações são requeridas até a convergência?

Resposta 0.

Iterações: 3, 𝒙=(2,0,1).

E. 3.5.3.

Considere o sistema linear A𝒙=𝒃 com

A =[2100121001210012], (3.338)
b =[5761]. (3.339)

Use o Método do Gradiente Conjugado com 𝒙(0)=𝟎 para computar a solução com tolerância

𝒓max{tol,tol𝒃}, (3.340)

onde 𝒓 é o resíduo do sistema e tol=1.49e8.

Resposta 0.

𝒙=(2.0,1.0,3.0,1.0)

E. 3.5.4.

Considere o sistema linear A𝒙=𝒃 com

A =[2110121011310012], (3.341)
b =[89105]. (3.342)

Use o Método do Gradiente Conjugado com 𝒙(0)=𝟎 para computar a solução com tolerância

𝒓max{tol,tol𝒃}, (3.343)

onde 𝒓 é o resíduo do sistema e tol=1.49e8.

Resposta 0.

𝒙=(2.0,3.0,1.0,2.0)

E. 3.5.5.

Considere o problema de Laplace

uxx=2,0<x<1, (3.344)
u(0)=u(1)=0. (3.345)

A discretização pelo Método das Diferenças Finitas em uma malha uniforme xi=ih, i=0.1,,n, h=1/(n1), leva ao seguinte sistema linear

u1=0 (3.346)
1h2ui1+2h2ui1h2ui+1=2, (3.347)
un=0 (3.348)

onde uiu(xi). Com u(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

𝒓tol, (3.349)

onde, 𝒓:=𝒃A𝒙 é o resíduo e tol=1e4.

Resposta 0.
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!

Opcional. Preencha seu nome para que eu possa lhe contatar.
Opcional. Preencha seu e-mail para que eu possa lhe contatar.
As informações preenchidas são enviadas por e-mail para o desenvolvedor do site e tratadas de forma privada. Consulte a política de uso de dados para mais informações.

Licença Creative Commons
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.

Pedro H A Konzen
| | | |