Algoritmo e Convergencia

Prévia do material em texto

Algoritmo e Convergência
Pedro H. A. Konzen
Instituto de Matemática e Estatística - UFRGS
Agosto, 2016
Algoritmo
Um algoritmo é um procedimento determinado por uma dada
sequência finita de passos.
Exemplo (Algoritmo do somatório (pseudo-código))
N∑
i=1
xi = x1 + x2 + · · ·+ xN
ENTRADA N, x1, x2, · · · , xN
SAÍDA SOMA =
∑N
i=1 xi
Passo 1 Faça SOMA = 0. (Inicializar acumulador.)
Passo 2 Para i = 1, 2, · · · ,N execute
(Adicionar o próximo termo.)
faça SOMA = SOMA+ xi .
Passo 3 SAÍDA (SOMA);
PARE.
Algoritmo
Exemplo (Código Scilab do somatório)
function [SOMA] = somatorio (N, x)
SOMA = 0 //inicializar acumulador.
for i = 1:N
//Adicionar o próximo termo.
SOMA = SOMA + x(i)
end
endfunction
-->N = 3
N =
3.
-->x = [1, 2, 3]
x =
1. 2. 3.
-->y = somatorio(N,x)
y =
6.
Critério de Estabilidade
Um algoritmo é dito estável quando pequenas alterações nos seus
dados iniciais produzem alterações correspondentemente pequenas
nos resultados finais.
I Algoritmo instável = algoritmo não estável.
I Algoritmo condicionalmente estável: aquele que é estável
somente para certas escolhas de dados iniciais.
Crescimento do erro
Definição (Classificação do crescimento do erro)
I E0 denota o erro inicial
I En denota o erro após n operações
I Se En = C · n · E0, então crescimento do erro linear (estável)
I Se En = CnE0, (C > 1), então crescimento do erro
exponencial (instável)
Observação
Algoritmos com crescimento do erro exponencial devem ser
evitados sempre que possível.
Exemplo: estável!
Exemplo
A equação recursiva
pn = 2pn−1 − pn−2, (n = 3, 4, . . .)
tem solução
pn = C1 + C2n
onde
C1 = p1, C2 = p2 − p1
Tomando p1 = 1 e p2 = 13 , então a solução particular exata é
pn = 1− 23(n − 1)
Exemplo: estável!
Exemplo (Continuação)
Suponhamos que p1 = pˆ1 + E0 e p2 = pˆ2 + E0, então:
En = |pn − pˆn| = (2n − 1)E0
i.e.
En ≈ CnE0, (C = 2), (n� 0)
-->n=linspace(0,1e6); E0 = %eps;
-->plot(n,(2*n-1)*E0)
Exemplo: estável! - CONTINUAÇÃO
Da análise do erro feita acima, concluímos que o seguinte
algoritmo é estável:
function p = estavel(n)
p = [1, 1/3]
for i = 3:n
p = [p, 2*p(i-1) - p(i-2)]
end
endfunction
-->deff('y = p(n)','y = 1 - (2/3) .* (n-1)')
-->x = 1:1e4;
-->plot(x,estavel(1e4),'b.-',x,p(x),'r-'
-->plot(abs(estavel(1e4)-p(x)))
Exemplo: instável!
Exemplo
A equação recursiva
pn =
10
3 pn−1 − pn−2, (n = 3, 4, . . .)
com p1 = 1 e p2 = 1/3 tem solução:
pn =
(1
3
)n−1
Exemplo: instável!
Exemplo (Continuação)
Agora, se p0 = pˆ0 + E0 e p1 = pˆ1 + E0, então
En = |pn − pˆn| = 34
(1
3
)n
E0 +
1
43
nE0
i.e.
En ≈ CnE0, (C = 3), (n� 0)
-->n=linspace(0,35); E0 = %eps;
-->plot(n,((3/4)*(1/3)^n) * E0 + ((1/4) * 3^n) * E0)
-->xlabel("n"), ylabel("E_n")
Exemplo: instável! - CONTINUAÇÃO
Da análise do erro feita acima, concluímos que o seguinte
algoritmo é instável:
function p = instavel(n)
p = [1, 1/3]
for i = 3:n
p = [p, (10/3)*p(i-1) - p(i-2)]
end
endfunction
-->deff('y = p(n)','y = (1/3) .^ (n-1)')
-->x = 1:35;
-->plot(x,instavel(1e4),'b.-',x,p(x),'r-')
-->plot(abs(instavel(35)-p(x)))
Taxa de Convergência (sequências)
Definição
I βn → 0
I αn → α
I Se |αn − α| ≤ K |βn|, K > 0 e n� 0, então αn = α+ O(βn)
i.e.
{αn}∞n=1 converge para α com taxa de convergência O(βn)
Observação
Muitas vezes estaremos interessados em comparar a taxa de
convergência de uma sequência numérica dada {αn} com relação a
sequência
βn =
1
np .
Isto é, é de grande interesse estimar o maior p tal que
αn = α+ O(1/np)
Taxa de Convergência (funções)
Definição
I lim
h→0
G(h) = 0
I lim
h→0
F (h) = L
I Se |F (h)− L| ≤ K |G(h)|, K > 0 e h ≈ 0, então
F (h) = L+ O(G(h))
Observação
É de grande interesse estimar o maior p tal que
F (h) = L+ O(hp)
Exercício
Exercício
(Fixação.) Seja f (x) = ln(x) e PN(x) sua expansão por série de
Taylor em torno de x0 = 1, i.e.
PN(x) =
N∑
i=1
(−1)i+1
i (x − 1)
i
(a) Calcule os erros absoluto e relativo ao aproximar f (1, 5) por
P5(1, 5).
(b) Faça um gráfico do erro absoluto em função do número de termos
da série de Taylor.
(c) Com base no gráfico da letra (b), infira sobre a taxa de
convergência do erro em função do número de termos da série de
Taylor. Compare sua resposta com a estimativa teórica do erro da
série de Taylor.
(d) Implemente no Scilab o pseudo-código do Exemplo 2 da seção 1.3
do Livro Texto.