Taxa de convergência
Em análise numérica, a velocidade com que uma série 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 série {xk} convirja para um número L.
Nós dizemos que essa série converge linearmente para L, se existir um número μ ∈ (0, 1) tal que
O número μ é chamado de taxa de convergência.
Se a série converge, e
- μ = 0, então a série possui convergência super-linear.
- μ = 1, então a série possui convergência sub-linear.
Se a série converge linearmente e adicionalmente
então é dito que a série {xk} converge logaritmicamente para L.
A próxima definição é usada para distinguir taxa de convergências supra-linear. Nós dizemos que a série 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 séries ainda pode ser razoavelmente rápida, porém essa "velocidade" é variável, assim como a série {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 série {xk} converge, com pelo menos, ordem q se existir a série {εk} tal que
e a série {ε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 séries:
A série {ak} converge linearmente para zero com taxa de 1/2. Mais genericamente, a série Cμk converge linearmente com taxa μ se |μ| < 1. A série {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 série {ck} converge supra-linearmente. De fato, é quadraticamente convergente. Finalmente, a série {dk} converge sub-linearmente.
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 série 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 série {dk} com dk = 1 / (k+1) foi introduzida abaixo. Essa série converge com ordem 1 de acordo com a convenção para métodos discretos.
A série {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 série, isto é, transformar uma dada série para uma que converge mais rápido para o mesmo limite. Tais técnicas são geralmente conhecidas como "Aceleração de séries". O objetivo da série transformada é se tornar menos "trabalhosa" para calcular do que a série original. Um exemplo de aceleração de séries é "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