Updated 11/30/15

Note: These homework assignments are subject to revision during the term.
Please check this page regularly for updates.

Homework 0

The following exercises are due Monday, Sept 28:

1. Turn in a pdf to Gradescope.com containing your name and the message "Hello World!"

Homework 1

The following exercises are due Monday, October 5:

Textbook:
Section 1.1: 8, 9, 14, 20
Section 1.2: 4, 16a, 18a,b, 20

Programming:
1. Write a function in Matlab that takes as input two n x n matrices A and B, and returns the product A*B and the number of flops used. Use only programming basics (i.e., not using Matlab's built in matrix multiplication.)
  (a) Write out or print out your program.
  (b) Create cases of your choice with n = 100; 200; 400 to run your function. Write down the number of flops used in each case.

Solutions for selected problems are here and one possible version of the program is here.

Homework 2

The following exercises are due Monday, October 12:

Textbook:
Section 1.3: 4, 17
Section 1.4: 15, 21, 23, 56, 62
Section 1.5: 4, 9, 12

Programming:
1. Write a function in Matlab that takes as input the number n, an n x n upper triangular matrix G, and an n-component column vector b, and returns as output the solution of Gy = b and the number of flops used. Use only programming basics. (This is programming back substitution.)
  (a) Write out or print out your program.
  (b) Create cases of your choice with n = 100; 200; 400 to run your function. Write down the number of flops used in each case. (To create an upper triangular matrix, you can use the command triu(A), where A is some random matrix.)
2. Write a function in Matlab that takes as input the number n and a symmetric tridiagonal matrix given as two vectors: n by 1 vector v representing the main diagonal and (n-1) by 1 vector w representing the upper diagonal. Have this function output the Cholesky factor of the matrix as a vector for the main diagonal and a vector for the upper diagonal and output the number of flops and, separately, the number of square roots used as well. Use only basic programming.
  (a) Write out or print out your function.
  (b) Run the case with v =2*ones(10,1), w = -ones(9,1) and write out or print out all your results.
  (c) Run the case with v =2*ones(100,1), w =-ones(99,1) and write out or print out your results just for the number of flops and square roots used. How many times more flops are used than in the previous case?

Solutions for selected problems are here and the programs here: backwardsub.m, choltrid.m.

Homework 3

The following exercises are due Monday, October 19:

Textbook:
Section 8.1: 14,
Section 8.2: 7 (use the code we wrote in class. You will have to modify it to measure the norm of the residual instead of the norm of x^(k+1)-x^(k).), 12, 15 (again, use the (modified) code from class), 27

Programming:
1. Write a function in Matlab that takes as input a matrix A, a vector b, a maximum number of iterations, a tolerance for convergence and the relaxation constant w. Have this function use SOR to calculate the solution x of Ax=b, using that max number of iterations and tolerance. Assume a starting guess of x=0. Use only basic programming.
  (a) Write out or print out your program.
  (b) Let A be the matrix for the Poisson equation, as we created earlier in class, for a 10x10 grid. Let b be the appropriate vector of 1's. For w=1 (standard Geiss-Seidel), how many iterations does it take to reach a tolerance of 10^-3? For w=1.6? For w=.8?

Solutions for selected problems are here and the program here: SOR.m.

Homework 4

The following exercises are due Monday, October 26:

Textbook:
Section 2.1: 4, 13, 14, 17, 23, 28, 30, 32, 33

Programming:
1. Write a function in Matlab that takes as input a 2 by 2 matrix A and return as output the approximate matrix 2-norm. Compute the approximate matrix 2-norm, by multiplying A by 100 unit vectors, x_k for k=1,2,...,100, pointed in directions (2*pi/100)*k radians. The approximate matrix 2-norm is the maximum of the 100 resultant vector norms, ||A*x_k|| where for a vector v=[c d], ||v|| = sqrt(c^2 + d^2). (Note: this is a conceptual assignment and isn't how mathematicians usually calculate the matrix 2-norm. We'll learn a better way later.)
  (a) Write out or print out your function.
  (b) Run the case of A = [1 2; 3 4] and write out or print out your results.
  (c) Run the case of A = [5 6; 7 8] and write out or print out your results.

Solutions for selected problems are here and the program here: twonorm.m.

Homework 5

The following exercises are due Monday, November 2:

Textbook:
Section 4.1: Math majors should do problem 16, but do not turn it in.
Section 5.2: 2, 13, 14 a, b (not c, d)
Section 5.3: 6, 7, 8, 15
Section 5.3, should do, don't turn in: 13, 14

Programming:
1. Write a function in Matlab that takes as input a square matrix A, a guess for an eigenvalue rho, and a number of iterations and returns as output the eigenvalue and eigenvector found using the shift-and-invert strategy. Use basic programming, except you may use Matlab's built in matrix computation commands such as addition, subtraction, "division," and multiplication, if needed.
  (a) Write out or print out your function.
  (b) Run the case of A = [1 2; 3 4] with initial guess rho=-1 and 100 iterations and write out or print out your results.
  (c) Run the case of A = [5 2 2; -2 -1 -3; 7 1 -4] with initial guess rho=1 and 100 iterations and write out or print out your results.

Solutions for selected problems are here and the program here: SAI.m.

Homework 6

The following exercises are due Monday, November 9:

Textbook:
Section 8.3: 10, 12, 17 a, 19 a,b,c, 20, 22
Section 8.4: 7 a, 8 a (look at b, c, but don't have to do them), 12

Programming:
1. Write a function in Matlab that takes as input a symmetric positive definite matrix A, the right hand side vector b, initial guess x, and number of iterations, and returns as output the solution of Ax=b as found by performing the conjugate-gradient method as found in (8.7.1). It will be easiest to program the exact algorithm found there, though you will have to change notation and names of variables so that MATLAB can understand it. Use basic programming, along with Matlab's built in basic matrix computations, such as addition, subtraction, "division," and multiplication, as needed.
  (a) Write out or print out your function.
  (b) Run the case with A=[9 1; 1 2], b=[1 1] and initial guess [1 1] for 10 iterations. Print out your solution. What is the residual of this result?
  (c) Run the case with A the matrix from the Poisson equation on a 10x10 grid (so 100 equations), b a vector of ones, and initial guess x=0. Run it for 100 iterations. Do not turn in the solution. However, calculate the residual, and turn in the 2-norm of the residual. Again, the only thing you should turn in for this question is the 2-norm of the residual after 100 iterations of this method.

Solutions for selected problems are here and the program here: CG.m.

Homework 7

The following exercises are due Monday, November 16:

Textbook:
Section 1.7: 10 b,c, 18, 34, 35, 36, 37

Programming:
1. Write a function in Matlab that takes as input a tridiagonal matrix given as three vectors: n by 1 vector v representing the main diagonal, (n-1) by 1 vector w representing the upper diagonal, and (n-1) by 1 vector z representing the lower diagonal. Have this function output the LU factorization with the U as two vectors and the L as one vector representing the diagonals. Also output the number of flops used. Use only basic programming.
  (a) Write out or print out your function.
  (b) Run the case with n = 10, v the vector of 2's, w and z the vector of -1's. Write down your results for the diagonals of L and U.
  (c) Run the case with n = 50 and n = 100 with v the vector of 2's, w and z the vector of -1's. Write down your results for the number of flops used.

Solutions for selected problems are here and the program here: triLU.m.

Homework 8

The following exercises are due Monday, November 23:

Textbook:
Section 1.8: 4, 9, 10
Section 2.2: 6, 15, 24
Section 2.3: 12
Section 2.4: 3

Programming:
1. Write a function in Matlab that takes as input an n by 1 vector p of rearranged integers from 1 to n representing a permutation matrix P whose ith row is the p(i)th row of the identity matrix; an n by n matrix B whose upper triangular portion stores U and strictly lower triangular portion stores L of the LU factoriation of PA; and an n by 1 vector b. Have this function output the solution to Ax = b. Use only basic programming.
  (a) Write out or print out your function.
  (b) Run the case with p = [3;1;2] and B = [2 -1 3;-0.4 -3 3;0.5 -0.2 4] and b = [2;-1;1] and output your results.

Solutions for selected problems are here and the program here: solver.m.

Homework 9

The following exercises are due Monday, November 30:

Textbook:
Section 2.5: 7, 12
Section 2.6: 6
Section 3.1: 5, 6, 8

Solutions for selected problems are here.

Homework 10

The following exercises are due Monday, December 7:

Textbook:
Section 3.5: 1, 2, 7, 11, 18a, 23 (do 17, but don't turn in. Read 28 and 29, but don't do (unless you want, of course.))
Section 3.2: 3, 8, 39. Also: Calculate the QR decomposition of A=[5 1; 12 1]
Section 3.3: 7 (For part b, use a reflector instead of a rotator.)

Programming:
1. Write a function in Matlab that takes as input Q, R, b, where A = QR is the QR factorization of an m by n matrix A, with m >= n, and b is an m by 1 vector, and outputs the least squares solution of Ax = b. Use only basic programming. In other words, program the matrix-vector multiplication and backwards substitution yourself.
  (a) Write out or print out your function.
  (b) Use MATLAB to get the QR decomposition of A=[1 2; 3 4; 5 6]. Use that Q and R with b=[1;3;5] in the function you programmed, and output your results.

Solutions for selected problems are here and the program here: QRsolver.m.