简单迭代算法

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编号。

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

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

UPD2：我需要精确的“简单迭代”算法。

Answer 1

您在评论中发布的链接解释了为什么您无法用此算法找到所有根--只有当|phi'(x)| < 1围绕根时，它才会收敛到根。多项式的任何根都不是这种情况；对于大多数起点，迭代最终会在中间根附近反弹，并最终意外地接近它；它几乎肯定永远不会接近其他根，无论它从哪里开始。

要找到这三个根，您需要一个更稳定的算法，如牛顿法 (您链接到的教程中也对此进行了描述)。这也是一种迭代方法；您可以使用迭代f(x)找到x -> x - f(x)/f'(x)的根。这仍然不能保证收敛，但收敛条件要宽松得多。对于多项式，它可能看起来有点像这样：

#include <iostream>
#include <cmath>

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 df(float x)
{
    return (3 * a[0] * x * x) + (2 * a[1] * x) + a[2];
}

float newtonMethod(float a, float b)
{
    float x = (a + b) / 2.f;
    while (fabs(f(x)) > etha)
    {
        x -= f(x)/df(x);
    }

    return x;
}

int main()
{
    std::cout << newtonMethod(-5,0) << '\n'; // prints -2.2341
    std::cout << newtonMethod(0,5) << '\n';  // prints  1.18367
    std::cout << newtonMethod(5,10) << '\n'; // prints  6.05043
}

还有许多其他的寻根算法；这里是一个很好的开始学习的地方。

Answer 2

比较传统的寻根算法之一是牛顿法.迭代步骤涉及到求函数的一阶逼近的根。

因此，如果我们有一个函数'f‘，并且在一个点x0，则线性裂变阶逼近将是

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

相应的近似根x'是

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

(请注意，您需要方便地使用导数函数，但是对于多项式，它应该非常容易获得)

牛顿法的优点是易于实现，而且速度往往很快。不好的是，有时它的行为不太好:方法在具有f'(x) = 0和某些函数中的某些输入的点上会失败(因此您需要检查它并在需要时重新启动)。