Tek bir değişkenle çok sayıda fonksiyonun köklerinin bulunması

Question

Küçük bir ışın izleyicisi yazmak için Python/numpy/scipy ile çalışıyorum. Yüzeyler normal düzlemin üzerinde bir yükseklik veren iki boyutlu fonksiyonlar olarak modellenmiştir. Bir değişken ile bir fonksiyonun kökenini bulmak için ışın ile yüzey arasındaki kesişme noktasını bulma problemini azalttım. Fonksiyonlar sürekli ve sürekli olarak ayırt edilebilir.

Bunu, scipy root finders kullanarak (ve birden çok işlem kullanarak) tüm işlevler üzerinde döngü yapmaktan daha verimli bir yolu var mı?

Düzenleme: Fonksiyonlar, kesişme düzlemine sınırlanmış ışın ve yüzey fonksiyonunu temsil eden doğrusal bir fonksiyon arasındaki farktır.

Answer 1

Aşağıdaki örnek, x ** (a + 1) - b işlevinin 1 milyon kopyası için köklerin (hepsi farklı a ve b), ikiye ayırma yöntemi kullanılarak paralel olarak hesaplanmasını göstermektedir. Yaklaşık 12 saniye sürüyor.

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 

temel fikir basitçe parametrelerin değişkenlerin vektörü ve eşdeğer vektör (ler) değerlendirilebilir bir fonksiyonu kullanılarak, değişkenlerin bir vektör üzerinde paralel bir kök bulucu her zamanki adımları çalıştırmaktır bireysel bileşen fonksiyonlarını tanımlar. Koşullar, maskelerin ve numpy.where() birleşimiyle değiştirilir. Bu, tüm kökler istenen hassasiyete ulaşılana kadar ya da dönüşümlü olarak onları sorunundan çıkarmaya yetecek kadar kökler bulunana kadar ve bu kökleri dışlayan daha küçük bir sorunla devam edinceye kadar dönüşümlü olarak devam edebilir.

Çözmeyi seçtiğim işlevler rastgeledir, ancak işlevlerin iyi davranıp davranmadığını yardımcı olur; Bu durumda ailedeki tüm işlevler monotoniktir ve tam olarak bir pozitif köke sahiptir. Ek olarak, ikiye ayırma yöntemi için, işlevin farklı belirtilerini veren değişken için tahminlere ihtiyacımız var ve buradakiler de (x0 ve x1'in başlangıç ​​değerleri) ortaya çıkmaları oldukça kolay olacaktır. Yukarıdaki kod, belki de en basit kök bulucuyu (ikiye ayırma) kullanır, ancak aynı teknik Newton-Raphson, Ridder'ın vb. Için kolayca uygulanabilir. Kök bulma yönteminde daha az şartlı koşul vardır, daha uygun buna. Ancak, istediğiniz herhangi bir algoritmayı yeniden uyarlamanız gerekir, mevcut bir kütüphane kök bulucu işlevini doğrudan kullanmanın bir yolu yoktur.

Yukarıdaki kod parçacığı, akılda değil, açık bir şekilde yazılmıştır. Karşılaştırma için

... 
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) 
... 

, birini bulmak için scipy.bisect() kullanarak şu şekildedir: sadece bir kez yerine 3 kez yinelemesi başına fonksiyonunu değerlendirmek özellikle bazı hesaplamaların tekrarını önleme, 9 saniyeye bu hızlandırır Bir anda kökü ~ 94 saniye sürer:

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)