a logo for the course

Numerical Analysis

David Gleich

Purdue University

Spring 2016

Course number CS-51400, MATH-51400

Tuesday and Thursday, noon-1:15pm

Location Lawson B155


Homework 1

Please answer the following questions in complete sentences in a typed manuscript and submit the solution on blackboard by on February 1st at noon.

Problem 0: Homework checklist

Problem 1: Gautschi Exercise 1.1

  1. Enumerate all positive elements of that correspond to normalized floating point values. (Recall that is a floating point system that uses 2-bits for the exponent and 3-bits for the significand or mantissa.) List each number on one line as a decimal.

  2. What is the distance of a positive normalized floating point number to its next larger floating-point number? (Do this for all values in .)

  3. Determine the relative distance for all numbers and give upper and lower bounds.

Problem 2: Gautschi Exercise 1.11

Let .

  1. Explain the difficulty of computing for a small value of and show how it can be circumvented.

  2. Determine an expression for the condition number of and discuss conditioning for small .

  3. How can the answers to 1 and 2 be reconciled?

Problem 3: Gautschi Machine Exercise 1.4

Euler's constant is defined as the limit Assuming that , try to determine and on the computer.

Problem 4: Gautschi Machine Exercise 1.6a.

Write a program to compute once using the first formula and once using the second formula. For , print the respective absolute errors. Comment on the results.

Problem 5: The Hurwitz zeta function

This is a real problem that I ran into! I was using a program written by someone else to compute a particular statistical estimate. The details don't really matter, but at one step, the code needed to compute the Hurwitz zeta function: where ranged from 1 to 7 and where ranged from 1 to 500. They were using Matlab, which doesn't provide a function for the Hurtwitz zeta function, but does provide a function for the Riemann zeta function: Note that the only difference between these two functions is that the first term in the Riemann zeta function is and the first term in the Hurwitz zeta function is . To account for this difference, the code I was using did the following:

 function h=hzeta(s,q)
 z = zeta(s)
 h = z - sum((1:(q-1)).^(-s));

Was I happy when I realized this? You should use what you've learned about floating point computations to answer this question. You can evaluate the Hurwitz zeta function to arbitrary precision via Wolfram Alpha.

Problem 6

Suppose you want to evaluate on a machine. Suppose that and that are all exact on the machine. Empirically illustrate that Now prove which of the three orders of evaluation result in the smallest error. (The three are (a+b)+c, (a+c)+b, a+(b+c).)

Problem 7

The Intel Penitum FDIV bug was illustrated with the procedure: Determine the accuracy of this computation assuming that and can be exactly stored in floating point on the computer.

Problem 8

  1. We want to understand computer implementations of methods to compute the roots of the quadratic equation given the coefficients in using the high school formula Show empirically that this formula can result in catastrophic errors in the computed roots and identify the cause.

  2. Consider Gautschi's suggestion in problem 9. Suppose we take (without loss of generality) the quadratic with roots . Suppose we compute the larger root first, and then use to determine the additional root. This results in the Julia program:

    x1=abs(p/2) + sqrt(p*p/4 - q)
    if p > 0
        x1 = -x1
    end
    x2 = q/x1
    

    Find two serious flaws with this program as a "general-purpose" quadratic equation solver. Support your arguments with specific examples, if necessary.

  3. Consider reading Kahan's note on quadratics for more on how to accurately evaluate them. https://www.cs.berkeley.edu/~wkahan/Qdrtcs.pdf