Homework 3 (due 2/4)
CSC 431

Midterm will be in 6th week, 2/11 for in-class students. For online students, midterm sign-up will be available next week.

We finished Section 1.3, skipping the material on complex numbers and interval arithmetic. Instead we saw how to compute (1+1/n)n by rewriting it as an exponential and using the Taylor expansion for ln(1+x), and Kahan's summation algorithm. Both examples can be found in Goldberg's paper on floating-point arithmetic, the summation algorithm is also nicely explained on the Kahan summation algorithm page in wikipedia. The problem of evaluating the roots of a quadratic equations is covered by Heath, Goldberg and also in O'Leary's book. We saw Heath's simulation.

After the break we started talking about linear systems of equations and matrices (Sections 2.1, 2.2, 2.4.1-2.4.4). For matrix review, check out SOS Math. We briefly discussed the Leontief Input/Output model, which I based on section 2.7 of Gareth William's Linear Algebra with Applications. Next week we will finish chapter 2 (including Sections 2.3 and parts of 2.5) and continue on to optimization problems (Chapters 3 and 6).

Submission: you can submit the homework by hardcopy in class or by sending it to me as an email.

1. [Quadratic Equations, 30pt] Do Problem 1.10 on page 46 of the textbook. Do not worry about the complex part, i.e. if b2-4ac < 0 simply return "no solution". Before you start implementation analyze the possible sources of error in the formulas:

  1. What are possible sources of unnecessary overflow (e.g. b2  might overflow, but  b2-4ac could be small)?
  2. What are possible sources of unnecessary underflow?
  3. What are possible sources of unnecessary cancellation (e.g. if 4ac is close to 0, then -b + sqrt(b*b-4ac) is problematic)

Include answers to a, b, and c with an explanation of how you adjust the formula to deal with this. The table of values in the problem will help you detect the issues with the standard formulas. Hint: possible adjustments of the formula to consider include pulling the b out of the square root, pushing the /2a into the square root, etc.

2. [Matrices, 15pt] Do Exercise 2.4, page 97 of the book. Hint: For a) you can use any of the methods we saw to show singularity (though finding a z <> 0 so that Az = 0 is the easiest here). For b) the answer is either none or infinity.

3. [Leontief Model, 30pt] Consider the following input/output matrix A:

  oil chemicals electricity
oil 0.1 0.4 0.3
chemicals 0.3 0 0.2
electricity 0.4 0.2 0.3

Demand is

oil 100
chemicals 40
electricity 60

We saw that the production x fulfills x = Ax + d, that is (I-A)x = d. Determine x by solving this system using Gaussian elimination: using elementary matrix operations turn I-A into a triangular matrix, and then solve the system through substitution.  While you're solving the system by hand, you can use a calculator/computer for calculations, of course.

(Extra Credit) Determine the LU factorization of I-A.

Marcus Schaefer
Last updated: January 22nd, 2010.