07. Computing Eigenvalues - Symmetric QR Algorithm

Inner Product for Iterative Methods

For $x\in {\mathbb{R}}^n$ then

$$||x||=\sqrt{x^{T}x}$$

Link to original

Notation for Iterative Methods

For iterative methods then

$$x_k\text{ or }{x}^k\text{ or }{x}^{(k)}$$

is used to denote the vector $x$ at $k$-th iteration

Link to original

Power Iteration

Method to calculate single largest eigenvalue of square matrix $A$ with associated eigenvector

Let $A\in {\mathbb{R}}^{n\times n}$
Let $y\in {\mathbb{R}}^n$ be arbitrary then

$$x_0=\frac{y}{||y||}$$

For $k=0,1,\cdots$ then
Compute

$$y_k=A{x}_k$$

Then set

$$x_{k+1}=\frac{y_k}{||y_k||}$$

Proof

Suppose $A$ is diagonalisable so there exists basis of eigenvectors of $A$

$$\{v_1,v_2,\cdots ,v_n\}$$

where

$$A{v}_i={\lambda }_i{v}_i\text{ and }||v_i||\text{ for }i=1,2,\cdots ,n$$

Assume

$$|{\lambda }_1|>|{\lambda }_2|\ge \cdots \ge |{\lambda }_n|$$

Then

$$x_0=\sum _{i=1}^n{\alpha }_i{v}_i$$

for ${\alpha }_i\in \mathbb{R}$ for $i=1,2,\cdots ,n$ hence

$$A^k{x}_0=A^k\sum _{i=1}^n{\alpha }_i{v}_i=\sum _{i=1}^n{\alpha }_i{A}^k{v}_i=\sum _{i=1}^n{\alpha }_i{\lambda }_i^k{v}_i={\lambda }_1^k\left[{\alpha }_1{v}_1+\sum _{i=2}^n{\alpha }_i{\left(\frac{{\lambda }_i}{{\lambda }_1}\right)}^k{v}_i\right]$$

As ${\frac{{\lambda }_i}{{\lambda }_1}}^k\to 0$ as $k\to \infty$ then

$$\frac{A^k{x}_0}{||A^k{x}_0||}\to \pm v_1\text{ and }\frac{||A^k{x}_0||}{||A^{k-1}{x}_0||}\approx \left|\frac{{\lambda }_1^k{\alpha }_1}{{\lambda }_1^{k-1}{\alpha }_1}\right|=|{\lambda }_1|$$

as $k\to \infty$

Link to original

QR Algorithm

Let $a$ be a symmetric matrix
Let $A_1=A$

For $k=1,2,\cdots$ then
Let

$$A_k=Q_k{R}_k$$

using QR Factorisation
Then

$$A_{k+1}=R_k{Q}_k$$

Link to original

Property of QR Algorithm

Let $A_1,A_2,\cdots ,A_k,\cdots$ be from QR Algorithm then

$A_1,A_2\cdots ,A_k,\cdots$ are all symmetric and similar so have same eigenvalues

Proof

As

$$A_{k+1}=R_k{Q}_k=(Q_k^T{Q}_k)R_k{Q}_k=Q_k^T(Q_k{R}_k)Q_k=Q_k^T{A}_k{Q}^k=Q_k^{-1}{A}_k{Q}_k$$

So $A_{k+1}$ is symmetric if $A_k$ is symmetric and similar to $A_k$

Link to original

Property of Iterates of QR Algorithm lemma

Let $A_k$ be iterates of QR algorithm
Let

$$Q^{(k)}:=Q_1\cdots Q_k\text{ and }{R}^{(k)}:=R_k\cdots R_1$$

Then

$$A_{k+1}=(Q^{(k)}{)}^{T}A{Q}^{(k)}$$

and

$$A^k=(Q_1\cdots Q_k)(R_k\cdots R_1)=Q^{(k)}{R}^{(k)}$$

is the QR factorisation of $A^k$

Proof

First part follows from repeatedly applying

$$A_{k+1}=R_k{Q}_k=(Q_k^T{Q}_k)R_k{Q}_k=Q_k^T(Q_K{R}_k)Q_k=Q_k^T{A}_k{Q}^k$$

Using induction then for $k=1$ result follows trivially
Suppose $A_{k-1}=Q^{(k-1)}{R}^{(k-1)}$ then

$$A_k=R_{k-1}{Q}_{k-1}=(Q^{(k-1)}{)}^{T}A(Q^{(k-1)})$$

And

$$(Q^{(k-1)}{)}^{T}A(Q^{(k-1)})=Q_k{R}_k$$

Hence

$$A{Q}^{(k-1)}=Q^{(k-1)}{Q}_k{R}_k$$

Thus

$$A^k=A{Q}^{(k-1)}{R}^{(k-1)}=Q^{(k-1)}{Q}_k{R}_k{R}^{(k-1)}=Q^{(k)}{R}^{(k)}$$

Link to original

Property of First Column of QR Factorisation lemma

Let $Q^{(k)}$ be defined as from Property of Iterates of QR Algorithm with first column $q_1$
Let $e_1=[1,0,\cdots ,0{]}^T$ then

$$q_1=\frac{A^k{e}_1}{||A^k{e}_1|{|}_2}\text{ or }{q}_1=-\frac{A^k{e}_1}{||A^k{e}_1|{|}_2}$$

Proof

Multiplying $A^k=Q^k{R}^k$ by $e_1$ then

$$A^k{e}_1=Q^{(k)}{R}^{(k)}{e}_1$$

As $R^{(k)}$ is upper triangular then

$$R^{(k)}{e}_1=[R_{1,1}^{(k)},0,\cdots ,0{]}^T$$

Hence $Q^{(k)}{R}^{(k)}{e}_1$ is parallel to $q_1$ which has unit form

Link to original

Convergence of $A_k$ of QR Algorithm

For fixed $k\in \mathbb{N}$

Let column $q_i$ be defined by

$$q_i=Q^{(k)}{e}_i$$

that is it is the $i$-th column of $Q^{(k)}$

Then

$$\begin{array}{rl}& q_1\text{ converges to dominant eigenvector}\\ & q_2\text{ converges to }2\text{nd dominant eigenvector}\\ & ⋮\end{array}$$

So columns of $Q^{(k)}$ converge to eigenvectors
Hence $A_k$ converges to diagonal matrix of eigenvalues

Link to original

Tridiagonal

Let $A$ be a matrix then

$A$ is tridiagonal if only non-zero elements are along diagonal, lower diagonal and upper diagonal
So $A$ is in form

$$A=\left(\begin{array}{ccccc}{a}_1& b_1& & & \\ c_1& a_2& b_2& & \\ & c_2& \ddots & \ddots & \\ & & \ddots & \ddots & b_{n-1}\\ & & & c_{n-1}& a_n\end{array}\right)$$

Link to original

Reduction to Tridiagonal Form

Let $A$ be a matrix then

There exists construction for $Q$ such that

$$QA{Q}^T\text{ is tridiagonal}$$

where $Q$ is orthogonal so a similarity transformation

Proof

If

$$H(w)A=\left[\begin{array}{cccc}\times & \times & \cdots & \times \\ 0& \times & \cdots & \times \\ ⋮& ⋮& \ddots & ⋮\\ 0& \times & \cdots & \times \end{array}\right]$$

Then $H(w)AH(w{)}^T$ is generally full so
All zeroes created by pre-multiplication are destroyed by post-multiplication

Assume $A=A^T$ then $A$ is in form

$$A=\left[\begin{array}{cc}\gamma & u^T\\ u& C\end{array}\right]$$

with

$$w=\left[\begin{array}{c}0\\ \hat{w}\end{array}\right]\text{ where }H(\hat{w})u=\left[\begin{array}{c}\alpha \\ 0\\ ⋮\\ 0\end{array}\right]$$

Then

$$H(w)A=\left[\begin{array}{cccc}\gamma & u^T& & \\ \alpha & \times & \cdots & \times \\ ⋮& ⋮& ⋮& ⋮\\ 0& \times & ⋮& \times \end{array}\right]$$

However

$$H(w)AH(w{)}^{-1}=H(w)AH(w{)}^T=H(w)AH(w)=\left(\begin{array}{ccccc}\gamma & \alpha & 0& \cdots & 0\\ \alpha & & & & \\ 0& & & & \\ ⋮& & B& & \\ 0& & & & \end{array}\right)$$

where

$$B=H(\hat{w})C{H}^T(\hat{w})\text{ as }{u}^{T}H(\hat{w}{)}^T=(\alpha ,0,\cdots ,0)$$

Inductively apply to smaller matrix $B$

After $n-2$ such Householder Similarity Transformations then

$$H(w_{n-2})\cdots H(w_2)H(w)AH(w)H(w_2)\cdots H(w_{n-2})$$

is tridiagonal

Link to original

Similar Matrices

Let $A$ be a symmetric matrix

$A$ is similar to $B$ if there exists non-singular matrix $P$ such that

$$A=P^{-1}BP$$

where $A,B$ have same eigenvalues as

$$0=\det (A-\lambda I)=\det (P^{-1}(B-\lambda I)P)=\det (P^{-1})\det (P)\det (B-\lambda I)=\det (B-\lambda I)$$

Hence

$$\det (A-\lambda I)=0⟺\det (B-\lambda I)=0$$

Link to original

Givens Rotation

Let $i,j\in \mathbb{N}$ then

Orthogonal Matrix

$$J(i,j)$$

is defined by
$I$ except for the four elements $(i,i),(i,j),(j,i),(j,j)$ replaced by

$$c,s,-s,c\text{ respectively}$$

where

$$c^2+s^2=1$$

Rotating

Given any vector

$$\left(\begin{array}{c}a\\ b\end{array}\right)$$

Can always find $c,s$ such that

$$\left(\begin{array}{cc}c& s\\ -s& c\end{array}\right)\left(\begin{array}{c}a\\ b\end{array}\right)=\left(\begin{array}{c}\sqrt{a^2+b^2}\\ 0\end{array}\right)$$

Link to original

Construction of Upper Triangular Matrix

Let $A$ be a matrix then exists orthogonal matrix such that

$$Q^{T}A\text{ is upper triangular}$$

And so $A$ in form

$$A=QR$$

Proof

From Reduction to Tridiagonal Form there exists $Q$ such that

$$QA{Q}^T\text{is tridiagonal}$$

Then using Givens Rotation Matrices choosing $c$ such that

$$\left[\begin{array}{cc}c& s\\ -s& c\end{array}\right]\left[\begin{array}{c}a\\ b\end{array}\right]=\left[\begin{array}{c}\sqrt{a^2+b^2}\\ 0\end{array}\right]$$

So there exists

$$J(n-1,n)\cdots J(2,3)J(1,2)A=R$$

such that $R$ is upper triangular and in form

$$R=\left[\begin{array}{cccccccc}\times & \times & \times & 0& 0& 0& \cdots & 0\\ 0& \times & \times & \times & 0& 0& \cdots & 0\\ 0& 0& \times & \times & \times & 0& \cdots & 0\\ ⋮& ⋮& & & & & & ⋮\\ 0& 0& 0& 0& \times & \times & \times & 0\\ 0& 0& 0& 0& 0& \times & \times & \times \\ 0& 0& 0& 0& 0& 0& \times & \times \\ 0& 0& 0& 0& 0& 0& 0& \times \end{array}\right]$$

Link to original

QR Algorithm on Symmetric Diagonal Matrix lemma

Let $A$ be a symmetric tridiagonal matrix then

Applying QR Algorithm to $A$ preserves symmetry and tridiagonal form so

$A_k$ is symmetric tridiagonal for all $k$

Proof

As $A_{k+1}=RQ$ is symmetric if $A_k=QR$ is symmetric
If

$$A_k=QR=J(1,2{)}^{T}J(2,3{)}^T\cdots J(n-1,n{)}^{T}R\text{ is tridiagonal}$$

Then

$$A_{k+1}=RQ=RJ(1,2{)}^{T}J(2,3{)}^T\cdots J(n-1,n{)}^T$$

is also tridiagonal

Post multiplication by $J(i,i+1{)}^T$ replaces columns $i$ and $i+1$ by linear combination
With columns $j=1,2,\cdots ,i-1,i+2,\cdots ,n$ being the same

As $R$ is upper triangular then subdiagonal entry $RJ(1,2{)}^T$ is in position $(2,1)$

Similarly,
Subdiagonal entries in $RJ(1,2{)}^{T}J(2,3{)}^T=(RJ(1,2){)}^{T}J(2,3{)}^T$ is position $(2,1)$ and $(3,2)$
Hence inductively

$$\begin{array}{rl}RJ(1,2)& {}^{T}J(2,3{)}^T\cdots J(i-2,i-1{)}^{T}J(i-1,i{)}^T\\ & =(RJ(1,2{)}^{T}J(2,3{)}^T\cdots J(i-2,i-1{)}^T)J(i-1,i{)}^T\end{array}$$

are in positions $(j,j-1)$ for $j=2,\cdots ,i$
Hence lower triangular part of $A_{k+1}$ has non-zeros on first subdiagonal

As $A_{k+1}$ is symmetric then it must be tridiagonal

Link to original

Shifted QR Algorithm

For $k=1,2,\cdots$ then

Find QR Factorisation of

$$A_k-{\mu }_{k}I=Q_k{R}_k$$

Define

$$A_{k+1}=R_k{Q}_k+{\mu }_{k}I$$

Note $\{A_k{\}}_{k=1}^{\infty }$ are symmetric and tridiagonal if $A_1$ satisfies it as well for any sequence ${\mu }_k\in \mathbb{R}$

Link to original

Deflation

Using Shifted QR Algorithm where ${\mu }_k=(A_k{)}_{n,n}$ so bottom-right element of $A_k$ then
Generally rapidly leads to

$$A_k=\left[\begin{array}{cc}{T}_k& 0\\ 0^T& \lambda \end{array}\right]$$

where $T_k$ is a $n-1\times n-1$ tridiagonal matrix and $\lambda$ an eigenvalue of $A_1$

Link to original

Property of Last Column of QR Factorisation

Let $Q^{(k)}$ be defined as from Property of Iterates of QR Algorithm with last column $q_n$
Let $e_n=[0,0,\cdots ,1{]}^T$ then

$$q_n=\frac{A^{-k}{e}_n}{||A^{-k}{e}_1|{|}_2}\text{ or }{q}_n=-\frac{A^{-k}{e}_N}{||A^{-K}{e}_1|{|}_2}$$

Proof

Inversing $A^{-k}$ so

$$A^{-k}=(Q^{(k)}{R}^{(k)}{)}^{-1}=(R^{(k)}{)}^{-1}(Q^{(k)}{)}^T$$

Then

$$(A^{-k}{)}^T=Q^{(k)}(R^{(k)}{)}^{-T}=A^{-k}$$

So

$$A^{-k}{e}_n=Q^{(k)}(R^{(k)}{)}^{-T}{e}_n$$

As $(R^{(k)}{)}^{-T}$ is lower triangular then

$$Q^{(k)}(R^{(k)}{)}^{-T}{e}_n\text{ is parallel to }{q}_n$$

Link to original

Eigenvalue Algorithm

Let $A=(a_{ij})$ be a $n\times n$ symmetric matrix

For $m=n,n-1,\cdots ,2$

While $a_{m-1,m}>\mathrm{tol}$
Let

$$\begin{array}{rl}& [Q,R]=\mathrm{qr}(A-a_{m,m}I)\\ & A=RQ+a_{m,m}I\end{array}$$

End while

Let eigenvalue ${\lambda }_m$ be defined by

$${\lambda }_m=a_{m,m}$$

Redefine $A$ as

$$A=\text{leading }m-1\text{ by }m-1\text{ submatrix of }A$$

End for

Let eigenvalue ${\lambda }_1$ be defined by

$${\lambda }_1=a_{1,1}$$

Note that $\mathrm{tol}$ is a very small number to check for convergence to $0$

Link to original

Roots of Polynomials through Eigenvalues

Let

$$p(x)=\sum _{i=0}^n{c}_i{x}^i$$

be a $n$-degree polynomial

Consider companion matrix for $p(x)$ defined by

$$C=\left(\begin{array}{ccccc}-\frac{c_{n-1}}{c_n}& -\frac{c_{n-2}}{c_n}& \cdots & -\frac{c_1}{c_n}& -\frac{c_0}{c_n}\\ 1& 0& \cdots & 0& 0\\ 0& 1& \cdots & 0& 0\\ 0& 0& \ddots & 0& 0\\ 0& 0& \dots & 1& 0\end{array}\right)$$

Then eigenvalues of $C$ are the roots of $p(x)$

Proof

If $p(\lambda )=0$ then

$$Cx=\lambda x$$

where

$$x=[{\lambda }^{n-1},{\lambda }^{n-2},\cdots ,\lambda ,1{]}^T$$

as characteristic polynomial is

$${\chi }_C(\lambda )=\det (\lambda I-C)=\frac{p(\lambda )}{c_n}$$

Link to original