牛顿-拉夫森法方程求解算法

Question

在下面的代码中，当我把“max_n_iterations”设置为1时，打印出来的“approximations”列表显示了两个元素，而它应该只显示一个（就是最开始的x）。

这是为什么呢？

#This exercise shows an immediate way to find the root of a real valued funciton, using   successive better approximations
#This method is known as Newton Raphson method

print 'Find the root of a given function - NEWTON RAPHSONS METHOD'
print 'The function is the following: ...'
x=input('Choose an initial estimate:') #An initial estimate is necessary to be choosen   to start the iteration process
x=float(x) #The number inserted is transformed into a floating point number
max_n_iterations=input('Choose max n. iterations:') #The user decides the maximum number   of iterations to run
approximations = [] #Vector collecting all the intermediate solutions; i.e. the  approximated roots evaluated before reaching the final solution 
iterations= []

def f(x):  #The given function has to be inserted manually in the code
return 2*x**3+45*x+1/x**2+16

def D(f):  #Evaluates the first derivative of the given function, using the definition of derivative 
def df(x, h): #x is the initial estimate, h is the increment
    return (f(x+h) - f(x))/h #Difference quotient
return df #First derivative

def newtons_method(f, x, h=0.000001, epsilon=0.000001,): #This is the main process: f is  the given function, x and h are the same as above, epsilon is the tolerance level. Epsilon  and h have to be choosen sufficiently small
df = D(f) #df is just the first derivative, as before
for i in range(max_n_iterations): #The code runs until the maximum number of iterations  is reached
    x1 = x - f(x)/df(x, h) #Essence of Newton Raphson method: the iteration process
    approximations.append(x) #Every intermediate solution is collected into a vector, as  defined above
    iterations.append(1)
    if abs(x1 - x) < epsilon: #When the absolute difference between two successive roots  is less than the tolerance level (i.e. the sequence of solutions strongly converges), the  program exists the cycle
        break
    x = x1 #The next solution becomes the starting solution in the new cycle
return x #Final solution

def final_solution(): #The final solution from the Newton Raphson method
return newtons_method(f,x) 

df=D(f) #These values have to be inserted again to allow the execution of the final step
h=0.000001
epsilon=0.000001
x=newtons_method(f,x)

if abs((x-f(x)/df(x,h))-x) < epsilon: #If (strong) convergence has been reached
   print 'Solution is:', final_solution() #Prints the final solution
   print 'Approximations before reaching convergence:', approximations #Prints the vector of intermediate solutions
   print 'Convergence has been reached after', len(iterations), 'iterations'
   print 'Newton Raphson method was successful!'
elif abs((x-f(x)/df(x,h))-x) >= epsilon: #If (strong) convergence has not been reached
   print 'Approximated solution is:', final_solution()
   print 'Approximations evaluated:', approximations
   print 'Convergence has not been reached after', max_n_iterations, 'iterations'
   print 'Newton Raphson method was not successful'

Answer 1

正如ajcr所说，不要在牛顿法内部再调用牛顿法来求解。你只需要用到f(x)就可以了。

其次，你的while循环需要在abs(x-x1)小于epsilon时结束（这里有个符号错误）。注意你现在的代码是这样写的。我还建议你确保至少进入一次while循环，这样才能让近似解的数组有值。

Answer 2

看起来在 newtons_method() 返回一个值之前，它必须先自己再调用一次。例如：

def newtons_method(f, x, h=0.000001, epsilon=0.000001,):
    ...
    if abs((x - f(x)/df(x, h))-x)< epsilon:
       print 'Solution is:', round(newtons_method(f,x),6) # function called again here
       ...
       return x

    else:
       print 'Approximated solution is:', round(newtons_method(f,x),4) # and again here
       ...
       return x

所以第一次调用 newtons_method() 时，它不会返回，因为它必须在 return 之前再调用自己，然后那个函数调用也必须在 return 之前再调用自己，然后……

你能修改你的代码，让 newtons_method() 不以这种方式递归调用吗？