Bissecção Newton-Raphson Discussão finalarosas/FisicaComputacional/aula03-raizes.pdf · Na...

IntroduçãoBissecção

Newton-RaphsonDiscussão final

Equações não-lineares e raizes de polinômios

Alexandre Rosas

Departamento de FísicaUniversidade Federal da Paraíba

6 de Maio de 2009

Alexandre Rosas Equações não-lineares e raizes de polinômios

IntroduçãoBissecção

Newton-RaphsonDiscussão final

O problema

Como calcular a solução de f (~x) = 0?

Exceto por problemas lineares, procedemos iterativamenteaté atingirmos um critério de paradaAqui, trataremos apenas de problemas unidimensionaisPara problemas multidimensionais

Método de Newton funciona se tivermos uma boaestimativa inicialHá ainda os métodos globalmente convergentes os quaisgarantem convergência (ver Numerical Recipes in C)

Alexandre Rosas Equações não-lineares e raizes de polinômios

IntroduçãoBissecção

Newton-RaphsonDiscussão final

O problema

Como calcular a solução de f (x) = 0

Exceto por problemas lineares, procedemos iterativamenteaté atingirmos um critério de paradaAqui, trataremos apenas de problemas unidimensionaisPara problemas multidimensionais

Método de Newton funciona se tivermos uma boaestimativa inicialHá ainda os métodos globalmente convergentes os quaisgarantem convergência (ver Numerical Recipes in C)

Alexandre Rosas Equações não-lineares e raizes de polinômios

IntroduçãoBissecção

Newton-RaphsonDiscussão final

O problema

Como calcular a solução de f (x) = 0

Exceto por problemas lineares, procedemos iterativamenteaté atingirmos um critério de paradaAqui, trataremos apenas de problemas unidimensionaisPara problemas multidimensionais

Método de Newton funciona se tivermos uma boaestimativa inicialHá ainda os métodos globalmente convergentes os quaisgarantem convergência (ver Numerical Recipes in C)

Alexandre Rosas Equações não-lineares e raizes de polinômios

IntroduçãoBissecção

Newton-RaphsonDiscussão final

O problema

Como calcular a solução de f (x) = 0

Exceto por problemas lineares, procedemos iterativamenteaté atingirmos um critério de paradaAqui, trataremos apenas de problemas unidimensionaisPara problemas multidimensionais

Método de Newton funciona se tivermos uma boaestimativa inicialHá ainda os métodos globalmente convergentes os quaisgarantem convergência (ver Numerical Recipes in C)

Alexandre Rosas Equações não-lineares e raizes de polinômios

IntroduçãoBissecção

Newton-RaphsonDiscussão final

O problema

Como calcular a solução de f (x) = 0?

Exceto por problemas lineares, procedemos iterativamenteaté atingirmos um critério de paradaAqui, trataremos apenas de problemas unidimensionaisPara problemas multidimensionais

Método de Newton funciona se tivermos uma boaestimativa inicialHá ainda os métodos globalmente convergentes os quaisgarantem convergência (ver Numerical Recipes in C)

Alexandre Rosas Equações não-lineares e raizes de polinômios

IntroduçãoBissecção

Newton-RaphsonDiscussão final

Valor inicial

ExemploNa aproximação de campo médio para o modelo de Ising despin-1/2, encontramos a seguinte equação transcendental:

m = tanh(βJm)

onde β = 1kBT , J é a constante de troca e m a magnetização.

f (x) = x − tanh(ax) = 0

Um valor inicial pode ser obtido do gráfico de f (x)

Alexandre Rosas Equações não-lineares e raizes de polinômios

IntroduçãoBissecção

Newton-RaphsonDiscussão final

Valor inicial

ExemploNa aproximação de campo médio para o modelo de Ising despin-1/2, encontramos a seguinte equação transcendental:

m = tanh(βJm)

Para determinar m(βJ), definimos

f (x) = x − tanh(ax) = 0

Um valor inicial pode ser obtido do gráfico de f (x)

Alexandre Rosas Equações não-lineares e raizes de polinômios

IntroduçãoBissecção

Newton-RaphsonDiscussão final

Valor inicial

ExemploNa aproximação de campo médio para o modelo de Ising despin-1/2, encontramos a seguinte equação transcendental:

m = tanh(βJm)

Para determinar m(βJ), definimos

f (x) = x − tanh(ax) = 0

Um valor inicial pode ser obtido do gráfico de f (x)

Alexandre Rosas Equações não-lineares e raizes de polinômios

IntroduçãoBissecção

Newton-RaphsonDiscussão final

Valor inicial

-0.15

-0.1

-0.05

0

0.05

0.1

0.15

-1 -0.5 0 0.5 1

f(m)

m

Alexandre Rosas Equações não-lineares e raizes de polinômios

IntroduçãoBissecção

Newton-RaphsonDiscussão final

Métodos iterativos

Encontrar uma raiz de f (x) ⇒ encontrar s tal que f (s) = 0Na prática, estamos limitados por uma precisão numéricaPortanto, vamos procurar x0 tal que |x0 − s| < ε ou|f (x0)| < δ

Alexandre Rosas Equações não-lineares e raizes de polinômios

IntroduçãoBissecção

Newton-RaphsonDiscussão final

Métodos iterativos

Encontrar uma raiz de f (x) ⇒ encontrar s tal que f (s) = 0Na prática, estamos limitados por uma precisão numéricaPortanto, vamos procurar x0 tal que |x0 − s| < ε ou|f (x0)| < δ

Alexandre Rosas Equações não-lineares e raizes de polinômios

IntroduçãoBissecção

Newton-RaphsonDiscussão final

Métodos iterativos

Encontrar uma raiz de f (x) ⇒ encontrar s tal que f (s) = 0Na prática, estamos limitados por uma precisão numéricaPortanto, vamos procurar x0 tal que |x0 − s| < ε ou|f (x0)| < δ

Alexandre Rosas Equações não-lineares e raizes de polinômios

IntroduçãoBissecção

Newton-RaphsonDiscussão final

Método

Algoritmo1 Escolha a e b tais que a < x0 < b

O intervalo deve conter apenas uma raiz ⇒ f (a)f (b) < 02 Defina c = a+b

2 e calcule f (c)

3 Se f (a)f (c) > 0, faça a = c, se não, faça b = c.4 Se b − a > ε, e |f (a)− f (b)| > δ vá para o passo 25 A solução é c

Alexandre Rosas Equações não-lineares e raizes de polinômios

IntroduçãoBissecção

Newton-RaphsonDiscussão final

Método

Algoritmo1 Escolha a e b tais que a < x0 < b

Quanto menor o intervalo [a,b] melhor!2 Defina c = a+b

2 e calcule f (c)

3 Se f (a)f (c) > 0, faça a = c, se não, faça b = c.4 Se b − a > ε, e |f (a)− f (b)| > δ vá para o passo 25 A solução é c

Alexandre Rosas Equações não-lineares e raizes de polinômios

IntroduçãoBissecção

Newton-RaphsonDiscussão final

Método

Algoritmo1 Escolha a e b tais que a < x0 < b

Quanto menor o intervalo [a,b] melhor!2 Defina c = a+b

2 e calcule f (c)

3 Se f (a)f (c) > 0, faça a = c, se não, faça b = c.4 Se b − a > ε, e |f (a)− f (b)| > δ vá para o passo 25 A solução é c

Alexandre Rosas Equações não-lineares e raizes de polinômios

IntroduçãoBissecção

Newton-RaphsonDiscussão final

Método

Algoritmo1 Escolha a e b tais que a < x0 < b

Quanto menor o intervalo [a,b] melhor!2 Defina c = a+b

2 e calcule f (c)

3 Se f (a)f (c) > 0, faça a = c, se não, faça b = c.4 Se b − a > ε, e |f (a)− f (b)| > δ vá para o passo 25 A solução é c

Alexandre Rosas Equações não-lineares e raizes de polinômios

IntroduçãoBissecção

Newton-RaphsonDiscussão final

Método

Algoritmo1 Escolha a e b tais que a < x0 < b

Quanto menor o intervalo [a,b] melhor!2 Defina c = a+b

2 e calcule f (c)

3 Se f (a)f (c) > 0, faça a = c, se não, faça b = c.4 Se b − a > ε, e |f (a)− f (b)| > δ vá para o passo 25 A solução é c

Alexandre Rosas Equações não-lineares e raizes de polinômios

IntroduçãoBissecção

Newton-RaphsonDiscussão final

Método

Algoritmo1 Escolha a e b tais que a < x0 < b

Quanto menor o intervalo [a,b] melhor!2 Defina c = a+b

2 e calcule f (c)

3 Se f (a)f (c) > 0, faça a = c, se não, faça b = c.4 Se b − a > ε, e |f (a)− f (b)| > δ vá para o passo 25 A solução é c

Alexandre Rosas Equações não-lineares e raizes de polinômios

IntroduçãoBissecção

Newton-RaphsonDiscussão final

Método

Algoritmo1 Escolha a e b tais que a < x0 < b

Quanto menor o intervalo [a,b] melhor!2 Defina c = a+b

2 e calcule f (c)

3 Se f (a)f (c) > 0, faça a = c, se não, faça b = c.4 Se b − a > ε, e |f (a)− f (b)| > δ vá para o passo 25 A solução é c

Alexandre Rosas Equações não-lineares e raizes de polinômios

IntroduçãoBissecção

Newton-RaphsonDiscussão final

Exemplo

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

m

kB T/J

Alexandre Rosas Equações não-lineares e raizes de polinômios

IntroduçãoBissecção

Newton-RaphsonDiscussão final

Prós e Contras

PrósTiro certo: dificilmente não encontrará a resposta

ContrasConvergência lenta: após n iterações, intervalo seráreduzido a

12n |a− b|

Não pode ser aplicado se a raiz for ponto de máximo oumínimo

Alexandre Rosas Equações não-lineares e raizes de polinômios

IntroduçãoBissecção

Newton-RaphsonDiscussão final

Prós e Contras

PrósTiro certo: dificilmente não encontrará a resposta

ContrasConvergência lenta: após n iterações, intervalo seráreduzido a

12n |a− b|

Não pode ser aplicado se a raiz for ponto de máximo oumínimo

Alexandre Rosas Equações não-lineares e raizes de polinômios

IntroduçãoBissecção

Newton-RaphsonDiscussão final

Prós e Contras

PrósTiro certo: dificilmente não encontrará a resposta

ContrasConvergência lenta: após n iterações, intervalo seráreduzido a

12n |a− b|

Não pode ser aplicado se a raiz for ponto de máximo oumínimo

Alexandre Rosas Equações não-lineares e raizes de polinômios

IntroduçãoBissecção

Newton-RaphsonDiscussão final

Método

A ideiaGeometricamente, consistem em estender a tangente no pontoatual até cruzar o eixo−x e tomar este valor como aaproximação seguinte

A matemática

f (s) = 0 = f (s − x + x) = f (x) + f ′(x)(s − x) + . . .

Portanto, para pequenas distâncias e funções bemcomportadas

s = x − f (x)

f ′(x)⇒ xn+1 = xn −

f (xn)

f ′(xn)

Alexandre Rosas Equações não-lineares e raizes de polinômios

IntroduçãoBissecção

Newton-RaphsonDiscussão final

Método

A ideiaGeometricamente, consistem em estender a tangente no pontoatual até cruzar o eixo−x e tomar este valor como aaproximação seguinte

A matemática

f (s) = 0 = f (s − x + x) = f (x) + f ′(x)(s − x) + . . .

Portanto, para pequenas distâncias e funções bemcomportadas

s = x − f (x)

f ′(x)⇒ xn+1 = xn −

f (xn)

f ′(xn)

Alexandre Rosas Equações não-lineares e raizes de polinômios

IntroduçãoBissecção

Newton-RaphsonDiscussão final

Método

A ideiaGeometricamente, consistem em estender a tangente no pontoatual até cruzar o eixo−x e tomar este valor como aaproximação seguinte

A matemática

f (s) = 0 = f (s − x + x) = f (x) + f ′(x)(s − x) + . . .

Portanto, para pequenas distâncias e funções bemcomportadas

s = x − f (x)

f ′(x)⇒ xn+1 = xn −

f (xn)

f ′(xn)

Alexandre Rosas Equações não-lineares e raizes de polinômios

IntroduçãoBissecção

Newton-RaphsonDiscussão final

Método

A ideiaGeometricamente, consistem em estender a tangente no pontoatual até cruzar o eixo−x e tomar este valor como aaproximação seguinte

A matemática

f (s) = 0 = f (s − x + x) = f (x) + f ′(x)(s − x) + . . .

Portanto, para pequenas distâncias e funções bemcomportadas

s = x − f (x)

f ′(x)⇒ xn+1 = xn −

f (xn)

f ′(xn)

Alexandre Rosas Equações não-lineares e raizes de polinômios

IntroduçãoBissecção

Newton-RaphsonDiscussão final

Método

A ideiaGeometricamente, consistem em estender a tangente no pontoatual até cruzar o eixo−x e tomar este valor como aaproximação seguinte

A matemática

f (s) = 0 = f (s − x + x) = f (x) + f ′(x)(s − x) + . . .

Portanto, para pequenas distâncias e funções bemcomportadas

s = x − f (x)

f ′(x)⇒ xn+1 = xn −

f (xn)

f ′(xn)

Alexandre Rosas Equações não-lineares e raizes de polinômios

IntroduçãoBissecção

Newton-RaphsonDiscussão final

Interpretação geométrica

x

f (x)

−1.1 −0.9 −0.7 −0.5 −0.3 −0.1 0.1 0.3 0.5 0.7 0.9 1.1

−0.2

−0.1

0.1

0.2

Alexandre Rosas Equações não-lineares e raizes de polinômios

IntroduçãoBissecção

Newton-RaphsonDiscussão final

Interpretação geométrica

x

f (x)

−1.1 −0.9 −0.7 −0.5 −0.3 −0.1 0.1 0.3 0.5 0.7 0.9 1.1

−0.2

−0.1

0.1

0.2

×n

f (×n)

Alexandre Rosas Equações não-lineares e raizes de polinômios

IntroduçãoBissecção

Newton-RaphsonDiscussão final

Interpretação geométrica

x

f (x)

−1.1 −0.9 −0.7 −0.5 −0.3 −0.1 0.1 0.3 0.5 0.7 0.9 1.1

−0.2

−0.1

0.1

0.2

×n

f (×n)

f ′ (×n)

Alexandre Rosas Equações não-lineares e raizes de polinômios

IntroduçãoBissecção

Newton-RaphsonDiscussão final

Interpretação geométrica

x

f (x)

−1.1 −0.9 −0.7 −0.5 −0.3 −0.1 0.1 0.3 0.5 0.7 0.9 1.1

−0.2

−0.1

0.1

0.2

f ′ (×n)

xn+1 = xn − f (xn)f ′(xn)

Alexandre Rosas Equações não-lineares e raizes de polinômios

IntroduçãoBissecção

Newton-RaphsonDiscussão final

Interpretação geométrica

x

f (x)

−1.1 −0.9 −0.7 −0.5 −0.3 −0.1 0.1 0.3 0.5 0.7 0.9 1.1

−0.2

−0.1

0.1

0.2

f ′ (×n)

xn+1 = xn − f (xn)f ′(xn)

f (×n+1)

Alexandre Rosas Equações não-lineares e raizes de polinômios

IntroduçãoBissecção

Newton-RaphsonDiscussão final

Implementação

Algoritmo1 Escolha um valor inicial para x0

2 Escolha um número máximo de passos Nmax

3 Inicialize a variável número de passos N4 Calcule o próximo valor de x0

x0 ← x0 −f (x0)

f ′(x0)

5 Se |f (x0)| > δ e N < Nmax , faça N ← N + 1 e vá para opasso 4

6 A solução é x0

Alexandre Rosas Equações não-lineares e raizes de polinômios

IntroduçãoBissecção

Newton-RaphsonDiscussão final

Implementação

Algoritmo1 Escolha um valor inicial para x0

2 Escolha um número máximo de passos Nmax

3 Inicialize a variável número de passos N4 Calcule o próximo valor de x0

x0 ← x0 −f (x0)

f ′(x0)

5 Se |f (x0)| > δ e N < Nmax , faça N ← N + 1 e vá para opasso 4

6 A solução é x0

Alexandre Rosas Equações não-lineares e raizes de polinômios

IntroduçãoBissecção

Newton-RaphsonDiscussão final

Implementação

Algoritmo1 Escolha um valor inicial para x0

2 Escolha um número máximo de passos Nmax

3 Inicialize a variável número de passos N4 Calcule o próximo valor de x0

x0 ← x0 −f (x0)

f ′(x0)

5 Se |f (x0)| > δ e N < Nmax , faça N ← N + 1 e vá para opasso 4

6 A solução é x0

Alexandre Rosas Equações não-lineares e raizes de polinômios

IntroduçãoBissecção

Newton-RaphsonDiscussão final

Implementação

Algoritmo1 Escolha um valor inicial para x0

2 Escolha um número máximo de passos Nmax

3 Inicialize a variável número de passos N4 Calcule o próximo valor de x0

x0 ← x0 −f (x0)

f ′(x0)

5 Se |f (x0)| > δ e N < Nmax , faça N ← N + 1 e vá para opasso 4

6 A solução é x0

Alexandre Rosas Equações não-lineares e raizes de polinômios

IntroduçãoBissecção

Newton-RaphsonDiscussão final

Implementação

Algoritmo1 Escolha um valor inicial para x0

2 Escolha um número máximo de passos Nmax

3 Inicialize a variável número de passos N4 Calcule o próximo valor de x0

x0 ← x0 −f (x0)

f ′(x0)

5 Se |f (x0)| > δ e N < Nmax , faça N ← N + 1 e vá para opasso 4

6 A solução é x0

Alexandre Rosas Equações não-lineares e raizes de polinômios

IntroduçãoBissecção

Newton-RaphsonDiscussão final

Implementação

Algoritmo1 Escolha um valor inicial para x0

2 Escolha um número máximo de passos Nmax

3 Inicialize a variável número de passos N4 Calcule o próximo valor de x0

x0 ← x0 −f (x0)

f ′(x0)

5 Se |f (x0)| > δ e N < Nmax , faça N ← N + 1 e vá para opasso 4

6 A solução é x0

Alexandre Rosas Equações não-lineares e raizes de polinômios

IntroduçãoBissecção

Newton-RaphsonDiscussão final

Prós e Contras

PrósConvergência rápida

εn+1 =|f ′′(s)|[f ′(s)]2

ε2n

Ótimo se conhecermos f ′(x) analiticamente

Contras

Às vezes é difícil prever para que raiz o método convergiráConverge se: f (x) ∈ C2(R), for convexa, crescente e possuir zero

Se não pudermos calcular f ′(x) analiticamente, podemoster erros devido à perda de precisão numérica

Alexandre Rosas Equações não-lineares e raizes de polinômios

IntroduçãoBissecção

Newton-RaphsonDiscussão final

Prós e Contras

PrósConvergência rápida

εn+1 =|f ′′(s)|[f ′(s)]2

ε2n

Ótimo se conhecermos f ′(x) analiticamente

Contras

Às vezes é difícil prever para que raiz o método convergiráConverge se: f (x) ∈ C2(R), for convexa, crescente e possuir zero

Se não pudermos calcular f ′(x) analiticamente, podemoster erros devido à perda de precisão numérica

Alexandre Rosas Equações não-lineares e raizes de polinômios

IntroduçãoBissecção

Newton-RaphsonDiscussão final

Prós e Contras

PrósConvergência rápida

εn+1 =|f ′′(s)|[f ′(s)]2

ε2n

Ótimo se conhecermos f ′(x) analiticamente

Contras

Às vezes é difícil prever para que raiz o método convergiráConverge se: f (x) ∈ C2(R), for convexa, crescente e possuir zero

Se não pudermos calcular f ′(x) analiticamente, podemoster erros devido à perda de precisão numérica

Alexandre Rosas Equações não-lineares e raizes de polinômios

IntroduçãoBissecção

Newton-RaphsonDiscussão final

Prós e Contras

PrósConvergência rápida

εn+1 =|f ′′(s)|[f ′(s)]2

ε2n

Ótimo se conhecermos f ′(x) analiticamente

Contras

Às vezes é difícil prever para que raiz o método convergiráConverge se: f (x) ∈ C2(R), for convexa, crescente e possuir zero

Se não pudermos calcular f ′(x) analiticamente, podemoster erros devido à perda de precisão numérica

Alexandre Rosas Equações não-lineares e raizes de polinômios

IntroduçãoBissecção

Newton-RaphsonDiscussão final

Possíveis dificuldades

Se o cálculo da função envolver instabilidades numéricas,os algoritmos podem não convergir ou retornar resultadoserradosErros de arredondamento podem fazer a função oscilarnumericamenteRaízes próximas também podem causar problemas

SaídaTransformar a função em uma função bem comportadaÉ importante conhecer as propriedades analíticas dafunção e configurar o algoritmo de acordo com elas

Alexandre Rosas Equações não-lineares e raizes de polinômios

IntroduçãoBissecção

Newton-RaphsonDiscussão final

Possíveis dificuldades

Se o cálculo da função envolver instabilidades numéricas,os algoritmos podem não convergir ou retornar resultadoserradosErros de arredondamento podem fazer a função oscilarnumericamenteRaízes próximas também podem causar problemas

SaídaTransformar a função em uma função bem comportadaÉ importante conhecer as propriedades analíticas dafunção e configurar o algoritmo de acordo com elas

Alexandre Rosas Equações não-lineares e raizes de polinômios

IntroduçãoBissecção

Newton-RaphsonDiscussão final

Possíveis dificuldades

Se o cálculo da função envolver instabilidades numéricas,os algoritmos podem não convergir ou retornar resultadoserradosErros de arredondamento podem fazer a função oscilarnumericamenteRaízes próximas também podem causar problemas

SaídaTransformar a função em uma função bem comportadaÉ importante conhecer as propriedades analíticas dafunção e configurar o algoritmo de acordo com elas

Alexandre Rosas Equações não-lineares e raizes de polinômios

IntroduçãoBissecção

Newton-RaphsonDiscussão final

Possíveis dificuldades

Se o cálculo da função envolver instabilidades numéricas,os algoritmos podem não convergir ou retornar resultadoserradosErros de arredondamento podem fazer a função oscilarnumericamenteRaízes próximas também podem causar problemas

SaídaTransformar a função em uma função bem comportadaÉ importante conhecer as propriedades analíticas dafunção e configurar o algoritmo de acordo com elas

Alexandre Rosas Equações não-lineares e raizes de polinômios

IntroduçãoBissecção

Newton-RaphsonDiscussão final

Possíveis dificuldades

Se o cálculo da função envolver instabilidades numéricas,os algoritmos podem não convergir ou retornar resultadoserradosErros de arredondamento podem fazer a função oscilarnumericamenteRaízes próximas também podem causar problemas

SaídaTransformar a função em uma função bem comportadaÉ importante conhecer as propriedades analíticas dafunção e configurar o algoritmo de acordo com elas

Alexandre Rosas Equações não-lineares e raizes de polinômios

IntroduçãoBissecção

Newton-RaphsonDiscussão final

Tipos de algoritmo

Isolamento de raízesInicia com uma região limitada que contém a raizReduzem a região iterativamente – proporciona estimativarigorosa do erroTêm convergência garantida

Refinamento de raízesParte de uma estimativa inicial e tenta melhorá-laSó converge se iniciado próximo a raizSe funcionar, converge rapidamente

Alexandre Rosas Equações não-lineares e raizes de polinômios

IntroduçãoBissecção

Newton-RaphsonDiscussão final

Tipos de algoritmo

Isolamento de raízesInicia com uma região limitada que contém a raizReduzem a região iterativamente – proporciona estimativarigorosa do erroTêm convergência garantida

Refinamento de raízesParte de uma estimativa inicial e tenta melhorá-laSó converge se iniciado próximo a raizSe funcionar, converge rapidamente

Alexandre Rosas Equações não-lineares e raizes de polinômios

IntroduçãoBissecção

Newton-RaphsonDiscussão final

Tipos de algoritmo

Isolamento de raízesInicia com uma região limitada que contém a raizReduzem a região iterativamente – proporciona estimativarigorosa do erroTêm convergência garantida

Refinamento de raízesParte de uma estimativa inicial e tenta melhorá-laSó converge se iniciado próximo a raizSe funcionar, converge rapidamente

Alexandre Rosas Equações não-lineares e raizes de polinômios

IntroduçãoBissecção

Newton-RaphsonDiscussão final

Tipos de algoritmo

Isolamento de raízesInicia com uma região limitada que contém a raizReduzem a região iterativamente – proporciona estimativarigorosa do erroTêm convergência garantida

Refinamento de raízesParte de uma estimativa inicial e tenta melhorá-laSó converge se iniciado próximo a raizSe funcionar, converge rapidamente

Alexandre Rosas Equações não-lineares e raizes de polinômios

IntroduçãoBissecção

Newton-RaphsonDiscussão final

Tipos de algoritmo

Isolamento de raízesInicia com uma região limitada que contém a raizReduzem a região iterativamente – proporciona estimativarigorosa do erroTêm convergência garantida

Refinamento de raízesParte de uma estimativa inicial e tenta melhorá-laSó converge se iniciado próximo a raizSe funcionar, converge rapidamente

Alexandre Rosas Equações não-lineares e raizes de polinômios

IntroduçãoBissecção

Newton-RaphsonDiscussão final

Tipos de algoritmo

Isolamento de raízesInicia com uma região limitada que contém a raizReduzem a região iterativamente – proporciona estimativarigorosa do erroTêm convergência garantida

Refinamento de raízesParte de uma estimativa inicial e tenta melhorá-laSó converge se iniciado próximo a raizSe funcionar, converge rapidamente

Alexandre Rosas Equações não-lineares e raizes de polinômios

IntroduçãoBissecção

Newton-RaphsonDiscussão final

Comparação

Isolamento Bissecção muito simples, convergência linear

Falsa posição baseado em interpolação, convergê-cia linear

Método deBrent

combina interpolação e bissecção,método rápido

Refinamento Newton toma a intersecção da tangente comabicissa como nova aproximação

Secante baseado no método de Newton, nãocalcula derivada em todos os passos

Método deSteffenson

Associa método de Newton a um pro-cedimento de aceleração produzindoa nova aproximaçãoRi = xi−(xi+1−xi)

2/(xi+2−2xi+1 +xi)Muito rápido

Alexandre Rosas Equações não-lineares e raizes de polinômios

IntroduçãoBissecção

Newton-RaphsonDiscussão final

Comparação

Isolamento Bissecção muito simples, convergência linear

Falsa posição baseado em interpolação, convergê-cia linear

Método deBrent

combina interpolação e bissecção,método rápido

Refinamento Newton toma a intersecção da tangente comabicissa como nova aproximação

Secante baseado no método de Newton, nãocalcula derivada em todos os passos

Método deSteffenson

Associa método de Newton a um pro-cedimento de aceleração produzindoa nova aproximaçãoRi = xi−(xi+1−xi)

2/(xi+2−2xi+1 +xi)Muito rápido

Alexandre Rosas Equações não-lineares e raizes de polinômios

IntroduçãoBissecção

Newton-RaphsonDiscussão final

Comparação

Isolamento Bissecção muito simples, convergência linear

Falsa posição baseado em interpolação, convergê-cia linear

Método deBrent

combina interpolação e bissecção,método rápido

Refinamento Newton toma a intersecção da tangente comabicissa como nova aproximação

Secante baseado no método de Newton, nãocalcula derivada em todos os passos

Método deSteffenson

Associa método de Newton a um pro-cedimento de aceleração produzindoa nova aproximaçãoRi = xi−(xi+1−xi)

2/(xi+2−2xi+1 +xi)Muito rápido

Alexandre Rosas Equações não-lineares e raizes de polinômios

IntroduçãoBissecção

Newton-RaphsonDiscussão final

Comparação

Isolamento Bissecção muito simples, convergência linear

Falsa posição baseado em interpolação, convergê-cia linear

Método deBrent

combina interpolação e bissecção,método rápido

Refinamento Newton toma a intersecção da tangente comabicissa como nova aproximação

Secante baseado no método de Newton, nãocalcula derivada em todos os passos

Método deSteffenson

Associa método de Newton a um pro-cedimento de aceleração produzindoa nova aproximaçãoRi = xi−(xi+1−xi)

2/(xi+2−2xi+1 +xi)Muito rápido

Alexandre Rosas Equações não-lineares e raizes de polinômios

IntroduçãoBissecção

Newton-RaphsonDiscussão final

Comparação

Isolamento Bissecção muito simples, convergência linear

Falsa posição baseado em interpolação, convergê-cia linear

Método deBrent

combina interpolação e bissecção,método rápido

Refinamento Newton toma a intersecção da tangente comabicissa como nova aproximação

Secante baseado no método de Newton, nãocalcula derivada em todos os passos

Método deSteffenson

Associa método de Newton a um pro-cedimento de aceleração produzindoa nova aproximaçãoRi = xi−(xi+1−xi)

2/(xi+2−2xi+1 +xi)Muito rápido

Alexandre Rosas Equações não-lineares e raizes de polinômios

IntroduçãoBissecção

Newton-RaphsonDiscussão final

Comparação

Isolamento Bissecção muito simples, convergência linear

Falsa posição baseado em interpolação, convergê-cia linear

Método deBrent

combina interpolação e bissecção,método rápido

Refinamento Newton toma a intersecção da tangente comabicissa como nova aproximação

Secante baseado no método de Newton, nãocalcula derivada em todos os passos

Método deSteffenson

Associa método de Newton a um pro-cedimento de aceleração produzindoa nova aproximaçãoRi = xi−(xi+1−xi)

2/(xi+2−2xi+1 +xi)Muito rápido

Alexandre Rosas Equações não-lineares e raizes de polinômios