Fundamentals of Numerical Mathematics for Physicists and Engineers. Alvaro Meseguer

Скачать книгу

is really close to the sought root, i.e. most of the methods are just locally convergent. In practice, a root‐finding algorithm starting from an initial guess moderately far away from the root could easily lead to a sequence that may wander from one point to another of the real axis, eventually diverging to infinity or converging to a solution (not necessarily the sought one). Figure 1.4b illustrates this phenomenon by showing the result of computing the roots of the function using Newton's method starting from different initial guesses. The first two roots of are located at and (black bullets in Figure 1.4b). In this example, we initialize Newton's method from two initial guesses reasonably close (but not too close) to . To guide the eye, we have indicated the history of each of the two sequences by encircled numbering of their ordinates. The first sequence starts at (gray square) and Newton's first iterate is already very close to , to which the sequence eventually converges (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

Скачать книгу