Per gli studenti del corso di Elementi di Analisi Numerica Questo scritto contiene:

(1)

Per gli studenti del corso di Elementi di Analisi Numerica Questo scritto contiene:

- Cose scritte e insegnate nel I semestre A.A.2013-2014 durante il corso di Elementi di Analisi Numerica (EAN), non trattate negli anni passati (per il resto del programma di Elementi di Analisi Numerica, vedi: “Analisi Numerica 3 - Di Fiore” al focal point; metodo QR; deflazione).

- I tre esoneri di EAN 2013-2014, con le rispettive correzioni.

Pi` u precisamente questo scritto contiene:

correzione I esonero EAN correzione III esonero EAN testo III esonero EAN

osservazioni su convergenza dei metodi φ e sui metodi Runge-Kutta (non presenti negli appunti al focal point)

correzione II esonero EAN

matrice di adiacenza dei ragazzi di EAN (..ha ilcellulare di..)

ci` o che ho insegnato di diverso rispetto agli anni scorsi sulla teoria di Perron-Frobenius, metodo delle potenze, pagerank e metodo di Richardson-Eulero (`e inclusa la dimostrazione del teorema di Gershgorin rafforzato)

osservazioni su problema di Cauchy e condiz. di Lip. (non presenti negli appunti al focal point) testo II esonero EAN

domanda di cultura generale

il problema di Bruno Iannazzo, risolto solo in un caso particolare (argomento non presente negli appunti al focalpoint)

testo I esonero EAN

29 Dicembre 2013, Carmine Di Fiore

(2)

Correzione I esonero Elementi di Analisi Numerica 2013-2014

1) (i) Posto I = R ^√ 3

1 1

1+x

²

dx, trovare le approssimazioni I ^√ ₃₋₁ e I

^√3−1

2

di I fornite dalla formula dei trapezi e dedurne, tramite il metodo di estrapolazione di Romberg, l’approssimazione di ordine superiore ˜ I

^√3−1

2

. (Facoltativo: notare che ˜ I

^√3−1

2

approssima I molto meglio di I

^√3−1 4

).

(ii) Si pu` o dire che la successione di approssimazioni I

^√3−1 2k

, k = 0, 1, 2, 3, . . ., `e non crescente?

Risoluzione (i) I ^√ ₃₋₁ = ( √

3 − 1) h

1 1+(1)

²

1 2 + ¹

1+( √ 3)

²

1 2

i

= ( √ 3 − 1) h

3 8

i

= 0.274519..

I

^√3−1 2

= ^√ ³⁻¹ ₂ h

3 8 + ¹

1+(

¹⁺₂^√³

)

²

i

= ^√ ³⁻¹ ₂ h

28+3 √ 3 8(4+ √

3)

i

= 0.26497..

I ˜

^√3−1 2

= ₂

2

¹ −1 (2 ² I

^√3−1

2

−I ^√ ₃₋₁ ) = ¹ ₃ h ( √

3−1)2 ₈₍₄₊ ²⁸⁺³ ^√ ^√ ₃₎ ³ − ³ ₈ ( √ 3 −1) i

= ^√ ³⁻¹ ₃ ⁴⁴⁺³ ^√ ³

8(4+ √

3) = 0.261788..

I

^√3−1 4

= ^√ ³⁻¹ ₄ h

28+3 √ 3 8(4+ √

3) + ¹

1+(1+

^√³⁻¹₄

)

²

+ ¹

1+(1+3

^√³⁻¹₄

)

²

i

= ^√ ³⁻¹ ₄ h

28+3 √ 3 8(4+ √

3) + ⁸

14+3 √

3 + ⁸

22+3 √ 3

i

= 0.26259...

I = R ^√ 3

1 1

1+x

²

dx = [arctan x] ^√ ₁ ³ = π/12 = 0.261799..

Dunque ˜ I

^√3−1

2

ha quattro cifre significative in comune con I, mentre I

^√3−1 4

, pur richiendendo due valutazioni di f (x) = 1/(1 + x ² ) in pi` u (rispetto a quelle sufficienti per ottenere ˜ I

^√3−1

2

), ha solo due cifre significative in comune con I.

(ii) La risposta `e si. Per provarlo `e sufficiente: notare che i nodi della formula dei trapezi I ₍ ^√ _3−1)/2

^k

sono nodi della formula dei trapezi I ₍ ^√ _3−1)/2

^k+1

; notare che le formule dei trapezi I ₍ ^√ _3−1)/2

^k

e I ₍ ^√ _3−1)/2

^k+1

sono relative allo stesso intervallo [1, √

3]; dimostrare che f `e convessa in [1, √

3]. In questa spiegazione `e di aiuto un disegno in [1, √

3] di f e delle funzioni “rette a tratti”

ϕ _k | _[1, ^√ _3] e ϕ _k+1 | _[1, ^√ _3] di cui I ₍ ^√ _3−1)/2

^k

e I ₍ ^√ _3−1)/2

^k+1

rappresentano gli integrali su [1, √ 3].

Segue una prova pi` u dettagliata.

Considerati i punti x _i = x ^(k) _i = 1+i ^√ ₂ ³⁻¹

k

, i = 0, 1, . . . , 2 ^k , dell’intervallo [1, √

3] e chiamata ϕ _k (x) la funzione definita in [1, √

3] dall’identit` a ϕ _k (x)| [x

i

,x

i+1

] = f (x _i ) _x ^x−x

ⁱ⁺¹

i

−x

i+1

+ f (x _i+1 ) _x ^x−x

ⁱ

i+1

−x

i

(retta per (x _i , f (x _i )) e (x _i+1 , f (x _i+1 )), i = 0, 1, . . . , 2 ^k − 1 (notare che ϕ k > 0 in [1, √

3]), il numero I ₍ ^√ _3−1)/2

^k

rappresenta l’integrale di ϕ _k in [1, √

3]. Analogamente, I ₍ ^√ _3−1)/2

^k+1

rappresenta l’integrale di ϕ _k+1 in [1, √

3].

Per i = 0, 1, . . . , 2 ^k − 1 si ha ϕ k (x _i ) = f (x _i ) = ϕ _k+1 (x _i ) e ϕ _k (x _i+1 ) = f (x _i+1 ) = ϕ _k+1 (x _i+1 ), perché x _i = x ^(k) _i = x ^(k+1) _2i e x _i+1 = x ^(k) _i+1 = x ^(k+1) _2(i+1) . Inoltre, ϕ _k è una retta in [x _i , x _i+1 ] e ϕ _k+1 è una retta in [x _i , (x _i + x _i+1 )/2] e in [(x _i + x _i+1 )/2, x _i+1 ] (notare che x ^(k+1) _2i+1 = (x _i + x _i+1 )/2). Se fosse

ϕ _k+1 (x ^(k+1) _2i+1 ) = f (x ^(k+1) _2i+1 ) ≤ ϕ k (x ^(k+1) _2i+1 ) = (f (x ^(k+1) _2i ) + f (x ^(k+1) _2i+2 ))/2, i = 0, 1, . . . , 2 ^k − 1, (∗) avremmo che ϕ _k+1 | [x

i

,x

i+1

] ≤ ϕ k | [x

i

,x

i+1

] , i = 0, 1, . . . , 2 ^k − 1, e quindi avremmo la disuguaglianza I ₍ ^√ _3−1)/2

^k+1

≤ I ₍ ^√ _3−1)/2

^k

. La disuguaglianza (*) `e ad esempio verificata se f `e convessa in [1, √

3].

Poich´e f (x) = 1/(1 + x ² ) ⇒ f ^′ (x) = −2x/(1 + x ² ) ² ⇒ f ^′′ (x) = 2(3x ² − 1)/(1 + x ² ) ³ e f ^′′ `e positiva in (1/ √

3, +∞) e quindi in [1, √

3], la nostra f `e effettivamente convessa in [1, √

3] e di

(3)

conseguenza vale (*), cio`e la successione {I ( √

3−1)/2

^k

} ^+∞ k=0 `e non crescente.

2) Sia f _t (x) = P _+∞

n=0 B _n (x)t ⁿ /n!.

(i) Dimostrare che f _t (x) soddisfa le due condizioni _dx ^d f _t (x) = tf _t (x) e R 1

0 f _t (x) dx = 1.

(ii) Dedurne una formula chiusa per f t (x).

Risoluzione (i) Poich´e R ₁

0 B _n (x) dx = 0 e B ^′ _n (x) = nB _n−1 (x), n = 1, 2, . . ., si ha

d

dx f _t (x) = _dx ^d P _+∞

n=0 B _n (x) ^t _n!

ⁿ

= _dx ^d ( 1 + P _+∞

n=1 B _n (x) ^t _n!

ⁿ

)

= P _+∞

n=1 B _n ^′ (x) ^t _n!

ⁿ

= P _+∞

n=1 nB _n−1 (x) ^t _n!

ⁿ

= P _+∞

n=1 B _n−1 (x) _(n−1)! ^t

ⁿ

= P _+∞

j=0 B _j (x) ^t

^j+1

_j! = tf _t (x), R ₁

0 f t (x) dx = R ₁

0 ( 1 + P _+∞

n=1 B n (x) ^t _n!

ⁿ

) dx

= 1 + P _+∞

n=1 t

ⁿ

n!

R ₁

0 B _n (x) dx = 1.

(ii) La condizione _dx ^d f _t (x) = tf _t (x) implica f _t (x) = c(t)e ^tx . Quindi, la condizione R 1

0 f _t (x) dx = 1 diventa 1 = R 1

0 c(t)e ^tx dx = c(t) R 1

0 e ^tx dx = c(t) ¹ _t [e ^tx ] ¹ ₀ = c(t) ¹ _t (e ^t − 1), da cui l’espressione per la funzione c(t), c(t) = t/(e ^t − 1). Dunque, f t (x) = e ^tx t/(e ^t − 1).

3) Si vuole approssimare ς(1 + ε) = P _+∞

r=1 1

r

^1+ε

uniformemente per ε ∈ (0, 2].

(i) Usando la formula di Eulero-Maclaurin, trovare una funzione ϕ(ε, m, k), ε ∈ R ⁺ , m ≥ 1, k ≥ 0 (m, k ∈ Z), per cui vale l’identit`a

X +∞

r=m

1 r ^1+ε = ϕ(ε, m, k) + u _k+1 (∞), dando una maggiorazione per |u k+1 (∞)| (in funzione di ε, m, k).

(ii) Usare la maggiorazione ottenuta nel punto precedente per trovare una costante M _m,k tale che

|u k+1 (∞)| ≤ M m,k per ogni ε ∈ [1, 2].

(iii) Porre m = 2 e, valutando la costante M _2,k del punto precedente per k = 0, 1, 2, . . ., determinare il minimo valore di k per cui

|{1 + ϕ(ε, 2, k)} − ς(1 + ε)| ≤ 1

2 ⁹ , ∀ ε ∈ [1, 2].

(Quest’ultimo risultato vale in realt` a per ogni ε ∈ (0, 2], con lo stesso k).

Risoluzione

La formula di Eulero-Maclaurin

n

X

r=m

f (r) = 1

2 (f (m) + f (n)) + Z n

m

f (x) dx +

k

X

j=1

B _2j (0)

(2j)! [f ^(2j−1) (n) − f ^(2j−1) (m)] + u _k+1 per f (x) = 1/x ^1+ε diventa

n

X

r=m

1 r ^1+ε = 1

2 ( 1

m ^1+ε + 1

n ^1+ε )− 1 εn ^ε + 1

εm ^ε +

k

X

j=1

B 2j (0)

(2j)! [(− 1

n ^2j+ε + 1

m ^2j+ε )(1+ε)(2+ε) · · · (2j−1+ε)]+u k+1

(EMform)

(4)

( R n m

1 x

^1+ε

dx = [ ^x _−ε

^−ε

] ⁿ _m ; f ^(s) (x) = (−1) ^s (1 + ε)(2 + ε) · · · (s + ε)x ^−(s+1+ε) , f ^(2j−1) (x) = −(1 + ε)(2 + ε) · · · (2j − 1 + ε)x ^−(2j+ε) ). Inoltre, poich´e f ^(2k+2) (x) > 0 in (0, +∞) e quindi non cambia segno in [m, n] se m ≥ 1, il modulo di u k+1 deve essere pi` u piccolo di due volte il modulo del termine successivo della somma,

|u k+1 | ≤ 2 |B 2k+2 (0)|

(2k + 2)! | − 1

n ^2k+2+ε + 1

m ^2k+2+ε |(1 + ε)(2 + ε) · · · (2k + 1 + ε). (EMerr) Per n → +∞, le (EMfor) e (EMerr) diventano

X +∞

r=m

1 r ^1+ε = 1

2m ^1+ε + 1 εm ^ε +

k

X

j=1

B _2j (0) (2j)!

(1 + ε)(2 + ε) · · · (2j − 1 + ε)

m ^2j+ε +u _k+1 (∞) =: ϕ(ε, m, k)+u k+1 (∞),

|u k+1 (∞)| ≤ 2 |B 2k+2 (0)|

(2k + 2)!

(1 + ε)(2 + ε) · · · (2k + 1 + ε)

m ^2k+2+ε .

(ii) In particolare, se ε ∈ [1, 2], allora

|u k+1 (∞)| ≤ 2 |B 2k+2 (0)|

(2k + 2)!

(3)(4) · · · (2k + 3)

m ^2k+3 = |B 2k+2 (0)|(2k + 3)

m ^2k+3 =: M _m,k , e se ε ∈ (0, 1], allora

|u k+1 (∞)| ≤ 2 |B 2k+2 (0)|

(2k + 2)!

(2)(3) · · · (2k + 2)

m ^2k+2 = 2|B 2k+2 (0)|

m ^2k+2 =: N _m,k . (iii) Sappiamo che

|1 + ϕ(ε, 2, k) − ζ(1 + ε)| = |ϕ(ε, 2, k) −

+∞

X

r=2

1 r ^1+ε | ≤

M _2,k ε ∈ [1, 2]

N _2,k ε ∈ (0, 1] , dove

M _2,k = |B 2k+2 (0)|(2k + 3)

2 ^2k+3 , N _2,k = |B 2k+2 (0)|

2 ^2k+1 .

Quindi, per rispondere alla domanda `e sufficiente trovare il minimo k per cui M _2,k ≤ 1/2 ⁹ . Vedremo che per lo stesso k si avr` a anche N _2,k ≤ 1/2 ⁹ . Si ha

M _2,0 = ¹ ₆ 3 ₂ ¹

₃

= ₂ ¹

₄

, N _2,0 = ¹ ₆ ¹ ₂ = ¹ ₃ ₂ ¹

₂

, M _2,1 = ₃₀ ¹ 5 ₂ ¹

5

= ¹ ₃ ₂ ¹

6

, N _2,1 = ₃₀ ¹ ₂ ¹

3

= ₁₅ ¹ ₂ ¹

4

, M _2,2 = ₄₂ ¹ 7 ₂ ¹

7

= ¹ ₃ ₂ ¹

8

< ₂ ¹

9

, N _2,2 = ₄₂ ¹ ₂ ¹

5

= ₂₁ ¹ ₂ ¹

6

< ₂ ¹

9

, dunque il valore di k richiesto `e k = 2. Ne segue che il numero

1 + ϕ(ε, 2, 2) = 1 + ¹

2·2

^1+ε

+ _ε2 ¹

ε

+ P 2 j=1

B

2j

(0)

(2j)! (1+ε)(2+ε)···(2j−1+ε) 2

^2j+ε

= 1 + ¹

2·2

^1+ε

+ _ε2 ¹

ε

+ ^B

²

_2! ⁽⁰⁾ ^(1+ε) ₂

2+ε

+ ^B

⁴

_4! ⁽⁰⁾ (1+ε)(2+ε)(3+ε) 2

^4+ε

= 1 + ¹

2·2

^1+ε

+ _ε2 ¹

ε

+ ^(1+ε)

12·2

^2+ε

− (1+ε)(2+ε)(3+ε)

30·24·2

^4+ε

(5)

`e tale che |1 + ϕ(ε, 2, 2) − ζ(1 + ε)| < 1/2 ⁹ , ∀ ε ∈ (0, 2].

4) Siano: A generica n × n (a ij ∈ C),

X n × k (k < n) con colonne linearmente indipendenti tale che AX = XJ per una matrice k × k J, Y n × (n − k) tale che la matrice n × n [X Y ] `e non singolare. Dimostrare che

(i) Esiste una matrice (n − k) × (n − k) B tale che [X Y ] ⁻¹ A[X Y ] =

J ∗ O B

.

(ii) (Facoltativo) Per ogni matrice k × n W ^H tale che det(W ^H X) 6= 0 si ha [X Y ] ⁻¹

A − XJ(W ^H X) ⁻¹ W ^H

[X Y ] =

O ∗ ^′ O B

. (iii) Per ogni matrice k × n W ^H tale che det(W ^H X) 6= 0 si ha

[X Y ] ⁻¹

A − X(W ^H X) ⁻¹ W ^H A

[X Y ] =

O ∗ ^′′

O B

.

e W ^H

A − X(W ^H X) ⁻¹ W ^H A

`e la matrice nulla k × n.

(iv) Posto

A =







0 1 0 0

a 0 1 − a 0

0 b 0 1 − b

0 0 1 0





 , X =







1 1

1 −1

1 1

1 −1





 , J =

1 0 0 −1

,

si osserva che AX = XJ; dunque lo spettro di A `e del tipo σ(A) = {1, −1, λ 3 , λ ₄ }. Osservare che si pu` o usare il risultato in (iii) per

W ^H =

1 0 0 0 0 1 0 0

e, quindi, introdurre una matrice 2 × 2 i cui autovalori sono λ 3 e λ ₄ . Risoluzione

(i)

h X

Y

i ₋₁ A h

X Y

i

= h X

Y

i ₋₁ h AX

AY

i

= h X

Y

i ₋₁ h XJ

AY

i

= hh X

Y

i ₋₁ XJ

h X

Y

i ₋₁ AY i

= h I _k O

J

h X

Y

i ₋₁ AY i

= h J O

h X Y

i ₋₁ AY i

=

J ∗ O B

,

dove si `e posto

∗ O

= h X

Y

i ₋₁

AY .

(6)

(ii) h

X Y

i ₋₁

(A − XJ(W ^H X) ⁻¹ W ^H ) h X

Y

i

=

J ∗ O B

−

I _k O

J(W ^H X) ⁻¹ h W ^H X

W

H Y i

=

J ∗ O B

−

J O

h I _k

(W

H X) ⁻¹ W ^H Y i

=

J ∗ O B

−

J J(W ^H X) ⁻¹ W ^H Y

O O

=

O ∗ ^′ O B

, ∗ ^′ = ∗ − J(W ^H X) ⁻¹ W ^H Y.

(iii) h

X Y

i ₋₁

(A − X(W ^H X) ⁻¹ W ^H A) h X

Y

i

=

J ∗ O B

−

I _k O

(W ^H X) ⁻¹ h

W ^H AX W

H AY i

=

J ∗ O B

−

I _k O

(W ^H X) ⁻¹ h

W ^H XJ W

H AY i

=

J ∗ O B

−

I _k O

h J

(W

H X) ⁻¹ W ^H AY i

=

J ∗ O B

−

J (W ^H X) ⁻¹ W ^H AY

O O

=

O ∗ ^′′

O B

, ∗ ^′′ = ∗ − (W ^H X) ⁻¹ W ^H AY.

(iv) AX e XJ sono entrambe uguali alla matrice







1 −1

1 1

1 −1

1 1







, dunque AX = XJ. Ne segue, in

particolare, che 1 e −1 sono autovalori di A, cio`e σ(A) = {1, −1, λ 3 , λ ₄ }.

Applicando il risultato (iii) per W ^H =

1 0 0 0 0 1 0 0

, si ha che M = A − X(W ^H X) ⁻¹ W ^H A

ha gli autovalori 0, 0, λ ₃ , λ ₄ e le prime due righe di M sono nulle (perch´e W ^H ( A−X(W ^H X) ⁻¹ W ^H A ) = O). Dunque una matrice 2 × 2 i cui autovalori sono λ 3 e λ ₄ `e la sottomatrice N 2 × 2 in basso a destra di M . Per trovarla basta scrivere esplicitamente M :

M = A −







1 1

1 −1

1 1

1 −1







1 1 1 −1

₋₁

1 0 0 0 0 1 0 0

A = A −





 1 0 0 1 1 0 0 1







1 0 0 0 0 1 0 0

A

= A −







1 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0





 A =







0 1 0 0

a 0 1 − a 0

0 b 0 1 − b

0 0 1 0





 −







0 1 0 0

a 0 1 − a 0

0 1 0 0

a 0 1 − a 0







=







0 0 0 0

0 b − 1 0 1 − b

−a 0 a 0







, N =

0 1 − b

a 0

.

Quindi λ ₃ e λ ₄ sono le radici del polinomio λ ² + a(b − 1).

(7)

Correzione III esonero di Elementi di Analisi Numerica (Dic. 2013)

(1) Data y funzione sufficientemente regolare in un intorno di x e preso h > 0 abbastanza piccolo, trovare una differenza finita ϕ

y(x − 2h), y(x − h), y(x), y(x + h), y(x + 2h)

tale che y ^′′ (x) = ϕ

y(x − 2h), y(x − h), y(x), y(x + h), y(x + 2h)

+ O(h ⁴ ).

Usare tale differenza finita per introdurre un sistema lineare Aη = b, A n×n, b n×1, la cui soluzione η ha come componente i-esima una approssimazione η(x i ) di y(x i ) essendo y(x) la soluzione del problema differenziale −y ^′′ (x) = q(x), x ∈ (a, b), y(a) = α, y(b) = β, e x i = a + i(b − a)/(n + 1), i = 0, 1, . . . , n, n + 1.

Risoluzione Sommando le identit` a y(x − h) = y(x) − hy ^′ (x) + h ²

2 y ^′′ (x) − h ³

6 y ^′′′ (x) + h ⁴

24 y ^′v (x) − h ⁵

120 y ^v (x) + O(h ⁶ ), y(x + h) = y(x) + hy ^′ (x) + h ²

2 y ^′′ (x) + h ³

6 y ^′′′ (x) + h ⁴

24 y ^′v (x) + h ⁵

120 y ^v (x) + O(h ⁶ ) si ottiene:

y(x − h) + y(x + h) − 2y(x) = h ² y ^′′ (x) + h ⁴

12 y ^′v (x) + O(h ⁶ ). (PrimaUguagl) Sommando le identit` a

y(x − 2h) = y(x) − 2hy ^′ (x) + (2h) ²

2 y ^′′ (x) − (2h) ³

6 y ^′′′ (x) + (2h) ⁴

24 y ^′v (x) − (2h) ⁵

120 y ^v (x) + O(h ⁶ ), y(x + 2h) = y(x) + 2hy ^′ (x) + (2h) ²

2 y ^′′ (x) + (2h) ³

6 y ^′′′ (x) + (2h) ⁴

24 y ^′v (x) + (2h) ⁵

120 y ^v (x) + O(h ⁶ ) si ottiene:

y(x − 2h) + y(x + 2h) − 2y(x) = 4h ² y ^′′ (x) + 16h ⁴

12 y ^′v (x) + O(h ⁶ ). (SecondaUguagl) Moltiplicando per 16 la (PrimaUguagl) ottenuta, si ha l’identit`a

16y(x − h) + 16y(x + h) − 32y(x) = 16h ² y ^′′ (x) + 16h ⁴

12 y ^′v (x) + O(h ⁶ ) e sottraendo a quest’ultima la (SecondaUguagl), si ricava

−y(x − 2h) + 16y(x − h) − 30y(x) + 16y(x + h) − y(x + 2h) = 12h ² y ^′′ (x) + O(h ⁶ ).

da cui la formula richiesta:

y ^′′ (x) = −y(x − 2h) + 16y(x − h) − 30y(x) + 16y(x + h) − y(x + 2h)

12h ² + O(h ⁴ ). (dII5punti)

(8)

Se y(t) `e la soluzione del problema differenziale −y ^′′ (x) = q(x), x ∈ (a, b), y(a) = α, y(b) = β, allora, considerati i punti x _i = a + ih, h = (b − a)/(n + 1), i = 0, 1, . . . , n, n + 1, dell’intervallo [a, b], devono essere verificate le seguenti uguaglianze:

−y ^′′ (x _i ) = q(x _i ), i = 1, . . . , n, y(x ₀ ) = α, y(x _n+1 ) = β.

A questo punto occorre approssimare le derivate seconde y ^′′ (x _i ), i = 1, . . . , n, con opportune differenze finite. Il testo dell’esercizio suggerisce di usare la formula (dII5punti) sopra ottenuta. Ci`o viene fatto bene in Appendice. Infatti in Appendice si mostra che tramite la (dII5punti) si pu`o ottenere un sistema lineare Ay(x) = b + ε, y(x) = [y(x ₁ ) y(x ₂ ) · · · y(x n )] ^T , tale che (ε) _i = O(h ⁶ ) per ogni i = 1, . . . , n. Qui invece, per semplicit` a, otteniamo un sistema lineare Ay(x) = b + ε, y(x) = [y(x ₁ ) y(x ₂ ) · · · y(x n )] ^T , meno preciso e precisamente tale che (ε) _i = O(h ⁶ ), i = 2, . . . , n −1, e (ε) _i = O(h ⁴ ), i = 1, n.

Usando la (dII5punti) per x = x _i , i = 2, . . . , n − 1, e la differenza finita y ^′′ (x) = y(x − h) − 2y(x) + y(x + h)

h ² + O(h ² ) (dII3punti)

(dimostrata a lezione) per x = x ₁ e x = x _n , le equazioni −y ^′′ (x _i ) = q(x _i ), i = 1, . . . , n diventano

−y(x 0 ) + 2y(x ₁ ) − y(x 2 ) = h ² q(x ₁ ) + O(h ⁴ ),

y(x _i−2 ) − 16y(x i−1 ) + 30y(x _i ) − 16y(x i+1 ) + y(x _i+2 ) = 12h ² q(x _i ) + O(h ⁶ ), i = 2, . . . , n − 1,

−y(x n−1 ) + 2y(x _n ) − y(x n+1 ) = h ² q(x _n ) + O(h ⁴ ),







2 −1 0 0 · · 0

−16 30 −16 1 · ·

1 −16 30 · ·

0 1 · · ·

· · · 1 0

· · 30 −16 1

· · 1 −16 30 −16

0 · · 0 0 −1 2













y(x ₁ ) y(x 2 ) y(x ₃ )

. . y(x _n−2 ) y(x _n−1 ) y(x n )







=





 α

−α 0

. . 0

−β β





 +12h ²







1 12 q(x ₁ )

q(x 2 ) q(x ₃ )

. . q(x _n−2 ) q(x _n−1 )

1 12 q(x n )







+O(h ^4,6 )

Si definiscono le approssimazioni η(x _i ) dei valori esatti y(x _i ), i = 1, . . . , n, sostituendo, nell’uguaglianza vettoriale ottenuta, y(x _i ), i = 1, . . . , n, con η(x _i ), i = 1, . . . , n, e togliendo gli errori “O(h ^4,6 )”.

(2) Dimostrare che se f `e tale che |f(x, y) − f(x, ˜ y)| ≤ L|y − ˜y| per ogni x ∈ [a, b], y, ˜y ∈ R (L ≥ 0), allora ogni schema di Runge-Kutta

φ(x, y; h) = a ₁ f (x, y) + a ₂ f (x + p ₁ h, y + p ₂ hf (x, y))

`e tale che |φ(x, y; h) − φ(x, ˜ y; h)| ≤ N|y − ˜y| per ogni x ∈ [a, b], y, ˜y ∈ R, |h| ≤ h 0 , dove N dipende da L, h 0 e dai parametri dello schema.

Risoluzione

(9)

|φ(x, y; h) − φ(x, ˜ y; h)| = |a

1

f (x, y) + a

2

f (x + p

1

h, y + p

2

hf (x, y)) − ( a

1

f (x, ˜ y) + a

2

f (x + p

1

h, ˜ y + p

2

hf (x, ˜ y)) )|

≤ |a

1

||f(x, y) − f(x, ˜ y)| + |a

2

||f(x + p

1

h, y + p

2

hf (x, y)) − f(x + p

1

h, ˜ y + p

2

hf (x, ˜ y))|

≤ |a

1

|L|y − ˜ y| + |a

2

|L|y + p

2

hf (x, y) − (˜ y + p

2

hf (x, ˜ y))|

≤ |a

1

|L|y − ˜ y| + |a

2

|L

|y − ˜ y| + |p

2

||h||f(x, y) − f(x, ˜ y)|

≤ |a

1

|L|y − ˜ y| + |a

2

|L

|y − ˜ y| + |p

2

||h|L|y − ˜ y|

≤ |y − ˜ y|

|a

1

|L + |a

2

|L

1 + |p

2

|h

0

L

= |y − ˜ y|N.

Nota (Martina): In uno dei passaggi si usa il fatto che x + p ₁ h ∈ [a, b]. Ci`o pu`o essere vero (per ogni h, |h| ≤ h 0 ) solo se x ∈ [c, d] ⊂ (a, b). Dunque la tesi dell’esercizio andrebbe perfezionata.

(3) Dimostrare che lo schema di Runge-Kutta η(x + h) − y

h = 1

4 f (x, y) + 3

4 f (x + 2

3 h, y + 2

3 hf (x, y))

`e di ordine due ma non di ordine tre. Calcolare con tale schema, ponendo h = 1, una approssimazione η(0) di y(0) essendo y(t) la soluzione del problema di Cauchy y ^′ (t) = −ty(t) ² , y(−1) = 2/3.

Facoltativo: confrontare il risultato con l’approssimazione ottenuta con lo schema di Eulero.

Risoluzione

A lezione si `e visto che uno schema di tipo Runge-Kutta

φ(x, y; h) = a ₁ f (x, y) + a ₂ f (x + p ₁ h, y + p ₂ hf (x, y))

`e di ordine due se i parametri a ₁ , a ₂ , p ₁ , p ₂ verificano le seguenti condizioni a ₁ + a ₂ = 1, a ₂ p ₁ = ¹ ₂ , a 2 p 2 = ¹ ₂ . ` E evidente che le scelte a 1 = 1/4, a 2 = 3/4, p 1 = p 2 = 2/3, che corrispondono allo schema dato, verificano tali condizioni. Quindi lo schema dato ha ordine almeno due. Vedremo che dello sviluppo in potenze di h dello schema dato, anche il coefficiente di h ² assomiglia, per quanto possibile, al coefficiente di h ² dello sviluppo del rapporto incrementale esatto (y(x + h) − y)/h.

Sia y(t), la soluzione del problema y ^′ (t) = f (t, y(t)), y(x) = y, sufficientemente regolare nell’intorno di t = x. Allora

y(x + h) − y

h = y ^′ (x) + h

2 y ^′′ (x) + h ²

6 y ^′′′ (x) + O(h ³ ).

Poich´e

y ^′′ (t) = d

dt y ^′ (t) = d

dt f (t, y(t)) = f _x (t, y(t)) + f _y (t, y(t))f (t, y(t)), y ^′′′ (t) = _dt ^d y ^′′ (t) = _dt ^d (f _x (t, y(t)) + f _y (t, y(t))f (t, y(t)))

=

f _xx + 2f _xy f + f _yy f ² + f _y f _x + f _y ² f (t,y(t)) , si ha

y(x + h) − y

h = f (x, y) + h

2 [f _x (x, y) + f _y (x, y)f (x, y)] + h ² 6

h

f _xx (x, y) + 2f _xy (x, y)f (x, y) +f _yy (x, y)f (x, y) ² + f _y (x, y)f _x (x, y) + f _y (x, y) ² f (x, y) i

+ O(h ³ ).

(10)

Inoltre,

f (x + p ₁ h, y + p ₂ hf (x, y)) = f (x, y) + p ₁ hf _x (x, y) + p ₂ hf (x, y)f _y (x, y) + 1

2 h p ² ₁ h ² f _xx (x, y) + 2p ₁ p ₂ h ² f (x, y)f _xy (x, y) + p ² ₂ h ² f (x, y) ² f _yy (x, y) i

+ O(h ³ )

= f (x, y) + h[p ₁ f _x (x, y) + p ₂ f (x, y)f _y (x, y)]

+h ² 1 2 h

p ² ₁ f xx (x, y) + 2p 1 p 2 f (x, y)f xy (x, y) + p ² ₂ f (x, y) ² f yy (x, y) i

+ O(h ³ ),

f (x + 2

3 h, y + 2

3 hf (x, y)) = f (x, y) + 2

3 hf x (x, y) + 2

3 hf (x, y)f y (x, y) + 1

2 h 4

9 h ² f _xx (x, y) + 2 4

9 h ² f (x, y)f _xy (x, y) + 4

9 h ² f (x, y) ² f _yy (x, y) i

+ O(h ³ )

= f (x, y) + h h 2

3 f _x (x, y) + 2

3 f (x, y)f _y (x, y) i +h ² h 2

9 f _xx (x, y) + 4

9 f (x, y)f _xy (x, y) + 2

9 f (x, y) ² f _yy (x, y) i

+ O(h ³ ).

Quindi

φ(x, y; h) := ¹ ₄ f (x, y) + ³ ₄ f (x + ² ₃ h, y + ² ₃ hf (x, y))

= ¹ ₄ f (x, y) + ³ ₄ n

f (x, y) + h h

2 3 f x (x, y) + ² ₃ f (x, y)f y (x, y) i +h ² h

2 9 f _xx (x, y) + ⁴ ₉ f (x, y)f _xy (x, y) + ² ₉ f (x, y) ² f _yy (x, y) i

+ O(h ³ ) o

= f (x, y) + ¹ ₂ h[f _x (x, y) + f (x, y)f _y (x, y)] + ^h ₆

²

h

f _xx (x, y) + 2f (x, y)f _xy (x, y) + f (x, y) ² f _yy (x, y) i

+ O(h ³ ).

Raccogliendo i risultati ottenuti, si ha y(x + h) − y

h − φ(x, y; h) = h ²

6 [f _y (x, y)f _x (x, y) + f _y (x, y) ² f (x, y)] + O(h ³ )

cio`e lo schema di Runge-Kutta φ(x, y; h) `e di ordine due, ma non di ordine tre, essendo in generale f _y (x, y)f _x (x, y) + f _y (x, y) ² f (x, y) 6= 0.

Scriviamo ora il metodo corrispondente: η(x ₀ ) = y(x ₀ ) = y ₀ , per i = 0, 1, 2, . . . η(x _i + h) = η(x _i ) + h h 1

4 f (x _i , η(x _i )) + 3 4 f

x _i + 2

3 h, η(x _i ) + 2

3 hf (x _i , η(x _i )) i

, x _i+1 = x _i + h.

Tale metodo, applicato al particolare problema di Cauchy y ^′ (t) = −ty(t) ² , y(−1) = 2/3, diventa:

η(−1) = y(−1) = 2/3, per i = 0, 1, 2, . . . η(x i + h) = η(x i ) + h h 1

4 (−x ⁱ )η(x i ) ² + 3

4 (−(x ⁱ + 2

3 h))(η(x i ) + 2

3 h(−x ⁱ )η(x i ) ² ) ² i

, x i+1 = x i + h.

Per h = 1, facendo un solo passo (i = 0) si ottiene la seguente approssimazione di y(0):

η(0; 1) = η(−1) + ¹ 4 (−(−1))η(−1) ² + ³ ₄ (−(−1 + ² 3 ))(η(−1) + ² 3 (−(−1))η(−1) ² ) ²

= ² ₃ + ¹ ₄ ⁴ ₉ + ³ ₄ ¹ ₃ ( ² ₃ + ² ₃ ⁴ ₉ ) ²

= ² ₃ + ¹ ₉ + ¹ ₄ ⁴ ₉ (1 + ⁴ ₉ ) ²

= ² ₃ + ¹ ₉ + ¹ ₉ ¹⁶⁹ ₈₁

= ² ₃ + ¹ ₉ ⁸¹⁺¹⁶⁹ ₈₁ = ⁷³⁶ ₇₂₉ = 1.0096.. .

(11)

L’approssimazione ottenuta di y(0) = 1 `e molto migliore di quella fornita dal metodo di Eulero (usando sempre un passo h = 1), che era 10/9 (vedi Lezione).

(4) Dimostrare che il metodo: η(x ₀ ) = y ₀ , per i = 0, 1, . . . K ₁ = f (x _i , η(x _i ; h)), K ₂ = f (x _i + h, η(x _i ; h) + 1

2 hK ₁ + 1 2 hK ₂ ), η(x _i + h; h) = η(x _i ; h) + 1

2 h(K ₁ + K ₂ ), x _i+1 = x _i + h,

`e convergente quando applicato al problema di Cauchy y ^′ (t) = µy(t), t ∈ R, y(0) = 1. Dimostrare inoltre che se µ < 0 allora, per h fissato maggiore di zero e opportunamente piccolo, la successione di approssimazioni η(x _i ) ha lo stesso andamento della successione di valori esatti y(x _i ) = e ^µx

ⁱ

, i = 0, 1, . . ..

Nota: il metodo considerato in questo esercizio funziona bene anche se applicato al problema (B) introdotto a lezione (il problema sul quale Eulero per funzionare richiedeva un passo troppo piccolo, considerato l’andamento regolare della soluzione). Verificare questa affermazione (vedi Appendice 2).

Risoluzione

Applichiamo il metodo al problema. Si ha K ₁ = µη(x _i ), K ₂ = µ(η(x _i ) + ¹ ₂ hµη(x _i ) + ¹ ₂ hK ₂ ), ovvero K ₂ = µη(x _i )(1 + ¹ ₂ hµ)/(1 − ¹ ₂ hµ), quindi

η(x _i + h) = η(x _i ) h 1 + 1

2 hµ + 1

2 hµ(1 + 1

2 hµ)/(1 − 1 2 hµ) i

, η(x _i+1 ) = η(x _i ) h

(1 + 1

2 hµ)/(1 − 1 2 hµ) i

.

Quest’ultima identit` a e la condizione iniziale η(x ₀ ) = η(0) = y(0) = 1 forniscono una formula esplicita per la successione η(x _i ) = η(x _i ; h), x _i = ih, generata dal metodo:

η(x i ; h) = 1 + ¹ ₂ hµ 1 − ¹ ₂ hµ

i

. (∗)

Convergenza: siano x 6= x 0 = 0 e h _n = (x−x 0 )/n = x/n; posto h = h _n nel metodo e fatti n passi con tale scelta di h, per la (*) si ottiene la seguente approssimazione in x = x ^(h n

ⁿ

⁾ di y(x) = e ^µx :

η(x; x/n) = 1 + ¹ ₂ xµ/n 1 − ¹ ₂ xµ/n

n

che, per n → +∞, tende a e

¹²

^xµ /e ⁻

¹²

^xµ = e ^xµ = y(x).

Sia µ < 0. Sia h > 0. La successione dei valori esatti y(x _i ) = y(ih) = e ^ihµ , i = 0, 1, 2, . . ., `e

composta da numeri reali positivi convergenti a zero in modo monotono decrescente. Usando la (*)

si pu` o dire che anche la successione η(x i ) = η(ih), i = 0, 1, 2, . . ., `e composta da numeri reali positivi

convergenti a zero in modo monotono decrescente a patto che il passo di integrazione h soddisfi la

condizione 1 + ¹ ₂ hµ > 0, ovvero se h < −2/µ.

(12)

(Nota: si richiede un passo molto piccolo solo quando µ è molto negativo; ma questa è una richiesta ammissibile perché quando µ è molto negativo, per accorgersi della forte decrescita iniziale di y(t), è ovviamente necessario scegliere un passo molto piccolo).

(5) La matrice

B =





2 1/3 1

3 −5/3 1 0 11/9 5/3





ha gli autovalori −2, 1 e 3. Dimostrare che esiste ed `e unico un vettore z tale che Bz = 3z, z > 0, kzk ¹ = 1 (senza scrivere esplicitamente z!) e che si pu` o utilizzare il metodo delle potenze per il calcolo di z, generando una successione di vettori z _k ben definiti per ogni k e convergenti a z. (Nota:

la coppia di Perron pu` o quindi esistere anche per matrici non non negative).

Risoluzione

La matrice A = B + ⁵ ₃ I ha gli autovalori −2 + ⁵ ₃ , 1 + ⁵ ₃ , 3 + ⁵ ₃ , ed `e non negativa irriducibile, quindi esiste un unico vettore positivo z tale che Az = ρ(A)z = (3 + ⁵ ₃ )z e kzk 1 = 1. Dunque esiste un unico vettore positivo z tale che Bz = 3z e kzk 1 = 1. Per calcolare z si pu`o applicare il metodo delle potenze alla matrice A: sia z ₀ > 0 tale che kz 0 k 1 = 1 e, per k = 1, 2, . . .,

a _k = Az _k−1 , ϕ _k = ka k k 1 , z _k = 1 ka k k 1

a _k

(Nota: a _k > 0, z _k > 0, kz k k 1 = 1, ∀ k). Poiché r = ρ(A) = 3 + ⁵ ₃ domina gli altri due autovalori di A (r > max{| − 2 + ⁵ ₃ |, |1 + ⁵ ₃ |}), si ha che ϕ k → ρ(A) = 3 + ⁵ ₃ e z _k → z. La velocità di convergenza è O((max{| − 2 + ⁵ ₃ |/r, |1 + ⁵ ₃ |/r}) ^k ) = O(( ⁴ ₇ ) ^k ), essendo la matrice A diagonalizzabile. Questi risultati di convergenza sono veri per il teorema enunciato a lezione sul metodo delle potenze per A non negativa irriducibile, che non richiede alcuna ipotesi tranne la dominanza dell’autovalore semplice ρ(A) di A sugli altri autovalori di A.

Nota. Perch´e non applicare il metodo delle potenze direttamente a B?

Sappiamo che Bz = 3z. Siano x, y non nulli tali che Bx = x, By = −2y. Sia v un qualsiasi vettore tale che nella espressione v = αz+ βx+ γy il coefficiente α `e diverso da zero. Il metodo delle potenze applicato a B pone v ₀ = v, e per k = 1, 2, . . . pone a _k = Bv _k−1 , ϕ _k = u ^H a _k /u ^H v _k−1 , v _k = a _k /ka k k. Tesi: per k → +∞ si ha ϕ k = u ^H B ^k v/u ^H B ^k−1 v → 3, v k = B ^k v /kB ^k v k → αz/kαzk.

Tuttavia la tesi appena enunciata `e vera solo se sono verificate le seguenti ipotesi non facilmente controllabili α 6= 0, u ^H (αz) 6= 0, u ^H B ^k−1 v 6= 0 (u ^H v _k−1 6= 0). Vedi il teorema enunciato a lezione sul metodo delle potenze per matrici generiche.

Dim. ₃ ¹

_k

B ^k v = αz + β( ¹ ₃ ) ^k x + γ(− ² ₃ ) ^k y → αz, σ k = ₃ ¹

_k

u ^H B ^k v = αu ^H z + β( ¹ ₃ ) ^k u ^H x + γ(− ² ₃ ) ^k u ^H y, σ _k+1 /σ _k → 1, u ^H B ^k+1 v/u ^H B ^k v → 3. . . . .

Nota. z = z ₂ [5/4 1 11/12] ^T con z ₂ tale che kzk 1 = 1.

Appendice

Si usa la differenza finita (dII5punti), per x = x _i , per ogni i = 1, . . . , n. In questo caso le

equazioni −y ^′′ (x _i ) = q(x _i ), i = 1, . . . , n, ovvero le equazioni −12h ² y ^′′ (x _i ) = 12h ² q(x _i ), i = 1, . . . , n,

(13)

diventano

y(x _i−2 ) − 16y(x i−1 ) + 30y(x _i ) − 16y(x i+1 ) + y(x _i+2 ) = 12h ² q(x _i ) + O(h ⁶ ), i = 1, . . . , n.







30 −16 1 0 0

−16 30 −16 1

1 −16 30

0 1

0 −16 1

1 −16 30 −16

0 0 1 −16 30













y(x ₁ ) y(x ₂ ) y(x ₃ )

. . y(x _n−2 ) y(x _n−1 ) y(x _n )







=







16α − y(x −1 )

−α 0 . . 0

−β 16β − y(x n+2 )





 +12h ²







q(x ₁ ) q(x ₂ )

. . . . q(x _n−1 )

q(x _n )







+O(h ⁶ ).

(∗) Se si suppone y (prolungabile in modo) sufficientemente regolare anche in un intorno sinistro di a e in un intorno destro di b, si pu` o pensare di sostituire, nella prima e nell’ultima equazione, y(x ₋₁ ) e y(x _x

_n+2

) rispettivamente con il valore in x ₋₁ del polinomio interpolante y in x ₀ , x ₁ , . . . e con il valore in x _n+2 del polinomio interpolante y in x _n+1 , x _n , . . . . (Per richiami sull’interpolazione polinomiale vedi la fine di questa Appendice).

Sia p ^(s) r il polinomio interpolante y in x ₀ , x ₁ , . . . , x _r . ` E semplice verificare che esiste ξ _s ∈ (x −1 , x _r ) tale che y(x ₋₁ ) − p ^(s) ^r (x ₋₁ ) = (−1) ^r+1 h ^r+1 y ^(r+1) (ξ _s ). Usando la formula di Lagrange per p ^(s) r (x) si ottengono facilmente le seguenti identit` a:

y(x ₋₁ ) = p ^(s) r (x ₋₁ ) + O(h ^r+1 ) : r = 0; y(x ₋₁ ) = y(x ₀ ) + O(h),

r = 1; y(x ₋₁ ) = 2y(x ₀ ) − y(x 1 ) + O(h ² ),

r = 2; y(x ₋₁ ) = 3y(x ₀ ) − 3y(x 1 ) + y(x ₂ ) + O(h ³ ),

r = 3; y(x ₋₁ ) = 4y(x ₀ ) − 6y(x 1 ) + 4y(x ₂ ) − y(x 3 ) + O(h ⁴ ),

r = 4; y(x ₋₁ ) = 5y(x ₀ ) − 10y(x 1 ) + 10y(x ₂ ) − 5y(x 3 ) + y(x ₄ ) + O(h ⁵ ),

r = 5; y(x ₋₁ ) = 6y(x ₀ ) − 15y(x 1 ) + 20y(x ₂ ) − 15y(x 3 ) + 6y(x ₄ ) − y(x 5 ) + O(h ⁶ )

(i passaggi sono descritti nei dettagli pi` u avanti nei casi r = 3 e r = 5). Utilizzando tali espressioni di y(x ₋₁ ) si vede che la prima equazione in (*)

30y(x ₁ ) − 16y(x 2 ) + y(x ₃ ) = 16α − y(x −1 ) + 12h ² q(x ₁ ) + O(h ⁶ )

`e equivalente rispettivamente alle seguenti equazioni:

30y(x ₁ ) − 16y(x 2 ) + y(x ₃ ) = 15α + O(h) + 12h ² q(x ₁ ) + O(h ⁶ ), 29y(x ₁ ) − 16y(x 2 ) + y(x ₃ ) = 14α + O(h ² ) + 12h ² q(x ₁ ) + O(h ⁶ ), 27y(x ₁ ) − 15y(x 2 ) + y(x ₃ ) = 13α + O(h ³ ) + 12h ² q(x ₁ ) + O(h ⁶ ), 24y(x ₁ ) − 12y(x 2 ) = 12α + O(h ⁴ ) + 12h ² q(x ₁ ) + O(h ⁶ ),

20y(x ₁ ) − 6y(x 2 ) − 4y(x 3 ) + y(x ₄ ) = 11α + O(h ⁵ ) + 12h ² q(x ₁ ) + O(h ⁶ ),

15y(x ₁ ) + 4y(x ₂ ) − 14y(x 3 ) + 6y(x ₄ ) − y(x 5 ) = 10α + O(h ⁶ ) + 12h ² q(x ₁ ) + O(h ⁶ ).

(14)

Nota: dalle identit` a appena ottenute, ricordando che q(x 1 ) = −y ^′′ (x 1 ), si ottengono le seguenti differenze finite approssimanti y ^′′ (x ₁ )

y ^′′ (x ₁ ) = 1 12h ²



 



 



13y(x ₀ ) − 27y(x 1 ) + 15y(x ₂ ) − y(x 3 ) 12y(x 0 ) − 24y(x ¹ ) + 12y(x 2 )

11y(x ₀ ) − 20y(x 1 ) + 6y(x ₂ ) + 4y(x ₃ ) − y(x 4 )

10y(x ₀ ) − 15y(x 1 ) − 4y(x 2 ) + 14y(x ₃ ) − 6y(x 4 ) + y(x ₅ ) +



 



 

 O(h) O(h ² ) O(h ³ ) O(h ⁴ ) Esempio (r = 3): Sostituire y(x ₋₁ ) e y(x _n+2 ) con il valore in x ₋₁ di

p ^s ₃ (x) = y(x ₀ ) _(x ^(x−x

¹

^)(x−x

²

^)(x−x

³

⁾

0

−x

1

)(x

0

−x

2

)(x

0

−x

3

) + y(x ₁ ) _(x ^(x−x

⁰

^)(x−x

²

^)(x−x

³

⁾

1

−x

0

)(x

1

−x

2

)(x

1

−x

3

)

+y(x ₂ ) _(x ^(x−x

⁰

^)(x−x

¹

^)(x−x

³

⁾

2

−x

0

)(x

2

−x

1

)(x

2

−x

3

) + y(x ₃ ) _(x ^(x−x

⁰

^)(x−x

¹

^)(x−x

²

⁾

3

−x

0

)(x

3

−x

1

)(x

3

−x

2

)

e il valore in x _n+2 di

p ^d ₃ (x) = y(x _n+1 ) _(x ^(x−x

ⁿ

^)(x−x

ⁿ⁻¹

^)(x−x

ⁿ⁻²

⁾

n+1

−x

ⁿ

)(x

n+1

−x

ⁿ−1

)(x

n+1

−x

ⁿ−2

) + y(x _n ) _(x ^(x−x

ⁿ⁺¹

^)(x−x

ⁿ⁻¹

^)(x−x

ⁿ⁻²

⁾

n

−x

n+1

)(x

n

−x

ⁿ−1

)(x

n

−x

ⁿ−2

)

+y(x _n−1 ) _(x ^(x−x

ⁿ⁺¹

^)(x−x

ⁿ

^)(x−x

ⁿ⁻²

⁾

n−1

−x

n+1

)(x

n−1

−x

ⁿ

)(x

n−1

x

n−2

) + y(x _n−2 ) _(x ^(x−x

ⁿ⁺¹

^)(x−x

ⁿ

^)(x−x

ⁿ⁻¹

⁾

n−2

−x

n+1

)(x

n−2

−x

ⁿ

)(x

n−2

x

n−1

) : y(x ₋₁ ) viene sostituito con y(x ₀ )4−y(x 1 )6+y(x ₂ )4−y(x 3 ) e y(x _n+2 ) viene sostituito con y(x _n+1 )4−

y(x _n )6 + y(x _n−1 )4 − y(x n−2 )

(errori: |y ^′v (ξ _s )|h ⁴ , ξ _s ∈ (x −1 , x ₃ ), e |y ^′v (ξ _d )|h ⁴ , ξ _d ∈ (x n−2 , x _n+2 )). Quindi:

y(x ₋₁ ) = y(x ₀ )4 − y(x 1 )6 + y(x ₂ )4 − y(x 3 ) + O(h ⁴ ),

y(x _n+2 ) = y(x _n+1 )4 − y(x n )6 + y(x _n−1 )4 − y(x n−2 ) + O(h ⁴ ).

Nota: si osserva che usando queste espressioni per y(x ₋₁ ) e y(x n+2 ) in (*) si ottiene proprio l’equazione vettoriale gi` a trovata (risolvendo in modo semplice l’esercizio) approssimando −y ^′′ (x ₁ ) = q(x ₁ ) e −y ^′′ (x _n ) = q(x _n ) con la (dIItrepunti).

Questa osservazione ci fa capire che ottenendo formule del tipo y(x ₋₁ ) = (...)+O(h ⁶ ) e y(x n+2 ) = (...) + O(h ⁶ ) — ad esempio scrivendo i due polinomi interpolanti y rispettivamente nei sei punti x _i , i = 0, . . . , 5, e nei sei punti x _n+1−i , i = 0, . . . , 5 e prendendo (...) = valori di tali polinomi in x ₋₁ e x n+2 — si otterrebbe allo stesso tempo una approssimazione di y ^′′ (x) con errore O(h ⁴ ) in termini di y(x − h), y(x), y(x + h), y(x + 2h), y(x + 3h), y(x + 4h).

r = 5: Quindi, si vuole sostituire y(x ₋₁ ) e y(x _n+2 ) con il valore in x ₋₁ di p ^s ₅ (x), il polinomio interpolante la funzione y(x) nei punti x _i , i = 0, . . . , 5, e il valore in x _n+2 di p ^d ₅ (x), il polinomio interpolante la funzione y(x) nei punti x _n+1−i , i = 0, . . . , 5:

y(x ₋₁ ) − p ^s 5 (x ₋₁ ) = y ^vi (ξ s )h ⁶ , ξ s ∈ (x −1 , x 5 ), y(x _n+2 ) − p ^d 5 (x _n+2 ) = y ^vi (ξ _d )h ⁶ , ξ _d ∈ (x n−4 , x _n+2 ),

y(x ₋₁ ) = 6y(x ₀ ) − 15y(x 1 ) + 20y(x ₂ ) − 15y(x 3 ) + 6y(x ₄ ) − y(x 5 ) + O(h ⁶ ) (quest’ultima formula si ottiene facilmente scrivendo p ^s ₅ (x) = P ₅

i=0 y(x _i ) _Π ^Π

^j⁶⁼ⁱ

^(x−x

^j

⁾

j6=i

(x

i

−x

^j

) per esteso e sostituendo, nell’espressione ottenuta, x con x ₋₁ ),

y(x n+2 ) = 6y(x n+1 ) − 15y(x ⁿ ) + 20y(x _n−1 ) − 15y(x n−2 ) + 6y(x _n−3 ) − y(x n−4 ) + O(h ⁶ ).

Sostituendo l’espressione di y(x ₋₁ ) nella prima equazione del sistema (*), si ottiene

30y ₁ − 16y 2 + y ₃ − 15y 1 + 20y ₂ − 15y 3 + 6y ₄ − y 5 + O(h ⁶ ) = 10α + 12h ² q ₁ + O(h ⁶ )

(15)

da cui l’identit` a: 15y 1 + 4y 2 − 14y ³ + 6y 4 − y ⁵ = 10α + 12h ² q 1 + O(h ⁶ ). Idem con l’espressione di y(x _n+2 ).

Dunque il sistema (*) diventa







15 4 −14 6 −1 0 · 0

−16 30 −16 1 0 ·

1 −16 30 ·

0 1 0 ·

· 0 1 0

· −16 1

· 0 1 −16 30 −16

0 · 0 −1 6 −14 4 15













y(x 1 ) y(x ₂ ) y(x ₃ )

. . y(x _n−2 ) y(x _n−1 ) y(x _n )







=





 10α

−α 0

. . 0

−β 10β





 +12h ²







q(x 1 ) q(x ₂ )

. . . . q(x _n−1 )

q(x _n )







+O(h ⁶ ).

Esercizio. Sia Aη = b il sistema lineare che si ottiene da quest’ultima uguaglianza vettoriale sostituendo y(x _i ) con η(x _i ) (i = 1, . . . , n) e togliendo gli errori O(h ⁶ ). La matrice A `e invertibile?

Quale metodo `e pi` u conveniente usare per calcolare η = A ⁻¹ b?

Si osserva inoltre che 15y ₁ + 4y ₂ − 14y 3 + 6y ₄ − y 5 = 10α + 12h ² q ₁ + O(h ⁶ ) = 10α − 12h ² y ^′′ (x ₁ ) + O(h ⁶ ), da cui si deduce che deve valere la seguente uguaglianza:

y ^′′ (x ₁ ) = 10y ₀ − 15y 1 − 4y 2 + 14y ₃ − 6y 4 + y ₅

12h ² + O(h ⁴ ),

ovvero si `e ottenuta la differenza finita non centrata che si cercava.

Esercizio. ` E possibile ottenere formule del tipo

y ^′′ (x ₁ ) = ϕ(y ₀ , y ₁ , y ₂ , y ₃ , h) + O(h ⁴ ), y ^′′ (x ₁ ) = ϕ(y ₀ , y ₁ , y ₂ , y ₃ , y ₄ , h) + O(h ⁴ ) ?

Cenni sull’interpolazione polinomiale (1) Il polinomio p _r (x) = P _r

i=0 y _i l _i (x), l _i (x) =

Π ^r _{j=0, j6=i} (x − x j ) .

Π ^r _{j=0, j6=i} (x _i − x j )

, con x _i reali distinti e y i reali, ha grado minore o uguale di r ed `e tale che p r (x _k ) = y _k , k = 0, 1, . . . , r (dimostrarlo!).

(2) Se p `e un polinomio tale che p(x _k ) = y _k , ∀ k, e ∂p ≤ r, allora p = p r (dimostrarlo!).

(3) Il polinomio p r è detto polinomio interpolante la tabella (x _k , y _k ), k = 0, 1, . . . , r. La sua rapp- resentazione in (1) è detta di Lagrange perché in termini della particolare base di Lagrange l _i (x), i = 0, 1, . . . , r, dell’insieme dei polinomi di grado minore o uguale di r.

(4) Se y _k = f (x _k ) con f sufficientemente regolare allora esiste ξ nel minimo intervallo contenente x, x ₀ , x ₁ , . . . , x _r tale che f (x) − p r (x) = _(r+1)! ¹ f ^(r+1) (ξ)Π ^r _j=0 (x − x j ).

Dimostrazione. Posto F (t) = (f (t) − p r (t))Π ^r _j=0 (x − x j ) − (f(x) − p r (x))Π ^r _j=0 (t − x j ), si osserva che F (x) = 0, F (x _k ) = 0 ∀ k. Supponendo x 6= x k ∀ k (per x = x k per qualche k la tesi `e banalmente vera), tali uguaglianze implicano che esiste ξ nel minimo intervallo contenente x, x 0 , x 1 , . . . , x r tale che f ^(r+1) (ξ) = 0. La tesi segue osservando che f ^(r+1) (t) = f ^(r+1) (t)Π ^r _j=0 (x−x j )−(f(x)−p r (x))(r+

1)!.

(16)

Appendice 2

Applicando il metodo Runge-Kutta implicito introdotto nell’esercizio (4) al problema (B) y ^′ (t) = λy(t) + (µ − λ)e ^µt , y(0) = 1 (λ < 0, µ < 0)

dopo alcuni passaggi si dimostra che

η((i + 1)h) = η(ih) 1 + ¹ ₂ hλ

1 − ¹ 2 hλ + s e ^µih , s = 1

2 h(µ − λ) 1 + e ^µh 1 − ¹ 2 hλ .

Risolvendo questa equazione alle differenze non omogenea con condizione iniziale η(0) = 1, si ottiene la seguente formula esplicita per η(x _i ) = η(ih):

η(ih) = (1 − r h ) 1 + ¹ ₂ hλ 1 − ¹ ₂ hλ

i

+ r _h e ^µih , r _h = 1 2

h(µ − λ)(1 + e ^µh ) e ^µh − 1 − ¹ ₂ hλ(e ^µh + 1) (Nota: r _h tende a 1 quando h → 0).

Usando questa formula `e facile vedere che η(x; x/n) → y(x) = e ^µx , se n → +∞, cio`e il metodo

`e convergente quando usato per risolvere il problema (B).

Inoltre, è evidente che, per h fissato piccolo (in modo che r _h è circa 1), la successione di valori approssimati η(ih) ha lo stesso andamento della successione dei valori esatti y(ih) = e ^µih a patto che |(1 + ¹ ₂ hλ)/(1 − ¹ ₂ hλ)| = |1 + ¹ ₂ hλ|/(1 − ¹ ₂ hλ) < 1. Ma questa disuguaglianza è sempre verificata (per ogni h > 0) nel nostro caso in cui λ < 0, anche se λ << 0.

Quindi, come previsto (dato il suo carattere implicito), il metodo dell’esercizio (4) funziona

bene sul problema (B), con µ < 0 moderato (ad es. µ = −1) e λ << 0, dove invece il classico

metodo di Eulero (esplicito) fallisce, nel senso che per funzionare richiede un passo troppo piccolo

se confrontato con l’andamento regolare della soluzione esatta e ^µt .

Per gli studenti del corso di Elementi di Analisi Numerica Questo scritto contiene: