Assignment 4 : Numerical Analysis - MATH 317
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
Assignment 4 : Numerical Analysis - MATH 317
Due date: December 7th 9 2022 - on myCourses
You must include all relevant program code and explanations of your results. Write your own codes and comment them.
1. (20 pts) (Forward substitution for lower triangular systems)
a) Write a MATLAB program that uses forward substitution to solve Ly = b, given an n × n lower triangular matrix L and a vector b e Rn . The code should have the input-output structure y - ForwardSubstitute(L, b)
b) Using the code from part a), find a solution y = (y1 , . . . , y5 )T to ╱ 
\ ╱ \
= ╱ \
.
2. (20 pts) (Backward substitution for upper triangular systems)
a) Write a pseudocode for backward substitution for upper triangular systems.
b) Show that backward substitution has O(n2 ) running time.
c) Write a MATLAB program that uses backward substitution to solve Ux = y , given an n × n upper triangular matrix U and a vector y e Rn . The code should have the input output structure x - BackwardSubstitute(U, y).
d) Using the code from part c), find a solution y = (y1 , . . . , y5 )T to
|
╱ |
2 6 0 0 0 |
3 7 10 0 0 |
4 8 11 13 0 |
|
3. (20 pts) Consider the matrix A = ╱ 
3 
、and compute its PLU decompo- sition using the algorithm of Gaussian Elimination with Partial Pivoting (G.E.P.P.) we have seen in class. Show each steps in details.
4. (20 pts) (LU Decomposition to solve linear systems)
a) Using the pseudocode we saw in class, write a MATLAB code A - LUDecomposition(A),
where the returned A will have the entries of L and U given by
Aij = 
Since Lii = 1, it does not need to be stored.
b) Write a MATLAB code LUSolve .m that combines the codes ForwardSubstitute .m, BackwardSubstitute .m and LUDecomposition .m to solve Ax = b.
5. (20 pts) (Least square to fit quadratic polynomial to data) Given a set of points {(xi , yi )}i=1,...,n we wish to fit the best quadratic function, that is, we want to find the coefficients c0 , c1 , c2 such that y = c0 + c1 x + c2 x2 fits best the data.
a) Letting
、( ╱．y(y)2(1)、(
M := ．(．) 1 x3 x3(2) 
and y := ．(．) y3 
,
． 
( ． 
(
(1 xn xn(2)． (yn ．
show that looking for the best quadratic fit leads to the overdetermined system of linear equations Mc = y, with c = (c1 , c2 , c3 )T e R3 .
b) Define the 3 × 3 matrix A := MT M and show that A is symmetric.
c) Find an explicit formula for b := MT y e R3 .
d) Write a MATLAB program that takes a list of points {(xi , yi )}i=1,...,n , con- structs the matrix A = MT M, the vector b = MT y, and solves the system Ac = b using the code LUSolve .m from question 4b).
e) Consider the ten points
{(5, 1), (5.5, 4), (6.5, 7), (8, 8), (8.5, 9.5), (10.8, 9.2), (11.5, 9), (13.7, 6), (14.5, 3), (15.9, 1)}
and apply the procedure presented in this problem to find the best quadratic polynomial y = c0 + c1 x +c2 x2 that fits the data. Plot the polynomial over the points. Comment.
2022-12-07