Let n be even and A R nn be constructed from the vectors c, d R n as ai,i = di , ani+1,i = ci for i = 1, . . . , n, and ai,j = 0 otherwise. (a) Write a function that, given the vectors d, c R n , explicitly constructs the matrix A. (b) State a sufficient condition that ensures that the LU factorization can be carried out without pivoting. (c) Assuming that the condition above is satisfied compute by hand the LU factorization of A. (d) Implement a function that computes the LU factorization of A in cn operations, where c is a constant independent of n. (e) State a sufficient condition that ensures that the Jacobi method applied to the system Ax = b converges. (f ) Write a function that implements Jacobi for the system Ax = b so that each iteration requires only cn operations, where c is a constant independent of n. (g) Let x R 1000 denote the exact solution of the system Ax = b and let x (100) R 1000 denote the 100th approximation produced by the Jacobi method. Produce an example in which kxx (100)k kxk 101 . (i) State a sufficient condition that ensures that the Gauss-Seidel method applied to the system Ax = b converges. (j) Write a function that implements Gauss-Seidel for the system Ax = b so that each iteration requires only cn operations, where c is a constant independent of n. Due: 30/16/2018 1 (k) Let x R 1000 denote the exact solution of the system Ax = b and let x (100) R 1000 denote the 100th approximation produced by the Gauss-Seidel method. Produce an example in which kxx (100)k kxk 101 . Exercise 2. What is the determinant of a real orthogonal matrix? Exercise 3. Show that the product U 1 1 U2, where U1 and U2 are orthogonal matrices is an orthogonal matrix. Exercise 4. Assume that the following relationship holds yi = p0 + p1e xi + p2e x 2 i + i i = 1, . . . , n. Given x = [x1, . . . , xn] and y = [y1, . . . , yn] we want to determine a good approximation of p = [p0, p1, p2]. Explain how we can use the QR factorization to achieve this goal.

Exercise 1. Let n be even and A E Rm\" be constructed from the vectors c, d E R\" as a\"; = d,-, an_,:+1,,; = c, fori = 1, . . . , n, and am: 2 0 otherwise. a Write a function that, given the vectors (1 c E R\" explicitly constructs the matrix A. I F ( b ) State a sufcient condition that ensures that the LU factorization can be carried out without pivoting. {c} Assuming that the condition above is satised compute by hand the LUfactorization ofA. (d) Implement a function that computes the LU factorization of A in on operations, where c is a constant independent of n. { e ) State a sufcient condition that ensures that the Jacobi method applied to the system Ax = b converges. (f) Write a function that implements Jacobi for the system Ax = b so that each iteration requires only on operations, where c is a constant independent of n. (g) Let x E R100" denote the exact solution of the system Ax = b and let x000) E R1000 denote the 100th approximation produced by the Jacobi method. Produce an example in which llxX'm'll _1 10 . IIXII {i} State a sufficient condition that ensures that the GaussSeidel method applied to the system Ax = b converges. {3'} Write a function that implements GaussSeidelfor the system Ax = b so that each iteration requires only on operations, where c is a constant independent of n. (h) Let x E R1000 denote the exact solution of the system Ax = b and let xm E R1000 denote the 100th approximation produced lag the GaussSeidel method. Produce an example in which 11%\" 101. Exercise 2. What is the determinant of a real orthogonal matrir? Exercise 3. Show that the product UflUg, where U1 and U2 are orthogonal matrices is an orthogonal matria; Exercise 4. Assume that the following relationship holds a: :32 . ys=m+p1e'+pael+ea: i=1,...,n. Given x = [plinwicn] and y = [ylrnjyn] we want to determine a good approaimation of p 2 [p0, p1, p2]. Explain how we can use the QR factorization to achieve this goal