On considère une matrice $A$ tridiagonale carré d'ordre $n \in \mathbb{N}^*$, tel que l'on souhaite résoudre le système suivant :

Illustration d'un système de la forme $Ax=d$.

De manière général, la matrice $A$ est donnée sous la forme :

$$A = \begin{pmatrix}b_1 & c_1 & 0 & \cdots & 0 \\a_2 & b_2 & c_2 & \ddots & \vdots \\0 & \ddots & \ddots & \ddots & 0 \\\vdots & \ddots & a_{n-1} & b_{n-1} & c_{n-1} \\0 & \cdots & 0 & a_n & b_n\end{pmatrix}$$

• $a_{i}$ les éléments de la diagonale gauche
• $b_{i}$ les éléments de la diagonale centrale
• $c_{i}$ les éléments de la diagonale droite

On peut donner le système "général" associé à l'équation $Ax=d$.

$$\begin{cases}b_1 x_1 + c_1 x_2 = d_1 \\a_2 x_1 + b_2 x_2 + c_2 x_3 = d_2 \\ \\a_i x_{i-1} + b_i x_i + c_i x_{i+1} = d_i \\ \\a_{n-1} x_{n-2} + b_{n-1} x_{n-1} + c_{n-1} x_n = d_{n-1} \\a_n x_{n-1} + b_n x_n = d_n\end{cases}$$

Chaque ligne $i$ permet d'exprimer $x_i$ en fonction de $x_{i+1}$.

Soit :

$$x_i = p_ix_{i+1}+q_i, \quad 1 \leq i \leq n-1$$

On peut alors calculer $x_n$ à partir de la dernière équation du système, puis ensuite, on calculera $x_{n-1}$, $x_{n-2}, \ldots$ en remontant au fur et à mesure dans le système.

On souhaite calculer $p_1$, $q_1$ et $p_2$, $q_2$.

D'après la relation précédente, on sait que :

$$x_1 = p_1x_2+q_1, \quad x_2=p_2x_3+q_2$$

En utilisant la première ligne du système ci-dessus, on a :

$$\begin{align*}b_1x_1+c_1x_2 &= d_1 \\ b_1x_1 &= d_1-c_1x_2 \\x_1 &= \frac{d_1-c_1x_2}{b_1}\end{align*}$$

La relation dans l'énoncé : $x_i=p_ix_{i+1}+q_i$ alors si on respecte cette relation pour $x_1$ trouvé ci dessus :

$$x_1 = -\frac{c_1}{b_1}x_2+\frac{d_1}{b_1}$$

d'où on a si $b_1 \ne 0$ :

$$x_1 = p_1x_2+q_1, \quad \text{ avec } \boxed{p_1=-\frac{c_1}{b_1} \; et \; q_1 = \frac{d_1}{b_1}}$$

Pour déterminer $p_2$ et $q_2$ faisons de même en utilisant la seconde ligne du système.

$$a_2x_1+b_2x_2+c_2x_3 = d_2$$

On peut utiliser le résultat de $x_1$ déterminé précédemment : $x_1=p_1x_2+q_1$

On a alors :

$$\begin{align*}a_2(p_1x_2+q_1)+b_2x_2+c_2x_3 &= d_2 \\ a_2p_1x_2+a_2q_1+b_2x_2+c_2x_3 &= d_2\\ x_2(a_2p_1+b_2)+a_2q_1+c_2x_3 &= d_2 \\ x_2(a_2p_1+b_2) &= d_2 - a_2q_1-c_2x_3 \\ x_2 &= \frac{d_2 - a_2q_1-c_2x_3}{a_2p_1+b_2}\end{align*}$$

Pareil que pour $x_1$, on cherche une équation de la forme $x_2=p_2x_3+q_2$ essayons de la rendre comme ceci :

$$x_2=\underbrace{-\frac{c_2}{a_2p_1+b_2}}_{p_2}x_3+\underbrace{\frac{d_2 - a_2q_1}{a_2p_1+b_2}}_{q_2}$$

si et seulement si : $a_2p_1+b_2 \ne 0$.

D'après l'expression donnée en consigne :

$$x_k = p_kx_{k+1}+q_k$$

Nous on cherche la formule récurrente c'est à dire $x_{k+1}$.

Toute à l'heure, lorsque l'on a écrit le système d'équation associé au système $Ax=d$ on a eu :

$$\begin{cases}b_1 x_1 + c_1 x_2 = d_1 \\a_2 x_1 + b_2 x_2 + c_2 x_3 = d_2 \\ \\a_i x_{i-1} + b_i x_i + c_i x_{i+1} = d_i \\ \\a_{n-1} x_{n-2} + b_{n-1} x_{n-1} + c_{n-1} x_n = d_{n-1} \\a_n x_{n-1} + b_n x_n = d_n\end{cases}$$

Pour $i=k+1$ on a :

$$a_{k+1}x_k+b_{k+1}x_{k+1}+c_{k+1}x_{k+2} = d_{k+1}$$

Comme on connait dans l'énoncé la formule de $x_k$, on peut la substituer de l'expression précédente, on a alors :

$$\begin{align*} a_{k+1}x_k+b_{k+1}x_{k+1}+c_{k+1}x_{k+2} &= d_{k+1} \\ a_{k+1}(p_kx_{k+1}+q_k)+b_{k+1}x_{k+1}+c_{k+1}x_{k+2} &= d_{k+1} \\ a_{k+1}p_kx_{k+1}+a_{k+1}q_k+b_{k+1}x_{k+1}+c_{k+1}x_{k+2} &= d_{k+1} \\ x_{k+1}(a_{k+1}p_k+b_{k+1})+a_{k+1}q_k+c_{k+1}x_{k+2} &= d_{k+1} \\ x_{k+1}(a_{k+1}p_k+b_{k+1}) &= d_{k+1} - a_{k+1}q_k-c_{k+1}x_{k+2} \\ x_{k+1} &= \frac{d_{k+1} - a_{k+1}q_k-c_{k+1}x_{k+2}}{a_{k+1}p_k+b_{k+1}}\end{align*}$$

Essayons d'obtenir quelque chose de la forme : $x_{k+1}=p_{k+1}x_{k+2}+q_{k+1}$

$$x_{k+1} = \underbrace{-\frac{c_{k+1}}{a_{k+1}p_k+b_{k+1}}}_{p_{k+1}}x_{k+2}+\underbrace{\frac{d_{k+1} - a_{k+1}q_k}{a_{k+1}p_k+b_{k+1}}}_{q_{k+1}}$$

Si et seulement si : $a_{k+1}p_k+b_{k+1} \neq 0$.

Nous pouvons repartir de l'expression donnée en consigne :

$$x_{n-1} = p_{n-1}x_n+q_{n-1}$$

on peut injecter celle-ci dans la dernière équation de notre système :

$$\begin{align*}a_nx_{n-1}+b_nx_n &= d_n \\ a_n(p_{n-1}x_n+q_{n-1})+b_nx_n &= d_n \\ a_np_{n-1}x_n+a_nq_{n-1}+b_nx_n &= d_n \\ x_{n}(a_np_{n-1}+b_n)+a_nq_{n-1} &= d_n \\ x_{n}(a_np_{n-1}+b_n) &= d_n-a_nq_{n-1} \\x_n &= \frac{d_n-a_nq_{n-1}}{a_np_{n-1}+b_n}=q_n\end{align*}$$

Si et seulement si : $a_np_{n-1}+b_n \ne 0$

• Calculer $p_1$ et $q_1$
• Calculer par récurrence les valeurs de $p_k$ et de $q_k$ pour $k \in [2; n-1]$
• Calcul de $x_n$
• Après on reprend la formule de l'énoncé et on calcul les inconnues en remontant en partant de l'équation $n-1$.

p1 ← -c1/b1
q1 ← d1/b1
pour k ← 1 à n-2
faire
  temp ← a_{k+1}pk+b_{k+1}
  p_{k+1} ← -c_{k+1}/temp
  q_{k+1} ← (d_{k+1}-a_{k+1}qk)/temp
fin pour
xn ← (dn - anq_{n-1})/(anp_{n-1}+bn)
pour k ← n-1 à 1
faire
  xk ← pkx_{k+1}+qk
fin pour

Algorithme de calcul des solution d'un système tridiagonale.

$$x_k = p_kx_{k+1}+q_k \Longleftrightarrow q_k = x_k-p_kx_{k+1}$$

D'après la formule déduite pour $q_k$, on peut construire le système suivant :

$$\begin{cases} x_1-p_1x_2 = q_1 \\ x_2-p_2x_3 = q_2 \\ \\ x_i-p_ix_{i+1} = q_i \\ \\ x_{n-1}-p_{n-1}x_{n} = q_{n-1} \\ x_n = q_n\end{cases}$$

On se retrouve alors avec le système suivant :

$$\begin{pmatrix} 1 & -p_1 & 0 & \ldots & 0 \\ 0 & 1 & -p_2 & \ddots & \vdots \\ \vdots & \ddots & \ddots & \ddots & \vdots \\ \vdots & & \ddots & 1 & -p_{n-1}\\ 0 & \ldots & \ldots & 0& 1 \end{pmatrix}\begin{pmatrix}x_1 \\ x_2 \\ \vdots \\ x_{n-1} \\ x_n\end{pmatrix}=\begin{pmatrix}d_1 \\ d_2 \\ \vdots \\ d_{n-1} \\ d_n\end{pmatrix}$$