Newton's Method in Mixed Precision

We investigate the use of reduced precision arithmetic to solve the linear equation for the Newton step. If one neglects the backward error in the linear solve, then well-known convergence theory implies that using single precision in the linear solve has very little negative effect on the nonlinear convergence rate. However, if one considers the effects of backward error, then the usual textbook estimates are very pessimistic and even the state-of-the-art estimates using probabilistic rounding analysis do not fully conform to experiments. We report on experiments with a specific example. We store and factor Jacobians in double, single, and half precision. In the single precision case we observe that the convergence rates for the nonlinear iteration do not degrade as the dimension increases and that the nonlinear iteration statistics are essentially identical to the double precision computation. In half precision we see that the nonlinear convergence rates, while poor, do not degrade as the dimension increases. Audience. This paper is intended for students who have completed or are taking an entry-level graduate course in numerical analysis and for faculty who teach numerical analysis. The important ideas in the paper are O notation, floating point precision, backward error in linear solvers, and Newton's method.

Automated summary

This study investigates the application of reduced precision arithmetic in solving linear equations for the Newton step. The experiments show that using single precision in the linear solve has little negative effect on the nonlinear convergence rate, if the backward error is neglected. However, considering the effects of backward error, the usual textbook estimates are overly pessimistic and even the state-of-the-art estimates using probabilistic rounding analysis do not fully conform to experiments. In specific examples, it is observed that using single precision does not degrade the convergence rates for the nonlinear iteration as the dimension increases, and similar results are seen in the half precision case.