Somma dei primi numeri n interi

Cosa sono il pigeonhole e l'induzione? Cosa dice il teorema di Ceva? 1 è un numero primo?
afullo
Messaggi: 927
Iscritto il: 01 gen 1970, 01:00
Località: Almese (TO)
Contatta:

Messaggio da afullo » 06 ago 2007, 16:08

Di fatto basta provare i primi $ i+2 $ valori e poi ricavare il polinomio di grado $ i+1 $ con il metodo che si preferisce (sistema di Vandermonde, polinomio di Lagrange, differenze divise, differenze finite...) :wink:

Avatar utente
mod_2
Messaggi: 726
Iscritto il: 18 ago 2007, 20:26
Località: In fondo a destra

Messaggio da mod_2 » 13 set 2007, 13:39

Jacobi ha scritto: Metodo generale per ottenere $ \sum_{k=1}^{n}{k^i} $: basta trovare un polinomio di grado i+1, privo di termine noto, tale che:

$ P(x) - P(x-1) = x^i $, e quindi calcolare $ P(n) $

in quanto $ \displaystile \sum_{k=1}^{n}{k^i} = \sum_{k=1}^{n}{[P(k) - P(k-1)]} = P(n)-P(0 $), ma per ipotesi e' P(0) = 0, quindi$ \sum_{k=1}^{n}{k^i} = P(n) $

Per alcuni questo metodo e' arcinoto, ma vale sempre la pena ricordarlo ( perche e' una figata :D :D )
beh... per me risulta nuovo, ma non ho capito bene i passaggi che fate per trovare i termini, potreste fare un esempio numerico? :?: grazie 1000
Appassionatamente BTA 197!

afullo
Messaggi: 927
Iscritto il: 01 gen 1970, 01:00
Località: Almese (TO)
Contatta:

Messaggio da afullo » 13 set 2007, 19:19

Esempio per trovare la somma dei primi n quadrati: il polinomio deve essere di grado 3, cioè a*x^3+b*x^2+c*x+d, e deve soddisfare le seguenti condizioni: P(0)=0 (poichè è privo di termine noto), P(1)=1 (la somma del primo quadrato perfetto), P(2)=5 (la somma dei primi due quadrati perfetti), P(3)=14 (la somma dei primi tre quadrati perfetti). Si ottiene un sistema di quattro equazioni in quattro incognite:

d = 0
a + b + c + d = 1
8a + 4b +2c + d = 5
27a + 9b + 3c + d = 14

la cui soluzione è: a = 1/3, b = 1/2, c = 1/6, d = 0.

Dunque il polinomio è: x^3/3+x^2/2+x/6.

Avatar utente
mod_2
Messaggi: 726
Iscritto il: 18 ago 2007, 20:26
Località: In fondo a destra

Messaggio da mod_2 » 13 set 2007, 19:53

afullo ha scritto: P(3)=14 (la somma dei primi tre quadrati perfetti).
capito il procedimento... :D ma nello stesso momento mi è venuto un altro dubbio: in questo caso abbiamo la somma dei quadrati che è facile da fare ma se avessimo avuto la somma dei cubi oppure dei $ k^{12} $, per esempio, dovrò quindi ad un certo punto del procedimento fare la somma dei primi 12 $ k^{12} $, che risulta comunque un passaggio lungo e pieni di calcoli, ci sarebbe un modo per risolvere questo problema? semplificando così la somma?
Appassionatamente BTA 197!

afullo
Messaggi: 927
Iscritto il: 01 gen 1970, 01:00
Località: Almese (TO)
Contatta:

Messaggio da afullo » 14 set 2007, 00:46

mod_2 ha scritto:
afullo ha scritto: P(3)=14 (la somma dei primi tre quadrati perfetti).
capito il procedimento... :D ma nello stesso momento mi è venuto un altro dubbio: in questo caso abbiamo la somma dei quadrati che è facile da fare ma se avessimo avuto la somma dei cubi oppure dei $ k^{12} $, per esempio, dovrò quindi ad un certo punto del procedimento fare la somma dei primi 12 $ k^{12} $, che risulta comunque un passaggio lungo e pieni di calcoli, ci sarebbe un modo per risolvere questo problema? semplificando così la somma?
Non ci ho mai pensato. :)
Quello che però ti posso dire, è che puoi utilizzare metodi differenti per trovare il polinomio. Per esempio, nel caso precedente si trattava di trovare il polinomio di grado 3 passante per i punti (0,0), (1,1), (2,5), (3,14): il sistema a quattro equazioni in quattro incognite, detto anche con matrice di Vandermonde, è il più semplice dal punto di vista concettuale, però è mal condizionato, nel senso che al crescere del grado e del numero di punti cresce il numero di incognite e la difficoltà del problema cresce rapidamente. Risolvere (perlomeno a mano) un sistema di 10 equazioni in 10 incognite richiede senza dubbio più del doppio del tempo che risolvere un sistema di 5 equazioni in 5 incognite! In genere per trovare il polinomio di grado n passante per n+1 punti assegnati si utilizzano altri metodi, come per esempio il procedimento di Lagrange o il procedimento di Newton, per i quali ti rimando alla letteratura specializzata. :arrow:
Comunque, quelle che generalmente vengono richieste sono la somma dei primi interi e la somma dei primi quadrati, raramente la somma dei primi cubi (che è il quadrato della somma dei primi interi), che io sappia non si è mai andati oltre. In ogni caso, per un calcolatore sommare le prime 13 dodicesime potenze non è poi un problema (anche se potrebbe un pochino approssimare, se le cifre tenute in memoria sono in numero minore rispetto alle cifre del risultato). :wink:

fph
Site Admin
Messaggi: 3648
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Messaggio da fph » 14 set 2007, 09:39

afullo ha scritto:
mod_2 ha scritto: il sistema a quattro equazioni in quattro incognite, detto anche con matrice di Vandermonde, è il più semplice dal punto di vista concettuale, però è mal condizionato, nel senso che al crescere del grado e del numero di punti cresce il numero di incognite e la difficoltà del problema cresce rapidamente. Risolvere (perlomeno a mano) un sistema di 10 equazioni in 10 incognite richiede senza dubbio più del doppio del tempo che risolvere un sistema di 5 equazioni in 5 incognite! In genere per trovare il polinomio di grado n passante per n+1 punti assegnati si utilizzano altri metodi, come per esempio il procedimento di Lagrange o il procedimento di Newton, per i quali ti rimando alla letteratura specializzata. :arrow:
Per risolvere i sistemi Vandermonde esistono algoritmi specializzati che impiegano O(n^2) passi e sono sorprendentemente ben condizionati, si chiamano algoritmi di Bj"orck-Pereira e di Traub. Credo che dovendo calcolare queste somme siano la scelta migliore. Ma qui entriamo nell'algebra lineare numerica spinta.
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]

Avatar utente
mod_2
Messaggi: 726
Iscritto il: 18 ago 2007, 20:26
Località: In fondo a destra

Messaggio da mod_2 » 14 set 2007, 11:46

capito grazie a tutti voi! :lol:
Appassionatamente BTA 197!

afullo
Messaggi: 927
Iscritto il: 01 gen 1970, 01:00
Località: Almese (TO)
Contatta:

Messaggio da afullo » 14 set 2007, 12:58

fph ha scritto:
afullo ha scritto:
mod_2 ha scritto: il sistema a quattro equazioni in quattro incognite, detto anche con matrice di Vandermonde, è il più semplice dal punto di vista concettuale, però è mal condizionato, nel senso che al crescere del grado e del numero di punti cresce il numero di incognite e la difficoltà del problema cresce rapidamente. Risolvere (perlomeno a mano) un sistema di 10 equazioni in 10 incognite richiede senza dubbio più del doppio del tempo che risolvere un sistema di 5 equazioni in 5 incognite! In genere per trovare il polinomio di grado n passante per n+1 punti assegnati si utilizzano altri metodi, come per esempio il procedimento di Lagrange o il procedimento di Newton, per i quali ti rimando alla letteratura specializzata. :arrow:
Per risolvere i sistemi Vandermonde esistono algoritmi specializzati che impiegano O(n^2) passi e sono sorprendentemente ben condizionati, si chiamano algoritmi di Bj"orck-Pereira e di Traub. Credo che dovendo calcolare queste somme siano la scelta migliore. Ma qui entriamo nell'algebra lineare numerica spinta.
Di questo non ero a conoscenza, nel corso di Analisi Numerica I abbiamo fatto i sistemi di Vandermonde ma non questi algoritmi. Probabilmente faremo qualcosa al corso di Algebra Lineare Numerica :wink:

afullo
Messaggi: 927
Iscritto il: 01 gen 1970, 01:00
Località: Almese (TO)
Contatta:

Messaggio da afullo » 14 set 2007, 13:00

mod_2 ha scritto:capito grazie a tutti voi! :lol:
Di niente :)

(scusate il doppio post ma non trovavo il multi-quote) :?

Rispondi