Velocidade de convergência das suítes

Na análise numérica - um ramo da matemática - pode-se classificar as sequências convergentes de acordo com sua velocidade de convergência em direção ao seu ponto limite. É uma forma de avaliar a eficiência dos algoritmos que os geram.

As sequências aqui consideradas são convergentes sem serem estacionárias (todos os seus termos são mesmo considerados diferentes do ponto limite). Se uma sequência é estacionária, todos os seus elementos são iguais a partir de um determinado posto e então é normal se interessar pelo número de elementos diferentes do ponto limite. Isso é o que fazemos quando estudamos a complexidade dos algoritmos que encontram o que procuram em um número finito de etapas.

Visão geral

Definições

Esta seção descreve algumas noções de velocidade de convergência de uma seqüência de um espaço vetorial normatizado , em direção ao seu limite , a partir da comparação da norma do erro de dois elementos sucessivos. O erro é sempre considerado diferente de zero :, para qualquer índice . Esta suposição é razoável quando a sequência é gerada por um algoritmo "bem projetado", ou seja, para o qual, assim que , a sequência se torna estacionária após (todas as iterações seguintes são iguais a e não há mais nenhum significado para falar velocidade de convergência). Estamos, portanto, interessados ​​no quociente(xk){\ displaystyle \ left (x_ {k} \ right)} (E,‖⋅‖){\ displaystyle \ left (E, \ | \ cdot \ | \ right)}x∗{\ displaystyle x _ {*}} xk-x∗{\ displaystyle x_ {k} -x _ {*}}xk≠x∗{\ displaystyle x_ {k} \ neq x _ {*}}k{\ displaystyle k}xk=x∗{\ displaystyle x_ {k} = x _ {*}}xk{\ displaystyle x_ {k}}x∗{\ displaystyle x _ {*}}

‖xk+1-x∗‖‖xk-x∗‖α{\ displaystyle {\ frac {\ | x_ {k + 1} -x _ {*} \ |} {\ | x_ {k} -x _ {*} \ | ^ {\ alpha}}}},

onde é um número real estritamente positivo. O interesse neste quociente vem do fato de que muitas vezes pode ser estimado fazendo uma expansão de Taylor em torno de funções que definem o problema que se busca resolver e para o qual é uma solução. Obviamente, quanto maior , mais rápida é a velocidade de convergência (porque assintoticamente ). α{\ displaystyle \ alpha}x∗{\ displaystyle x _ {*}}x∗{\ displaystyle x _ {*}}α{\ displaystyle \ alpha}‖xk-x∗‖<1{\ displaystyle \ | x_ {k} -x _ {*} \ | <1}

Resumidamente, dizemos que a ordem q de convergência é se o quociente acima for limitado. O prefixo q-, que lembra a palavra quociente , é freqüentemente omitido. Também dizemos que a convergência é: α>1{\ displaystyle \ alpha> 1}

• linear , se há um padrão , um verdadeiro e um índice de tal forma que para todos ,  ;‖⋅‖{\ displaystyle \ | \ cdot \ |}τ∈[0,1[{\ displaystyle \ tau \ in {[0,1 [}}k1{\ displaystyle k_ {1}}k⩾k1{\ displaystyle k \ geqslant k_ {1}}‖xk+1-x∗‖⩽τ‖xk-x∗‖{\ displaystyle \ | x_ {k + 1} -x _ {*} \ | \ leqslant \ tau \ | x_ {k} -x _ {*} \ |}
• superlinear se  ;‖xk+1-x∗‖/‖xk-x∗‖→0{\ displaystyle \ | x_ {k + 1} -x _ {*} \ | / \ | x_ {k} -x _ {*} \ | \ to 0}
• quadrática (segunda ordem) se existe uma constante de tal modo que para cada índice ,  ;VS{\ displaystyle C}k{\ displaystyle k}‖xk+1-x∗‖⩽VS‖xk-x∗‖2{\ displaystyle \ | x_ {k + 1} -x _ {*} \ | \ leqslant C \ | x_ {k} -x _ {*} \ | ^ {2}}
• cúbico (ordem 3) se existe uma constante de tal modo que para cada índice ,  ;VS{\ displaystyle C}k{\ displaystyle k}‖xk+1-x∗‖⩽VS‖xk-x∗‖3{\ displaystyle \ | x_ {k + 1} -x _ {*} \ | \ leqslant C \ | x_ {k} -x _ {*} \ | ^ {3}}
• quártico (ordem 4) existe uma constante de tal modo que para cada índice , ,  etc.VS{\ displaystyle C}k{\ displaystyle k}‖xk+1-x∗‖⩽VS‖xk-x∗‖4{\ displaystyle \ | x_ {k + 1} -x _ {*} \ | \ leqslant C \ | x_ {k} -x _ {*} \ | ^ {4}}

As três principais taxas de quociente de convergência são as taxas de convergência linear , superlinear e quadrática . Eles são discutidos mais detalhadamente abaixo.

Impacto no número de dígitos significativos válidos

Numericamente, quanto mais rápida a convergência, mais rápido o número de dígitos significativos válidos de (aqueles idênticos aos de ) aumenta. Vamos dar uma definição mais precisa dessa noção. Se for um vetor, não podemos definir por um escalar a correção dos algarismos significativos de todos os seus componentes, mas podemos fazê-lo em média no sentido da norma em diante . Presumimos isso porque não podemos definir quais são os dígitos significativos de zero. Se for igual , diremos que tem 4 dígitos significativos corretos (este seria de fato o caso se e fosse escalar). Isso leva à seguinte definição. xk{\ displaystyle x_ {k}}x∗{\ displaystyle x _ {*}}xk{\ displaystyle x_ {k}}E{\ displaystyle E}x∗≠0{\ displaystyle x _ {*} \ neq 0}‖xk-x∗‖/‖x∗‖{\ displaystyle \ | x_ {k} -x _ {*} \ | / \ | x _ {*} \ |}10-4{\ displaystyle 10 ^ {- 4}}xk{\ displaystyle x_ {k}}xk{\ displaystyle x_ {k}}x∗{\ displaystyle x _ {*}}

Número de dígitos significativos corretos  -  O número de dígitos significativos corretos em comparação com o número real xk{\ displaystyle x_ {k}}x∗≠0{\ displaystyle x _ {*} \ neq 0}

σk: =-registro10‖xk-x∗‖‖x∗‖{\ displaystyle \ sigma _ {k}: = - \ log _ {10} \, {\ frac {\ | x_ {k} -x _ {*} \ |} {\ | x _ {*} \ |} }}.

Quando , podemos expressar as taxas de convergência como um quociente, usando em vez do quociente acima, o que faremos. x∗≠0{\ displaystyle x _ {*} \ neq 0}σk{\ displaystyle \ sigma _ {k}}

Estimativa sem conhecimento do limite

Às vezes é interessante verificar numericamente se as sequências geradas por um algoritmo realmente têm a velocidade de convergência esperada. Claro, essa é uma maneira de verificar se o algoritmo está implementado corretamente, mas há outra motivação. Por exemplo, sob certas suposições de regularidade, sabemos que o algoritmo de Newton converge quadraticamente; este algoritmo procede pela linearização da função que ele procura cancelar; verificar se a convergência das sequências geradas é de fato quadrática é então uma indicação sobre a exatidão do cálculo da derivada.

Em geral, a solução não é conhecida, de modo que verificar a velocidade de convergência no quociente esperado, examinando o quociente do padrão de erros sucessivos, requer uma resolução dupla do problema. A primeira resolução é usada para calcular uma aproximação precisa da solução  ; a segunda resolução examina os quocientes acima. Pode-se evitar essa dupla resolução se conseguirmos expressar a velocidade de convergência em termos de uma quantidade cujo limite é conhecido, normalmente zero. x∗{\ displaystyle x _ {*}}

Este é o caso se buscarmos cancelar uma função , ou seja, encontrar um ponto tal que f:E→F{\ displaystyle f: E \ a F}x∗{\ displaystyle x _ {*}}

f(x∗)=0{\ displaystyle f (x _ {*}) = 0},

providenciou que

f(x)∼(x-x∗){\ displaystyle f (x) \ sim (x-x _ {*})}.

Esta escrita significa que existem constantes e tais que, para qualquer vizinho de , temos . Tal equivalência de comportamento assintótico é verificada se é diferenciável em e se é invertível. As velocidades de convergência de uma sequência apresentada a seguir também serão expressas em termos do logaritmo da norma de , de forma a permitir a verificação numérica dessa convergência. VS1>0{\ displaystyle C_ {1}> 0}VS2>0{\ displaystyle C_ {2}> 0}x{\ displaystyle x} x∗{\ displaystyle x _ {*}}VS1‖f(x)‖⩽‖x-x∗‖⩽VS2‖f(x)‖{\ displaystyle C_ {1} \ | f (x) \ | \ leqslant \ | x-x _ {*} \ | \ leqslant C_ {2} \ | f (x) \ |}f{\ displaystyle f}x∗{\ displaystyle x _ {*}}f′(x∗){\ displaystyle f '(x _ {*})}(xk){\ displaystyle \ left (x_ {k} \ right)}f(xk){\ displaystyle f (x_ {k})}

Convergência linear

Essa velocidade de convergência é às vezes chamada de convergência geométrica , porque a norma do erro é aumentada assintoticamente por uma seqüência geométrica da razão . ‖xk-x∗‖{\ displaystyle \ | x_ {k} -x _ {*} \ |}τ{\ displaystyle \ tau}

Convergência linear  -  Dizemos que uma sequência converge linearmente para se houver uma norma , um escalar e um índice tal que (xk){\ displaystyle \ left (x_ {k} \ right)}x∗{\ displaystyle x _ {*}}‖⋅‖{\ displaystyle \ | \ cdot \ |}τ∈[0,1[{\ displaystyle \ tau \ in \ left [0,1 \ right [}k1{\ displaystyle k_ {1}}

∀k⩾k1‖xk+1-x∗‖⩽τ‖xk-x∗‖{\ displaystyle \ forall k \ geqslant k_ {1} \ quad \ | x_ {k + 1} -x _ {*} \ | \ leqslant \ tau \ | x_ {k} -x _ {*} \ |}.

Portanto, é necessário que a norma do erro diminua estritamente a cada iteração de uma determinada iteração, com uma taxa de diminuição estritamente menor que 1. O escalar é chamado de taxa de convergência da sequência. Esta propriedade depende da escolha da norma que será utilizada para medir o erro, pois a estimativa acima pode ser verdadeira para uma norma e (apesar da equivalência das normas dimensionais finitas) não pode mais ser verificada com uma constante para outro padrão. τ{\ displaystyle \ tau}τ{\ displaystyle \ tau}τ<1{\ displaystyle \ tau <1}

O resultado a seguir relaciona a convergência linear ao número de dígitos significativos corretos da iteração. σk{\ displaystyle \ sigma _ {k}}

Convergência linear em termos de σk{\ displaystyle \ sigma _ {k}} -  A sequência converge linearmente para a norma se, e somente se, houver uma constante e um índice tal que (xk){\ displaystyle \ left (x_ {k} \ right)}x∗≠0{\ displaystyle x _ {*} \ neq 0}‖⋅‖{\ displaystyle \ | \ cdot \ |}σ>0{\ displaystyle \ sigma> 0}k1{\ displaystyle k_ {1}}

∀k⩾k1σk+1⩾σk+σ{\ displaystyle \ forall k \ geqslant k_ {1} \ quad \ sigma _ {k + 1} \ geqslant \ sigma _ {k} + \ sigma},

onde é definido com o padrão . σk{\ displaystyle \ sigma _ {k}}‖⋅‖{\ displaystyle \ | \ cdot \ |}

Exemplos de algoritmos que geram sequências linearmente convergentes

• o algoritmo de gradiente para minimizar uma função quadrática estritamente convexa. Esta não é uma boa velocidade de convergência para um algoritmo de otimização diferenciável;
• o método da dicotomia ou bissecção para encontrar um zero de uma função real de uma variável real.

Convergência Superlinear

Convergência superlinear  -  Dizemos que uma sequência converge superlinearly para si (xk){\ displaystyle \ left (x_ {k} \ right)}x∗{\ displaystyle x _ {*}}

a continuação tende para .(‖xk+1-x∗‖‖xk-x∗‖){\ displaystyle \ left ({\ frac {\ | x_ {k + 1} -x _ {*} \ |} {\ | x_ {k} -x _ {*} \ |}} \ right)}0{\ displaystyle 0}

Esta propriedade é independente da escolha do padrão. Claramente, qualquer sequência superlinearmente convergente converge linearmente.

O resultado a seguir relaciona a convergência superlinear ao número de dígitos significativos corretos das iterações. σk{\ displaystyle \ sigma _ {k}}

σk{\ displaystyle \ sigma _ {k}}Convergência superlinear em termos de  -  A sequência converge superlinearmente para a norma se, e somente se, (xk){\ displaystyle \ left (x_ {k} \ right)}x∗≠0{\ displaystyle x _ {*} \ neq 0}‖⋅‖{\ displaystyle \ | \ cdot \ |}

σk+1-σk→∞{\ displaystyle \ sigma _ {k + 1} - \ sigma _ {k} \ to \ infty},

onde é definido com o padrão . σk{\ displaystyle \ sigma _ {k}}‖⋅‖{\ displaystyle \ | \ cdot \ |}

Aqui está uma maneira de verificar numericamente a convergência superlinear de uma sequência por meio de uma função que desaparece no ponto limite.

Convergência superlinear em termos de uma função que desaparece no ponto limite  -  Seja um ponto e uma função tal que e tal que por perto de . Então, a sequência converge superlinearmente para a norma se, e somente se, x∗∈E{\ displaystyle x _ {*} \ in E}f:E→E{\ displaystyle f: E \ a E}f(x∗)=0{\ displaystyle f (x _ {*}) = 0}f(x)∼(x-x∗){\ displaystyle f (x) \, \ sim \, (x-x _ {*})}x{\ displaystyle x}x∗{\ displaystyle x _ {*}}(xk){\ displaystyle \ left (x_ {k} \ right)}x∗{\ displaystyle x _ {*}}‖⋅‖{\ displaystyle \ | \ cdot \ |}

registro⁡‖f(xk+1)‖-registro⁡‖f(xk)‖→-∞{\ displaystyle \ log \ | f (x_ {k + 1}) \ | - \ log \ | f (x_ {k}) \ | \ to - \ infty}.

Podemos dizer de outra forma: a sequência converge superlinearmente se, e somente se, a trama tiver um afim maior com uma inclinação negativa arbitrária. (xk){\ displaystyle \ left (x_ {k} \ right)}k↦registro⁡‖f(xk)‖{\ displaystyle k \ mapsto \ log \ | f (x_ {k}) \ |}

Exemplos de algoritmos que geram sequências convergentes superlineares

• os algoritmos quase-Newton para otimização ou para resolver um sistema de equações não lineares;
• o método de Müller para encontrar um zero de uma função real de uma variável real. Mais precisamente, sua ordem de convergência é 1,84.

Convergência quadrática

Convergência quadrática  -  Dizemos que uma sequência converge quadraticamente para si (xk){\ displaystyle \ left (x_ {k} \ right)}x∗{\ displaystyle x _ {*}}

o resto é aumentado(‖xk+1-x∗‖‖xk-x∗‖2){\ displaystyle \ left ({\ frac {\ | x_ {k + 1} -x _ {*} \ |} {\ | x_ {k} -x _ {*} \ | ^ {2}}} \ right )}

Claramente, qualquer sequência quadraticamente convergente converge superlinearmente.

O resultado a seguir relaciona a convergência quadrática ao número de dígitos significativos corretos das iterações. σk{\ displaystyle \ sigma _ {k}}

Convergência quadrática em termos de σk{\ displaystyle \ sigma _ {k}} -  A sequência converge quadraticamente para a norma se, e somente se, existe uma constante tal que (xk){\ displaystyle \ left (x_ {k} \ right)}x∗≠0{\ displaystyle x _ {*} \ neq 0}‖⋅‖{\ displaystyle \ | \ cdot \ |}VS{\ displaystyle C}

σk+1⩾2σk+VS{\ displaystyle \ sigma _ {k + 1} \ geqslant 2 \ sigma _ {k} + C},

onde é definido com o padrão . Nesse caso, σk{\ displaystyle \ sigma _ {k}}‖⋅‖{\ displaystyle \ | \ cdot \ |}

lim infk→∞σk+1σk⩾2{\ displaystyle \ liminf _ {k \ to \ infty} \; {\ frac {\ sigma _ {k + 1}} {\ sigma _ {k}}} \ geqslant 2}.

De forma pictórica, podemos expressar verbalmente a última desigualdade dizendo que uma sequência quadraticamente convergente tem elementos cujo número de dígitos significativos corretos dobra a cada iteração assintoticamente . É uma convergência muito rápida, pois se atinge muito rapidamente o número máximo de dígitos significativos que um determinado computador pode representar (15..16 para números em precisão dupla ). Portanto, raramente é útil ter sequências convergindo mais rapidamente. (xk){\ displaystyle \ left (x_ {k} \ right)}xk{\ displaystyle x_ {k}}

Aqui está uma maneira de verificar numericamente a convergência quadrática de uma sequência por meio de uma função que desaparece no ponto limite.

Convergência quadrática em termos de uma função que desaparece no ponto limite  -  Seja um ponto de e uma função tal que e tal que por perto de . Em seguida, a sequência converge quadraticamente para se, e somente se, existe uma constante tal que x∗{\ displaystyle x _ {*}}E{\ displaystyle E}f:E→E{\ displaystyle f: E \ a E}f(x∗)=0{\ displaystyle f (x _ {*}) = 0}f(x)∼(x-x∗){\ displaystyle f (x) \, \ sim \, (x-x _ {*})}x{\ displaystyle x}x∗{\ displaystyle x _ {*}}(xk){\ displaystyle \ left (x_ {k} \ right)}x∗{\ displaystyle x _ {*}}VS{\ displaystyle C}

registro⁡‖f(xk+1)‖⩽2registro⁡‖f(xk)‖+VS{\ displaystyle \ log \ | f (x_ {k + 1}) \ | \ leqslant 2 \ log \ | f (x_ {k}) \ | + C}.

Nesse caso,

lim infk→∞registro⁡‖f(xk+1)‖registro⁡‖f(xk)‖⩾2{\ displaystyle \ liminf _ {k \ to \ infty} \, {\ frac {\ log \ | f (x_ {k + 1}) \ |} {\ log \ | f (x_ {k}) \ |} } \ geqslant 2}. Exemplos de algoritmos que geram sequências convergentes quadraticamente

• a otimização do algoritmo de Newton ou para a resolução de um sistema de equações não lineares;
• o algoritmo Josephy-Newton para resolver uma inclusão funcional particular;
• o algoritmo semi-suave de Newton para resolver sistemas semi-suaves de equações.

Normalmente, são os algoritmos que procedem por linearização total ou parcial das equações / inclusões a serem resolvidas que geram sequências quadraticamente convergentes.

Bibliografia

(en) JM Ortega e WC Rheinboldt, Solução Iterativa de Equações Não Lineares em Várias Variáveis , Nova York, Academic Press ,1970( leia online )

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">