Algoritmo di Ada Lovelace per i numeri di Bernoulli

L'algoritmo di Ada Lovelace (nata Ada Byron) permette di calcolare i numeri di Bernoulli. Questo algoritmo è noto soprattutto per essere stato il primo programma della storia dell'informatica.

Nota G, diagramma di Ada Lovelace: fu il primo algoritmo per computer pubblicato

La formula utilizzata

Come si vede dal diagramma in figura e dal testo relativo disponibile in lingua inglese, Ada Lovelace nell'implementare il suo algoritmo si servì della seguente formula:

$0=-\frac{1}{2}\frac{2n-1}{2n+1}+B_2\frac{2n}{2}+B_4\frac{2n(2n-1)(2n-2)}{4!}+B_6\frac{2n(2n-1)...(2n-4)}{6!}+...+B_{2n}$

dove abbiamo sostituito gli indici dispari usati da Ada con i pari secondo la moderna notazione dei Numeri di Bernoulli. Utilizzando il fattoriale decrescente possiamo scrivere in forma compatta:

$\frac{1}{2}\frac{2n-1}{2n+1}=\sum _{k=1}^n\frac{{(2n)}^{\underset{\_}{2k-1}}}{(2k)!}{B}_{2k}$

essendo il ${(2n)}^{\underset{\_}{2n-1}}=(2n)!$ la precedente equivale a

$B_{2n}=\frac{1}{2}\frac{2n-1}{2n+1}-\sum _{k=1}^{n-1}\frac{{(2n)}^{\underset{\_}{2k-1}}}{(2k)!}{B}_{2k}pern>1pern=1B_2=\frac{1}{2}\frac{2-1}{2+1}=\frac{1}{6}$

Le fonti concordano con Ada stessa, sul fatto che questa formula derivi dalla funzione generatrice e anche nel fornire solo un accenno di dimostrazione per giustificarlo:

$\frac{x}{e^x-1}=:\sum _{k=0}^{\mathrm{\infty }}\frac{x^k}{k!}{B}_k$

La funzione generatrice può considerarsi una uguaglianza fra serie formali di potenze o fra funzioni analitiche; in questo caso per la convergenza della serie si chiede che x abbia valore assoluto minore di 2π (il raggio di convergenza della serie stessa).

È sicuramente più semplice mostrare invece che la formula usata dalla Byron non è altro che la consueta formula di ricorrenza:

$B_m=-\frac{1}{m+1}\sum _{j=0}^{m-1}(\genfrac{}{}{0ex}{}{m+1}{j})B_{j}ossia:\sum _{j=0}^m(\genfrac{}{}{0ex}{}{m+1}{j})B_j=0(conm>0e{B}_0=1)$

resa più efficiente per il calcolo automatico. Per questo è sufficiente notare che:

$\sum _{k=1}^{n-1}\frac{{(2n)}^{\underset{\_}{2k-1}}}{(2k)!}{B}_{2k}=\frac{1}{2n+1}\sum _{k=1}^{n-1}(\genfrac{}{}{0ex}{}{2n+1}{2k})B_{2k}$

e che

$\frac{1}{2n+1}\sum _{k=0}^1(\genfrac{}{}{0ex}{}{2n+1}{k})B_k=\frac{1}{2n+1}((\genfrac{}{}{0ex}{}{2n+1}{0})(1)+(\genfrac{}{}{0ex}{}{2n+1}{1})(-\frac{1}{2}))=$

$=\frac{1}{2n+1}(1+(2n+1)(-\frac{1}{2}))=\frac{1}{2n+1}(-\frac{1}{2})(-2+2n+1)=-\frac{1}{2}\frac{2n-1}{2n+1}$

Come si può controllare nella nota G in figura questa è la funzione utilizzata da Ada dato che ai suoi tempi, come aveva indicato anche Jacob Bernoulli nel suo "Ars Conjectandi" più di un secolo prima i numeri di Bernoulli cominciavano dopo i primi due attuali che quindi vanno sostituiti con i loro valori numerici per ottenere la formula usata. Nella nota Ada scrive $B_1{B}_3{B}_5...$ che chiaramente corrispondono ai nostri $B_2{B}_4{B}_6...$ .

Bibliografia

• Template:Cita libro
• Template:Cita web

Voci correlate

• Ada Lovelace
• Numeri di Bernoulli