Méthode de relaxation
La méthode de relaxation est une méthode itérative (utilisant des suites) pour résoudre les systèmes linéaires $Ax=b$, où $A$ est une matrice $n\times n$ et $x,b$ sont des vecteurs de $\mathbb R^n$. Elle consiste en la manipulation suivante : on décompose $A$ comme $A=D-E-F$, où $D$ est une matrice diagonale, $-E$ est une matrice triangulaire inférieure, et $-F$ est une matrice triangulaire supérieure : $$M=\begin{pmatrix} &\\ &&&&-F\\ &&D&&\\ -E&&&&\\ &&&&\\ \end{pmatrix} $$ Soit aussi $\omega$ un nombre réel non nul, appelé paramètre de la méthode de relaxation. La méthode de relaxation consiste à écrire le système sous la forme \begin{align*} Ax=b&\iff \left(\frac 1\omega D-E\right)x+\left(\frac{\omega-1}{\omega}D-F\right)x=b\\ &\iff \left(\frac 1\omega D-E\right)x=\left(\frac{1-\omega}{\omega}D+F\right)x+b. \end{align*} puis à définir une suite de vecteurs $(x^k)$ par la formule $$\left(\frac 1\omega D-E\right)x^{k+1}=\left(\frac{1-\omega}\omega D+F\right)x^k+b.$$ On espère alors que la suite $(x^k)$ converge vers une solution de $Ax=b$. Sous de bonnes hypothèses concernant la matrice $A$ et le réel $\omega$, c'est effectivement le cas. Par exemple, si $A$ est tridiagonale et définie positive, et si $0<\omega<2$, alors la suite $(x^k)$ converge effectivement vers l'unique solution de $Ax=b$.
Lorsque $\omega=1$, on retrouve la méthode de Gauss-Seidel.
On peut généraliser cette méthode à la minimisation d'une fonction convexe $f:\mathbb R^n\to\mathbb R$. On définit une suite $(x^k)$ en choisissant un premier terme $x^0\in\mathbb R^n$ et en posant $$x^{k+1}=x^k-\rho_k d_k$$ où $\rho_k$ est tel que $$f(x^k-\rho_k d_k)=\inf_{\rho\in\mathbb R}f(x^k-\rho d_k)$$ et les directions de descente $d_k$ sont les vecteurs successifs de la base canonique ($d_1=e_1$, $d_2=e_2$, ... , $d_n=e_{n}$, $d_{n+1}=e_{1}$, ...). Il s'agit donc d'une méthode de descente particulière. Lorsque $f$ est $\alpha$-convexe, c'est-à-dire lorsque $$\exists \alpha>0,\ \forall (x,y)\in\mathbb R^n,\ f(tx+(1-t)y)\leq tf(x)+(1-t)f(y)-\alpha t(1-t)\|x-y\|^2.$$ alors on peut démontrer que la suite $(x^{k})$ converge vers l'unique minimum de $f$.
Cette méthode de relaxation est liée à la méthode précédente en posant $$f(x)=\frac 12\langle Ax,x\rangle -\langle b,x\rangle$$ où $A$ est symétrique définie positive. Minimiser $f$ revient à résoudre l'équation $Ax=b$, et la suite $(x^{kn})$ donnée par la méthode de relaxation pour minimiser $f$ (on fait donc les $n$ directions de descente) donne la même suite que la méthode de relaxation (avec $\omega=1$) pour résoudre $Ax=b$.