Método ITP

Em análise numérica, o método ITP, abreviação de Interpolar, Truncar e Projetar, é o primeiro algoritmo de busca de raízes a atingir a convergência superlinear do método secante garantindo o desempenho de pior caso do método de biseção. O método ITP segue a mesma estrutura das estratégias que mantém o controle dos limites superior e inferior para a localização da raiz; e, em adição, o método mantém o controle da região onde o desempenho do pior caso é mantido sob controle. Em cada iteração o método ITP consulta o valor da função em um ponto intermediário do intervalo e descarta a parte do intervalo entre dois pontos onde o valor da função compartilha o mesmo sinal . O método ITP também é o primeiro método com desempenho médio estritamente melhor do que o método de biseção sob qualquer distribuição contínua .

O Método

Dado uma função $f:[a_{0},b_{0}]\to \mathbb {R}$ deseja-se encontrar uma raiz com uma precisão $\epsilon >0$. O método ITP utiliza de hiperparâmetros $\kappa _{1}\in (0,\infty ),\kappa _{2}\in \left[1,1+\phi \right)$, $n_{1/2}\equiv \lceil \log _{2}((b_{0}-a_{0})/2\epsilon )\rceil$ e $n_{0}\in [0,\infty )$ fornecidos pelo usuário, onde $\phi$ é a proporção áurea ${\tfrac {1}{2}}(1+{\sqrt {5}})$. Em cada interação $j=0,1,2...$ o método ITP calcula o ponto $x_{\text{ITP}}$ seguindo as três etapas:

1ª Etapa - Interpolação: Cálculo da bisseção e o ponto da regula-falsi:

$x_{1/2}\equiv {\frac {a+b}{2}}$ e $x_{f}\equiv {\frac {bf(a)-af(b)}{f(a)-f(b)}}$;

2ª Etapa - Truncamento: Perturbação da estimativa em direção ao centro:

$x_{t}\equiv x_{f}+\sigma \delta$, onde $\sigma \equiv {\text{sign}}(x_{1/2}-x_{f})$ e $\delta \equiv \min\{\kappa _{1}|b-a|^{\kappa _{2}},|x_{1/2}-x_{f}|\}$;

3ª Etapa - Projeção: Projetar a estimativa no intervalo minmax:

$x_{\text{ITP}}\equiv x_{1/2}-\sigma \rho _{k}$ onde $\rho _{k}\equiv \min \left\{\epsilon 2^{n_{1/2}+n_{0}-j}-{\frac {b-a}{2}},|x_{t}-x_{1/2}|\right\}$.

Com isso o valor da função neste ponto é consultado e o intervalo é reduzido mantendo o subintervalo com valores de função de sinais opostos em cada extremidade.

Análise

A principal vantagem do método ITP é a sua garantia de não necessitar de mais interações do que o método de bissecção quando $n_{0}=0$. E assim seu desempenho médio é sempre melhor do que o método de bissecção mesmo quando a interpolação falha. Além disso, se as interpolações não falharem (funções suaves), então é garantido que aproveite da alta ordem de convergência como métodos baseados em interpolação.

Pior desempenho do caso

Como método ITP projeta sua estimativa no intervalo minmax ele exigirá no máximo $n_{1/2}+n_{0}$ interações (Teorema 2.1 de ). Este é mesmo número de iterações do método de bissecção quando $n_{0}$ é escolhido para ser $n_{0}=0$.

Desempenho médio

Como o método ITP não leva mais do que $n_{1/2}+n_{0}$ interações, o número médio de interações será sempre menor do que o método da bissecção para qualquer distribuição quando $n_{0}=0$ (Corolário 2.2 de ).

Desempenho assintótico

Se a função $f(x)$ for duas vezes diferenciavel e a raiz $x^{*}$ for simples os intervalos produzidos pelo método ITP convergem para 0 com uma ordem de convergência de ${\sqrt {\kappa _{2}}}$ se $n_{0}\neq 0$ ou se $n_{0}=0$ e $(b-a)/\epsilon$ não for uma potência de dois com o termo ${\tfrac {\epsilon 2^{n_{1/2}}}{b-a}}$ não tão próximo de zero (Teorema 2.3 de ).

Bibliografia

• Richard L. Burden, J. Douglas Faires (2000). Numerical Analysis, 7th ed. Brooks/Cole. ISBN 0-534-38216-9.
• L.E. Sigler (2002). Fibonacci's Liber Abaci, Leonardo Pisano's Book of Calculation. Springer-Verlag, New York. ISBN 0-387-40737-5.
• A. M. Roberts (2020). "Mathematical Philology in the Treatise on Double False Position in an Arabic Manuscript at Columbia University." Philological Encounters 5.3–4 (2020). (On a previously unpublished treatise on Double False Position in a medieval Arabic manuscript.)[1]| [2]

Ligações externas

• «An Improved Bisection Method, por Kudos.» (em inglês)