2

我有两个量 a 和 b 由递归定义，并通过引用另一个值列表 x = [ x_1, x_2, ... x_N ]，这将是程序的输入。该程序将遍历 x 中的所有值并根据以下内容更新 a 和 b：

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

和起始值

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

x 中的值不是很大的数字（总是<10），但 N 将是数百个，并且由于所有指数，a 和 b 的最终值将非常大。我担心由于递归的形式，我们不断地将指数大的数字与指数小的数字相乘并将它们相加，这个方案将在数值上变得非常不稳定。

理想情况下，我会计算 log(a) 和 log(b) 来阻止值变得太大。但是由于递归方案是不可能的，除非我计算出更混乱的东西

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

我在这里关心的数字稳定性是正确的吗？如果是这样，基于日志的方案是否有助于稳定它？

4

2 回答 2

1

我们可以先将其重写为：

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

然后改变我们的迭代变量：

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

可以使用以下方法更稳定地计算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])

的实现logaddexp可以在这里看到

于 2016-02-05T19:38:23.467 回答
-1

据我所知，所有（？）递归问题都可以通过动态编程来解决。例如，斐波那契数列可以这样表示：

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

或者，迭代地：

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

大概如果您遇到递归问题，您可以执行类似的解包。

于 2016-02-05T19:41:30.453 回答