0

许多数值问题的形式如下：

initialize:  x_0 = ...
iterate:     x_i+1 = function(x_i) until convergence, e.g., 
             || x_i+1 - x_i || < epsilon

我想知道是否有一种很好的方法可以使用惯用的 Scala 编写这样的算法。问题的性质要求使用Iteratoror Stream。但是，我目前对此的看法真的很丑：

val xFinal = Iterator.iterate(xInit) { x_i =>
  // update x_i+1
}.toList      // necessary to pattern match within takeWhile
 .sliding(2)  // necessary since takeWhile needs pair-wise comparison
 .takeWhile{ case x_i :: x_iPlus1 :: Nil => /* convergence condition */ }
 .toList      // since the outer container is still an Iterator
 .last        // to get the last element of the iteration
 .last        // to get x_iPlus1

这不仅丑陋，模式匹配takeWhile也会引起警告。显然我不必在这里进行模式匹配，但我希望与数学原件保持强烈的相似性。

有什么想法可以让这个看起来更漂亮吗？

4

2 回答 2

1

以下极简主义（愚蠢）的例子可以说明一个有用的框架来适应，

def function (i:Int): Int = i+1

def iter (x0: Int): Int = {
  val x1 = function(x0)
  if (x1 - x0 == 1) x1 else iter(x1)
}
于 2014-04-09T19:21:28.897 回答
1

这是我使用牛顿法求平方根的示例的解决方案，在这种情况下简化为巴比伦法：

import math.abs                                                                                                                                                                                                    

val tol=0.00001                                                                                                                                                                                                    
val desiredSqRoot=256                                                                                                                                                                                              
val xFinal = Iterator.iterate(1.0) { x => 0.5*(x+desiredSqRoot/x) }                                                                                                                                                

def converged(l: Seq[Double]): Boolean = l match{
  case x_old :: x_new :: Nil => if( abs(x_old-x_new)/x_old < tol ) true else false                                                                                                                                 
  case _ => true                                                                                                                                                                                                  
}                                                                                                                                                                                                                  

xFinal.sliding(2).dropWhile( x=> !converged(x) ).next.last

结果为：

scala> xFinal.sliding(2).dropWhile( x=> !converged(x) ).next.last
res23: Double = 16.00000000000039

在这个例子中，我们知道它应该收敛到的值，但是我在没有这方面知识的情况下编写了收敛标准，因为通常我们不知道这一点。

于 2016-09-03T15:08:09.413 回答