Considérons avec presque singulier, ce qui signifie qu'il existe une valeur propre de qui est très petite. Le critère d'arrêt habituel d'une méthode itérative est basé sur le résiduel et concerne les itérations peuvent s'arrêter lorsque avec n le numéro d'itération. Mais dans le cas que nous considérons, il pourrait y avoir une grande erreur v vivant dans l'espace propre associé à la petite valeur propre \ lambda_0 qui donne une petite valeur résiduelle Av = \ lambda_0v . Supposons que le r_0 résiduel initial soit grand, alors il pourrait arriver que nous nous arrêtions à mais l'erreur est toujours importante. Quel est un meilleur indicateur d'erreur dans ce cas? Est un bon candidat?
linear-algebra
Hui Zhang
la source
la source
Réponses:
Veuillez ne jamais utiliser la différence entre les itérations successives pour définir un critère d'arrêt. Cette erreur diagnostique la stagnation de la convergence. La plupart des itérations matricielles non symétriques ne sont pas monotones, et même GMRES en arithmétique exacte sans redémarrage peut stagner pendant un nombre arbitraire d'itérations (jusqu'à la dimension de la matrice) avant de converger soudainement. Voir des exemples dans Nachtigal, Reddy et Trefethen (1993) .
Une meilleure façon de définir la convergence
Nous nous intéressons généralement à la précision de notre solution plus qu'à la taille du résidu. Plus précisément, nous pourrions garantir que la différence entre une solution approximative et la solution exacte x satisfait | x n - x | < c pour certains c spécifiés par l'utilisateur . Il s'avère que cela peut être réalisé en trouvant un x n tel que | A x n - b | < c ϵ où ϵ est la plus petite valeur singulière de A , en raison dexn x
où nous avons utilisé que est la plus grande valeur singulière de A - 1 (deuxième ligne) et que x résout exactement A x = b (troisième ligne).1/ϵ A−1 x Ax=b
Estimation de la plus petite valeur singulièreϵ
Une estimation précise de la plus petite valeur singulière n'est généralement pas directement disponible à partir du problème, mais elle peut être estimée comme un sous-produit d'un gradient conjugué ou d'une itération GMRES. Notez que bien que les estimations des plus grandes valeurs propres et valeurs singulières soient généralement assez bonnes après seulement quelques itérations, une estimation précise de la plus petite valeur propre / singulière n'est généralement obtenue qu'une fois la convergence atteinte. Avant la convergence, l'estimation sera généralement nettement supérieure à la valeur réelle. Cela suggère que vous devez réellement résoudre les équations avant de pouvoir définir la bonne tolérance c ϵ . Une tolérance de convergence automatique qui prend une précision fournie par l'utilisateur cϵ cϵ c pour la solution et estime que la plus petite valeur singulière avec l'état actuel de la méthode de Krylov pourrait converger trop tôt car l'estimation de ϵ était beaucoup plus grande que la valeur réelle.ϵ ϵ
Remarques
-ksp_monitor_singular_value
de n'importe quel programme PETSc. Voir KSPComputeExtremeSingularValues () pour calculer des valeurs singulières à partir du code.-ksp_gmres_restart 1000
dans PETSc).la source
Une autre façon de voir ce problème est de considérer les outils à partir de problèmes inverses discrets, c'est-à-dire des problèmes qui impliquent la résolution de ou min | | A x - b | | 2 où A est très mal conditionné (ie le rapport entre la première et la dernière valeur singulière σ 1 / σ n est grand).Ax=b min||Ax−b||2 A σ1/σn
Ici, nous avons plusieurs méthodes pour choisir le critère d'arrêt, et pour une méthode itérative, je recommanderais le critère de la courbe en L car il n'implique que des quantités qui sont déjà disponibles il). J'ai utilisé cela avec succès dans une méthode itérative.
L'idée est de surveiller la norme résiduelle et la norme de solution η k = | | x k | | 2 , où x k est le k -ième itération. Au fur et à mesure que vous itérez, cela commence à dessiner la forme d'un L dans un graphique loglog (rho, eta), et le point au coin de ce L est le choix optimal.ρk=||Axk−b||2 ηk=||xk||2 xk k
Cela vous permet d'implémenter un critère où vous gardez un œil lorsque vous avez franchi le coin (c'est-à-dire en regardant le gradient de ), puis choisissez l'itération qui était située au coin.(ρk,ηk)
La façon dont je l'ai fait impliquait de stocker les 20 derniers itérations, et si le gradient était supérieur à un certain seuil pour 20 itérations successives, je savais que j'étais sur la partie verticale de la courbe et que j'avais dépassé le coin. J'ai ensuite pris la première itération de mon tableau (c'est-à-dire celle d'il y a 20 itérations) comme solution.abs(log(ηk)−log(ηk−1)log(ρk)−log(ρk−1))
Il existe également des méthodes plus détaillées pour trouver le coin, et elles fonctionnent mieux mais nécessitent de stocker un nombre important d'itérations. Jouez un peu avec. Si vous êtes dans matlab, vous pouvez utiliser la boîte à outils Outils de régularisation, qui implémente une partie de cela (en particulier la fonction "coin" est applicable).
Notez que cette approche est particulièrement adaptée aux problèmes à grande échelle, car le temps de calcul supplémentaire impliqué est minuscule.
la source