Scribd
Upload
48 views5 pages

QR Algorithm for Eigenvalues Explained

The QR algorithm is used to find the eigenvalues of a matrix. It works by iteratively decomposing the matrix into orthogonal and upper triangular matrices using Gram-Schmidt orthogonalization. Each iteration produces a new matrix with the same eigenvalues as the original. As the iterations continue, the matrix converges to a triangular or diagonal form where the diagonal elements are the eigenvalues of the original matrix. The example shows applying this to a 2x2 matrix, decomposing it into orthogonal and upper triangular forms over multiple iterations until it becomes diagonal.

Uploaded by

drake3510
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
48 views5 pages

QR Algorithm for Eigenvalues Explained

The QR algorithm is used to find the eigenvalues of a matrix. It works by iteratively decomposing the matrix into orthogonal and upper triangular matrices using Gram-Schmidt orthogonalization. Each iteration produces a new matrix with the same eigenvalues as the original. As the iterations continue, the matrix converges to a triangular or diagonal form where the diagonal elements are the eigenvalues of the original matrix. The example shows applying this to a 2x2 matrix, decomposing it into orthogonal and upper triangular forms over multiple iterations until it becomes diagonal.

Uploaded by

drake3510
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

QR algorithm for finding eigenvalues of a matrix

See also [Link]

Given matrix
(

with exact eigenvalues as 3,2.

STEP 1: Q R factorization
First let us Q R factorise this matrix where Q is an orthogonal matrix
=
and
is an upper triangular matrix.
To find Q (orthogonal matrix) we write,
(

Now we have to use Gram Schmidt procedure to orthonormalize the


+
basis *
(
|(

| |

(
(

)
)

= ( )

= (

OR

),

( )=(

= ( )

)
)|

Prove that
(
(

=
)

(
(

)
)
)

It is easy to verify that


STEP 2: ITERATIVE PROCEDURE

Start with
Write
Now write

using the ideas in STEP 1

Again find
Now decompose

using the ideas in STEP 1

and so on ..
till
for some large n itself becomes simple enough to be able to
read off its eigenvalues.
BUT THE CRUCIAL POINT OF THIS ALGORITHM IS
for each value of the index k,
the starting matrix
To see this consider the kth iteration.

has the same eigenvalues as

above, we have used the orthogonality of Q.


But
This means,

This means

and

have the same eigenvalues

Why ?
If

is an eigenvector of
insert

with eigenvalue ,
to get,
multiply with

Call
This means
This means
has the same eigenvalue
though the eigenvector is u instead of v

even

Thus successive iterations lead to A-matrices that all have the same
eigenvalues. Since we started with the original matrix A this means
has the same eigenvalue as A.
After many iterations if
becomes triangular or diagonal then these
diagonal elements are themselves the eigenvalues of the original
matrix A,

STEP 3: EXAMPLE CONTINUED

Start with

Write

= (

) (

)(

Now write

using the ideas in STEP 1

Again find

(
(

(
)

Now decompose

)
(

using the ideas in STEP 1

AND SO ON ..
The sequence of matrices is
(
(

)
)

(
= (

)
)

and so on .
We see that slowly the matrix
is becoming an upper
triangular matrix. The exact eigenvalues of
are 3,2.

You might also like