非线性代数方程(组)的所有根的无限精度的 逆天算法？

wayne

Mathematica的最新版本12.3有了好像很逆天的算法。
任意给定一个非线性代数方程(组)，Mathematica都能给出指定区间的所有的根的无限精度，无需预设初始值。
这个理论上是怎么做到的？

比如，对于 $x sin(\frac{1}{x})=\frac{1}{10000}$

1. c = 10^-4; SolveValues[x Sin[1/x] == c && -100 < x < 100, x, Reals]

复制代码

直接返回了6366个根的Root符号表达。

zeroieme

嗯，专业的果然吊打我这个业余的

————————————瞌睡后的分割线————————————————

慢着！Root表达会不会只是暂缓求值？

wayne

再比如$x^2 \sin \left(x^3+x\right)+\tan \left(\frac{1}{x}\right)=0$

1. Solve[x^2Sin[x+x^3]+Tan[1/x]==0&&100<x<101,x,Reals]

复制代码

在区间内[100,101],有 9646 个根

kastin

刚刚看了官网ref页，说是只适合多项式方程和线性方程(组)的求解，不知道实际上如何。个人感觉很难实现超越方程都能求出指定区间所有解，否则的话，全局最优化就不是问题了，牛顿迭代法及其衍生版本可以退出历史舞台了。

会不会是对超越方程只是给出根的数目而不求解？但如果能给出根的精确数目，这也不是一件容易的事，毕竟函数曲线可能出现各种奇异表现，容易漏掉一些根。

mathe

严格找到所以零点会很困难，但是可以以较高概率找到大部分零点。假设我们已经找到若干个零点，这些零点会将目标区间划分为若干小区间。在每个区间再均匀采样若干个点，如果函数取值都同号，可以判断为大概率没有零点

wayne

zeroieme 发表于 2021-5-22 22:38
嗯，专业的果然吊打我这个业余的

Mathematica创新的地方 我觉得有两个
1）超越数的符号表达。
Mathematica自创了一种数据结构， 就是 Root[{expr,x0}]，expr本质上是非线性方程表达式，然后x0是初始值。在x0处的邻域。所以， 我觉得在理论上应该是至少要证明非线性方程在 x0邻域内是可以快速收敛的，任意精度的计算。
2）解的无漏
给定一个区间，要能无漏的 给出所有解的这种表达。

wayne

为了试探Mathematica的极限。 我选择了一个病态的方程$x+\tan (\frac{1}{x}) =0$ 在$x \in [0,1]$内的解。
软件报了一个warining。并返回了101个解。

1. {a,b}={0,1};Solve[Tan[1/x]+x==0&&a<x<b,x]

复制代码

1. Solve::incs: Warning: Solve was unable to prove that the solution set found is complete.

复制代码

这个警告的意思是说 无法证明 解集 是完整的。这就对了。 算法背后是有理论 证明解集的完整性的
然后我再缩小 区间$x \in [10^{-5},10^{-4}]$。看Mathematica这么拼,我也挺有耐心的，等待了几十分钟，返回了$28647$个解，

1. {a,b}={10^-5,10^-4};ans=Solve[Tan[1/x]+x==0&&a<x<b,x]

复制代码

kastin

wayne 发表于 2021-5-23 12:37
Mathematica创新的地方 我觉得有两个
1）超越数的符号表达。
Mathematica自创了一种数据结构， 就是 Root ...

"非线性方程在 x0邻域内是可以快速收敛的"，如果是这样的，那么给出Root[{expr,x0}]等价于给出了精确的根。无非就是一个时间问题。但实际上，若能给出精确根，那么一大部分优化问题就不是问题了（添加拉格朗日乘子，令梯度为零，然后检验高阶梯度符号，可求最值）。那么对于可以解析表示的函数最优化问题，基本上不需要用什么遗传算法、模拟退火之类了。因此，我觉得这个x0不一定保证可以快速收敛到真正的根。Root[{expr,x0}]也许只是说，在x0附近的根而已。我看了下ref，它确实是说表示在x0附近的精确根，没有提到一定能通过迭代算法快速收敛。不过你可以试试，检验一下这个x0是不是任何情况下都能快速受到到根，还是说有些情况无法收敛到根。

mathe

如果我们能够验证在一个小区间内部连续二阶可微函数二阶函数不变号，在两个端点函数值符号相反，那么就可以证明区间内部只有唯一零点，而且可以用牛顿迭代法快速收敛

wayne

mathe 发表于 2021-5-23 21:44
如果我们能够验证在一个小区间内部连续二阶可微函数二阶函数不变号，在两个端点函数值符号相反，那么就可以 ...

换句话说，就是在给定区间内 二阶导函数的最大值和最小值是同号的。。，于是根的唯一性问题变成了 最优化问题了。