Conditionnement (analyse numérique)

En analyse numérique, une discipline des mathématiques, le conditionnement mesure la dépendance de la solution d'un problème numérique par rapport aux données du problème, ceci afin de contrôler la validité d'une solution calculée par rapport à ces données. En effet, les données d'un problème numérique dépendent en général de mesures expérimentales et sont donc entachées d'erreurs.

Il s'agit le plus souvent d'une quantité numérique.

De façon plus générale, on peut dire que le conditionnement associé à un problème est une mesure de la difficulté de calcul numérique du problème. Un problème possédant un conditionnement bas est dit bien conditionné et un problème possédant un conditionnement élevé est dit mal conditionné.

Conditionnement d'un problème

Soit un problème $\mathrm {P} :\mathbb {R} ^{n}\rightarrow \mathbb {R}$. Soit aussi une variable perturbée ${\hat {x}}_{i}=x_{i}(1+\varepsilon _{i})$, avec $|\varepsilon _{i}|<\varepsilon$, où ε est la précision de la machine. Alors, la condition Modèle:Math du problème est le plus petit nombre tel que :

${\frac {|\mathrm {P} ({\hat {x}})-\mathrm {P} (x)|}{|\mathrm {P} (x)|}}\leqslant k\varepsilon +o(\varepsilon ).$

Le problème Modèle:Math est bien conditionné si Modèle:Math n'est pas très grand par rapport à $\varepsilon$. Sinon, ce problème P est mal conditionné.

Selon N. Higham, il semble que la notion de conditionnement ait été introduite par Alan Turing qui, par exemple, a défini le conditionnement d'une matrice carrée de taille n à partir de la norme de Frobenius par :

$\mathrm {C} (\mathrm {A} )={\frac {1}{n}}\cdot \|\mathrm {A} \|\cdot \|\mathrm {A} ^{-1}\|$

Conditionnement d'une matrice

Le conditionnement d'une matrice inversible Modèle:Math relativement à une norme subordonnée, notée $||\cdot ||$ est défini par la formule:

$\kappa (\mathrm {A} )=\Vert \mathrm {A} ^{-1}\Vert \,\Vert \mathrm {A} \Vert$.

Comme on suppose que la norme est subordonnée, le conditionnement est supérieur à 1 :

$\kappa (\mathrm {A} )\geqslant 1.$

Notons que la matrice vide 0 × 0 est son propre inverse et que sa norme est nulle quelle que soit la norme retenue. Son conditionnement est donc 0 selon cette définition. Certains définissent cependant cond()_{0 × 0} = 1 car l'application linéaire nulle a une précision parfaite (donc un score de 1) et cette matrice vide est une identité, les matrices unités ayant toutes un conditionnement de 1.

Pour le système linéaire Modèle:Math, où les données sont la matrice Modèle:Math et le vecteur du second membre Modèle:Math, le conditionnement donne une borne de l'erreur relative commise sur la solution Modèle:Math lorsque les données Modèle:Math ou Modèle:Math sont perturbées. Il peut s'avérer que cette borne soit très grande, de sorte que l'erreur qui pourrait en découler rende la solution numérique inexploitable.

Le conditionnement dépend de la norme utilisée. Pour la norme d'espace ℓ² , notée Modèle:Math, on a alors :

$\kappa (\mathrm {A} )={\frac {\sigma _{\max }(\mathrm {A} )}{\sigma _{\min }(\mathrm {A} )}}$

où Modèle:Math et Modèle:Math sont les valeurs singulières maximales et minimales de Modèle:Math. En conséquence :

• si Modèle:Math est normale, alors
  $\kappa (\mathrm {A} )={\frac {|\lambda _{\max }(\mathrm {A} )|}{|\lambda _{\min }(\mathrm {A} )|}}$
  où Modèle:Math et Modèle:Math sont les valeurs propres maximales et minimales de Modèle:Math ;
• si Modèle:Math est unitaire, alors
  $\kappa (\mathrm {A} )=1$.

Pour la norme d'espace ℓ^∞, notée Modèle:Math, si A est une matrice triangulaire inférieure non singulière (c'est-à-dire que Modèle:Math), alors :

$\kappa (\mathrm {A} )\geqslant {\frac {\max _{i}(|a_{ii}|)}{\min _{i}(|a_{ii}|)}}.$

Formules de majoration de l'erreur

Dans les formules suivantes, les calculs sont supposés faits avec une précision infinie, c'est-à-dire que les systèmes perturbés sont résolus de manière exacte.

On considère deux cas, selon que c'est le second membre Modèle:Math ou la matrice Modèle:Math qui n'est pas connu précisément.

Cas où le second membre varie

Le calcul effectif de l'inversion du système Modèle:Math, où la matrice Modèle:Math est connue avec précision et où la valeur du second membre Modèle:Math, supposé non nul, est entachée d'une erreur $\Delta b$, produira une erreur relative théorique $\|\Delta x\|/\|x\|$ sur la solution Modèle:Math majorée par

${\frac {\Vert \Delta x\Vert }{\Vert x\Vert }}\leqslant \kappa (\mathrm {A} ){\frac {\Vert \Delta b\Vert }{\Vert b\Vert }}$.

Cas où la matrice varie

Si la matrice Modèle:Math subit une modification de $\Delta \mathrm {A}$, on dispose d'une majoration de l'erreur par rapport au calcul avec la matrice exacte Modèle:Math donnée par

${\frac {\Vert \Delta x\Vert }{\Vert x+\Delta x\Vert }}\leqslant \kappa (\mathrm {A} ){\frac {\Vert \Delta \mathrm {A} \Vert }{\Vert \mathrm {A} \Vert }}$.

Un exemple de matrice mal conditionnée

Soit la matrice

$\mathrm {A} ={\begin{pmatrix}7&1&11&10\\2&6&5&2\\8&11&3&8\\6&9&3&6\\\end{pmatrix}}$,

et le vecteur

$b={\begin{pmatrix}29\\15\\30\\24\\\end{pmatrix}}$.

La résolution du système Modèle:Math donne

$x={\begin{pmatrix}1\\1\\1\\1\\\end{pmatrix}}$.

Si on substitue au second membre Modèle:Math le second membre perturbé

$b'=b+{\begin{pmatrix}0{,}1\\-0{,}1\\0{,}1\\-0{,}1\\\end{pmatrix}}={\begin{pmatrix}29{,}1\\14{,}9\\30{,}1\\23{,}9\\\end{pmatrix}}$,

la solution Modèle:Math correspondante sera

$x'=\mathrm {A} ^{-1}b'\simeq {\begin{pmatrix}6{,}222\\0{,}133\\1{,}633\\-3{,}256\\\end{pmatrix}}.$

Les erreurs relatives de Modèle:Math et Modèle:Math sont respectivement de 0,004 et 3,4108 ce qui représente une multiplication par environ 860 de l'erreur relative. Ce nombre est du même ordre que le conditionnement de la matrice Modèle:Math qui est de 1 425 (le conditionnement est pris relativement à la norme matricielle induite par la norme euclidienne sur $\mathbb {R} ^{4}$).

Annexes

Articles connexes

• Analyse numérique
• Erreur d'approximation
• Préconditionnement