Cálculo de funciones en N dimensiones

Question

Existe un concepto muy conocido de sumas parciales. Sé cómo aplicarlo a la 1D, 2D y 3D. Supongamos que tenemos una función N-dimensional $F(X_1, X_2,\; \dots \;, X_n)$ que es una suma parcial de alguna función $F'$ en este contexto. ¿Cómo podemos deducir el valor de $F'$ solicitado $A_1\leq X_1 \leq A_2$ , $B_1 \leq X_2 \leq B_2$ ... con el conocimiento de la función $F$ para cada coordenada?

por ejemplo, para el caso 2D: $F(x, y) = F'(x,y) + F(x - 1, y) + F(x, y - 1) - F(x - 1, y - 1)$ .
Necesitamos $T =$ suma de $F'$ valores para $x_1 \leq x \leq x_2$ , $y_1 \leq y \leq y_2$ . Por lo tanto, el resultado es $T = F(x_2, y_2) - F(x_2, y_1 - 1) - F(x_1 - 1, y_2) + F(x_1 - 1, y_1 - 1)$ .

Answer 1

Si te entiendo bien, tienes una cierta función $f: \mathbb Z^n \to \mathbb R$ y su suma parcial

$$F(y_1, y_2, \ldots, y_n) = \sum_{x_1=-\infty}^{y_1}\;\sum_{x_2=-\infty}^{y_2} \cdots \sum_{x_n=-\infty}^{y_n} f(x_1, x_2, \ldots, x_n).$$

Desea calcular

$$T = \sum_{x_1=a_1}^{b_1}\;\sum_{x_2=a_2}^{b_2} \cdots \sum_{x_n=a_n}^{b_n} f(x_1, x_2, \ldots, x_n)$$

para unos límites dados $a_k \le b_k$ , $1 \le k \le n$ utilizando únicamente los valores de $F$ .

Si es así, esto parece una aplicación directa de la principio de inclusión-exclusión . Específicamente,

$$\begin{aligned} T &= F(b_1, b_2, \ldots, b_n) \\ &-\ F(a_1-1, b_2, \ldots, b_n) - F(b_1, a_2-1, \ldots, b_n) - \cdots \\ &+\ F(a_1-1, a_2-1, \ldots, b_n) + \cdots \\ &\;\vdots \\ &\pm\ F(a_1-1, a_2-1, \ldots, a_n-1) \end{aligned}$$

donde los términos abarcan todas las combinaciones posibles de $a_k-1$ y $b_k$ y el signo de cada término es positivo si el número de $a_k-1$ parámetros es par y negativo si es impar.

Más formalmente, dejemos que

$$q_k(\xi) = \begin{cases} a_k-1 & \text{if the }k\text{-th lowest binary digit of }\xi\text{ is 1} \\ b_k & \text{if the }k\text{-th lowest binary digit of }\xi\text{ is 0} \end{cases}$$

y que

$$\sigma(\xi) = \begin{cases} \phantom +1 & \text{if the sum of the binary digits of }\xi\text{ is even} \\ -1 & \text{if the sum of the binary digits of }\xi\text{ is odd.} \end{cases}$$

Entonces

$$T = \sum_{\xi=0}^{2^n-1} \sigma(\xi)\ F(q_1(\xi), q_2(\xi), \ldots, q_n(\xi)).$$

Answer 2

Aquí tienes una respuesta parcial para empezar. Si lo he entendido bien, en general tiene $$F(a_1,\dots,a_n) = \sum\limits_{x_1=0}^{a_1}\sum\limits_{x_2=0}^{a_2}\dots\sum\limits_{x_n=0}^{a_n}F'(x_1,\dots,x_n).$$ Para cada $S \subseteq \{1,\dots,n\}$ deje $F^S(a_1,\dots,a_n) = F(b_1,\dots,b_n)$ donde $b_k = a_k-1$ si $k \in S$ et $b_k = a_k$ de lo contrario.

Supongamos ahora que $0 \le c_k \le a_k$ para $k=1,\dots,n$ y que $S = \left\{k \in \{1,\dots,n\}: c_k < a_k \right\}$ . El término $F'(c_1,\dots,c_n)$ se incluye en la suma $F^T(a_1,\dots,a_n)$ si $T \subseteq S$ . Sea $$G(a_1,\dots,a_n) = \sum\limits_{k=1}^n (-1)^{k+1}\sum\limits_{|T|=k}F^T(a_1,\dots,a_n),$$ donde se entiende que $T$ en la suma interna abarca subconjuntos de $\{1,\dots,n\}$ . El término $F'(c_1,\dots,c_n)$ se cuenta $\sum\limits_{k=1}^{|S|}(-1)^{k+1}\binom{|S|}{k}$ veces en esta suma. Pero $\sum\limits_{k=1}^{|S|}(-1)^{k+1}\binom{|S|}{k} = (-1)\sum\limits_{k=1}^{|S|}(-1)^k \binom{|S|}{k} = (-1)\left(\sum\limits_{k=0}^{|S|}(-1)^k \binom{|S|}{k} - 1\right) = 1$ Así que $$F(a_1,\dots,a_n) = F'(a_1,\dots,a_n)+G(a_1,\dots,a_n),$$ y $$\begin{align*} F'(a_1,\dots,a_n) &= F(a_1,\dots,a_n) - \sum\limits_{k=1}^n (-1)^{k+1}\sum\limits_{|T|=k}F^T(a_1,\dots,a_n) \\ &= F(a_1,\dots,a_n) + \sum\limits_{k=1}^n (-1)^k\sum\limits_{|T|=k}F^T(a_1,\dots,a_n). \end{align*}$$ En $n=2$ esto se reduce esencialmente a su fórmula $$F(x,y) = F'(x,y) + F(x-1,y) + F(x,y-1) - F(x-1,y-1).$$

Hay que hacer ajustes cuando uno o más de los $a_k$ son $0$ pero aparte de eso, esto recupera $F'$ de $F$ y a partir de ahí no debería ser muy difícil obtener las sumas de intervalos que quieres. Si tengo tiempo más tarde (y nadie me gana) voy a trabajar esos también.