Taxa de convergência
Em análise numérica, a velocidade com que uma sequência convergente se aproxima do seu limite é chamada de taxa de convergência. Embora estritamente falando, o comportamento assintótico de uma sequência não forneça informações sobre qualquer primeira parte finita desta, este conceito é de importância prática se lidamos com uma sequência de sucessivas aproximações para um método iterativo, assim, poucas iterações são necessárias para se obter uma boa aproximação quando a taxa de convergência é alta. Isso pode até mesmo fazer a diferença entre necessitar dez ou um milhão de iterações.
Conceitos semelhantes são usados para métodos discretos. A solução de um problema discreto converge para a solução de um problema contínuo quando o tamanho da grade tende a zero, e a velocidade da convergência é um dos fatores de eficiência do método. No entanto, a terminologia, nesse caso, é diferente da terminologia para métodos iterativos.
Velocidade de convergência para métodos iterativos
Definição básica
Suponha que a sequência {xk} convirja para um número L.
Nós dizemos que essa sequência converge linearmente para L, se existir um número μ ∈ (0, 1) tal que
O número μ é chamado de taxa de convergência.
Se a sequência converge, e
- μ = 0, então a sequência possui convergência super-linear.
- μ = 1, então a sequência possui convergência sub-linear.
Se a sequência converge linearmente e adicionalmente
então é dito que a sequência {xk} converge logaritmicamente para L.
A próxima definição é usada para distinguir taxa de convergências supra-linear. Nós dizemos que a sequência converge com ordem q para L para q>1[notas 1] se
Em particular, convergir com ordem
- 2 é chamado de convergência quadrática,
- 3 é chamado de convergência cúbica,
- etc.
Essa definição é as vezes chamada de Q-convergência linear, Q-convergência quadrática, etc., para distinguir da definição abaixo. O Q significa "quociente", porque a definição usa o quociente entre dois termos sucessivos.
Definição estendida
A desvantagem das definições acima é que, mesmo se não forem satisfeitas essas condições, a convergência de algumas sequências ainda pode ser razoavelmente rápida, porém essa "velocidade" é variável, assim como a sequência {bk} abaixo. Dessa forma, a definição de taxa de convergência é, as vezes, estendida como se segue.
De acordo com a nova definição, a sequência {xk} converge, com pelo menos ordem q, se existir a sequência {εk} tal que e a sequência {εk} converge para zero com ordem q de acordo com a "simples" definição acima. Para distinguir da outra definição, essa é as vezes chamada de R-convergência linear, R-convergência quadrática, etc. (com o R significando "raiz").
Exemplos
Considere as seguintes sequências:
A sequência {ak} converge linearmente para zero com taxa de 1/2. Mais genericamente, a sequência Cμk converge linearmente com taxa μ se |μ| < 1. A sequência {bk} também converge linearmente para 0 com taxa 1/2 de acordo com a definição estendida, mas não sob a definição simples. A sequência {ck} converge supra-linearmente. De fato, é quadraticamente convergente. Finalmente, a sequência {dk} converge sub-linearmente.
![Plot showing the different rates of convergence for the sequences a_k, b_k, c_k and d_k.](http://upload.wikimedia.org/wikipedia/commons/thumb/2/2c/ConvergencePlots.png/400px-ConvergencePlots.png)
Velocidade de convergência para métodos discretos
Uma situação similar existe para métodos discretos. O parâmetro de importância aqui para a velocidade de convergência não é o número de iterações k, mas depende do número de "pontos de grade" e "espaçamento de grade". Nesse caso, o número de pontos de grade num processo de discretização é inversamente proporcional ao número de espaçamento de grade aqui denotado como n.
Nesse caso, a sequência converge para L com ordem p se existe uma constante C tal que
Isso é escrito como |xn - L| = O(n-p) usando a notação do Grande-O.
Essa é uma definição relevante quando discutimos métodos para Integração numérica ou solução para equações diferenciais ordinárias.
Exemplos
A sequência {dk} com dk = 1 / (k+1) foi introduzida abaixo. Essa sequência converge com ordem 1 de acordo com a convenção para métodos discretos.
A sequência {ak} com ak = 2-k, que também foi introduzida abaixo, converge com ordem p para todo número p. Diz-se que converge exponencialmente usando a convenção para métodos discretos. No entanto, converge apenas linearmente (isso é, com ordem 1) usando a convenção para métodos iterativos.
A ordem de convergência de um método discreto é relacionada com seu erro de truncamento.
Aceleração da convergência
Existem muitos métodos que aumentam a taxa de convergência de uma dada sequência, isto é, transformar uma dada sequência para uma que converge mais rápido para o mesmo limite. Tais técnicas são geralmente conhecidas como "Aceleração de sequências". O objetivo da sequência transformada é se tornar menos "trabalhosa" para calcular do que a sequência original. Um exemplo de aceleração de sequência é "Aitken's delta-squared process".
Notas
- ↑ q pode não ser um número inteiro. Por exemplo, o método das secantes tem, nesse caso de convergência para uma raiz regular, ordem de convergência φ=1.618....
Literatura
A definição simples é usada em
- Michelle Schatzman (2002), Numerical analysis: a mathematical introduction, Clarendon Press, Oxford. ISBN 0-19-850279-6.
A definição estendida é usada em
- Kendell A. Atkinson (1988), An introduction to numerical analysis (2nd ed.), John Wiley and Sons. ISBN 0-471-50023-2.
- http://web.mit.edu/rudin/www/MukherjeeRuSc11COLT.pdf
- Walter Gautschi (1997), Numerical analysis: an introduction, Birkhäuser, Boston. ISBN 0-8176-3895-4.
- Endre Süli and David Mayers (2003), An introduction to numerical analysis, Cambridge University Press. ISBN 0-521-00794-1.
Convergência logarítmica é usada em
- Van Tuyl, Andrew H. (1994). «Acceleration of convergence of a family of logarithmically convergent sequences» (PDF). Mathematics of Computation. 63 (207): 229–246
A definição do Grande-O é usada em
- Richard L. Burden and J. Douglas Faires (2001), Numerical Analysis (7th ed.), Brooks/Cole. ISBN 0-534-38216-9
Os termos Q-linear e R-linear são usados em; A definição do Grande-O quando usando séries de Taylor é usada em
- Nocedal, Jorge; Wright, Stephen J. (2006). Numerical Optimization 2nd ed. Berlin, New York: Springer-Verlag. pp. 619+620. ISBN 978-0-387-30303-1
Pode-se também estudar o seguinte artigo sobre Q-linear e R-linear:
- Potra, F. A. (1989). «On Q-order and R-order of convergence». J. Optim. Th. Appl. 63 (3): 415–431. doi:10.1007/BF00939805