Résolution d'un système avec une mise à jour diagonale de petit rang

Supposons que j'ai le grand système linéaire clairsemé d'origine: . Maintenant, je n'ai pas A - 1 car A est trop grand pour factoriser ou toute sorte de décomposition de A , mais supposons que j'ai la solution x 0 trouvée avec une résolution itérative.$A\textbf{x}_0=\textbf{b}_0$$A^{-1}$$A$$\textbf{x}_0$

Maintenant, je souhaite appliquer une petite mise à jour de rang à la diagonale de A (changer quelques entrées diagonales): où D est une matrice diagonale avec principalement des 0 sur sa diagonale et quelques valeurs différentes de zéro. Si j'avais A - 1, je pourrais profiter de la formule de Woodbury pour appliquer une mise à jour à l'inverse. Cependant, je ne l'ai pas disponible. Y a-t-il quelque chose que je puisse faire à part simplement résoudre tout le système à nouveau? Existe-t-il un moyen de trouver un préconditionneur M qui soit facile \ plus facile à inverser, tel que M A 1$(A+D)\textbf{x}_1=\textbf{b}_0$$D$$A^{-1}$$M$ , de sorte que tout ce que j'aurais à faire si j'ai x 0 est d'appliquer M - 1 et qu'une méthode itérative converge en quelques / quelques itérations?$MA_1 \approx A_0$$\textbf{x}_0$$M^{-1}$

1. Enregistrez dans les colonnes de deux matrices et C tous les vecteurs b j auxquels vous avez appliqué la matrice dans les itérations précédentes et les résultats c j = A b j .$B$$C$$b_j$$c_j=Ab_j$

2. Pour chaque nouveau système (ou A x = b ′ , qui est le cas particulier D = 0 ), résoudre approximativement le système linéaire surdéterminé ( C + D B ) y ≈ b ′ , par exemple , en sélectionnant un sous-ensemble des lignes (éventuellement toutes) et en utilisant une méthode dense des moindres carrés. Notez que seule la partie sélectionnée de C + D B doit être assemblée; c'est donc une opération rapide!$(A+D)x'=b'$$Ax=b'$$D=0$$(C+DB)y\approx b'$$C+DB$

3. Mettez . Il s'agit d'une bonne approximation initiale avec laquelle commencer l'itération pour résoudre ( A + D ) x ′ = b ′ . Dans le cas où d'autres systèmes doivent être traités, utilisez les produits vectoriels matriciels dans cette nouvelle itération pour étendre les matrices B et C sur le sous-système résultant.$x_0=By$$(A+D)x'=b'$$B$$C$

$B$$C$$B$$B$$C$$x_0$$B$

Les lignes doivent être sélectionnées de manière à correspondre approximativement à une discrétisation grossière du problème complet. Prendre cinq fois plus de lignes que le nombre total de multiplications attendues des vecteurs matriciels devrait suffire.

$B$$C$$C=AB$$B$$x'$$x'$$x'=By$$y$$x'$$(C+DB)y= b'$$x_0=By=x'$

$x'$$B$$x'$

$(k+1)$$k$