Even if we cover many different algorithms and examples, there are a few central ideas in this book that we try to emphasize over and over.<\/p>\n
The first idea is that we can simplify the solution of a problem by using an approximation and then systematically improve our approximation by iterating and computing corrections.<\/p>\n
The divide-and-conquer methodology can be seen as an example of this approach. We do this with the insertion sort when we sort the first two numbers, then we sort the first three, then we sort the first four, and so on. We do it with merge sort when we sort each set of two numbers, then each set of four, then each set of eight, and so on. We do it with the Prim, Kruskal, and Dijkstra<\/a> algorithms when we iterate over the nodes of a graph, and as we acquire knowledge about them, we use it to update the information about the shortest paths.<\/p>\n We use this approach in almost all our numerical algorithms because any differentiable function can be approximated with a linear function<\/a>:<\/p>\n f (x +\u00a0\u03b4<\/i>x) ‘ f (x) + f \u2032(x)\u03b4<\/i>x (1.1)<\/p>\n We use this formula in the Newton method<\/a> to solve nonlinear equations and optimization problems, in one or more dimensions.<\/p>\n We use the same approximation in the fix point method, which we use to solve equations like f (x) = 0; in the minimum residual and conjugate gradient methods<\/a>; and to solve the Laplace equation in the last chapter of the book. In all these algorithms, we start with a random guess for the solution, and we iteratively find a better one until convergence.<\/p>\n The second idea of the book is that certain quantities are random, but even random numbers have patterns that we can capture using instruments like distributions and correlations. The presence of these patterns helps us model those systems that may have a random output (e.g., nuclear reactions, financial systems) and also helps us in computations. In fact, we can use random numbers to compute quantities that are not random (Monte Carlo methods<\/a>). The most common approximation that we make in different parts of the book is that when a random variable x is localized at a point with a given uncertainty,\u00a0\u03b4<\/i>x, then its distribution is Gaussian. Thanks to the properties of Gaussian random numbers, we conclude the following:<\/p>\n