Mastering Algorithms With C - Kyle Loudon [155]
Q: Recall that to approximate a root of an equation using Newton's method, we select an interval [a, b] on which the root exists and iterate closer and closer to it. What if we choose this interval much larger than needed, but in such a way that both rules mentioned in this chapter are still satisfied?
A: The discussion of Newton's method mentioned two rules that must be satisfied in order to guarantee the algorithm's success: we need to determine an interval [a, b ] where one and only one root exists; and we need to choose x 0, the initial iteration point, so that f (x 0) has the same sign as f '' (x) over the interval. Provided these rules are satisfied, the interval [a, b ] can be as large as we would like to make it. However, Newton's method will require more iterations to converge if we use an interval that is excessively large. Therefore, typically a relatively small interval convenient to the problem should be chosen.
Q: In the implementation of root, what symptoms might we notice if we have violated one the rules of Newton's method that guarantee convergence?
A: If we follow the rules presented in this chapter, Newton's method guarantees convergence to the root that exists on the interval [a, b ] containing the initial iteration point, x 0. Various symptoms help to determine when we have violated these rules. For example, successive approximations that appear to be diverging instead of converging indicate a problem. Another symptom is convergence to a root other than the one we expect. For example, suppose we think there is a root near -2 (perhaps by plotting the function), but we end up finding a root near 9. In order to relay these symptoms back to the caller, root returns both an array of the approximations obtained in successive iterations of Newton's method and an array of values for f (x) computed using the approximations. Normally, successive values for f (x) should approach 0. The parameter n of the root operation provides a way to keep a divergent series from running too long.
Related Topics
Error approximation
An important part of more substantial work with numerical methods. Numerical analysis is replete with approximation methods, and inherent in any approximation is some amount of error. Often it is important to quantify this.
Derivatives of functions
A fundamental part of calculus. The numerical methods presented in this chapter required only a primitive understanding of derivatives. However, for many numerical methods, a more complete understanding of derivatives and calculus is essential.
Muller's method
An algorithm for finding both the real and complex roots of equations. Complex roots are complex numbers, which result from taking the square root of negative numbers. This chapter focused on finding real roots.
Chapter 14. Data Compression
Data compression is the process of reducing the number of bits used to represent data. It is one of the most significant results of information theory, an area of mathematics that addresses various ways to manage and manipulate information. Data compression entails two processes: in one process the data is compressed, or encoded, to reduce its size; in a second process it is uncompressed, or decoded, to return it to its original state.
To understand why data compression is possible, we must first understand that all data can be characterized by some informational content, called its entropy (a term borrowed from thermodynamics). Compression is possible because most data is represented with more bits than its entropy suggests is optimal. To gauge the effectiveness of compression, we look at the ratio of the size of the compressed data divided by its original size, and subtract this from 1. This value is known as the data's compression ratio .
In the broadest sense, data compression methods are divided into two classes: lossy and lossless.