CS513, Spring 14Prof. RonAssignment #4Due April 3, 2014General: you are not allowed in this assignment to u se the Matlab command A\b for findinga solution of a linear system. Also, the assignment will require you to solve triangular systems ofequations. Wh en you write a code for that, you will get 5% extra credit, if you shorten that codeby u sing the Matlab notation A(:,j) for the jth column of the matrix A.(1) In this question, you are asked to develop an algorithm for solving a symmetric linearsystem.(a) You are given a linear system Ax = b, A symmetric and n on -singular. Prove that Gausselimination without pivoting preserves the symmetry of A in the following sense: after i eliminationsteps, the (n − i) × (n − i) lower right portion of the matrix is still symmetric. (Hint: do a smallexample to see what happens.)(b) Use (a) in ord er to modify the Gauss elimination method for LU factorization for a symmetricA. Your new algorithm should obtain the correct L and U without modif y ing the elements ofA below the diagonal. Write a Matlab code for that algorithm. Your code will be used in Q.2.Submit a well-docum ented printout of your code and explain (on a s eparate sheet), how you avoidedprocessing the lower portion of the matrix.(c) Find the complexity of your algorithm (remember that the complexity of Gauss elimination forgeneral matrices is n3/3).(d) Test your observation in (c): run your algorithm on 2 − 3 examples of symmetric matricesof different sizes (see Q.2), and run on those matrices the Gauss elimination algorithm from Q.2.Check the tic-toc count for each run (run tic-toc about 100 times and average in order to get areliable reading) and compare. Compare your experiment here with your analysis in (c).(2) I n this q uestion you compare three algorithms for solving linear systems of equations. Oneof the main points of the q uestion is to experiment with the notions of conditioning and stability,and to be able, eventually, to distinguish between the two. A good answer should not only consistof a successful code, but should demons trate your ability to digest th e notions of stability andconditioning via the numerical experiments.The three algorithms are(a) LU factorization using Gauß elimination (without pivoting) and then solving the so-obtained triangular systems.1(b) LU factorization usin g Matlab’s lu routine.(c) LU using full pivoting: full pivoting means that you bring to the pivot location the largestentry (in absolute value) among all the entries that are available. You do that by permuting rowsand columns.Next we generate various different matrices A. Some choices are given below(aij) = (1i+j−1)(aij) = (ij−1)To these choices add two of your own, an d also you need to generate at least four r an dommatrices (use Matlab’s rou tin e rand), and also some symmetric random matrices (an easy way togenerate a sym metric matrix is to take a square matrix B and to define A := B +B′.) Furthermore,you may play with the order of each matrix by specifying different orders.In order to associate A with b and x, choose first x (take convenient vectors like x = (1, ..., 1) orx = (1, 2, ...)). Then compute b simply by multiplying Ax. Then “forget” your x (save the originalx for error analysis).Now you are ready to go: apply to each one of the (many) pairs (A, b) each of the threealgorithms and solve for x. Save then A, b, x1, x2, x3, e1, e2, e3, where xi’s are the three (different?)solutions you obtained for the system, and ei’s are the corresponding errors. (If you incorporatecorrectly you r algorithm from Q.1 into the experiment here, you will get 5% extra credit).The issues now are the cond itioning of each system Ax = b, the stability of the algorithm thatsolves the sy stem, and the complexity of the algorithm. From all the examples you r an , choose5 which in your opinion represent the issues in the best manner. Turn in your well-documentedcodes, the output (for these 5 cases you’ve ch osen), and for each one of them discuss br iefly theissue.What did you learn from this assignment about the conditioning issue and the stability issuewhen A is a random matrix?Keep your code handy. Our TA may ask you to send him the code in order to try it himself.(3) This qu estion deals with deflation of eigenvectors. You are given the matrixA =309 228 −24060 −117 51012 6 298/49,and are told that the vector v = [6 3 2]′is an eigenvector of A.(i) Deflate v from A.(ii) Find (say, directly) the eigenvectors of the 2X2 deflated matrix.(iii) Use (ii) is order to find an eigenbasis of A to R3(i.e., a basis for R3made of eigenvectors ofA).(iv) Diagonalize A, i.e., wr ite it in the form P