摘要
QR 分解是數值線性代數中使用最廣泛的矩陣分解方法之一。它將矩陣 A 分解為A = QR，其中 Q 是正交矩陣，R 是上三角矩陣。 QR 分解有很多應用，例如用來計算矩陣的特徵值。 在本論文中，我們首先回顧了三種 QR 分解方法。 接下來，我們實作如何用QR分解計算特徵值。 我們透過將原始矩陣轉換為 Hessenberg 矩陣來降低之後每一次QR分解所花費的時間。再來，我們通過對 Hessenberg 矩陣使用Rayleigh shift來加快收斂速度。 但是我們發現有些矩陣最後不會收斂到上三角矩陣。 所以我們應用另一個Wilkinson shift來解決這個問題。
並列摘要
QR factorization, sometimes also called QR decomposition, is one of the most widely used matrix decomposition method in numerical linear algebra. It decomposed a matrix A into a product A = QR, where Q is an orthogonal matrix and R is an upper triangular matrix. QR factorization has many applications such as QR algorithm, which is used to compute the eigenvalues of a matrix. In this thesis, we first review three QR factorization methods. Next, we implement the QR algorithm. We reduce the cost of QR factorization per iteration by transforming an original matrix to a Hessenberg matrix. And we speed up the convergence rate by applying a Rayleigh quotient shift to a Hessenberg matrix. But we find some matrix will not converge to an upper triangular matrix at the end. So we apply another shift called Wilkinson shift to overcome this problem.