「学习笔记」牛顿迭代法

牛顿迭代法（Newton′smethod$Newto{n}^{\prime }smethod$）一般用于求函数的一个零点。

牛顿迭代法

牛顿迭代法三个步骤：

1. 随机 / 猜一个p$p$值
2. 求x=p$x=p$时的切线，即求导数
3. 令p=$p=$切线零点，返回步骤2$2$，重复若干次.

即：xn+1=xn−f(xn)f′(xn)$x_{n+1}=x_n-\frac{f(x_n)}{f^{\prime }(x_n)}$

重复得越多得到的根越精确，一般达到精度要求就可以停止.

例：求f(x)=x3−2x2+x−1$f(x)=x^3-2x^2+x-1$的一个零点

首先求出导数f′(x)=3x2−4x+1$f^{\prime }(x)=3x^2-4x+1$.然后就开始牛顿迭代.

#include <cstdio>
#include <cmath>

#define f(x) (x*x*x-2*x*x+x-1)
#define f1(x) (3*x*x-4*x+1)

int main() {
    double x = 111, nx;
    const double eps = 1e-6;
    while(true) {
        nx = x - f(x) / f1(x);
        if(fabs(nx - x) < eps) break;
        x = nx;
    }
    printf("%f\n", x);
    return 0;
}

牛顿迭代法的应用

应用：只能求函数零点

应用除了求函数零点外，还可以求解：

a−−√m$$\sqrt[m]{a}$$

方法：设b=a−−√m$b=\sqrt[m]{a}$，则a=bm$a=b^m$，转换成求f(b)=bm−a$f(b)=b^m-a$的零点

首先求导。f′(b)=mbm−1$f^{\prime }(b)=m{b}^{m-1}$

下面是求平方根的程序：

#include <cstdio>
#include <cmath>

#define f(b) (b*b-a)
#define f1(b) (2*b)

double Sqrt(double a) {
    double x = 111, nx;
    const double eps = 1e-6;
    while(true) {
        nx = x - f(x) / f1(x);
        if(fabs(nx - x) < eps) break;
        x = nx;
    }
    return x;
}

int main() {
    double x;
    scanf("%lf", &x);
    printf("%f\n", Sqrt(x));
    return 0;
}