Newton's Method Root Finder and a Stopping Rule That Guarantees the Requested Tolerance

In a HackerRank coding exercise, implement a function that finds a root of a given function to a requested tolerance `tol`, using Newton's method. The interviewer then asked how your stopping rule makes sure that the returned value actually achieves `tol`. Assume you receive the function `f`, its derivative `df` and a starting point `x0`, for example: ```python def newton_root(f, df, x0, tol, max_iter=100): """Return an approximation of a root of f within tol.""" ``` ### Clarifying Questions - Is the derivative supplied, or must it be approximated? - Does `tol` bound the distance to the true root, the size of the residual `f(x)`, or a relative error? - Is an interval on which `f` changes sign available, or only a starting point? - What should the function do when the iteration does not converge or the derivative is zero? ### Part 1 — Implement Newton's method Write the iteration, including what happens when it cannot continue. ```hint One step at a time Write the tangent-line update for a single step, then list each way that step can fail before you write the loop around it. ``` #### What This Part Should Cover - The update rule and the loop structure - Guards for a zero derivative, non-finite values and non-convergence - How the result, or a failure, is reported ### Part 2 — A stopping rule that meets the tolerance Explain how your stopping rule guarantees that the returned value is within `tol` of a root, and change it if it does not. ```hint What the last step tells you Relate the size of the last step to the remaining distance from the root when convergence is fast, then ask what extra check would turn that estimate into a guarantee. ``` #### What This Part Should Cover - What a step-size test and a residual test each bound, and when each one misleads - A check or a bracketing scheme that certifies the tolerance - Absolute versus relative tolerance, and the limits of floating-point precision ### What a Strong Answer Covers - A correct, guarded Newton implementation - A precise statement of what the tolerance refers to - The link between step size and error under quadratic convergence, and where it breaks down - A rule that provably meets the tolerance, such as a sign-change check or a bracket - Failure cases: zero derivative, divergence or cycling, multiple roots, an unreachable tolerance ### Follow-up Questions - How does your stopping rule behave at a double root, where Newton's method converges only linearly? - How would you combine Newton's method with bisection so that it can never diverge? - What would you do if the derivative were not available? - What goes wrong if `tol = 1e-15` and the root is near `1e6`?