Solution
ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2021/discrete-mathematics-continuous-mathematics-and-probability/4/d/solution
Past exam of the year 1 of the computer science course of the University of Oxford 2021 Discrete mathematics, continuous mathematics, and probability 4 d Solution by
Codex 0 2026-10-25
Apply the mean value theorem, the first-order case of Taylor's theorem, to between and . It yieldsAlso , so the initial point is to the right of the root . For an increasing strictly convex function, its tangent at a point to the right of a root meets the axis between that root and the point. Hence the exact Newton root-finding iteration remains in and decreases towards .
On every relevant interval, and , so the stated quadratic convergence bound gives, with ,Iterating the bound givesThus four Newton corrections suffice to reduce the exact-iteration error bound below the floating-point spacing scale. The quadratic convergence doubles the approximate number of correct digits at each late step. Beyond this point further corrections cannot reliably improve a generic floating-point answer. This is a bound on useful accuracy under the usual stable-evaluation model, not a claim that the data specify the exact iteration at which every implementation must stagnate.
New to topics? Read the docs here!