This presentation is a summary of the divide-and-conquer method. For more in-depth coverage of this algorithm, see Refs. [1, pp. 216-228], [19, pp. 359-363], and [26, pp. 229-232].

The recursive algorithm divides a symmetric tridiagonal matrix into submatrices and then applies the same algorithm to the submatrices. We will illustrate the method of splitting the problem into smaller submatrix problems using a 5 ×5 matrix

$T=\left[\begin{array}{ccccc}{a}_{1}& {b}_{1}& 0& 0& 0\\ {b}_{1}& {a}_{2}& {b}_{2}& 0& 0\\ 0& {b}_{2}& {a}_{3}& {b}_{3}& 0\\ 0& 0& {b}_{3}& {a}_{4}& {b}_{4}\\ 0& 0& 0& {b}_{4}& {a}_{5}\end{array}\right].$

Write A as a sum of two matrices as follows:

$T=\left[\begin{array}{ccccc}{a}_{1}& {b}_{1}& 0& 0& 0\\ {b}_{1}& {a}_{2}-{b}_{2}& 0& 0& 0\\ 0& 0& {a}_{3}-{b}_{2}& {b}_{3}& 0\\ 0& 0& {b}_{3}& {a}_{4}& {b}_{4}\\ 0& 0& 0& {b}_{4}& {a}_{5}\end{array}\right]+\left[\begin{array}{ccccc}0& 0& 0& 0& 0\\ 0& {b}_{2}& {b}_{2}& 0& 0\\ 0& {b}_{2}& {b}_{2}& 0& 0\\ 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0\end{array}\right].$

If we let

${T}_{1}=$

Start Free Trial

No credit card required