Sumatori

El sumatori és l'addició d'un conjunt de nombres; el resultat és la seva suma o total. Els "nombres" a sumar poden ser nombres naturals, nombres complexos, matrius, o objectes encara més complicats. La quantitat d'elements del conjunt pot ser infinit. Una suma infinita però numerable és un procediment conegut com a sèrie. El terme addició té un significat especial relacionat amb l'extrapolació en el context de sèries divergents.

Notació

L'addició d'1, 2, i 4 és 1 + 2 + 4 = 7. La suma és 7. Com que l'addició és associativa, no importa si s'interpreta "1 + 2 + 4" com (1 + 2) + 4 o com 1 + (2 + 4); el resultat és el mateix, així els parèntesis s'ometen normalment en una suma. L'addició finita també és commutativa, així l'ordre en el qual s'escriuen els nombres no afecta la seva suma. (Per qüestions relacionades amb l'addició infinita, vegeu convergència absoluta.)

Si una suma té massa termes per ser escrits individualment, la suma es pot escriure amb punts suspensius per indicar els termes omesos. Així, la suma de tots els nombres naturals des de l'1 fins a 100 és 1 + 2 + ... + 99 + 100 = 5050.

Notació sigma majúscula

La notació matemàtica té una representació especial per representar de forma compacta l'addició de molts termes similars: el símbol de sumatori ∑ (U+2211), una lletra Sigma majúscula. Això es defineix així:

$\sum _{i=m}^{n}x_{i}=x_{m}+x_{m+1}+x_{m+2}+\cdots +x_{n-1}+x_{n}.$

El subíndex dona el símbol per a una variable d'índex, i. Aquí, i representa l'índex del sumatori; m és la fita inferior del sumatori, i n és la fita superior del sumatori. Aquí i = m sota el símbol de sumatori vol dir que l'índex i comença sent igual a m. Els successius valors d'i s'obtenen afegint-li 1 al valor previ d'i, s'atura quan i = n. També es podria haver fet servir k en comptes d'i, com a

$\sum _{k=2}^{6}k^{2}=2^{2}+3^{2}+4^{2}+5^{2}+6^{2}=90$.

L'escriptura informal a vegades omet la definició de l'índex i les fites del sumatori quan aquests són clars pel context, com a

$\sum x_{i}^{2}$

que és informalment equivalent a

$\sum _{i=1}^{n}x_{i}^{2}$.

Un sovint es veuen generalizations d'aquesta notació en les que es dona una condició lògica arbitrària, i la suma està pensada per ser feta sobre tots els valors que satisfan la condició. Per exemple:

$\sum _{0\leq k<100}f(k)$

és la suma de f(k) sobre tot (enter) k que compleix la condició de ser més gran o igual que zero i més petit que cent,

$\sum _{x\in S}f(x)$

és la suma de f(k) sobre tots els elements x que compleixin la condició de pertànyer al conjunt S

$\sum _{d|n}\;\mu (d)$

és la suma de μ(d) sobre tots els enters d que són divisors de n.

(Comentari: Encara que el nom de la variable índex i de les variables fita no importa (per definició), normalment es fan servir lletres del mig de l'alfabet (de i fins a q) per denotar enters, si hi ha risc de confusió. Per exemple, fins i tot si no hi ha d'haver dubte sobre la interpretació, podria semblar una mica confós per a molts matemàtics veure x en comptes de k en les fórmules citades que impliquen k.

També hi ha maneres de generalitzar l'ús de molts símbols sigma encadenats. Per exemple,

$\sum _{\ell ,\ell '}$

és el mateix que

$\sum _{\ell }\sum _{\ell '}.$

Una notació similar s'aplica quan es tracta de trobar productes; es fa servir la mateixa estructura bàsica, amb ∏, la lletra pi majúscula, en comptes de la ∑.

Notació en llenguatge de programació

Els sumatoris també es poden representar en llenguatge de programació. Alguns llenguatges fan servir per al sumatori una notació similar a la matemàtica. Per exemple en Python:

sum(x[m:n+1])
# o alternativament i de forma més general
sum(f(i) for i in x[m:n+1])

i en Fortran (o Matlab):

sum(x(m:n))

en J:

+/x

en Haskell:

fold (+) 0 x

en Scheme:

(apply + x)

En altres llenguatges es fan servir bucles, com en el següent programa en Visual Basic/VBScript:

 Sum = 0
 For I = M To N
 Sum = Sum + X(I)
 Next I

o el següent codi en C/C++/C#/Java, que assumeix que les variables m i n estan definies com tipus enter no més gran que int, de forma que m ≥ n, i que la variable x està definida com un vector de valors de tipus enter no més gran que int, que contenen com a mínim m − n + 1 elements definits:

int i;
int sum = 0;
for (i = m; i <= n; i++)
 { sum += x[i]; }

En alguns casos un bucle es pot definir de forma més precisa com en codi Perl:

$sum = 0;
$sum += $x[$_] for ($m..$n);

o aquestes expressions alternatives en Ruby:

x[m..n].inject{|a,b| a+b}
x[m..n].inject(0){|a,b| a+b}

o en C++, fent servir la seva biblioteca estàndard:

std::accumulate(&x[m], &x[n + 1], 0)

quan x és un vector integrat o un std::vector.

Fixeu-vos que la majoria d'aquests exemples comencen inicialitzant amb 0 la variable sum, l'element identitat de la suma. (vegeu "casos especials" més avall).

Fixeu-vos també que la notació ∑ tradicional permet que la fita superior sigui més petita que la fita inferior. En aquest cas, la variable d'índex s'inicialitza amb la fita superior en comptes de la fita inferior, i es disminueix en comptes d'incrementar. Ja que l'addició és commutativa, això també es podria resoldre canviant la fita superior per la inferior i incrementant com és normal.

Fixeu-vos també que la notació ∑ s'avalua en un valor definit, mentre que la majoria de les estructures de bucle que s'han fet servir a dalt només són vàlides en el context d'una llenguatge de programació imperatiu, que exigeix l'ús d'una variable extra per emmagatzemar el valor final. Aquesta és la variable que s'utilitzaria llavors en una expressió més gran.

El significat exacte de ∑, i per tant la seva traducció en un llenguatge de programació, canvia depenent del tipus de dades del subíndex i de la fita superior. En altres paraules, ∑ és un símbol sobrecarregat.

En els exemples citats, el subíndex de ∑ es traduïa en una instrucció d'assignació a una variable d'índex al començament d'un bucle for. Però el subíndex no és sempre una instrucció d'assignació. A vegades el subíndex activa l'iterator per un bucle foreach, i a vegades el subíndex és ell mateix un vector, sense subministrar variable d'índex o iterador. Altres vegades, el subíndex és merament una expressió booleana que conté una variable, que implica per un humà, però no per un ordinador, que s'hauria de ver servir cada un dels valors on en avaluar l'expressió Booleana dona veritat.

En el següent exemple:

$\sum _{x\in S}f(x)$

$x$ és un iterator, que implica un bucle foreach, però S és un conjunt, que és una estructura de dades com la de tipus vector que pot emmagatzemar dades de tipus mixt. La rutina de sumatori per a un conjunt hauria de tenir en compte que en un conjunt és possible emmagatzemar-hi dades no numèriques.

El valor que retorna ∑, en tots els exemples anteriors és un Escalar

Casos especials

Es poden sumar menys de 2 nombres:

• Si se suma l'únic terme x, llavors el resultat del sumatori és x.
• Si se sumen zero termes, llavors el resultat del sumatori és zero, perquè zero és l'element identitat de la suma. Això es coneix com la suma buida.

Aquests casos degenerats normalment només es fan servir quan la notació de sumatori dona un resultat degenerat en un cas particular. Per exemple, si m = n en la definició de damunt, llavors només hi ha un terme en la suma; si m > n, llavors no n'hi ha cap.

Aproximació per integrals definides

Moltes aproximacions similars es poden obtenir amb la següent connexió entre sumes i integrals, les quals són vàlides per qualsevol:

Funció creixent f:

$\int _{s=a-1}^{b}f(s)\ ds\leq \sum _{i=a}^{b}f(i)\leq \int _{s=a}^{b+1}f(s)\ ds$

Funció decreixent f:

$\int _{s=a}^{b+1}f(s)\ ds\leq \sum _{i=a}^{b}f(i)\leq \int _{s=a-1}^{b}f(s)\ ds$

Per aproximacions més generals, vegeu la fórmula d'Euler-Maclaurin.

Per funcions que són integrables en l'interval [a, b], el sumatori de Riemann es pot fer servir com una aproximació de la integral definida. Per exemple, la següent fórmula és el sumatori de Riemann esquerre amb la mateixa partició de l'interval:

${\frac {b-a}{n}}\sum _{i=0}^{n-1}f\left(a+i{\frac {b-a}{n}}\right)\approx \int _{a}^{b}f(x)\ dx$

La precisió de tal aproximació incrementa segons el nombre n d'intervals, de tal manera que:

$\lim _{n\rightarrow \infty }{\frac {b-a}{n}}\sum _{i=0}^{n-1}f\left(a+i{\frac {b-a}{n}}\right)=\int _{a}^{b}f(x)\ dx$

Identitats

Les següents identitats són útils:

$\sum _{n=s}^{t}C\cdot f(n)=C\cdot \sum _{n=s}^{t}f(n)$, on 'C' és una constant que compleix la propietat distributiva. (vegeu Producte per un escalar)

$\sum _{i=s}^{n}f(C)=(n-s+1)f(C)$, on 'C' és una constant.

$\sum _{n=s}^{t}f(n)+\sum _{n=s}^{t}g(n)=\sum _{n=s}^{t}\left[f(n)+g(n)\right]$

$\sum _{n=s}^{t}f(n)=\sum _{n=s+p}^{t+p}f(n-p)$

$\sum _{n=s}^{j}f(n)+\sum _{n=j+1}^{t}f(n)=\sum _{n=s}^{t}f(n)$

$\sum _{i=m}^{n}x=(n-m+1)x$

$\sum _{i=1}^{n}x=nx$, definició de multiplicació on n és un enter que multiplica x

$\sum _{i=m}^{n}i={\frac {(n-m+1)(n+m)}{2}}$ (vegeu sèrie aritmètica)

$\sum _{i=0}^{n}i=\sum _{i=1}^{n}i={\frac {n(n+1)}{2}}$ (Cas especial de la sèrie aritmètica)

$\sum _{i=1}^{n}i^{2}={\frac {n(n+1)(2n+1)}{6}}={\frac {n^{3}}{3}}+{\frac {n^{2}}{2}}+{\frac {n}{6}}$

$\sum _{i=1}^{n}i^{3}=\left({\frac {n(n+1)}{2}}\right)^{2}={\frac {n^{4}}{4}}+{\frac {n^{3}}{2}}+{\frac {n^{2}}{4}}=\left[\sum _{i=1}^{n}i\right]^{2}$

$\sum _{i=1}^{n}i^{4}={\frac {n(n+1)(2n+1)(3n^{2}+3n-1)}{30}}={\frac {n^{5}}{5}}+{\frac {n^{4}}{2}}+{\frac {n^{3}}{3}}-{\frac {n}{30}}$

$\sum _{i=0}^{n}i^{p}={\frac {(n+1)^{p+1}}{p+1}}+\sum _{k=1}^{p}{\frac {B_{k}}{p-k+1}}{p \choose k}(n+1)^{p-k+1}$

on $B_{k}$ és el k-èsim nombre de Bernoulli.

$\sum _{i=m}^{n}x^{i}={\frac {x^{n+1}-x^{m}}{x-1}}$ (vegeu sèrie geomètrica)

$\sum _{i=0}^{n}x^{i}={\frac {1-x^{n+1}}{1-x}}$ (cas especial de la sèrie anterior on m = 0)

$\sum _{i=0}^{n}i2^{i}=2+2^{n+1}(n-1)$

$\sum _{i=0}^{n}{\frac {i}{2^{i}}}={\frac {2^{n+1}-n-2}{2^{n}}}$

$\sum _{i=0}^{n}ix^{i}={\frac {x}{(1-x)^{2}}}(x^{n}(n(x-1)-1)+1)$

$\sum _{i=0}^{n}i^{2}x^{i}={\frac {x}{(1-x)^{3}}}(1+x-(n+1)^{2}x^{n}+(2n^{2}+2n-1)x^{n+1}-n^{2}x^{n+2})$

$\sum _{i=0}^{n}{n \choose i}=2^{n}$ (vegeu coeficient binomial)

$\sum _{i=0}^{n-1}{i \choose k}={n \choose k+1}$

$\left(\sum _{i}a_{i}\right)\left(\sum _{j}b_{j}\right)=\sum _{i}\sum _{j}a_{i}b_{j}$

$\left(\sum _{i}a_{i}\right)^{2}=2\sum _{i}\sum _{j<i}a_{i}a_{j}+\sum _{i}a_{i}^{2}$

$\sum _{n=a}^{b}f(n)=\sum _{n=b}^{a}f(n)$

$\sum _{n=s}^{t}f(n)=\sum _{n=-t}^{-s}f(-n)$

$\sum _{n=0}^{t}f(2n)+\sum _{n=0}^{t}f(2n+1)=\sum _{n=0}^{2t+1}f(n)$

$\sum _{n=0}^{t}\sum _{i=0}^{z-1}f(z\cdot n+i)=\sum _{n=0}^{z\cdot t+z-1}f(n)$

${\widehat {b}}^{\left[\sum _{n=s}^{t}f(n)\right]}=\prod _{n=s}^{t}{\widehat {b}}^{f(n)}$

$\sum _{n=s}^{t}\ln f(n)=\ln \prod _{n=s}^{t}f(n)$

$\lim _{t\rightarrow \infty }\sum _{n=a}^{t}f(n)=\sum _{n=a}^{\infty }f(n)$ (Vegeu Límits infinits)

$(a+b)^{n}=\sum _{i=0}^{n}{n \choose i}a^{(n-i)}b^{i}$, Binomi de Newton

$\sum _{n=b+1}^{\infty }{\frac {b}{n^{2}-b^{2}}}=\sum _{n=1}^{2b}{\frac {1}{2n}}$

$\left(\sum _{i=1}^{n}f_{i}(x)\right)^{\prime }=\sum _{i=1}^{n}f_{i}^{\prime }(x)$

$\lim _{n\to \infty }\sum _{i=0}^{n}f\left(a+{\frac {b-a}{n}}i\right)\cdot {\frac {b-a}{n}}=\int _{a}^{b}f(x)dx$

$2^{x-1}+\sum _{n=0}^{x-2}2^{n}=x+\sum _{n=0}^{x-2}(2^{n}\cdot (x-1-n))$

Ritmes de creixement

Les següents aproximacions són útils (fent servir la notació theta):

$\sum _{i=1}^{n}i^{c}=\Theta (n^{c+1})$ per c real més gran que −1

$\sum _{i=1}^{n}{\frac {1}{i}}=\Theta (\log n)$

$\sum _{i=1}^{n}c^{i}=\Theta (c^{n})$ per c real més gran que 1

$\sum _{i=1}^{n}\log(i)^{c}=\Theta (n\cdot \log(n)^{c})$ per c real més gran o igual que 0

$\sum _{i=1}^{n}\log(i)^{c}\cdot i^{d}=\Theta (n^{d+1}\cdot \log(n)^{c})$ per c i d reals més grans o iguals que 0

$\sum _{i=1}^{n}\log(i)^{c}\cdot i^{d}\cdot b^{i}=\Theta (n^{d}\cdot \log(n)^{c}\cdot b^{n})$ per b > 1, c ≥ 0, i d ≥ 0, tots tres reals.

Vegeu també

• Notació d'Einstein
• Checksum

Referències

• Nicholas J. Higham, "The accuracy of floating point summation", SIAM J. Scientific Computing 14 (4), 783–799 (1993).

Enllaços externs

• Summation a PlanetMath
• Method to Derive Polynomial Representations that Sum Natural Numbers with Exponents Arxivat 2013-02-18 a Wayback Machine.