Algorithme de Thomas

En algèbre linéaire appliquée à la résolution numérique d'équation, l'algorithme de Thomas (du nom de Llewellyn Thomas), est une forme simplifiée du pivot de Gauss qui peut être utilisée pour résoudre des systèmes d'équations tridiagonales. Un système tridiagonal pour n inconnues peut s'écrire a i x i − 1 + b i x i + c i x i + 1 = d i , {\displaystyle a_{i}x_{i-1}+b_{i}x_{i}+c_{i}x_{i+1}=d_{i},} où a 1 = 0 {\displaystyle a_{1}=0} et c n = 0 {\displaystyle c_{n}=0} . [ b 1 c 1 0 a 2 b 2 c 2 a 3 b 3 ⋱ ⋱ ⋱ c n − 1 0 a n b n ] [ x 1 x 2 x 3 ⋮ x n ] = [ d 1 d 2 d 3 ⋮ d n ] . {\displaystyle {\begin{bmatrix}b_{1}&c_{1}&&&0\\a_{2}&b_{2}&c_{2}&&\\&a_{3}&b_{3}&\ddots &\\&&\ddots &\ddots &c_{n-1}\\0&&&a_{n}&b_{n}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\\x_{3}\\\vdots \\x_{n}\end{bmatrix}}={\begin{bmatrix}d_{1}\\d_{2}\\d_{3}\\\vdots \\d_{n}\end{bmatrix}}.} Pour de tels systèmes, la solution a une complexité algorithmique de O ( n ) {\displaystyle O(n)} au lieu de O ( n 3 ) {\displaystyle O(n^{3})} requis par élimination gaussienne. Un premier balayage élimine les coefficients a i {\displaystyle a_{i}} , puis une retro substitution (abrégée) produit la solution. Des exemples de telles matrices proviennent généralement de la discrétisation de l'équation de Poisson 1D et de l'interpolation par splines cubiques. L'algorithme de Thomas n'est pas stable en général, mais il l'est dans plusieurs cas particuliers, notamment lorsque la matrice est diagonalement dominante (soit par lignes, soit par colonnes) ou symétrique définie positive. Pour une caractérisation plus précise de la stabilité de l'algorithme de Thomas, voir le théorème de Higham 9.12. Si la stabilité est nécessaire dans le cas général, l'élimination gaussienne avec pivotement partiel (GEPP) est alors recommandée.