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 {x_k} 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

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

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

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

então é dito que a série {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 série converge com ordem q para L para q>1 se

$\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.

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 {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 série {x_k} converge, com pelo menos, ordem q se existir a série {ε_k} tal que

$|x_{k}-L|\leq \varepsilon _{k}\quad {\mbox{para todo }}k,$

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:

${\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 série {a_k} 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 {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 série {c_k} converge supra-linearmente. De fato, é quadraticamente convergente. Finalmente, a série {d_k} converge sub-linearmente.

Linear, Linear, Superlinear/Quadratic and sublinear rate of convergence.

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

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

Exemplos

A série {d_k} com d_k = 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 {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.

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

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