O Calculo Númerico

[pic 1]

Projeto 1 da disciplina de Cálculo Numérico

Professor: Rafael Galvão

Grupo: Ana Cecília Cavalcanti

        Dayvson Rafael da Silva Macena

        Lucas Oliveira Braga Silva        

        Matheus Henrique Ventura Ferreira

        Ramires Nogueira da Silva

2 de maio de 2015

Introdução ao problema

Para determinadas funções do tipo:

 [pic 2]

Foi pedido que se fizesse um programa computacional e linguagem C, que contivesse os algoritmos dos métodos numéricos de Halley, Newton-Raphson e Bisseção, com isso o programa deveria informar uma raiz da função.

Foram informados alguns itens que serviriam de entrada para o programa, entre eles estão os coeficientes, identificados acima como   a , o intervalo de separação, ou seja, que contenha apenas uma raiz (condição fundamental para o método da bisseção funcionar, caso que será explicado na conclusão), os erros máximos permitidos:  e , além do número máximo de iterações que o algoritmo deve calcular (para não gerar um laço infinito).[pic 3][pic 4][pic 5][pic 6]

O funcionamento deverá ser de forma que digitada uma entrada, o programa seja executado e devolva uma saída com os seguintes resultados: se a convergência foi alcançada, a raiz obtida, número de iterações e os erros e .[pic 7][pic 8]

Descrição dos métodos utilizados

1.Método da bisseção

O método da bisseção não possui uma fórmula ou expressão geradora, como muitos métodos, e sim um algoritmo. Segue abaixo sua explicação e sua interpretação geométrica:

[pic 9]

- Dado o intervalo (a,b), cujo ponto médio é c (  ),se calcula f(c), f(a), se compara da seguinte forma: f(c).f(a)<0 ? Se sim, houve mudança de sinal da função naquele ponto, logo, haverá pelo menos um zero nesse intervalo (teorema de Bolzano), faz-se a mesma coisa com o outro intervalo. A partir disso, se utiliza o novo intervalo como prioritário e processa da mesma forma até se aproximar satisfatoriamente da raiz.[pic 10]

Precisa-se também garantir que a raiz é única em cada intervalo para isso é necessário que f´ (x) não troque de sinal em [a, b], ou seja, f ‘ (x) > 0 sempre em [a, b] ou f  ́(x)<0 sempre em [a, b].

2. Método de Halley

O algoritmo de Halley surgiu a partir do método de Newton, ele é considerado o método de Newton de ordem superior, ou ordem cúbica.

Pode ser explicado a partir da série de Taylor:

[pic 11]

Reduzindo a expressão acima, chegamos a:

[pic 12]

3. Método de Newton-Raphson

Interpretação geométrica e algoritmo do método de Newton-Raphson

[pic 13][pic 14]

Para utilizar o método é preciso escolher um ponto que você acredita ser próximo à raiz, depois se calcula a equação da reta tangente através da imagem desse ponto na curva e encontra-se o ponto de encontro dessa reta com o eixo das abcissas, repetindo todo esse processo, o método se torna iterativo. A “maquina geradora” do método está demonstrada na equação abaixo, é preciso que a derivada no ponto não seja zero, e que a função seja diferenciável.

[pic 15][pic 16]

 Além disso, a convergência dependerá do valor da derivada de f na região em torno da raiz e do comportamento da função nessa região. Quanto mais próxima de uma reta a função se comportar no entorno da raiz, mais rápida será a convergência, pois a reta tangente irá ser uma ótima aproximação da função naquela região.[pic 17]

Exemplos:

Exemplo 1.   [pic 18]

[pic 19]

O intervalo de entrada do programa foi (3.0, 4.0)

O tempo de cálculo é diferente para cada método, isso está relacionado ao número de operações algébricas que cada método faz e o número de iterações que o algoritmo precisou calcular antes de convergir.

Método	Iterações	Tempo médio	Raiz
Bisseção	19	47 µseg	3.141592979431152
Halley	3	7 µseg	3.141592653589793
Newton	3	3 µseg	3.141592653589793

Para cada iteração que o algoritmo faz, o erro absoluto vai diminuindo, é possível observar que os métodos de Halley e Newton convergem para o resultando precisando de uma quantidade muito menor de iterações. Pode-se observar nas figuras abaixo, em que as abcissas representam o número da iteração e a ordenada o erro relacionado.

 [pic 20][pic 21]

Algoritmo de Newton-Raphson                                Algoritmo de Halley

[pic 22]

Algoritmo da Bisseção

Exemplo 2.          [pic 23]

[pic 24]

O intervalo que se encontra a raiz é (0,1)

Pode-se montar também uma tabela para relacionara velocidade de cálculo dos métodos:

Método	Iterações	Tempo médio	Raiz
Bisseção	20	51 µseg	0.497200489044189
Halley	2	8 µseg	0.497200366107629
Newton	2	3 µseg	0.497200366107651

Gráfico de erros relacionados ao número da iteração para cada método:

[pic 25][pic 26]

Método de newton                                  Método de Halley