2.2.4 Recursion Method

Find solution $\mbox{$\bf x$}$ if $\mbox{${\bf A}$}$ is tri-diagonal (maybe after Householder).

With

$$\mbox{${\bf A}$} \equiv \left( \begin{array}{cccccc} \beta_{1}& \gamma_{1} & 0 & . & . & ... ...1} & \gamma_{N-1} \\ . & . & . & 0 & \alpha_{N} & \beta_{N} \end{array}\right)$$

the system of equations reads

$$\beta_{1}\,x_{1} + \gamma_{1}\,x_{2} = b_{1}$$

$$\alpha_{i}\,x_{i-1}+\beta_{i}\,x_{i} + \gamma_{i}\,x_{i+1} = b_{i} \, ; \;\; i=2,\dots,N\!-\!1$$

$$\alpha_{N}\,x_{N\!-\!1} + \beta_{N}\,x_{N} = b_{N}$$

Introducing auxiliary variables $g_{i}$ and $h_{i}$ by the recursive ansatz

$$x_{i+1} = g_{i} \, x_{i} + h_{i} \, ; \; i=1, \dots , N\!-\!1$$

we find the ``downward recursion formulae''

$\parbox{600pt}{ \begin{eqnarray} g_{N\!-\!1}=\frac{-\alpha_{N}}{\bet... ...{i}+\gamma_{i}\,g_{i}} \, ; \;\; i=N\!-\!1, \dots,2 \nonumber \end{eqnarray}}$


Having arrived at $g_{1}$ and $h_{1}$ we insert the known values of $g_{i},\, h_{i}$ in the ``upward recursion formulae''

$\parbox{600pt}{ \begin{eqnarray} x_{1}&=&\frac{b_{1}-\gamma_{1}\,h_{... ...i+1}&=&g_{i}\,x_{i}+h_{i}\, ; \;\; i=1, \dots,N\!-\!1 \nonumber \end{eqnarray}}$

(The equation for the starting value $x_{1}$ follows from $\beta_{1} x_{1} + \gamma_{1}x_{2}=b_{1}$ and $x_{2}=g_{1}x_{1}+h_{1}$.)



EXAMPLE: In $\mbox{${\bf A}$} \cdot \mbox{$\bf x$}=\mbox{$\bf b$}$, let

$$\mbox{${\bf A}$} \equiv \left( \begin{array}{cccc} \beta_{1... ... \left( \begin{array}{c} 1 \\ 2 \\ 3 \\ 4 \end{array} \right)$$

Downward recursion: $g_{3}=-\alpha_{4}/\beta_{4}=-1/3$, $h_{3}= b_{4}/\beta_{4}=4/3$, and

$$i=3: \;\; g_{2}= -3/10 \; , \;\; h_{2}= 1/10$$

$$i=2: \;\; g_{1}= -20/27 \; , \;\; h_{1}= 19/27$$

Upward recursion: $x_{1} = 8/34$, and

$$i=1: \;\; x_{2} = 9/17$$

$$i=2: \;\; x_{3} = -1/17$$

$$i=3: \;\; x_{4} = 23/17$$