Algorithme de Thomas

Le balayage vers l'avant consiste en le calcul de nouveaux coefficients comme suit, où les nouveaux coefficients sont notés par des dérivées :

${\displaystyle c'_{i}={\begin{cases}{\cfrac {c_{i}}{b_{i}}},&i=1,\\{\cfrac {c_{i}}{b_{i}-a_{i}c'_{i-1}}},&i=2,3,\dots ,n-1\end{cases}}}$

et

Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « http://localhost:6011/fr.wikipedia.org/v1/ » :): {\displaystyle d'_i = \begin{cases} \cfrac{d_i}{b_i}, & i = 1, \\ \cfrac{d_i - a_i d'_{i - 1}}{b_i - a_i c'_{i - 1}}, & i = 2, 3, \dots, n. \end{cases} }

La solution est alors obtenue par substitution à rebours :

${\displaystyle x_{n}=d'_{n},}$

${\displaystyle x_{i}=d'_{i}-c'_{i}x_{i+1},\quad i=n-1,n-2,\ldots ,1.}$

La méthode ci-dessus ne modifie pas les vecteurs de coefficients d'origine, mais doit stocker les nouveaux coefficients. Si les vecteurs de coefficients doivent être modifiés, alors un algorithme avec moins de gestion de l'information est possible :

Pour ${\displaystyle i=2,3,\dots ,n,}$ on détermine

${\displaystyle w={\cfrac {a_{i}}{b_{i-1}}},}$

${\displaystyle b_{i}:=b_{i}-wc_{i-1},}$

${\displaystyle d_{i}:=d_{i}-wd_{i-1},}$

suivi du remplacement à rebours

Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « http://localhost:6011/fr.wikipedia.org/v1/ » :): {\displaystyle x_n = \cfrac{d_n}{b_n},}

${\displaystyle x_{i}={\cfrac {d_{i}-c_{i}x_{i+1}}{b_{i}}}\quad {\text{pour }}i=n-1,n-2,\dots ,1.}$

L'algorithme matriciel tridiagonal est un cas particulier d'élimination gaussienne.

On suppose que les inconnues soient ${\displaystyle x_{1},\ldots ,x_{n}}$, et que les équations à résoudre sont :

${\displaystyle {\begin{alignedat}{4}&&&b_{1}x_{1}&&+c_{1}x_{2}&&=d_{1}\\&a_{i}x_{i-1}&&+b_{i}x_{i}&&+c_{i}x_{i+1}&&=d_{i}\,,\quad i=2,\ldots ,n-1\\&a_{n}x_{n-1}&&+b_{n}x_{n}&&&&=d_{n}\,.\end{alignedat}}}$

En modifiant la deuxième équation ( ${\displaystyle i=2}$ ) avec la première équation comme suit :

${\displaystyle ({\mbox{équation 2}})\cdot b_{1}-({\mbox{équation 1}})\cdot a_{2}}$

ce qui donnerait :

${\displaystyle (b_{2}b_{1}-c_{1}a_{2})x_{2}+c_{2}b_{1}x_{3}=d_{2}b_{1}-d_{1}a_{2}.}$

On peut remarquer que Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « http://localhost:6011/fr.wikipedia.org/v1/ » :): {\displaystyle x_1} a été éliminé de la deuxième équation. Utiliser une tactique similaire avec la deuxième équation modifiée sur la troisième équation donne :

${\displaystyle (b_{3}(b_{2}b_{1}-c_{1}a_{2})-c_{2}b_{1}a_{3})x_{3}+c_{3}(b_{2}b_{1}-c_{1}a_{2})x_{4}=d_{3}(b_{2}b_{1}-c_{1}a_{2})-(d_{2}b_{1}-d_{1}a_{2})a_{3}.\,}$

Cette fois ${\displaystyle x_{2}}$ a été éliminé. Si cette procédure est répétée pour l'ensemble des ${\displaystyle n}$ lignes, alors chaque équation modifiée n'impliquerait qu'une seule inconnue, ${\displaystyle x_{n}}$. Cette équation peut être résolue puis utilisée pour résoudre l'équation ${\displaystyle (n-1)}$, et ainsi de suite jusqu’à ce que toutes les inconnues soient obtenues.

On observe que les coefficients des équations modifiées deviennent de plus en plus compliqués s’ils sont exprimés de façon explicite. En examinant la procédure, les coefficients modifiés (notés par des tildes) peuvent plutôt être définis de manière récursive :

${\displaystyle {\tilde {a}}_{i}=0\,}$

${\displaystyle {\tilde {b}}_{1}=b_{1}\,}$

${\displaystyle {\tilde {b}}_{i}=b_{i}{\tilde {b}}_{i-1}-{\tilde {c}}_{i-1}a_{i}\,}$

${\displaystyle {\tilde {c}}_{1}=c_{1}\,}$

${\displaystyle {\tilde {c}}_{i}=c_{i}{\tilde {b}}_{i-1}\,}$

${\displaystyle {\tilde {d}}_{1}=d_{1}\,}$

${\displaystyle {\tilde {d}}_{i}=d_{i}{\tilde {b}}_{i-1}-{\tilde {d}}_{i-1}a_{i}.\,}$

Pour accélérer encore la résolution, les coefficients ${\displaystyle {\tilde {b}}_{i}}$ peuvent être divisés (s'il n'y a pas de risque de division par zéro), les coefficients modifiés les plus récents, ici notés par une dérivée, seront :

${\displaystyle a'_{i}=0\,}$

${\displaystyle b'_{i}=1\,}$

${\displaystyle c'_{1}={\frac {c_{1}}{b_{1}}}\,}$

${\displaystyle c'_{i}={\frac {c_{i}}{b_{i}-c'_{i-1}a_{i}}}\,}$

Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « http://localhost:6011/fr.wikipedia.org/v1/ » :): {\displaystyle d'_1 = \frac{d_1}{b_1}\,}

${\displaystyle d'_{i}={\frac {d_{i}-d'_{i-1}a_{i}}{b_{i}-c'_{i-1}a_{i}}}.\,}$

Cela donne le système suivant :

${\displaystyle {\begin{array}{lcl}x_{i}+c'_{i}x_{i+1}=d'_{i}\qquad &;&\ i=1,\ldots ,n-1\\x_{n}=d'_{n}\qquad &;&\ i=n.\\\end{array}}\,}$

La dernière équation ne comportant qu’une seule inconnue, en la résolvant on réduit l'avant-dernière équation à une inconnue, de sorte que cette substitution à rebours puisse être utilisée pour trouver toutes les inconnues :

${\displaystyle x_{n}=d'_{n}\,}$

${\displaystyle x_{i}=d'_{i}-c'_{i}x_{i+1}\qquad$ ;\ i=n-1,n-2,\ldots ,1.}

• W. H. Press, S. A. Teukolsky, W. T. Vetterling et B. P. Flannery, Numerical Recipes: The Art of Scientific Computing, New York, Cambridge University Press, 2007 (ISBN 978-0-521-88068-8), « Section 2.4 »

• Portail de l’algèbre