MÉTODOS NUMÉRICOS
INFORMÁTICA DE GESTÃO
EXERCÍCIOS
TEÓRICO-PRÁTICOS
2003/2004
Métodos Numéricos
Exercícios
Optimização não linear sem restrições
Condições de optimalidade
Folha 1
1. Baseando-se no estudo das condições necessárias e/ou suficientes de optimalidade,
determine e classifique, se possível, os pontos estacionários de cada uma das seguintes
funções:
(a) f (x) = 2x2 − 3x + 9
(b) f (x) = x3 − 6x2 + 9x + 4
(c) f (x) = x2 + 2e−x
(d) f (x1 , x2 ) = 4x21 − 4x1 x2 + 3x22
(e) f (x1 , x2 , x3 ) = x21 − x1 x2 + x22 − x2 x3 + x23 + 2x1 − x2
(f) f (x1 , x2 ) = 3x1 x2 − x31 − x32
(g) f (x1 , x2 ) = x41 + x42 + 16x1 x2
(h) f (x1 , x2 , x3 ) = 5x21 + 6x1 x2 + 2x22 − 32x3 + x43 + 5ex2
2. Dada a função f : IR3 → IR definida por
f (x1 , x2 , x3 ) = 5x21 + 2x22 + x43 − 32x3 + 6x1 x2 + 5x2
verifique que ela tem apenas um ponto estacionário. Classifique-o.
3. Considere a função
f (x, y) = 3x21 − x22 + x31
Mostre que:
(a) a função dada tem um máximo local em (−2, 0)T ;
(b) a função dada tem um ponto de sela em (0, 0)T ;
(c) a função dada não tem mínimos.
4. Mostre que qualquer ponto da linha x2 − 2x1 = 0 é um mínimo de f : IR2 → IR
definida por
f (x1 , x2 ) = 4x1 2 − 4x1 x2 + x22 .
5. Dada a função f : IR2 → IR definida por
f (x1 , x2 ) = x21 (1 − x1 )2 + x1 x2 .
Verifique se tem pontos máximos, mínimos e/ou de descanso.
2
Métodos Numéricos
Exercícios
Condições de optimalidade - Limitações da solução analítica
Solução de uma equação não linear
Folha 2
1. Considere a seguinte função
f (x) = x − e−x .
(a) Determine através de métodos gráficos e por dois processos distintos, a localização do zero da função.
(b) Use o método da secante para calcular uma aproximação a esse zero. Pare o
processo iterativo quando
|xk+1 − xk |
≤ 0.01
|xk+1 |
e
|f (xk+1 )| ≤ 0.05
(c) Repita o processo utilizando o método de Newton e considerando a aproximação inicial x0 = 0 e o mesmo critério de paragem.
2. Determine através de métodos gráficos e por dois processos distintos, a localização
do zero das funções:
(a) f (x) = x + ln(x)
(b) g(x) = x3 − 3x + 1
3. A equação
f (x) = x2 + tg(x) = 0
tem uma raiz no intervalo [1, 2].
(a) Use o método da secante para a calcular. Pare o processo iterativo quando
|xk+1 − xk |
≤ 0.01
|xk+1 |
e
|f (xk+1 )| ≤ 0.05
(b) Estude a convergência da implementação anterior.
3
4. A equação
1
f (x) = 1 + (sec (x)) 2 − tg (x) = 0
surge na teoria das reacções nucleares e tem várias raízes. Calcule a raiz que pertence ao intervalo [1, 1.5] usando um método iterativo que não precise do cálculo
das derivadas. Pare o processo iterativo quando os critérios de paragem forem verificados:
|xk+1 − xk |
≤ 0.05
|xk+1 |
e
|f (xk+1 )| ≤ 0.05
5. Considere a equação não linear f (x) = x + ln(x) que tem uma única raiz. Sabe-se
que esta pertence ao intervalo [0.5, 1.0].
(a) Determine uma aproximação a essa raiz através do método da secante. Considere os seguintes critérios de paragem
|xk+1 − xk |
≤ 0.005
|xk+1 |
e
|f (xk+1 )| ≤ 0.0005
(b) Determine uma aproximação a essa raiz agora através do método de Newton.
Considere o mesmo critério de paragem da alínea anterior.
(c) Repita o processo, para o método de Newton, tomando agora x0 = 3.0. Que
conclusões pode tirar desta implementação?
(d) Estude a convergência das implementações anteriores.
4
Métodos Numéricos
Exercícios
Condições de optimalidade - Limitações da solução analítica
Sistemas de equações lineares - Métodos directos
Folha 3
1. Dada a matriz


2.4
6.0 −2.7
5.0
 −2.1 −2.7
5.9 −4.0 

A=
 3.0
5.0 −4.0
6.0 
0.9
1.9
4.7
1.8
(a) Verifique se o determinante da matriz A é igual a −4.872.
(b) Calcule A−1 .
(c) Considere a matriz A e o vector b = (14.6, −11.4, 14.0, −0.9)T e resolva o
sistema correspondente recorrendo a um método directo e estável.
2. Considere a matriz A quadrada de ordem 4,

0.5 0.25
0
0
 0.25 0.5 −0.25 0 

A=
 0 −0.25 0.5 0.25 
0
0
0.25 0.5

(a) Calcule o determinante da matriz A.
(b) Calcule A−1
3. Considere a seguinte matriz quadrada


4 2 4
A= 2 1 2 
4 2 4
Calcule usando um método directo e estável o determinante da matriz dada.
4. Dada a matriz

e o vector b = (−2, 1, 0)T .

2 −1
0
2 −1 
A =  −1
0 −1
2
5
(a) Resolva o sistema correspondente recorrendo a um método directo e estável.
(b) Verifique se a matriz A é definida positiva.
5. Considere o seguinte sistema linear

 4x1 + 13x2 + 2x3 = −15
−8x1 + 10x2 + 8x3 = 6 .

2x1 + 6.5x2 + 5.5x3 = −3
(a) Resolva-o pelo método de eliminação de Gauss com pivotagem parcial.
(b) Calcule o determinante da matriz dos coeficientes.
(c) Calcule a inversa da matriz dos coeficientes.
6. Considere o seguinte sistema linear

 x1 + 2x2 + x3 = 1
2x1 + x2 + 2x3 = 3 .

x1 + 2x2 + x3 = 0
resolva-o recorrendo ao método de eliminação de Gauss com pivotagem parcial.
6
Métodos Numéricos
Exercícios
Condições de optimalidade - Limitações da solução analítica
Sistemas de equações lineares - Métodos iterativos
Folha 4
1. Dada a matriz


2 −1
0
2 −1 
A =  −1
0 −1
2
e o vector b = (−2, 1, 0)T .
(a) Estude as condições suficientes de convergência do método de Gauss-Seidel.
(b) Use o método de Gauss-Seidel para calcular a solução, considerando x(0) =
(−0.5, 0.5, 0)T, com
° (k+1)
°
°x
− x(k) °
≤ 0.1
kx(k+1) k
2. Considere o seguinte sistema linear

 8x1 + 2x2 + x3 = 1
5x1 + 4x2 + x3 = 3

x1 + 2x2 + 2x3 = 0
(a) Mostre que a matriz de iteração de Jacobi é


0 −0.25 −0.125
0 −0.25  .
CJ =  −1.25
−0.5
−1
0
(b) Estude as condições suficientes de convergência do método de Jacobi.
(c) Aplique o método iterativo de Jacobi, considerando x(0) = (0, 1.2, −0.8)T e
° (k+1)
°
°x
− x(k) °
≤ 0.25
kx(k+1) k
7
3. Considere o sistema

 x1 + 0.5x2 + 0.5x3 = 2
0.5x1 + x2 + 0.5x3 = 2

0.5x1 + 0.5x2 + x3 = 2
(a) Verifique as condições suficientes de convergência do método de Gauss-Seidel.
(b) Use o método de Gauss-Seidel para calcular a solução, com
° (k+1)
°
°x
− x(k) °
≤ 0.3
kx(k+1) k
4. Considere o seguinte sistema de equações lineares

2x1 + 0.5x2 = 1




 0.5x1 + x2 = 1
2x3 = −1


x4 + x5 = 1



x4 + 2x5 = −1
Pretende-se resolvê-lo usando o método de Gauss-Seidel.
(a) Estude a convergência do referido método.
(b) Implemente o método para resolver o sistema. Pare o processo iterativo quando
uma das seguintes condições for verificada:
°
° (k+1)
°x
− x(k) °
≤ 0.5
i.
kx(k+1) k
ii. número máximo de iterações = 3.
8
Métodos Numéricos
Exercícios
Condições de optimalidade - Limitações da solução analítica
Sistemas de equações não lineares
Folha 5
1. Determine uma aproximação à solução do sistema não linear
½ 3
4x1 + 16x2 = 0
4x32 + 16x1 = 0
através do método de Newton. Considere como aproximação inicial o vector (1, 1)T e
para o critério de paragem use os valores
°
° (k+1)
°x
− x(k) °
≤ 0.01
kx(k+1) k
e.
°
°
°f (x(k+1) )° ≤ 0.005
2. Determine uma aproximação à solução do sistema não linear

µ
¶
+
x
x

1
2

 2x1 = sin
µ 2 ¶
x1 − x2


 2x2 = cos
2
através do método de Newton. Considere como aproximação inicial o vector (0, 0)T e
para o critério de paragem use os valores
°
° (k+1)
°x
− x(k) °
≤ 0.01
kx(k+1) k
e.
°
°
°f (x(k+1) )° ≤ 0.005
3. Calcule a solução do sistema de equações não lineares
½ 2
x1 + x22 = 5
ex1 + x2 = 3
Tome para aproximação inicial o vector (−0.1, 2)T .
9
Pare o processo iterativo quando o critério de paragem for verificado para
°
° (k+1)
°x
− x(k) °
≤ 0.05
kx(k+1) k
e.
°
°
°f (x(k+1) )° ≤ 0.01
ou quando atingir as 2 iterações (completas).
4. O sistema de equações não lineares
½
x21 − x22 − 1
= 0
(x21 + x22 − 1) (x21 + x22 − 2) = 0
tem uma raiz na vizinhança do ponto (1, 1)T . Calcule-a usando o método iterativo
de Broyden. Pare o processo iterativo quando o critério de paragem for verificado
para
°
° (k+1)
°x
− x(k) °
≤ 0.5
kx(k+1) k
e.
ou ao fim da primeira iteração.
°
°
°f (x(k+1) )° ≤ 0.5
5. Calcule uma das soluções do seguinte sistema
 5
 x1 + x32 x43 + 1 = 0
x2 x2 x3
= 0
 14
x3 − 1
= 0
usando o método de Broyden. Inicie o processo com a aproximação (−1, 0, 1.5)T .
Pare o processo iterativo ao fim de 2 iterações.
10
Métodos Numéricos
Exercícios
Optimização não linear sem restrições
Optimização numérica unidimensional
Folha 6
1. Dada a função f : IR → IR definida por
f (x) = x2 + 4 |x − 1|
calcule o seu mínimo usando o algoritmo de Fibonacci. O processo iterativo deve
ser iniciado com N = 4 e pelo intervalo [0.7, 1.3].
2. Dada a função f : IR → IR definida por
½
|x|
para x < 0
2
x − x para x ≥ 0
calcule o seu mínimo usando o algoritmo de Fibonacci. O processo iterativo deve
ser iniciado com o intervalo [−2, 2].
Considere N = 10 e ε = 0.0000001.
3. Dada a função f : IR → IR definida por
f (x) = x2 + 2e−x
calcule o seu mínimo usando o algoritmo de Davies, Swann e Campey (DSC),
baseado na interpolação quadrática. O processo iterativo deve ser iniciado com
o ponto x0 = 0.
Considere δ = 1, M = 0.5 e ε = 0.5.
4. Considere a função f : IR → IR definida por
½
(x − 1)2 para x ∈
/ [0, 2]
1
para x ∈ [0, 2]
Implemente o algoritmo de Davies, Swann e Campey (DSC), baseado em interpolação quadrática, fazendo x0 = 4, δ = 0.5 e M = 0.5.
5. Dada a função f : IR → IR definida por
f (x) = x2 − x
calcule o seu mínimo usando o algoritmo de Davies, Swann e Campey (DSC),
baseado na interpolação quadrática. O processo iterativo deve ser iniciado com
o ponto x0 = 2.
Considere δ = 1, M = 0.5 e ε = 0.5.
11
Métodos Numéricos
Exercícios
Optimização não linear sem restrições
Optimização numérica multidimensional
Folha 7
1. Calcule o mínimo da função f (x) definida por
¡
¢
f (x1 , x2 ) = máx (x1 − 1)2 , x21 + 4 (x2 − 1)2
implementando o método de Nelder-Mead, tomando para conjunto inicial os vectores
µ ¶ µ ¶ µ ¶
1
0
1
,
e
0
0
1
e ε = 0.5.
2. Dada a função f : IR2 → IR definida por
f (x1 , x2 ) = x21 + x22 − 2x1 x2
calcule o seu mínimo usando o método de Nelder-Mead.
O processo iterativo deve terminar quando o critério de paragem for verificado para
ε = 0.1. Considere os seguintes pontos iniciais:
(0.1, −0.1)T , (−0.1, 0.1)T e (0.1, 0.1)T .
12
Métodos Numéricos
Exercícios
Optimização não linear sem restrições
Optimização numérica multidimensional
Folha 8
1. Dada a função f : IR2 → IR definida por
f (x1 , x2 ) = x1 x22 + (2 − x1 )2
calcule o seu mínimo usando o algoritmo de segurança de Newton.
O processo iterativo deve ser iniciado com o ponto (1, 1) e deve terminar quando o
critério de paragem for verificado para ε1 = ε2 = ε3 = 0.1. Considere η = 0.0001.
Deve implementar o algoritmo de procura unidimensional exacta para calcular o
comprimento do passo α, em cada iteração.
2. Dada a função f : IR2 → IR definida por
f (x1 , x2 ) = −x21 − 6x22
calcule o seu máximo usando o algoritmo de segurança de Newton.
O processo iterativo deve ser iniciado com o ponto (1, −1) e deve terminar quando
o critério de paragem for verificado para ε1 = ε2 = ε3 = 0.5. Considere η = 0.0001.
Deve implementar o algoritmo de Davies, Swann e Campey (DSC), baseado na
interpolação quadrática, para calcular o comprimento do passo α, em cada iteração.
Nesta fase, considere como valor de partida α1 = 0 e δ = 1
3. Dada a função f : IR2 → IR definida por
f (x1 , x2 ) = x21 + x22 − x1 x2
calcule o seu mínimo usando o algoritmo Quasi-Newton, na versão DFP.
O processo iterativo deve ser iniciado com o ponto (1, 0) e deve terminar quando o
critério de paragem for verificado para ε3 = 0.02. Para calcular o comprimento do
passo α, use, em cada iteração, o algoritmo de procura unidimensional exacta.
4. Dada a função f : IR2 → IR definida por
f (x1 , x2 ) = (x1 − 1)2 + (x2 − 1)3
calcule o seu mínimo usando a versão mais adequada do algoritmo dos gradientes
conjugados.
O processo iterativo deve ser iniciado com o ponto (2, 1.1) e deve terminar quando
a direcção de procura calculada verificar kdk2 < 0.1. Deve também, implementar
o algoritmo das repetidas divisões de α por dois para calcular o comprimento do
passo α.
13
5. Dada a função f : IR2 → IR definida por
f (x1 , x2 ) = x21 + x22 − 2x1 x2
calcule o seu mínimo usando a versão mais adequada do algoritmo dos gradientes
conjugados.
O processo iterativo deve ser iniciado com o ponto (1, −1) e deve terminar quando
o critério de paragem for verificado para ε1 = ε2 = ε3 = 0.01.
Deve, também, implementar o algoritmo das repetidas divisões de α por dois para
calcular o comprimento do passo α, em cada iteração.
14
Métodos Numéricos
Exercícios
Aproximação dos mínimos quadrados
Folha 9
1. Um carro inicia a sua marcha num dia frio de inverno e um aparelho mede o consumo
de gasolina verificado no instante em que percorreu x Km. Os resultados obtidos
foram:
x
distância em Km
f (x)
l
consumo em Km
0
1.25
2.5
3.75
5
6.25
0.260 0.208 0.172 0.145 0.126 0.113
Construa um modelo quadrático, para descrever o consumo de gasolina em função
da distância percorrida, usando a técnica dos mínimos quadrados.
2. Pretende-se ajustar o modelo linear
M(x; c1 , c2 , c3 ) = c1 e−x + c2 x + c3
à função f (x) dada pela tabela
xi
−1 0 1
2
f (xi ) 1.4 0 0.75 2.3
no sentido dos mínimos quadrados. Determine os coeficientes do modelo apresentado. Apresente uma estimativa para f (0.5).
3. Implemente o método de Newton, com o objectivo de ajustar o melhor possível o
modelo
M (x; c1 , c2 ) = c1 x + e(c2 x)
à função f (x) dada pela seguinte tabela de 3 pontos
xi
fi
-1 0 1
0 1 2
no sentido dos mínimos quadrados. Como aproximação inicial aos parâmetros considere o vector (1, 1)T . Páre o processo iterativo quando o critério de paragem for
verificado para ε2 = 0.75.
15
4. Implemente o método de Gauss-Newton, com o objectivo de ajustar o melhor possível o modelo
M (x; c1 , c2 ) = c1 + sen (c2 x)
à função f (x) dada pela seguinte tabela de 3 pontos
xi
fi
-1
0
1
0.9 1.0 1.1
no sentido dos mínimos quadrados. Como aproximação inicial aos parâmetros considere o vector (1, 3)T . Páre o processo iterativo quando o critério de paragem for
verificado para ε1 = ε2 = 0.02.
16
Métodos Numéricos
Exercícios
Optimização não linear com retrições
Condições de Optimalidade
Folha 10
1. Considere o problema
min 2(x21 + x22 − 1) − x1
sujeito a
x21 + x22 − 1 = 0.
Mostre que x∗ = (1, 0)T é um mínimo local e λ∗ =
associado a ele.
3
2
é o vector dos multiplicadores
2. Considere o seguinte problema de optimização
minf (x) ≡ (x1 − 2)2 + (x2 − 2)2 + (x3 − 3)2 + (x4 − 4)2
x∈IR4
sujeito a
c1 (x) ≡ x1 − 2 = 0
c2 (x) ≡ x23 + x24 − 2 = 0.
Verifique as condições necessárias e suficientes de optimalidade.
17