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

Introdução

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

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

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

Código em Octave

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

Zeros simples

$x_{0}$

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

Zeros múltiplos

$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

Implementação em Octave

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)

Implementação em Octave

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

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

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

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.