[算法设计与分析]4.1.3迭代法解方程(牛顿迭代法+二分法解方程)

#include<stdio.h>
#include<iostream>
#include<math.h>

using namespace std;

void NewtonIteration();//牛顿迭代法求解方程
void DichotomySolving();//二分法求解方程

int main ()
{
    NewtonIteration();
    DichotomySolving();
}

//牛顿迭代法：y=f(x0)+f'(x0)(x-x0)-> 0=f+f'(x-x0)->x=x0-f/f'
void NewtonIteration()
{
    int a = 3, b = 2, c = 1, d = -6;//系数

    float x1 = 1, x0;
    float f0, f1;//f0是原方程 f1是方程的一阶导
    do
    {
        x0 = x1;
        f0 = ((a * x0 + b) * x0 + c) * x0 + d;//即a*x^3+b*x^2+c*x+d
        f1 = (3 * a * x0 + 2 * b) * x0 + c;//一阶导数
        x1 = x0 - f0/f1;
    }while(fabs(x1 - x0) >= 1e-4);
    printf("(%d)x^3+(%d)x^2+(%d)x+(%d) = 0\n", a, b, c, d);
    cout << "方程的解为：" << x1 << endl;
}

void DichotomySolving()//二分法求解方程
{
    float x, x1 = 0, x2 = 2;
    float f1, f2, f;
    cout << "input x1, x2 (f(x1)*f(x2)<0)" << endl;
    //假设原方程为 1/2x^3+2x^2-8
    f1 = pow(x1, 3) / 2 + pow(x1, 2) * 2 - 8;
    f2 = pow(x2, 3) / 2 + pow(x2, 2) * 2 - 8;
    if(f1 * f2 > 0)
    {
        cout << "error" << endl;
        return;
    }
    do
    {
        x = (x1 + x2) / 2;
        f = pow(x, 3) / 2 + 2 * pow(x, 2) - 8;//f为飞f1
        if(f == 0)
            break;
        if(f1 * f > 0)//已知解一定在f1与f2之间 因此以f1为切入点逐步逼近解
        {//f1 * f > 0证明解在右半部分中 因此要将求解的范围右移
            x1 = x;
            f1 = f;
        }
        else
        {
            x2 = x;//解在左边 范围左移
        }
    }while(fabs(f) >= 1e-4);
    cout << "root = " << x << endl;
}