Python - 牛顿法

Question

我是 Python 新手，我需要编写一个牛顿法脚本。

我一直在尝试这样做，但我不断收到错误或没有返回...

这是作业：

---

一个函数

newton(f, x, feps, maxit)

需要：

• 一个函数

  f(x)

  ,
• 函数 f(x) 的根的初始猜测

  x

  ，
• 允许的公差

  feps

  ,
• 以及允许的最大迭代次数

  maxit

  。

牛顿函数应使用以下牛顿-拉夫森算法：

while |f(x)| > feps, do
   x = x - f(x) / fprime(x)

其中

fprime(x)

是位置

x

处的一阶导数 (df(x)/dx) 的近似值。您应该使用本实验训练部分的导数函数。

确保将导数函数定义从training7.py复制到lab7.py（有更优雅的方法可以做到这一点，但出于评估的目的，这是我们推荐的最直接的方法）。

如果 |f(x)| 需要

maxit

或更少的迭代次数变得小于

feps

，则应返回 x 的值：

In [ ]: def f(x):
   ....:     return x ** 2 - 2
   ....:

In [ ]: newton(f, 1.0, 0.2, 15)
Out[ ]: 1.4166666666783148

In [ ]: newton(f, 1.0, 0.2, 15) - math.sqrt(2)
Out[ ]: 0.002453104305219611

In [ ]: newton(f, 1.0, 0.001, 15)
Out[ ]: 1.4142156862748523

In [ ]: newton(f, 1.0, 0.001, 15) - math.sqrt(2)
Out[ ]: 2.1239017571339502e-06

In [ ]: newton(f, 1.0, 0.000001, 15) - math.sqrt(2)
Out[ ]: 1.5949463971764999e-12

---

这是我尝试做的，但这是完全错误的：

def derivative(f, x):
    """A function derivative(f, x) which computes a numerical approximation of
    the first derivative of the function f(x) using central differences."""
    R = (f(x + (10 ** -6) / 2.0) - f(x - (10 ** -6) / 2.0)) / (10 ** -6)
    return R


def newton(f, x, feps):
    """A function newton(f, x, feps, maxit) which takes a function f(x) and
    an initial guess x for the root of the function f(x), an allowed tolerance
    feps and the maximum number of iterations that are allowed maxit. The
    newton function should use the following Newton-Raphson algorithm:
    while |f(x)| > feps, do
    x = x - f(x) / fprime(x)
    where fprime(x) is an approximation of the first derivative (df(x)/dx) at
    position x."""
    while abs(f(x) > feps):
        fprime(x) = derivative(f, x)
        Result = x - f(x) / fprime(x)
        return Result

我应该怎么做才能让它发挥作用？

Answer 1

在 while 循环的第一步后返回结果

    while abs(f(x) > feps):
        fprime(x) = derivative(f, x)
        Result = x - f(x) / fprime(x)
        return Result

这样做

    while abs(f(x) > feps):
        fprime(x) = derivative(f, x)
        Result = x - f(x) / fprime(x)
    return Result

附注但我不确定你的代码是否正常工作

fprime(x) = derivative(f, x)

- 这不是 python 的正确语法

我认为这段代码一定更正确

    while abs(f(x) > feps):
        x = x - f(x) / derivative(f, x)
    return x

对于牛顿法，您必须获得类似递归的结果并检查最佳近似值。

            f(x)
Xn+1 = Xn - -----
            f'(x)

您会循环检查何时最适合您

附注抱歉我的伪数学代码

Answer 2

参见用于您的函数的 this 示例 - 将

f

f 和

df

传递给您的

newton

函数，如下所示：

def f(x):
    return x ** 2 - 2

def derivative(f, x):
    """A function derivative(f, x) which computes a numerical approximation of
    the first derivative of the function f(x) using central differences."""
    R = (f(x + (10 ** -6) / 2.0) - f(x - (10 ** -6) / 2.0)) / (10 ** -6)
    return R

# https://patrickwalls.github.io/mathematicalpython/root-finding/newton/
def newton(f,Df,x0,epsilon,max_iter):
    # Approximate solution of f(x)=0 by Newton's method.
    xn = x0
    for n in range(0,max_iter):
        fxn = f(xn)
        if abs(fxn) < epsilon:
            print('Found solution after',n,'iterations.')
            return xn
        Dfxn = Df(f, xn)
        if Dfxn == 0:
            print('Zero derivative. No solution found.')
            return None
        xn = xn - fxn/Dfxn
    print('Exceeded maximum iterations. No solution found.')
    return None

##f = lambda x: x**3 - x**2 - 1
##Df = lambda x: 3*x**2 - 2*x
approx = newton(f,derivative,1,1e-10,10)
print(approx)

牛顿法需要详细说明 𝑓′(𝑥)/𝑓′′(𝑥) 𝑓𝑜𝑟 𝑓′(𝑥) = 𝑓′′(𝑥) = 0，意味着程序将因除零错误而停止。

附注机器学习中的有用性（尽管由于二阶推导而成本高昂）：

如果我们的误差函数是二次的，这将找到全局最优值 一步到位！

例如在岭回归中，我想