Quels sont les symptômes d'un mauvais conditionnement lors de l'utilisation de méthodes directes?

Supposons que nous ayons un système linéaire et que nous ne sachions rien de son conditionnement et que nous n'ayons aucune information préliminaire sur la solution. Nous appliquons aveuglément l'élimination gaussienne et obtenons une solution . Est-il possible de déterminer si cette solution est fiable (c'est-à-dire que le système est bien conditionné) sans une analyse préalable approfondie de la matrice ? L'ampleur des pivots donne-t-elle des informations fiables? $x$

Et généralement, quelles sont les principales lignes directrices pour détecter les mauvais conditionnements "à la volée"?

linear-solver condition-number conditioning faleichik
la source

Réponses:

Quand une matrice est-elle mal conditionnée ? Cela dépend de la précision de la solution que vous recherchez, autant que "la beauté est dans l'œil du spectateur" ...

Peut-être votre question devrait-elle être mieux reformulée, car existe-t-il des estimateurs de nombre de conditions bon marché et robustes basés sur la factorisation ? $LU$

En supposant que vous êtes intéressé par le vrai problème général (dense, non symétrique) en arithmétique double précision, je vous suggère d'utiliser le solveur expert LAPACK DGESVX qui fournit une estimation de condition sous la forme de son réciproque, . En prime, vous avez également d'autres avantages comme l'équilibrage / équilibrage d'équations, le raffinement itératif, les limites d'erreur avant et arrière. Soit dit en passant, un mauvais conditionnement pathologique ( ) est signalé comme une erreur par . $\text{RCOND}\approx 1/\kappa(A)$ $\kappa(A) > 1/\epsilon$ INFO>0

Pour aller plus loin, LAPACK estime le nombre de conditions dans la norme 1 (ou normale si vous résolvez ) via DGECON . L'algorithme sous-jacent est décrit dans la pelouse 36: "Résolutions triangulaires robustes pour une utilisation dans l'estimation de la condition" . $\infty$ $A^T x = b$

Je dois avouer que je ne suis pas un expert dans le domaine, mais ma philosophie est: "si c'est assez bon pour LAPACK, c'est pour moi".

Stefano M
la source

La solution d'un système d'équations mal conditionné avec une matrice de norme 1 un côté aléatoire aléatoire de la norme 1 aura avec une forte probabilité une norme de l'ordre du nombre de conditions. Ainsi, le calcul de quelques-unes de ces solutions vous dira ce qui se passe.

Arnold Neumaier
la source

C'est en effet ce que fait DGECON, avec la finesse supplémentaire d'affiner itérativement la direction de recherche afin de maximiser le résultat, et d'utiliser un solveur triangulaire personnalisé (pas les BLAS) afin de ne pas fausser les choses par des erreurs d'approximation. Le coût de calcul de DGECON est donc comparable à votre simple test. +1 pour nous souvenir de la signification simple des normes matricielles et du numéro de condition. Il devrait être intéressant de savoir si DGECON est vraiment plus robuste qu'un simple contrôle aléatoire.

Stefano M

Tenant compte du fait que le nombre de conditions de résolution

coïncide avec le nombre de conditions de calcul

suffit-il simplement de multiplier la matrice mise à l'échelle avec ces vecteurs aléatoires au lieu de résoudre réellement

A x = b

$Ax=b$

A x

$Ax$

A x = b

$Ax=b$

faleichik

@faleichik Bien sûr que non: l'astuce ici est de mettre à l'échelle

telle sorte que

. Bien sûr, étant cette algèbre linéaire, vous n'avez pas à mettre à l'échelle

mais seulement

... néanmoins vous devez d'abord calculer

. Votre argument inverse nécessiterait de calculer d'abord

A

$A$

‖ A ‖ = 1

$\| A \| = 1$

κ (A) = ‖ A ‖ \cdot ‖ A^{- 1} ‖ = ‖ A^{- 1} ‖

$\kappa(A) = \| A \| \cdot \| A^{-1} \| = \| A^{-1} \|$

A

$A$

A x

$Ax$

‖ A ‖

$\| A \|$

‖ A^{- 1} ‖

$\| A^{-1} \|$ ce que nous nous efforçons d'évaluer.

Stefano M

Il est presque impossible de dire si votre système est mal conditionné à partir d'un seul résultat. À moins que vous ayez une certaine prévoyance sur le comportement de votre système (c.-à-d. Que vous sachiez quelle solution DEVRAIT être), vous ne pouvez pas dire grand-chose d'une solution unique.

Cela dit, vous pouvez obtenir plus d' informations si vous résolvez plus d'un système avec le même . Supposons que vous ayez un système de la forme . Pour un A spécifique dont vous n'avez aucune connaissance préalable sur son conditionnement, vous pouvez effectuer le test suivant: $A$ $Ax=b$

Résoudre pour un vecteur spécifique du côté droit . $Ax=b$ $b$
Perturbez votre vecteur de droite par où est très petit par rapport à . $b_{new}=b+\mathbf{\varepsilon}$ $||\mathbf{\epsilon}||$ $||b||$
Résoudre . $Ax_{new}=b_{new}$
Si votre système est bien conditionné, votre nouvelle solution doit être assez proche de votre ancienne solution (ie doit être petite). Si vous observez un changement radical de votre nouvelle solution (c'est-à-dire est grand), alors votre système est probablement mal conditionné. $||x-x_{new}||$ $||x-x_{new}||$

Vous devrez peut-être résoudre plusieurs systèmes linéaires avec différents vecteurs du côté droit pour vous donner une meilleure indication si le système est mal conditionné. Bien sûr, ce processus est un peu cher (opérations pour la première solution et opérations pour chaque solution successive, en supposant que votre solveur direct enregistre ses facteurs). Si votre matrice A est assez petite, ce n'est pas un problème. S'il est grand, vous ne voudrez peut-être pas le faire. Au lieu de cela, vous feriez mieux de calculer le numéro de condition $\Theta(n^3)$ $\Theta(n^2)$ dans une norme pratique. $||A||\cdot||A^{-1}||$

Paul
la source

Θ (k n^{3})

$\Theta(kn^3)$

A

$A$

A

$A$

O (n^{3})

$O(n^3)$

O (n^{2})

$O(n^2)$

@JackPoulson: Vous avez absolument raison ... Je suppose que je me suis complètement écarté. Pas de soucis :) Je mettrai à jour ma réponse

Paul

Pourrait-on également évaluer le résidu de la résolution résultante? Puisque

| | UNE X - b | |

$||Ax - b ||$ échelles comme

| | UNE | | \cdot | | X | |

$||A||\cdot||x||$ un presque singulier

A

$A$ pourrait donner un résidu significatif même si sa solution est très mauvaise.

Reid.Atcheson

@ Reid.Atcheson: Pas vraiment. La solution approximative à un système mal conditionné peut encore produire un petit résidu. Cela ne vous donne pas vraiment d'indication sur la distance à laquelle il est éloigné de la vraie solution.

Paul

Il est peut-être plus sage de déclarer explicitement

‖ ε ‖

$\|\varepsilon\|$ très petit par rapport à

‖ b ‖

$\|b\|$ . Tout est relatif dans ce domaine ... La plupart des lecteurs le sauront, mais quelqu'un pourrait être induit en erreur dans des eaux dangereuses.

Stefano M