使用根查找算法查找多个根

Question

找到具有多个根的方程根的最佳方法是什么？我明白，没有一种方法可以解决每个方程，并且您必须使用多个方法，但是我找不到可以在最简单的情况下解决多个根问题的根算法。

例如：y = x^2

虽然根求解算法，解决了基本方程这样是有帮助的，它需要的东西，我可以适应求解方程有两个以上的根。

还有一点要注意的是，公式不会是典型的多项式，但可能是因为ln(x^2) + x - 15 = 0

这样的东西是什么，可以解决这一点，否则你怎么能编辑求根算法（如Bisection/Newton/Brent方法）来解决这个问题，（假设我正确的说牛顿和布伦特方法只能求解一个根）。

Answer 1

我想说，没有一般的方法来找到一般方程的所有根。但是，一旦指定了足够的条件，就可以尝试设计方法。即使是简单的二次方程ax + bx + c = 0并不是完全无关紧要的，因为实根的存在取决于b的符号，这并不明显。因此，有很多的技术应用，例如Newton-Raphson，但一般情况下没有通用的方法，特别是对于像LN方程（X ）+ X-15 = 0

Answer 2

底线：您需要隔离自己的根。

细节取决于算法： 如果您使用平分法或布伦特法，您需要提出一组含有唯一根的间隔。 如果使用牛顿的方法，你需要提出一组起始估计（因为它收敛到一个根给定的起点，并有不同的起点可能会或可能不会收敛到不同的根）。

Answer 3

正如大家所说，不可能提供一个通用算法来查找所有或某些根（其中一些大于一）。有多少根？一般来说，你无法找到所有的根，因为许多函数将具有无穷多的根。

即使像牛顿这样的方法并不总是趋于解决方案。我倾向于喜欢一个好的，相当稳定的方法，它将在合理的情况下融合到一个解决方案，比如已知函数会改变符号的括号。你可以找到这样一个代码，它在单根上有很好的收敛行为，但是当函数表现不好时，它仍然可以被保护起来，基本上就像一个二分法。

因此，给定一个体面的根发现计划，你可以尝试简单的事情，如通货紧缩。因此，考虑一个简单的函数，就像第一类贝赛尔函数。我将使用MATLAB来完成所有的例子，但是任何在MATLAB中具有像fzero这样稳定良好的rootfinder的工具就足够了。

ezplot(@(x) besselj(0,x),[0,10]) 
grid on 

f0 = @(x) besselj(0,x); 
xroots(1) = fzero(f0,1) 
xroots = 
    2.4048 

从情节，我们可以看到有5周围的第二根或6。

现在，为该根放大f0，根据f0创建一个新函数，但在xroots（1）中缺少一个根。

f1 = @(x) f0(x)./(x-xroots(1)); 
ezplot(f1,[0,10]) 
grid on 

注意，在这个曲线中，F0在xroots根（1）目前已轮回一圈走，就好像它不存在。我们能找到第二个根吗？

xroots(2) = fzero(f1,2) 
xroots = 
    2.4048 5.5201 

我们当然可以继续下去，但是在某些时候这个方案会因数值问题而失败。而这种失败也不会太长。

一个更好的方案可能是（对于一维问题）使用包围方案，并结合抽样方法。我说得更好，因为它不需要修改初始功能来压缩根源。 （有关2-d或更高，事情就变得更加有毛当然）。

xlist = (0:1:10)'; 
flist = f0(xlist); 

[xlist,flist] 
ans = 
     0 1.0000 
    1.0000 0.7652 
    2.0000 0.2239 
    3.0000 -0.2601 
    4.0000 -0.3971 
    5.0000 -0.1776 
    6.0000 0.1506 
    7.0000 0.3001 
    8.0000 0.1717 
    9.0000 -0.0903 
    10.0000 -0.2459 

正如你可以看到，该函数具有登入的时间间隔[2,3]变化，[5,6]，和[8,9]。可以在支架中搜索的Rootfinder将在这里执行。

fzero(f0,[2,3]) 
ans = 
    2.4048 

fzero(f0,[5,6]) 
ans = 
    5.5201 

fzero(f0,[8,9]) 
ans = 
    8.6537 

只需查找符号更改，然后将已知括号放入根查找程序。这将提供尽可能多的解决方案，您可以找到括号。

请注意，上述方案存在严重问题。它完全无法找到像f（x）= x^2这样简单函数的双根，因为没有符号变化存在。如果您选择的抽样太粗糙，那么您可能会有一个带有两个根的间隔，但您在终点处不会看到符号更改。例如，考虑函数f（x）= x^2-x，其单根在0和1处。但是如果在-1和2处对该函数进行采样，则会发现它是正的两点。没有迹象改变，但有两个根源。

此外，NO方法可以做到完美。你总是可以设计一个能够导致任何这种数值方法失败的函数。