我用Python编写了一个递归函数来评估一个序列插值法 http://en.wikipedia.org/wiki/Divided_differences#Definition.
下图对此进行了图形化解释:
f[x]=f(x)
and f[x0,x1]= f[x1]-f[x0]) / (x1 - x0)
所以当f[x0,x1,...xn]=f[all_leastFirst,allbutLast] / xlast-xfirst
.
这就是递归。
我得到了以下代码:
xxs=[]
yys=[]
coeficientes = []
h = {}
r = 0.0
def a_j(xx,yy):
global r
if len(yy) == 1:
h[xx[0]] = yy[0]
return yy[0]
else:
r = (a_j(xx[1:],yy[1:]) - a_j(xx[:-1],yy[:-1])) / (xx-1]-xx[0])
h[''.join(str(i) for i in xx[::-1])]=r
coeficientes.append(r)
return ( r )
但需要获取一个数组作为输出仅限绿色圆圈中标记的数字。我不知道如何在递归实现中只获取那些。
他们的一个常见模式是他们总是从X_0
,所以我选择标记它们或使用字典可能会有所帮助。
预期结果是:
[1,1.71828,1.47625,.84553]
我正在获得:
[1, 2.71828, 7.3890599999999997, 20.085540000000002, 1.71828, 4.6707799999999997, 12.696480000000001, 1.4762499999999998, 4.0128500000000003, 0.84553333333333347]
再跑一次如果通过以下方式调用,则具有不同的参数:
a_j([1,2,3,5][4,3.5,4,5.6])
应该输出:
[4,-0.5,0.5,-0.1]
我正在获得:
[4, 3.5, 4, 5.6, -0.5, 0.5, 0.5, 0.7999999999999998, 0.09999999999999994, -0.10000000000000002]
另一个例子:
a_j([-2,-1,0,1,2], [13,24,39,65,106])
将输出:
[13, 24, 39, 65, 106, 11, 15, 2, 26, 5, 1, 41, 7, 0, -1]
但输出应该是:
[13,11,2,1.167,-0.125]
我也成功地编写了这个代码迭代实施,即已经正确了:
diferencias = {}
coeficientes = []
def sublists_n(l, n):
subs = []
for i in range(len(l)-n+1):
subs.extend([l[i:i+n]])
return subs
def sublists(l):
subs = []
for i in range(len(l)-1,0,-1):
subs.extend(sublists_n(l,i))
subs.insert(0,l)
return subs[::-1]
def diferenciasDivididas(xx,yy,x):
combinaciones = sublists([i for i in range(len(xx))])
for c in combinaciones:
if len(c) == 1:
diferencias[str(c[0])]= float(yy[c[0]])
if c[0] == 0:
coeficientes.append(float(yy[c[0]]))
else:
c1 = diferencias.get(''.join(str(i) for i in c[1:]))
c2 = diferencias.get(''.join(str(i) for i in c[:-1]))
d = float(( c1 - c2 ) / ( xx[c[len(c)-1]] - xx[c[0]] ))
diferencias[''.join(str(i) for i in c)] = d
if c[0] == 0:
coeficientes.append(float(d))
我只是想知道我错过了什么?