用QR與LR迭代法求矩陣特徵值與特徵向量之過程中，前人曾提出位移策略以加速其收斂速度，其中最有效的是Wilkinson 移位值。在此我們希望尋求能使收斂更快速的位移值。

我們首先嘗使用一三階子矩陣之特徵值作為一次QR迭代之移位值。在此子矩陣之特徵值中，我們選擇最接近Wilkinson 移位值的特徵值為移位值，期使特徵值之收斂更快。

另一移位策略是用一較快速省功的算則先計算矩陣之特徵值，再以這些計算值作為QR迭代之位移值，來計算較為費功的特徵向量。希望能較快得到所需要的特徵值與特徵向量。

在計算特徵值之算則中，Cholesky迭代法以其計算簡單，執行速度快為我們所選擇。由程式執行結果可知這兩種算則較EISPACK 的算則分別節省了約10% 與30% 的運算量。我們比較這些策略，並將結果列於文中。

Abstract

The QR and LR algorithms are the general methods for computing eigenvalues and eigenvectors of a dense matrix. In this paper, we propose some shift strategies that can increase the efficiency of the QR algorithm by first computing the eigenvalues of the matrix (or its trailing submatrix) in a fast and economical way, and then using them as shifts to find the eigenvalues and their corresponding eigenvectors. When incorporated with QR algorithm, these kinds of shift strategies can save about 10 to 30percent of work in arithmetic operations.

References:
[l] Dekker, T . J. and Traub, J. F., 1971. "The Shifted QR Algorithm for Hermitian
Matrices." Linear Algebra and Its Applications, 4:137-154
[2] Dubrulle, A., 1970. "A Short Note on the Implicit QL Algorithm for Symmetric
Tridiagonal Matrix." Numer. Math. , 15 :450.
[3] Golub, G. H. and Van Loan, C. F. , 1989. Matrix Computations. 2nd edition,
Baltimore, MD: The Johns Hopkins University Press.
[4] Jiang, E. and Zheng, Z., 1985. "A New Shift of the QL Algorithm for Irreducible
Symmetric Tridiagonal Matrices." Linear Algebra and Its Applications,65:261-272.
[5] Ortega, J. M. and Kaiser, H. F., 1963. "The LLT and QR Methods for Symmetric
Tridiagonal matrices." Computer Journal, 99-101.
[6] Parlett, B. N. , 1964. "The Development and Use of Methods of LR Type."
SIAM Review, 6:275-295 .
[7] Parlett, B. N., 1966. "Singular and Invariant Matrices Under the QR Transformation. " Math. Comp., 611-615.
[8] Parlett, B. N., 1980. The Semmetric Eigenvalue Problem. Prentice-Hall Inc. ,
Englewood Cliffs 1980.
[9] Rutishauser, H. and Schwarz, H. R., 1963. "The LR Transformation Method
for Symmetric Matrices." Numer. Math. 5:273-289.
[10] Saad, Y. , 1974, "Shift of Origin for the QR Algorithm." Toronto: Proceedings
IFIP Congress.
[11] Smith, B. T. and Boyle, J. M., 1974. Matrix Eigensystem Routines - EISPACK
Guide, Springer Verlag.
[12] 'Ward, R. C. and Gray, L. J ., 1978. "Eigensystem Computation for Skew-Symmetric Matrices and a Class of Symmetric Matrices." A CM Trans. on
Math. Software , 4:278-285 .
[13] Wilkinson, J. H. and Reisch, C., 1961. Handbook for A'l?tomatric Computation.
Volum. II. Linear Algebra, Springer Verlag.
[14] Wilkinson, J. H. , 1968. "Global Convergence of Tridiagonal QR Algorithm
with Origin Shifts." Linear Algebra and Its Applications, 1:409-420.
Notation Convention:
(1) CHOLESKY: This subroutine is the implementation of the modified LLT
algorithm.
(2)imTQLl: This subroutine from the EISPACK computes the eigenvalues.
by the implicit QL algorithm.
(3) imTQL2: This subroutine from the EISPACK computes the eigenvalues
and eigenvectors at the same tims by the implicit QL method.
(4) imTQL2s4l: This routine first computes eigenvalues by CHOLESKY and
then uses these eigenvalues as shifts in imTQL2.
(5) imTQL2s42: This subroutine makes the use of imTQL1 to compute the
eigenvalues and then uses these computed values as shifts in imTQL2 . .
(6) TQL1: This subroutine from the EISPACK computes eigenvalues by the
QL method.
(7) TQL1s31, TQL1s32, TQL1s33 : These subroutines are the test of the use
of 83 , described in section 3.
(8) TQL2: This subroutine from the EISPACK computes eigenvalues and
eigenvectors simultaneously by the QL method.
(9) TQL2s41: This subroutine calculate eigenvalues by CHOLESKY at first
and then uses these eigenvalues as shifts in TQL2.
(1 0) TQL2s42: This subroutine uses eigenvalues computed by TQL1 as shifts
in TQL2.