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
[editar | editar código-fonte]Dado uma função deseja-se encontrar uma raiz com uma precisão . O método ITP utiliza de hiperparâmetros , e fornecidos pelo usuário, onde é a proporção áurea . Em cada interação o método ITP calcula o ponto seguindo as três etapas:
1ª Etapa - Interpolação: Cálculo da bisseção e o ponto da regula-falsi[3][4]:
e ;
2ª Etapa - Truncamento: Perturbação da estimativa em direção ao centro:
, onde e ;
3ª Etapa - Projeção: Projetar a estimativa no intervalo minmax:
onde .
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
[editar | editar código-fonte]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 . 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
[editar | editar código-fonte]Como método ITP projeta sua estimativa no intervalo minmax ele exigirá no máximo interações (Teorema 2.1 de [2]). Este é mesmo número de iterações do método de bissecção quando é escolhido para ser .
Desempenho médio
[editar | editar código-fonte]Como o método ITP não leva mais do que 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 (Corolário 2.2 de [2]).
Desempenho assintótico
[editar | editar código-fonte]Se a função for duas vezes diferenciavel e a raiz for simples os intervalos produzidos pelo método ITP convergem para 0 com uma ordem de convergência de se ou se e não for uma potência de dois com o termo não tão próximo de zero (Teorema 2.3 de [2]).
Referências
- ↑ 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
- ↑ 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
- ↑ Bertoldi., Franco, Neide (2006). Cálculo numérico. São Paulo: Pearson. ISBN 9788576050872. OCLC 77545415
- ↑ C., Chapra, Steven (2010). Numerical methods for engineers 6th ed. Boston: McGraw-Hill Higher Education. ISBN 9780073401065. OCLC 244764203
Bibliografia
[editar | editar código-fonte]- 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
[editar | editar código-fonte]- «An Improved Bisection Method, por Kudos.» (em inglês)