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

Origem: Wikilivros, livros abertos por um mundo aberto.

Índice

1 Introdução
- 1.1 Iterações, ordem de convergência e constante assimptótica de erro
- 1.2 Critérios de parada
2 Método da bissecção
- 2.1 Código em Octave
3 Método de Newton
- 3.1 Zeros simples
  - 3.1.1 Implementação em Octave
- 3.2 Zeros múltiplos
4 Método da secante
- 4.1 Implementação em Octave
5 Método da falsa posição (Regula falsi)
- 5.1 Implementação em Octave
6 Método da falsa posição modificado
7 Método do ponto fixo
- 7.1 Implementação em Octave

[editar] 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):\R\to\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$ .

[editar] 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 $λ$ , $α$ . 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 $α$ e constante assimptótica de erro $λ$ .

Um método iterativo diz-se com convergência linear se $α = 1$ , com convergência supra linear se $α > 1$ e com convergência quadrática se $α = 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 $λ$ 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 ( $α = 1$ ) com uma constante assimptótica de erro próxima de um, têm por isso uma convergência muito lenta.

[editar] Critérios de parada

Os métodos que serão expostos nas secçõ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 exactidã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 < ε < 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\ne 0$ ,
iii.: $\vert f(x_n) \vert< \epsilon$ .

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

[editar] Método da bissecção

[editar] Código em Octave

function bf=bissec(a,b,Niter,tol)
 
format short g;
disp("")
disp ("Output for the Bisection method")
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 ("The method completed successfully!")
    disp("")
    return;
    else
      if (fa*fx>0)
      a=x;
      fa=fx;
    else
      b=x;
    endif
  endif
 
endfor
disp("")
disp ("The method failed after (Niter)")
disp (Niter)
disp ("iterations")
disp("")
endfunction

Com a função

function fv = f (x)
  fv=cos(x)-x;
endfunction

Para correr o programa fazer

Input

bissec(0,3,100,.01)

e gera o

Output

Output for the Bisection method

           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

The method completed successfully!

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

Input

bissec(0,3,5,.01)

Output

Output for the Bisection method

           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

The method failed after (Niter)
         5
iterations

[editar] Método de Newton

[editar] Zeros simples

$x 0$

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

[editar] Implementação em Octave

São necessárias as funções:

function fv = f (x)
 
  fv=cos(x)-x;
 
endfunction

function dfv = df (x)
 
  dfv=-sin(x)-1;
 
endfunction

function nf=newton(xo,Niter,tol)
 
format short g;
disp("")
disp ("Output for the Newton method")
disp("")
disp ("           n          x          err        f(x)")  
 
for i=1:Niter
  x=xo-f(xo)/df(xo);
  if (f(xo)==0 |abs(x-xo)<tol)
    disp("")
    disp ("The method completed successfully!")
    disp("")
    return;
  else 
    epsilon=abs(x-xo);
    xo=x;
    disp ([i, xo, epsilon, f(xo)]);
  endif
endfor
disp("")
disp ("The method failed after (Niter)")
disp (Niter)
disp ("iterations")
disp("")
endfunction

Input

newton(.5,100,.001)

Output

Output for the Newton method

           n          xo         err        f(x)
           1         0.5     0.25522     0.37758
           2     0.75522    0.016081   -0.027103

The method completed successfully!

[editar] Zeros múltiplos

$x 0$

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

[editar] Método da secante

[editar] Implementação em Octave

Com a mesma f.m definida anteriormente.

function sf=secant(x,y,Niter,tol)
 
format short g;
disp("")
disp ("Output for the Secant method")
disp("")
disp ("           n          x         err        f(x)")  
 
for i=1:Niter
  if (f(x)==0 |abs(x-y)<tol)
    disp("")
    disp ("The method completed successfully!")
    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 ("The method failed after (Niter)")
disp (Niter)
disp ("iterations")
disp("")
endfunction

Input

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

Output

Output for the Secant method

           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

The method completed successfully!

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

[editar] Implementação em Octave

Com a mesma f.m definida anteriormente.

function rff=regulafalsi(x,y,Niter,tol)
 
format short g;
disp("")
disp ("Output for the Regula Falsi method")
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 ("The method completed successfully!")
    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 ("The method failed after (Niter)")
disp (Niter)
disp ("iterations")
disp("")
 
endfunction

Input

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

Output

Output for the Regula Falsi method

           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

The method completed successfully!

[editar] 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

[editar] 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 .

[editar] 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 ("Output for the Fixed Point method")
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 ("The method completed successfully!")
    disp("")
    return;
  else
    epsilon=abs(x-oldx);
    disp ([i,x, epsilon, g(x)]);
  endif 
 
endfor
 
disp("")
disp ("The method failed after (Niter)")
disp (Niter)
disp ("iterations")
disp("")
 
endfunction

Input

fpoint(.2,100,.01)

Output

Output for the Fixed Point method

           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

The method completed successfully!

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

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

Origem: Wikilivros, livros abertos por um mundo aberto.

Índice

[editar] Introdução

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

[editar] Critérios de parada

[editar] Método da bissecção

[editar] Código em Octave

[editar] Método de Newton

[editar] Zeros simples

[editar] Implementação em Octave

[editar] Zeros múltiplos

[editar] Método da secante

[editar] Implementação em Octave

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

[editar] Implementação em Octave

[editar] Método da falsa posição modificado

[editar] Método do ponto fixo

[editar] Implementação em Octave

Acessos

Ferramentas pessoais

Pesquisa

Navegação

Projecto

Imprimir/exportar

Ferramentas