单调函数的高效求根算法

计算科学 计算几何
2021-12-02 18:31:25

这是我第一次在这里问问题,所以我可能没有在正确的地方问这个问题。我试图用尽可能少的函数评估来找到单调函数的根。

我已经用分段定义的多项式逼近了一个流形。流形是周期性的,所以我只考虑它的单位单元(一个周期)。我将单元格(通常是平行四边形,但在本例中为正方形)拆分为三角形。

在此处输入图像描述

然后,我用一个唯一的二次多项式来近似每个三角形内的流形的每个表。

在此处输入图像描述

我想找到满足方程的根

isheetsjtrianglespi,j(x,y)dCi,jA=0
在哪里i是流形表的总和,j是三角形瓷砖的总和,pi,j是流形的二次多项式逼近i内的表j瓷砖,和Ci,j是流形的多项式逼近的水平曲线内的区域i内的表j瓷砖。这是一个情节Ci,j对于每个三角形和薄片,对根进行一些估计。

在此处输入图像描述

换句话说,我想找到一个等值,其中多项式水平曲线内的区域,多项式小于等值的区域,是某个预定值A.

目前我正在使用二分法,这非常慢,因为在每次迭代中,都需要花费大量时间来插入流形,然后计算水平曲线及其包含区域。我可能有数百个三角形和数十张纸。

我也尝试了常规的 falsi 方法,但遇到了收敛性比二分法差的情况。

1个回答

似乎您主要关心的是在尽可能少的迭代中将根括起来,因为每次迭代都是昂贵的。在某些情况下,您发现 regula falsi 方法不可靠,这表明根上的界限可能很大,或者函数不能很容易地线性逼近。要在不明显慢于二分法的情况下处理此类情况,您可能需要尝试Brent 的方法它结合了二分法和类似于 regula falsi 方法的概念,以尽可能加快收敛速度​​。

如果您确定根应该是简单的,则可以使用 Chandrupatla 的方法。根据我的经验,当初始迭代从二分法中受益最多时,它往往比布伦特的方法更快。

如果您不需要这么快的速度,伊利诺伊方法也可能就足够了。它是对regula falsi 方法的改进,极大地提高了收敛速度和可靠性。虽然不如上述算法快/可靠,但它要简单得多。