Due Giorni di Algebra Lineare Numerica www.dima.unige.it/∼dibenede/2gg/home.html Genova, 16–17 Febbraio 2012
Bernoulli, Ramanujan, Toeplitz e le matrici triangolari
Carmine Di Fiore, Francesco Tudisco, Paolo Zellini Speaker: Carmine Di Fiore
Usando una delle definizioni dei numeri di Bernoulli, si osserva che essi risolvono particolari sistemi even e odd triangolari inferiori di Toeplitz (l.t.T.).
In un articolo Ramanujan riporta un sistema lineare triangolare inferiore sparso risolto dai numeri di Bernoulli; si osserva che tale sistema `e equivalente a un sistema l.t.T. sparso.
Cercando di ottenere il sistema di Ramanujan l.t.T. dai sistemi l.t.T. odd e even, si `e indotti a studiare metodi efficienti per la risoluzione di sistemi l.t.T. generici.
I numeri di Bernoulli sono i numeri razionali che soddisfano la seguente identit`a t
et− 1 =
+∞
X
n=0
Bn(0)
n! tn= −1 2t +
+∞
X
k=0
B2k(0) (2k)! t2k. Ne segue che essi soddisfano le seguenti equazioni lineari
−1 2j +
[j−12 ]
X
k=0
j 2k
B2k(0) = 0, j = 2, 3, 4, . . . ,
j pari :
2 0
4 0
4 2
6 0
6 2
6 4
8 0
8 2
8 4
8 6
· · · · ·
B0(0) B2(0) B4(0) B6(0)
·
=
1 2 3 4
·
,
j dispari :
1 0
3 0
3 2
5 0
5 2
5 4
7 0
7 2
7 4
7 6
· · · · ·
B0(0) B2(0) B4(0) B6(0)
·
=
1 3/2 5/2 7/2
·
.
In altre parole, i numeri di Bernoulli possono essere ottenuti risolvendo (per sostituzione in avanti) un sistema lineare triangolare inferiore (uno dei due di cui sopra). Per esempio, risolvendo per sostituzione in avanti il primo sistema, ho ottenuto i primi numeri di Bernoulli:
B0(0) = 1, B2(0) = 1
6, B4(0) = −1
30, B6(0) = 1
42, B8(0) = −1
30, B10(0) = 5 66, B12(0) = −691
2730, B14(0) = 7
6 ≈ 1.16, B16(0) = −47021
6630 ≈ −7.09, . . .
I numeri di Bernoulli appaiono nella formula per le somme di Eulero-Maclaurin, e, in particolare, nell’espressione dell’errore della formula di quadratura trapezoidale come somma di potenze pari del passo di integrazione h (l’espressione che giustifica l’efficienza del metodo di quadratura Romberg-Trapezoidale).
I numeri di Bernoulli sono anche spesso coinvolti negli studi sulla funzione Zeta di Riemann. Per esempio, `e ben nota la seguente formula di Eulero:
ζ(s) =
+∞
X
k=1
1
ks, ζ(2n) = 4n|B2n(0)|π2n
2(2n)! , n ∈ 1, 2, 3, . . . (vedi anche [Riemann’s Zeta Function, H. M. Edwards, 1974]).
L’articolo di Ramanujan cui ci riferiremo in seguito `e intitolato “Some properties of Bernoulli’s numbers”
Le matrici dei coefficienti dei due precedenti sistemi lineari triangolari inferiori sono sottomatrici della matrice X mostrata qui sotto:
X =
0 0
1 0
1 1
2 0
2 1
2 2
3 0
3 1
3 2
3 3
4 0
4 1
4 2
4 3
4 4
5 0
5 1
5 2
5 3
5 4
5 5
6 0
6 1
6 2
6 3
6 4
6 5
6 6
· · · · · · · ·
=
1 1 1 1 2 1 1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
· · · · · · ·
.
Si pu`o facilmente osservare che X pu`o essere riscritta come una serie di potenze:
X =
+∞
X
k=0
1
k! Yk, Y =
0 1 0
2 0 3 0
4 0
· ·
Dim: [X]ij = 1
(i − j)![Yi−j]ij= 1
(i − j)!j · · · (i − 2)(i − 1) = i − 1 j − 1
, 1 ≤ j ≤ i ≤ n.
Questa osservazione `e il punto da cui partire per dimostrare che
2
12 30
56
·
+∞
X
k=0
1
(2k + 2)!φk=
2 0
4 0
4 2
6 0
6 2
6 4
8 0
8 2
8 4
8 6
· · · · ·
,
1
3 5
7
·
+∞
X
k=0
1
(2k + 1)!φk=
1 0
3 0
3 2
5 0
5 2
5 4
7 0
7 2
7 4
7 6
· · · · ·
,
doveφ =
0 2 0
12 0 30 0
56 0
,2 = 1 · 2, 12 = 3 · 4, 30 = 5 · 6, . . . .
Quindi i sistemi lineari risolti dai numeri di Bernoulli (di cui sopra) possono essere riscritti come qui di seguito, in termini di φ:
+∞
X
k=0
2 1
(2k + 2)!φk
B0(0) B2(0) B4(0) B6(0)
·
= 2
1/2 2/12 3/30 4/56 5/90
·
= 2
1/2 1/6 1/10 1/14 1/18
·
=: qe, (almosteven)
+∞
X
k=0
1 (2k + 1)!φk
B0(0) B2(0) B4(0) B6(0)
·
=
1/1 (3/2)/3 (5/2)/5 (7/2)/7 (9/2)/9
·
=
1 1/2 1/2 1/2 1/2
·
=: qo. (almostodd)
Adesso trasformiamo φ in una matrice di Toeplitz. Si osserva che
DφD−1=
d1
d2
d3
d4
·
0 2 0
12 0 30 0
56 0
· ·
d−11
d−12 d−13
d−14
·
=
0 2dd2
1 0
12dd3
2 0
30dd4
3 0
56dd5
4 0
· ·
= xZ, Z =
0 1 0
1 0 1 0
1 0
· ·
,
sse dk = xk−1d1
(2k − 2)! , k = 1, 2, 3, . . ., sse
D = d1Dx, Dx=
1
x 2!
x2 4! ·
xn−1 (2n−2)!
·
.
Siamo pronti per introdurre i due sistemi triangolari inferiori di Toeplitz (l.t.T.) even e odd risolti dai numeri di Bernoulli. Poniamo
b =
B0(0) B2(0) B4(0)
·
dove i B (0), i = 0, 1, 2, . . ., sono i numeri di Bernoulli.
Allora il sistema (almosteven) P+∞
k=02(2k+2)!1 φkb = qe `e equivalente al sistema P+∞
k=02(2k+2)!1 (DxφD−1x )k(Dxb) = Dxqe, cio`e al seguente sistema l.t.T. even:
+∞
X
k=0
2 xk
(2k + 2)!Zk(Dxb) = Dxqe. (even) Idem, il sistema (almostodd) P+∞
k=0 1
(2k+1)!φkb = qo `e equivalente al sistema P+∞
k=0 1
(2k+1)!(DxφDx−1)k(Dxb) = Dxqo, cio`e al seguente sistema l.t.T. odd:
+∞
X
k=0
xk
(2k + 1)!Zk(Dxb) = Dxqo. (odd)
Ne segue che i numeri di Bernoulli possono essere calcolati usando un solver di sistemi lineari l.t.T.. Tale solver produce il seguente vettore z:
z = Dxb =
1 · B0(0)
x 2!B2(0)
x2 4!B4(0)
·
xs
(2s)!B2s(0)
·
xn−1
(2n−2)!B2n−2(0)
·
,
dal quale si ottiene il vettore dei primi n numeri di Bernoulli:
{b}n = {Dx−1z}n. Perch´e pu`o essere utile scegliere x positivo diverso da 1 ?
Una opportuna scelta di x pu`o rendere possibile e pi`u stabile il calcolo, attraverso un l.t.T. solver, degli elementi zi di z anche per i molto grandi. Infatti, poich´e
xi
(2i)!B2i(0) ≈ (−1)i+1pi, pi= xi (2i)!4√
πi i2i
(πe)2i, pi+1
pi → x 4π2,
si ha che |(2i)!xi B2i(0)| → 0 (+∞) se x < 4π2 (x > 4π2), entrambe situazioni non ok. Invece, per x ≈ 4π2 = 39.47.. la successione |(2i)!xi B2i(0)|, i = 0, 1, 2, . . ., `e (dovrebbe essere) limitata sia inferiormente che superiormente. . . .
|(4)!x2 B4(0)| ≤ 1 sse |x| ≤ 26.84
|(8)!x4 B8(0)| ≤ 1 sse |x| ≤ 33.2
|(16)!x8 B16(0)| ≤ 1 sse |x| ≤ 36.2
|(32)!x16 B32(0)| ≤ 1 circa sse |x|16≤ 12931 (8.54)4·7.0932 sse |x| ≤ 37.82
|(2s)!xs B2s(0)| ≤ 1 circa sse |(2s)!xs 4√
πs(πe)s2s2s| ≤ 1 sse |x|s≤ (2s)!s2s
(πe)2s 4√
πs . . . Insomma, il parametro x dovrebbe essere utilizzato per rendere pi`u stabile il l.t.T. solver.
Ramanujan in un articolo osserva che i numeri di Bernoulli B2(0), B4(0), B6(0), . . ., soddisfano il seguente sistema triangolare inferiore sparso di equazioni lineari:
1
0 1
0 0 1
1
3 0 0 1
0 52 0 0 1
0 0 11 0 0 1
1
5 0 0 1434 0 0 1
0 4 0 0 2863 0 0 1
0 0 2045 0 0 221 0 0 1
1
7 0 0 19387 0 0 32307 0 0 1
0 112 0 0 71065 0 0 35534 0 0 1
· · · · · · · · · · · ·
B2(0) B4(0) B6(0) B8(0) B10(0) B12(0) B14(0) B16(0) B18(0) B20(0) B22(0)
·
=
1/6
−1/30 1/42 1/45
−1/132 4/455 1/120
−1/306 3/665 1/231
−1/552
·
(per essere esatti, poich´e i numeri di Bernoulli per Ramanujan sono i moduli dei nostri, le sue equazioni, ottenute per via analitica, sono leggermente diverse).
Per esempio, dalle equazioni di cui sopra ho facilmente calcolato i numeri di Bernoulli B18(0), B20(0), B22(0) (a partire da quelli gi`a calcolati):
B18(0) = 43867
798 ≈ 54.97, B20(0) = −174611
330 ≈ −529.12, B22(0) = 854513
138 ≈ 6192.12.
Problema.
E possibile ottenere tale sistema di Ramanujan, triangolare inferiore di equazioni sparse, dai nostri sistemi` lineari l.t.T. even e odd ? `E possibile ottenere altre equazioni sparse (possibilmente pi`u sparse di quelle di Ramanujan) che definiscono i numeri di Bernoulli ?
Si noti che la matrice di Ramanujan, chiamiamola R, ha elementi non nulli esattamente nei posti dove la matrice di Toeplitz
+∞
X
k=0
γk(Z3)k, Z =
0 1 0
1 0
· ·
ha elementi non nulli. Ma R non `e una matrice di Toeplitz !
. . . pausa per alcuni mesi . . .
Si noti che il vettore delle indeterminate nel sistema di Ramanujan `e ZT volte il nostro vettore b:
B2(0) B4(0) B6(0)
·
=
0 1
0 1 0 ·
·
B0(0) B2(0) B4(0)
·
= ZTb.
Quindi, il sistema di Ramanujan pu`o essere riscritto come segue R(ZTb) = f , f = [ f1f2f3 · ]T.
Osservazione
La matrice di Ramanujan R soddisfa la seguente identit`a, coinvolgente una matrice triangolare inferiore sparsa di Toeplitz ˜R:
R
2!
x 4!
x2 6!
x3
·
=
2!
x 4!
x2 6!
x3
·
R,˜ R =˜
+∞
X
s=0
2 x3s
(6s + 2)!(2s + 1)Z3s.
⇒
RZTb = f , f = [f1f2f3· ]T sse
R
2!
x 4!
x2 6!
x3
·
x 2!
x2 4!
x3 6!
·
ZTb = f sse
2!
x 4!
x2 6!
x3
·
R˜
x 2!
x2 4!
x3 6!
·
ZTb = f sse
R˜
x 2!
x2 4!
x3 6!
·
B2(0) B4(0) B6(0)
·
=
x 2!
x2 4!
x3 6!
·
f1 f2 f3
·
.
In altre parole, il sistema di Ramanujan `e equivalente al seguente sistema sparso l.t.T.:
R (Z˜ TDxb) =
x 2!
x2 4!
x3 6!
·
f1
f2
f3
·
, dove
R = L(a˜ R) =
1
0 1
0 0 1
2
8!3x3 0 0 1
0 8!32 x3 0 0 1
0 0 8!32 x3 0 0 1
2
14!5x6 0 0 8!32 x3 0 0 1
0 14!52 x6 0 0 8!32 x3 0 0 1 0 0 14!52 x6 0 0 8!32 x3 0 0 1
2
20!7x9 0 0 14!52 x6 0 0 8!32 x3 0 0 1
0 20!72 x9 0 0 14!52 x6 0 0 8!32 x3 0 0 1
· · · · · · · · · · · ·
, aR=
1 0 0
2 8!3x3
0 0
2 14!5x6
0 0
2 20!7x9
0
·
.
Si noti la nuova notazione : a =
a0
a1
a2
·
, ⇒ L(a) =
a0
a1 a1
a2 a1 a2
· · · ·
.
TEOREMA
Notazioni: Z `e la matrice lower shift
Z =
0 1 0
1 0
· ·
,
L(a) `e la matrice triangolare inferiore di Toeplitz con prima colonna a, i.e.
a =
a0 a1 a2
·
, L(a) =
+∞
X
i=0
aiZi=
a0 a1 a0 a2 a1 a0 a3 a2 a1 a0
· · · · ·
,
d(z) `e la matrice diagonale con zi come elementi diagonali.
Poniamo
b =
B0(0) B2(0) B4(0)
·
, Dx= diag ( xi
(2i)!, i = 0, 1, 2, . . .), x ∈ R,
dove B2i(0), i = 0, 1, 2, . . ., sono i numeri di Bernoulli.
Allora i vettori Dxb e ZTDxb risolvono i seguenti sistemi lineari l.t.T.
L(a) (Dxb) = Dxq, L(a) (ZTDxb) = d(z)ZTDxq,
dove i vettori a = (ai)+∞i=0, q = (qi)+∞i=0, e z = (zi)+∞i=1, possono assumere rispettivamente i valori:
aRi = δi=0mod3
2xi
(2i + 2)!(23i + 1), qRi = 1
(2i + 1)(i + 1)(1 − δi=2mod3
3
2), i = 0, 1, 2, 3, . . . zRi = 1 − δi=0mod3
1
2
3i + 1, i = 1, 2, 3, . . . , aei = 2xi
(2i + 2)!, qei = 1
2i + 1, i = 0, 1, 2, 3, . . . zie= i
i + 1, i = 1, 2, 3, . . . , aoi = xi
(2i + 1)!, i = 0, 1, 2, 3, . . . , qo0= 1, qoi = 1
2, i = 1, 2, 3, . . . zoi = 2i − 1
2i + 1, i = 1, 2, 3, . . . .
