Problems and Algorithms

Problems and Algorithms (updated a bit)

Problem - Mathematical statement of a question. No particular method of solution is implied. Example: find the solution x to Ax = b.

Algorithm – Particular sequence of calculations whose intent is to solve a problem. Example: solve for x in Ax = b using Gaussian elimination without pivoting, as detailed in class.

Remarks on Problems

(1)To examine error growth in problems use the condition number. For example for the problem y = f(x) use Crel = | x f ’(x) / f(x) |. For the problem of finding x in Ax = b use the matrix condition number ||A|| ||A-1||. If the condition number is sufficiently large the problem is said to be poorly or badly conditioned.

(2) If the problem is sufficiently poorly conditioned then no algorithm can solve it accurately. There may be no cure for the difficulty. . Example: determine the amount of rain that will fall in San Jose on Jan. 1, 2050.

(3) If the problem is poorly condition the potential cures are

(a)Change the problem

(b)Use regularization. Regularization is a systematic procedure to change the problem by a small amount to create a better conditioned problem. There is a balance between how much to change the problem and the effects of the modified problem still being somewhat ill-conditioned. The effects of changing the problem is called the regularization error and the effects of the problem being ill-conditioned is called the perturbation error. There are techniques that try to balance these two errors. This balancing act is still an art. The most commonly used method often work but are not guaranteed to work.

(c)Use higher precision arithmetic and more accurate input data

Remarks on Algorithms

(1)Even though a problem is well conditioned an algorithm to solve it may be inaccurate. Such an algorithm is said to be numerically unstable.

(2)To test for potential disasters in an algorithm look for subtractive cancellation.

(3)To cure potential disasters in an algorithm attempt to change the algorithm so that subtractive cancellation is eliminated. We discussed several tools that may help avoid subtractive cancellation including rewriting formulas with algebra, trig identities and Taylor’s series and also use of pivoting in Gaussian elimination..

(4) On can quantitatively analyze error growth in an algorithms via (forward or backwards) error analysis. One must trace through errors that may occur at every step of the algorithm. We won’t do this in our class.

(5)The most common way to prove that an algorithm is numerical stable is to show that the calculated solution exactly solves a problem that is close to the true problem. For example, our results on the accuracy of Gaussian elimination were this type of result (assuming that the growth factor is not large).