牛顿法

我们知道解线性方程和二次方程的简单公式及三次四次方程更为复杂的公式。然而对于大于4次的多项式方程不可能有类似的公式。这时候就需要微积分的数值方法来求解我们想要的根了。
牛顿法的解题步骤如下：

猜方程 $f(x) = 0$ 的解的第一个近似值。
确定递推公式 $x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$ ，并且迭代计算直到得到想要的精度。
以下是一些牛顿法的应用。

求平方根

假设我们想求n的平方根。那么我们需要解方程 $x^2 = n$ 。
确定 $f(x) = x^2 - n$ , $f'(x) = 2x$ .
步骤1. 估算方程的第一个近似值 $x_0 = \frac{n} {2}$
步骤2. 估算 $x_0 = n / 2$ 迭代计算 $x_{n+1} = x_{n} - \frac{f(x)}{f'(x)} = x_n - (\frac{x}{2} - \frac{n}{2x})$
以下是C++的计算代码：

#include <iostream>
using namespace std;
double sqrt(double n, double precision = 10e-8) {
    double x =  max(n / 2, n), delta = 0;
    while ((delta = x / 2 - n / (2 * x)) > precision) x -= delta;
    return x;
}
int main(int argc, const char * argv[]) {
    for (int i = 0; i <= 10000; ++i) {
        cout << sqrt(i) << endl;
    }
    return 0;
}

求立方根

如果我们需要求n的立方根，那么这里的 $f(x) = x^3 - n$ , $f'(x) = 3x^2$ , 我们需要计算递推公式 $x_{n+1} = x_n - \frac{f(x)}{f'(x)} = x_n - (\frac{x}{3} - \frac{n}{3x^2})$ 。以下是C++的计算代码：

#include <iostream>
#include <math.h>
using namespace std;
double cubeRoot(double n, double precision = 10e-8) {
    double x =  max(n / 2, n), delta = 0;
    while ((delta = x / 3 - (n / 3) * pow(1 / x, 2)) > precision) x -= delta;
    return x;
}
int main(int argc, const char * argv[]) {
    for (int i = 0; i <= 10000; ++i) {
        cout << cubeRoot(i) << endl;
    }
    return 0;
}

计算 $\pi$

这里我们利用公式 $tan(\pi) = 0$ 来计算 $\pi$ 的值。可以确定 $f(x) = tan(x)$ , $f'(x)=sec^2$ , 由于 $\pi$ 的值大概是3.14，我们可以设定 $x_0 = 3$ , 递推公式为 $x_{n+1} = x_n - \frac{f(x)}{f'(x)} = x_n - tan(x)cos^2(x)$ 。
以下是C++的计算代码:

#include <iostream>
#include <math.h>
using namespace std;
double pi() {
    double x = 3;
    double delta = 0;
    while (abs(delta = tan(x) * pow(cos(x), 2)) > 10e-8) {
        x -= delta;
    }
    return x;
}
int main(int argc, const char * argv[]) {
    cout << pi() << endl;
    return 0;
}