Qual é a pior complexidade do Gradiente Conjugado?

9

Seja ARn×n , simétrico e positivo definido. Suponhamos que leva m unidades de trabalho para multiplicar um vector por A . É sabido que a execução do algoritmo CG em A com o número de condição κ requer O(mκ), unidades de trabalho.

Agora, é claro, sendo uma declaração O , esse é um limite superior. E o algoritmo de CG pode sempre terminar em zero etapas com um palpite inicial de sorte.

Sabemos se existe um RHS e um palpite inicial (infeliz) que exigirá Θ(κ)etapas? Em outras palavras, a pior complexidade de trabalho do CG é realmenteΘ(mκ)?

Essa questão surge quando tentei determinar se o benefício de um pré-condicionador ( inferior κ) superava seu custo ( superior m). No momento, estou trabalhando com problemas de brinquedo e gostaria de ter uma idéia melhor antes de implementar qualquer coisa em uma linguagem compilada.

fred
fonte
5
Presumivelmente, você poderia construir um palpite inicial pessimal, executando o algoritmo de CG "para trás" e colocando energia adequada em cada direções de pesquisa A- horizontais que o algoritmo requer todas as etapas. A
origimbo

Respostas:

9

A resposta é um sim retumbante. A taxa de convergência vinculada de é nítido sobre o conjunto de matrizes definidas positivas simétricas com número de condição(κ1)/(κ+1) . Em outras palavras, sabendo nada mais sobre A que seu número de condição, o CG realmente pode assumirκAiterações k para convergir. Em termos gerais, o limite superior é atingido se os valores próprios deAforem distribuídos uniformemente (isto é, "salpicados") dentro de um intervalo do número de condiçãoκ.κAκ

Aqui está uma declaração mais rigorosa. As versões determinísticas estão mais envolvidas, mas funcionam usando os mesmos princípios.

Teorema (pior opção de ). Escolher qualquer matriz ortogonal aleatório L , deixar λ 1 , ... , λ n ser n números reais uniformemente amostrados a partir do intervalo verdadeira [ 1 , κ ] , e deixou b = [ b 1 ; ... ; b n ] sejam n números reais amostrados iid do gaussiano padrão. Defina A = U d i a g ( λ 1 ,AUλ1,,λnn[1,κ]b=[b1;;bn]nEm seguida, no limite n , gradientes conjugados vai convergência com uma probabilidade para uma ε solução precisa de um x = b em não menos do que Ω (

A=Udiag(λ1,,λn)UT.
nϵAx=biterações.Ω(κlogϵ1)

Prova. A prova padrão é baseada em aproximações polinomiais ótimas de Chebyshev, usando técnicas encontradas em vários locais, como o livro de Greenbaum ou o livro de Saad .

Richard Zhang
fonte
11
O limite não é nítido, como a resposta explica mais adiante: se os autovalores não forem distribuídos uniformemente, cg converge mais rapidamente, pois não é uma iteração estática. Portanto, precisamos saber mais sobre a matriz.
Guido Kanschat
@GuidoKanschat: Bom ponto, e eu corrigi a declaração para esclarecer que a nitidez é alcançada em todos os com a condição κ . Aκ
Richard Zhang
A prova se resume a minimizar no espaço de polinômios de ordem k que satisfazem p ( 0 ) = 1 . Equivalentemente, isto é min p max λ Λ ( A ) | p ( λ ) | . No limite estabelecido, Λ ( A ) [ 1 , κ ]__p(UMA)__kp(0 0)=1 1minpmaxλΛ(A)|p(λ)|Λ(A)[1,κ] , e a solução para o problema minimax é o polinômio de Chebyshev, cujo erro converge como κ
Richard Zhang
0

Tomando isso como minha pergunta original: sabemos se existe um RHS e um palpite inicial (sem sorte) que exigirá etapas?Θ(κ)

A resposta para a pergunta é "não". A idéia desta resposta vem do comentário de Guido Kanschat.

Reivindicação: Para qualquer condição número , existe uma matrizk , com esse número de condição para o qual o algoritmo CG terminará em no máximo duas etapas (para qualquer RHS dado e estimativa inicial).A

Considere onde A = d i a g ( 1 , κ , κ , , κ ) . Então o número da condição de A é κ . Seja b R n o RHS e denote os autovalores de A como λ i onde λ i = { 1 i = 1 k i 1 .ARn×nA=diag(1,κ,κ,,κ)AκbRnAλi

λi={1i=1κi1.

Nós primeiro considerar o caso em que , a estimativa inicial, é zero. Denuncie x ( 2 )R n como a segunda estimativa de A - 1 b do algoritmo CG. Mostramos que x ( 2 ) = A - 1 b , mostrando x ( 2 ) - A - 1 b , A ( x ( 2 ) - Umx(0)Rnx(2)RnA1bx(2)=A1b . De fato, temosx(2)A1b,A(x(2)A1b)=0

x(2)A1b,A(x(2)A1b)=x(2)A1bA2=minppoly1(p(A)A1)bA2=minppoly1i=1n(p(λi)λi1)2λibi2i=1n(p^(λi)λi1)2λibi2=0

p^p^(x)=(1+κx)/κ. So we proven the case for x(0)=0.

If x(0)0, then x(2)=x(2)¯+x(0) where x(2)¯ is the second estimate of the CG algorithm with b replaced with b¯=bAx(0). So we have reduced this case to the previous one.

fred
fonte
How much of this is robust to finite precision arithmetic?
origimbo
@origimbo If your question was directed to me, the answer is, "I don't know."
fred