Appunti Calcolo numerico

C

n (k+1) (k)

Qualsiasi sia x la successione definita da x =Bx +c (k= 0, 1, …) converge a x*

0

n*n

b. BC

X*, soluzione di Ax=b, sia l’unica soluzione di x=Bx+c

(B)=max |λ | il raggio spettrale di B

k=1, …, n k

C (x

(0) n (k) (k+1) (k) (k)

Qualsiasi sia x , la successione {x } definita da x = ) = Bx +c (k=0, 1, 2,

(B)<1

…) converge a x* SE E SOLO SE (sono da preferire matrici con raggio

spettrale il più piccolo possibile)

A partire da questi teoremi si è dimostrato che:

I. Se A è a predominanza diagonale stretta per le righe il metodo di Jacobi converge;

II. Se A è a predominanza diagonale stretta per le righe, o è simmetrica e definita

positiva, il metodo di Gauss-Seidel converge.

APPELLO 4 2022 

DOMANDA 1

- • Il problema della derivazione numerica consiste nell’approssimare la derivata di una

funzione f in un certo punto x , ovvero (qualora esista la derivata della funzione): f’(x ) = D

0 0

)

()−( 0

f(x )= = limite del rapporto incrementale. Ma è da prestare attenzione al

0 −

→ 0

0

fatto che se f e f (approssimazione di f) sono “vicine”, non vuol dire che anche f’ e f ’ lo

n n

siano.

Tra le formule di derivazione c’è quella della differenza in avanti: Sia f derivabile in [a,b].



Supposto che per un h>0 fissato siano x, x+h [a,b]. Si definisce “differenza in avanti” in x

(+ℎ)−() (+ℎ)−() ′

2 ()

= +

di passo h: δ (f, x , h): = , se poi f C ([a,b]): δ (f, x , h): =

+ 0 + 0

ℎ ℎ

′′ ()

ℎ x (x,

tale che x+h)

2

• Errore delle differenze in avanti nel valutare f’ in x : Dalla formula di Taylor, f(x +h)= f(x ) +

0 0 0

x (x

2

hf’(x ) + h f’’(x )/2 con , x +h), per cui, riarrangiando i termini si ottiene f (x + h) −

0 0 0 0 0 0

′′

) ( )

( +ℎ)−( ℎ

′

0 0 0

2 ( )

= +

f (x ) = hf ′ (x ) + h f ′′(ξx )/2, da cui: δ (f, x , h): = tale

0 0 0 + 0 0

ℎ 2

′′ ( )

ℎ

x (x ′ 0

( )

+

che , x +h). Essendo h>0 e : δ (f, x , h): = , l’errore assoluto risulta:

0 0 0 + 0 0 2

′′

) ( )

( +ℎ)−( x (x

′

0 0 0

( )|

− = ℎ

| | |

|δ (f, x , h) – f’(x )| : = tale che , x +h). (stima

+ 0 0 0 0 0

0

ℎ 2

errore delle differenze in avanti ottenuta matematicamente mediante formula di taylor)

• In aritmetica esatta diremmo che utilizzando passi h sempre più piccoli abbiamo

approssimazioni sempre migliori della derivata prima, ma numericamente le cose vanno

diversamente. Infatti la funzione f non viene sempre valutata esattamente ed ogni volta

̃( +ℎ)−̃( )

̃ 0 0

(,

+ , ℎ) =

calcoliamo un rapporto incrementale perturbato: e questo

0 ℎ

crea problemi numerici, di fatto non suggerendo l’utilizzo in aritmetica non esatta di passi h

troppo piccoli, contrariamente a quanto detto dalla convergenza teorica. (si suggerisce di

4 4 ̃

(x )|,

=√ f

scegliere un h non più piccolo di h*= con ε=max(|f(x )- f(x +h)-

√ 0 0

0

′′ ( )

2 0

̃ (2)

(x

f + h)| ed M = max |f (x)|, in quanto risulta

2 x[a,b]

0 ℎ 2

̃

′ 2

( ) (,

| − + , ℎ)| ≤ + (per h sufficientemente piccolo risulta rilevante il

0 0 2 ℎ

termine 2ε/h, altrimenti per h non sufficientemente piccolo risulta rilevante il termine

M h/2).

2

DOMANDA 2

- • In cosa consiste la fattorizzazione P A = LU (descrivere le matrici P, L, U)? La matrice P, detta

matrice di permutazione (= matrice le cui componenti sono 0 o 1, in particolare ogni sua

riga e colonna contiene una sola componente 1) è tale che C=PA coincide con la matrice A

n*n

eccetto per il fatto che le righe i, j sono scambiate. Sia AR , allora esiste una matrice di

permutazione P tale che PA=LU, con:

C →

n*n

a) L=(l ) triangolare inferiore con elementi diagonali l =1 contiene tutti i

i,j i,i

moltiplicatori del processo noto come eliminazione gaussiana senza pivoting (pivot:

k,k(k)

a ) C

n*n

b) U=(u ) triangolare inferiore

i,j

• (Matrice

Nota la fattorizzazione P A = LU, come si può risolvere il sistema Ax = b, con A matrice quadrata non singolare?

quadrata non singolare, o invertibile ha il determinante diverso la zero). Il processo di

eliminazione gaussiana con pivoting, è lo stesso di quello senza pivoting, però in aggiunta

dobbiamo scambiare ad ogni passo certe equazioni e matricialmente questo corrisponde a

scambiare (ovvero permutare) certe righe della matrice utilizzando la matrice di

permutazione P. L’algoritmo di Gauss con pivoting di colonna si può rappresentare nella

forma PA=LU: non è altro che la forma più generale della fattorizzazione LU ed è applicabile

ad ogni matrice non singolare. La risoluzione di un sistema lineare Ax=b (con det(A)0, A

matrice non singolare) tramite la fattorizzazione sopra citata si riduce alla risoluzione di due

sistemi triangolari:

=

{ (y soluzione della prima equazione, x soluzione del sistema lineare)

=

• Nota la fattorizzazione P A = LU, come si può calcolare il determinante di A e perché?

C

n*n

Essendo che L=(l ) triangolare inferiore con elementi diagonali l =1, det(L)=1,

i,j i,i

→

det(P)=1 det(A)=det(L)det(U)=det(U), siccome PA=LU

Da notare che essendo U una matrice triangolare superiore, il suo determinante sarà più

semplice da calcolare rispetto a calcolare il determinante di una matrice A (costo

computazionale minore).

APPELLO 3 2022 

DOMANDA 1

- • Formula dell’errore del prodotto dei numeri macchina, ovvero determinare una

|(x · y) − (x ⊗ y)| |x − fl(x)| |y − fl(y)|

⊗

ϵ = ϵ = ϵ =

maggiorazione di in funzione di , , nelle

x y

x,y |x · y| |x| |y|

|fl(x)| |fl(y)|

 0, ⁄ ⁄

ipotesi che x 0, y ≈ 1, ≈ 1, fl ( fl(x) · fl(y) ) = fl(x) · fl(y).

|x| |y|

⊗

ϵ <≈ ϵ ϵ

In queste ipotesi + .

x y

x,y

• Dimostrazione di tale asserto (nelle ipotesi del punto precedente):

|(x (x

· y) − ⊗ y)| ∙ ) − ∙ ())|

|( (()

⊗

ϵ = =

x,y |x |

· y| ∙ |

∙ ) − ∙ ()) + ∙ ()) − ∙ ())|

|( ( ( (()

= | ∙ |

| ∙ ( − () + ()) ∙ ( − ())|

= | ∙ |

∙ − ())| + ∙ ∗ −())|

| ( |() (

≤ | ∙ |

|| | |()| |

∙ − ()| ∙ − ()|

= +

|| || || ||

∙ ∙

| |()| |

− ()| − ()|

= + ∙ ≈ + 1 ∙

|| || ||

⊗

ϵ <≈ ϵ ϵ

Quindi: + .

x y

x,y

• Per quanto riguarda le analisi di stabilità della somma e della sottrazione, si nota che per

ϵ

queste due operazioni abbiamo che per piccoli errori sui dati (ϵ e ) possono aversi errori

x y

rivelanti sui risultati, qualora ciò accada si parla del fenomeno della cancellazione, ovvero

somma e sottrazione non sono stabili.

DOMANDA 2

- • Suppongo che un metodo per la risoluzione di equazioni non lineari generi una successione

{x } converge alla soluzione x* del problema f(x*)=0. Pongo e =|x -x*| (=errore assoluto

k k k

nell’approssimare la soluzione x con la soluzione generata dal metodo x*).

k enp

Il metodo ha ordine di convergenza ALMENO p≥1 se esiste C>0 tale che e ≤C per

n+1

+1

lim ( )=≠0

n=0,1,2,… e ordine di convergenza ESATTAMENTE p se vale

→∞

(L=costante asintotica di errore)

• Il metodo di bisezione utilizza il segno di f(x) non il valore effettivo. Data f:[a,b]→ R

continua, si suppone f(a)f(b)<0 quindi l’intervallo [a,b]contiene almeno uno di zero di f(x*).

Fisso un intervallo (a ,b ) tale che k appartiene {0,1,…} in cui il segno di f(a ) è diverso da

k k k

quello di f(b ), ovvero f(a )f(b )<0, quindi in (a ,b ) esiste uno zero x* di f. Si calcola ora il

k k k k k

punto medio x di questo intervallo: x =(a +b ):2. Se f(x )=0 si conclude il processo in quanto

k k k k k

x è lo zero cercato di f. Più in generale se un certo criterio di arresto è verificato si conclude

k

il processo in quanto si ritiene che x sia una buona approssimazione dello zero di f.

k

• Teorema di convergenza del metodo di bisezione: Sia f:[a,b]→ R funzione continua e

f(a)f(b)<0. Allora se x è la k-esima iterazione del metodo di bisezione, esiste uno zero x* di f

k

-(k+)

tale che: |x -x*|≤2 (b-a) (a lungo andare va sempre meglio asintoticamente). Inoltre

k −

( )⌉ − 1

⌈

affinché per un certo ε>0 si abbia |x -x*|≤ ε, necessitano al più k*(ε)=

k 2

iterazioni (⌈⌉= funzione che arrotonda x appartenente ad r al più piccolo intero non minore

di x, in matlab corrisponde al comando “ceil”)

• 

Se f C([a,b]) il metodo delle secanti definisce la successione:

− 

−1 1

)

= − ( ⋅ ( ). Se f C ([a,b]) essa può essere considerata una

+1 )−( )

( −1

variazione del metodo di Newton avente come iterate {x~ } solo che: il metodo delle secanti

n

necessita di 2 punti iniziali (x ,x ), non necessita del calcolo della derivata f’, in quanto “f(x )-

0 1 n

f(x )” ne è un’approssimazione. (Quale è la principale differenza rispetto al metodo di Newton, relativamente alla

n-1

regolarità di f?)

APPELLO 2 2022

DOMA