Newton's method root

mediumMathsacceptance —~20 min

Implement newton(coeffs, x0, tol, max_iter) — Newton's method for a root of the polynomial with coefficients coeffs (highest power first). Iterate x ← x - f(x) / f'(x) from x0 until |f(x)| < tol or max_iter steps have run. If the derivative is exactly zero at any point, there is no step to take — return None.

The implied-vol solver, the yield solver and the Kelly optimiser are all this loop wearing different hats. Return [root, iterations] with the root rounded to 6 decimal places.

example 1

input

coeffs=[1.0, 0.0, -2.0], x0=1.0, tol=1e-10, max_iter=50

output

[1.414214, 4]

example 2

input

coeffs=[1.0, 0.0, -2.0], x0=0.0, tol=1e-10, max_iter=50

output

None

note

x0 = 0 sits on the minimum of x² − 2: the derivative is zero, so there is no step.

constraints

2 ≤ len(coeffs) ≤ 8
1 ≤ max_iter ≤ 100
tol > 0

teacher · 2 hints · the first is free

↗ read the theory

the chapter this problem is cut from

▶ open in the workbench

run the same math on a real tape

●solution.py· utf-8 · spaces:4

def _eval(coeffs, x):
    f = 0.0
    for c in coeffs:
        f = f * x + c
    return f


def _deriv(coeffs):
    n = len(coeffs) - 1
    return [c * (n - i) for i, c in enumerate(coeffs[:-1])]


def newton(coeffs: list, x0: float, tol: float, max_iter: int):
    """[root to 6 dp, iterations], or None when the derivative vanishes."""
    d = _deriv(coeffs)
    x = x0
    it = 0
    while it < max_iter and abs(_eval(coeffs, x)) >= tol:
        # TODO: a zero derivative has no Newton step — return None instead of dividing by it
        x = x - _eval(coeffs, x) / _eval(d, x)
        it += 1
    return [round(x, 6), it]

ln 1, col 1tab indent · esc leave editor

python 3.13 · pyodide

+ 6 hidden on submit

input · keyword arguments to newton()

coeffs=[1.0, 0.0, -2.0], x0=1.0, tol=1e-10, max_iter=50

expected

[1.414214, 4]

the judge calls newton() with exactly these inputs · outputs are compared to 6 decimal places

● standing bypython 3.13 in your browser · pyodide 0.28.3 · judged on the server to 6 dp⌘↵ run · ⌘⇧↵ submit

paper only · educational · not advice