Método ITP

Origem: Wikipédia, a enciclopédia livre.

Na análise numérica , o método ITP , abreviação de Interpolar, Truncar e Projeto , é o primeiro algoritmo de descoberta de raiz que atinge a convergência superlinear do método secante[1], enquanto mantém o desempenho de pior caso ideal, do método de bissecção. O método ITP segue a mesma estrutura das estratégias de agrupamento padrão que mantém o controle dos limites superior e inferior para a localização da raiz; mas também mantém o controle da região onde o desempenho do pior caso é mantido no limite superior. Como estratégia de agrupamento, em cada iteração o ITP consulta o valor da função em um ponto e descarta a parte do intervalo entre dois pontos onde o valor da função compartilha o mesmo sinal.[2] É também o primeiro método com desempenho médio garantido estritamente melhor do que o método de bissecção em qualquer distribuição contínua.[2]

Etapas do Método[editar | editar código-fonte]

Para realizar o método o ponto consultado é calculado com três etapas:

1ª Etapa: interpolação para encontrar a estimativa da regra falsi[3][4];

2ª Etapa: perturbação / truncamento da estimativa (semelhante à regra falsi § Melhorias na regra falsi);

3ª Etapa: projeção da estimativa perturbada em um intervalo na vizinhança do ponto médio da bissecção.

A vizinhança em torno do ponto de bissecção é calculada em cada iteração para garantir a otimização minmax (Teorema 2.1 de [5] ).

É necessário três hiperparâmetros , e . Onde  é a proporção áurea , sendo que os dois primeiros controlam o tamanho do truncamento e o terceiro é uma variável de folga que controla o tamanho do intervalo para a etapa de projeção.

Dado , e . 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 os pontos falsos da regra: e ;

2ª Etapa - Truncamento: Perturbação do estimador em direção ao centro: , onde e ;

3ª Etapa - Projeção: Projetar o estimador para o intervalo minmax: onde .

Com isso o valor da função neste ponto é consultado e o intervalo é reduzido para colocar a raiz entre parênteses, mantendo o subintervalo com valores de função de sinal oposto em cada extremidade.[2]

Análise[editar | editar código-fonte]

A principal vantagem do método ITP é a de que ele é garantido que não necessita mais interações do que o método de bissecção quando . E assim seu desempenho médio é garantido ser 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 o estimador no intervalo mínimo/máximo com ele exigirá no máximo interações (Teorema 2.1 de [2]). Este é o mínimo/máximo ideal como o método de bissecção quando é escolhido para ser .

Desempenho médio[editar | editar código-fonte]

Como não leva mais do que as interações 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 considerada quando (Corolário 2.2 de [2]).

Desempenho assintótico[editar | editar código-fonte]

Se a função for duas vezes diferençável e a raiz for simples, em seguida, os intervalos produzidos pelo método ITP convergem para 0 com uma ordem de convergência de se ou se e não é uma potência de dois com o termo 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 
  5. 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 (1): 5:1–5:24. ISSN 0098-3500. doi:10.1145/3423597. Consultado em 3 de maio de 2021 

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]