Taxa de convergência

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

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 interativo, 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[editar | editar código-fonte]

Definição básica[editar | editar código-fonte]

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

 \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

 \lim_{k\to \infty} \frac{|x_{k+2} - x_{k+1}|}{|x_{k+1} - x_k|} = 1,

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

 \lim_{k\to \infty} \frac{|x_{k+1}-L|}{|x_k-L|^q} = \mu \,\big|\; \mu > 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[editar | editar código-fonte]

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

|x_k - L|\le\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[editar | editar código-fonte]

Considere as seguintes séries:

\begin{align}
  a_0 &= 1 ,\,       &&a_1 = \frac12 ,\, &&a_2 = \frac14 ,\,    &&a_3 = \frac18 ,\,     &&a_4 = \frac1{16} ,\,    &&a_5 = \frac1{32} ,\, &&\ldots ,\, &&a_k = \frac1{2^k} ,\,                           &&\ldots \\
  b_0 &= 1 ,\,       &&b_1 = 1 ,\,       &&b_2 = \frac14 ,\,    &&b_3 = \frac14 ,\,     &&b_4 = \frac1{16} ,\,    &&b_5 = \frac1{16} ,\, &&\ldots ,\, &&b_k = \frac1{4^{\left\lfloor \frac{k}{2} \right\rfloor}} ,\, &&\ldots \\
  c_0 &= \frac12 ,\, &&c_1 = \frac14 ,\, &&c_2 = \frac1{16} ,\, &&c_3 = \frac1{256} ,\, &&c_4 = \frac1{65\,536} ,\,                      &&&&\ldots ,\, &&c_k = \frac1{2^{2^k}} ,\,                       &&\ldots \\
  d_0 &= 1 ,\,       &&d_1 = \frac12 ,\, &&d_2 = \frac13 ,\,    &&d_3 = \frac14 ,\,     &&d_4 = \frac15 ,\,       &&d_5 = \frac16 ,\,    &&\ldots ,\, &&d_k = \frac1{k+1} ,\,                           &&\ldots
\end{align}

A série {ak} converge linearmente para zero com taxa de 1/2. Mais genericamente, a série 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.

Plot showing the different rates of convergence for the sequences a_k, b_k, c_k and d_k.
Linear, Linear, Superlinear/Quadratic and sublinear rate of convergence.

Velocidade de convergência para métodos discretos[editar | editar código-fonte]

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 |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[editar | editar código-fonte]

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[editar | editar código-fonte]

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[editar | editar código-fonte]

  1. 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[editar | editar código-fonte]

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

Convergência logarítmica é usada em

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

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.