O número da condição da matriz afeta a precisão dos solucionadores lineares iterativos?

8

Eu tenho uma pergunta bastante específica em relação ao número da condição. Eu corro simulações FEM que possuem várias escalas de comprimento, o que resulta em uma enorme disparidade entre as entradas maiores e as menores da minha matriz. O número da condição pode chegar a 10 ^ 15 em algumas circunstâncias.

Na análise numérica, vejo frequentemente o erro associado ao número da condição, que se aplica ao erro na solução computada usando métodos diretos. Minha curiosidade é se essa lógica se aplica ao erro em um solucionador de tipo iterativo como CG ou GMRES também. Sei que a taxa de convergência é impactada pelos valores próprios da matriz e noto enormes perdas de velocidade ao executar problemas desse tipo. Mas não tenho certeza quanto à precisão. Qualquer ajuda seria apreciada.

linear-algebra numerical-analysis linear-solver CraigJ
fonte
é possível reduzir o número da sua condição refinando a malha?
Nathanielng
Pode ser a minha falta de entendimento do FEM. Mas, nos problemas de modelagem em várias escalas, o volume do meu maior elemento para o menor é de 10 ^ 10. Eu sei que esses parâmetros vão para as entradas da matriz. O que eu não sei é se esse tipo de coisa é explicado nos solucionadores lineares do FEM (mas não sei como seria, e foi por isso que fiz a pergunta). Portanto, para responder à sua pergunta, a malha é refinada, pois todos os elementos têm qualidade aceitável, mas os tamanhos díspares dos elementos me levaram a estimar que meu número de condição estaria nessa ordem.
CraigJ

Respostas:

13

O mau condicionamento é uma característica do sistema de equações, não do algoritmo usado para resolver o sistema de equações. Se seus sistemas estiverem muito condicionados ( ), você poderá esperar que a solução seja extremamente sensível a qualquer perturbação nos dados do problema, mesmo que a solução seja feita com precisão extremamente alta (por exemplo, 500 dígitos ) aritmética usando fatoração direta. 1015

É improvável que seu método iterativo converja para uma solução em qualquer período de tempo razoável. Mesmo se você estivesse disposto a esperar por séculos, a solução obtida ainda seria extremamente sensível a qualquer perturbação nos dados do problema.

Brian Borchers
fonte
Então, se eu tiver um parâmetro com uma variabilidade de 5 a 10% que influencie os valores na matriz, essa incerteza será ampliada muitas vezes, independentemente do tipo de método da solução? Obrigado, apenas pedindo um pouco de esclarecimento.
CraigJ
1
Sim, se seus dados tiverem de 5 a 10% de precisão e você tiver esse sistema muito condicionado, você estará em apuros. Você realmente precisa considerar algum tipo de regularização.
Brian Borchers
Isto é interessante. Se meus tamanhos de elemento são aproximadamente os mesmos, mas eu tenho matrizes mal condicionadas devido ao dimensionamento de cada kernel em nosso PDE, você menciona a regularização, alguma sugestão sobre como resolver isso? Por exemplo, uma versão relativamente pequena do nosso problema: -pc_svd_monitor no PETSc revelou algo como 540/620 com ordem valores singulares quase zero. Nós redimensionamos os kernels com a escala de comprimento e reduzimos esse problema para cerca de 280/620 valores singulares próximos a zero. O problema é que os maiores valores singulares ainda estão na ordem ou mais e o problema não está convergindo. 10-201012
John M
7

Deveríamos ser mais precisos aqui. A estimativa mais simples que você pode dar é que para que, se você encerrar sua iteração usando o resíduo, possa estar desabilitado por um fator de, para o resíduo relativo de para que você tenha uma estimativa simples de quantos dígitos está perdendo

||x∗-x||=||UMA-1UMA(x∗-x)||≤||UMA-1||||b-UMAx||
||UMA-1||
κ(UMA)=||UMA||||UMA-1||
registro⁡κ.
Matt Knepley
fonte