Seminário de Dinâmica
Orbital I
Métodos Iterativos para encontrar as
raízes de uma função
Aluno - Carlos H. G. Hassmann
Prof. - Mário Ricci
Introdução
Motivação – raízes de eq. Algébricas
Breve Histórico:
- Sec. XII – Eq. no padrão atual.
- Bhaskara – Solução para eq. de 2º grau.
- Nicolo Fontana – Solução para eq. de 3º grau
(trabalhos publicados por Cardano).
- Fórmulas para 3º e 4º graus são as fórmulas de
Cardano
- Teorema de Niel Abel – Eq. de grau superior a
4 não tem solução por intermédio de fórmulas
Introdução
- O teorema de Abel, juntamente com o de
D´lambert (1746 e provado por Gauss em 1799)
findaram as pesquisas das fórmulas de eq. de
grau n.
- D´lambert – Todo polinômio de grau n tem,
exatamente, n raízes.
- A partir deste momento os estudos se voltaram
a métodos numéricos iterativos
Métodos numéricos iterativos
a)
Métodos de quebra
Temos de ter um intervalo [a, b], onde a função troque de sinal.
O intervalo é partido em dois outros intervalos e verificamos
onde está a raiz e assim prosseguimos.
Ex.: Método da Bissecção.
Métodos numéricos iterativos
b)
Métodos de Ponto Fixo
Começamos de uma aproximação inicial x0 e construímos uma
seqüência {xi} na qual termo é dado por xi+1 = f(xi), onde “ f ” é
uma função de iteração.
Ex.: Método de Newton Raphson
Métodos numéricos iterativos
c)
Métodos de Múltiplos Passos
Generalização do método anterior. Para determinar um ponto
xi+1 utilizamos vários pontos anteriores.
Ex.: Método das secantes
Métodos numéricos iterativos
Método de Newton – Raphson
-
Este é um dos mais clássicos métodos para o cálculo de zeros
de uma função.
As iterações são dadas pelas seguinte fórmula:
xi+1 = xi – [ f(xi) / f´(xi) ]
O entendimento do método é fácil graficamente:
Métodos numéricos iterativos
Método de Newton – Raphson
Do triângulo reto dado por xi, xi+1, f(xi) temos:
tan ø = f(xi) / (xi – xi+1) = f´(xi)
donde:
xi+1 = xi – [ f(xi) / f´(xi) ]
Métodos numéricos iterativos
Método de Newton – Raphson
Ex.:
f(x) = x3 – 5x2 + 17x + 21
f´(x) = 3x2 – 10x + 17
x0 = 1 (arbitrário)
x1 = 1 – (34 / 20) = -2,4
x2 = -2,4 – (-62,424 / 58,28) = -1,3289
x3 = -1,3289 – (-12,7680 / 35,5869) = -0,9701
x4 = -0,9701 – (-1,1101 / 29,5243) = -0,9325
f(x4) = -0,114
Raiz calculada = -0,9321
Métodos numéricos iterativos
Método de Newton – Raphson
Problemas:
- Para raízes de multiplicidade > 1
xi+1 = xi – q [ f(xi) / f´(xi) ]
q=p
onde: p = multiplicidade, pelo menos, 2
Fazer q = p acelera o processo
- Demora na convergência com raízes de multiplicidade
superior a 1.
- Dependendo da escolha de “x0” o método pode ou não
convergir.
Métodos numéricos iterativos
Método das secantes
-
Quando no método de Newton for complicado demais
trabalhar com as derivadas, então usamos o método
das secantes.
-
Este método é baseado nos dois valores mais recentes
de “ f ”.
-
Parte-se de duas aproximações x0 e x1, determinando a
reta que passa por (x0, f(x0)) e (x1, f(x1)).
-
A intersecção dessa reta com o eixo X determina o
próximo ponto x2.
-
Processo continua, então a partir de x1 e x2.
Métodos numéricos iterativos
Método das secantes
- A derivada é substituída pelo quociente das diferenças.
f´(xi) = [ f(xi) – f(xi – 1) ] / [ xi – xi-1]
- O método segue o seguinte equacionamento:
xi+1 = xi – {[ (xi – xi-1).f(xi) ] / [ f(xi) – f(xi-1) ]}
Métodos numéricos iterativos
Método das secantes
- Graficamente:
Métodos numéricos iterativos
Método das secantes
- Exemplo:
f(x) = x3 – 5x2 + 17x + 21
x0 = -1 e x1 = 1
teremos então:
x2 = -0,888 888 888 9
x3 = -0,960 142 348 7
x4 = -0,931 787 651 6
x5 = -0,932 112 394 7
x6 = -0,932 114 856 9
x7 = -0,932 114 856 9
Obs.: Este método é rápido, mas pode ser bem mais demorado
que o método de Newton
Métodos numéricos iterativos
Resolução de sistemas de eq. algébricas ou transcendentes
De modo geral, o problema da resolução de um Sistema de Eq.
Algébricas ou Transcendentes (SEAT) é da seguinte forma.
f1(x1, x2, x3, ... , xn) = 0
f2(x1, x2, x3, ... , xn) = 0
:
:
.
.
fm(x1, x2, x3, ... , xn) = 0
onde:
f1,f2, ... , fn -> funções quaisquer
x1,x2, ... , xn -> varáveis algébricas ou transcendentes
e “n” incógnitas e “m” equações com “m = n”
Métodos numéricos iterativos
Resolução de sistemas de eq. algébricas ou transcendentes
Geometria do problema
x + 2y – 3 = 0
3x2 + y2 – 7 = 0
A solução do sistema está
na intersecção da reta
com a elipse
Métodos numéricos iterativos
Resolução de sistemas de eq. algébricas ou transcendentes
Método de Newton
x(1) = x(0) – (J(x(0))-1 . F(x(0))
Analogia com o método de Newton para uma eq.
-
Onde tínhamos a divisão pela derivada temos a divisão pela
matriz Jacobiana.
-
Onde tínhamos uma reta tangente à curva “ f ” temos um plano
tangente à superfície y = fi(x).
Obs.: “x” é um vetor
Métodos numéricos iterativos
Resolução de sistemas de eq. algébricas ou transcendentes
Calcular, contudo, (J(0))-1 não é interessante, logo resolveremos um
sistema linear.
∆x(0) = x(1) – x(0)
Teremos o seguinte procedimento:
- F(x(0)) = J(∆x(0))
Métodos numéricos iterativos
Resolução de sistemas de eq. algébricas ou transcendentes
Ex. numérico:
x2 + y2 + z2 -1 = 0
2x2 + y2 + 4z = 0
3x2 - 4y + z2
=0
J(x) =
2x
4x
6x
0,25
-F(x0) = 1,25
1,00
2y
2y
-4
2z
-4
2z
x(0) = (0.5 , 0.5 , 0.5)
1
J(x0) = 2
3
∆x
∆x = ∆ y
∆z
1
1
-4
1
-4
1
Métodos numéricos iterativos
Resolução de sistemas de eq. algébricas ou transcendentes
Ex. numérico:
∆x + ∆y + ∆z = 0,25
2∆x + ∆y - 4∆z = 1,25
3∆x - 4∆y + ∆z = -0,125
daí
x(1) = x(0) + ∆x(0) , logo
x(1) = (0.825 , 0.5 , 0.375)
Métodos numéricos iterativos
Resolução de sistemas de eq. algébricas ou transcendentes
Método de Newton Modificado
- Por simplicidade escolheremos m = n = 2
- Consiste em aplicar o método anterior em apenas uma variável,
considerando as demais fixas.
Seja o sistema:
f(x,y)
g(x,y)
com aproximação inicial x(0) = (x0 , y0)
Métodos numéricos iterativos
Resolução de sistemas de eq. algébricas ou transcendentes
Os novos valores serão dados por:
Raízes de Polinômios
Alguns Teoremas:
Se x´ é um zero de f(x), então a multiplicidade “m” de x´ é o
ínfimo de todos os números “k” tais que:
-
Seja p(x) um polinômio de grau n>1 . A multiplicidade de “α”
(zero do p(x)) é “m” se e somente se:
p(α) = p´(α) = p´´(α) = ... = p(m-1) (α) = 0
p(m) (α) ≠ 0
e
Raízes de Polinômios
Alguns Teoremas:
Se os coeficientes de p(x) são reais e µ é a multiplicidade de
uma raiz α , então perto de α o polinômio p(x) deve ter uma das
formas a seguir:
Raízes de Polinômios
Enumeração das raízes -> Descobrirmos o número de raízes e de
que tipo são.
Raízes reais.
O número de raízes positivas de uma eq., com coeficientes
reais, nunca é maior que o número de trocas de sinal T na
seqüência de seus coeficientes não nulos.
Ex.:
p(x) = x3 + 2x2 – 3x – 5
A seqüência de sinais é ++ - - , logo T = 1 e podemos afirmar
que p(x) tem uma raiz positiva.
Raízes de Polinômios
Enumeração das raízes:
-
A mesma regra pode ser aplicada para a enumeração das
raízes reais e negativas de p(x), calculando-se p(-x), pois as
raízes positivas de p(-x) são as negativas de p(x).
p(-x) = -x3 + 2x2 + 3x – 5
-
A seqüência de sinais é - ++ - , logo T = 2. Poderemos ter 2 ou
0 raízes negativas.
-
Se p(x) tiver duas raízes negativas não terá complexas, mas se
não tiver raízes negativas terá, obrigatoriamente, duas
complexas.
Raízes de Polinômios
Enumeração das raízes:
Raízes complexas
-
Dada a eq. p(x) = 0 de grau n sem raízes nulas e se para algum
k, 1≤ k < n tivermos a2k ≤ ak+1, então p(x) terá raízes complexas.
-
Se os coeficientes de p(x) forem todos reais e para algum k,
1 ≤ k < n tivermos ak = 0 e ak-1 . ak+1, então p(x) = 0 terá raízes
complexas.
-
Se os coeficientes forem todos reais e existirem dois ou mais
coeficientes nulos, então p(x) = 0 terá raízes complexas.
Raízes de Polinômios
Enumeração das raízes:
Raízes complexas
Ex.:
p(x) = 2x5 + 3x4 + x3 + 2x2 – 5x + 3
T = 2; daí p(x) = 0 tem duas ou zero raízes reais positivas
p(-x) = -2x5 + 3x4 - x3 + 2x2 + 5x + 3
T = 3; daí p(x) = 0 tem três ou uma raízes reais negativas
Logo:
Raízes de Polinômios
Enumeração das raízes:
Raízes complexas
Ex.:
Pela regra de “du Gua” temos que:
a22 ≤ a3 . a1 , logo 1 ≤ 3 . 2
daí p(x) = 0 tem raízes complexas, eliminando a 1a alternativa
do quadro.
Minimização sem vínculos
-
-
Todos os métodos apresentados até agora são métodos de
minimização. São, porém, métodos que apresentam vínculos.
Os vínculos desses métodos são as raízes das equações. Ao
procurarmos as raízes de uma equação f(x) estamos, na
verdade, procurando valores de x que levem a f(x) ao valor
mínimo zero.
Uma equação f(x), no entanto, pode ter valores de x que
proporcionem igualdades inferiores a zero.
A minimização sem vínculos é a procura de valores “x” para
uma f(x) que a leve para seu menor valor.
Minimização sem vínculos
-
Um bom exemplo para esse tipo de procedimento são
algoritmos de busca seqüencial como por ex. o Método de
Busca de Fibonacci.
-
A busca de Fibonacci é inicializada determinando-se o menor
número de Fibonacci que satisfaz Fne ≥ b – a , onde “e” é uma
tolerância preestabelecida e [a,b] o intervalo original de
interesse. Seja e´ = (b – a) / Fn
-
Os 2 primeiros pontos são localizados Fn-1e´ unidades a partir
dos pontos extremos do intervalo [a,b], sendo Fn-1 o número
precedente de Fn.
Bibliografia
-
-
Matemática Computacional – Dalcídio Cláudio – Porto Alegre
Cálculo Numérico Aspectos Teóricos e Computacionais –Márcia
A. Gomes Ruggiero e Vera Lúcia da Rocha Lopes – McGraw –
Hill 1988 São Paulo
Pesquisa Operacional - Richard Bronson – McGraw – Hill 1985
São Paulo
Numerical Recipies: The art of Scientific Computing – William H.
Press, Brian P. Flannery, Saul A. Teukolsky, Willian T. Vetterling
– Cambridge University Press - Cambridge