Base conceitual
Bisecção
O método da bisecção se aplica quando dada a função y = f(x), contínua em um intervalo [a, b] que contém uma, e só uma, raiz, ξ, da equação f(x) = 0. Este método consiste em dividir o intervalo [a, b], de forma iterativa, ao meio. Para verificar se a raiz está contida na primeira ou na segunda metade do intervalo inicial, é utilizado o teorema de Bolzano. Em seguida, o processo é repetido para aquela metade que contém a raiz de f(x) = 0, ou seja, aquela em que a função, y = f(x), tem valores numéricos com sinais opostos nos seus extremos, como ilustra a Figura 1.
Figura 1 - Método da bisecção.
Esse método pode ser considerado interativo, pois em cada iteração é atualizado o ponto “a” ou “b”, tem-se que a função de iteração desse método é dada por: xk = (a+b)/2, k = 1, 2, 3…
O critério de parada é dado por uma precisão, sendo que o processo iterativo é finalizado quando se obtém um intervalo cujo tamanho é menor ou igual a, então qualquer ponto nele contido pode ser tomado como uma estimativa para a raiz; ou quando for atingido um número máximo de iterações.
O critério de convergência ocorre quando y = f(x) for contínua em [a, b] e f(a).f(b) < 0, então o método da Bisseção gera uma seqüência que converge para uma raiz de f(x) = 0.
Falsa-posição
Esse método considera que para y = f(x), seja uma função contínua em um intervalo [a,b] que contém uma, e só uma, raiz da equação f(x) = 0. O Método da Falsa Posição consiste em dividir, de forma iterativa, o intervalo [a, b] no ponto em que a reta que passa por [a, f(a),] e [b, f(b)] intercepta o eixo das abscissas. A Figura 2 ilustra o processo.
O foco do Método da Falsa Posição é gerar, em cada iteração, uma aproximação para a raiz cuja imagem seja a menor possível, isto é, uma aproximação tal que |f(xk)| ε, sem se preocupar com a diminuição do tamanho do intervalo [a, b] que a contém. No caso do Método da Bisseção, em cada iteração é feita a média aritmética dos extremos a e b. Por outro lado, o Método da Falsa Posição parte do princípio de que a raiz deve estar mais próxima do ponto que apresenta o menor valor da função, sendo assim, ao invés de fazer a média aritmética entre a e b, faz a média aritmética ponderada entre ambos
Figura 2 - Método da falsa - posição.
A função de interação do método é dada por:
O critério de parada verifica - se para uma dada uma precisão, o processo iterativo é finalizado quando se obtém um ponto xk, k = 0, 1, 2, ...; tal que |f(xk)| ≤ e, então, ele é tomado como uma estimativa para uma raiz de f(x) = 0; ou quando for atingido um número máximo de iterações.
O critério de convergência ocorre se y = f(x) for contínua em [a, b] e f(a).f(b) < 0, então o método da Falsa Posição gera uma seqüência que converge para a raiz
Newton-Rapshon
Para esse método considera - se y = f(x) uma função contínua em um intervalo [a, b] que contém uma, e só uma, raiz da equação f(x) = 0 e no qual f '(x) e f ''(x) não se anulam e preservam o sinal. O Método de Newton-Raphson consiste em:
(a) atribuir uma estimativa inicial x0 ∈ [a, b] para uma raiz de f(x) = 0;
(b) gerar uma sequência de estimativas, {xk + 1}, k = 0, 1, 2, 3, ...; onde cada ponto é a interseção da reta tangente a y = f(x), em [xk, f(xk)], com o eixo das abscissas.
Figura 3 - Método de Newton-Raphson.
A função de interação é dada por:
Critério de parada se da para uma precisão, na qual o processo iterativo é finalizado quando é obtido um ponto xk + 1, k = 0, 1, 2, ...; tal que |xk + 1 – xk| ≤ ou |f(xk + 1)| ≤ , então ele é tomado como uma estimativa para a raiz; ou quando for atingido um número máximo de iterações.
Critério de convergência em que dada uma f '(x) e f ''(x) não se anulam e preservam o sinal em [a, b] e a estimativa inicial, x0, é tal que f(x0). f ''(x0) > 0; então o Método de Newton-Raphson gera uma sequência que converge para uma raiz de f(x) = 0. Em geral, afirma-se que o método gera uma série convergente desde que x0 seja escolhido “suficientemente próximo” da raiz.
Fonte: http://www.decom.ufop.br/bcc760/material_de_apoio/notas_de_aulas/notas_raizes.pdf
Lista 2A
Seja y = f(x) uma função contínua em um intervalo [a, b] que contém uma, e só uma, raiz, ξ, da equação f(x) = 0. Este método consiste em dividir o intervalo [a, b], de forma iterativa, ao meio. Para verificar se a raiz está contida na primeira ou na segunda metade do intervalo inicial, é utilizado o teorema de Bolzano. Em seguida, o processo é repetido para aquela metade que contém a raiz de f(x) = 0, ou seja, aquela em que a função, y = f(x), tem valores numéricos com sinais opostos nos seus extremos.
Método de bissecção
package javaapplication3;
public class JavaApplication3 {
/**
* @param args the command line arguments
*/
static double funcao(double x){
double y = ((3.5E7+0.401*Math.pow((1000/x),2))*(x-42.7E-3))-1.3806503E-23*3E5;
return(y);
}
public static void main(String[] args) {
// TODO code application logic here
double a, b, eps, x, R, M;
int k = 0;
a = 0.01;
b = 0.1;
eps = 1E-12;
if (b - a < eps){
R = a + (Math.random()*(b-a));
System.out.println("A raiz é:"+R);
}
else{
k = 1;
M = funcao(a);
while((b-a) >= eps){
x = (a + b)/2;
if((M*funcao(x)) > 0){
a = x;
}
else{
b = x;
}
k = k + 1;
}
R = a + (Math.random()*(b-a));
}
System.out.println("A raiz da função vale:"+R);
System.out.println("Foram utilizadas "+(k-1)+" iterações");
}
}
Resultado do programa no intervalo de [0,01;0,1]
Método de Newton - Raphson
package javaapplication5;
import java.util.Scanner;
public class JavaApplication5 {
/**
* @param args the command line arguments
*/
static double funcao(double x){
double y = ((3.5E7+0.401*Math.pow((1000/x),2))*(x-42.7E-3))-1.3806503E-23*3E5;
return(y);
}
static double derivada(double x){
double y = (-0.401*(1E6)/(Math.pow(x, 2)))+2*0.401*(1E9)*(42.7E-6)/(Math.pow(x,3));
return(y);
}
public static void main(String[] args) {
// TODO code application logic here
double a, b,eps, x1, x0, R;
int k = 0;
Scanner sc = new Scanner(System.in);
System.out.println("digite um valor entre 0,01 e 0,06 para a aproximação inicial.");
a = sc.nextDouble();
eps = 1E-12;
if(Math.abs(funcao(a)) < eps){
R = a;
}
else{
k = 1;
x1 = a - (funcao(a))/(derivada(a));
x0 = a;
while(Math.abs(funcao(x1)) >= eps || Math.abs(x1-x0) >= eps){
x1 = x0 - (funcao(x0))/(derivada(x0));
x0 = x1;
k = k + 1;
}
R = x1;
}
System.out.println("O valor da raiz é: "+R);
System.out.println("O número de iterações foi "+k);
}
}
Resultados obtidos através de diferentes valores iniciais.
1 - Método da Falsa Posição.
prompt = 'Coloque um valor de E negativo';
E = input(prompt);
b = 0.9;
a = 0.6;
contador=2;
N=60;
fa= -(1 /a^3)+(-1 /a^2)-E;
fb=-(1 /b^3)+(-1 /b^2)-E;
tic
for i= 1:N
x=b-(fb.*(b-a))./(fb-fa);
y=-(1 /x^3)+(-1 /x^2)-E;
fx=y;
if (abs(x-b))<eps*max(1,abs(x))
printf('Quantidade de interacoes = %f',contador)
disp(x);
break;
end
contador=contador+1;
j=fx;
if (j*fxb<0)
a=b;
fa=fb;
end
b=x;
fb=j;
end
toc
E = input(prompt);
b = 0.9;
a = 0.6;
contador=2;
N=60;
fa= -(1 /a^3)+(-1 /a^2)-E;
fb=-(1 /b^3)+(-1 /b^2)-E;
tic
for i= 1:N
x=b-(fb.*(b-a))./(fb-fa);
y=-(1 /x^3)+(-1 /x^2)-E;
fx=y;
if (abs(x-b))<eps*max(1,abs(x))
printf('Quantidade de interacoes = %f',contador)
disp(x);
break;
end
contador=contador+1;
j=fx;
if (j*fxb<0)
a=b;
fa=fb;
end
b=x;
fb=j;
end
toc
2 - Método de Bissecção
a0 = 0.5;
b0 = 0.9;
prompt = 'Coloque um valor para E negativo ';
E = input(prompt);
tic
for contador = 1:100
x=(a0+b0)/2;
y= -(1 /x^3)+(-1/x^2)-E;
if (y==0||abs(b0-a0)/2< eps*max(1,abs(x)))
printf('Numero de iteracoes = %f',contador)
disp(x)
break
end
if (-(1 /x^3)+(-1 /x^2)-E)*(-(1 /a0^3)+(-1 /a0^2)-E) > 0
a0=x;
else
b0=x;
end
end
toc
b0 = 0.9;
prompt = 'Coloque um valor para E negativo ';
E = input(prompt);
tic
for contador = 1:100
x=(a0+b0)/2;
y= -(1 /x^3)+(-1/x^2)-E;
if (y==0||abs(b0-a0)/2< eps*max(1,abs(x)))
printf('Numero de iteracoes = %f',contador)
disp(x)
break
end
if (-(1 /x^3)+(-1 /x^2)-E)*(-(1 /a0^3)+(-1 /a0^2)-E) > 0
a0=x;
else
b0=x;
end
end
toc
Discussão geral das questões 1 e 2:
Nos exercícios 1 e 2 tivemos que trabalhar com diferentes métodos (bissecção, falsa posição e Newton-Raphson) de resolução e obtivemos, para cada um dos exercícios, os mesmos resultados em ambos os métodos utilizados, porém observamos que houveram variações significativas no número de iterações necessárias para a resolução em cada um deles.
O esforço computacional é medido através do número de operações efetuadas a cada iteração e suas complexidades, bem como através dos números de decisões logicas, avaliações de função a cada interação e total de iterações.
Em uma análise geral dos dois exercícios observamos que o método da bissecção é o que efetua os cálculos mais simples por iteração, no entanto o número de iterações efetuadas pode ser mais elevado que o de Newton, que pode possuir menor número de iterações, mas requer o cálculo da função e de sua derivada a cada iteração. Dessa forma torna-se difícil escolher um método ideal com base apenas em sua eficiência computacional.
Lista 2B
Cálculo da derivada no Wolfram Alpha: α=x
Software: Excel - Método de Newton Raphson
Comandos:
Por fins didáticos, considerou-se α=x
Figura 4 - Cálculo de Xn+1.
Figura 5 - Cálculo da função f(Xn).
Figura 6 - Cálculo da primeira derivada f `(Xn).
Figura 7 - Razão f(Xn) / f ´(Xn).
Figura 8 - Intervalo |Xn+1 - Xn|.
Figura 9 - Ponto de parada do cálculo com épsilon de 0,000000001.
Figura 10 - Conversão de radianos para graus.
Figura 11 - Tabela com método de Newton Rapshon no Excel.
Discussão:
A estimativa do zero da função Y=f(X) é feita a partir da reta tangente à função em um ponto de partida. O ponto em que essa reta tangente intercepta o eixo das abscissas corresponde à estimativa do zero da função. Se o valor estimado não atender à tolerância estabelecida para o problema, |f(ze)| > tol. , repete - se os procedimentos até que está seja atendida, como representa o esquema da Figura 12.
Figura 12- Representação esquemática do método de Newton Rapshon.
O outro método que poderia ser utilizado para o cálculo do valor de L através do valor de α é o Método das Secantes:
Esse método fundamenta-se no fato de que, geralmente, o zero da função vai estar localizado o mais próximo do extremo do intervalo onde a função apresenta o menor valor em módulo. A estimativa do zero da função Y=f(X) é feita a partir da reta secante que une os pares extremos (a,f(a)) e (b,f(b)) do intervalo analisado. O ponto em que essa reta secante intercepta o eixo das abscissas corresponde à estimativa do zero da função. Se o valor estimado não atender à tolerância estabelecida para o problema, ou seja, |f(ze)|>tol, redefine-se o intervalo de estudo, repetindo-se a estratégia até que a tolerância seja verificada.
Figura 13 - Representação esquemática do Método das Secantes.
Fonte: http://www1.univap.br/spilling/CN/apostila1.pdf
Considerando que o método de ideal seria aquele em que a convergência estivesse assegurada, a ordem de convergência fosse alta e os cálculos por interação fossem simples, o método Newton é o mais indicado sempre que for fácil verificar as condições de convergência e que o cálculo de f´(x) não seja muito elaborado. Nos casos em que é trabalhoso obter e/ou avaliar f´(x), é aconselhável usar o método da secante, uma vez que é o método que converge mais rapidamente entre as outras opções.
Fonte: RUGGIERO, M. A. G. e LOPES, V. L. .R. CÁLCULO NUMÉRICO: Aspectos teóricos e computacionais; 2ª edição. Cap. 2, p. 78.
O método das secantes é um algoritmo de busca de raízes que usa uma sequência de raízes de linhas secantes para aproximar cada vez melhor a raiz de uma função f e, pode ser pensado como uma aproximação por diferenças finitas do método de Newton.O método das secantes é definido pela relação de recorrência (é uma técnica matemática que permite definir sequências, conjuntos, operações ou até mesmo algoritmos partindo de problemas particulares para problemas genéricos. Ou seja, por intermédio de uma regra pode-se calcular qualquer termo em função do(s) antecessor(es) imediato(s)).
ou
Como pode ser visto da relação de recorrência, o método das secantes requer dois valores iniciais, x0 e x1, que devem ser preferencialmente escolhidos próximos da raiz.
As relações de recorrência são compostas por duas partes importantes: a(s) condição(ões) inicial(is) — que deve(m) ser conhecida(s) —, e a “equação de recorrência” — que é a regra que permitirá calcular os próximos termos em função dos antecessores.
Fonte: Press, William H.; Teukolsky, Saul A.; Vetterling, William T.; Flannery, Brian P. (2002). Numerical Recipes in C: The Art of Scientific Computing (New York: Press Syndicate of the University of Cambridge). pp. 354–357. ISBN 0-521-43108-5.
No desenvolvimento do algorítimo no Excel, buscou-se seguir a regra todas essas etapas, contudo percebe-se que o valor de L obtido de 21,50139838 está distante do esperado de 30.84, isso pode ter ocorrido devido a conversão de radianos para graus, feito no processo de cálculo, propagando sucessivos erros e aumentando a quantidade de interações necessárias para chegar a uma raiz menor que o ponto de parada épsilon de 0,000000001, cuja escolha deveu-se ao fato de ser o menor número que o programa computa sem fazer uso de notação científica.
JAVA:
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int b,i;
double a,x=1,c,ant;
System.out.println("Digite um número positivo para calcular a raiz ");
a=sc.nextDouble();
while(a<0){
System.out.println("ERRO!!");
System.out.println("Digite numero positivo, maior que zero!!");
a=sc.nextInt();
}
System.out.println("Quantas interaçoes terá sobre a função?");
System.out.println("Digite um numero inteiro ");
b=sc.nextInt();
while(b<0){
System.out.println("ERRO!!");
System.out.println("Digite numero positivo, maior que zero!!");
b=sc.nextInt();
}
for(i=1;i<(1+b);i++){
c=(x*(Math.pow(x,2)+3*a))/(3*Math.pow(x,2)+a);
x=c;
System.out.println("Interações Raiz");
System.out.print(""+i);
System.out.println(" "+x);
}
}
Explicando como funciona o algoritmo: o usuário digita um número, no qual deseja calcular a sua raiz e outro número para definir quantidade de interações. Caso for introduzido um numero negativo aparecerá um aviso de “ERRO” e a maquina irá pedir para que digite somente o numero positivo. Após a entrada de dados, o algoritmo calcula o valor de “c” para cada interação.
Exemplo 01: a=15 (calculo do raiz) , b=10 (número de interações)
Exemplo 02 : a=500000000, b=20
Discussão:
Ponto fixo é aquele que quando utilizado em uma função, retorna a si mesmo, ou seja,
φ(x) = x
Para se chegar a esse valor, é utilizado o algoritmo de nome iterações de ponto fixo, ou método de ponto fixo, definido como:
x^(k+1) = φ(x^(k));
com k sendo o número de iterações. A cada iteração, o valor obtido se torna mais próximo do ponto fixo.
No algoritmo montando em JAVA acima, é utilizada a função de recursividade para se chegar ao valor mais próximo do ponto fixo, através da repetição do cálculo da função. Quando é determinado um valor inicial, o número positivo ‘a’ da equações problema, o algoritmo inicia o seu cálculo e o perpetua até que o número de iterações suficientes, determinado pelo usuário, seja atingido, sendo esse o valor ‘k’.
