CAMA : ma12 Méthodes itératives

Cours du 27 / 04

La simulation numérique

Pour faire cette image, on transforme des équations physique en systèmes matriciels ou les inconnues sont définies en chaque point d'un maillage a définir.

Dans ce cas l'inconnue est la pression et le maillage est une boîte imaginaire comprenant l'avion et l'air qui circule autour.
Si la boîte est un cube avec 1000 points dans chaque direction, on a 1 milliard de points et une matrice a 1 trillion d'éléments :

$$\left[\begin{array}{c}{a}_{11}{a}_{12}\dots a_{1,{10}^9}\\ a_{21}{a}_{22}\dots a_{2,{10}^9}\\ ⋮\\ a_{{10}^9,1}{a}_{n2}\dots a_{{10}^9,{10}^9}\end{array}\right]\left[\begin{array}{c}{p}_1\\ p_2\\ ⋮\\ p_{{10}^9}\end{array}\right]=\left[\begin{array}{c}{f}_1\\ f_2\\ ⋮\\ f_{{10}^9}\end{array}\right]$$
Cela prendrait 300 000 ans à inverser la matrice.

Inverser une matrice ou résoudre par une méthode directe n'est pas la bonne solution pour résoudre un grand système matriciel.

Méthodes itératives

Les méthodes itératives s'approchent pas à pas de la solution recherchée et permettent de trouver une approximation de

$\mathbf{x}$ dans

$A\mathbf{x}=b$.

On arrête le calcul lorsqu'on est à une distance choisie de la solution, appelée l'erreur.

On cherchera jamais à avoir une erreur plus petite que notre précision maximale.

On a une formule

${\mathbf{x}}^{t+1}=B{\mathbf{x}}^t+\mathbf{c}$ ou en Python:

x = np.random(size = c.size)
while np.square(x - old_x) > seuil:
    old_x = x
    x = B @ x + c

Si

$\mathbf{x}$ converge on a atteint un point fixe, c.a.d

${\mathbf{x}}^{t+1}={\mathbf{x}}^t$ et donc

$${\mathbf{x}}^t=B{\mathbf{x}}^t+\mathbf{c}\text{c.a.d.}(Id-B){\mathbf{x}}^t=\mathbf{c}$$

Méthode de Jacobi

La méthode de Jacobi découpe la matrice A en M et N avec

• $M$ : matrice diagonale des éléments de la diagonale de
  $A$
• $N=M-A$ (donc 0 sur la diagonale et l'opposé des éléments de
  $A$ ailleurs)

Le système à resoudre est

$(M-N)\mathbf{x}=\mathbf{b}$.

La formule iterative pour

$k+1$ est :

$$M{\mathbf{x}}^{k+1}=N{\mathbf{x}}^k+\mathbf{b}$$
Comme

$M$ est une matrice diagonale :

$$\begin{array}{l}{a}_{11}{x}_1^{k+1}=-a_{12}{x}_2^k-a_{13}{x}_3^k\dots -a_{1n}{x}_n^k+b_1\\ a_{22}{x}_2^{k+1}=-a_{21}{x}_1^k-a_{23}{x}_3^k\dots -a_{2n}{x}_n^k+b_2\\ a_{33}{x}_3^{k+1}=-a_{31}{x}_1^k-a_{32}{x}_3^k\dots -a_{3n}{x}_n^k+b_3\\ ⋮\\ a_{nn}{x}_n^{k+1}=-a_{n1}{x}_1^k-a_{n2}{x}_3^k\dots -a_{n-1,n-1}{x}_{n-1}^k+b_n\end{array}$$
Pour calculer

$x_i^{k+1}$ il faut diviser par

$a_{ii}$ donc il faut que

$A$ n'ait pas pas de zéro sur sa diagonale.

A = np.random.randint(10, size=(4,4))
b = A.sum(axis=1) # la solution est [1,1,1,1]

A:
 [[2 2 6 1]
 [3 9 6 1]
 [0 1 9 0]
 [0 9 3 4]] 
b:
 [11 19 10 16] 

M = np.diag(A)        # vecteur
N = np.diag(M) - A    # np.diag d'une matrice donne un vecteur, np.diag d'un vecteur donne une matrice

M:
 [[2 0 0 0]
 [0 9 0 0]
 [0 0 9 0]
 [0 0 0 4]]
N:
 [[ 0 -2 -6 -1]
 [-3  0 -6 -1]
 [ 0 -1  0  0]
 [ 0 -9 -3  0]]

x = np.random.random(4)
for i in range(20):
    x = (N @ x + b) / M

...
x_16 = [-4.194 -1.298  0.76  -4.026]
x_17 = [6.531 3.45  1.255 6.35 ]
x_18 = [-4.891 -1.608  0.728 -4.704]
x_19 = [7.277 3.779 1.29  7.073]

Ca ne converge pas.

2e essai :

A = np.random.randint(10, size=(4,4))
A = A + np.diag(A.sum(axis=0))
b = A.sum(axis=1) # la solution est [1,1,1,1]

A:
 [[24  2  4  8]
 [ 0 24  9  3]
 [ 4  6 16  5]
 [ 6  2  1 32]] 
b:
 [38 36 31 41] 

M = np.diag(A)        # vecteur
N = np.diag(M) - A    # np.diag d'une matrice donne un vecteur, np.diag d'un vecteur donne une matrice

M:
 [[24  0  0  0]
 [ 0 24  0  0]
 [ 0  0 16  0]
 [ 0  0  0 32]]
N:
 [[ 0 -2 -4 -8]
 [ 0  0 -9 -3]
 [-4 -6  0 -5]
 [-6 -2 -1  0]]

x = np.random.random(4)
for i in range(20):
    x = (N @ x + b) / M

...
x_17 = [1. 1. 1. 1.]
x_18 = [1. 1. 1. 1.]
x_19 = [1. 1. 1. 1.]

Pourquoi le 2e cas marche ?

Pour qu'une méthode itérative du type

$\mathbf{x}=B\mathbf{x}+\mathbf{c}$ converge il faut au choix :

• $\rho (B)<1$
  • $\rho$ : le rayon spectral (la plus grande valeur propre en valeur absolue)
• $||B||<1$ où :
  
  $$||B||=\underset{\mathbf{v}}{sup}\frac{||B\mathbf{v}||}{||\mathbf{\text{v}}||}=\underset{\mathbf{\text{v}}t.q.||\mathbf{\text{v}}||=1}{sup}||B\mathbf{v}||=\underset{\mathbf{\text{v}}t.q.||\mathbf{\text{v}}||\le 1}{sup}||B\mathbf{v}||$$

Cas de la méthode de Jacobi

• On respecte ces conditions si
  $A$ est a diagonale dominante, c.a.d. que chaque élément de la diagonale est plus grand que tous les autres de sa ligne et colonne.
• Jacobi converge aussi si
  $A$ est symétrique, réelle et définie positive (
  $\mathrm{\forall }\mathbf{x},{\mathbf{x}}^{T}A\mathbf{x}>0$).