Root finding methods for one dimensional optimisation

• the exact formula may have difficulties due to rounding errors • the exact formula may be more expensive to compute

• give an initial estimate of the root x(0), try to generate a better approximate x(1) of the root • once x(1) has been computed, it can be used to compute another estimate x(2) in the same way • generally, x(i) is used to compute x(i + 1)

• does the iteration converge • in other words, will x(i+1) be a better estimate than x(i) • is there a way to check this as part of the computation • if the iteration does converge, then how quickly does this happen • how should we decided to stop the iteration

• suppose we know there is a root x* between two end points a and b • call c = a+b/2, then the solution is either between a and c or between c and b • if the solution is between a and c: • then go to step 1 with the end points as a and c • otherwise, go to step 1 with the end points c and b we repeat this process until b - a < TOL where TOL is a user-supplied value we can check if the root is between a and b by checking if the signs of F’(a) and F’(b) are different

• finding an initial bracket is not always easy • it can take a very large number of iterations to obtain an accurate answer • it can never find a solution of f(x) for which f does not change sign

we start our initial guess x(0) and find the corresponding point on the graph function (x(0), f(x(0)). we find the tangent to the graph at (x(0), f(x(0)) and follow this line to the x-axis. where the tangent line intersects the x-axis is our new value for x(1)

x(i+1) = x(i) - f(x(i))/f’(x(i))

• potential division by zero • derivative is zero