05 criterio de parada

Prévia do material em texto

Critérios de Parada e Aceleração da Convergência 
 
Esses critérios NÃO se restringem apenas aos métodos da Dicotomia e das 
Aproximações Sucessivas. 
ITMAX - critério que garante a repetição até um número máximo de 
iterações 
 
 
Independente do problema que estamos tratando, sempre que a solução é 
determinada numericamente é preciso estabelecer critérios para avaliar a 
qualidade da resposta além de estabelecer critérios que garantam a parada do 
algoritmo. Esses critérios de parada devem contemplar a precisão da solução. 
Um critério que sempre dever estar presente os métodos iterativos é o ITMAX, ou 
número de iterações máximas. Isso evita que seu algoritmo entre em loops 
infinitos. Entretanto, é necessário saber se seu algoritmo foi interrompido por esse 
critério, pois isto pode significar que NÃO foi atingido o critério de precisão. 
Lembrando o exemplo do Método das Aproximações Sucessivas , 
para a função f(x) = x2 - x -2, intervalo [0,3] que contém a raiz 2, foi 
usado x0 =3, como valor inicial e a função φ1 (x) = x2 - 2, para definir 
a seqüência das iteradas. Obtivemos, 
3, 7, 47,2.207 X 103, ... como resultado das sucessivas 
aplicações. 
Se não incluirmos um critério por número máximo de iterações, um erro 
de overflow
 
vai ocorrer, já que os valores determinados pelo algoritmo 
aumentam a cada iteração. 
Algoritmo com ITMAX: 
� n, x0 ITMAX; 
 
� x
n+1 =φ (xn); 
� pare se 
� precisão foi atingida 
� ou 
� n+1 >ITMAX 
 
Erro absoluto em função de duas iteradas consecutivas 
Página 1 de 8Critérios de Parada para Zeros de Funções
21/8/2009file://F:\DISCIPLINAS\CALC_NUM\AULAS\zeros\zeros_criterio_parada.htm
A comparação entre duas iteradas consecutivas pode não garantir que uma 
determinada precisão seja atingida. 
Seja a seqüência {x0, x1, x2, ..., xn-1, xn,...} gerada por φ (x
n
), a partir do chute 
inicial x0. 
O erro entre duas iteradas consecutivas é definido por: 
En = | xn - xn-1 | 
Verificar que En
 
≤ δ, onde δ é a precisão pré-fixada, não garante que a 
precisão foi atingida, ou seja que | f(xn)| ≤
 
δ. Mas o seguinte corolário, 
com base no teorema do ponto fixo, mostra como obter um limite 
superior para o erro de truncamento da k-ésima iterada. 
Corolário: Sejam φ, X_exata e k, tal que , satisfazendo 
as hipóteses do teorema do ponto fixo. 
Se 
x
n
 = φ (x
n-1)
 
então 
| X_exata - xn | ≤ k / (1-k) * | xn - x n-1| 
Impondo 
k / (1-k) * | xn - x n-1| ≤ δ, 
garantimos que a solução aproximada está dentro dos critérios 
estabelecidos. 
Algoritmo com ITMAX e erro absoluto: 
� n, x0 ITMAX; 
 
�
 x
n+1 =φ (xn); 
� pare se 
� | X_exata - x n | ≤≤≤≤ k / (1-k) * | xn - x n-1| ≤ ≤ ≤ ≤ δδδδ (precisão foi 
atingida) 
� ou 
� n+1 >ITMAX 
Página 2 de 8Critérios de Parada para Zeros de Funções
21/8/2009file://F:\DISCIPLINAS\CALC_NUM\AULAS\zeros\zeros_criterio_parada.htm
 
Aceleração da convergência - Precisão pré-fixada 
É claro que é aconselhável que todo algoritmo pare por critérios que garantam 
precisões pré-fixadas e sempre iremos buscar esse objetivo. 
1. Verificando se uma precisão pré-fixada foi atingida 
É sempre possível substituir o valor obtido pela n-ésima iterada na 
função f e verificar se a precisão foi atingida. 
Algoritmo que verifica se uma precisão δδδδ foi atingida: 
� n, x0 ITMAX; 
 
�
 x
n+1 = φ (xn); 
� pare se 
� | f( xn+1) | ≤ δ (precisão foi atingida) 
� ou 
� | X_exata - x n | ≤≤≤≤ k / (1-k) * | xn - x n-1| ≤ ≤ ≤ ≤ δδδδ (precisão foi 
atingida) 
� ou 
� n+1 > ITMAX (número máximo de iterações) 
 
Observação: apesar da vantagem em oferecer uma delimitação 
para o erro absoluto, a dificuldade é o cálculo de k 
2. Usando a seqüencia gerada pelas iteradas 
Para garantir uma precisão pré-fixada precisamos ter uma idéia de 
onde a solução exata se encontra, ou seja é preciso confinar a solução 
exata em um intervalo de tamanho finito. 
Ao isolarmos uma única raiz num intervalo [a, b], tal que f(a)*f(b) < 
0, conseguimos esse intervalo de tamanho finito. 
No método da dicotomia sabemos que a raiz exata encontra-se 
SEMPRE entre duas iteradas consecutivas. No método das 
aproximações sucessivas, isso ocorre somente quando a seqüência 
gerada pela φ for oscilante. Caso essa seqüência seja crescente (ou 
decrescente) a raiz exata está sempre à direita (ou esquerda) das 
iteradas e precisamos de alguma forma confinar a raiz exata para 
podermos avaliar se a precisão pré-fixada foi atingida. 
Página 3 de 8Critérios de Parada para Zeros de Funções
21/8/2009file://F:\DISCIPLINAS\CALC_NUM\AULAS\zeros\zeros_criterio_parada.htm
Os casos de seqüências oscilante, crescente ou decrescente serão 
estudados a seguir. 
Caso1: seqüência oscilante 
Considere uma seqüêcia de iteradas oscilante e 
convergente para a raiz ( uma seqüencia como essa pode 
ser gerada por vários métodos numéricos), representada na 
Figura 1. 
 
Figura 1 
Neste caso a raiz α está sempre confinada entre duas 
iterações consecutivas ou seja α [ x
n
,x
n+1 ] (ou 
[ x
n+1,xn]). Logo, o valor de x5 estará certamente no sub-
intervalo [x3 , x4 [. 
Se escolhermos como valor aproximado para a raiz 
Xa = [ xn+xn+1] / 2
 
o erro cometido será no máximo 
En = | xn+1- xn| / 2.
 
 Para definir uma aproximação com precisão pré-fixada δ, 
basta escolher 
En = | xn+1- xn| / 2 ≤ δ 
 
Algoritmo que verifica se uma precisão 
δδδδ
 foi atingida no caso de seqüências 
oscilantes: 
� n, x0 ITMAX; 
 
� x
n+1 = φ (xn); 
Página 4 de 8Critérios de Parada para Zeros de Funções
21/8/2009file://F:\DISCIPLINAS\CALC_NUM\AULAS\zeros\zeros_criterio_parada.htm
� pare se 
� | f(xn+1) | ≤ δ (precisão foi atingida) 
� ou 
� | X_exata - x n | ≤≤≤≤ k / (1-k) * | xn - x 
n-1| ≤≤≤≤ δδδδ (precisão foi atingida) 
� ou 
� En = | xn+1- xn| / 2 ≤ δ (precisão foi 
atingida) 
� ou 
� n+1 > ITMAX (número máximo de 
iterações) 
Caso2: seqüência crescente ou decrescente 
Considere um intervalo I que contenha a raiz α, 
para o qual foi verificado que a seqüência 
definida por φestá totalmente contido nele e é 
convergente para a raiz. Considere que a 
seqüência que converge para a raiz é crescente . 
Como a seqüência é crescente e convergente, 
a raiz sempre estará à direita de qualquer valor 
φ(xk). 
Para confinar a raiz temos que tentar 
ultrapassá-la. 
Seja δ > 0 a precisão pré-fixada . 
Se, ao invés de calcularmos a aproximação φ
(x
n
) calcularmos φ(x
n
+2δ), o processo 
iterativo será acelerado, já que o ponto onde 
será calculada a próxima iterada será "jogado" 
para a direção da raiz. 
Este processo de aceleração deve ser 
repetido até que o ponto ultrapasse a raiz. 
Isto está ilustrado na Figura2. 
Página 5 de 8Critérios de Parada para Zeros de Funções
21/8/2009file://F:\DISCIPLINAS\CALC_NUM\AULAS\zeros\zeros_criterio_parada.htm
 
 
Figura 2 
� início das iteradas com o chute x0; 
� região rosa: indica a posição do ponto 
adicionado de 2δ(no caso o ponto x3 foi 
levado para x3 + 2δ); 
� região verde: região onde a aproximação 
atinge a precisão pré fixada, é um intervalo 
de tamanho ( α - δ, α +δ) 
� se xk+2δ está a esquerda da raiz,o valor de 
 φ(xk+2δ) estará a direita de xk+2δ (pois a 
seqüência é sempre crescente e não 
ultrapassa a raiz). Essa relação é 
representada por 
x
n
+2δ φ(x
n
+2δ) ; 
 
� quando x
n
+2δ ultrapassar a raiz, φ(x
n
+2δ) 
ficará à esquerda de x
n
+2δ, pois φ é 
convergente para a raiz em
 I. A região 
cinza indica onde poderá cair φ(x
n
+2δ) e, 
portanto, a desigualdade acima fica 
x
n
+2δ φ(x
n
+2δ) ; 
 
Portanto, quando troca a desigualdade 
conseguimosidentificar um intervalo que conté a 
raiz, que é aquele definido por [x
n
,x
n
+2δ]. 
Quando esta última situação ocorrer, a raiz α 
[x
n
,x
n
+2δ]. 
Página 6 de 8Critérios de Parada para Zeros de Funções
21/8/2009file://F:\DISCIPLINAS\CALC_NUM\AULAS\zeros\zeros_criterio_parada.htm
Se tomarmos 
Xa = x
n
+δ
 
temos garantido que o erro absoluto é menor 
que δ. 
No exemplo mostrado na Figura 2, é o intervalo 
[x4,x4+2δ]. 
De maneira análoga procedemos para 
seqüências que são decrescentes para a raiz, 
subtraindo de cada iterada o valor 2δ. 
 
 
Algoritmo que verifica se uma precisão 
δδδδ
 foi atingida no caso de seqüências 
crescentes: 
se a seqüência das iteradas é crescente então 
x
n
+2δ - φ(x
n
+2δ) ≤≤≤≤ 0, enquanto xn+2δ está à 
esquerda da raiz. 
� n, x0 ITMAX; 
 
�
 x
n+1 = φ (xn); 
� pare se 
� | f(xn+1) | ≤ δ (precisão foi atingida) 
� ou 
� | X_exata - xn | ≤≤≤≤ k / (1-k) * | xn - x 
n-1| ≤≤≤≤ δδδδ (precisão foi atingida) 
� ou 
� x
n
+2δ - φ(x
n
+2δ) 0
 (precisão foi 
atingida) 
� ou 
� n+1 > ITMAX (número máximo de 
iterações) 
 
Algoritmo que verifica se uma precisão 
δ δ δ δ foi atingida no caso de seqüências 
Página 7 de 8Critérios de Parada para Zeros de Funções
21/8/2009file://F:\DISCIPLINAS\CALC_NUM\AULAS\zeros\zeros_criterio_parada.htm
decrescentes: 
se a seqüência das iteradas é decrescente então 
x
n
-2δ - φ(x
n
-2δ) 0, enquanto x
n
-2δ está à 
direita da raiz. 
� n, x0 ITMAX; 
 
�
 x
n+1 = φ (xn); 
� pare se 
� | f(xn+1) | ≤ δ (precisão foi atingida) 
� ou 
� | X_exata - x n | ≤≤≤≤ k / (1-k) * | xn - x 
n-1| ≤≤≤≤ δδδδ (precisão foi atingida) 
� ou 
� x
n
-2δ- φ(x
n
-2δ) ≤≤≤≤ 0 (precisão foi 
atingida) 
� ou 
� n+1 > ITMAX (número máximo de 
iterações) 
 
 
Página 8 de 8Critérios de Parada para Zeros de Funções
21/8/2009file://F:\DISCIPLINAS\CALC_NUM\AULAS\zeros\zeros_criterio_parada.htm