Analisi numerica - Appunti

Analisi Numerica

AlpT (@freaknet.org)

http://freaknet.org/alpt

April 29, 2008

Abstract

Questo testo e’ una rielaborazione personale degli appunti presi durante il corso di Analisi

Numerica, tenuto dal Prof. Giovanni Russo presso il dipartimento di Matematica, Catania,

A.A. 2007/2008.

Saro’ ben lieto di correggere ogni eventuale errore che mi comunicherai.

Buon lettura. ^_^

i

c

Copyright 2007 Andrea Lo Pumo aka AlpT <alpt@freaknet.org>. All rights reserved.

This document is free; you can redistribute it and/or modify it under the terms of the GNU General

Public License as published by the Free Software Foundation; either version 2 of the License, or (at your

option) any later version.

This document is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;

without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PUR-

POSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this document; if

not, write to the Free Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.

ii

Contents

1 Proposizioni varie 1

2 Preliminari 2

3 Norme 3

4 Sistemi lineari 12

4.1 Fattorizzazione LU . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

4.1.1 Applicazioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

4.2 Fattorizzazione di Cholesky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

4.3 Autovalori . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

5 Interpolazione e approssimazione 31

5.1 Interpolazione polinomiale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

6 Approssimazione polinomiale 40

6.1 Spline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

7 * 46

iii

1 Proposizioni varie

Proposition 1.1. n n(n + 1)

X i = 2

i=1

Proof : Supponiamo dapprima n dispari:

n

X

· · · − − − · · · − − −

i = 1 + 2 + 3 + + (n 3) + (n 2) + (n 1) + n = 1 + 2 + (3 + + n 3) + n 2 + n 1 + n =

i=1 −

n 1 n(n + 1)

· · · ) + n =

= (n + n + n + + n n + n =

2 2

{z }

| (n−1)/2 volte

Se n e’ pari: n n−1 2 −

− n(n + 1)

2n + n n

(n 1)n

X X =

i = n + i = n + 2 2 2

|{z}

i=1 i=1 n−1 dispari

Proposition 1.2. Somma quadrati: n 3 2

2n + 3n + n

X 2

i = 6

i=1

{a },

Proof : Data una successione poniamo:

i −

∆a = a a

i i+1 i

Si ha

3 3 3 2

−

∆i = (i + 1) i = 1 + 3i + 3i

2 3 − −

3i = ∆i 3i 1

n n

X X

2 3

− −

3 i = ∆i 3i 1 =

i=1 i=1

n n

X

X 3 3 3 3 3 3 3 3 3 3 3

− − − · · · − −

∆i = (i + 1) i = 2 1 + 3 2 + + (n + 1) n = (n + 1) 1

i=1 i=1 n n n(n + 1)

X X 3 3

3 3 − − −

− − − (n + 1) 1 3 n

= (n + 1) 1 3 i 1 = 2

|{z}

i=1 i=1 [1.1,pg.1]

n 3 2 2 3 2

3 − − − −

− − − 2n + 2 + 6n + 6n 2 3n 3n 2n 2n + 3n + n

2(n + 1) 2 3n(n + 1) 2n

X 2 = =

i = 6 6 6

i=1 1

2 Preliminari

Definition 2.1. Definiamo il costo in un algoritmo numerico, misurato in flops (Floating Point

Operations), come il numero di divisioni e moltiplicazioni e l’algoritmo esegue.

Useremo la seguente scrittura per il callcolo del costo di un algoritmo:

1. Il costo della procedura α, verra’ indicato con [α]

2. Verranno evidenziate le operazioni usate con degli opportuni simboli (operazione *, divi-

sione /)

3. Ogni operazione verra’ sostituita da un 1. Tutte le non operazioni verranno eliminati

Definizioni: def

∗

[a b] = [a/b] 1

def

±

[a b] = 0

Come esempio completo, vedi il calcolo del costo dell’algoritmo [4.1,pg.12].

p

∈ ∈ ∈

Proposition 2.2. Siano m, n a, b, λ X + Y , si ha

N, R, R

" #

n n

X X

=

x [x ]

i i

i=m i=m

−

[n!] = n 1

2

[(a + b) ] = 4

[λX] = p

{x } {y },

Definition 2.3. Date due successioni , poniamo

n n

def

⇔ ∃C, ∈ |x | ≤ | ∀n

x = O(y ) N : C|y > N

R

n n n n

Usiamo la seguente convenzione: def

⇔ −

a = b + O(y ) a b = O(y )

n n

Example 2.4. Preso k > 1 3

n 3

+ n = O(n ), infatti,

k 3

n 3 3

≤ ≤ ∀n ≥

+ n n + n 2n 1

k

3 3

n

n , infatti,

+ n = O

k k √

3 3

n

n ≤ ∀n ≥

+ n 2 k

k k −→ ∈

Definition 2.5. Date due funzioni f (x), g(x) : I⊆R dato x I, poniamo

R, 0

def

⇔ ∃C, ∈ |f ≤ ∀x ∈]x −

f (x) = O (g(x)) r r > 0 : (x)| C|g(x)| r, x + r[

R,

x 0 0

0

Adottiamo la seguente convenzione: def

⇔

f (x) = O(g(x)) f (x) = O (g(x))

0

2 −→ ∈

Definition 2.6. Date due funzioni f (x), g(x) : I⊆R dato x I, poniamo

R, 0

( ≤ ∀x ∈]x −

f (x)| k(x)|g(x)| r, x + r[

def 0 0

⇔ ∃r ∃k(x) −

f (x) = o (g(x)) > 0, :]x r, x + r[−→ tale che

R

x 0 0 +

0 lim k(x) = 0

x→x

0

Adottiamo la seguente convenzione: def

⇔ (g(x))

f (x) = o(g(x)) f (x) = o

0

3 Norme n n

Proposition 3.1. Consideriamo lo spazio vettoriale o e sia v = (v , . . . , v ) un suo

R C 1 n

vettore. Si puo’ dimostrare che le seguenti funzioni sono delle norme:

n

X

kvk |v |

= i

1 i=1

v n

u

X

u 2

|v |

kvk = i

t

2 i=1 1

!

n 3

X 3

kvk |v |

= i

3 i=1

..

. 1

!

n p

X p

kvk |v |

= i

p i=1

kvk | |

= max{|v i = 1, . . . , n}

i

∞

Proposition 3.2. kvk kvk

lim = ∞

p

p→+∞

Proof : Sia | | | kvk

|v = max{|v i = 1, . . . , n} =

k i ∞

|v |

i

⇒ |v | ≥ |v | ∀i ⇔ ≥ ≥ ∀i

1 0

k i |v |

k

p

|v |

i

⇒ ≥ ≥

1 lim 0

|v |

p→+∞ k

| {z }

s i

n n

p

|v |

i

X X

s := lim = s (1)

i

|v |

k

i=1 i=1

3

|v | |v | 6

Se = 0, la tesi e’ vera. Supponiamo che = 0.

k k

Si ha: 1 1 1 (2)

! ! !

n n

n p p

p p p

|v |

|v | i

i

X X X

p p

kvk |v | |v | |v |

= = =

i k k

p |v | |v |

k k

i=1 i=1

i=1

1 0

kvk |v |s |v |s |v |

lim = lim = =

p

k k k

p

p→+∞ p→+∞

|{z}

(1),(2) 0

k − k, k − k

Definition 3.3. Siano due norme. Poniamo

0 0

k − k ∼ k − k ⇔ ∃m, ≤ kvk ≤ kvk ∀v ∈

M > 0 : mkvk M V

Proposition 3.4. La relazione definita in [3.3,pg.4] e’ una relazione d’equivalenza.

Proof : ∼

1. E’ riflessiva: N (−) N (−), infatti, ≤ ≤ ∀v ∈

N (v) N (v) N (v) V

0 0

∼ ⇒ ∼

2. E’ simmetrica: N (−) N (−) N (−) N (−), infatti, 1

1 0 0

0 0 ≤ ≤

∼ ⇔ ≤ ≤ ⇒ N (v) N (v) N (v)

N (−) N (−) mN (v) N (v) M N (v) M m

0 00 00

∼ ∼ ⇒ ∼

3. E’ transitiva: N (−) N (−) N (−) N (−) N (−) , infatti,

0 0

∼ ⇔ ≤ ≤

N (−) N (−) mN (v) N (v) M N (v)

0 00 0 00 0

∼ ⇔ ≤ ≤

N (−) N (−) bN (v) N (v) BN (v)

0 00 0 00

≤ ≤ ≤ ⇔ ∼

≤ N (v) BN (v) BM N (v) N (−) N (−)

bmN (v) bN (v)

Theorem 3.5. Tutte le norme in uno spazio vettoriale V di dimensione finita n sono equivalenti.

Proof : }

⇒ ∃B {e , . . . , e base di V

dim V = n = 1 n

Definiamo la funzione: −→

N : V R

0 +

{|v | |

N (v) = max i = 1, . . . , n}

0 i

dove con v abbiamo indicato la i-esima componente di v secondo B, ovvero:

i v = ([v] )

i B i

h1i1. e’ una norma

N 0 ≥

1. N (v) 0

0 ⇔

2. N (v) = 0 v = 0

0 |k|N

3. N (kv) = (v), infatti,

0 0 {|([kv] | |k([v] | | |k|N

N (kv) = max ) = ) i = 1, . . . , n} = (v)

0 B i B i 0

≤

4. N (v + w) N (v) + N (w), infatti,

0 0 0

{|(v | |v | | |v | ≤ |v | |w | ≤

N (v + w) = max + w) = + w i = 1, . . . , n} = + w + N (v) + N (w)

0 i i i k k k k 0 0

h1i2. Dimostriamo che una qualsiasi norma N e’ equivalente a N . Cosi’ avremo acquisito la

0

tesi.

Basta dimostrare che ∃m, ≤ ≤ ∀∪ ∈

M > 0 : mN (v) N (v) M N (v) V

0 0

Per v = 0 la tesi e’ vera. Consideriamo quindi solo vettori non nulli.

h2i1. ∃M

Dim. 4

Sia H = max N (e )

i

i=1,...,n !

n n n n

X X X X

≤ |v |N ≤

N (v) = N v e N (v e ) = (e ) N (v)H = nHN (v)

i i i i i i 0 0

i=1 i=1 i=1 i=1

Quindi M = nH

h2i2. ∃m

Dim

(V, d) e’ uno spazio metrico, dove −

d(v, w) = N (w v)

0

e’ una metrica.

N e’ allora una funzione dallo spazio metrico (V, d) allo spazio metrico (R, d ), dove d e’

e e

la norma euclidea. Possiamo quindi applicare a N i thm di analisi II.

() e’ una funzione continua in V.

Si prova che N 0

h2i3. N () e’ continua

⇒ ⇔ |N −

N continua in x lim N (x) = N (x ) lim (x) N (x )| = 0

0 0 0 0 0 0 0

x→x x→x

0 0

 ≤ |N − ≤ |N −

0 (x) N (x )| M (x) N (x )|

0 0 0 0



 |{z}



 h2i1 |N − ⇔

⇒ lim (x) N (x )| = 0 lim N (x) = N (x )

0 0

−→

0 0 x→x x→x

0 0

|{z}



 [AII,8.27,pg.85]

 − −→

|N (x ) N (x)| 0

M

 0 n 0

Quindi N () e’ continua.

h2i4. ∃m

Sia data la n-sfera secondo la norma N :

0

{v ∈ |

S = V N (v) = 1}

n 0

S e’ un insieme sequenzialmente compatto.

n , per il thm di Weierstrass (vedi [AII,8.34,pg.88]) si ha

Allora, poiche’ N e’ continua in S n

∃c ∃C

= min N (S ), = max N (S ) > 0

n n

allora,

v v N (v)

∈ ⇒ ≥ ⇔ ≥

S N c N (v) cN (v)

=

n 0

N (v) N (v) N (v)

0 0 0

Quindi m = c n×m

∈

Definition 3.6. Sia A , utilizzando le norme viste in [3.1,pg.3], definiamo

K )

( kAxk

def p m×1

| ∈ 6

kAk x , x = 0

= sup K

p,q kxk q

def

kAk kAk

=

p p,p

k − k k − k

chiamata norma matriciale, indotta da , .

p q

Definiamo la trasposta coniugata di una matrice complessa:

τ t

A = A

τ 1

ovvero, A, e’ la matrice coniugata della trasposta di A. Se A e’ reale, la trasposta coniugata

coincide con la normale trasposta.

1 (A) = a

ij ij 5

Useremo anche la seguente convenzione:

(

√ ∈

valore assoluto di a a R

|a| = aa = ∈

modulo di a a C

Definiamo il raggio spettrale di A: |

ρ(A) = max{|λ| λ autovalore di A}

n

Il prodotto scalare su , con = oppure = e’ definito come:

K K R K C, def

1,n τ

∈

se x, y : x·y = x y

K def

n,1 τ

∈

se x, y : x·y = xy

K

2 ·

) Se = si riduce al prodotto scalare standard.

(Nota K R, n×m

∈

Proposition 3.7. Sia A , si ha

K n o

m×1

kAk kAxk | ∈ kxk

1. = max x , = 1

K

p,q p q

Supponendo = si ha

K R, m

X

kAk |a |

2. = max ij

∞ 1≤i≤n j=1

n

X |a |

kAk

3. = max ij

1 1≤j≤m i=1

t

kAk k

4. = Ak ∞

1 p t

kAk ρ( AA)

5. =

2 t ⇒ kAk

5.1 A = A = ρ(A)

2

dove ρ e’ il raggio spettrale.

Proof :

h1i1. Dim 1.

Sia kxk

λ = q

x

x = e’ il versore di x

kxk q

kxk = 1 (∗)

q

x = λx

2 le due definizione sono equivalenti: τ t t t

t

xy = xy = xy = x· y

6

Osserviamo che: kAxk kAλxk |λ|kAxk kAxk

p p p p kAxk

= = = = p

kxk kλxk |λ|kxk kxk |{z}

q q q q (∗)

Quindi, basta limitarsi a considerare i versori, ovvero consideriamo tutti e soli i vettori di

n o

m×1

| ∈ kxk

S = x x , = 1

K

n q 0 0

kAxk

Consideriamo la funzione N (x) = . N (x) e’ continua, perche’ composizione di funzioni

p 0

3

continue . Allora, procedendo come nella dim. del thm [3.5,pg.4], deduciamo che N (x)

ammette minimo e massimo su S , e quindi

n 0 0

sup N (x) = max N (x)

x∈S

x∈S n

n

h1i2. Dim. 2. k − k

Ridefiniamo S secondo la norma :

n ∞ m×1

| ∈ kxk

S = x x , = 1

K

n ∞

Si ha kAxk

kAk max (2)

=

∞ ∞

x∈S

|{z} n

1. m

X

kAxk |(Ax) | | |

= max = max a x (2.1)

i ij j

∞ 1≤i≤n 1≤i≤n j=1

h2i1. ∃c ≥ kAxk ≤ ∀x ∈

0 : c S n

∞

∈ ⇒ kxk ⇔ |x | ⇔ |x | ≤ ∀h

x S = 1 max = 1 1 = 1, 2, . . . , m (∗)

n h h

∞

m m m

X X X

| | ≤ |a ||x | ≤ |a |

a x =: c

ij j ij j ij i

j=1 j=1 j=1

Sia c = max c

i

i=1,...,n

kAxk ≤ max c = c

i

∞ 1≤i≤n

|{z}

(2.1)

h2i2. ∃x ∈ kAxk

S : = c

n ∞ m

X |a |

c = max c = c =

i k kj

i=1,...,n j=1

m

X

⇒ ≥ |a | ∀i

c = 1, . . . , n (3)

ij

j=1

Scegliamo la seguente x: ( ≥

1 a 0

kj

x = (∗∗)

j −1 a < 0

kj

si ha m m

X X |a |

(A ) = a x = = c = c

x k kj j kj k

|{z}

j=1 j=1

(∗∗)

kAxk |(Ax) | ≥ |(A |

= max ) = c

i x k

∞ 1≤i≤n

kAxk ≥ c

∞

h2i3. Q.E.D.

3 kxk

Ax e’ continua perche’ composizione di funzioni lineari. N (x) = e’ continua per quanto visto in [3.5,pg.4]

p

7

Sia kAyk kAxk

= max

∞ ∞

x∈S n

h2i1

Il passo implica che

∀x ∈ kAxk ≤ ⇒ kAyk ≤ ⇔ kAxk ≤

S c c max c

n ∞ ∞ ∞

x∈S n

h2i2

Il passo implica che ≥

kAxk ≥ kAxk c

max ∞ ∞

x∈S n

Quindi m

X

kAxk ≤≥ ⇔ kAxk ⇔ kAk |a |

max c max = c = c = max ij

∞ ∞ ∞ i=1,...,n

x∈S x∈S

n n j=1

h1i3. Dim 4.

Immediata conseguenza della 2., 3..

h1i4. Dim 5.

h2i1. Osserviamo che dati n numeri reali o complessi s , . . . , s , si ha

1 n

2 2 2

{|s |, |s |}) |s | |s |

(max . . . , = max , . . . ,

1 n 1 n

|s| {|s |, |s |},

Infatti, sia = max . . . , allora

1 n

2 2 2 2 2

|s| ≥ |s | ∀i ⇒ |s| ≥ |s | ∀i ⇒ |s| |s | |s |

= 1, . . . , n = 1, . . . , n = max , . . . ,

i i 1 n

Abbiamo: {kAxk | kxk

kAk max = 1}

=

2 2 2

|{z}

1.

2 t

h2i2. kAxk ∈

Dim. che = xCx, con C Sym (R)

m

2 kxk

Fissiamo adesso una x : = 1, si ha

2 v n

u

X

u 2

|(Ax) |

kAxk = i

t

2 i=1

2 t t t

kAxk = Ax·Ax = (Ax)Ax = x AAx

2

t m×m

∈

Sia C = AA . C e’ simmetrica, infatti,

R t t t t

C = AA = AA = C

Allora per quanto visto in Geometria II: m

∈ ⇒ ∃B {u }

C Sym (R) = , . . . , u base ortonormale di : u sono autovettori di C

R

1 m i

m |{z}

[GII,4.13,pg.72]

(

ku k ∀i

= 1 = 1, . . . , m

i 2

⇒

B ortonormale ⊥ ⇔ ·u ∀i 6

u u = 0 = j

u i j i j

Sia λ l’autovalore di u , ovvero

i i Cu = λ u

i i i

∈ ∀i

si ha λ = 1, . . . , m.

Per il lemma [GII,4.11,pg.70], R

i

h2i3. {|λ | |

Dim. che max i = 1, . . . , m} = ρ(C)

i {λ |

Se costruiamo B usando il metodo descritto in [GII,4.12,pg.71], allora i = 1, . . . , m} e’

i 6

l’insieme di tutti gli autovalori di C (puo’ anche darsi che λ = λ per qualche i = j).

i j

si ha

Quindi, per definizione (vedi [3.6,pg.6]),

{|λ | |

max i = 1, . . . , m} = ρ(C)

i

≥ ∀i

h2i4. 0 = 1, . . . , m

λ i 2 t t t

kCu k ·u ku k

= u Cu = u λ u = λ u u = λ u = λ

i i i i i i i i i i i i i i 2

2 |{z}

h2i2

passo 2

ku k kCu k ≥ ⇔ ≥

λ = 0 λ 0

i i i i

2 2 8

h2i5. Dim. che m

X

2 2

kAxk |λ ||α |

= i i

2 i=1

m

X

2 2

kxk |α |

= i

2 i=1

dove le α sono le componenti di x secondo la base B

i

( m

m

B base ortonormale di R X

⇒ x = α u

i i

m

∈

x R i=1

m m m m m m m

X X X X X X X

2 t t t t t

kAxk = xCx = xCα u = (α u )Cα u = α α u Cu = α α λ u u =

i i j j i i j i j i j i i j i

2 |{z} |{z}

i=1 i=1