Lien de la note Hackmd
Cours du 27 / 04
Soit la matrice symétrique $A$ suivante :
1
| A = np.array([[10, 7, 8, 7], [7, 5, 6, 5], [8, 6, 10, 9], [7, 5, 9, 10]])
|
1
2
3
4
| array([[10, 7, 8, 7],
[ 7, 5, 6, 5],
[ 8, 6, 10, 9],
[ 7, 5, 9, 10]])
|
1
| lin.det(A) # calcul son determinant
|
1
| 0.9999999999999869 # on peut arrondir a 1
|
Construisons $b$ tel que $A{\bf x} = b$ et $\bf x = [1,1,1,1]$
1
| array([1., 1., 1., 1.])
|
Perturbons $b$, comme s’il y avait une erreur de mesure ou d’arrondi.
1
2
3
| bp = [32.1, 22.9, 33.1, 30.9]
eb = lin.norm(b - bp) / lin.norm(b)
# une erreur se mesure par rapport à la valeur de la donnée
|
On a une erreur de l’ordre de $0,3\%$.
On note l’erreur : \(\frac{||{\bf \delta b}||}{||{\bf b}||}\)
Regardons la solution ${\bf x}$ de notre système matriciel perturbé:
1
| array([ 9.2, -12.6, 4.5, -1.1])
|
La solution n’a rien n’a voir avec $[1,1,1,1]$
1
| ex = lin.norm(x - xp) / lin.norm(x) #mesure de l'erreur
|
L’erreur est de l’ordre de 8.
C’est $2460$ fois plus que l’erreur sur $b$.
Pourquoi ?
\(\begin{aligned} A ({\bf x} + {\bf \delta x}) &= {\bf b} + {\bf \delta b} \quad \textrm{et donc} \\ A \, {\bf \delta x} &= {\bf \delta b} \; \textrm{ puisque } A {\bf x} = {\bf b} \quad \textrm{et finalement}\\ {\bf \delta x} &= A^{-1} \, {\bf \delta b} \end{aligned}\) Comme $A$ et son inverse sont des applications linéaires :
\[||{\bf b}|| \le ||A|| \, ||{\bf x}|| \quad \textrm{et} \quad ||{\bf \delta x}|| \le ||A^{-1}|| \, ||{\bf \delta b}||\]
donc :
\[\frac{||{\bf \delta x}||}{||{\bf x}||} \le ||A^{-1}|| \, \frac{||{\bf \delta b}||}{||{\bf x}||} \le ||A^{-1}|| \, ||A|| \, \frac{||{\bf \delta b}||}{||{\bf b}||}\]
1
| lin.norm(lin.inv(A)) * lin.norm(A)
|
On appelle cela le conditionnement de $A$ : \(cond(A) = ||A^{-1}|| \, ||A||\) Une matrice mal conditionnée va générer des erreurs de calcul lors de la résolution du système matriciel.
1
| np.linalg.cond(A) # scipy n'a pas le conditionnement mais numpy l'a.
|
1
| 2984.0927016757555 # different de 3009
|
Perturbons la matrice
1
2
3
| np.random.seed(0)
dA = 2 * np.random.random(size = A.shape) - 1
|
1
2
3
4
| array([[ 0.098, 0.43 , 0.206, 0.09 ],
[-0.153, 0.292, -0.125, 0.784],
[ 0.927, -0.233, 0.583, 0.058],
[ 0.136, 0.851, -0.858, -0.826]])
|
1
| ea = lin.norm(dA) / lin.norm(A) # erreur relative sur A
|
1
2
3
4
5
| array([[10.098, 7.43 , 8.206, 7.09 ],
[ 6.847, 5.292, 5.875, 5.784],
[ 8.927, 5.767, 10.583, 9.058],
[ 7.136, 5.851, 8.142, 9.174]])
|
1
| array([-12.365, 15.574, 10.146, -5.94 ])
|
1
| ex = lin.norm(xp - x) / lin.norm(x)
|
1
| ex / ea # valeur de l'erreur
|
L'erreur est moins grande.
Une erreur peut fortement perturber $A$, le conditionnement et l’erreur sont tous les deux importants.
Pour retrouver le conditionnement de $A$ dans ce cas : \(\begin{align} & (A + \Delta A) \, ({\bf x} + {\bf \delta x}) = {\bf b} \quad \textrm{et donc} \\ & A \, {\bf \delta x} + \Delta A \, ({\bf x} + {\bf \delta x}) = 0 \; \textrm{ puisque } A {\bf x} = {\bf b} \quad \textrm{et finalement}\\ & {\bf \delta x} = -A^{-1} \,\Delta A \, ({\bf x} + {\bf \delta x}) \quad \textrm{et} \\ & ||{\bf \delta x}|| \le ||A^{-1}|| \, ||\Delta A|| \, ||{\bf x} + {\bf \delta x}|| \end{align}\) Donc \(\begin{align} \frac{||{\bf \delta x}||}{||{\bf x} + {\bf \delta x}||} \le ||A^{-1}|| \, ||\Delta A|| = ||A^{-1}|| \, ||A|| \, \frac{||\Delta A||}{||A||} \end{align}\) et \(\begin{align} \frac{||{\bf \delta x}||}{||{\bf x} + {\bf \delta x}||} \le cond(A) \, \frac{||\Delta A||}{||A||} \end{align}\)
Propriétés
| $cond(A) \ge 1$ car $Id = A\, A^{-1}$ et donc $1 \le | | A | | \, | | A^{-1} | | $ |
- $cond(A) = cond(A^{-1})$
| $\displaystyle cond_2(A) = \frac{\max_i | \lambda_i | }{\min_i | \lambda_i | }$ si la matrice est réelle |
- 2 indique qu’on utilise la norme 2
- $\lambda_i$ sont les valeurs propres de A
1
2
| vp = lin.eigvals(A)
vp.max() / vp.min()
|
- si A est unitaire ou orthogonale : $cond_2(A) = 1$
- le conditionnement n’est pas modifié par transformation unitaire
Préconditionnement
Le conditionnement peut etre tranformé :
\(\forall A, \exists B \; \textrm{appelée matrice de préconditionnement t.q.} \quad cond(B\, A) < cond(A)\)
On résoud $B\, A {\bf x} = B\, {\bf b}$.
