We are solving (approximately) the equation f(x) = 0, where f is a nice function.
Start by guessing the solution: x0
Locally replace the function f(x) with a straight line and find where this line intersects the x-axis. We denote this point as x1.
Iterate to your heart’s content. We want to make a more precise (n + 1)-estimate xn+1 of the root r of the equation f(x) = 0 from the n-th estimate xn.
In the vicinity of xn, replace f with a straight line (Taylor polynomial of the 1st degree, lol).
The equation of the line (y - yk) = f’0(xk)(x - xk).
We want xk+1 such that y = 0. Also, yk = f(xk).
-f(xk) = f’(xk)(xk+1 - xk) → xk+1 = xk - f(xk) / f’(xk). Just choose the initial estimate x0 and figure out when to stop iterating. Newton’s tangent method Create a function newton(fun, x0, tol = 6) that, using Newton’s tangent method, finds (and returns) an approximate solution to the equation fun = 0 with an initial guess of x0 and with precision 10-tol. Your function must not use any external libraries (especially math). Submit your solution as a single .py file containing the function newton(fun, x0, tol = 6) and any auxiliary functions (e.g., for differentiation).
I wrote this code for it
def derivative(f, x, tol = 6):
h = 0.1
df = (f(x+h) - f(x)) / h
est = 0
while abs((est - df)) >= 10 ** (-tol):
h /= 2
est = df
df = (f(x+h) - f(x)) / h
return df
import math
def myFun(x):
return math.cos(x)
def newton(fun, x0, tol=6):
x = x0 - (fun(x0) / derivative(fun, x0))
while abs(x - x0) > 10 ** -tol:
x0 = x
if derivative(fun, x0) == 0:
x = x0 - (fun(x0) / 10 ** -323)
else:
x = x0 - (fun(x0) / derivative(fun, x0))
return x
When you run the code does it give the right answers?
If not what does it output and what did you expect.
What have you done to investigate the problem?
Do you suggestions on how to debug your code?
It looks okish. For these algorithms there are always many choices that can be made.
You can have all sorts of stopping conditions.
The condition of comparing the derivative with zero is better to replace it with being close to zero.
When that condition happen it could be good to check if the value of the function is already small enough. One could be near or at a multiple root of the function.
Likewise, the stopping condition could check if the value of the function is already small enough. You could have a function that is very flat and close or equal to zero, the values of x and x0 still not close together, but the value of the function is already sufficiently close to zero or zero.
The stopping condition could also involve the number of iterations. Sometimes Newton can enter an infinite loop, or too many iterations.
Perhaps the stopping conditions can be kept simple and sweep any problem under the “is a nice function” assumption.
You could pass the derivative as an argument. That way, if they have an explicit way to compute the derivative, then they can use it (without having to re-define your approximate derivative): newton(x0, fun, dfun=derivative, tol=6)
In the approximate derivative, the stopping condition could also consider how small h is already. Suppose you have a function that changes a lot. Then it would take many iterations before est is close to df. The h could even become zero before this happens.