OliForum Matematico

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...)

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 )

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

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.

afullo ha scritto: P(3)=14 (la somma dei primi tre quadrati perfetti).

capito il procedimento... 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?

mod_2 ha scritto:

afullo ha scritto: P(3)=14 (la somma dei primi tre quadrati perfetti).

capito il procedimento... 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.
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).

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.

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.

capito grazie a tutti voi!

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.

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

mod_2 ha scritto:capito grazie a tutti voi!

Di niente

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