Projeto Numerico Relatorio - Zeros de Funcoes

Prévia do material em texto

UNIVERSIDADE FEDERAL DE PERNAMBUCO
 CENTRO DE CIÊNCIAS EXATAS E DA NATUREZA
PROJETO DE CÁLCULO NUMÉRICO
ZEROS DE FUNÇÕES
Professor: Pedro Machado Manhaes de Castro
Turma: T1 Curso: Engenharia Mecânica
Grupo: X
Introdução
	Nas mais diversas áreas da ciência ocorrem, frequentemente, situações envolvendo a resolução de uma equação do tipo f(x) = 0. Os valores de x que tornam essa equação verdadeira são chamados de raízes da função (zeros da função), e podem ser valores reais ou complexos. 
	Sabemos que, para algumas equações, como, por exemplo, as equações polinomiais de segundo grau, existem fórmulas explícitas que nos dão as raízes em função dos coeficientes. Para polinômios de graus mais altos, entretanto, não há resolução trivial e é quase impossível se achar as raízes exatamente.
	O objetivo deste projeto é, portanto, conseguir encontrar raízes de polinômios de grau N (N= 1, 2, 3, 4...) através de métodos numéricos. A ideia central dos métodos numéricos é partir de uma aproximação inicial para a raiz e em seguida refinar essa aproximação através de um método iterativo. Os métodos numéricos usados para resolver equações podem ser divididos em dois grupos: métodos de confinamento e métodos abertos.
CONFINAMENTO: identifica-se um intervalo que contém a solução. Por definição, os pontos finais do intervalo são os limites superior e inferior da solução. Então, usando um esquema numérico, o tamanho do intervalo é reduzido sucessivamente até que a distância entre os pontos finais seja menor que a precisão desejada para a solução.
ABERTO: assume-se uma estimativa inicial para a solução. O valor dessa tentativa inicial para a solução deve ser próximo à solução real. Então, usando um esquema numérico, valores melhores (mais precisos) são calculados para a solução.
Métodos de confinamento sempre convergem para uma solução. Métodos abertos são usualmente mais eficientes, mas às vezes podem não levar à solução. Estamos interessados em apenas três métodos numéricos: método de Newton, da falsa-posição e bissecção. Newton é um método aberto e os outros dois são métodos de confinamento.
 Explanação Teórica
	Começaremos explicando como encontrar uma aproximação para a raiz e como garantir que o intervalo contenha apenas uma raiz, sendo assim um intervalo de separação. Para isso iremos precisar conhecer o Teorema de Bolzano e nos utilizar de um conceito de Cálculo Diferencial, a derivada.
TEOREMA DE BOLZANO
Esse teorema afirma que:
Seja f(x) uma função contínua num intervalo [a,b]. Se f(a).f(b)<0, então existe pelo menos um ponto x em [a,b] que é zero da função f(x).
	Graficamente, podemos ter uma ideia mais clara do que o teorema afirma. Observe o gráfico da função f(x) = x2 + 16x +1:
	Considere a função dentro do intervalo [-20, -10]. Veja que o f(-10) é negativo, enquanto que o f(-20) é positivo. Se fizermos o produto f(-20).f(-10), vamos obter um número com sinal negativo. Portanto, [-20,-10] é um intervalo de separação que contém pelo menos uma raiz de f(x). No caso dessa função, fica evidente o fato de que há apenas uma raiz no intervalo escolhido. Mas no caso de funções que admitam um grande número de raízes, como garantir que há apenas uma no intervalo escolhido?
DERIVADA
	Do Cálculo Diferencial, sabemos que a derivada [f ‘(x)] define os intervalos de crescimento e decrescimento da função. Intuitivamente e nos valendo do exemplo anterior para ilustrar, vemos que num intervalo de separação a função ou apenas cresce ou apenas decresce. Assim, concluímos que, para garantir a existência de apenas uma raiz dentro do intervalo, a derivada não pode mudar de sinal dentro desse intervalo. A derivada deverá ser ou sempre positiva ou sempre negativa. Isso garantirá a caracterização do intervalo escolhido como intervalo de separação.
	Agora que já estamos munidos do intervalo contendo a raiz, vamos nos concentrar em como diminuir a amplitude desse intervalo até conseguir uma boa aproximação para o zero da função.
MÉTODO DA BISSECÇÃO
Na figura acima, vemos a ilustração gráfica da aplicação do método da bissecção. Ele começa com a determinação dos pontos a e b que definem um intervalo onde existe uma solução. Tal intervalo é encontrado ou com o traçado de um gráfico de f(x) e a identificação de um cruzamento por zero, ou com o exame da função buscando uma mudança de sinal. O ponto central do intervalo, XNS, é então tomado como sendo a primeira estimativa da solução numérica. A solução exata está contida ou na seção entre a e XNS ou na seção entre os pontos XNS e b. Se a solução numérica não for suficientemente precisa, define-se um novo intervalo que contenha a solução exata, e seu ponto central é escolhido como a nova (segunda) estimativa da solução numérica. O processo continua até que a solução numérica seja suficientemente precisa de acordo com o critério selecionado.
MÉTODO DA FALSA-POSIÇÃO
	
Também conhecido como método das cordas, esse método é extremamente similar ao da bissecção, sendo também um método de confinamento. A solução tem início com a obtenção de um intervalo [a1, b1] que confine a solução. Os valores da função nos pontos finais são f(a1) e f(b1).Os pontos finais são então conectados por uma linha reta, e a primeira estimativa da solução numérica, XNS1, é o ponto onde a linha reta cruza o eixo x. Isso contrasta com o método da bisseção, onde o ponto central do intervalo foi escolhido como solução. Para a segunda iteração, define-se um novo intervalo [a2, b2]. Esse novo intervalo corresponde à subseção do primeiro intervalo que contém a solução. Ele é [a1, XNS1] (a1 atribuído a a2 e XNS1 a b2) ou [XNS1, b1] (XNS1 atribuído a a2 e b1 a b2). Os pontos finais do segundo intervalo são em seguida conectados por uma linha reta, e o ponto onde essa nova reta cruza o eixo x se torna a segunda solução estimada, XNS2. Para a terceira iteração, um novo subintervalo [a3, b3] é selecionado, e as iterações continuam da mesma forma até que a solução numérica seja considerada suficientemente precisa. Para um dado intervalo [a, b], a equação da linha reta que conecta os pontos (b, f(b)) e (a, f(a)) é dada por: 
 
MÉTODO NEWTON-RAPHSON
	O método de Newton, também conhecido como método das tangentes, parte de uma aproximação inicial X1 e, através da fórmula a seguir, tenta chegar o mais próximo possível do zero da função.
	Considere uma função f(x) contida num intervalo de separação [a,b]. Escolhemos um número X1 contido nesse intervalo (nesse projeto, especificamente, X1 = (a+b)/2) e aplicamos a equação acima com X1 = Xn. Repetimos o processo com Xn+1 até que se atinja a precisão desejada de aproximação da raiz. 
	Graficamente, a ideia é traçar a tangente no ponto [x1, f(x1)] e ver onde essa tangente intercepta o eixo x. Chamamos esse ponto de X2 e traçamos uma nova tangente em [x2, f(x2)]. Repetimos o processo para cada novo x encontrado e assim nos aproximaremos cada vez mais da raiz.
Metodologia
	O programa consiste numa função main (principal), responsável por abrir um arquivo texto padronizado que contém o grau de cada polinômio seguido de seus coeficientes em ordem crescente de grau dos expoentes. Ao ler a primeira informação do arquivo (o grau do polinômio), é possível pré-estabelecer o espaço a ser alocado na memória para comportar os coeficientes que posteriormente serão usados na função resolver_pol(bis, newt ou falscord) que irá retornar o número de raízes e as raízes do polinômio que serão armazenadas em três novos arquivos, cada um contendo as raízes obtidas por cada um dos métodos.
A função resolver_pol (trataremos genericamente, já que as descrições são análogas para os três métodos) é a função de maior importância para o código. Esta função associa todas as outras funções e é onde está presente a recursão. Inicialmente a funçãorecebe os parâmetros fundamentais do polinômio e caso o polinômio seja de grau 1, sua raiz é calculada de forma trivial. Caso não seja de grau 1, a função derivada é chamada e seu retorno, um ponteiro apontando para o vetor de coeficientes da derivada, é usado novamente na função resolver_pol. Isto deve se repetir até que a derivada atinja grau 1 e sua raiz seja calculada de forma trivial, como no primeiro caso. Esta solução é, então, utilizada na função gerar intervalo.
A função gerar intervalo recebe como argumento o numero de raízes e as raízes da derivada, retornando o ponteiro de um vetor que contém os extremos -10 e 10 e as raízes da derivada em ordem crescente compreendidas nesse intervalo. Cada par de números consecutivos do vetor define um intervalo que será posteriormente submetido ao teste de Bolzano (na função bolzano) para determinar os intervalos que contém raiz.
A função bolzano recebe dois números reais (que delimitam um intervalo no domínio da função entre -10 e 10) e um vetor com os coeficientes de um polinômio. A função realiza o teste do teorema para verificar se existe alguma raiz da função neste intervalo. Caso seja comprovado que há uma raiz, estes mesmos parâmetros são enviados para as três funções responsáveis por aplicar os métodos iterativos solicitados nesse projeto (bissecção, newton e falsas cordas). 
Uma vez encontradas as raízes, é criado um vetor para armazena-las e esse mesmo vetor é retornado para a função resolver_pol. Estas raízes serão utilizadas para delimitar os intervalos onde se encontram as raízes do polinômio de grau N+1, e isso deve se repetir até que o polinômio de grau N seja o polinômio cujas raízes foram solicitadas. Daí, o número de raízes e as raízes serão retornados para a função main. 
Exemplos
Exemplo 1
Gráfico de f(x) = 2x3-4x2-3x+2
 	Cálculo das raízes pelo método da Bissecção:
	Iteração (i)
	X(i)
	Erro(i)
	(i)
	X(i)
	(i)
	X(i)
	Erro(i)
	1
	5,819246
	3,373153
	1
	-2,728869
	1
	0,180754
	0,273374
	4
	2,161086
	0,285007
	4
	-0,608122
	4
	0,484449
	0,030321
	8
	2,455045
	0,008925
	8
	-0,892151
	8
	0,457876
	0,003748
	16
	2,445987
	0,000106
	16
	-0,900213
	16
	0,454124
	0,000004
	32
	2,446093
	0
	32
	-0,900221
	28
	0,454128
	0
O polinômio possui três raízes reais e todas as três foram encontradas através do método da Bissecção. Cada raiz precisou em média de 30 iterações para ser encontrada.
Cálculo das raízes pelo método de Newton:
	Iteração (i)
	X(i)
	Erro (i)
	(i)
	X(i)
	Erro(i)
	(i)
	X(i)
	Erro (i)
	0
	5,819246
	3,373153
	0
	-2,728869
	1,828648
	0
	0,180754
	0,273374
	1
	4,236139
	1,790046
	1
	-3,318132
	2,417911
	1
	0,457516
	0,003388
	2
	3,243574
	0,797481
	2
	-2,144639
	1,244418
	2
	0,454130
	0,000002
	3
	2,709023
	0,26293
	3
	-1,433511
	0,53329
	3
	0,454128
	0
	4
	2,487972
	0,041879
	4
	-1,057948
	0,157727
	
	
	
	5
	2,447429
	0,001336
	5
	-0,920713
	0,020492
	
	
	
	6
	2,446094
	0,000001
	6
	-0,900642
	0,000421
	
	
	
	7
	2,446093
	0
	7
	-0,900221
	0
	
	
	
	
	
	
	8
	-0,900221
	0
	
	
	
	Pelo método de Newton, precisamos em média de 5 iterações para convergir para a raiz. Nesse caso, o método de Newton mostrou-se bastante eficiente. 
Cálculo das raízes pelo método da Falsa Posição:
	Iteração (i)
	X(i)
	Erro(i)
	(i)
	X(i)
	(i)
	X(i)
	Erro(i)
	1
	1,664244
	0,781849
	1
	-0,315327
	1
	0,352941
	0,101187
	30
	2,239245
	0,207848
	30
	-0,585753
	2
	0,479611
	0,025483
	100
	2,443731
	0,002362
	100
	-0,864231
	4
	0,454124
	0,000004
	150
	2,446007
	0,000086
	150
	-0,893926
	5
	0,454128
	0
	300
	2,446093
	0
	300
	-0,900190
	6
	0,454128
	0
	361
	2,446093
	0
	654
	-0,900221
	
	
	
	Pelo método das Falsas Cordas, precisamos de um número muito elevado de iterações para alcançar a raiz. 
Exemplo 2
Gráfico de f(x)=X2-11x+30
 
Cálculo das raízes pelo método da Bissecção:
	Iteração (i)
	X(i)
	Erro(i)
	(i)
	X(i)
	Erro(i)
	1
	-2,25
	7,25
	1
	7,85
	1,85
	2
	1,625
	3,375
	2
	6,625
	0,625
	3
	3,5625
	1,4375
	3
	6,0625
	0,0625
	5
	5,015625
	0,015625
	5
	5,921875
	0,078125
	14
	5,000015
	0,000015
	12
	5,998779
	0,001221
	30
	5
	0
	27
	6
	0
	
	
	
	
	
	
Cálculo das raízes pelo método de Newton:
	Iteração (i)
	X(i)
	Erro (i)
	(i)
	X(i)
	Erro (i)
	0
	-2,25
	7,25
	0
	7,85
	1,85
	1
	1,608871
	3,391129
	1
	6,680556
	0,680556
	2
	3,522311
	1,477689
	2
	6,196160
	0,196160
	3
	4,447950
	0,55205
	3
	6,027636
	0,027636
	4
	4,855160
	0,14484
	4
	6,000724
	0,000724
	5
	4,983733
	0,016267
	5
	6,000001
	0,000001
	6
	4,999744
	0,000256
	6
	6
	0
	7
	5
	0
	
	
	
	8
	5
	0
	
	
	
Cálculo das raízes pelo método das Falsas Cordas:
	Iteração (i)
	X(i)
	Erro(i)
	 (i)
	X(i)
	Erro (i)
	1
	5,555556
	0,444444
	1
	 5,483871
	0,483871
	20
	5,988602
	0,011398
	20
	5,215722
	0,215722
	50
	5,999986
	0,000014
	50
	5,000062
	0,000062
	93
	6
	0
	322
	5
	0
	Analisando os dados do exemplo 2 é possível verificar que em ambos os exemplos os métodos numéricos se comportaram de forma similiar. O método Newton Raphson converge mais rápido enquanto o método da falsa posição é o mais lento. Este comportamento é característico dos métodos e é observado na maioria dos exemplos com exceção de alguns que não obedecem um ou outro requisito, mas por enquanto uma conclusão razoável seria de que o método de newton é o mais eficiente.
Dificuldades Encontradas
No decorrer do processo de criação do código-fonte, notamos que os métodos das falsas-cordas e de newton apresentaram certos problemas na convergência, tais como: 
Em polinômios com graus elevados as convergências dependeram de um numero muito grande de iterações no método das falsas-cordas, enquanto que na bissecção e em newton, o mesmo polinômio precisava de um numero consideravelmente menor. Com o polinômio f(x)=2x7+3x6+2x5+3x4+2x3+4x2+2x+4, o método da bissecção precisa de apenas 35 iterações para convergir ate a raiz e o método de newton precisa de 14 iterações. O método das falsas cordas, entretanto, precisa de 893.627 iterações.
No método de Newton, em alguns exemplos, obtivemos a impossibilidade de convergência ou ate mesmo a convergência para uma raiz fora do intervalo desejado. Isso ocorreu porque as exigências para a convergência não foram todas satisfeitas. As exigências são: f(x), f ‘(x) e f ‘’(x) serem contínuas (o que, por estarmos tratando com polinômios, é sempre verdade), f ‘(x) for diferente de zero na solução e o ponto de partida for próximo da solução. No polinômio
 f(x)=4x4+2x3-3x2+2x+3, obtivemos os seguintes resultados:
Isso se dá pelo fato de f’(x) ser muito próximo de zero e o ponto de partida ser muito longe da raiz.
 
Figura 1 Gráfico de f(x)=2x7+3x6+2x5+3x4+2x3+4x2+2x+4. Nota-se que perto de -1, onde se encontram duas das raízes, as derivadas são muito próximas de zero (de um ponto crítico da função)
Houve também certa dificuldade em entender como funciona o mecanismo de recursão, utilizado no processo de obtenção dos intervalos onde iremos procurar as raízes do polinômio. Esse método exigiu certo nível de abstração por parte dos programadores e um alto nível de compreensão da linguagem usada.
Conclusão
Apesar das dificuldades encontradas, pudemos perceber a importância do domínio do conhecimento dos métodos numéricos, em particular os referentes aos zeros de funções, no campo da engenharia e exatas. Além de, obviamente, aprender como aplicar esses métodos computacionalmente, efetuando cálculos através de uma máquina que seriam inviáveis de serem realizados à mão. 
Embora tenhamos utilizado todos os métodos para obter as raízes das funções (métodode newton, bissecção e falsa-posição), pudemos notar que certos métodos são mais eficientes do que outros. O método da bissecção, por exemplo, convergiu rápido para todos os polinômios testados. Mesmo que em alguns casos simples o método de Newton tenha sido muito mais rápido que a bissecção, vemos que com alguns polinômios com características mais peculiares esse método não se mostrou nada eficiente, pois depende de certas condições para que obtenha a convergência.