Description

Programming Assignment 2: System of Linear Equations and Eigenvalues

Program 1
Write a computer program for the solution of a linear system of equations using direct methods, LU decomposition and matrix Inversion.
Initial input screen should have the following choices:
A. Solve a System of Equation
B. Perform a LU decomposition
C. Perform a Matrix Inversion
If A. is chosen, it should ask if the system is tri-diagonal and take the answer in (Y/N)
• If the answer is (Y), it should ask for a file name from where it can read out the following: size n, vectors l, d, u and b. Solve the system using Thomas algorithm and send the solution to an output file.
• If the answer is (N), it should ask for a file name from where it can read out the following: size n, matrix A and vector b. Solve the system using Gauss Elimination with partial pivoting and send the solution to an output file.
If B. is chosen, it should ask if the matrix is symmetric and positive definite and take the answer in (Y/N)
• If the answer is (Y), it should ask for a file name from where it can read out the following: size n, matrix A and vector b. Perform the LU decomposition using Cholesky algorithm and store the matrix L to an output file. Prior to LU decomposition, the program should perform full pivoting. Output should contain a log of all the row and column exchanges performed.
• If the answer is (N), it should ask for a file name from where it can read out the following: size n, matrix A and vector b. It should then give a choice to the user for Doolittle or Crout decomposition, perform the LU decomposition using the chosen algorithm and store the matrices L and U to an output file. Prior to LU decomposition, the program should perform full pivoting. Output should contain a log of all the row and column exchanges performed.
If C. is chosen, it should ask for a file name from where it can read out the following: size n and matrix A. The program should augment an identity matrix of the same size and compute the inverse using the Gauss-Jordon algorithm (without pivoting). The program should store the inverse in an output file.
Test Problems:
1.
4×1 2×2 10
2×1 4x x2  3 11.5
x2 5×3  5
Sample input file
3
4.0 2.0 0.0 10.0
2.0 4.0 1.0 11.5
0.0 1.0 5.0 5.0

Sample output file
Crout method

x
1.5
2.0
0.5

L
4.0 0.0 0.0
2.0 3.0 0.0
0.0 1.0 4.667

U
1.0 0.5 0.0
0.0 1.0 0.3333
0.0 0.0 1.0

 9.3746 3.0416  2.4371x1 9.2333
2. Solve  3.0416 6.1832 1.2163 x2 8.2049
 2.4371 1.2163 8.4429 x3 3.9339

9 3 −2
3. 𝑨=[ 3 6 1 ]
−2 1 9
a) Reduce it to an upper triangular matrix using Gauss Elimination Procedure.
b) Synthesize a lower triangular matrix L and an upper triangular matrix U from the steps of (a) above such that A = LU.
c) Compute A-1 using the LU decomposition obtained in (b).

4. Solve the following system of equation using Thomas algorithm:

2 1 0 0 x1  3 
 1 4 1 0 x2  1 

 0 1 4 1 x3  2 
 0 0 1 2x4 2

5. Consider the following matrix:
10 7 8 7
7 5 6 5
A  
8 6 10 9
 
7 5 9 10
a) Compute A-1
b) Find the solution of Ax=b where, b = [4 3 3 1]T.

Program 2
Write a computer program for estimation of the eigenvalues.
First it should ask for a file name from where it can read out the following: size n and matrix A and approximate relative error tolerance (in %). Then it should give a choice to the user whether (s)he wants only the largest eigenvalue (L) or all eigenvalues (A):
• If the response is (L), program computes the largest eigenvalue using Power method.
• If the response is (A), program computes all the eigenvalues using QR decomposition with Gram-Schmidt algorithm.
Test Problems:
1. Consider the following matrix:
 2 1 0 0 
1 4 1 0 
 
 0 1 4 1
 
 0 0 1 2 
a) Find the eigenvalue of maximum absolute magnitude and the corresponding eigenvector using the Power method with an accuracy of 0.001% of relative approximate error on the eigenvalue.
d) Obtain all the eigenvalues using QR algorithm and compare with those obtained in (a), (b) and (c) above.

Sample input file
4
2.0 -1.0 0 0
-1.0 4.0 -1.0 0
0 -1.0 4.0 -1.0
0 0 -1.0 2
0.001

Sample output files

A. Direct power method (listed below are not the answers to the test problem but just how the answers would like)

Eigenvalue
10.7787

Eigenvector -0.2509
-0.2397
0.9379

Iterations
30

B. QR method

Eigenvalues
10.7788
8.1462
3.0749

Iterations
23

2. Consider the following Matrix:
 7  2 1 
 2 10  2
 
 1  2 7 
3. Consider the following matrix:
3 4 1
3 5 1
 
2 2 1
a) Find the eigenvalue of maximum absolute magnitude and the corresponding eigenvector using the Power method.
d) Obtain the eigenvalues using QR algorithm.

Make a single zip folder with all your program file(s) name it roll_number.zip (e.g., If your roll no. is 123456, the folder name should be ‘P2_123456.zip’). The folder should include –
(i) All the computer program file(s), input file(s) and output file(s)
(ii) A PDF file of the plots and the solution of the test cases given in this assignment.
Send the zip file by e-mail to: eso208.sec*@gmail.com, where * is section number 1-10. Example: for section O5, it is eso208.sec5@gmail.com; for section O10, it is eso208.sec10@gmail.com