修正牛顿差分插值法的递归python实现，在递归内部获取部分返回值 [英] Correct recursive python implementation of Newton 's differences interpolation method, obtaining some of the returned values inside recursion
问题描述
我在 python 中编写了一个递归函数来评估 插值方法的序列.
在这张图片中以图形方式解释了:
f[x]=f(x) 和 f[x0,x1]= f[x1]-f[x0])/(x1 - x0)所以当 f[x0,x1,...xn]=f[all_leastFirst,allbutLast]/xlast-xfirst 时.
这就是递归的.
我得到了以下代码:
xxs=[]yys=[]系数 = []h = {}r = 0.0定义 a_j(xx,yy):全局r如果 len(yy) == 1:h[xx[0]] = yy[0]返回 yy[0]别的: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系数.append(r)返回 ( 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.0999999999999994, -0.100000000000000002]另一个例子:
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 = {}系数 = []def sublists_n(l, n):子 = []对于范围内的 i(len(l)-n+1):subs.extend([l[i:i+n]])返回潜艇定义子列表(l):子 = []对于范围内的 i (len(l)-1,0,-1):subs.extend(sublists_n(l,i))subs.insert(0,l)返回子[::-1]def diferenciasDivididas(xx,yy,x):combinaciones = sublists([i for i in range(len(xx))])对于组合中的 c:如果 len(c) == 1:差异[str(c[0])]= float(yy[c[0]])如果 c[0] == 0:coeficientes.append(float(yy[c[0]]))别的: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如果 c[0] == 0:coeficientes.append(float(d))我只是想知道我错过了什么?
我稍微修改了脚本.
数组=[]r='s's=0定义 a_j(xx,yy):全局 r,s如果 r == 's':s=xx[0]r=0.0如果 len(yy) == 1:如果 xx[0]==s: array.append(yy[0])返回浮点数(yy[0])别的:r=( a_j(xx[1:],yy[1:]) - a_j(xx[:-1],yy[:-1]))/(xx[-1]-xx[0])如果 xx[0]==s: array.append(r)返回浮点数(r)a_j([1,2,3,5],[4,3.5,4,5.6])打印数组输出:[4, -0.5, 0.5, -0.10000000000000002]
此外，您给出的第二个示例看起来也不正确.a_j([-2,-1,0,1,2], [13,24,39,65,106]) --> [13,11,4,7,-3]
上面的答案说第三个元素是 4.
第三个元素表示 -->x(-2,-1,0) ->x(-1,0) - x(-2,-1)/(2)->x(0)-x(-1)/1 - x(-1)-x(-2)/(1)/(2)->(39-24) - (24-13)/(2)-> 15-11/(2)-> 4/2 =2如果我错了，请纠正我.
I wrote a recursion function in python to evaluate the sequence of an interpolation method.
It's graphically explained in this image:
f[x]=f(x) and f[x0,x1]= f[x1]-f[x0]) / (x1 - x0) and so when f[x0,x1,...xn]=f[all_leastFirst,allbutLast] / xlast-xfirst.
This is it then, recursively.
I had got the following code:
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 )
But it was needed to get as output an array with only the numbers marked in a green circle. I was lost about how to get only those in a recursive implementation.
One common pattern about them will be they ALWAYS start at X_0, so I opted about tagging them or using a dictionary might help.
Expected result would be:
[1,1.71828,1.47625,.84553]
I was obtaining:
[1, 2.71828, 7.3890599999999997, 20.085540000000002, 1.71828, 4.6707799999999997, 12.696480000000001, 1.4762499999999998, 4.0128500000000003, 0.84553333333333347]
For another run wit different parameters, if it's called by:
a_j([1,2,3,5][4,3.5,4,5.6])
Should output:
[4,-0.5,0.5,-0.1]
I was obtaining:
[4, 3.5, 4, 5.6, -0.5, 0.5, 0.5, 0.7999999999999998, 0.09999999999999994, -0.10000000000000002]
Another example:
a_j([-2,-1,0,1,2], [13,24,39,65,106])
Will output:
[13, 24, 39, 65, 106, 11, 15, 2, 26, 5, 1, 41, 7, 0, -1]
But the output should be:
[13,11,2,1.167,-0.125]
I also managed to code this iterative implementation, which is already correct:
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))
I only wonder what was I missing?
I have modified the script a bit.
array=[]
r='s'
s=0
def a_j(xx,yy):
global r,s
if r == 's':
s=xx[0]
r=0.0
if len(yy) == 1:
if xx[0]==s: array.append(yy[0])
return float(yy[0])
else:
r=( a_j(xx[1:],yy[1:]) - a_j(xx[:-1],yy[:-1])) / (xx[-1]-xx[0])
if xx[0]==s: array.append(r)
return float(r)
a_j([1,2,3,5],[4,3.5,4,5.6])
print array
Output: [4, -0.5, 0.5, -0.10000000000000002]
also, the second example that you have given doesnt look correct. a_j([-2,-1,0,1,2], [13,24,39,65,106]) --> [13,11,4,7,-3]
above answer says that the 3rd element is 4.
3rd element means --> x(-2,-1,0) -> x(-1,0) - x(-2,-1)/(2)
-> x(0)-x(-1)/1 - x(-1)-x(-2)/(1) /(2)
->(39-24) - (24-13) /(2)
->15-11/(2)
->4/2 =2
Please correct me if i am wrong.
这篇关于修正牛顿差分插值法的递归python实现，在递归内部获取部分返回值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
