to COMP 205 Homework 2 Jan 21, 1998, Due: Jan. 28, 1998

Problems

1. (15 points) We are given a order polynomial :

   

   where is a root and is the coefficient of the high-order term. Consider the following procedure for evaluating the polynomial:

   

   Show that the relative error in evaluating a value is: where .

2. ( 15 points) Consider the following procedure to solve a linear system of equations:

   

   

   

   

   Show by means of a numerical example that Cramer's rule is not backward stable. Hint: choose the matrix nearly singular and . Your numerical example can be done by hand on paper (for example with 4 decimal digit floating point), on a computer, or a hand calculator. You should clearly explain why Cramer's rule is not backward stable.

3. (20 points) Many geometric algorithms implemented on top of floating-point arithmetic fail due to inconsistent arithmetic. In this case we are given four lines in the plane: , , and . Let each line be represented as:

   

   We want to check whether these four lines intersect at a common point. We use the following algorithm (Algorithm A):

   • Compute the intersection of the first two lines, say and . Let us represent this point as .
   • Compute the distance of from the other two lines, in this case and . If both of those distances are less than some tolerance (say ), we conclude that the four lines intersect at a common point.

   The problem of computing the intersection of two lines corresponds to solving two linear equations in two unknowns. Lets assume that we are able to compute these intersections accurately (say up to 14 or 15 digits). To compute the distance of a point from a line, , we use the formula:

   

   Given four lines, we compare two different algorithms to check whether they intersect at a point:

   • Algorithm I: Compute . Check whether the distance of from and is less than .
   • Algorithm II: Compute . Check whether the distance of from and is less than .
   If we used exact arithmetic, both these algorithms should result in the same answer. Now consider the following data:

   

   

   

   

   All the computations are performed using IEEE double precision arithmetic. Furthermore, we use . Moreover . If we compute the intersection of these lines based on Algorithm I & II, we obtain:

   

   

   Both these numbers are exact up to 16 digits. Based on Algorithm I, we get

   

   

   As a result, Algorithm I concludes that the four lines DO NOT intersect at a common point.

   Based on Algorithm II, we get

   

   

   and it implies that the four lines INTERSECT at a common point.

   1. How do you account for this asymmetry between Algorithm I and Algorithm II? Using a different positive value of would not solve the asymmetry problem. Try to explain your answer geometrically. (10 points)

   2. Your goal is to modify the algorithm to account for the asymmetry for all pairs of four lines. Given four lines, for all input permutations (24 permutations in this case), the algorithm should give a consistent answer using floating point arithmetic. You can assume that no two lines are parallel to each other. Furthermore, we would like to use a positive (non-zero) value of . (10 points)

• About this document ...