用一個變量找出大量函數的根

Question

我正在用Python/numpy/scipy寫一個小光線跟蹤器。曲面被建模爲二維函數，給出高於正常平面的高度。我減少了找到射線和曲面之間交點的問題，以找到一個變量的函數根。這些功能是連續不斷的微分。

有沒有比使用scipy root finders（也許使用多個進程）循環遍歷所有函數更有效的方法？

編輯：這些函數是表示光線的線性函數和表面函數之間的差異，限於交叉平面。

Answer 1

以下示例顯示使用平分方法並行計算函數x **（a + 1） - b（全部使用不同的a和b）的100萬份副本的根。在這裏約需要12秒。

import numpy 

def F(x, a, b): 
    return numpy.power(x, a+1.0) - b 

N = 1000000 

a = numpy.random.rand(N) 
b = numpy.random.rand(N) 

x0 = numpy.zeros(N) 
x1 = numpy.ones(N) * 1000.0 

max_step = 100 
for step in range(max_step): 
    x_mid = (x0 + x1)/2.0 
    F0 = F(x0, a, b) 
    F1 = F(x1, a, b) 
    F_mid = F(x_mid, a, b) 
    x0 = numpy.where(numpy.sign(F_mid) == numpy.sign(F0), x_mid, x0) 
    x1 = numpy.where(numpy.sign(F_mid) == numpy.sign(F1), x_mid, x1) 
    error_max = numpy.amax(numpy.abs(x1 - x0)) 
    print "step=%d error max=%f" % (step, error_max) 
    if error_max < 1e-6: break 

的基本思想是簡單地對變量的矢量運行求根的所有通常的步驟並行，使用能夠對參數的變量的矢量和等價矢量（S）進行評價的功能定義了各個組件的功能。條件被替換爲掩碼和numpy.where（）的組合。這可以繼續下去，直到找到所有的根，直到找到所需的精度，或者直到發現足夠的根，以便將它們從問題中移除並繼續處理排除這些根的較小問題。

我選擇解決的功能是任意的，但是如果功能表現良好，它會有所幫助;在這種情況下，家庭中的所有功能都是單調的，並且只有一個正根。此外，對於平分法，我​​們需要對賦予函數不同符號的變量進行猜測，而且這裏碰巧也很容易想到（x0和x1的初始值）。

上面的代碼使用的可能是最簡單的根發現者（二分法），但同樣的技術可以很容易地應用到牛頓 - 拉夫遜，Ridder等等。根發現方法中的條件越少，越適合它對此。但是，您將不得不重新實現所需的任何算法，因此無法直接使用現有的庫根查找程序功能。

上面的代碼片段的寫法是清晰的，而不是速度。避免一些計算的重複，特別是評估函數每次迭代，而不是3次只有一次，這個速度最多9秒，如下：

... 
F0 = F(x0, a, b) 
F1 = F(x1, a, b) 

max_step = 100 
for step in range(max_step): 
    x_mid = (x0 + x1)/2.0 
    F_mid = F(x_mid, a, b) 
    mask0 = numpy.sign(F_mid) == numpy.sign(F0) 
    mask1 = numpy.sign(F_mid) == numpy.sign(F1) 
    x0 = numpy.where(mask0, x_mid, x0) 
    x1 = numpy.where(mask1, x_mid, x1) 
    F0 = numpy.where(mask0, F_mid, F0) 
    F1 = numpy.where(mask1, F_mid, F1) 
... 

爲了進行比較，使用scipy.bisect（）來查找一個根在一次需要〜94秒：

for i in range(N): 
    x_root = scipy.optimize.bisect(lambda x: F(x, a[i], b[i]), x0[i], x1[i], xtol=1e-6)