c++ - 简单的迭代算法

Question

如果给定一个非线性方程系数数组和某个范围，我们如何在给定范围内找到该方程的根？

例如:等式是

因此系数数组将是a 的数组。假设等式是

则系数数组为{ 1, -5, -9, 16 }。

正如 Google 所说，首先我们需要将给定的函数(实际上是方程)变形为其他函数。例如。如果给定的方程是 y = f(x)，我们应该定义其他函数，x = g(x) 然后执行算法:

while (fabs(f(x)) > etha)
  x = g(x);

找出根源。

问题是:如何使用系数数组和仅给定的范围来定义g(x)？

问题是:当我这样定义g(x)时

或

对于给定的方程式，x 的任何起始值都会引导我找到第二个方程式的根。他们中没有人会给我另外两个(根是 { -2.5, 1.18, 6.05 } 而我的代码只给出 1.18)。

我的代码是这样的:

float a[] = { 1.f, -5.f, -9.f, 16.f }, etha = 0.001f;

float f(float x)
{
    return (a[0] * x * x * x) + (a[1] * x * x) + (a[2] * x) + a[3];
}

float phi(float x)
{
    return (a[3] * -1.f) / ((a[0] * x * x) + (a[1] * x) + a[2]);
}

float iterationMethod(float a, float b)
{
    float x = (a + b) / 2.f;

    while (fabs(f(x)) > etha)
    {
        x = phi(x);
    }

    return x;
}

因此，调用 iterationMethod() 传递范围 { -3, 0 }、{ 0, 3 } 和 { 3, 10 将提供 1.18 数字 3 次。

我哪里错了，我应该怎么做才能让它正常工作？

UPD1:我不需要任何第三方库。

UPD2:我恰好需要“简单迭代”算法。

Answer 1

一种更传统的寻根算法是 Newton's method .迭代步骤涉及找到函数的一阶逼近的根

因此，如果我们有一个函数“f”并且位于点x0，则线性一阶近似将为

f_(x) = f'(x0)*(x - x0) + f(x0)

对应的近似根x'为

x' = phi(x0) = x0 - f(x0)/f'(x0)

(请注意，您需要手边有导数函数，但对于多项式来说应该很容易获得它)

---

牛顿法的优点是易于实现，而且速度通常很快。糟糕的是，有时它表现不佳:该方法在具有 f'(x) = 0 的点上失败，并且某些函数中的某些输入可能会发散(因此您需要检查并在需要时重新启动)。