Algoritmul Ada Lovelace pentru numerele Bernoulli

Algoritmul Ada Lovelace (născut Ada Byron ) permite calcularea numerelor Bernoulli . Acest algoritm este cel mai bine cunoscut pentru că este primul program din istoria calculelor .

Nota G, diagramă de Ada Lovelace: a fost primul algoritm computerizat publicat

Formula folosită

După cum se poate vedea din diagrama din figură și textul aferent disponibil în limba engleză ^[1] , Ada Lovelace în implementarea algoritmului său a folosit următoarea formulă:

0=-{1 \over 2}{{2n-1} \over {2n+1}}+B_{2}{{2n} \over 2}+B_{4}{{2n(2n-1)(2n-2)} \over 4!}+B_{6}{{2n(2n-1)...(2n-4)} \over 6!}+...+B_{2n}

{\ displaystyle 0 = - {1 \ over 2} {{2n-1} \ over {2n + 1}} + B_ {2} {{2n} \ over 2} + B_ {4} {{2n (2n- 1) (2n-2)} \ peste 4!} + B_ {6} {{2n (2n-1) ... (2n-4)} \ peste 6!} + ... + B_ {2n}}

{\ displaystyle 0 = - {1 \ over 2} {{2n-1} \ over {2n + 1}} + B_ {2} {{2n} \ over 2} + B_ {4} {{2n (2n- 1) (2n-2)} \ peste 4!} + B_ {6} {{2n (2n-1) ... (2n-4)} \ peste 6!} + ... + B_ {2n}}

unde am înlocuit indicii impari folosiți de Ada cu cei pari conform notației moderne a numerelor Bernoulli . Folosind factorialul descrescător putem scrie în formă compactă:

{1 \over 2}{{2n-1} \over {2n+1}}=\sum _{k=1}^{n}{\frac {{(2n)}^{\underline {2k-1}}}{(2k)!}}B_{2k}

{\ displaystyle {1 \ over 2} {{2n-1} \ over {2n + 1}} = \ sum _ {k = 1} ^ {n} {\ frac {{(2n)} ^ {\ underline { 2k-1}}} {(2k)!}} B_ {2k}}

{\ displaystyle {1 \ over 2} {{2n-1} \ over {2n + 1}} = \ sum _ {k = 1} ^ {n} {\ frac {{(2n)} ^ {\ underline { 2k-1}}} {(2k)!}} B_ {2k}}

fiind cea ${(2n)}^{\underline {2n-1}}=(2n)!$ ${\ displaystyle {(2n)} ^ {\ underline {2n-1}} = (2n)!}$ ${\ displaystyle {(2n)} ^ {\ underline {2n-1}} = (2n)!}$ precedentul este echivalent cu

B_{2n}={1 \over 2}{{2n-1} \over {2n+1}}-\sum _{k=1}^{n-1}{\frac {{(2n)}^{\underline {2k-1}}}{(2k)!}}B_{2k}~~~per~n>1~~~~~~~per~n=1~~~B_{2}={1 \over 2}{{2-1} \over {2+1}}={1 \over 6}

{\ displaystyle B_ {2n} = {1 \ over 2} {{2n-1} \ over {2n + 1}} - \ sum _ {k = 1} ^ {n-1} {\ frac {{(2n )} ^ {\ underline {2k-1}}} {(2k)!}} B_ {2k} ~~~ for ~ n> 1 ~~~~~~~ for ~ n = 1 ~~~ B_ {2 } = {1 \ peste 2} {{2-1} \ peste {2 + 1}} = {1 \ peste 6}}

{\ displaystyle B_ {2n} = {1 \ over 2} {{2n-1} \ over {2n + 1}} - \ sum _ {k = 1} ^ {n-1} {\ frac {{(2n )} ^ {\ underline {2k-1}}} {(2k)!}} B_ {2k} ~~~ for ~ n> 1 ~~~~~~~ for ~ n = 1 ~~~ B_ {2 } = {1 \ peste 2} {{2-1} \ peste {2 + 1}} = {1 \ peste 6}}

Sursele sunt de acord ^[2] cu Ada însăși ^[1] , cu privire la faptul că această formulă derivă din funcția generatoare și, de asemenea, în furnizarea doar a unui indiciu de probă care să o justifice:

 ${\frac {x}{e^{x}-1}}=:\sum _{k=0}^{\infty }{\frac {{x}^{k}}{k!}}B_{k}$  $X$   $Și$   $X$   $-$   $1$   $=:$   $\sum$   $k$   $=$   $0$   $\infty$   $X$   $k$   $k$   $!$   $B.$   $k$   ${\ displaystyle {\ frac {x} {e ^ {x} -1}} =: \ sum _ {k = 0} ^ {\ infty} {\ frac {{x} ^ {k}} {k!} } B_ {k}}$   ${\ displaystyle {\ frac {x} {e ^ {x} -1}} =: \ sum _ {k = 0} ^ {\ infty} {\ frac {{x} ^ {k}} {k!} } B_ {k}}$

Funcția generatoare poate fi considerată o egalitate între serii formale de puteri sau între funcții analitice; în acest caz, pentru convergența seriei, x are o valoare absolută mai mică de 2π ( raza de convergență a seriei în sine).

Este cu siguranță mai ușor să arăți că formula folosită de Byron nu este altceva decât formula obișnuită de recurență:

B_{m}=-{1 \over {m+1}}\sum _{j=0}^{m-1}{m+1 \choose {j}}B_{j}~~~~ossia:~~~\sum _{j=0}^{m}{m+1 \choose {j}}B_{j}=0~~~~~~(con~m>0~e~B_{0}=1)~

{\ displaystyle B_ {m} = - {1 \ over {m + 1}} \ sum _ {j = 0} ^ {m-1} {m + 1 \ alege {j}} B_ {j} ~~~ ~ adică: ~~~ \ sum _ {j = 0} ^ {m} {m + 1 \ alege {j}} B_ {j} = 0 ~~~~~~ (cu ~ m> 0 ~ și ~ B_ {0} = 1) ~}

{\ displaystyle B_ {m} = - {1 \ over {m + 1}} \ sum _ {j = 0} ^ {m-1} {m + 1 \ alege {j}} B_ {j} ~~~ ~ adică: ~~~ \ sum _ {j = 0} ^ {m} {m + 1 \ alege {j}} B_ {j} = 0 ~~~~~~ (cu ~ m> 0 ~ și ~ B_ {0} = 1) ~}

a devenit mai eficient pentru calculul automat. Pentru aceasta este suficient să rețineți că:

\sum _{k=1}^{n-1}{\frac {{(2n)}^{\underline {2k-1}}}{(2k)!}}B_{2k}={\frac {1}{2n+1}}\sum _{k=1}^{n-1}{{2n+1} \choose {2k}}B_{2k}

{\ displaystyle \ sum _ {k = 1} ^ {n-1} {\ frac {{(2n)} ^ {\ underline {2k-1}}} {(2k)!}} B_ {2k} = { \ frac {1} {2n + 1}} \ sum _ {k = 1} ^ {n-1} {{2n + 1} \ alege {2k}} B_ {2k}}

{\ displaystyle \ sum _ {k = 1} ^ {n-1} {\ frac {{(2n)} ^ {\ underline {2k-1}}} {(2k)!}} B_ {2k} = { \ frac {1} {2n + 1}} \ sum _ {k = 1} ^ {n-1} {{2n + 1} \ alege {2k}} B_ {2k}}

este asta

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

{\ displaystyle {\ frac {1} {2n + 1}} \ sum _ {k = 0} ^ {1} {{2n + 1} \ choose {k}} B_ {k} = {\ frac {1} {2n + 1}} ({{2n + 1} \ alege {0}} (1) + {{2n + 1} \ alege {1}} (- {\ frac {1} {2}})) = }

{\ displaystyle {\ frac {1} {2n + 1}} \ sum _ {k = 0} ^ {1} {{2n + 1} \ choose {k}} B_ {k} = {\ frac {1} {2n + 1}} ({{2n + 1} \ alege {0}} (1) + {{2n + 1} \ alege {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}}

{\ displaystyle = {\ 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}}}

{\ displaystyle = {\ 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}}}

Așa cum se poate verifica în nota G din figură, aceasta este funcția utilizată de Ada întrucât pe vremea ei, așa cum Jacob Bernoulli indicase și în „Ars Conjectandi” cu mai mult de un secol mai devreme, numerele lui Bernoulli au început după primele două curente că de aceea trebuie înlocuite cu valorile lor numerice pentru a obține formula utilizată. În nota scrie Ada $B_{1}B_{3}B_{5}...$ ${\ displaystyle B_ {1} B_ {3} B_ {5} ...}$ ${\ displaystyle B_ {1} B_ {3} B_ {5} ...}$ care corespund clar cu ale noastre $B_{2}B_{4}B_{6}...$ ${\ displaystyle B_ {2} B_ {4} B_ {6} ...}$ ${\ displaystyle B_ {2} B_ {4} B_ {6} ...}$ .

Notă

^ ^a ^b Lovelace .
^ Adity Kar, Ada Lovelace , la people.maths.ox.ac.uk (arhivat din original la 3 iulie 2017) .

Bibliografie

( EN ) Luigi F. Menabrea, Nota G de Ada Lovelace , în Sketch the analytical engine invented by Charles Babbage , Bibliothèque Universelle de Genève, 1842. Accesat la 19 iunie 2017 .

Elemente conexe

Portal IT

Portalul de matematică

[Ada-1] Lovelace .

[2] Adity Kar, Ada Lovelace , la people.maths.ox.ac.uk (arhivat din original la 3 iulie 2017) .

[1]

[2]