Assignment 1 Solution

Web Site: cs370 piazza




Your assignment should be handed in electronically on UW Learn. The submission should include one pdf le containing the assignment answers and the cover sheet and all the m- les required to run the code, preferably with no folder structure (not zipped).







1. (10 marks) The roots of a quadratic equation, ax2 + bx + c = 0, are given by






p






b + p








x1 =
b
b2 4ac
;
x2 =
b2
4ac




2a
2a




















when a 6= 0.


















(a) Consider the 5-digit arithmetic of the oating point number system F (10; 5;
10; 10)
with truncation. Using the above formulae, carry out by hand (with the aid of Matlab
or a calculator) the computation of the roots of the following quadratic equation






1:03x2 + 22:41x + 0:1123 = 0:




(1)



The roots of the given quadratic, correct to ve signi cant digits, are -0.0050123 and -21.752. What is the relative error of each of your computed roots, x1 and x2?




(b) A cancellation problem arises when applying the above formulae for any quadratic equa-tion having the property that

p




jbj b2 4ac:




When this property holds, if b 0 then the quadratic formula for x2 will exhibit cancel-lation. Show that an alternate formula for the roots is given by




p




x1 =
b
b2 4ac
; x2 =
c
:


2a


ax1



Redo the calculation of the roots of equation (1) by applying the above formula. Compute the relative error of the computed roots and compare against your results from part (a).



























1



( 15 marks )



Consider the sequence fpng de ned by p0 = 1; p1 = 47 , with pn for n 2 determined by




pn =
41
pn 1
+ 2pn


2;


n 2:
(2)






14


One can show that if
















4






p0 = 1;
p1


=


















7




then




4






n




























pn =


















7








is an exact solution of (2) for all n 0.




Write a Matlab function to evaluate (2) for n = 2; : : : ; 40 using the oating point ap-
proximation 47 = 0:5714285. What happens?




Carry out a stability analysis of this recursion, similar to what we did in class. Can you explain what you see? Hint: given a recursion



qn + aqn 1 + bqn 2 = 0




with a; b constant, then the solution to this recursion is given by




qn = c1x1n + c2x2n




where c1; c2 are constants, and x1; x2 are roots of the equation x2 + ax + b = 0.




Assume that machine epsilon is 2 10 8. Based on your analysis in (b), predict how many steps it will take before you will see an O(1) error1 in the oating point implementation of equation (2). (This does not have to be a rigorous argument.) How does your prediction agree with the experiment in part (a)?



Hint: assume that papprox0 = pexact0 and that




(p1)approx = (p1)exact(1 + )

= (p1)exact + e1; with e1 = (p1)exact




where is machine epsilon, and e1 is the absolute error at step 1. Assume that no other new oating point errors are introduced after step 1 (this is obviously an approximation).




3. ( 10 marks ) Suppose we have a natural spline:

S(x) = 8 a2 + 19x + a3x2
x3

28 + a1x + 9x2
+ x3
2


3
<
26 + 19x + 3x + a4x







:










x 2 [ 3; 1]




x 2 [ 1; 0]




x 2 [0; 3]



Determine the values of a1, a2, , a4.



Using the Lagrange basis, construct a cubic interpolation polynomial which interpolates



the values of S(x) at 3; 1; 0; 3.







1By O(1) we mean that the error is about one.



2



( 20 marks )



A cubic spline S(x) through the points ( 1; 2), (1; 1), (2; 4), (5; 3) and (7; 1) and having natural boundary conditions de nes a piecewise polynomial de ned by




S1(x) = a1 + b1(x + 1) + c1(x + 1)2 + d1(x + 1)3
1 x 1;
S2(x) = a2 + b2(x 1) + c2(x 1)2 + d2(x 1)3
1 x 2;
S3(x) = a3 + b3(x
2) + c3(x
2)2 + d3(x
2)3
2 x 5;
S4(x) = a4 + b4(x
5) + c4(x
5)2 + d4(x
5)3
5 x 7:



Write down the 5 5 linear system of equations needed to determine the derivative values s1; s2; s3; s4; s5 for the above cubic spline S(x).



Solve the linear system from part (a) and use this to determine the 16 coe cients a1; : : : ; d4 needed for the cubic spline S(x).



Using Matlab or Maple graph the spline S(x).



( 20 marks ) Create parametric curves representing the outline of an image of your hand with your rst and last initial separated by an ampersand inside the hand.



For example,























































Follow the steps below:




Start by downloading the script le init.m from the course website, which can be mod-i ed and used to initialize data arrays for your drawing. Use Matlab’s help command to learn any commands that are unfamiliar to you. Given an image, you can load it and trace the image of the object directly using mouse clicks. To add your initials, write them on a piece of paper, and then hold it up to the computer screen to trace it similarly. Create your data using the mouse to select a few dozen points outlining the object and your initials. Hitting enter once begins a new sequence of points; hitting enter twice terminates the input. Points to note: You can modify the script as needed. The script calls ginput for each segment (i.e., each pen stroke), and uses cell arrays to store the data. You may also nd the save and load commands useful.



Using the resulting data arrays produced above, generate parametric curve representa-tions based on smooth parametric curve interpolation as described in the course notes (see sections 3.1 and 3.2). At least one region of the sequence should be curved enough to be interesting (if not, you may change your initials). Show the output using piecewise linear and cubic splines. Speci cally, you will...



3



Write a Matlab script splineplots.m to load the data and generate the following four (separate) gures. Use the same axis scaling v from init.m for your plots (i.e., axis(v)).




(part1.m) Create a plot of the interpolation data points corresponding to the crude initial shape, plotted with the ’ ’ symbol and no connecting lines. The plot should have a title, and display both the axes and gridlines.




(part2.m) Create a plot of your initials and the object created by joining the original data points with straight lines. (The curves are not expected to look very smooth.) Include a title, and both axis and gridlines.




(part3.m) Create two smooth plots of your initials and the object using spline interpolation. Use the (approximate) arc length distance for the parameter t (described by equation 3.2 in the notes), and re ne the parameter partition by a factor of 6. For the rst plot use natural (or variational) end conditions, and for the second plot use not-a-knot end conditions (see functions csape and fnval). Include titles, but no gridlines or axes.







Include printouts of the generated plots as part of your written submission.


































































































































4