MediumCalculusca-117

Broyden 1D Update

Problem

Apply one Broyden update to the secant slope estimate and take the next quasi-Newton step.

Given the previous points x0, x1, the old slope b0, and f(x) = sum(coeffs[i] * x^i), update b1 = b0 + (f(x1) - f(x0) - b0*(x1 - x0)) / (x1 - x0), then set x2 = x1 - f(x1) / b1. Return [b1, x2]. In 1D the update reduces to the secant slope, so b0 cancels out.

Hint

The rank-one update enforces the secant condition at the new pair of points.

Test cases

case 1

in: [[-2,0,1],1,2,1]

expected: [3,1.3333333333333335]

case 2

in: [[-2,0,1],1,2,10]

expected: [3,1.3333333333333335]

case 3

in: [[0,0,1],1,2,2]

expected: [3,0.6666666666666667]

case 4

in: [[-2,-1,0,1],2,1.5,0]

expected: [8.25,1.5151515151515151]

Starter codePython

def broyden_update(coeffs, x0, x1, b0):
    # Return [b1, x2]
    # Your code here
    pass

4 test cases · run your code against them in the editor