数学研发论坛

 找回密码
 欢迎注册
查看: 604|回复: 27

[原创] 非线性代数方程(组)的所有根的无限精度的 逆天算法?

[复制链接]
发表于 2021-5-22 21:47:16 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
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符号表达。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-5-22 22:38:09 | 显示全部楼层
本帖最后由 zeroieme 于 2021-5-22 23:07 编辑

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

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

慢着!Root表达会不会只是暂缓求值?

点评

Mathematica自创了一种数据结构, 就是 Root[{expr,x0}],expr本质上是非线性方程表达式,然后x0是初始值。在x0处的邻域。所以, 我觉得在理论上应该是至少要证明非线性方程在 x0邻域内是可以快速收敛的,任意精度的   发表于 2021-5-23 16:20
要能无漏解,这个本身是有挑战的吧  发表于 2021-5-23 09:57
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2021-5-22 23:01:28 | 显示全部楼层
再比如$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 个根
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-5-23 10:35:35 | 显示全部楼层
刚刚看了官网ref页,说是只适合多项式方程和线性方程(组)的求解,不知道实际上如何。个人感觉很难实现超越方程都能求出指定区间所有解,否则的话,全局最优化就不是问题了,牛顿迭代法及其衍生版本可以退出历史舞台了。

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

点评

哦哦哦,也对。好像在 自动控制原理里 多项式的递推关系是线性方程。非多项式的递推就是非线性。  发表于 2021-5-23 21:53
@wayne 多项式方程本身就是非线性方程  发表于 2021-5-23 21:14
漏解的时候 软件一定会 报warning出来  发表于 2021-5-23 16:20
不漏解  发表于 2021-5-23 16:19
也适用于非线性方程  发表于 2021-5-23 16:19
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-5-23 12:19:14 来自手机 | 显示全部楼层
严格找到所以零点会很困难,但是可以以较高概率找到大部分零点。假设我们已经找到若干个零点,这些零点会将目标区间划分为若干小区间。在每个区间再均匀采样若干个点,如果函数取值都同号,可以判断为大概率没有零点
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2021-5-23 12:37:47 | 显示全部楼层
zeroieme 发表于 2021-5-22 22:38
嗯,专业的果然吊打我这个业余的
Mathematica创新的地方 我觉得有两个
1)超越数的符号表达
Mathematica自创了一种数据结构, 就是 Root[{expr,x0}],expr本质上是非线性方程表达式,然后x0是初始值。在x0处的邻域。所以, 我觉得在理论上应该是至少要证明非线性方程在 x0邻域内是可以快速收敛的,任意精度的计算。
2)解的无漏
给定一个区间,要能无漏的 给出所有解的这种表达。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2021-5-23 12:44:41 | 显示全部楼层
为了试探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]
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-5-23 21:33:58 | 显示全部楼层
wayne 发表于 2021-5-23 12:37
Mathematica创新的地方 我觉得有两个
1)超越数的符号表达。
Mathematica自创了一种数据结构, 就是 Root ...


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

点评

我添加 "快速收敛" 是想强调 邻域性。  发表于 2021-5-23 21:58
ref里并没有说是 快速收敛。这个是我自己擅自添加的,汗....  发表于 2021-5-23 21:58
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-5-23 21:44:46 来自手机 | 显示全部楼层
如果我们能够验证在一个小区间内部连续二阶可微函数二阶函数不变号,在两个端点函数值符号相反,那么就可以证明区间内部只有唯一零点,而且可以用牛顿迭代法快速收敛
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2021-5-23 21:57:07 | 显示全部楼层
mathe 发表于 2021-5-23 21:44
如果我们能够验证在一个小区间内部连续二阶可微函数二阶函数不变号,在两个端点函数值符号相反,那么就可以 ...


换句话说,就是在给定区间内 二阶导函数的最大值和最小值是同号的。。,于是根的唯一性问题变成了 最优化问题了。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2021-6-21 02:06 , Processed in 0.059802 second(s), 17 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表