Dart

Question

我试图在函数中找到所有根 [f(x) = 0]。我目前的解决方案只有在它们间隔足够大并且不会相互干扰的情况下才有效。（例如，它适用于 x^2 - 2）

bool numberIsCloseToZero(num number){
  return (num.parse(number.abs().toStringAsFixed(1)) == 0.0) ? true : false;
}

List<num> calculateRoots(String function){

  num eval = 0.0;
  List<num> roots = [];

  for (num x = -10; x < 10; x += 0.1){
    eval = calculateYOfX(function, x);
    if (numberIsCloseToZero(num.parse(eval.toStringAsFixed(2)))){
      roots.add(x);
    }
  }
  return roots;
}

显然，这是由于我四舍五入造成的。（例如，x^2 的根的周围值太接近于零，因此它假定它们也是根）。你认为我应该通过实际求解方程而不是 "brute forcing" 求根吗？

谢谢

Answer 1

如果你能找到解析解 - 使用它。低次多项式方程是可能的（如提到的x^2 - 2）。

在一般情况下 - 你肯定必须学习数值方法 - 在这种情况下，root finding。

从bisection method or Newthon's方法开始。它们允许在每一步获得越来越准确的根位置。

Answer 2

你需要对允许的功能进行一些限制，否则你没有希望。

例如，在没有任何限制的情况下，您不能保证只有有限数量的值（考虑 f(x)=sin(x) ），甚至不能保证给定区间内的有限数量的值（考虑 f(x)=x sin(1/x)）。甚至是无限个相连的零点 ( f(x) = max(0,x) )

而且这些情况甚至不被认为是特别病态的数学函数。

如果您愿意沿着要求您的函数几乎处处非零、平滑、连续且具有有界的一阶和二阶导数的道路前进，那么我认为您可以想出一个相对简单的算法，可确保您在给定的有限区域内获得所有零。

（我会寻找一种基于细分的算法，该算法递归地分割区域并确定每个间隔的严格界限。）

当导数受已知常数限制时，我们可以推导出一个示例算法，即 |f'(x)| < D。请注意，如果我们在某个点 p 评估 f，那么对于任何其他点 p+d 我们可以证明 f(p) - |d| D < f(p+d) < f(p) + |d| D。

使用这个我们可以考虑在区间 [A,B] 中求根 - 我们可以写成 [p-d, p+d] 其中 p=(A+B)/2, d=(B-A)/2。在中点采样 f 得到 f(p)。最小值f可以取区间为f(p) - d D，最大值为f(p) + d D。如果 f(p)-d D <= 0 <= f(p) +d D 等价于 |f(p)| < d D，我们只能在这个区间内有一个根。

如果 [A,B] 中没有根，我们就完成了，否则我们在 [A,p] 和 [p,B] 的两半上重复。（在 f(p)=0 的情况下需要注意）

Dart - 查找函数中的所有根

Dart - Find all roots in a function

math

equation