Métodos numéricos/Equações não lineares

Introdução editar

Os métodos descritos neste capítulo permitem obter, por um processo iterativo, uma solução de uma equação $f(x)=0$ onde $f(x):\mathbb {R} \to \mathbb {R}$ fornecendo uma aproximação inicial $x_{0}$ . Obtém-se um sucessão de pontos $\{x_{n}\}_{n=0}^{+\infty }$ tal que $x_{n}\to p$ quando $n\to +\infty$ e $f(p)=0$ .

Definição: Diz-se que $p$ é uma raiz da equação $f(x)=0$ se $f(p)=0$ .

Iterações, ordem de convergência e constante assimptótica de erro editar

Definição: Seja $\{x_{n}\}_{n=0}^{+\infty }$ uma sucessão de pontos tal que $x_{n}\to p$ quando $n\to +\infty$ e $x_{n}\neq p$ e duas constantes $\lambda$ , $\alpha$ . Se o limite existe

$\lim _{n\to +\infty }{\frac {\vert x_{n+1}-p\vert }{\vert x_{n}-p\vert ^{\alpha }}}=\lambda$

Então diz-se que a sucessão de pontos dada converge para $p$ com ordem de convergência $\alpha$ e constante assimptótica de erro $\lambda$ .

Um método iterativo diz-se com convergência linear se $\alpha =1$ , com convergência supra linear se $\alpha >1$ e com convergência quadrática se $\alpha =2$ .

Exemplo: Considere-se as seguintes sucessões:

Este exemplo precisa de ser melhorado!

$x_{n}=1+{\frac {1}{n}}$ ,

$y_{n}=\left(1+{\frac {1}{n}}\right)^{n}$ ,

$z_{n}=4\sum _{k=1}^{+\infty }{\frac {(-1)^{k+1}}{2k-1}}$ , para as quais se tem

$x_{n}\to 1,n\to +\infty$ ,

$y_{n}\to e,n\to +\infty$ e

$z_{n}\to \pi ,n\to +\infty$ .

Pode então construir-se a seguinte tabela de valores para cada uma das sucessões:

$n$	$x_{n}$	$y_{n}$	$z_{n}$
$1$	$2$	$2$	$4$
$2$	$1.5$	$2.25$	$2.66...$
$3$	$1.33...$	$2.37...$	$3.46...$
$4$	$1.25$	$2.44...$	$2.89...$
$5$	$1.2$	$2.48...$	$2.97...$
$10$	$1.1$	$2.59...$	$3.04...$
$25$	$1.04$	$2.66...$	$3.18...$
$50$	$1.02$	$2.69...$	$3.12...$
$100$	$1.01$	$2.70...$	$3.13...$

E estimar quanto vale a constante assimptótica de erro $\lambda$ através da expressão

$\lambda _{n}={\frac {\vert x_{n+2}-x_{n+1}\vert }{\vert x_{n+1}-x_{n}\vert }}$ . Para $n=100$ obtém-se

$\lambda _{x_{100}}$	$\lambda _{y_{100}}$	$\lambda _{z_{100}}$
$0.9800392$	$0.9800567$	$0.990148$

A tabela anterior mostra que as sucessões têm uma convergência linear ( $\alpha =1$ ) com uma constante assimptótica de erro próxima de um, têm por isso uma convergência muito lenta.

Critérios de parada editar

Os métodos que serão expostos nas seções seguintes permitem obter uma sucessão de valores que aproximam sucessivamente o zero de uma função. De modo a definir um critério que permita aferir qual a exatidão da aproximação obtida é usual terminar o algoritmo que calcula cada aproximação através da verificação das seguintes condições, dado um $0<\epsilon <1$ :

i.: $\vert x_{n+1}-x_{n}\vert <\epsilon$
ii.: ${\frac {\vert x_{n+1}-x_{n}}{\vert x_{n}\vert }}\vert <\epsilon$ onde $x_{n}\neq 0$ ,
iii.: $\vert f(x_{n})\vert <\epsilon$ .

A estas condições é necessário adicionar ainda a condição $n\leq N$ onde $N$ é o número máximo de iterações.

Método da bissecção editar

Código em Octave editar

function bf=bissec(a,b,Niter,tol)

format short g;
disp("")
disp ("Resultado do metodo da bisseccao")
disp("")
disp ("           n           a           b           x         f(x)")  
fa=f(a);
for i=1:1:Niter
  fb=f(b);
  x=a+(b-a)/2;
  fx=f(x);

  disp ([i, a, b, x, fx]);
  if (fx==0 |(b-a)/2<tol)
    disp("")
    disp ("O metodo foi aplicado com sucesso!")
    disp("")
    return;
    else
      if (fa*fx>0)
      a=x;
      fa=fx;
    else
      b=x;
    endif
  endif
  
endfor
disp("")
disp ("O metodo falhou depois da iteracao (Niter)")
disp (Niter)
disp("")
endfunction

Com a função

function fv = f(x) 
x*ln(x) - 3.2;
endfunction

Para correr o programa fazer

Input

bissec(2,3)

e gera o

Output

Resultado do metodo da bisseccao

           n           a           b           x         f(x)
           1           0           3         1.5     -1.4293
           2           0         1.5        0.75   -0.018311
           3           0        0.75       0.375     0.55551
           4       0.375        0.75      0.5625     0.28342
           5      0.5625        0.75     0.65625     0.13604
           6     0.65625        0.75     0.70312      0.0597
           7     0.70312        0.75     0.72656      0.0209
           8     0.72656        0.75     0.73828   0.0013451
           9     0.73828        0.75     0.74414  -0.0084704

O metodo foi aplicado com sucesso!

No caso de o número de iterações não seja suficiente o resultado é este

Input

bissec(2,3)

Output

Resultado do metodo da bisseccao

           n           a           b           x         f(x)
           1           0           3         1.5     -1.4293
           2           0         1.5        0.75   -0.018311
           3           0        0.75       0.375     0.55551
           4       0.375        0.75      0.5625     0.28342
           5      0.5625        0.75     0.65625     0.13604

O metodo falhou depois da iteracao
         5

Método de Newton editar

Zeros simples editar

$x_{0}$

$x_{n}=x_{n-1}-{\frac {f(x_{n-1})}{f'(x_{n-1})}}$ , $n\geq 1$

Zeros múltiplos editar

$x_{0}$

$x_{n}=x_{n-1}-m{\frac {f'(x_{n-1})}{f(x_{n-1})}}$ , $n\geq 1$ onde $m=1,2,\ldots$ é a multiplicidade da raíz.

Método da secante editar

Implementação em Octave editar

Com a mesma f.m definida anteriormente.

function sf=secant(x,y,Niter,tol)

format short g;
disp("")
disp ("Resultado para o metodo da secante")
disp("")
disp ("           n          x         err        f(x)")  

for i=1:Niter
  if (f(x)==0 |abs(x-y)<tol)
    disp("")
    disp ("O metodo foi aplicado com sucesso!")
    disp("")
    return;
  else
    epsilon=abs(f(y)*(y-x)/(f(y)-f(x)));
    disp ([i, y, epsilon, f(y)]);
    oldx=y;
    y=y-f(y)*(y-x)/(f(y)-f(x));
    x=oldx;
  endif 
endfor

disp("")
disp ("O metodo falhou depois da iteracao (Niter)")
disp (Niter)
disp("")
endfunction

Input

secant(.2,.3,15,.01)

Output

Resultado para o metodo da secante

           n          x         err        f(x)
           1         0.3      0.5254     0.65534
           2      0.8254    0.096338    -0.14714
           3     0.72907   0.0098364    0.016732

O metodo foi aplicado com sucesso!

Método da falsa posição (Regula falsi) editar

Implementação em Octave editar

Com a mesma f.m definida anteriormente.

function rff=regulafalsi(x,y,Niter,tol)

format short g;
disp("")
disp ("Resultado para o metodo da falsa posicao")
disp("")
disp ("           n          x          y         err        f(x)")  


for i=1:Niter
  oldy=y;
  y=y-f(y)*(y-x)/(f(y)-f(x));
  if (f(y)==0 |abs(y-oldy)<tol)
    disp("")
    disp ("O metodo foi aplicado com sucesso!")
    disp("")
    return;
  else
    epsilon=abs(x-y);
    disp ([i,x, y, epsilon, f(y)]);
    if (f(oldy)*f(y)<0)
      x=oldy;
    else
    endif
  endif 
endfor

disp("")
disp ("O metodo falhou depois da iteracao (Niter)")
disp (Niter)
disp("")

endfunction

Input

regulafalsi(.2,1,100,.001)

Output

Resultado para o metodo da falsa posicao

           n          x          y         err        f(x)
           1         0.2     0.70336     0.50336    0.059306
           2           1     0.73726     0.26274   0.0030522
           3           1     0.73899     0.26101   0.0001531

O metodo foi aplicado com sucesso!

Método da falsa posição modificado editar

PASSO 1

Faça i = 1

PASSO 2

Enquanto i £ ITMAX, execute os passos 3 – 6

PASSO 3

Faça p = f( p) (calcular pi )

PASSO 4

Se 0 p - p < e então Saída ( p ) (procedimento efetuado com sucesso) FIM

PASSO 5

Faça i = i + 1

PASSO 6

Faça p0 = p (atualize p0 )

PASSO 7

Saída (solução não encontrada após ITMAX iterações)

FIM

Método do ponto fixo editar

i) f e f' são funções contínuas em I; ii) = f ( ) <1 Î k x x I max ' iii) x0 ÎI e xn+1 = f(xn )ÎI , para n = 0, 1, 2, ¼ Então a seqüência { } xn converge para o zero a .

Implementação em Octave editar

Com a função g.m definida por:

function gv = g(x)

  gv=cos(x);

endfunction

function sfp=fpoint(x,Niter,tol)

format short g;
disp("")
disp ("Resultado para o metodo do ponto fixo")
disp("")
disp ("           n          x          err        g(x)")  

for i=1:Niter
  oldx=x;
  x=g(x);
  
  if (g(x)==x |abs(x-oldx)<tol)
    disp("")
    disp ("O metodo foi aplicado com sucesso!")
    disp("")
    return;
  else
    epsilon=abs(x-oldx);
    disp ([i,x, epsilon, g(x)]);
  endif 

endfor

disp("")
disp ("O metodo falhou depois da iteracao (Niter)")
disp (Niter)
disp ("iterations")
disp("")

endfunction

Input

fpoint(.2,100,.01)

Output

Resultado para o metodo do ponto fixo

           n          x          err        g(x)
           1     0.98007     0.78007     0.55697
           2     0.55697      0.4231     0.84886
           3     0.84886     0.29189     0.66084
           4     0.66084     0.18802     0.78948
           5     0.78948     0.12864     0.70422
           6     0.70422    0.085263     0.76212
           7     0.76212    0.057904     0.72337
           8     0.72337    0.038745     0.74958
           9     0.74958    0.026202     0.73198
          10     0.73198    0.017599     0.74385
          11     0.74385    0.011877     0.73586

O metodo foi aplicado com sucesso!

Esta página é um esboço de matemática. Ampliando-a você ajudará a melhorar o Wikilivros.