cn2013_01_aula_03_Metodos_Iterativos

Prévia do material em texto

Computação	
  Numérica	
  
Fabíola	
  Guerra	
  Nakamura	
  
Métodos	
  Itera;vos	
  
•  Elabore	
  um	
  algoritmo	
  para	
  calcular	
  o	
  sen(x)	
  
sabendo	
  que	
  :	
  
Sistemas Lineares 
∑
∞
=
+
≤≤+−+−=
+
−=
0
75312
4
0...,
50401206)!12(
)1()(
n
n
n xxxxx
n
xxsen π
Métodos	
  Itera;vos	
  
•  Métodos	
  Itera;vos	
  
–  Partem	
  de	
  uma	
  solução	
  inicial	
  e	
  a	
  par;r	
  dela	
  geram	
  uma	
  
nova	
  solução.	
  O	
  processo	
  então	
  se	
  repete	
  gerando	
  um	
  
seqüência	
  de	
  soluções	
  que	
  deve	
  convergir	
  para	
  a	
  solução	
  
do	
  problema.	
  
	
  	
  
Sistemas Lineares 
f(x) 
| 
x0 
| 
x1 
... | 
x2 
| 
xk 
... 
método	
  itera;vos	
  
•  Métodos	
  Itera;vos	
  
–  Partem	
  de	
  uma	
  solução	
  inicial	
  e	
  a	
  par;r	
  dela	
  geram	
  uma	
  
nova	
  solução.	
  O	
  processo	
  então	
  se	
  repete	
  gerando	
  um	
  
seqüência	
  de	
  soluções	
  que	
  deve	
  convergir	
  para	
  a	
  solução	
  
do	
  problema.	
  
	
  	
  
Sistemas Lineares 
0	
  
1	
  
2	
  
3	
  
4	
  
5	
  
6	
  
0	
   1	
   2	
   3	
   4	
   5	
   6	
  
Equação	
  1	
  
Equação	
  2	
  
x0	
  
x1	
  
x2	
  
Series6	
  
Series7	
  
Métodos	
  Itera;vos	
  
•  Métodos	
  Itera;vos	
  
–  Partem	
  de	
  uma	
  solução	
  inicial	
  e	
  a	
  par;r	
  dela	
  geram	
  uma	
  
nova	
  solução.	
  O	
  processo	
  então	
  se	
  repete	
  gerando	
  um	
  
seqüência	
  de	
  soluções	
  que	
  deve	
  convergir	
  para	
  a	
  solução	
  
do	
  problema.	
  
	
  	
  
Sistemas Lineares 
f(x) 
| 
x0 
| 
x1 
... | 
x2 
| 
xk 
... 
O	
  que	
  significa	
  convergir	
  para	
  uma	
  
solução?	
  
método	
  itera;vos	
  
•  Métodos	
  Itera;vos	
  
•  Um	
  processo	
  itera;vo	
  repete	
  uma	
  mesma	
  série	
  de	
  operações	
  
várias	
  vezes.	
  
	
  	
  
Sistemas Lineares 
O	
  que	
  você	
  acha	
  que	
  deve	
  ser	
  considerado	
  
em	
  um	
  processo	
  itera;vo?	
  Quais	
  são	
  os	
  
elementos	
  que	
  compõem	
  um	
  processo	
  
itera;vo?	
  
método	
  itera;vos	
  
Elementos	
  de	
  
um	
  processo	
  
Itera;vo	
  
Fórmula	
  de	
  
iteração	
  
Condição	
  de	
  
Convergência	
  
Critério	
  de	
  
parada	
  
Solução	
  
inicial	
  	
  
Sistemas Lineares 
métodos	
  itera;vos	
  
Sistemas Lineares 
Ò  Fórmula de iteração.	
  
Ò  Corresponde	
  às	
  operações	
  matemá;cas	
  que	
  a	
  
solução	
  atual	
  sofre	
  para	
  gerar	
  uma	
  nova	
  solução.	
  
	
  
	
  	
   xk+1 = h(xk )
método	
  itera;vos	
  
Elementos	
  de	
  
um	
  processo	
  
Itera;vo	
  
Fórmula	
  de	
  
iteração	
  
Condição	
  de	
  
Convergência	
  
Critério	
  de	
  
parada	
  
Solução	
  
inicial	
  	
  
Sistemas Lineares 
métodos	
  itera;vos	
  
Sistemas Lineares 
Ò  Condição de Convergência.	
  
Ò  Todo	
  método	
  itera;vo	
  tem	
  associado	
  a	
  ele	
  uma	
  
condição	
  de	
  convergência	
  que	
  irá	
  garan;r	
  que	
  a	
  cada	
  
iteração	
  o	
  método	
  está	
  caminhando	
  em	
  direção	
  da	
  
solução	
  do	
  problema	
  
Ò  Uma	
  vez	
  garan;da	
  a	
  convergência,	
  os	
  métodos	
  
itera;vos	
  a	
  cada	
  passo	
  obtêm	
  soluções	
  com	
  exa;dão	
  
crescente.	
  Isso	
  significa	
  que	
  :	
  
	
  	
   lim
k→∞
xk = x; f (x) = 0
método	
  itera;vos	
  
Elementos	
  de	
  
um	
  processo	
  
Itera;vo	
  
Fórmula	
  de	
  
iteração	
  
Condição	
  de	
  
Convergência	
  
Critério	
  de	
  
parada	
  
Solução	
  
inicial	
  	
  
Sistemas Lineares 
métodos	
  itera;vos	
  
Sistemas Lineares 
Ò  Critério de Parada 
Ò  Os	
  métodos	
  itera;vos	
  não	
  podem	
  con;nuar	
  indefinidamente,	
  
ou	
  seja,	
  eles	
  devem	
  ser	
  interrompidos	
  em	
  algum	
  momento.	
  
Ò  Alguns	
  critérios	
  de	
  parada	
  para	
  esses	
  métodos	
  podem	
  ser	
  
	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  sendo	
  ε	
  um	
  parâmetro	
  de	
  entrada	
  do	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  
	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  algoritmo	
  
	
  	
  
ε≤− ),( 1kk xxg
métodos	
  itera;vos	
  
Sistemas Lineares 
Ò  Critério de Parada 
	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  onde	
  kmax	
  é	
  um	
  parâmetro	
  de	
  entrada	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  
	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  do	
  algoritmo	
  que	
  indica	
  o	
  número	
  máximo	
  
de	
  iterações	
  do	
  método.	
  
	
  
Os	
  dois	
  critérios	
  podem	
  ser	
  u;lizados	
  separadamente	
  
ou	
  em	
  conjunto.	
  Neste	
  úl;mo	
  caso	
  	
  evita-­‐se	
  que	
  o	
  
programa	
  entre	
  o	
  loop	
  por	
  não	
  conseguir	
  a;ngir	
  o	
  
valor	
  de	
  ε	
  	
  estabelecido.	
  
maxkk ≥
método	
  itera;vos	
  
Elementos	
  de	
  
um	
  processo	
  
Itera;vo	
  
Fórmula	
  de	
  
iteração	
  
Condição	
  de	
  
Convergência	
  
Critério	
  de	
  
parada	
  
Solução	
  
inicial	
  	
  
Sistemas Lineares 
métodos	
  itera;vos	
  
Sistemas Lineares 
Ò  Solução Inicial 
Ò  Como	
  o	
  método	
  parte	
  de	
  uma	
  solução	
  inicial	
  x0	
  deve-­‐se	
  
estabelecer	
  como	
  esse	
  x0	
  deve	
  ser	
  gerado.	
  
.