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 ℝ$ deseja-se encontrar uma raiz com uma precisão $ϵ>0$. O método ITP utiliza de hiperparâmetros ${\kappa }_1\in (0,\mathrm{\infty }),{\kappa }_2\in [1,1+\varphi )$, $n_{1/2}\equiv \lceil {\log }_2((b_0-a_0)/2ϵ)\rceil$ e $n_0\in [0,\mathrm{\infty })$ fornecidos pelo usuário, onde $\varphi$ é a proporção áurea $\frac{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 \{ϵ2^{n_{1/2}+n_0-j}-\frac{b-a}{2},|x_t-x_{1/2}|\}$.

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\ne 0$ ou se $n_0=0$ e $(b-a)/ϵ$ não for uma potência de dois com o termo $\frac{ϵ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. Predefinição:ISBN.
• L.E. Sigler (2002). Fibonacci's Liber Abaci, Leonardo Pisano's Book of Calculation. Springer-Verlag, New York. Predefinição:ISBN.
• 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

• Predefinição:Link