CS 323 Numerical Analysis and Computing

Programming Assignments 2 & 3

• 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 ﬁles (3 source codes, and 1 pdf ﬁle)

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), deﬁned 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 DividedDiﬀerences.m, if using Matlab, or DividedDiﬀerences.py, if using Python, to obtain the divided-diﬀerence coeﬃcients of the interpolation polynomial Pn on the (n + 1) distinct points x0,x1,…,xn for the function f.

Algorithm – Newton’s Divided-Diﬀerences

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 ﬂight. To approximate the top proﬁle 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 coeﬃcients for the natural cubic spline going through the given data points; (b) uses your code from Problem 2 to generate the coeﬃcients for the interpolating polynomial (in Newton form) going through the given data points; (c) plots, in the same ﬁgure, in a coordinated system: ∗ the given data points ∗ the cubic spline ∗ the interpolating polynomial Note: For the ﬁgure, use diﬀerent 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 coeﬃcients obtained for the natural cubic spline in Problem 3 (b) a table with the coeﬃcients obtained for the interpolating polynomial in Problem 3 (c) the ﬁgure from Problem 3

5

Sale!