Seja A uma matriz simétrica, positiva definida, isto é, A^T=A e x^T A x>0, para qualquer x não nulo. Por notação, x é o vetor coluna e x^T seu transposto. Os métodos numéricos do tipo gradiente para resolver sistemas lineares A x=b têm como ideia básica minimizar a função de x=(x1, x2, ldots, xn), dada por:
F(x) & =12 x^T A x-b^T x F(x1, x2, ldots, xn) & =12(lll x1 & cdots & xn )(ccc a11 & cdots & a1 n vdots & ddots & vdots a1 n & cdots & an n )(c x1 vdots xn )-(lll b1 & cdots & bn )(c x1 vdots xn )
Para simplificar, quando abrirmos as equações matriciais, o faremos supondo n=2, embora o desenvolvimento seja o mesmo para um número arbitrário de componentes. Por exemplo, para verificar que F(x) é uma função quadrática nas componentes do vetor x, tomamos n=2 na equação (1):
F(x1, x2)=12(a11 x1^2+2 a12 x1 x2+a22 x2^2)-b1 x1-b2 x2,
onde foi usada a simetria da matriz A. As curvas de nível da função F(x1, x2) são elipses. Assim, o gráfico de F é um parabolóide eliptíco e esta função tem um único mínimo. O mínimo da função é atingido no ponto que anula o gradiente da função, portanto
nabla F(x1, x2)=binompartial Fpartial x1partial Fpartial x2=binoma11 x1+a12 x2-b1a21 x1+a22 x2-b2=A x-b
Sendo assim, nabla F=(0,0) significa A x=b, isto é, a solução do sistema de equações lineares minimiza a função quadrática e vice-versa. Como sabemos, o vetor gradiente aponta a direção de crescimento máximo da função. Portanto, é natural que, nos passos de busca do mínimo, caminhemos na direção contrária ao gradiente, isto é:
x^(k+1)=x^(k)-sk nabla F(x^(k))
Assim, a aproximação num passo k+1 é calculada a partir da aproximação no passo anterior, caminhando na direção contrária ao gradiente. O parâmetro real sk regula o tamanho do passo na k-ésima iteração. Considerando A=(ll4 & 2 2 & 5) e b=binom-61, faça o que se pede:
d) Utilize a equação (4) para aproximar a solução do sistema utilizando 5 passos. Para tanto, considere x^(0)=(-1,0), s0=s2=0.35 e s1=s3=s4=0.16.

Passo 1

Beleza, vamos lá! A gente tem uma matriz A que é simétrica e positiva definida, junto com um vetor b. A missão é resolver o sistema linear A x = b usando o método do gradiente. Esse método vai nos ajudar a encontrar a solução aproximada passo a passo, minimizando uma função quadrática associada. Vamos precisar calcular o gradiente dessa função e seguir na direção oposta a ele, usando tamanhos de passo específicos em cada iteração.

Passo 2

Iteração 0: Calculando x^(1)
Começamos com x^(0) = -1 0 e s0 = 0.35.
Primeiro, calculamos o gradiente nabla F(x^(0)):
nabla F(x) = A x - b
Então,
A x^(0) = 4 & 2 2 & 5 -1 0 = -4 -2
Agora,
nabla F(x^(0)) = -4 -2 - -6 1 = 2 -3
Atualizamos x^(1):
x^(1) = x^(0) - s0 nabla F(x^(0)) = -1 0 - 0.35 2 -3 = -1 - 0.7 0 + 1.05 = -1.7 1.05

Passo 3

Iteração 1: Calculando x^(2)
Agora, x^(1) = -1.7 1.05 e s1 = 0.16.
Calculamos o gradiente nabla F(x^(1)):
A x^(1) = 4 & 2 2 & 5 -1.7 1.05 = 4*(-1.7) + 2*1.05 2*(-1.7) + 5*1.05 = -6.8 + 2.1 -3.4 + 5.25 = -4.7 1.85
Então,
nabla F(x^(1)) = -4.7 1.85 - -6 1 = 1.3 0.85
Atualizamos x^(2):
x^(2) = x^(1) - s1 nabla F(x^(1)) = -1.7 1.05 - 0.16 1.3 0.85 = -1.7 - 0.208 1.05 - 0.136 = -1.908 0.914

Passo 4

Iteração 2: Calculando x^(3)
Agora, x^(2) = -1.908 0.914 e s2 = 0.35.
Calculamos o gradiente nabla F(x^(2)):
A x^(2) = 4 & 2 2 & 5 -1.908 0.914 = 4*(-1.908) + 2*0.914 2*(-1.908) + 5*0.914 = -7.632 + 1.828 -3.816 + 4.57 = -5.804 0.754
Então,
nabla F(x^(2)) = -5.804 0.754 - -6 1 = 0.196 -0.246
Atualizamos x^(3):
x^(3) = x^(2) - s2 nabla F(x^(2)) = -1.908 0.914 - 0.35 0.196 -0.246 = -1.908 - 0.0686 0.914 + 0.0861 = -1.9766 1.0001

Passo 5

Iteração 3: Calculando x^(4)
Agora, x^(3) = -1.9766 1.0001 e s3 = 0.16.
Calculamos o gradiente nabla F(x^(3)):
A x^(3) = 4 & 2 2 & 5 -1.9766 1.0001 = 4*(-1.9766) + 2*1.0001 2*(-1.9766) + 5*1.0001 = -7.9064 + 2.0002 -3.9532 + 5.0005 = -5.9062 1.0473
Então,
nabla F(x^(3)) = -5.9062 1.0473 - -6 1 = 0.0938 0.0473
Atualizamos x^(4):
x^(4) = x^(3) - s3 nabla F(x^(3)) = -1.9766 1.0001 - 0.16 0.0938 0.0473 = -1.9766 - 0.0150 1.0001 - 0.0076 = -1.9916 0.9925

Passo 6

Iteração 4: Calculando x^(5)
Agora, x^(4) = -1.9916 0.9925 e s4 = 0.16.
Calculamos o gradiente nabla F(x^(4)):
A x^(4) = 4 & 2 2 & 5 -1.9916 0.9925 = 4*(-1.9916) + 2*0.9925 2*(-1.9916) + 5*0.9925 = -7.9664 + 1.9850 -3.9832 + 4.9625 = -5.9814 0.9793
Então,
nabla F(x^(4)) = -5.9814 0.9793 - -6 1 = 0.0186 -0.0207
Atualizamos x^(5):
x^(5) = x^(4) - s4 nabla F(x^(4)) = -1.9916 0.9925 - 0.16 0.0186 -0.0207 = -1.9916 - 0.0030 0.9925 + 0.0033 = -1.9946 0.9958

Resposta

Após 5 passos, a aproximação da solução do sistema A x = b é:
x^(5) = -1.9946 0.9958

Exercícios relacionados