Problem 7 - Algorithms

A tridiagonal matrix is defined as a matrix of the form:

$$A=\left[\begin{tabular}{ccccc} $b_1$ & $c_1$ & & & \\ $a_2$ & $... ... & \\ & & & & \\ & & & & \\ & & & $a_n$ & $b_n$ \\ \end{tabular}\right]$$

Suppose that $A$ can be LU-decomposed into the following form:

$$A=\left[\begin{tabular}{ccccc} $1$ & & & & \\ $l_2$ & $1$ & & &... ... $u_3$ & \\ & & & & \\ & & & & \\ & & & & $d_n$ \\ \end{tabular}\right]$$

1.

Describe the relationship between $(a_i),(b_i),(c_i)$ and $(l_i),(d_i),(u_i)$.

2.

Show an algorithm to compute $(l_i),(d_i),(u_i)$.