Corrija la implementación de Python recursiva del método de interpolación de diferencias de Newton, obteniendo algunos de los valores devueltos dentro de la recursión

Escribí una función de recursión en python para evaluar la secuencia de un método de interpolación .

Se explica gráficamente en esta imagen:

introduzca la descripción de la imagen aquí

f[x]=f(x) f[x0,x1]= f[x1]-f[x0]) / (x1 - x0) y así cuando f[x0,x1,...xn]=f[all_leastFirst,allbutLast] / xlast-xfirst .

Esto es así, recursivamente.

Yo tenía el siguiente código:

 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 ) 

Pero era necesario para obtener como salida una matriz con solo los números marcados en un círculo verde . Estaba perdido acerca de cómo obtener solo aquellos en una implementación recursiva. Un patrón común acerca de ellos será que SIEMPRE comiencen en X_0 , así que opté por etiquetarlos o usar un diccionario podría ayudar.

El resultado esperado sería:

 [1,1.71828,1.47625,.84553] 

Yo estaba obteniendo:

 [1, 2.71828, 7.3890599999999997, 20.085540000000002, 1.71828, 4.6707799999999997, 12.696480000000001, 1.4762499999999998, 4.0128500000000003, 0.84553333333333347] 

Para otra ejecución con diferentes parámetros, si es llamado por:

 a_j([1,2,3,5][4,3.5,4,5.6]) 

Debe salir:

 [4,-0.5,0.5,-0.1] 

Yo estaba obteniendo:

 [4, 3.5, 4, 5.6, -0.5, 0.5, 0.5, 0.7999999999999998, 0.09999999999999994, -0.10000000000000002] 

Otro ejemplo:

 a_j([-2,-1,0,1,2], [13,24,39,65,106]) 

Saldrá:

 [13, 24, 39, 65, 106, 11, 15, 2, 26, 5, 1, 41, 7, 0, -1] 

Pero la salida debe ser:

 [13,11,2,1.167,-0.125] 

También logré codificar esta implementación iterativa , que ya es correcta :

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

Solo me pregunto que me estaba perdiendo?

He modificado un poco el guión.

  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 

Salida: [4, -0.5, 0.5, -0.10000000000000002]

Además, el segundo ejemplo que has dado no parece correcto. a_j ([- 2, -1,0,1,2], [13,24,39,65,106]) -> [13,11,4,7, -3]

La respuesta anterior dice que el tercer elemento es 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 

Por favor, corríjame si estoy equivocado.

Obtiene valores negativos aquí porque no ha incluido la resta entre paréntesis. De lo contrario, el código se ve bien.

  r = ( a_j(xx1,yy1) - a_j(xx0,yy0) ) / (xx[len(xx)-1]-xx[0]) 

http://www.mathcs.emory.edu/~valerie/courses/fall10/155/resources/op_precedence.html

Prueba esto:

  array=[] h={} r=0 def a_j(xx,yy): global r if len(yy) == 1: h[int(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[int(''.join(str(i) for i in xx[::-1]))]=r return r a_j([0,1,2,3], [1,2.71828,7.38906,20.08554]) array=[h[key] for key in sorted(h.keys())] print array 

Salida: [1, 2.71828, 7.3890599999999997, 20.085540000000002, 1.71828, 4.6707799999999997, 12.696480000000001, 1.4762499999999998, 4.0128500000000003, 0.84553333333333337337

En este código, los valores se asignan primero a un dict con claves como los elementos de xx invertidos y se convierten en un entero.

Como está haciendo una recursión, agregará cada valor a medida que sale de la función, terminará haciendo el agregado en reversa xn, …, x3, x2, x1

Una vez que termine la recursión total y salga por última vez, simplemente invierta la lista, lo cual es relativamente simple por varios métodos y se ha preguntado anteriormente. Le dejo el método que desea usar (o recuerde que “Google es su amigo”)