Saat menghitung nilai eigen dari matriks simetris M∈Rn×n hal terbaik yang dapat Anda lakukan dengan reflektor Householder adalah mengarahkan M ke bentuk tridiagonal. Seperti yang telah disebutkan dalam jawaban sebelumnya karena M adalah simetris ada transformasi kesamaan orthogonal yang menghasilkan matriks diagonal, yaitu, D=STMS . Ini akan menjadi nyaman jika kita bisa menemukan aksi matriks orthogonal diketahui S ketat menggunakan Householder reflektor dengan menghitung urutan reflektor dan menerapkan HT dari kiri ke M. dan Hdari kanan ke . Namun ini tidak mungkin karena cara reflektor Householder dirancang untuk nol kolom. Jika kita menghitung reflektor Householder untuk nol semua angka di bawah M 11 kita menemukan
M = (M.M.11
M.= ⎛⎝⎜⎜⎜⎜⎜⎜∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗⎞⎠⎟⎟⎟⎟⎟⎟→ HT1M.= ⎛⎝⎜⎜⎜⎜⎜⎜∗0000∗′∗′∗′∗′∗′∗′∗′∗′∗′∗′∗′∗′∗′∗′∗′∗′∗′∗′∗′∗′⎞⎠⎟⎟⎟⎟⎟⎟.
But now the entries
M.12−M1 n have been altered by the reflector
HT1 applied on the left. Thus when we apply
H1 on the right it will no longer zero out the first row of
M. leaving only
M.11. Instead we will obtain
HT1M=⎛⎝⎜⎜⎜⎜⎜⎜∗0000∗′∗′∗′∗′∗′∗′∗′∗′∗′∗′∗′∗′∗′∗′∗′∗′∗′∗′∗′∗′⎞⎠⎟⎟⎟⎟⎟⎟→HT1MH1=⎛⎝⎜⎜⎜⎜⎜⎜∗∗′∗′∗′∗′∗′′∗′′∗′′∗′′∗′′∗′′∗′′∗′′∗′′∗′′∗′′∗′′∗′′∗′′∗′′∗′′∗′′∗′′∗′′∗′′⎞⎠⎟⎟⎟⎟⎟⎟.
Where not only did we not zero out the row but we may destroy the zero structure we just introduced with the reflector
HT1.
MHT1
M=⎛⎝⎜⎜⎜⎜⎜⎜∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗⎞⎠⎟⎟⎟⎟⎟⎟→HT1M=⎛⎝⎜⎜⎜⎜⎜⎜∗∗′000∗∗′∗′∗′∗′∗∗′∗′∗′∗′∗∗′∗′∗′∗′∗∗′∗′∗′∗′⎞⎠⎟⎟⎟⎟⎟⎟.
Thus when we apply the same reflector from the right we obtain
HT1M=⎛⎝⎜⎜⎜⎜⎜⎜∗∗′000∗∗′∗′∗′∗′∗∗′∗′∗′∗′∗∗′∗′∗′∗′∗∗′∗′∗′∗′⎞⎠⎟⎟⎟⎟⎟⎟→HT1MH1=⎛⎝⎜⎜⎜⎜⎜⎜∗∗′000∗′∗′′∗′′∗′′∗′′0∗′′∗′′∗′′∗′′0∗′′∗′′∗′′∗′′0∗′′∗′′∗′′∗′′⎞⎠⎟⎟⎟⎟⎟⎟.
Applied recursively this allows us to drive M to a tridiagonal matrix T. You can complete the diagonalization of M efficiently, as was mentioned previously, using Jacobi or Givens rotations both of which are found in the Golub and Van Loan book Matrix Computations. The accumulated actions of the sequence of Householder reflectors and Jacobi or Givens rotations allows us to find the action of the orthogonal matrices ST and S without explicitly forming them.
For what reason do you assume that this is impossible?
Any symmetric real matrixS can be orthogonally diagonalized, i.e. S=GDGt , where G is orthogonal and D is diagonal.
Any orthogonal matrix of size n×n can be constructed as a product of at most n such reflections.Wikipedia. Therefore you have this decomposition.
I am not sure about the last statement, I just cite it (and I think it is correct). As far as I understand your question, it boils down to whether any orthogonal matrix can be decomposed into a sequence of Householder transforms.
sumber
If the eigenvalues are already known (from a preliminary calculation based on the usual approach), one can use them to triangulize a nonsymmetric matrix (or diagonalize a symmetric matrix) by a product onn−1 Householder reflections. In the k th step the k th column is brought to triangular form. (This also provides a simple inductive proof of the existence of the Schur factorization.)
It is actually useful for methods where one repeatedly needs the orthoginal matrix in a numerically stable factored form.
sumber