CS-SE4X03 -  Assignment 2 - Solved

Solve the system
3    4    3
⎡ 1    5    −1 ⎤
⎣ 6    3    7 ⎦    X1
⎡    ⎤
⎣ X2 X3 ⎦    =    10
⎡    ⎤
⎣ 7 
⎦ 
15

using Gaussian elimination
•    without pivoting
•    with partial pivoting
Show all steps. In your calculations, you can carry four digits after the decimal point, and a nonzero digit before the decimal point.
Problem 2 [3 points] Consider the linear system
~ 1    1 + c ~ ~X1    ~    ~1 + (1 + c)c ~
=
1 − c    1    X2    1
The exact solution is X = [1, c]T for any value of c. Solve this system in MATLAB with various values for c, especially for values near √cmach.
•    For each value of c you try, compute the condition number of the matrix and the relative error in each component of the solution. Submit in the PDF results for 4 different values of c in the form
c |X1 − 1| |X2 − c|/c cond(A)
...
•    What conclusions can you draw from this experiment?
Problem 3 [12 points]
(a) [2,3,1 points] Implement in Matlab the following functions:
function B = GE(A)
performs LU factorization of an m x m matrix A without pivoting and stores the L and U factors in the output B. U is stored in the upper-triangular part of B. The diagonal of L is not stored, and the part of L below the main diagonal is stored below the main diagonal of B. For example, for a 3 x 3 matrix A, B is
⎡u11 u12 u13
⎣
l21 u22 u23 l31 l32 u33
 
function [B, ipivot] = GEPP(A)
performs LU factorization with partial pivoting. The L and U factors are stored in the output B as in GE. ipivot is permutation of the vector 1:n recording the row permutations. When computing the LU factorization you must not swap rows in memory.
function x = backward(B, b, ipivot)
performs backward substitution. B contains the L and U factors as computed by GE or GEPP; ipivot is an index vector storing row permutations. b is an n-vector.
Then you can solve a linear system Ax = b as
 

 
Store these functions in files GE.m, GEPP.m, and backward.m. (b) [2 points] Write a main program main_ge.m that
•    generates an n × n random matrix A and vector x of ones
•    computes b = Ax
•    solves Ax = b using Gauss elimination with and without partial pivoting and with MATLAB’s A\b
•    produces output in the format A\b    no pivoting pivoting cond(A)
1 7.3e-13    6.5e-11    6.2e-13    1.9e+04
The first column is experiment number, the next three columns are the relative errors in the solutions computed with A\b, Gauss elimination without pivoting, and with pivoting, respectively. The last column is the condition number of A.
(c)    [2 points] Generate a table for 5 systems with matrices of size 2000 × 2000 each.
(d)    [2 points] How do the condition numbers relate to the accuracy of the computed solu-tions?
Submit
•    PDF: the Matlab files, table, (d)
•    Avenue: the Matlab files
 
Problem 4 [4 points] You have to interpolate ex by a polynomial of degree five using equally spaced points in [0, 1]. What error would you expect if you use this polynomial?
Using equally spaced points, what degree polynomial would you use to achieve a maxi-mum error of 10-8?
Problem 5 [5 points] You are given the data points
x,        0    0.1    0.2    0.3
y,        1.0000    1.0488    1.0954    1.1402

where y, ≈ √x, + 1, i = 0,1,2,3.
a.    (2 points) Using these data calculate approximations for √0.05 and √0.15
b.    (2 points) Derive a bound for the error in these approximations.
c.    (1 point) How does it compare to the actual errors?
Problem 6 [4 points] Let f(x) = |x| where x ∈ [−1, 1]. Use the polyfit function to interpolate f(x) at 21 equally spaced points −1 = x0 < x1 < · · · x20 = 1. Denote the interpolating polynomial by p(x).
(a)    Plot on the same plot f(x) and p(x) versus x at 41 equally spaced points in [−1, 1].
(b)    Plot the error |f(x) − p(x)| versus x at these points.
(c)    Repeat (a) and (b), but now use Chebyshev points for the interpolation. Submit
. PDF: the four plots
Problem 7 [3 points] Redo Problem 6, with f(x) = sin(x) and interval [−π, π]. Explain the differences in the errors when interpolating |x| and sin(x).