Write a routine that, given a matrix AM×M, and a number n < m, computes the
matrix and the matrix e that appear in the Arnoldi Method (which is the algorithm
QN SN
that underlines the GMRES). Note that e is ( + 1) . Make it square by deleting its
SN n × n
last row. Denote this new matrix by SN′.
Then choose a random matrix A of order 100 × 100. Using MATLAB find the spectrum of this matrix, and graph the absolute values of the eigenvalues.
Compare now σ(A) to σ(SN′), for different (small) values of n. Draw conclusions concerning (i) how fast σ(SN′) converges to σ(A), and (ii) the ”type” of eigenvalues in σ(A) which are actually approximated by σ(SN′) (for a small n).
Turn in your code, the output of your experiment, and your observations.
Let I1, I2, I3 be three intervals of length ε centered around 4, 5 and 10 respectively. Choose randomly 100 eigenvalues from the union of the three intervals, and create a matrix A whose spectrum are these 100 numbers (first, create a diagonal matrix D with the above
eigenvalues, and then define A = P DP −1, for some random, well-conditioned, P .) Let b ∈ IR100 be a randomly chosen vector. Use your routine in Q. 1 in order to write a routine that implements the GMRES method for solving the system Ax = b:
Use first MATLAB and find x directly
Apply GMRES for n = 5, 10, 20, 90. For each case, check accuracy.
Turn in your code, the output, and your observations. Try to include in your observations the speed of convergence, and to compare, if possible, to the theory studied in class.
Note: there is a parameter ε here. You can play with ε and see how its choice affects the speed of convergence.
In this question, you investigate the power of the SVD.
Create a random 30 × 10 matrix B. Then, multiply your matrix B by a matrix C10×10, such that the entries in the first two rows of C are, say, k times larger than the entries in the other rows. Denote A = BC.
Use the SVD in order to find the two dominant singular vectors of A (i.e., the first two columns of U in A = U ΣV ′). Try to draw connections between A and those singular vectors. Note that your experiment involves a parameter k, so make sure you run a few experiments with different values of k.
