Numerical Analysis and Computing Assignments 2 & 3

CS 323 Numerical Analysis and Computing
Programming Assignments 2 & 3 Due: 04/02/2018
Important
 Submit your source code - no screenshot, or copy/paste into a word/pdf document. • Follow the instructions given in each of the problems. • In each question, if your code does not run, no credit will be given for the respective problem and the solutions you got from it. • Write a short report (this is problem 4), presenting only the requested information. Do not just paste all the program output. • You have to submit 4 files (3 source codes, and 1 pdf file)
1
(1.) (20 points) Write a function named NaturalSpline.m, if using Matlab, or NaturalSpline.py, if using Python, to implement the following algorithm to construct the Natural Cubic Spline interpolant S(x), defined at the numbers x0 < x1 < ··· < xn. Remember that S(x) = Sj(x) = aj + bj(x−xj) + cj(x−xj)2 + dj(x−xj)3, for xj ≤ x ≤ xj+1
Algorithm – Natural Cubic Spline
INPUT n;x0,x1,...,xn;a0 = f(x0),a1 = f(x1),...,an = f(xn) OUTPUT aj,bj,cj,dj for j = 0,1,...,n−1 Step 1 For i = 0,1,...,n−1 set hi = xi+1 −xi Step 2 For i = 1,2,...,n−1 set
αi =
3 hi
(ai+1 −ai)−
3 hi−1
(ai −ai−1)
Step 3 Set l0 = 1; µ0 = 0; z0 = 0 Step 4 For i = 1,2,...,n−1 set li = 2(xi+1 −xi−1)−hi−1µi−1; µi = hi/li; zi = (αi −hi−1zi−1)/li;
Step 5 Set ln = 1; zn = 0; cn = 0 Step 6 For j = n−1,n−2,...,0 set cj = zj −µjcj+1; bj = (aj+1 −aj)/hj −hj(cj+1 + 2cj)/3; dj = (cj+1 −cj)/(3hj);
Step 7 OUTPUT (aj,bj,cj,dj for j = 0,1,...,n−1) STOP
2
(2.) (10 points) Write a function named DividedDifferences.m, if using Matlab, or DividedDifferences.py, if using Python, to obtain the divided-difference coefficients of the interpolation polynomial Pn on the (n + 1) distinct points x0,x1,...,xn for the function f.
Algorithm – Newton’s Divided-Differences
INPUT x0,x1,...,xn; and f(x0),f(x1),...,f(xn) as F0,0,F1,0,...,Fn,0
OUTPUT F0,0,F1,1,...,Fn,n, where
Pn(x) = F0,0 +
n X i=1
Fi,i
i−1 Y j=0 (x−xj)
and Fi,i = f[x0,x1,··· ,xi]
Step 1 For i = 1,2,...,n For j = 1,2,...,i set Fi,j = Fi,j−1 −Fi−1,j−1 xi −xi−j
(Notice Fi,j = f[xi−j,··· ,xi].)
Step 2 OUTPUT (F0,0,F1,1,...,Fn,n) STOP
3
(3.) (15 points) Figure 1 shows a ruddy duck in flight. To approximate the top profile of the duck, we have chosen points along the curve through which we want the approximating curve to pass.
Figure 1: Flying duck.
The tables below list the coordinates of 21 data points relative to the superimposed coordinate system shown in Figure 2. Notice that more points are used when the curve is changing rapidly than when it is changing more slowly.
x 0.9 1.3 1.9 2.1 2.6 3.9 3.9 4.4 4.7 5.0 6.0 f(x) 1.3 1.5 1.85 2.1 2.6 2.7 2.4 2.15 2.05 2.1 2.25
x 7.0 8.0 9.2 10.5 11.3 11.6 12.0 12.6 13.0 13.3 f(x) 2.3 2.25 1.95 1.4 0.9 0.7 0.6 0.5 0.4 0.25
Figure 2: Points through which we want the approximating curve to pass.
4
Instructions for Problem 3: Write a script, named Problem3.m, if you are using Matlab, or Problem3.py, if you are using Python, that
(a) uses your code from Problem 1 to generate the coefficients for the natural cubic spline going through the given data points; (b) uses your code from Problem 2 to generate the coefficients for the interpolating polynomial (in Newton form) going through the given data points; (c) plots, in the same figure, in a coordinated system: ∗ the given data points ∗ the cubic spline ∗ the interpolating polynomial Note: For the figure, use different colors for each plot, and plot the data points with a big dot (or circle, or asterisk) so it is easy to identify the given points.
(4.) (15 points) Write a “report”. Your report should be named Report.pdf and should include:
(a) a table with the coefficients obtained for the natural cubic spline in Problem 3 (b) a table with the coefficients obtained for the interpolating polynomial in Problem 3 (c) the figure from Problem 3
5