# 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 {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
    $\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
    ${\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 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 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 $|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").

### Exemplos

Considere as seguintes sequências:
    ${\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.

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

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