Mastering Algorithms with C

Chapter 13. Numerical Methods

Numerical methods are algorithms in numerical analysis. Numerical analysis is the study of problems in which numbers and approximation play an especially significant role. Computers are particularly well-suited to problems in numerical analysis because many such problems, while essentially involving common mathematical operations, require a lot of them. In the early days of computing, scientists monopolized computers with problems like this, which were far too intensive to be carried out by hand. Even today, problems in numerical analysis still occupy a good part of the cycles of some of the largest computers in the world. Hence, numerical analysis is a vast subject, and many numerical methods are as complicated and specific as the mathematical problems they solve. This chapter presents three numerical methods that are relatively simple but applicable to a wide variety of problems. This chapter covers:

Polynomial interpolation

A method of approximating values of a function for which values are known at only a few points. Fundamental to this method is the construction of an interpolating polynomial p _n(z) of degree ≤ n, where n + 1 is the number of points for which values are known.

Least-squares estimation

A method of determining estimators b ₁ and b ₀ for a function y (x) = b ₁ x + b ₀ so that y (x) is a best-fit line through a set of n points (x ₀, y ₀), . . ., (x _{n - 1}, y _{n - 1}). A best-fit line using least-squares estimation minimizes the sum of ...