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[1] 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 [2]. 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 [2].

O Método

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

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

x 1 / 2 ≡ a + b 2 {\displaystyle x_{1/2}\equiv {\frac {a+b}{2}}} e x f ≡ b f ( a ) − a f ( b ) f ( a ) − f ( b ) {\displaystyle 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 ≡ x f + σ δ {\displaystyle x_{t}\equiv x_{f}+\sigma \delta } , onde σ ≡ sign ( x 1 / 2 − x f ) {\displaystyle \sigma \equiv {\text{sign}}(x_{1/2}-x_{f})} e δ ≡ min { κ 1 | b − a | κ 2 , | x 1 / 2 − x f | } {\displaystyle \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 ITP ≡ x 1 / 2 − σ ρ k {\displaystyle x_{\text{ITP}}\equiv x_{1/2}-\sigma \rho _{k}} onde ρ k ≡ min { ϵ 2 n 1 / 2 + n 0 − j − b − a 2 , | x t − x 1 / 2 | } {\displaystyle \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.[2]

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 {\displaystyle 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 {\displaystyle n_{1/2}+n_{0}} interações (Teorema 2.1 de [2]). Este é mesmo número de iterações do método de bissecção quando n 0 {\displaystyle n_{0}} é escolhido para ser n 0 = 0 {\displaystyle n_{0}=0} .

Desempenho médio

Como o método ITP não leva mais do que n 1 / 2 + n 0 {\displaystyle 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 {\displaystyle n_{0}=0} (Corolário 2.2 de [2]).

Desempenho assintótico

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

Referências

  1. ↑ Argyros, I. K.; Hernández-Verón, M. A.; Rubio, M. J. (2019). «On the Convergence of Secant-Like Methods». Current Trends in Mathematical Analysis and Its Interdisciplinary Applications (em inglês): 141–183. ISBN 978-3-030-15241-3. doi:10.1007/978-3-030-15242-0_5 
  2. ↑ a b c d e f Oliveira, I. F. D.; Takahashi, R. H. C. (6 de dezembro de 2020). «An Enhancement of the Bisection Method Average Performance Preserving Minmax Optimality». ACM Transactions on Mathematical Software. 47 (1): 5:1–5:24. ISSN 0098-3500. doi:10.1145/3423597 
  3. ↑ Bertoldi., Franco, Neide (2006). Cálculo numérico. São Paulo: Pearson. ISBN 9788576050872. OCLC 77545415 
  4. ↑ C., Chapra, Steven (2010). Numerical methods for engineers 6th ed. Boston: McGraw-Hill Higher Education. ISBN 9780073401065. OCLC 244764203 

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)