Divide-and-conquer eigenvalue algorithm: Difference between revisions

Revision as of 17:43, 26 October 2004

Revision as of 18:02, 26 October 2004

Line 16:

The ''divide'' part of the divide and conquer algorithm comes from the realization that a tridiagonal matrix is "almost" block diagonal.

<!-- For original TeX, see image description page -->

:<math>T = \begin{bmatrix} & & & & & \\ & T_{1} & & & & \\ & & & \beta & & \\ & & \beta & & & \\ & & & & T_{2} & \\ & & & & & \end{bmatrix}</math>

:[[Image:Almost_block_diagonal.png]]

We write <math>T</math> as a block diagonal matrix, plus a [[Rank (linear algebra)|rank-1]] correction:

<!-- For original TeX, see image description page -->

:<math>T =

:[[Image:Block_diagonal_plus_correction.png]]

\begin{bmatrix} & & & & & \\ & \hat{T}_{1} & & & 0 & \\ & & & & & \\ & & & & & \\ & 0 & & & \hat{T}_{2} & \\ & & & & & \end{bmatrix}

+ \begin{bmatrix} & & & & & \\ & & & & & \\ & & \beta & \beta & & \\ & & \beta & \beta & & \\ & & & & & \\ & & & & & \end{bmatrix}</math>

[[Category:Numerical analysis]][[Category:Linear algebra]][[Category:Algorithms]]