[obm-l] Re: [obm-l] Método Numérico
Obrigado pela análise prof. Nicolau !
Vou pensar um pouco e ver se tenho uma luz.
Até mais.
> On Wed, Nov 24, 2004 at 12:00:15AM -0200, Osvaldo Mello Sponquiado wrote:
> > Olá pessoal!
> >
> > Criei um método numérico (Método Mello) para o cálculo de raízes de funções
> > reais, com uma variável real...
>
> Estou cortando partes para comentar.
>
> ...
> > O resumo do método é o seguinte:
> >
> > Método numérico iterativo para determinação de raízes reais de funções reais.
> > O método se baseia em traçar circunferências com centro em (x0,f(x0)) e raio
> > f(x0), sendo x0 um valor inicial dado, e tomar uma das intersecções da
> > circunferência com a função como sendo o valor x1, e assim iterativamente até
> > que xn, resultado da n-ésima iteração, possa ser admitido como aproximação
> > para o valor da raiz.
>
> A pergunta principal para mim é: como você vai encontrar a interseção
> do gráfico de f com a circunferência? Isto deve ser pelo menos tão difícil
> quanto encontrar a interseção do gráfico com uma reta, por exemplo o eixo x,
> mas este é o problema original que o algoritmo todo tenta resolver.
>
> ...
>
> > Tendo definido a circunferência C, sua equação é:
> > (x_0-x_1)^2+(f(x-0)-f(x_1))^2=[f(x_0)]^2 (i)
> >
> > Usando Aproximação de Taylor f(x)= S[n=0;+inf]f{n}(x_0).(x-x_0)^n/n! ({n}
> > indica ordem n para a derivada de f)utilizo so as duas primeiras parcelas
> > desta formula: f(x_1)=f(x_0)+f'(x_0).(x_1-x_0) (ii)
> >
> > Substituindo ii em i chego à equação geral dos x_k's do metodo: x_(k+1)=x_k
> > + 'ou' - sqrt[(f(x_k))^2/(1+(f'(x_k))^2)] (iii)
>
> Se eu bem entendi esta passagem, você resolve a dificuldade acima
> encontrando não a interseção do gráfico com a circunferência e sim
> a interseção da reta tangente com a circunferência.
> Assim o seu método é uma variação do método de Newton
> e para que ele seja de interesse você deveria apontar
> algum ponto de vista, alguma situação, em que ele seja
> *melhor* do que o método de Newton. Certamente que nas situações
> mais óbvias o seu método é um pouco *pior* do que Newton.
>
> A situação típica para o método de Newton é a do seguinte exemplo.
> Tome f(x) = x^2 - 1. Se x_n = 1 + eps, a reta tangente ao gráfico
> de f por (x_n,f(x_n)) tem coeficiente angular 2x_n logo é
> y - x_n^2 + 1 = 2x_n (x - x_n).
> Resolvendo y = 0 (Newton) temos
> x_{n+1} = x_n - (x_n^2 - 1)/(2 x_n) =
> = 1 + eps - (1 + 2 eps + eps^2 - 1)/(2(1+eps))
> = 1 + eps ( 1 - (2 + eps)/2(1 + eps) ) ~= 1 + eps ( 1 - (2+eps)(1-eps)/2)
> ~= 1 + eps ( 1 - 1 - eps/2) = 1 + eps^2/2.
> A sua aproximação a partir de x_n claramente está entre x_{n+1} e x_n.
> Mas ela é bem pior do que x_{n+1}. No limite (quando eps é pequeno),
> o gráfico fica quase reto. Newton toma por aproximação a reta tangente
> e pega a interseção desta reta com o eixo horizontal, o que dá convergência
> quadrática, como você viu acima. O seu método toma a mesma reta tangente
> e pega um ponto que está a uma razão mais ou menos fixa,
> garantindo convergência apenas linear.
>
> []s, N.
> =
> Instruções para entrar na lista, sair da lista e usar a lista em
> http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
> =
>
Atenciosamente,
Osvaldo Mello Sponquiado
Engenharia Elétrica, 2ºano
UNESP - Ilha Solteira
__
Acabe com aquelas janelinhas que pulam na sua tela.
AntiPop-up UOL - É grátis!
http://antipopup.uol.com.br/
=
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=
Re: [obm-l] Método Numérico
Oi,
O Livro do Elon "Análise Real" apresenta um tópico sobre Método de
Newton (eu acho que é na seção de aplicações da derivada) que explica
muito bem porquê é quadrático, quais as hipóteses necessárias, etc.
Vale a pena ver para ter uma orientação.
Abraços,
--
Bernardo Freitas Paulo da Costa
On Wed, 24 Nov 2004 00:00:15 -0200, Osvaldo Mello Sponquiado
<[EMAIL PROTECTED]> wrote:
> Olá pessoal!
>
> Criei um método numérico (Método Mello) para o cálculo de raízes de funções reais,
> com uma variável real e gostaria de saber se existe algum professor de Cálculo
> Numérico na lista, pois aqui na UNESP de Ilha Solteira existe um único professor
> deste ramo (que não se interessou pelo meu trabalho) e preciso de um orientador para
> poder apresentar o trabalho em congressos e me ajudar a fazer algumas analises (de
> convergencia por exemplo).
> Criei um método numérico para o cálculo de raízes de funções reais, com uma variável
> real.
>
> O resumo do método é o seguinte:
>
> Método numérico iterativo para determinação de raízes reais de funções reais. O
> método se baseia em traçar circunferências com centro em (x0,f(x0)) e raio f(x0),
> sendo x0 um valor inicial dado, e tomar uma das intersecções da circunferência com a
> função como sendo o valor x1, e assim iterativamente até que xn, resultado da
> n-ésima iteração, possa ser admitido como aproximação para o valor da raiz. O
> método apresenta as características de exigir a escolha de um único valor inicial,
> de possuir convergência garantida e de ter fácil interpretação geométrica, servindo
> também como ferramenta didática em cursos de Cálculo Numérico
>
> Olhando geometricamente considera-se uma função real f(x) contínua ao menos no
> intervalo [x,x_0], no qual x é a raiz de f e x_0 é um valor tal que x_0 >x.
> Define-se a circunferência C como a circunferência de centro (x_0,f(x_0)) e raio
> f(x_0) conforme ilustrado pela fig em anexo.
>
> Percebe-se que, sendo a função contínua ao menos no intervalo entre a raiz e o ponto
> x_0, garante-se que a circunferência intercepta a função em pelo menos um ponto, de
> abscissa x_1 e ordenada f(x_1).
>
> O método apresentado consiste em traçar uma nova circunferência de centro
> (x_1,f(x_1)) e raio f(x_1), que interceptará um novo ponto da função, de abscissa
> x_2 e ordenada f(x_2), e assim iterativamente até que se possa tomar xn, resultado
> da n-ésima iteração, como sendo aproximadamente uma raiz da função. Tendo definido a
> circunferência C, sua equação é:
> (x_0-x_1)^2+(f(x-0)-f(x_1))^2=[f(x_0)]^2 (i)
>
> Usando Aproximação de Taylor f(x)= S[n=0;+inf]f{n}(x_0).(x-x_0)^n/n! ({n} indica
> ordem n para a derivada de f)utilizo so as duas primeiras parcelas desta formula:
> f(x_1)=f(x_0)+f'(x_0).(x_1-x_0) (ii)
>
> Substituindo ii em i chego à equação geral dos x_k's do metodo: x_(k+1)=x_k + 'ou'
> - sqrt[(f(x_k))^2/(1+(f'(x_k))^2)] (iii)
>
> A partir dele consegui mostrar que a diferença entre os erros entre as iterações k+1
> e k vale
> -[(eps-x_k).f'(x_k)+0,5.(eps-x_k)^2.f'(c_k)]/sqrt(1+(f'(x_k))^2); c_k pertence a
> (eps;x_k)
>
> Como pode ser percebido geometricamente, o método nunca encontrará a raiz da função,
> já que o valor xk só seria igual a x se o raio da circunferência C fosse zero.
> Assim, por maior que seja o número de iterações, o valor obtido será sempre uma
> aproximação. Além disso, a equação geral do método considera o valor negativo do
> (iii). Além de este fato garantir a convergência da série numérica (x_0; x_1; x_2;
> ...), pode-se prever que | x_(k+1) | será sempre menor que | x_k |, o que exige a
> escolha de um valor inicial maior que a raiz. No entanto, se por algum motivo for
> necessário escolher x_0 menor que o possível valor da raiz (por exemplo, se a
> continuidade da função só puder ser garantida para valores menores que a raiz),
> basta considerar o valor positivo do , na Equação 3.
>
> Fiz algumas analises comparativas com Newton-Raphson para testar o metodo, alem
> disso implementei - o em Python e depois plotei alguns graficos de (x_(k+1)-x_k) x
> nº d iterações
> para uma função fixa e sendo aplicado Newton-Raphson e meu método.
>
> Mas a questão que quero levantar é como fazer uma análise de convergencia do método ?
> como garantir que ele é ao menos linear ?
> Há alguma maneira de se calcular sua ordem de convergência?
> Procurei varias bibliografias, mas nelas se mostra como foi feita para outros
> métodos, e não para um metodo generico.
> Bom se alguem puder me ajudar, escrevendo, indicando um livro, ou algum professor, é
> bem vindo.
>
> Atenciosamente,
>
> Osvaldo Mello Sponquiado
> Engenharia Elétrica, 2ºano
> UNESP - Ilha Solteira
>
> __
> Acabe com aquelas janelinhas que pulam na sua tela.
> AntiPop-up UOL - É grátis!
> http://antipopup.uol.com.br/
>
> =
>
Re: [obm-l] Método Numérico
On Wed, Nov 24, 2004 at 12:00:15AM -0200, Osvaldo Mello Sponquiado wrote:
> Olá pessoal!
>
> Criei um método numérico (Método Mello) para o cálculo de raízes de funções
> reais, com uma variável real...
Estou cortando partes para comentar.
...
> O resumo do método é o seguinte:
>
> Método numérico iterativo para determinação de raízes reais de funções reais.
> O método se baseia em traçar circunferências com centro em (x0,f(x0)) e raio
> f(x0), sendo x0 um valor inicial dado, e tomar uma das intersecções da
> circunferência com a função como sendo o valor x1, e assim iterativamente até
> que xn, resultado da n-ésima iteração, possa ser admitido como aproximação
> para o valor da raiz.
A pergunta principal para mim é: como você vai encontrar a interseção
do gráfico de f com a circunferência? Isto deve ser pelo menos tão difícil
quanto encontrar a interseção do gráfico com uma reta, por exemplo o eixo x,
mas este é o problema original que o algoritmo todo tenta resolver.
...
> Tendo definido a circunferência C, sua equação é:
> (x_0-x_1)^2+(f(x-0)-f(x_1))^2=[f(x_0)]^2 (i)
>
> Usando Aproximação de Taylor f(x)= S[n=0;+inf]f{n}(x_0).(x-x_0)^n/n! ({n}
> indica ordem n para a derivada de f)utilizo so as duas primeiras parcelas
> desta formula: f(x_1)=f(x_0)+f'(x_0).(x_1-x_0) (ii)
>
> Substituindo ii em i chego à equação geral dos x_k's do metodo: x_(k+1)=x_k
> + 'ou' - sqrt[(f(x_k))^2/(1+(f'(x_k))^2)] (iii)
Se eu bem entendi esta passagem, você resolve a dificuldade acima
encontrando não a interseção do gráfico com a circunferência e sim
a interseção da reta tangente com a circunferência.
Assim o seu método é uma variação do método de Newton
e para que ele seja de interesse você deveria apontar
algum ponto de vista, alguma situação, em que ele seja
*melhor* do que o método de Newton. Certamente que nas situações
mais óbvias o seu método é um pouco *pior* do que Newton.
A situação típica para o método de Newton é a do seguinte exemplo.
Tome f(x) = x^2 - 1. Se x_n = 1 + eps, a reta tangente ao gráfico
de f por (x_n,f(x_n)) tem coeficiente angular 2x_n logo é
y - x_n^2 + 1 = 2x_n (x - x_n).
Resolvendo y = 0 (Newton) temos
x_{n+1} = x_n - (x_n^2 - 1)/(2 x_n) =
= 1 + eps - (1 + 2 eps + eps^2 - 1)/(2(1+eps))
= 1 + eps ( 1 - (2 + eps)/2(1 + eps) ) ~= 1 + eps ( 1 - (2+eps)(1-eps)/2)
~= 1 + eps ( 1 - 1 - eps/2) = 1 + eps^2/2.
A sua aproximação a partir de x_n claramente está entre x_{n+1} e x_n.
Mas ela é bem pior do que x_{n+1}. No limite (quando eps é pequeno),
o gráfico fica quase reto. Newton toma por aproximação a reta tangente
e pega a interseção desta reta com o eixo horizontal, o que dá convergência
quadrática, como você viu acima. O seu método toma a mesma reta tangente
e pega um ponto que está a uma razão mais ou menos fixa,
garantindo convergência apenas linear.
[]s, N.
=
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=
[obm-l] Método Numérico
Olá pessoal!
Criei um método numérico (Método Mello) para o cálculo de raízes de funções reais, com
uma variável real e gostaria de saber se existe algum professor de Cálculo Numérico na
lista, pois aqui na UNESP de Ilha Solteira existe um único professor deste ramo (que
não se interessou pelo meu trabalho) e preciso de um orientador para poder apresentar
o trabalho em congressos e me ajudar a fazer algumas analises (de convergencia por
exemplo).
Criei um método numérico para o cálculo de raízes de funções reais, com uma variável
real.
O resumo do método é o seguinte:
Método numérico iterativo para determinação de raízes reais de funções reais. O método
se baseia em traçar circunferências com centro em (x0,f(x0)) e raio f(x0), sendo x0 um
valor inicial dado, e tomar uma das intersecções da circunferência com a função como
sendo o valor x1, e assim iterativamente até que xn, resultado da n-ésima iteração,
possa ser admitido como aproximação para o valor da raiz. O método apresenta as
características de exigir a escolha de um único valor inicial, de possuir
convergência garantida e de ter fácil interpretação geométrica, servindo também como
ferramenta didática em cursos de Cálculo Numérico
Olhando geometricamente considera-se uma função real f(x) contínua ao menos no
intervalo [x,x_0], no qual x é a raiz de f e x_0 é um valor tal que x_0 >x. Define-se
a circunferência C como a circunferência de centro (x_0,f(x_0)) e raio f(x_0)
conforme ilustrado pela fig em anexo.
Percebe-se que, sendo a função contínua ao menos no intervalo entre a raiz e o ponto
x_0, garante-se que a circunferência intercepta a função em pelo menos um ponto, de
abscissa x_1 e ordenada f(x_1).
O método apresentado consiste em traçar uma nova circunferência de centro (x_1,f(x_1))
e raio f(x_1), que interceptará um novo ponto da função, de abscissa x_2 e ordenada
f(x_2), e assim iterativamente até que se possa tomar xn, resultado da n-ésima
iteração, como sendo aproximadamente uma raiz da função. Tendo definido a
circunferência C, sua equação é:
(x_0-x_1)^2+(f(x-0)-f(x_1))^2=[f(x_0)]^2 (i)
Usando Aproximação de Taylor f(x)= S[n=0;+inf]f{n}(x_0).(x-x_0)^n/n! ({n} indica ordem
n para a derivada de f)utilizo so as duas primeiras parcelas desta formula:
f(x_1)=f(x_0)+f'(x_0).(x_1-x_0) (ii)
Substituindo ii em i chego à equação geral dos x_k's do metodo: x_(k+1)=x_k + 'ou' -
sqrt[(f(x_k))^2/(1+(f'(x_k))^2)] (iii)
A partir dele consegui mostrar que a diferença entre os erros entre as iterações k+1 e
k vale
-[(eps-x_k).f'(x_k)+0,5.(eps-x_k)^2.f'(c_k)]/sqrt(1+(f'(x_k))^2); c_k pertence a
(eps;x_k)
Como pode ser percebido geometricamente, o método nunca encontrará a raiz da função,
já que o valor xk só seria igual a x se o raio da circunferência C fosse zero. Assim,
por maior que seja o número de iterações, o valor obtido será sempre uma aproximação.
Além disso, a equação geral do método considera o valor negativo do (iii). Além de
este fato garantir a convergência da série numérica (x_0; x_1; x_2; ...), pode-se
prever que | x_(k+1) | será sempre menor que | x_k |, o que exige a escolha de um
valor inicial maior que a raiz. No entanto, se por algum motivo for necessário
escolher x_0 menor que o possível valor da raiz (por exemplo, se a continuidade da
função só puder ser garantida para valores menores que a raiz), basta considerar o
valor positivo do , na Equação 3.
Fiz algumas analises comparativas com Newton-Raphson para testar o metodo, alem disso
implementei - o em Python e depois plotei alguns graficos de (x_(k+1)-x_k) x nº d
iterações
para uma função fixa e sendo aplicado Newton-Raphson e meu método.
Mas a questão que quero levantar é como fazer uma análise de convergencia do método ?
como garantir que ele é ao menos linear ?
Há alguma maneira de se calcular sua ordem de convergência?
Procurei varias bibliografias, mas nelas se mostra como foi feita para outros métodos,
e não para um metodo generico.
Bom se alguem puder me ajudar, escrevendo, indicando um livro, ou algum professor, é
bem vindo.
Atenciosamente,
Osvaldo Mello Sponquiado
Engenharia Elétrica, 2ºano
UNESP - Ilha Solteira
__
Acabe com aquelas janelinhas que pulam na sua tela.
AntiPop-up UOL - É grátis!
http://antipopup.uol.com.br/
=
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=
