Ricorrenza Il problema dei conigli

(1)

Ricorrenza Il problema dei conigli

Un allevatore compra una coppia di conigli appena nati.

Dopo due mesi i conigli sono in grado di riprodursi, dando vita ad un’altra coppia di conigli; questa pu` o riprodursi dopo altri due mesi. Supponendo che nes- sun coniglio muoia, qual ` e il numero totale delle coppie di conigli dopo N mesi?

la successione del numero di coppie ` e

1, 1, 1 + 1 = 2, 2 + 1 = 3, 3 + 2 = 5, . . . e, in generale

u _n+1 = u _n + u _n−1 con u ₀ = 1 e u ₁ = 1

(2)

Si pu` o affrontare il problema al calcolatore in due modi

• mettere tutti i numeri in un vettore (se non sono troppi)

• applicare la formula spostando n Esempio 1

u[0]=1 u[1]=1

per n che va da 2 a N u[n]=u[n-1]+u[n-2]

ripeti Esempio 2 unm2=1 unm1=1

per n che va da 2 a N un = unm1 + unm2 unm2 = unm1

unm1 = un

ripeti

(3)

formula di Binet Cerco una successione come quella di Fibonacci ma fatta a potenza

q ^N = q ^{N −1} + q ^{N −2} che implica

q ² + q = 1 e che ha due soluzioni

q ₁ = 1 + √ 5

2 e q ₂ = 1 − √ 5 2 scrivo

u _N = c ₁ · q 1 ^N + c ₂ · q 2 ^N

con

c ₁ =

√ 5 + 1 2 √

5 e c ₂ =

√ 5 − 1 2 √

5 Per N → ∞ il contributo di q ₂ ^N scompare e

u _N ≈ c ¹ · q ₁ ^N

(4)

Polinomi ortogonali

Molti polinomi sono importanti per la Fisica.

Spesso li caratterizza una relazione di ricor- renza che permette anche di calcolarli.

1. • Polinomi di Legendre

• P

⁰

(x) = 1, P

1

(x) = x

• (N + 1)P

N +1

= (2N + 1)xP

_N

(x) − NP

_{N −1}

(x) 2. • Polinomi di Hermite

• H

⁰

(x) = 1, H

1

(x) = x

• H

N +1

= 2 · xH

^N

(x) − 2 · N · H

N −1

(x) 3. • Polinomi di Laguerre

• L

^a0

(x) = 1, L

^a₁

(x) = 1 + a − x

• (N + 1)L

^a_{N +1}

= (2N + 1 + a − x) · L

^a_N

(x)

− (N + a) · L

^a_{N −1}

(x) 4. • Polinomi di Hermite

• H

⁰

(x) = 1, H

1

(x) = x

• H

^{N +1}

= 2 · xH

^N

(x) − 2 · N · H

N −1

(x) 5. • Polinomi di Chebychev

• T

⁰

(x) = 1, T

1

(x) = x

• T

^{N +1}

= 2 · x · T

^N

(x) − T

N −1

(x)

(5)

integrali dei polinomi

1.

Z ₊₁

−1 P _n (x)P _m (x)dx = δ _nm 2 2n + 1

2.

Z _+∞

−∞ e ^−x

²

H _n (x)H _m (x) = δ _nm 2 ⁿ n! √ π

3.

Z _∞

0 e ^−x L ^a _n (x)L ^a _m (x) = δ _nm Γ(n + a + 1) n!

4.

Z ₊₁

−1

T _n (x)T _m (x)

q

1 − x ²

= δ _nm π

2 o δ _nm π se n ` e 0

(6)

Funzioni associate di Legendre

Sono importanti nel calcolo delle armoniche sferiche

Y _l ^m (θ, φ) =

s (2l + 1) 4π

(l − m)!

(l + m)! P _l ^m (cos(θ))e ^imφ P _l ^m sono le funzioni associate di Legendre.Per m = 0 si trovano i polinomi di Legendre Posso calcolarle tramite una relazione di ricorrenza

1. P _m ^m (x) = (−1) ^m (2m − 1)!!(1 − x ² ) ^m/2

2. P _m+1 ^m (x) = (2m + 1)xP m ^m (x)

3. (l − m)P _l ^m (x) = (2l − 1)xP _l−1 ^m (x)

2cm − (l − m + 1)P _l−2 ^m (x)

(7)

Funzioni di Bessel e ricorsione inversa

Le funzioni di Bessel sferiche possono essere definite da

j ₀ (x) = sin(x)/x j ₁ (x) = sin(x)/x ² −cos(x)/x j _n+1 (x) = 2n + 1

x j _n (x) − j _n−1 (x)

Se x ` e piccolo, (2n + 1)/x ` e grande Cosa suc- cede in una ricorrenza in cui

u _n+1 = Ku _n − u _n−1

con K molto grande? Cerco la risposta in una ricorrenza della forma

q ⁿ⁺¹ = Kq ⁿ − q ⁿ⁻¹ q ² − Kq + 1 = 0 che ha soluzione

q _± = (K ±

q

1 + K ² )/2 che d` a circa

q ₊ = 2K q ₋ = 1

2K

(8)

e quindi

u _n = A ₊ q ₊ ⁿ + A ₋ q ₋ ⁿ

Se A ₊ = 0, basta un piccolo errore numerico perch´ e la soluzione corrispondente a q ₊ prevalga comunque Per ovviare a questo inconveniente parto da u _n e faccio la ricorsione all’indietro

Ricorrenza Il problema dei conigli

Ricorrenza Il problema dei conigli

Un allevatore compra una coppia di conigli appena nati.

Dopo due mesi i conigli sono in grado di riprodursi, dando vita ad un’altra coppia di conigli; questa pu` o riprodursi dopo altri due mesi. Supponendo che nes- sun coniglio muoia, qual ` e il numero totale delle coppie di conigli dopo N mesi?

la successione del numero di coppie ` e

1, 1, 1 + 1 = 2, 2 + 1 = 3, 3 + 2 = 5, . . . e, in generale

u n+1 = u n + u n−1 con u 0 = 1 e u 1 = 1

Si pu` o affrontare il problema al calcolatore in due modi

• mettere tutti i numeri in un vettore (se non sono troppi)

• applicare la formula spostando n Esempio 1

u[0]=1 u[1]=1

per n che va da 2 a N u[n]=u[n-1]+u[n-2]

ripeti Esempio 2 unm2=1 unm1=1

per n che va da 2 a N un = unm1 + unm2 unm2 = unm1

unm1 = un

ripeti

formula di Binet Cerco una successione come quella di Fibonacci ma fatta a potenza

q N = q N −1 + q N −2 che implica

q 2 + q = 1 e che ha due soluzioni

q 1 = 1 + √ 5

2 e q 2 = 1 − √ 5 2 scrivo

u N = c 1 · q 1 N + c 2 · q 2 N

con

c 1 =

√ 5 + 1 2 √

5 e c 2 =

√ 5 − 1 2 √

5

Per N → ∞ il contributo di q 2 N scompare e

u N ≈ c 1 · q 1 N

Polinomi ortogonali

Molti polinomi sono importanti per la Fisica.

Spesso li caratterizza una relazione di ricor- renza che permette anche di calcolarli.

1. • Polinomi di Legendre

• P

(x) = 1, P

(x) = x

• (N + 1)P

= (2N + 1)xP

(x) − NP

(x) 2. • Polinomi di Hermite

• H

(x) = 1, H

(x) = x

• H

= 2 · xH

(x) − 2 · N · H

(x) 3. • Polinomi di Laguerre

• L

(x) = 1, L

(x) = 1 + a − x

• (N + 1)L

= (2N + 1 + a − x) · L

(x)

− (N + a) · L

(x) 4. • Polinomi di Hermite

• H

(x) = 1, H

(x) = x

• H

= 2 · xH

(x) − 2 · N · H

(x) 5. • Polinomi di Chebychev

• T

(x) = 1, T

(x) = x

• T

= 2 · x · T

(x) − T

(x)

integrali dei polinomi

1.

Z +1

−1 P n (x)P m (x)dx = δ nm 2 2n + 1

2.

Z +∞

−∞ e −x

H n (x)H m (x) = δ nm 2 n n! √ π

3.

Z ∞

u _n+1 = u _n + u _n−1 con u ₀ = 1 e u ₁ = 1

q ^N = q ^{N −1} + q ^{N −2} che implica

q ² + q = 1 e che ha due soluzioni

q ₁ = 1 + √ 5

2 e q ₂ = 1 − √ 5 2 scrivo

u _N = c ₁ · q 1 ^N + c ₂ · q 2 ^N

c ₁ =

5 e c ₂ =

Per N → ∞ il contributo di q ₂ ^N scompare e

u _N ≈ c ¹ · q ₁ ^N

Z ₊₁

−1 P _n (x)P _m (x)dx = δ _nm 2 2n + 1

Z _+∞

−∞ e ^−x

H _n (x)H _m (x) = δ _nm 2 ⁿ n! √ π

Z _∞

0 e ^−x L ^a _n (x)L ^a _m (x) = δ _nm Γ(n + a + 1) n!

Z ₊₁

T _n (x)T _m (x)

1 − x ²

= δ _nm π

2 o δ _nm π se n ` e 0

Y _l ^m (θ, φ) =

(l + m)! P _l ^m (cos(θ))e ^imφ P _l ^m sono le funzioni associate di Legendre.Per m = 0 si trovano i polinomi di Legendre Posso calcolarle tramite una relazione di ricorrenza

1. P _m ^m (x) = (−1) ^m (2m − 1)!!(1 − x ² ) ^m/2

2. P _m+1 ^m (x) = (2m + 1)xP m ^m (x)

3. (l − m)P _l ^m (x) = (2l − 1)xP _l−1 ^m (x)

2cm − (l − m + 1)P _l−2 ^m (x)

j ₀ (x) = sin(x)/x j ₁ (x) = sin(x)/x ² −cos(x)/x j _n+1 (x) = 2n + 1

x j _n (x) − j _n−1 (x)

u _n+1 = Ku _n − u _n−1

q ⁿ⁺¹ = Kq ⁿ − q ⁿ⁻¹ q ² − Kq + 1 = 0 che ha soluzione

q _± = (K ±

1 + K ² )/2 che d` a circa

q ₊ = 2K q ₋ = 1

u _n = A ₊ q ₊ ⁿ + A ₋ q ₋ ⁿ

Se A ₊ = 0, basta un piccolo errore numerico perch´ e la soluzione corrispondente a q ₊ prevalga comunque Per ovviare a questo inconveniente parto da u _n e faccio la ricorsione all’indietro

u ₀ = A ₊ /q ₊ ⁿ + A ₋ /q ₋ ⁿ

che fa prevalere il termine che dipende da q ₋ In pratica considero la formula inversa

j _n−1 (x) = 2n + 1

x j _n (x) − j n+1 (x)

con valori iniziali j _N (x) e j _{N −1} (x) casuali e

ver` o anche j _n (x).