Problem 1 [8 points] Consider the system , where and
a. [2 points] Show that is singular.
b. [2 points] If we were to use Gaussian elimination with partial pivoting to solve this system using exact arithmetic, show where the process fails.
c. [2 points] Solve this system in double precision using partial pivoting. Do not use Matlab’s functions. What is the solution that you obtain?
d. [2 points] Matlab’s A\b
produces NaN -Inf Inf
as a solution. Explain why NaN, -Inf and Inf.
Answer:
a. For to be singular, prove
Using Gaussian elimination without partial pivoting
Lemma
is singular
b. With partial pivoting:
We notice that , thus invalid.
c. With partial pivoting in double precision
The decomposition of
The following portray steps to calculate (lower triangular):
note: the is close to zero, hence consistent with previous finding
To solve for with decomposition, We solve
d. Since A is singular, it doesn’t have an inverse.
Matlab uses LU decomposition, and as we explored above, a pivot element is found to be zero or close to zero (matrix is probably ill-conditioned), which leads to , which results in NaN
. For the second value -Inf
, the division is small. Inf
is due to division by zero
Problem 2 [2 points] Apply Gaussian elimination with partial pivoting on the following matrix
Show all the steps.
Answer:
Problem 3 [5 points] (a) (3 points) Let , , and be matrices, where and are nonsingular. For an vector , describe how you would implement the formula without computing any inverses. Here, is the identity matrix.
(b) (2 points) What is the complexity of your approach in terms of big-O notation?
Answer:
a. Given and are non-singular
- Step 1: Using decomposition of B, such that
- Step 2: Solve for in (As )
- solve for in via forward substitution
- solve for in via backward substitution
- Step 3: Compute
- This becomes
- Step 4: Compute
- Via matrix multiplication
- Step 5: using decomposition of C, such that
- Step 6: Solve for in (As )
- Solve for in via forward substitution
- Solve for in via backward substitution
With expansion, solved
b. Complexity analysis
Let total_cost
be the big-O notation
Step 1 using decomposition of
Step 2 solving each and takes each, thus solving using decomposition takes
Step 3 Compute
- MatmulOp of is
- AddOp of is
- Total for this step
Step 4 Compute
- MatmulOp of is
- AddOp of is
- Total for this step
Step 5 using decomposition of
Step 6 solving each and using LU composition takes
Problem 4 [6 points] An Hilbert matrix, denote it by , has entries
For , generate the Hilbert matrix of order , and also generate the vector , where is a random vector. Solve the resulting system to obtain an
approximate solution . (See the functions hilb
and rand
.)
(a) [2 points] How large can you take before the error is 100 percent?
(b) [2 points] For up to the value you find in (a), report , where , and .
(c) [2 points] As increases, how does the number of correct digits in the computed solution relate to the condition number of the matrix?
See the cond
function.
Submit your Matlab program producing the above results. Name the Matlab file hilb_problem.m
.
Answer:
The following hilb_problem.m
is used:
a. largest before the error is 100 percent.
b. The following entails the value of and
n | ||
---|---|---|
1 | 0.00000000000000000000000000000000 | 0.00000000000000000000000000000000 |
2 | 0.00000000000000000000000000000000 | 0.00000000000000013220372219891702 |
3 | 0.00000000000000000000000000000000 | 0.00000000000000363350625815651572 |
4 | 0.00000000000000000000000000000000 | 0.00000000000006709266750580992637 |
5 | 0.00000000000000007733975117624287 | 0.00000000000747821082933078000054 |
6 | 0.00000000000000013934207506736382 | 0.00000000023960543432895825359428 |
7 | 0.00000000000000010660570398371085 | 0.00000000837749558262967895463873 |
8 | 0.00000000000000007165565184570407 | 0.00000009992506975169996005028294 |
9 | 0.00000000000000007076549838447114 | 0.00000608952488692639798140973303 |
10 | 0.00000000000000012662840530707719 | 0.00002450986238666613242472361311 |
11 | 0.00000000000000011997633780813789 | 0.00379971054180424641297242338567 |
12 | 0.00000000000000006503338066505365 | 0.25404291536273732043937911839748 |
c. As increases, the condition number increases, which means the matrix becomes more ill-conditioned. This means fewer digits in the computed solution are correct.
IMPORTANT
The number of correct digits in the computed solution decreases due to the increase in the condition number as increases
Problem 5 [4 points] You have to interpolate by a polynomial of degree five using equally spaced points in [0, 1].
(a) [2 points] What (absolute) error would you expect if you use this polynomial?
(b) [2 points] Using equally spaced points, what degree polynomial would you use to achieve a maximum error of ?
Answer:
a. Interpolate by a polynomial of degree five using equally spaced on in , Error as follow
where
- is the degree of the polynomial ()
- is derivate of
Derivate of every 4 terms is . Therefore the 6th derivative is
Here and
Therefore
b. To achieve maximum error of , We have
derivative of cycles every 4 term, thus the max value of over is 1
Thus we need to solve for in
Hence considering to use polynomial degree seven to achieve the desired error bound.
Problem 6 [3 points] You are given the values of at three points
x | 1 | 4 | 9 |
1 | 2 | 3 |
(a) [2 points] Construct the interpolating polynomial interpolating these data.
(b) [1 points] Using this polynomial, approximate .
Answer:
a. To construct the interpolating polynomial for these data, we will use Lagrange basis
where is the Lagrange basis polynomial, defined as
With , and data point
IMPORTANT
The interpolating polynomial
b. The approximation of
Problem 7 [7 points] Let . Interpolate this function over using
(a) [2 points] polynomial interpolation of degree at equally spaced points. Then evaluate this polynomial at equally spaced points. Denote the interpolating polynomial by . Plot
- and versus at the interpolation points and at the points (on the same plot);
- versus at the points.
You can use the
polyfit
function. See thelinspace
function.
(b) [2 points] Repeat (a) but now using Chebyshev points.
(c) [2 points] Repeat (a) but now using spline interpolation at equally spaced points. See the spline
function.
(d) [1 points] Discuss the accuracies of your results.
Submit your plots (6 in total) and the Matlab code producing them. Name your Matlab file interp_problem.m
.
Answer
implementation in matlab are as follow:
a. The following is a snippet of interp_problem.m
for polynomial interpolation of degree
b. The following is a snippet of interp_problem.m
for Cheybyshev points
c. The following is a snippet of interp_problem.m
through spline interpolation at equally spaced points.
d. Discussion
- The polynomial interpolation using equally spaced points might show oscillations near endpoints due to Runge phenomenon (oscillations near the endpoints of the interpolated interval become pronounced). We saw oscillation in the error graph here.
- Polynomial interpolation using Chebyshev points should mitigate the oscillations
- The spline interpolation will provide a piecewise polynomial that should fit the function smoothly and might offer better accuracy than polynomial interpolation
Problem 8 [4 points] Given the three data points , determine the interpolating polynomial of degree two using:
a. [1 point] monomial basis
b. [1 point] Lagrange basis
c. [1 point] Newton basis
[1 point] Show that the three representations give the same polynomial.
Answer:
a. Monomial basis
The monomial basis for a polynomial of degree two is given by:
The linear system as follow
Solving this system to obtain the
NOTE
Thus monomial basis of this polynomial of degree two is
b. Lagrange basis
The Lagrange basis for a polynomial of degree two is given by: where
Thus
NOTE
Thus Lagrange basis of this polynomial of degree two is
c. Newton basis
The Newton basis for a polynomial of degree two is given by: where
We have
Thus
NOTE
Thus Newton basis of this polynomial of degree two is
Therefore, we prove that all three basis yield the same polynomial for degree two.