Programming Assignments 2 & 3 Solution

Important




Sakai submission only.




No late submission will be accepted.




Only Python or Matlab implementation will be accepted. No credit will be given for implementation in other languages.




This is an individual assignment.




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 informa-tion. Do not just paste all the program output.




You have to submit 4 les (3 source codes, and 1 pdf le)









(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
(ai+1
ai)




3
(ai
ai 1)


















hi
hi 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.) (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












n
i
1








Xi
Y


Pn(x) = F0;0 +
Fi;i
(x xj)








=1
j=0
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


(Notice Fi;j = f[xi j; ; xi].)




xi
xi j
Step 2 OUTPUT (F0;0; F1;1; : : : ; Fn;n)




STOP





(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 superim-posed 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.








Instructions for Problem 3:




Write a script, named Problem3.m, if you are using Matlab, or Problem3.py, if you are using Python, that




uses your code from Problem 1 to generate the coe cients for the natural cubic spline going through the given data points;



uses your code from Problem 2 to generate the coe cients for the interpo-lating polynomial (in Newton form) going through the given data points;



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 table with the coe cients obtained for the natural cubic spline in Prob-lem 3



a table with the coe cients obtained for the interpolating polynomial in Problem 3



the gure from Problem 3