Goals: The goal of this assignment is to implement and validate several DIRECT and several ITERATIVE METHODS for solving systems of linear algebraic equations as modular codes or functions that you can call in matlab. Problem Description: Given an nn Matrix A and a vector b your codes should solve the matrix equation Ax=b for the unknown vectors x. You will implement the following algorithms Direct Methods: Cramer's Rule, Gauss Elimination, LU factorization ( you can use matlab's LU function for this) Iterative Methods: Gauss-Seidel, Jacobi's Method, Successive Over Relaxation. Each code should be implemented such that given an nn matrix A and an nx1 vector b it solves Ax=b, for the n1 vector x.. For the direct methods the only arguments are A and b e.g. MyCramer(A,b) returns x. Your methods should be compared to known solutions and to MATLAB's methods for solving the system. Overview: For an nn matrix A, an n1 vector x and an n1 solution vector b we can do the following: For any random A and random x we can compute b and pretend we never knew x. For example: (these are not actual matlab commands and there may be better choices than just random values for A and x ) n= dimension to test A= gallery('matrixtype', n ) xsoln = random (n,1) b=Axsoln; Then solving the system with (A,b) should give you x Specifically Given A and b the solution xmatlab can be determined by matlab as x matlab =Alb or x matlab =inv(A)bx matlab = linsolve (A,b) Direct Methods should run similar to myCramerSol = myCramer (A,b) myGaussElimSol = myGaussElim (A,b) myLUSol = myLU (A,b) Iterative methods should run similar, Iter =1000; tol =1e10; (use whatever values here seem appropriate) myGSsol = myGS (A,b, iter, tol ) myJacobisol = myJacobi (A,b, iter, otl ) mySoRSol = mySoR(A,b, iter,tol ) Note that my SOR may have an additional argument "w" The result will be an n1 vector from which you can determine error as follows: Err=(mySolxexact).(mySolxexact)/N Where mySol is any one of the above solutions. NOTEI This assignment has the extra complication that you can stop the interactions after a set number of interactions or after it converges to some tolerance. So how do you setup your error in this case? Results: Evaluate the performance (timing, number of iterations) and accuracy of each of your functions against matlabs routines and the known value of X. Compare your codes to each other and the theoretical expectations of accuracy/timing. You should evaluate your methods for matrices of different sizes nxn where n ncludes a range of small matrices and some large matrices: example n=5,10,15,20,25,50,75,100,200,300,400,500 (use as large a value as possible for each method). You may use larger matrices if your computer obtains solutions in a reasonable time frame. You are free to choose any matrix or matrices you like to test your systems. You might choose some matrices with known structure, see Matlab's "matrix gallery" to pick some matrices HINT: Some functions are provided (mymat and xmasmat) that generate random matrices, that have "good" properties. (diagonally dominant and positive definite....well maybe. Matlab's Gallery may be a wiser choice. HINT: Be aware that the ITERATIVE methods only work for very specific types of matrices. e.g. diagonally dominant matrices are required for the iterative methods to be guaranteed to converge. HINT: There are to different types of methods: iterative and direct. You should structure you paper to include two subsections in Methods (direction and interactive) and Results (direct and interactive) You may combine the analysis into one set of graphs that includes both types of methods
