Stabilan számítástechnikai nagy mennyiségben keresztül rekurzió

Question

Stabilan számítástechnikai nagy mennyiségben keresztül rekurzió

szavazat

2

Van két mennyiség a & b által definiált rekurzió és hivatkozás révén egy másik listát értékek x = [x_1, x_2, ... x_N], amely bemenete a programot. A program végighaladni minden értéke x és frissítés a & b szerinti:

for n in range(1,N)
    a[n] = a[n-1] * exp(+x[n]) + b[n-1] * exp(-x[n])  
    b[n] = b[n-1] * exp(+x[n]) + a[n-1] * exp(-x[n])

és a kiindulási érték

a[0] = exp(+x[0])
b[0] = exp(-x[0])

Az értékek x nem nagy szám (mindig <10), de az N lesz a több száz, mert az összes exponenciálisok végső értékeit & b lesz nagyon nagy. Aggódom, hogy azért, mert a forma a rekurzió, ahol folyamatosan megszorozzuk exponenciálisan nagyszámú exponenciálisan kicsiket és hozzátéve, ez a rendszer lesz elég numerikusan instabil.

Ideális esetben azt kiszámítani log (a) és log (b) helyett, hogy állítsa le az értékeket túlságosan nagy. De mivel a rekurzió rendszer, ez nem lehetséges, kivéve, ha azt számítja valami sokkal mocskosabb, mint a

log_a[n] = x[n] + log_a[n-1] + log( 1 + exp(-2*x[n] + log_b[n-1]-log_a[n-1] ) )

Van valami a numerikus stabilitás igazam is aggasztja itt? És ha így lenne valami, mint a napló alapú rendszer stabilizálását segíti ez?

python numpy scipy numerical-stability

A kérdést 05/02/2016 17:26
felhasználó RGWinston

Más nyelveken...

2 válasz

szavazat

-1

Amennyire tisztában vagyok, minden (?) Rekurzív probléma megoldható a dinamikus programozás. Például, a Fibonacci szekvencia lehet kifejezni, mint így:

def fibo(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    return fibo(n-1) + fibo(n-2)

Vagy, iteratív:

n = 10
fibo_nums = [0, 1]
while len(fibo_nums) <= n:
    fibo_nums.append(fibo_nums[-2] + fibo_nums[-1])

Feltehetően, ha van egy rekurzív probléma tudna végrehajtani egy hasonló kicsomagolás.

Válaszolt 05/02/2016 17:41
a forrás felhasználó Wayne Werner

Eric · Accepted Answer · 2016-02-05 17:38

Mi lehet átírni, hogy az első, mint:

for n in range(1,N)
    a[n] = exp(log(a[n-1]) + x[n]) + exp(log(b[n-1]) - x[n])
    b[n] = exp(log(b[n-1]) + x[n]) + exp(log(a[n-1]) - x[n]))

Akkor változik a iterációs változók:

for n in range(1,N)
    log_a[n] = log(exp(log_a[n-1] + x[n]) + exp(log_b[n-1] - x[n]))
    log_b[n] = log(exp(log_b[n-1] + x[n]) + exp(log_a[n-1] - x[n]))

Melyik lehet számítani stabilabban segítségével np.logaddexp:

for n in range(1,N)
    log_a[n] = np.logaddexp(log_a[n-1] + x[n], log_b[n-1] - x[n])
    log_b[n] = np.logaddexp(log_b[n-1] + x[n], log_a[n-1] - x[n])

Végrehajtásának logaddexplátható itt