AN_Aula02

Prévia do material em texto

Aula de 19/02/14
INF1608
Definição de um problema do ponto fixo 
Considere a expressão polinomial
 
x5 – 3x4 – 5 x3 + 15 x2 + 4 x – 12 = 0 	 (1.2)
e, a partir dela, escreva
 15 x2 = 12 – 4 x + 5 x3 + 3x4 – x5
obtendo 
Podemos usar a expressão acima para definir valores de uma seqüência que se aproximem da raiz u = 1 da expressão (1.2). 
Usaremos esta expressão para tentar achar uma das raízes de f. Vamos atribuir à variável x um valor inicial que vamos chamar de x0 e que, neste caso, vai ser igual a zero. Aplicando o valor de x0 à expressão, chega-se a um novo valor de x, que vamos chamar de x1:
 (1.2a) 
Se x1 for exatamente igual a x0 tivemos sorte pois detectamos uma das raízes de f(x)=0, já que o valor de x usado se repetiu quando aplicamos a expressão (1.2a). Se não tivermos a sorte de acertar a raiz logo na primeira tentativa, vamos repetir esse processo, várias vezes, construindo uma seqüência { xi+1 } com elementos xi que são obtidos de 
 (1.2b)
Então, para resolver o problema (1.2) com a expressão (1.2b) e considerando-se x0 = 0, teremos os primeiros valores calculados, para i< 10:
	i
	xi
	i
	xi
	0
	0
	5
	0,993471
	1
	0,894427
	6
	0,995912
	2
	0,945967
	7
	0,997609
	3
	0,969310
	8
	0,998736
	4
	0,981348
	9
	0,999400
					Tabela 1.2
Na expressão (1.2b) vamos dar à função que fica do seu lado direito o nome de 
. Com isso podemos reescrever a mesma expressão (1.2b ) na seguinte forma
 
((xi)=
, i=1, 2, … (1.2c)
Examinando os elementos da Tabela 1.2, vemos que os elementos xi da seqüência gerada a partir de x0 e pela aplicação sucessiva da função 
, parecem se aproximar da raiz u = 1 procurada, o que vai ser confirmado mais tarde quando estudarmos os critérios de convergência de seqüências construídas dessa forma.
Esse é um exemplo da construção de uma seqüência gerada por uma função de iteração convergente.
	Outras funções de iteração podem ser usadas, a partir da equação f(x) = 0 para se tentar atingir a raiz u = 1 do polinômio 
 f(x) = x5 – 3x4 – 5 x3 +15 x2 + 4 x – 12. 
Por exemplo: 
 
 
 
 
 
	Essas funções de iteração, com 
= 0, fornecerão as seqüências:
	 
	
	
	
	x0 = 0
	x0 = 0
	x0 = 0
	x0 = 0
	0,894427
	 (- 4)1/4
	 -1.3388659
	1,6437518
	0,945967
	 ___
	-.9589382184
	1,5519745
	0,969310
	 ___
	- 1.025350232 
	1,41922377
	0,981348
	 ___
	 -.9851515395
	1,20816139
	0,993471
	 ___
	 -1.009013886
	0,86411929
	0,995912
	 ___
	 -.9946344251
	 1,17522908
	0,997609
	 ___
	 ...
	0,84087179
	0,998736
	 ___
	 ...
	1,20142342
	Converge à raiz u1 = 1 
	 Número Imaginário; não converge a u1= 1
	 Converge à raiz 
 u2 = -1
	No início parece que vai convergir para u1 = 1, o que não ocorre; fica com valores oscilantes
 Tabela 1.3
Voltando às observações sobre a função dada, pode-se verificar que, quando o processo é convergente, as diferenças
 
 
isto é, 
 
 
diminuem gradativamente. Esse comportamento nos leva a considerar que, se a seqüência obtida com a função de iteração dada tem um ponto limite (chamado de u), e se fosse possível atingir esse limite da seqüência 
, poderíamos garantir que:
 
,	
isto é, 			
 
. 				 (1.3)
Isso quer dizer que u é um ponto que não muda ao se aplicar a ele a função 
. Formalmente, quando isso acontece, diz-se que u é invariante em relação à aplicação da função 
. Isso é caracterizado dizendo-se que u é ponto fixo de 
.
	A definição de uma seqüência que fornece elementos que se aproximam mais e mais uns dos outros e da raiz buscada é um exemplo da obtenção de um proces​so iterativo convergente. Necessitam-se, portanto, de algumas definições e conceitos básicos sobre iterações para que se esteja apto a resolver equações algébricas com métodos da forma (1.1a).
	Para se estudar o que está acontecendo com a seqüência construída anteriormente, devemos nos situar em relação ao uso de funções de iteração.
 De forma geral, pode-se dizer que uma iteração gera um processo infinito através do qual se cria uma seqüência. A defi​nição desse processo, como foi visto no caso da equação (1.2c), necessita de quatro elemen​tos:
a ligação entre a aproximação da variável em um passo i e o sucessivo passo i+1, isto é, uma função de iteração que chamamos de 
;
a escolha de um valor inicial 
;
a verificação da possível convergência da seqüência 
 à solução u, isto é um critério de convergência;
a verificação da qualidade da aproximação obtida, isto é, um critério para a determinação do número de passos de iteração que serão necessários para se atingir uma certa precisão.
	Para se estudar esses elementos, é necessário examinar com cuidado o novo problema que está sendo definido. 
Exemplo 1.6
Considere a função 
, x pertencente ao intervalo [ 0 , 1 ]. Seu gráfico é:
> plot(4.*cos(t)-exp(t),t=-3..2);
 
 Gráfico 1.5
Então, vê-se que f tem uma raiz próxima de 1. Construindo-se a função de iteração 
 e dando-se a x o valor inicial 0,9 , obtém-se a seqüência dada pelo programa: 
> fiter:=xx->ln(4.*cos(xx));
xx:=0.9;
for i from 1 to 29 do 
xx:=fiter(xx);
end do;
derivfiter:=D(fiter);derivfiter(xx);
 
 
 
...
Claramente essa seqüência não converge. Então, a função de iteração resultou inútil. Vamos usar outra. 
Consideremos, agora, a função 
. Sua aplicação fornece:
> Digits:=30;
f:=x->exp(x)-4.*cos(x); f_iter:=x->arccos(0.25*exp(x));
x[0]:=0.5;
d:=50;
for n from 1 to d do
x[n]:=f_iter(x[n-1]);
end do:
aproximação:=x[d]: erro[d]:=abs(x[d]-x[d-1]):
valordafunção:=f(x[d]):
 for i from 0 to d-2 do
 taxa:=abs((x[i+2]-x[i+1])/(x[i+1]-x[i])):
 end do:
valor_da_aproximacao_com_a_funcao_iter_com_d_iteracoes:=x[d];
valor_do_erro_associado_ao_valor_calculado_com_d_iteracoes:=erro[d];
valor_de_f_no_ponto_calculado_com_d_iteracoes:=f(x[d]);
valor_da_taxa_de_convergencia_de_iter_com_d_iteracoes:=taxa;
Os resultados mostram que esta função é convergente. Por que?
No programa anterior, foi calculada uma constante chamada de taxa de convergência. Ela nos dá uma indicação sobre a convergência ou não da seqüência usada. Vamos falar mais sobre ela um pouco adiante. 
Lembre-se desse exemplo. Analise o programa e seu resultado. Você vai ver que a função de iteração, neste caso, forneceu uma seqüência que converge à raiz procurada. Então, dizemos que ela é convergente à essa raiz. 
Exemplo 1.7
, com raiz no intervalo [ 0 , 1 ].
> fiter:=x->sqrt(sin(x));
x:=0.9;
for i from 1 to 30 do 
x:=fiter(x);
end do;
...
Os valores obtidos por essa função de iteração convergem a uma raiz de f próxima a 0,877.
Exemplo 1.8
Determinar as raízes de f(x) = ex - ln(20x), com uma raiz real no intervalo [ 0 , 2 ]: ~1.175927162170410
Inicialmente é visto o comportamento da função f.
 
> solve(exp(z)-ln(20.*z),z);
# nos fornece o valor de uma das raízes da função f
 > plot(exp(z)- ln(20.*z), z=0..2);
# nos fornece o grafico de fGráfico 1. 6
> plot([exp(t), ln(20*t)], t=0..2, y=0..4,color=[blue, red] );
 # nos fornece os gráficos de duas funções separadas, ex (em cor azul) e ln(20x) (em cor vermelha)
Gráfico 1.7
Neste exemplo são vistos os gráficos de f e de suas duas componentes, exp (x) e ln(20x) .
O Gráfico 1.6 mostra as 2 raízes de f: pontos próximos de 0,2 e de 1,2.
O Gráfico 1.7 mostra a interseção das duas curvas que representam as duas funções exp e ln: os pontos de interseção dessas funções são exatamente as raízes de f!
Continuando-se o exemplo, vê-se que, de f(x) = ex - ln(20x), f(x) = 0, obtém-se 
 ex = ln(20x)
para gerar uma função de iteração pode-se “tirar o valor de x” pelo menos de duas formas, fazendo-se : 
 
x = ln(ln(20.*x)) 
ou 
x = exp(exp(x))/20.
No primeiro caso, a aplicação da iteração fornece:
> Digits:=40;
 x:=0.2;
for i from 1 to 8 do
x:=ln(ln(20.*x));
od;
Neste caso, verifica-se a convergência para uma das 2 raízes de f, próxima a 1,139554...
No segundo caso, fica:
> valor_da_funcao:=exp(x)-ln(20.*x);
x:=0.2;
for i from 1 to 8 do
x:=exp(exp(x))/20.;
od;
valor_da_funcao:=exp(x)-ln(20.*x);
Neste caso, verifica-se a convergência para a outra raiz de f, próxima a 0,162057...
Exemplo 1.9 
Determinar as raízes de 
, no intervalo [ 1 , 2] .
Façamos, inicialmente, 
. 
Consideremos, agora, a função de iteração 
. 
Para entender melhor a iteração, podemos fazer o gráfico das duas funções que se interceptam, representado os dois lados da equação 
. 
Os pontos de interseção são as raízes de f, mostradas no gráfico abaixo: 
> fi1:=x->x^2-2;
 plot([x,fi1(x)],x=-3..3,color=[red,blue]);
Gráfico 1.8
Como já se disse, os dois pontos de interseção das funções 
 
 
representam as duas raízes da função f original! Confira.
A seguir é mostrado o programa que aplica a função de iteração anteriormente indicada e os gráficos de f(x)= x^2-x-2 e g(x) = x e de h(x) = x^2-2.
 > Digits:=20;
 # f(x)=x^2-x-2 
 # calculo_das_raizes_de_f(x)=0
print(calculo_das_raizes_de_f(x)=0);
#inicialmente vamos plotar as funções
f:=x->x^2-x-2.; plot(x^2-x-2.,x=-3..3);
fi1:=x->x^2-2.; plot(x^2-2.,x=-3..3);
plot([x,fi1(x)],x=-3..3,color=[red,blue]);
fi2:=x->sqrt(x+2.);
plot(sqrt(x+2.),x=-3..3);
plot([x,fi2(x)],x=-3..3,color=[red,blue]);
x[0]:=3.;
 
 
 Gráfico 1.9 Gráfico 1.10
 de f(x)=x2-x-2 de fi1(x)=x2-2 e de g(x) = x 
 
 Gráfico 1.11 Gráfico 1.12
 de fi2(x)=
 de fi2(x) e de g(x) = x
# aproximacao_com_a_funcao_fi1
print(aproximacao_com_a_funcao_fi1);
for n from 1 to 4 do
x[n]:=fi1(x[n-1]);
erro:=abs(x[n]-x[n-1]);
end do:
 for i from 0 to 2 do
 taxa:=abs(x[i+2]-x[i+1])/(x[i+1]-x[i]);
 end do:
valor_da_aproximacao_com_a_funcao_fi1_com_4_iteracoes:=x[4];
valor_do_erro_associado_ao_valor_calculado_com_4_iteracoes:=erro;
valor_de_f_no_ponto_calculado_com_4_iteracoes:=f(x[4]);
valor_da_taxa_de_convergencia_de_fi1_com_4_iteracoes:=taxa;
 
> # aproximacao_com_a_funcao_fi2
print(aproximacao_com_a_funcao_fi2);
for n from 1 to 4 do
x[n]:=fi2(x[n-1]);
erro:=abs(x[n]-x[n-1]);
end do:
 for i from 0 to 2 do
 taxa:=abs(x[i+2]-x[i+1])/(x[i+1]-x[i]);
 end do:
valor_da_aproximacao_com_a_funcao_fi2_com_4_iteracoes:=x[4];
valor_do_erro_associado_ao_valor_calculado_com_4_iteracoes:=erro;
valor_de_f_no_ponto_calculado_com_4_iteracoes:=f(x[4]);
valor_da_taxa_de_convergencia_de_fi2_com_4_iteracoes:=taxa;
Verifique o que ocorreu, em relação à convergência.
Como foi visto antes, a convergência da seqüência gerada pela iteração depende de sua estrutura. Por exemplo:
M:=90;
Digits:=60;
fi1:=x->arccos(exp(x)/4.);
x[0]:=1.; x[1]:=fi1(x[0]);
for i from 2 to M do
x[i]:=fi1(x[i-1]);
od;
for i from 2 to M do
taxa:=abs((x[i]-x[i-1])/(x[i-1]-x[i-2]));
od;
x[M];	taxa;	derivada_de_fi1:= D(fi1);
abs(derivada_de_fi1(x[M]));
....
...
_1279707178/��
_1356780634.unknown
_1356780825.unknown
_1405941135.unknown
_1356782824.unknown
_1356780816.unknown
_1296296903/��
_1296394681.unknown
_1296296912/��
_1296296900/��
_1279707224.unknown
_1279707196.unknown
_1233735131.unknown
_1278757908.unknown
_1278758017.unknown
_1279619111.unknown
_1278757997.unknown
_1278756989.unknown
_1278757697.unknown
_1234170316.unknown
_1140433019.unknown
_1170854613/��
_1170852086.unknown