r - 用 R 中的数值迭代器改进收敛算法

Question

我正在执行迭代计算来检查 y变化超过 x在 R 中。我的目标是估计 x 截距。现在每次迭代的计算成本都很高，因此实现此目标所需的迭代次数越少越好。

这是 y 的图片针对 x 绘制 我通过定义一个充分捕获问题的渐近函数创建了一个工作示例

y <- (-1/x)+0.05

当绘制产量

x <- 1:100
y <- (-1/x)+0.05
DT <- data.frame(cbind(x=x,y=y))
ggplot(DT, aes(x, y)) + geom_point() + geom_hline(yintercept=0, color="red")

我开发了两种迭代算法来近似 x 轴截距。

解决方案 1:x最初是很小的台阶1...n次。步骤的大小是预定义的，从大开始(增加 10 倍)。每一步之后 y.i被计算。如果abs(y.i) < y[i-1]然后重复那一大步，除非y.i更改符号，这表明该步骤超出了 x 截距。如果算法超调，那么我们回溯并采取更小的步骤(增加 2 倍)。随着每次超调，步长从 10*、2*、1.1*、1.05*、1.01*、1.005*、1.001* 开始越来越小。

x.i <- x <- runif(1,0.0001,0.001)
y.i <- y <- (-1/x.i)+0.05
i <- 2
while(abs(y.i)>0.0001){
  x.i <- x[i-1]*10
  y.i <- (-1/x.i)+0.05
  if(abs(y.i)<abs(y[i-1]) & sign(y.i)==sign(y[i-1])){
    x <- c(x,x.i); y <- c(y,y.i)
  } else {
    x.i <- x[i-1]*2
    y.i <- (-1/x.i)+0.05
    if(abs(y.i)<abs(y[i-1]) & sign(y.i)==sign(y[i-1])){
      x <- c(x,x.i); y <- c(y,y.i)
    } else {
      x.i <- x[i-1]*1.1
      y.i <- (-1/x.i)+0.05
      if(abs(y.i)<abs(y[i-1]) & sign(y.i)==sign(y[i-1])){
        x <- c(x,x.i); y <- c(y,y.i)
      } else {
        x.i <- x[i-1]*1.05
        y.i <- (-1/x.i)+0.05
        if(abs(y.i)<abs(y[i-1]) & sign(y.i)==sign(y[i-1])){
          x <- c(x,x.i); y <- c(y,y.i)
        } else {
          x.i <- x[i-1]*1.01
          y.i <- (-1/x.i)+0.05
          if(abs(y.i)<abs(y[i-1]) & sign(y.i)==sign(y[i-1])){
            x <- c(x,x.i); y <- c(y,y.i)
          } else {
            x.i <- x[i-1]*1.005
            y.i <- (-1/x.i)+0.05
            if(abs(y.i)<abs(y[i-1]) & sign(y.i)==sign(y[i-1])){
              x <- c(x,x.i); y <- c(y,y.i)
            } else {
              x.i <- x[i-1]*1.001
              y.i <- (-1/x.i)+0.05
            }
          }
        }
      }
    }
  }
  i <- i+1
}

解决方案 2:该算法基于 Newton-Raphson 方法的思想，其中步骤基于 y 的变化率.变化越大，采取的步骤越小。

x.i <- x <- runif(1,0.0001,0.001)
y.i <- y <- (-1/x.i)+0.05
i <- 2
d.i <- d <- NULL
while(abs(y.i)>0.0001){
  if(is.null(d.i)){
    x.i <- x[i-1]*10
    y.i <- (-1/x.i)+0.05
    d.i <- (y.i-y[i-1])/(x.i-x[i-1])
    x <- c(x,x.i); y <- c(y,y.i); d <- c(d,d.i)
  } else {
    x.i <- x.i-(y.i/d.i)
    y.i <- (-1/x.i)+0.05
    d.i <- (y.i-y[i-1])/(x.i-x[i-1])
    x <- c(x,x.i); y <- c(y,y.i); d <- c(d,d.i)
  }
  i <- i+1
}

比较

1. 解决方案 1 需要的迭代次数始终少于解决方案 2(如果不是 1/3，则为 1/2)。
2. 解决方案 2 更优雅，不需要任意减小步长。
3. 我可以设想解决方案 1 卡住的几种情况(例如，即使在最小的步骤中，循环也不会收敛到 y.i 的足够小的值)

问题

1. 在这种情况下是否有更好(迭代次数更少)的近似 x 轴截距的方法？
2. 谁能给我指出一些解决此类问题的文献(最好是为像我这样的初学者写的)？
3. 欢迎就代表此类问题/算法的术语或关键词提出任何建议。
4. 我提出的解决方案是否可以改进？
5. 欢迎就如何使更广泛的社区或具有潜在解决方案的专家更容易访问标题/问题提出任何建议。

Answer 1

根据@Lyngbakr 和@LutzL 的阅读推荐和建议，寻根算法称为Brent's Method证明是有效的，并且比我实现的 Newton-Raphson(解决方案 2)快得多。该算法由R中的uniroot实现。

f <- function(x){(-1/x)+0.05}
uniroot(f, interval=c(0,100), maxiter=100)