Suposições iniciais para sistemas lineares perturbados

8

Suponha que você resolva um sistema linear por um método iterativo, por exemplo, gradientes conjugados ou iteração de Richardson. Então você tenta resolver um sistema linear que é ligeiramente perturbado na matriz e no lado direito, digamos, .˜ A ˜ u = ˜ fAu=fA~u~=f~

Faz sentido usar a solução antiga como valor inicial para o método iterativo? "Faz sentido" significa que há um ganho confiável no tempo de execução do método iterativo. Eu me pergunto se isso leva a uma melhoria em geral, de forma que possa ser considerada uma prática recomendada.u~0=u

Um aplicativo que tenho em mente vem de elementos finitos adaptativos. Se computamos uma solução em uma grade grosseira e queremos encontrar uma solução em uma grade mais fina (que pode ter sido gerada com base em um método adaptativo), o valor inicial de qualquer algoritmo iterativo pode ser o prolongamento de na grade mais fina. Da mesma forma, o método Newton ou a iteração Picard, que está envolvida na solução de problemas não-lineares, poderia ser "impulsionado" dessa maneira, se fizer algum sentido.~ u uuu~u

linear-algebra finite-element linear-solver shuhalo
fonte
1
Pelo menos do ponto de vista teórico, reciclar uma solução em uma grade grossa como um valor inicial em uma grade fina gera um erro inicial limitado que cresce cada vez menor à medida que a malha é (uniformemente) refinada, enquanto como um valor inicial leva a um erro inicial cada vez maior. Portanto, estimativas de erro muito básicas sugerem que faz uma tremenda diferença. - Então, para mim, ainda me pergunto se isso é feito na prática. Em muitas comunidades, isso não é padrão. 0
shuhalo

Respostas:

5

Tentamos isso com elementos finitos adaptativos, onde levamos a solução anterior para a nova malha por interpolação. Acontece que começar com esse vetor não tem efeito perceptível no número de iterações de CG. Em outras palavras, para a iteração de CG, um bom palpite inicial é praticamente inútil.

Obviamente, a situação é totalmente diferente para métodos não lineares (como o método de Newton), onde vale a pena fazer a última iteração na malha grossa como o palpite inicial para a malha fina. Na prática, costuma-se fazer de 5 a 10 iterações na malha mais grossa, mas depois é necessário apenas 1-2 iterações em cada malha sucessivamente refinada.

Wolfgang Bangerth
fonte
4

Eu acho que realmente depende do número de condição da matriz A. Se ele tem um número de condição grande, perturbar o sistema levemente pode produzir uma solução radicalmente diferente. Para o Adaptive FEM, depende do que você espera que o comportamento do sistema seja (e, obviamente, da qualidade da própria malha). Se você espera uma transição razoavelmente suave da grade grossa para a fina, devemos esperar que o sistema perturbado tenha uma solução bastante próxima do sistema imperturbado. Se você pode esperar mudanças dramáticas repentinas, não há garantia real da proximidade dos sistemas perturbados e imperturbáveis.

Paulo
fonte
1
Boa maneira de pensar sobre isso! Há algum valor em pensar sobre como parece também. (A−A~)(f−f~)
precisa saber é