Content deleted Content added
CyborgTosser (talk | contribs) use images instead of TeX |
CyborgTosser (talk | contribs) finished divide section |
||
Line 18:
<!-- For original TeX, see image description page -->
:[[Image:Almost_block_diagonal.png]]
The size of submatrix <math>T_{1}</math> we will call <math>n \times n</math>, and then <math>T_{2}</math> is <math>(m - n) \times (m - n)</math>. Note that the remark about <math>T</math> being almost block diagonal is true regardless of how <math>n</math> is chosen (i.e., there are many ways to so decompose the matrix). However, it makes sense, from an efficiency standpoint, to choose <math>n \approx m/2</math>.
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 -->
:[[Image:Block_diagonal_plus_correction.png]]
The only difference between <math>T_{1}</math> and <math>\hat{T}_{1}</math> is that the lower right entry <math>t_{nn}</math> in <math>\hat{T}_{1}</math> has been replaced with <math>t_{nn} - \beta</math> and similarly, in <math>\hat{t}_{2}</math> the top left entry <math>t_{n+1,n+1}</math> has been replaced with <math>t_{n+1,n+1} - \beta</math>.
The remaineder of the divide step is to solve for the eigenvalues (and if desired the eigenvectors) of <math>\hat{T}_{1}</math> and <math>\hat{T}_{2}</math>, that is to find the [[diagonalization]]s <math>\hat{T}_{1} = Q_{1} D_{1} Q_{1}^{T}</math> and <math>\hat{T}_{2} = Q_{2} D_{2} Q_{2}^{T}</math>. This can be accomplished with recursive calls to the divide-and-conquer algorithm.
==Conquer==
[[Category:Numerical analysis]][[Category:Linear algebra]][[Category:Algorithms]]
| |||