具有单调性的二维非线性方程组的迭代求根

计算科学 算法
2021-12-20 00:00:58

f(x,y)g(x,y)成为两个R2R函数,在两个参数中都严格递增。假设它们是表现良好的函数(连续、可微等)

鉴于这些属性,我想找到以下方程组的根:

f(x,y)=f0
g(x,y)=g0

假设存在解决方案并且它是唯一的。

是否有一种有效的算法可以迭代地在越来越小的区域中对根进行括号括起来R2? 也就是说,我正在寻找一种无导数的方法,它是二分法的扩展,用于 2 个变量,并保证收敛。

2个回答

因为函数是严格递增的,所以可以简化为一维情况。在每个一维问题中,都有更有效的标准方法可用,比二分法更有效,这也意味着不必自己想出非标准方法。毕竟,一维求根是一个“已解决”的标准问题。

不失一般性,假设f0=g0=0, 并定义xf=xf(y)xg=xg(y)成为解决方案f(xf(y),y)=0, 和g(xg(y),y)=0, 分别。两个都xf,xg是定义良好的严格递减函数y,并且可以通过一维寻根,甚至二等分来进行数值评估。那么共同的根f=g=0对应于一个解决方案xf(y)xg(y)=0,这又是一个一维问题。

必须适当地选择初始括号,以便正确地将每个一维问题的根括号括起来。从几何上讲,可以选择一个有顶点的矩形(x,y),(x+,y+)使得曲线x=xf(y)x=xg(y)穿过矩形y=const仅边界(绘制它更容易),并在矩形内相互交叉(必须只有一次)。

假设您最初可以将根“括起来”,这意味着您有四个点(xi,yi),i=1,...,4这样:

f(x1,y1)<f0 and g(x1,y1)<g0,
f(x2,y2)<f0 and g(x2,y2)>g0,
f(x3,y3)>f0 and g(x3,y3)<g0,
f(x4,y4)>f0 and g(x4,y4)>g0.

那么我们可以保证方程组的一个根包含在四个点的凸包中。

算法可以迭代以下两个步骤:

  1. 计算四个点的质心。
  2. 用质心替换四个点之一。选择替换的点以使上述八个不等式仍然适用于新的四个点集。

四个点的凸包面积最终会缩小,从而将根定位到任意精度。

我无法分析凸包面积减小的速度。此外,找到最初四个点的稳健方法将很有用。另外,我声称四个点的凸包包含一个根,但我无法对这个陈述给出严格的证明(我认为直觉上是正确的,但我可能是错的)。