Fundamentals of Numerical Mathematics for Physicists and Engineers. Alvaro Meseguer

(gray dashed lines and symbols). The second sequence starts from (white diamond), unfortunately leading to a location where Newton's algorithm predicts a negative second iterate , which is not even within the function's domain due to the logarithmic term.

      From the previous example we can conclude that forecasting the fate of a Newton's sequence based on the location of the initial guess is usually impossible. In the first case, we may have naturally expected the sequence to approach instead of (because of its initial proximity to the former one). In the second case, we could have also naturally expected the sequence to converge at least to either one of the two roots, but never such a dramatic failure of the iteration. We recommend the reader to explore the complex convergence properties of Newton's method by starting the iteration from a wide range of initial guesses located between and . The reader may also repeat the experiment with the secant or chord algorithms to conclude that the behavior of the sequences is also unpredictable when using these methods.

Under particular circumstances, there are certain root‐finding methods that always converge to the same root, regardless of the initial guess from which they have been started. In general, for a given function with a unique root in the open interval , a root‐finding method is said to be globally convergent within if for all initial guesses . The bisection method or the Regula Falsi¹² method are examples of globally convergent algorithms. However, these and other univariate globally convergent methods are not always easily adaptable to solve systems of nonlinear equations.

      Complementary Reading

      For an authoritative study of different root‐finding methods for nonlinear scalar equations, I strongly recommend Dahlquist and Björk's Numerical Methods in Scientific Computing, Vol. I. The reader will find there detailed mathematical proofs of the convergence of many algorithms, as well as other very important topics that have not been covered in this chapter, such as Fixed‐Point Iteration, Minimization or the solution of algebraic equations and deflation. That chapter also addresses the Termination Criteria problem (i.e. when to stop the iteration) in depth and with mathematical rigor.

      For a different approach to the root‐finding problem, Acton's Numerical Methods that Work is an alternative. The reader will find in that text very clear geometrical explanations of why different root‐finding methods may have convergence problems. Acton's book also provides deep insight into the technical aspects of root‐finding algorithms, as well as very useful tips and strategies.

      Practical 1.2 Throwing Balls and Conditioning

A ball is thrown from the lowest point of a hill with initial angle and speed (see the figure below). The height of the hill is given by the expression , where and are measured in meters, , and .

      1 Edit a Matlab .m function corresponding to the equation whose solution is the abscissa where the parabola and the hill's profile intersect (for arbitrary initial speed and angle and , respectively).

      2 Using Newton's method, find the abscissa of the point A where the ball impacts with the hill. Provide your result with at least five exact figures.

      3 With the same initial speed, represent the impact abscissa for initial angles within the range .

      4 Find the minimum initial angle that allows the ball to impact beyond , i.e. to the right of the hill's peak. Provide your result with at least three exact figures.

      5 Explore the order of convergence of the root‐finding method when computing the minimum angle in (d). Do you observe an increase in the number of iterations required to achieve the desired accuracy? If so, explain what may be the reason for that phenomenon.

      Problems and Exercises

The symbol (A) means that the problem has to be solved analytically, whereas (N) means to use numerical Matlab codes. Problems with the symbol * are slightly more difficult.

      1 1. (A) Consider the bisection method starting from the interval . Let be the resulting bisection sequence satisfying . Let be a given tolerance.How many iterations are required in order to satisfy that ?Once that tolerance has been reached, how many iterations should be added to have one more digit of precision?

      2 2. (N) Apply the bisection algorithm to solve the equations over the intervals indicated below. Provide the numerical approximation of the root with at least 10 significant digits and also report how many bisections were required to achieve that accuracy., ., ., .

      3 3. (A) Show that the chord method starting within the interval with has linear convergence to the root and obtain its corresponding asymptotic error constant . If for linear convergence, what constraints does this condition impose? Will the method converge linearly to a double root?

      4 4. (A)* Show that the secant method converges superlinearly with order of convergence . As a hint, use Taylor's expansion to show that the errors obey (to the lowest order) the recurrence: .Next, assume that the absolute error obeys the relation , with in order to provide the value of the exponent as well as the asymptotic error constant .

      5 5. (N) Using your own codes for the chord and secant methods, solve the equation starting from the interval and reproduce the results of Figure 1.2b.

      6 6. (N) Regula Falsi or false position method: this root‐finding algorithm is in essence a globally convergent version of the secant method. Starting from the interval satisfying , proceed with the iterationwhere is the last iterate satisfying , that is,You need to modify your secant method code by storing the history of the iterates in order