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.

Suponha que a sequência {x_k} 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

${\displaystyle \lim _{k\to \infty }{\frac {|x_{k+1}-L|}{|x_{k}-L|}}=\mu .}$

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

${\displaystyle {\frac {|x_{k+2}-x_{k+1}|}{|x_{k+1}-x_{k}|}}=1,}$

então é dito que a sequência {x_k} 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

${\displaystyle \lim _{k\to \infty }{\frac {|x_{k+1}-L|}{|x_{k}-L|^{q}}}>0.}$

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.

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 {b_k} 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 {x_k} converge, com pelo menos ordem q, se existir a sequência {ε_k} tal que ${\displaystyle |x_{k}-L|\leq \varepsilon _{k}\quad {\mbox{para todo }}k,}$ 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").

Considere as seguintes sequências:

${\displaystyle {\begin{aligned}a_{0}&=1,\,&&a_{1}={\frac {1}{2}},\,&&a_{2}={\frac {1}{4}},\,&&a_{3}={\frac {1}{8}},\,&&a_{4}={\frac {1}{16}},\,&&a_{5}={\frac {1}{32}},\,&&\ldots ,\,&&a_{k}={\frac {1}{2^{k}}},\,&&\ldots \\b_{0}&=1,\,&&b_{1}=1,\,&&b_{2}={\frac {1}{4}},\,&&b_{3}={\frac {1}{4}},\,&&b_{4}={\frac {1}{16}},\,&&b_{5}={\frac {1}{16}},\,&&\ldots ,\,&&b_{k}={\frac {1}{4^{\left\lfloor {\frac {k}{2}}\right\rfloor }}},\,&&\ldots \\c_{0}&={\frac {1}{2}},\,&&c_{1}={\frac {1}{4}},\,&&c_{2}={\frac {1}{16}},\,&&c_{3}={\frac {1}{256}},\,&&c_{4}={\frac {1}{65\,536}},\,&&&&\ldots ,\,&&c_{k}={\frac {1}{2^{2^{k}}}},\,&&\ldots \\d_{0}&=1,\,&&d_{1}={\frac {1}{2}},\,&&d_{2}={\frac {1}{3}},\,&&d_{3}={\frac {1}{4}},\,&&d_{4}={\frac {1}{5}},\,&&d_{5}={\frac {1}{6}},\,&&\ldots ,\,&&d_{k}={\frac {1}{k+1}},\,&&\ldots \end{aligned}}}$

A sequência {a_k} 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 {b_k} 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 {c_k} converge supra-linearmente. De fato, é quadraticamente convergente. Finalmente, a sequência {d_k} converge sub-linearmente.

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 ${\displaystyle x_{n}}$ converge para L com ordem p se existe uma constante C tal que

${\displaystyle |x_{n}-L|<Cn^{-p}{\text{ para todo }}n.}$

Isso é escrito como |x_n - 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.

A sequência {d_k} com d_k = 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 {a_k} com a_k = 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.

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".

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