Numerical Analysis II 1

Assignment

Submitted to: Mam Gul Sana

Submitted by: Group # 1

Aleeha Rauf (3)

Aman Fatima (5)

Amna Saif (6)

Inam Kausar (29)

Isha Fatima (31)

Laiba Zafar (37)

Mahnoor Khalid (41)

Course Title: Numerical Analysis II

Course Code: MTH-462

Program: BS (MA) 8TH

Government College Women University Faisalabad

 Numerical Analysis II 2

Table of Content

 Eigenvalue Problems and Eigenvectors…………………3-6

 Estimation of Eigenvalue Problems………………………7

 Power Method……………………………………………7-10

 Inverse Power Method……………………………………10-14

 QR Factorization Method………………………………..15-18

 Shifted Method……………………………………………19-20

 Gershgorian Theorem……………………………………..21-23

 Applications of Gershgorian Theorem…………………….23-24

 References………………………………………………….24
 Numerical Analysis II 3

Eigenvalues and eigenvectors

An eigenvalue of a square matrix A=[𝑎𝑖𝑗 ] nxn is a number a such that the vector equation
𝐴𝑋 = 𝜆𝑋
has a non-zero solution vector X. The solution vector X is then called an eigenvector of the matrix. A
corresponding to the eigenvalue λ. The set of all eigenvalues of a matrix is called the spectrum of the
matrix. An eigenvalue is also called a characteristic value or latent root. Likewise, an eigenvector also
called a characteristic vector or latent vector.
𝜆 is an eigenvalue of an nxn matrix A if and only if
det(𝐴 − 𝜆𝐼 ) = 0
Thus, all the eigenvalues of A can be determined as the roots of the characteristic equation det(𝐴 − 𝜆𝐼 ) =
0. The nth degree polynomial det⁡(𝐴 − 𝜆𝐼) is called the characteristic polynomial of A. An eigenvalue of A
can be real or complex, and repeated/multiple, as well. Hence, there could be at most n distinct eigenvalues
of A. Once an eigenvalue λ is known, an eigenvector corresponding to λ can be determined by solving the
homogeneous system
(𝐴 − 𝜆𝐼 )𝑋 = 0
Remark:
The problem of finding eigenvalues and corresponding eigenvectors for a given square matrix is called as
eigenvalue problem, more precisely matrix eigenvalue problem.
Remark:
Suppose that 𝜆1 , 𝜆2 , … , 𝜆𝑛 are the eigenvalues of an nxn matrix A=(𝑎𝑖𝑗 ). The following are some important
results about eigenvalues:
 Trace(A)= sum of all the diagonal entries of A= ∑𝑛𝑖=1 𝑎𝑖𝑗 = ∑𝑛𝑖=1 𝜆𝑖
 Det(A)= determinant of A=𝜆1 , 𝜆2 , … , 𝜆𝑛 = ∏𝑛𝑖=1 𝜆𝑖
 Spectral radius of A =P(A)=max(|𝜆1 |, |𝜆2 |, … , |𝜆𝑛 |) = max(|𝜆𝑖 |) , 𝑤ℎ𝑒𝑟𝑒⁡1 ≤ 𝑖 ≤ 𝑛.

Remark: For each distinct eigenvalue 𝜆𝑗⁡ of a matrix A, there exists at least one eigenvector corresponding
to 𝜆𝑗 .

Remark:
If a distinct eigenvalue 𝜆𝑗 , of a matrix A has (algebraic) multiplicity 𝑚𝑗 , then there exist at most 𝑚𝑗 linearly
independent eigenvectors corresponding to 𝜆𝑗 . The number of such linearly independent eigenvectors is called
geometric multiplicity of 𝝀𝒋 . The set of all the linearly independent eigenvectors corresponding to 𝜆𝑗 form a
basis of a vector space called the eigenspace. Thus, A has k number of eigenspaces corresponding to k distinct
eigenvalues.
Remark: If 𝜆1, 𝜆2, … , 𝜆𝑘 ⁡ are the distinct eigenvalues of a matrix A with corresponding eigenvectors
𝑋1 , 𝑋2 , … , 𝑋𝑘 respectively, then the said eigenvectors are linearly independent.
 Numerical Analysis II 4

Remark: If X is an eigenvector, corresponding to an eigenvalue λ of a matrix A, then any scalar multiple

ẞX is also an eigenvector of A corresponding to λ. Because,
Α(βΧ) = β(ΑΧ) = β(λΧ) = λ(βΧ)

Problem 1:
Find all the eigenvalues and eigenvectors of the following matrix:
4 1 0
𝐴 = [2 5 0]
7 2 1
Solution:
The characterstics polynomial of the matrix A is given as by,
P(λ) = det(𝐴 − 𝜆𝐼 )
4−𝜆 1 0
=| 2 5−𝜆 0 | = (4 − 𝜆)[(5 − 𝜆)(1 − 𝜆) − 0] − 2(1 − 𝜆) + 0
7 2 1−𝜆
= (1-λ)[(4-λ)(5-λ)-2] =(1-λ)(𝜆2 -9λ+18)
= (1-λ)(λ-6)(λ-3)
The roots of P(λ) are the eigenvalues of the matrix A, and are as follows:
𝝀𝟏 = 𝟏, 𝝀𝟐 = 𝟑, 𝝀𝟑 = 𝟔
Finding an eigenvector corresponding to 𝝀𝟏 = 𝟏:
An eigenvector, say 𝑉1⁡ , can be determined by solving the following system:
(𝐴 − 𝜆1 𝐼 )𝑉1 = 0
4 − 𝜆1 1 0 𝑣1 0
[ 2 5 − 𝜆1 0 ] [𝑣2 ] = [0]
7 2 1 − 𝜆1 𝑣3 0
3 1 0 𝑣1 0
𝑣
[2 4 0] [ 2 ] = [0] ---------------------(1)
7 2 0 𝑣3 0
Let us solve the linear system (1) by Gaussain elimination method. For this, the argumented matrix is formed
as:
3 1 0 0
[2 4 0 |0]
7 2 0 0
1 −3 0 0
≈ ⁡⁡⁡⁡⁡ [2 4 0 |0] ⁡⁡⁡ ∴ 𝑅𝑜𝑤⁡1 − 𝑅𝑜𝑤⁡2⁡
7 2 0 0
1 −3 0 0
≈ ⁡⁡⁡⁡⁡ [0 10 0 |0] ⁡⁡⁡ ∴ 𝑅𝑜𝑤⁡2 − 2⁡𝑋⁡𝑅𝑜𝑤⁡1⁡⁡⁡ ∴ 𝑅𝑜𝑤⁡3 − 7⁡𝑋⁡𝑅𝑜𝑤1
0 23 0 0
1 −3 0 0
1
≈ ⁡⁡⁡⁡⁡ [0 1 0 |0] ⁡⁡⁡ ∴ (10)𝑋⁡𝑅𝑜𝑤⁡2
0 23 0 0
 Numerical Analysis II 5
1 −3 0 0
[0 1 0 |0] ⁡⁡⁡⁡ ∴ 𝑅𝑜𝑤3 − 23⁡𝑋⁡𝑅𝑜𝑤2
⁡⁡⁡⁡≈⁡
0 0 0 0
Using this form with Eq.1, gives the following system:
1 −3 0 𝑣1 0
[0 1 0] [𝑣2 ] = [0]
0 0 0 𝑣3 0
It implies that: 𝑣2 = 0, 𝑣1 = 3𝑣2 = 0⁡𝑎𝑛𝑑⁡𝑣3⁡ 𝑐𝑎𝑛⁡𝑏𝑒⁡𝑐ℎ𝑜𝑜𝑠𝑒𝑛⁡𝑎𝑟𝑏𝑖𝑡𝑟𝑎𝑟𝑦. 𝐿𝑒𝑡⁡𝑣3 = 1⁡
𝟎
Thus, 𝑽𝟏 = [𝟎]. Similarly, by putting 𝜆2 = 3⁡𝑎𝑛𝑑⁡𝜆3 = 6⁡⁡we get the eigenvectors as:
𝟏
𝟐 𝟓
𝑽𝟐 = [−𝟐] ⁡𝑎𝑛𝑑⁡𝑽𝟑 = [𝟏𝟎]
𝟓 𝟏𝟏
Remarks:
 Spectrum of A= {1,3,6}
 Trace (A)= sum of all the eigenvalues of A = 1+3+6 = 10
 Det(A)= determinant of A = 1 × 3 × 6 = 18
 Spectral radius of A = 𝑚𝑎𝑥(|1|, |3|, |6|) = 6

Example:
4⁡ 2
Let A = [ ]
1 3
Step 1: Find the eigenvalues (𝜆) , Solve the det(𝐴 − 𝜆𝐼 ) = 0

|4 − 𝜆 2 | (
= 4 − 𝜆)(3 − 𝜆) − 2 = 0
1 3−𝜆
𝜆2 − 7𝜆 + 10 = 0
(𝜆 − 5)(𝜆 − 2) = 0
Eigenvalues are: 𝝀𝟏 = 𝟓⁡𝒂𝒏𝒅⁡𝝀𝟐 = 𝟐
Step 2: Find the eigenvectors:
For 𝝀 = 𝟓:
−1 2 𝑥 0
⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡(𝐴 − 5𝐼 )𝑥 = [ ][ ] = [ ]
1 −2 𝑦 0
−𝑥 2𝑦 0
[ ]=[ ]
𝑥 −2𝑦 0
Solve −𝑥 + 2𝑦 = 0⁡
Put 𝒚 = 𝟏⁡𝑤𝑒⁡𝑔𝑒𝑡:
−𝑥 + 2(1) = 0
−𝑥 = −2
𝒙=𝟐
2
So, the eigenvector is: [ ]
1
 Numerical Analysis II 6

For 𝝀 = 𝟐:
𝑥
(𝐴 − 2𝐼 )𝑥 = [2 2] [𝑦] = [0]
1 1 0
2𝑥 2𝑦 0
[ ]=[ ]
𝑥 𝑦 0
Solve 𝑥 + 𝑦 = 0
Put 𝒚 = 𝟏⁡𝑤𝑒⁡𝑔𝑒𝑡:⁡
𝒙 = −𝟏
−1
So, the eigenvector is : [
]
1
Eigenvalues and eigenvectors have various types and properties in numerical methods:

Types of Eigenvalues:
1. Real Eigenvalues: Eigenvalues that are real numbers.
2. Complex Eigenvalues: Eigenvalues that are complex numbers.
3. Distinct Eigenvalues: Eigenvalues that are unique and not repeated.
4. Repeated Eigenvalues: Eigenvalues that have multiplicity greater than 1.

Types of Eigenvectors:
1. Real Eigenvectors: Eigenvectors corresponding to real eigenvalues.
2. Complex Eigenvectors: Eigenvectors corresponding to complex eigenvalues.
3. Orthogonal Eigenvectors: Eigenvectors that are orthogonal to each other.
4. Generalized Eigenvectors: Eigenvectors that satisfy (A - λI)^k v = 0, where k > 1.

Properties of Eigenvalues and Eigenvectors:

1. Eigenvalue Decomposition: A matrix can be decomposed into its eigenvalues and eigenvectors.
2. Diagonalization: A matrix can be diagonalized using its eigenvalues and eigenvectors.
3. Orthogonality: Eigenvectors corresponding to distinct eigenvalues are orthogonal.
4. Determinant: The product of eigenvalues equals the determinant of the matrix.
Applications:
1. Stability Analysis: Eigenvalues help determine the stability of numerical methods.
2. Linear Systems: Eigenvalues and eigenvectors are used to solve systems of linear equations.
3. Principal Component Analysis (PCA): Eigenvectors are used to reduce the dimensionality of datasets.
4. Markov Chains: Eigenvalues and eigenvectors help analyze the long-term behavior of Markov chains.
 Numerical Analysis II 7

Estimation of Eigenvalue Problems

Basic Power Method

Algorithm for the Power Method:

 Start with a column eigenvector [x]i of length n. The vector can be any nonzero vector.

 Multiply the vector [x]i by the matrix [a]. The result is a column vector [x] i + 1 ,

 [x]i + 1 =[a][x]i

 Normalize the resulting vector [x] i + 1 This is done by factoring out the largest element in the vector. The
result is a multiplicative factor times a normalized vector.

 Assign the normalized vector (without the multiplicative factor) to [x] i and go back to first step.

 The iterations continue in this manner until the difference between the vector [x] i and the normalized
vector [x] i + 1 is less than some specified tolerance.

 ||[X]i+1-[x]i || ≤ Tolerance

 The last multiplicative factor is the largest eigen value, and the normalized vector is the associated eigen
vector.

Power Method
1 6 1
Find the largest eigen value and the corresponding eigen vector of matrix A=[1 2 0]
0 0 3
|A-λI|=0

(A-λI)X=0

AX-λX=0

AX=λX

1
Let the initial eigen vector be X0 =[0].Then
0
1st iteration:

1 6 1 1 1+ 0+ 0 1 1
AX0=[1 2 0] [0]=[1 + 0 + 0]=[1]=1[1]
0 0 3 0 0+ 0+ 0 0 0
 Numerical Analysis II 8
1
The first approximation to the eigenvalue is 1 and the corresponding eigen vector is X=[1]
0
1
λ1=1 , X1=[1]
0
2nd Iteration:

1 6 1 1 1+ 6+ 0 7 1
AX1 =[1 2 0] [1]=[1 + 2+ 0]=[3]=7[0.4]
0 0 3 0 0+ 0+ 0 0 0
1
λ2 =7 , X2 =[0.4]
0
3rd Iteration:

1 6 1 1 1+ 2.4 + 0 3.4 1
AX2 =[1 2 0] [0.4]=[1 + 0.8 + 0]=[1.8]=3.4[0.53]
0 0 3 0 0+ 0+ 0 0 0
1
λ3 =3.4 , X3 =[0.53]
0
4th Iteration :

1 6 1 1 1 + 3.18 + 0 4.18 1
AX3 =[1 2 0] [0.53]=[1 + 1.06 + 0]=[2.06]=4.18[0.49]
0 0 3 0 0+ 0+ 0 0 0
1
λ4 =4.18 , X4 =[0.49]
0
5th Iteration:

1 6 1 1 1 + 2.94 + 0 3.94 1
AX4=[1 2 0] [0.49]=[1 + 0.98 + 0]=[1.98]=3.94[0.5]
0 0 3 0 0+ 0+ 0 0 0
1
λ5 =3.94 , X5 =[0.5]
0
6th Iteration:

1 6 1 1 1+ 3+ 0 4 1
AX5 =[1 2 0] [0.5]=[1 + 1+ 0]=[2]=4[0.5]
0 0 3 0 0+ 0+ 0 0 0
 Numerical Analysis II 9
1
λ6 =4 , X6 =[0.5]
0
1
Hence the largest eigen value is 4 and the corresponding eigen vector is[0.5].
0
Example:

1 6 1
Find all the largest eigen value of A=[1 2 0] and point out the smallest eigen value.
0 0 3
Solution:

Formula:

Smallest eigen value of A=largest value of B+largest value of A

Where B=A-λI

λ=largest eigen value of matrix A

1 6 1 1 0 0
B=[1 2 0]-4 [0 1 0]
0 0 3 0 0 1
1 6 1 4 0 0 −3 6 1
[1 2 0]- [0 4 0]= [ 1 −2 0]
0 0 3 0 0 4 0 0 −1
Now we have to find the largest eigen value of B.

1
Starting with X0=[0]
0
1st iteration:

−3 6 1 1 −3 + 0 + 0 −3 1
BX0=[ 1 −2 0 ] [0]=[ 1 + 0 + 0]=[ 1 ]=-3[−0.33]
0 0 −1 0 0+ 0+ 0 0 0
1
λ1=-3 , X1=[−0.33]
0
2nd Iteration:

−3 6 1 1 −3 − 1.98 + 0 −4.98 1
BX1 =[ 1 −2 0 ] [−0. 33]=[ 1 + 0.66 + 0]=[ 1.66 ]=-4.98 [−0.33]
0 0 −1 0 0+ 0+ 0 0 0
 Numerical Analysis II 10
1
λ2 =-4.98 , X2 =[−0.33]
0
We observe that

X2 = X1

1
The largest eigen value of B is -4.98 and the corresponding eigen vector is [−0.33]
0
Hence ,

Smallest eigen value of A is = Largest eigen value of B +Largest value of A

= -4.98 + 4

= -9.8 ≈-1

Now

λ1=1

λ2=4

λ3 =?

Sum of all the diagonal elements of matrix A = sum of all eigen value of matrix A

1+2=3=4+(-1)+λ3

6-3=λ3

3=λ3

λ1=-1

λ2=4

λ3 =3

Hence smallest eigen value of A=-1.

Inverse Power Method

The inverse power method is an iterative technique to used to determine the dominant eigenvalue of a
matrix i.e. the eigenvalue with the smallest [Link] is essentially a variation of the Power Method, but
instead of multiplying the matrix directly, it uses the inverse of the matrix to find the eigenvalue closest to
zero.
 Numerical Analysis II 11

Procedure:

For an n×n matrix A, the smallest eigenvalue 𝜆𝑛 where |𝜆1 | > |𝜆2 | >. . . . > |𝜆𝑛 | and its corresponding
eigenvalue 𝑉𝑛 can be obtained by Inverse Power Method.

To implement the method the system:

AV -λV =0

AV= λV

Multiplying both sides with 𝐴−1 ,

A𝐴−1 V=⁡λ⁡𝐴−1 V ∵ A𝐴−1 =I

IV =⁡λ⁡𝐴−1 V ∵ VI=V=IV

V=⁡𝛌⁡𝑨−𝟏 V

Hence, the eigenvalue can be calculated from the eigenvector in an iterative manner with:

⁡𝐴−1 {𝑉 (𝑘) }
{𝑉 (𝑘+1)} =
𝛌𝑘+1

This iteration requires an initial eigenvector {𝑉 (0) } and iterate untill |𝛌𝑘+1 − 𝛌𝑘 | < 𝜀 .The smallest
1
eigenvalue is given by 𝛌=𝛌
𝑘+1

In engineering, it is also named as Standard matrix iteration method. This is due the inverse power method
gives the lowest eigenvalue which is the standard information in vibration.

 Why we use Inverse Power Method for smallest eigenvalue of a matrix?

The inverse power method is used to find the smallest eigenvalue of a matrix because the eigenvalues of the
inverse of a matrix are the reciprocals of the eigenvalues of the original matrix. By applying the power
method to the inverse of the matrix, we effectively find the largest eigenvalue in magnitude of the inverse
matrix, which corresponds to the smallest eigenvalue in magnitude of the original matrix.

Example:
4 1 2
Given A = [1 0 1]
2 1 4
Find the smallest eigenvalue and its corresponding eigenvector using the inverse power method.
 Numerical Analysis II 12
1
Take 𝑉 (0)=[1] and iterate untill |𝛌𝑘+1 − 𝛌𝑘 | <0.005.
0

Solution:
4 1 2 1
Given that A = [1 0 1] and 𝑉 (0) =[1]
2 1 4 0
Now we will first find 𝐴−1 ,
1
𝐴−1 = 𝑑𝑒𝑡𝐴⁡ 𝐴𝑑𝑗⁡𝐴

4 1 2
det A=|1 0 1| =4(0-1)-1(4-2)+2(1-0)=-4-2+2=-4
2 1 4
Now, for 𝐴𝑑𝑗⁡𝐴

−1 −2 1
𝐴𝑑𝑗⁡𝐴 =[−2 12 −2]
1 −2 −1
−1 −2 1
−1 1
𝐴 = −4⁡ [−2 12 −2]
1 −2 −1
0.25 0.5 −0.25
𝐴−1 = [ 0.5 −3 0.5 ]
−0.25 0.5 0.25

0 iteration:
The iterative formula of inverse power method is :

⁡𝐴−1 {𝑉 (𝑘)}
{𝑉 (𝑘+1) } = ⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡(1)
𝛌𝑘+1

Put k=0 in (1)

⁡𝐴−1 {𝑉 (0) }
{𝑉 (1) } = ⁡⁡⁡⁡
𝛌1
 Numerical Analysis II 13
0.25 0.5 −0.25 1 0.25 + 0.5 + 0 0.75
−1 (0) ] [ ]=[ ]=[
𝐴 𝑉 =[ 0.5 −3 0.5 1 0.5 − 3 + 0 −2.5]
−0.25 0.5 0.25 0 −0.25 + 0.5 + 0 0.25

𝛌1 = -2.5 (Largest Absolute value from 𝐴−1 𝑉 (0) )

0.75
[−2.5] −0.3
⁡𝐴−1{𝑉 (0)} 0.25
𝑉 (1) = ⁡= =[ 1 ]
𝛌1 −2.5
−0.1
Now we proceed towards next iteration to get the smallest eigenvalue.

1st iteration:
The iterative formula of inverse power method is :

⁡𝐴−1 {𝑉 (𝑘)}
{𝑉 (𝑘+1) } = ⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡
𝛌𝑘+1

Put k=1

⁡𝐴−1 {𝑉 (1) }
{𝑉 (2) } = ⁡
𝛌2

0.25 0.5 −0.25 −0.3 −0.075 + 0.5 + 0.025 0.45

𝐴−1 𝑉 (1) =[ 0.5 −3 0.5 ] [ 1 ]=[ −0.15 − 3 − 0.05 ]=[−3.2]
−0.25 0.5 0.25 −0.1 0.075 + 0.5 − 0.025 0.55

𝛌2 = -3.2(Largest Absolute value from 𝐴−1 𝑉 (1) )

0.45
[−3.2] −0.1406
⁡𝐴−1{𝑉 (1)} 0.55
𝑉 (2) = ⁡= =[ 1 ]
𝛌2 −3.2
−0.1719
Now, |𝛌𝑘+1 − 𝛌𝑘 | < 𝜀

Put k=1

|𝛌2 − 𝛌1 |=|−3.2 − (−2.5)| = 0.7 > 0.005

Since, the approximation error is greater than the error tolerance we proceed towards next iteration.

2nd iteration:
The iterative formula of inverse power method is :

⁡𝐴−1 {𝑉 (𝑘)}
{𝑉 (𝑘+1) } = ⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡
𝛌𝑘+1

Put k=2

⁡𝐴−1 {𝑉 (2) }
{𝑉 (3) } = ⁡
𝛌3
 Numerical Analysis II 14
0.25 0.5 −0.25 −0.1406 −0.03515 + 0.5 + 0.42975 0.5078
−1 (2) ] [ ]=[ ]=[
𝐴 𝑉 =[ 0.5 −3 0.5 1 −0.0703 − 3 − 0.08595 −3.1563]
−0.25 0.5 0.25 −0.1719 0.03515 + 0.5 − 0.42975 0.4922

𝛌3 = −3.1563 (Largest Absolute value from 𝐴−1 𝑉 (2) )

0.5078
⁡[−3.1563] −0.1609
⁡𝐴−1{𝑉 (2)} 0.4922
𝑉 (3) = ⁡= =[ 1 ]
𝛌3 −3.1563
−0.1559
Now, |𝛌𝑘+1 − 𝛌𝑘 | < 𝜀

Put k=2

|𝛌3 − 𝛌2 | = |−3.1563 − (−3.2)| = 0.0437 > 0.005

Since, the approximation error is greater than the error tolerance we proceed towards next iteration.

3rd iteration:
The iterative formula of inverse power method is :

⁡𝐴−1 {𝑉 (𝑘)}
{𝑉 (𝑘+1) } = ⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡
𝛌𝑘+1

Put k=3

⁡𝐴−1 {𝑉 (3) }
{𝑉 (4) } = ⁡
𝛌4

0.25 0.5 −0.25 −0.1609 −0.040225 + 0.5 + 0.038975 0.49875

𝐴−1 𝑉 (3) =[ 0.5 −3 0.5 ] [ 1 ] = [ −0.08045 − 3 − 0.07795 ]=[−3.1584]
−0.25 0.5 0.25 −0.1559 0.040225 + 0.5 − 0.038975 0.5013

𝛌4 = -3.1584 (Largest Absolute value from 𝐴−1 𝑉 (3) )

0.49875
[−3.1584 ] −0.1579
⁡𝐴−1{𝑉 (3)} 0.5013
𝑉 (4) = ⁡= =[ 1 ]
𝛌4 −3.1584
−0.1587
Now, |𝛌𝑘+1 − 𝛌𝑘 | < 𝜀

Put k=3

|𝛌4 − 𝛌3 |=|−3.1584 − (−3.1563)| = 0.002 < 0.005

−0.1579
Hence, the smallest eigenvalue is given by⁡𝛌4 = -3.1584 and its corresponding eigenvector is [ 1 ].
−0.1587
 Numerical Analysis II 15

QR Method

In this QR factorization method, matrix A is decomposed as

A=QR
Where Q is the orthonormal matrix (orthogonal) and R is the upper triangular matrix. Computing the
QR decomposition by using Gram-Schmidt process.

Working Procedure:
Let A be a matrix of order m×n (m rows, n columns)
 Let the column of A be a1, a2, …… an
 Use Gram-Schmidt process to make the columns of A into pairwise orthonormal as follows:
 Define new vector u1, u2, …... un using the columns of A
u1
u1= a1  e1=⁡
||u1 ||
u2
u2= a2 - (a2. e1) e1  e2=⁡
||u2 ||
u3
u3 = a3 - (a3. e1) e1 – (a3. e2) e2  e3=⁡
||u3 ||

.
.
.
un
un = an - (an. e1) e1 - (an. e2) e2 - ……... -(an. en-1) en-1  en=⁡
||un ||

there e1, e2, ……., en are pair-wise orthogonal

Q=[e1 , e2 , … … , en ]  Q-1=QT

How to find R:
We have A=QR
Multiply both side with Q-1
Q-1 (A)= Q-1 (QR)
=(Q-1Q) R =IR=R
Thus,
R= Q-1 (A) = QTA
Hence an Upper triangular matrix R can be obtained from R= QTA
Finally express the matrix A as A=QR
 Numerical Analysis II 16

Example:
𝟏 𝟏 𝟎
Find QR decomposition of the matrix A =[𝟏 −𝟏 𝟏] using Gram- Schmidt process.
𝟎 𝟏 𝟎

Solution:
Let A=[a1 , a2⁡⁡ , a3 ]

1 1 0
Thus a1 =[1] , a2 =[−1]⁡ , a3 =[1]
0 1 0
Now we find new vector u1, u2,u3 using the columns of A by using Gram-Schmidt process as follow

1
Define u1= a1 =[1]
0
u1
 e1=⁡
||u1 ||

||u1||=√(1² + 1²) = √2
u1
e1 =
√2

1
√2
e1=[ 1 ]
√2
0
u2= a2 - (a2. e1) e1
1 1
1 1 √2 √2
=[−1]⁡–([−1] . [ ]⁡) [ 1 ]
1
1 1 √2 √2
0 0
1
1 √2 1
=[−1] − 0⁡. [ 1 ] =[−1]
1 √2 1
0
1
 u2 = [−1]
1
Numerical Analysis II 17
u2
e2 =⁡
||u2 ||

||u2|| = √(1² + (-1)² + 1²) = √3

1
√3
u2 −1
e2 =⁡ e2=
√3 √3
1
[ √3 ]

u3 = a3 - (a3. e1) e1 - (a3. e2) e2

1 1
1 1
0 √3 √3
0 0 √2 √2 −1 −1
=⁡[1] − [1 ] . 1 . [ 1 ] −⁡ [ 1] .
√3 √3
0 0 √2 √2 0 1 1
( [ 0 ]) 0
( [√3]) [√3]
1
1
√3
0 √2
−1 −1
1
= [1] −⁡( ) [ 1 ] −( )
√2 √3 √3
0 √2 1
0 [ √3 ]
−1 1 1 −1 −1
1 0 −⁡ + ⁡
3 2 3 6 6
0 2 1 1 1 1 1
= ⁡[1] − [ 1 ] −
3
= 1 − 2⁡− 3 = 6
or 6
0 2 −1 1 1 2
0 [3] [0 − 0 + 3] [ 3 ] [6]
−1
6
1
u3 =
6
2
[6]

u3 −1 1 2 1
e3=⁡  || u3|| =√( )2 + ( )2 + ( )2 =
||u3 || 6 6 6 √6

−1 −1
6 √6
u3 1 1
e3=⁡ =u3 √6 = √6 =
||u3 || 6 √6
2 2
[6] [ √6 ]
Q=[e1 , e2 , e3 ]
 Numerical Analysis II 18
1 1 −1
√2 √3 √6
1 −1 1
Q=
√2 √3 √6
1 2
[0 √3 √6 ]

Since e1 , e2 , e3 ⁡are pairwise orthonormal

So, Q is orthonormal (orthogonal)

1 1
0
√2 √2
1 −1 1
Q-1=QT=
√3 √3 √3
−1 1 2
[ √6 √6 √6]

To Find R
An upper triangular matrix R is obtained from

R= QTA
1 1
0
√2 √2 1 1 0
1 −1 1
= [1 −1 1]
√3 √3 √3
−1 1 2 0 1 0
[ √6 √6 √6 ]

1
√2 0 √2
−1
R =⁡ 0 √3 √3
1
[0 0 √6 ]

Thus,
1 1 −1 1
√2 0
√2 √3 √6 √2
1 −1 1 −1
A=QR = 0 √3
√2 √3 √6 √3
1 2 1
[0 √3 √6 ] [
0 0
√6 ]

1 1 1 −1 3 4
√2 0 1
√ 2 √2 √3 √6 √6 √12
−1 1 −1 1 √3 −4 √2
𝐴1 = 𝑅𝑄 = 0 √3 =
√ 3 √2 √3 √6 √2 3 6
1 1 2 √2 2
[0 0 √6 ] [
0 √3 √6 ] [ 0 √6 √36]
 Numerical Analysis II 19

Shifted power method

The power method/approach can be used to identify the remaining eigenvalues after the greatest or smallest eigenvalue
is known. The shifted power method uses an important property of matrices and their eigenvalues. Given
[ a][x] =λ1 [x]
If λ1 is the largest (or smallest) eigenvalue obtained by using the power method (or the inverse power method), then the
eigenvalue of a new shifted matrix [a − λ1 I]are
Eig’s A shifted = {𝛌𝟏 − 𝛌𝟏, 𝛌𝟐 − 𝛌𝟏 , 𝛌𝟑 − 𝛌𝟏 , … 𝛌𝐧 − 𝛌𝟏 }={0, 𝛌𝟐 − 𝛌𝟏 , 𝛌𝟑 − 𝛌𝟏 , … 𝛌𝐧 − 𝛌𝟏 }
This can be seen easily because the eigenvalues of [a-λ1 I]are found from
[a − λ1 I][x] = a[x] … , …⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡(i)
 Eq. (i)could be simplified as
 [a − λ1 I][x] = a[x]⁡⁡
 [a][x] − λ1 [x] = a[x]
 λ[x] − λ1 [x] = a[x]
 (λ − λ1 ) = a[x]
Where the a′s are the eigenvalues of the shifted matrix [a − λ1 I]. Equation(i) becomes
(𝛌 − 𝛌𝟏 ) = 𝐚[𝐱]
Where λ = λ1 , λ2 , λ3 , … λn is an eigenvalues of matrix [a] therefore, the eigenvalues of the shifted matrix
a = {λ1 − λ1, λ2 − λ1 , λ3 − λ1 , … λn − λ1 } = {0, λ2 − λ1 , λ3 − λ1 , … λn − λ1 }
The eigenvalues of the shifted matrix [a − λ1 I]are the same as the eigenvectors of the original matrix [a].
The largest eigenvalues of the shifted matrix becomes λB = λn − λ1
The smallest eigenvalues of the shifted matrix becomes λn = λB + λ1
All the other eigenvalues can be determind by repeating this process k-2 times , where at each times the shifted
matrix [a − λk I],where λk is the eigenvalues obtained from pervious shift.
Steps:
1. We need a shifted factor λ1 , where λ1 dominanteigenvalue⁡(by⁡power⁡method)
2. Find matrix B, B= a − λ1 I, where⁡I = identity⁡matrix
3. Use power method to get λB (the dominant eigenvalue for matrix B)
4. Find λn :⁡⁡λn = λB + λ1 ⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡
5. The associated eigenvalue to λn ⁡𝑖𝑠⁡𝑔𝑖𝑣𝑒𝑛⁡𝑏𝑦⁡⁡⁡⁡⁡⁡⁡⁡𝑣𝑛≅⁡ ⁡𝑣𝑏
Example:
Determine the smallest eigenvalues of the following matrix:
𝟒 𝟐 −𝟐
[
𝐀 = −𝟐 𝟖 𝟏 ] using shifted power method and start with the vector x=[0 0 1] T and
𝟏 𝟒 −𝟒
𝛌 =7.6898.
Solution:
[A − λI][x]i = [x]i+1

Iteration no 1: for i=1

 Numerical Analysis II 20
T
Initial vector x1=[0 0 1] and λ1 =7.6898.
[A − λI][x]1 = [x]2
4 2 −2 1 0 0 0 −2
[x]2 = [[−2 8 1 ] − 7,6898 [0 1 0]] [0] = [ 1 ]
1 4 −4 0 0 1 1 −11.6898

0.1711
=−11.6898 [−0.0855]
1
Error in solution:
Error = [0.5 0.0776 1]T- [0 0 1]T =0.1711
Iteration n.02: for i=2
Now normalized vector [x]T= [ 0.1711 -0.0855 1 ] T is multiplied by [A − λI]
[A − λI][x]2 = [x]3
−3.68998 2 −2 0.1711 −2.8023
[x]3 = [ −2 0.3102 1 ] [−0.0855 ] = [ 0.6313 ]
1 4 −11.6898 1 −11.8607
0.2363
=-11.8607[−0.05322]
1
[x]3 = [0.2363 -0.05322 1 ]T⁡
Error in solution:
Error =[0.2363 -0.05322 1 ]T - [0.5 0.0776 1]T =0.0652
After 5 iterations
Iteration no 8: Now normalized vector [x]7= [ 0.2633 -0.0398 1 ] T is multiplied by [A − λI]
[A − λI][x]7 = [x]8
−3.68998 2 −2 0.2633 −3.0512
[x]8 = [ −2 0.3102 1 ] [−0.0398 ] = [ 0.4610 ]
1 4 −11.6898 1 −11.5857
0.2634
= -11.5857[−0.0398]
1
0.2634
[x]8 = [−0.0398]
1
Error in solution:
0.2634 0.2633
Error = [−0.0398 ] − [−0.0398] = 0.0000
1 1
The largest eigenvalues=λB =-11.5857
The smallest eigenvalues =λ8 = λB + λ1 ⁡⁡
λ8 = −11.5857 + 7.6878
⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡= ⁡ −3.8959⁡
 Numerical Analysis II 21

Gerschgorin circle theorem

An important tool in eigenvalue approximation is the ability to localize the eigenvalues, and the most important tool
in eigenvalue localization is Gerschgorin's theorem.
This theorem explicitly constructs n disks in the complex plane with centers at the diagonal elements of the matrix;
and all the eigenvalues of the matrix lie in the union of these disks.

History of the Gerschgorin Circle Theorem:

The theorem is named after the Belarusian mathematician Semyon Aranovich Gershgorin (1901–1933). He introduced
it in 1931 in his paper titled “Über die Abgrenzung der eigenwerte einer Matrix”(On the Delimitation of the
Eigenvalues of a Matrix).
In this paper, Gershgorin proposed a simple yet powerful way to estimate the location of eigenvalues of a square
complex matrix by placing them within certain discs (now called Gershgorin discs) in the complex plane.
Unfortunately, Gershgorin passed away very young, at the age of just 32, but his theorem became a fundamental result
in matrix theory and numerical analysis.

Statement:
Let A be an n×n matrix. For each k=1,2,3,…,n we define pk as:
𝑛

𝑃𝑘 = ∑|𝑎𝑘𝑗 |
𝑗=0
𝑘≠𝑗

And Dk denotes the closed discs in complex plane with center a kk and radius pk. Tℎ𝑎𝑡⁡𝑖𝑠⁡
𝐷𝑘 = ⁡ {⁡𝑧 ∈ ℂ ∶ |𝑧 − ⁡ 𝑎𝑘𝑘 | ≤ pk }
Each eigenvalue of A lies in one of the disks Dk. That is, no eigenvalue of A lies in ℂ\⋃𝑛𝑘=1 𝐷𝑘

Proof:
Let λ be the eigenvalue of A. Then there exists v= {𝑣1 , 𝑣2 , … 𝑣𝑛 } ∈ ℝ𝑛 ⁡𝑎𝑛𝑑⁡𝒗 ≠ 0⁡𝑠𝑢𝑐ℎ⁡𝑡ℎ𝑎𝑡:
Av=λv …(1)
𝐿𝑒𝑡⁡1 ≤ 𝑟 ≤ 𝑛⁡𝑏𝑒⁡𝑠𝑢𝑐ℎ⁡𝑡ℎ𝑎𝑡⁡|𝑣𝑟 | = {|𝑣1 |, |𝑣2 |, … , |𝑣𝑛 |}. 𝑇ℎ𝑒𝑛⁡𝑟𝑡ℎ⁡𝑒𝑞𝑢𝑎𝑡𝑖𝑜𝑛⁡𝑜𝑓⁡(1)𝑖𝑠⁡𝑔𝑖𝑣𝑒𝑛⁡𝑏𝑦:
𝑎𝑟1 𝑣1 + 𝑎𝑟2 𝑣2 + ⋯ + 𝑎𝑟 ,𝑟−1 𝑣𝑟−1 + (𝑎𝑟𝑟 − 𝜆)𝑣𝑟 + 𝑎𝑟 ,𝑟+1 𝑣𝑟+1 + ⋯ + 𝑎𝑟𝑛 𝑣𝑛 = 0⁡⁡⁡⁡⁡⁡ … (𝟐)
From the last equation we get
𝑣1 𝑣2 𝑣𝑟+1 𝑣𝑛
𝜆 − ⁡ 𝑎𝑟𝑟 = 𝑎𝑟1 + 𝑎𝑟2 + ⋯ + 𝑎𝑟,𝑟+1 + ⋯ + 𝑎𝑟𝑛 ⁡⁡⁡⁡… (𝟑)
𝑣𝑟 𝑣𝑟 𝑣𝑟 𝑣𝑟
Taking modulus on both sides and using the triangular inequality (|a+b|≤|a|+|b|) repeatedly we get:
|𝑣1 | |𝑣 | |𝑣 | |𝑣 |
|𝜆 − 𝑎𝑟𝑟 | ≤ |𝑎𝑟1 | + 2 |𝑎𝑟2 | + ⋯ + 𝑟+1 |𝑎𝑟,𝑟+1 | + ⋯ + 𝑛 |𝑎𝑟𝑛 | ⁡⁡⁡… (𝟒)
|𝑣𝑟 | |𝑣𝑟 | |𝑣𝑟 | |𝑣𝑟 |
𝑣
In view of choice of r, the components of Vector v satisfy⁡| 𝑠 | ≤ 1
𝑣𝑟

⁡⁡𝑇ℎ𝑒⁡𝑙𝑎𝑠𝑡⁡𝑒𝑞𝑢𝑎𝑡𝑖𝑜𝑛⁡𝑏𝑒𝑐𝑜𝑚𝑒𝑠:
|𝜆 − 𝑎𝑟𝑟 | ≤ |𝑎𝑟1 | + |𝑎𝑟2 | + ⋯ + |𝑎𝑟,𝑟+1 | + ⋯ + |𝑎𝑟𝑛 | ⁡⁡⁡… (𝟓)
 Numerical Analysis II 22
Observe that the right hand side of the above equation is 𝑝𝑟 . This proves that λ ∈ ⁡𝐷𝑟 .
This completes the proof.

Example:
For the given matrix
4 1 1
[0 2 1]
−2 0 9
The Gerschgorin’s discs are given by:
𝐷1 = ⁡ {⁡𝑧 ∈ 𝐶: |𝑧 − 4||≤ 2}⁡
𝐷2 = ⁡ {⁡𝑧 ∈ 𝐶: |𝑧 − 2||≤ 1}
𝐷3 = ⁡ {⁡𝑧 ∈ 𝐶: |𝑧 − 9||≤ 2}
Draw a picture of these discs and observe that D3 intersect neither D1 not D2. By gerschgorian theorem D 1 has one
eigenvalue and 𝐷2 𝑈𝐷3 has two eigenvalues counting multiplicities.

Remark:
Gerschgorin’s circle theorem is helpful in finding bound for eigenvalues. For the matrix in the above example, any
number z in D₁ satisfies |z|≤6. Similarly any number z in D₂ satisfies |z|≤3, and any number z in D3 satisfies |z| ≤ 11.
Since any eigenvalue λ lies in one of three disks, we can conclude that | λ | ≤ 11.
The main disadvantage of the power method is that, If a given matrix has more than one dominant eigenvalues, then
the method may not converge.
So, for a given matrix, we do not know whether the power method will converge or not.
Also, as the power method is slow we may have to perform reasonably large number of iterations to come to know that
the method is not actually converging.

Corollary:
Since A and A transpose AT has same eigenvalues we conclude that:
Let A be an n×n matrix. For each k=1,2,3,…,n we define 𝑇𝑘 as:
𝑛

𝑇𝑘 = ∑|𝑎𝑘𝑗 |
𝑗=0
𝑘≠𝑗

𝐴𝑛𝑑⁡𝐵𝑘 ⁡𝑑𝑒𝑛𝑜𝑡𝑒𝑠⁡𝑡ℎ𝑒⁡𝑐𝑙𝑜𝑠𝑒𝑑⁡𝑑𝑖𝑠𝑐𝑠⁡𝑖𝑛⁡𝑐𝑜𝑚𝑝𝑙𝑒𝑥⁡𝑝𝑙𝑎𝑛𝑒⁡𝑤𝑖𝑡ℎ⁡𝑐𝑒𝑛𝑡𝑒𝑟⁡𝑎𝑘𝑘 ⁡𝑎𝑛𝑑⁡𝑟𝑎𝑑𝑖𝑢𝑠⁡𝑇𝑘 . 𝑇ℎ𝑎𝑡⁡𝑖𝑠⁡

𝐵𝑘 = ⁡ {⁡𝑧 ∈ ℂ: |𝑧 − ⁡ 𝑎𝑘𝑘 | ≤ 𝑇𝑘 }
𝐸𝑎𝑐ℎ⁡𝑒𝑖𝑔𝑒𝑛𝑣𝑎𝑙𝑢𝑒⁡𝑜𝑓⁡𝐴⁡𝑙𝑖𝑒𝑠⁡𝑖𝑛⁡𝑜𝑛𝑒⁡𝑜𝑓⁡𝑡ℎ𝑒⁡𝑑𝑖𝑠𝑘𝑠⁡𝐵𝑘 . 𝑇ℎ𝑎𝑡⁡𝑖𝑠, 𝑛𝑜⁡𝑒𝑖𝑔𝑒𝑛𝑣𝑎𝑙𝑢𝑒⁡𝑙𝑖𝑒𝑠⁡𝑖𝑛⁡𝑜𝑛𝑒⁡𝑜𝑓⁡𝑡ℎ𝑒⁡𝑑𝑖𝑠𝑘𝑠⁡𝐵𝑘 .
⁡𝑇ℎ𝑢𝑠, 𝑛𝑜⁡𝑒𝑖𝑔𝑒𝑛𝑣𝑎𝑙𝑢𝑒⁡𝑜𝑓⁡𝐴⁡𝑙𝑖𝑒𝑠⁡𝑖𝑛⁡ℂ\ ⋃𝑛𝑘=1 𝐵𝑘 .Suppose that among the disks 𝐵1 , 𝐵2 , … , 𝐵𝑛 , there is a collection of m
disks whose union (denoted by C₁) is disjoint from the union of the rest of the n-m disks (denoted by C2). Then exactly
m eigenvalues lie in C₁ and n-m eigenvalues lie in C2 (here each eigenvalue is counted as many times as its algebraic
multiplicity).

Other statements of Gerschgorin theorem:

 Numerical Analysis II 23

Statement 2:
For any given square matrix A with dimensions n x n, let R i denote the sum of the absolute values of the elements in
the ith row (excluding the diagonal element ai,j
𝑅𝑖 = ⁡ ∑|𝑎𝑖𝑗 |⁡𝑎𝑛𝑑⁡𝑖 ≠ 𝑗

Then, the eigenvalues of the matrix A lie within the union of the circles in the complex plane with centers at the
diagonal elements ai,i and radii Ri.

Statement 3:
Consider the system of linear equations Ax = b where A is a square matrix and b is a vector. If the diagonal elements
of A are nonzero (|ai,i |>0 for all i). And if the matrix B is defined as the matrix A with the ith row divided by the
diagonal element then the system Ax = b a unique solution for any b if and only if the spectral radius of the matrix B is
less than 1.

Applications of Gershgorian Circle Theorem:

It is a powerful tool in linear algebra, particularly for estimating the location of eigenvalues of a
square matrix. It has several practical applications in mathematics, engineering, and computer science.

1. Estimating Eigenvalue Bounds:

Purpose:
Quickly locate where eigenvalues of a matrix are likely to lie.

Application:
Useful when solving systems of equations or analyzing matrix stability without computing
eigenvalues directly.

2. Preconditioning in Numerical Methods:

Gershgorian’s theorem helps in designing preconditioners that improve the convergence of
iterative methods like Jacobi or Gauss-Seidel.

3. Spectral Graph Theory:

In analyzing the Laplacian matrix of graphs, Gershgorian circles help estimate eigenvalue ranges,
useful for understanding graph connectivity or clustering.
 Numerical Analysis II 24

4. Error Bounds in Numerical Computations:

When computing approximate eigenvalues numerically, Gershgorian discs provide a check or
range where the true eigenvalues should lie.

5. Matrix Perturbation Analysis:

Used to estimate how eigenvalues change when a matrix is perturbed slightly, relevant in
sensitivity analysis.

References:
 [Link]

 [Link]

 [Link]

 Simplified Numerical Analysis by DR Amjad Ali 4th Edition

….…..Thank You………