05 - Iteration Methods

Inner Product for Iterative Methods

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

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

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

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$

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$$

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$

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)}$$

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

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

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}$

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$

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$$

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$

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}$$