Zeros de Funções: mudanças entre as edições
(Criou página com 'O problema aqui é encontrar os valores da variável independente <math>x_i</math> que fazem com a função <math>f(x_i)</math> tenha o valor zero.<br> Matematicamente pode ser f...') |
Sem resumo de edição |
||
| Linha 1: | Linha 1: | ||
O problema aqui é encontrar os valores da variável independente <math>x_i</math> que fazem com a função <math>f(x_i)</math> | O problema aqui é encontrar os valores da variável independente <math>x_i</math> que fazem com a função <math>f(x_i)</math> | ||
tenha o valor zero. | tenha o valor zero. | ||
Matematicamente pode ser formalizado assim: | Matematicamente pode ser formalizado assim: | ||
| Linha 26: | Linha 27: | ||
De outra forma podemos dizer que trata-se do problema '''inverso:''' dado o valor da função queremos saber de que valor da variável independente partiu. | De outra forma podemos dizer que trata-se do problema '''inverso:''' dado o valor da função queremos saber de que valor da variável independente partiu. | ||
O método de Newton-Raphson é um procedimento para encontrar zeros de funções de maneira iterativa. | Numericamente, temos três métodos usuais que serão descritos aqui, os métodos da Iteração Simples, Newton-Raphson e Método da Bisecção. | ||
Partindo de um ponto qualquer da função vamos ao próximo ponto com deslocamento dado pela derivada no ponto inicial: | |||
== Iteração Simples == | |||
Para o método da iteração simples, utiliza-se uma nova função <math>F(x)</math> para encontrar-se o zero da função original <math>f(x)</math>, de modo que se define | |||
:<math> F(x) = f(x) + x,</math> | |||
assim | |||
:<math> F(x) = x \,\; para \,\; f(x) = 0.</math> | |||
Utilizamos a própria função para definir o valor de <math>x</math> nas iterações, tendo que existir um "chute" inicial para o valor <math>x_0</math>. Assim, a iteração pode ser definida como | |||
:<math> x_{n+1} = F(x_n) </math>. | |||
Itera-se a equação até atingir-se um valor fixo, ou seja, <math>x_{n+1} = x_n </math>. | |||
As duas principais destavantagens deste método devem-se ao fato de ele ser mais lento que demais métodos e quando utlizados para encontrar raízes "instáveis" de iteração. Para descobrir se haverá raizes instáveis de convergência, utilizamos a condição de convergência do método, perturbando a solução <math>x_{n+1} = x_n = x^*</math> e expandindo em série de Taylor: | |||
:<math>x^*+\delta = F(x^*+\delta) = F(x^*) + \frac{dF(x^*)}{dx}\delta+ ...</math> | |||
Note que para | |||
:<math>\|\frac{dF(x^*)}{dx}\| \leqslant 1</math> | |||
o efeito da perturbação decai, indicando que a raíz <math>x^*</math> é estável por este método. | |||
== Newton-Raphson == | |||
O método de '''Newton-Raphson''' é um procedimento para encontrar zeros de funções de maneira iterativa, assim como o método da iteração simples. Partindo de um ponto qualquer da função vamos ao próximo ponto com deslocamento dado pela derivada no ponto inicial: | |||
:<math>f'(x_{n}) = \frac{ f( x_{n} ) - 0 }{ x_{n} - x_{n+1} } = \frac{0 - f(x_{n})}{(x_{n+1} - x_{n})}\,\!</math> | :<math>f'(x_{n}) = \frac{ f( x_{n} ) - 0 }{ x_{n} - x_{n+1} } = \frac{0 - f(x_{n})}{(x_{n+1} - x_{n})}\,\!</math> | ||
| Linha 36: | Linha 64: | ||
e o processo é repetido até a precisão desejada. | e o processo é repetido até a precisão desejada. | ||
Note que numericamente não temos garantia de achar exatamente a raiz. Devemos fixar um <math>\epsilon</math> | |||
que determina a tolerância com que vamos a aceitar o zero. Ou seja quando | que determina a tolerância com que vamos a aceitar o zero. Ou seja quando | ||
<math>|f(x)| < \epsilon</math> paramos a procura. | <math>|f(x)| < \epsilon</math> paramos a procura. | ||
| Linha 55: | Linha 83: | ||
else | else | ||
x = x - f(x)/g(x) | x = x - f(x)/g(x) | ||
if (f(x) < eps) then | if (abs(f(x)) < eps) then | ||
print*, " | print*, "raiz em x=", x, "f(x)=", f(x) | ||
exit | exit | ||
endif | endif | ||
Edição das 12h00min de 18 de outubro de 2011
O problema aqui é encontrar os valores da variável independente Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_i} que fazem com a função Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x_i)} tenha o valor zero.
Matematicamente pode ser formalizado assim:
- Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle x : f(x) = 0\,}
Os zeros da função f são também chamados de raízes.
Um exemplo simples é achar as raízes da função Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1/(x + 1) - 2} . A simplicidade vem do fato dessa função ter inversa, com o qual a solução pode ser encontrada isolando o x: Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle x = -1/2} que é o zero dessa função ou equação.
Outro exemplo clássico são as raízes de uma parábola:
- Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x)=ax^2+bx+c \,}
da qual existe uma expressão para as raízes (cuja programação é um dos exercícios):
- Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle x = (-b +- \sqrt{b^2 - 4ac})/2a}
Porem, quando a função é mais complicada, o problema de achar os zeros pode não ter (é o mais comum) solução analítica.
Vale notar que ao tratar dos zeros podemos generalizar o conceito para qualquer outro valor. Por exemplo, achar x tal que Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x) = d} é equivalente a achar os zeros de Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x)-d} . De outra forma podemos dizer que trata-se do problema inverso: dado o valor da função queremos saber de que valor da variável independente partiu.
Numericamente, temos três métodos usuais que serão descritos aqui, os métodos da Iteração Simples, Newton-Raphson e Método da Bisecção.
Iteração Simples
Para o método da iteração simples, utiliza-se uma nova função Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle F(x)} para encontrar-se o zero da função original Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x)} , de modo que se define
- Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle F(x) = f(x) + x,}
assim
- Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle F(x) = x \,\; para \,\; f(x) = 0.}
Utilizamos a própria função para definir o valor de Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} nas iterações, tendo que existir um "chute" inicial para o valor Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_0} . Assim, a iteração pode ser definida como
- Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_{n+1} = F(x_n) } .
Itera-se a equação até atingir-se um valor fixo, ou seja, Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_{n+1} = x_n } .
As duas principais destavantagens deste método devem-se ao fato de ele ser mais lento que demais métodos e quando utlizados para encontrar raízes "instáveis" de iteração. Para descobrir se haverá raizes instáveis de convergência, utilizamos a condição de convergência do método, perturbando a solução Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_{n+1} = x_n = x^*} e expandindo em série de Taylor:
- Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle x^*+\delta = F(x^*+\delta) = F(x^*) + \frac{dF(x^*)}{dx}\delta+ ...}
Note que para
- Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle \|\frac{dF(x^*)}{dx}\| \leqslant 1}
o efeito da perturbação decai, indicando que a raíz Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle x^*} é estável por este método.
Newton-Raphson
O método de Newton-Raphson é um procedimento para encontrar zeros de funções de maneira iterativa, assim como o método da iteração simples. Partindo de um ponto qualquer da função vamos ao próximo ponto com deslocamento dado pela derivada no ponto inicial:
- Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle f'(x_{n}) = \frac{ f( x_{n} ) - 0 }{ x_{n} - x_{n+1} } = \frac{0 - f(x_{n})}{(x_{n+1} - x_{n})}\,\!}
Desta forma o próximo ponto está dado por:
- Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}\,\!} .
e o processo é repetido até a precisão desejada. Note que numericamente não temos garantia de achar exatamente a raiz. Devemos fixar um Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle \epsilon} que determina a tolerância com que vamos a aceitar o zero. Ou seja quando Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle |f(x)| < \epsilon} paramos a procura.
Por outra parte o método não garante a convergência, isto é, pode acontecer que o processo entre num ciclo infinito pipocando de uma lado para outro da raiz, sem poder encontrar uma solução.
Programação
Para programá-lo em FORTRAN o mais prático é definir como funções tanto a própria função como a sua derivada. Sejam elas f(x) e g(x) respectivamente, o trecho de código com a implementação do método fica:
...
x = x0
Do
if (g(x)==0) then
print*, "em x=", x, "a derivada é zero"
else
x = x - f(x)/g(x)
if (abs(f(x)) < eps) then
print*, "raiz em x=", x, "f(x)=", f(x)
exit
endif
endif
endo
...
Plano Complexo
O método pode ser estendido a funções f(z) onde z, e f(z) pertencem a C (domínio dos números complexos). Dessa forma todas as raízes de um polinômio podem em princípio ser encontradas. O método tem a mesma formulação teórica. Só muda o programa pois precisamos usar complexos.
Complex f, z Real x,y Read*, x,y z = CMPLX(x,y) ! função FORTRAN intrínseca para converter un par x,y de variáveis reais numa variável complexa ... if (abs(f(z)<eps) print*, z ...