Newton迭代法数学原理

求非线性方程 f ( x ) = 0 f(x) = 0 f(x)=0的根 x ∗ x^{*} x∗，牛顿迭代法计算公式

x 0 = α x_{0} = \alpha x0​=α

x n + 1 = x n − f ( x n ) f ′ ( x n ) x_{n + 1} = x_{n} - \frac{f(x_{n})}{f^{'}(x_{n})} xn+1​=xn​−f′(xn​)f(xn​)​

n = 0 , 1 , ⋯ n = 0,1,\cdots n=0,1,⋯

一般地，牛顿迭代法具有局部收敛性，为保证迭代收敛，要求，对充分小的 δ > 0 \delta > 0 δ>0， α ∈ O ( x ∗ , δ ) \alpha \in O(x^{*},\delta) α∈O(x∗,δ)。如果 f ( x ) ∈ C 2 [ a , b ] f(x) \in C^{2}\lbrack a,b\rbrack f(x)∈C2[a,b]， f ( x ∗ ) = 0 f(x^{*}) = 0 f(x∗)=0， f ′ ( x ∗ ) ≠ 0 f^{'}(x^{*}) \neq 0 f′(x∗)​=0，那么，对充分小的 δ > 0 \delta > 0 δ>0，当 α ∈ O ( x ∗ , δ ) \alpha \in O(x^{*},\delta) α∈O(x∗,δ)时，由牛顿迭代法计算出的 { x n } \{ x_{n}\} {xn​}收敛于 x ∗ x^{*} x∗，且收敛速度是2阶的；如果 f ( x ) ∈ C m [ a , b ] f(x) \in C^{m}\lbrack a,b\rbrack f(x)∈Cm[a,b]， f ( x ∗ ) = f ′ ( x ∗ ) = ⋯ = f ( m − 1 ) ( x ∗ ) = 0 f(x^{*}) = f^{'}(x^{*}) = \cdots = f^{(m - 1)}(x^{*}) = 0 f(x∗)=f′(x∗)=⋯=f(m−1)(x∗)=0， f ( m ) ( x ∗ ) ≠ 0 ( m > 1 ) f^{(m)}(x^{*}) \neq 0(m > 1) f(m)(x∗)​=0(m>1)，那么，对充分小的 δ > 0 \delta > 0 δ>0，当 α ∈ O ( x ∗ , δ ) \alpha \in O(x^{*},\delta) α∈O(x∗,δ)时，由牛顿迭代法计算出的 { x n } \{ x_{n}\} {xn​}收敛于 x ∗ x^{*} x∗，且收敛速度是1阶的；

问题

利用牛顿迭代法求 f ( x ) = 0 f(x) = 0 f(x)=0的根

输入：初值 α \alpha α，精度 ε 1 , ε 2 \varepsilon_{1},\varepsilon_{2} ε1​,ε2​，最大迭代次数 N N N

输 出：方程 f ( x ) = 0 f(x) = 0 f(x)=0根 x ∗ x^{*} x∗的近似值或计算失败标志

程序流程

核心代码

#include <cmath>
#include <cstdio>
#include <iostream>
using namespace std;

double x, e1, e2;
int n;

double f(double x) { return cos(x) - x; }
double df(double x) { return -sin(x) - 1; }

int main() {
    scanf("%lf%lf%lf%d", &x, &e1, &e2, &n);
    for (int i = 1; i <= n; i++) {
        double F = f(x), DF = df(x);
        if (fabs(F) < e1) {
            printf("%lf", x);
            return 0;
        }
        if (fabs(DF) < e2) {
            printf("Failed");
            return 0;
        }
        double x1 = x - F / DF;
        double tol = fabs(x - x1);
        if (tol < e1) {
            printf("%lf", x1);
            return 0;
        }
        x = x1;
    }
    printf("Failed");
    return 0;
}

详细报告