Somma dei primi numeri n interi
beh... per me risulta nuovo, ma non ho capito bene i passaggi che fate per trovare i termini, potreste fare un esempio numerico?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
grazie 1000Appassionatamente BTA 197!
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.
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.
capito il procedimento...afullo ha scritto: P(3)=14 (la somma dei primi tre quadrati perfetti).
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!
Non ci ho mai pensato.mod_2 ha scritto:capito il procedimento...afullo ha scritto: P(3)=14 (la somma dei primi tre quadrati perfetti).
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.
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).
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.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.
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
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 Numericafph ha scritto:afullo ha scritto: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.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.
