牛顿法特殊形式——开方公式与二分逼近开方的

数值分析-开方公式

// 开方公式
#include<bits/stdc++.h>

using namespace std;

int main()
{
    double c, x0, jingdu;
    printf("请输入被开方数c：");
    scanf("%lf", &c);
    printf("请输入初值x0：");
    scanf("%lf", &x0);
    printf("请输入精度（用小数表示）：");
    scanf("%lf", &jingdu);

    double xk, xk1 = x0;
    int i = 0;
    do {
        i++;
        xk = xk1;
        xk1 = 0.5 * (xk + c / xk);
        printf("x%d = %lf\n", i, xk1);
    } while (abs(xk1 - xk) > jingdu);

    printf("故 √c ≈ x%d = %lf\n", i, xk1);

    return 0;
}

二分逼近开方

#include<iostream>

using namespace std;
using ll = long long;

const int N = 5000 + 10;

int n;

int main()
{
    double c, jingdu;
    printf("------------------二分逼近------------------\n");
    printf("请输入被开方数c：");
    scanf("%lf", &c);
    printf("请输入精度（用小数表示）：");
    scanf("%lf", &jingdu);

    double l = 0, r = max(1.0, c), mid = 0;
    int i = 0;
    while(abs(mid * mid - c) > jingdu) {
        i++;
        mid = (l + r) / 2.0;
        if (mid * mid < c) l = mid;
        else r = mid;
        printf("x%d = %lf\n", i, mid);
    }

    printf("故 √c ≈ x%d = %lf\n", i, mid);

    return 0;
}

对比总结

二分逼近的复杂度是O(logN)*
开方公式的时间复杂度是O(k)=O(loglogN)**
开方公式的收敛速度更快。