Analisi numerica - Appunti

Analisi numerica

AlpT (@freaknet.org)

http://freaknet.org/alpt

April 29, 2008

Abstract

Questo testo è 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. Sarò ben lieto di correggere ogni eventuale errore che mi comunicherai. Buon lettura. ^_^

© 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 PURPOSE. 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.

Contents

• Proposizioni varie
• Preliminari
• Norme
• Sistemi lineari
• Fattorizzazione LU
• Applicazioni
• Fattorizzazione di Cholesky
• Autovalori
• Interpolazione e approssimazione
• Interpolazione polinomiale
• Approssimazione polinomiale
• Spline

1. Proposizioni varie

Proposition 1.1.

n n(n + 1)
X i = 2i=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 è pari:

n n−1 2 −− n(n + 1)2n + n n(n 1)nX X =i = n + i = n + 2 2 2|{z}i=1 i=1 n−1 dispari

Proposition 1.2. Somma quadrati:

n 3 22n + 3n + nX 2i = 6i=1{a },

Proof: Data una successione poniamo:

i −∆a = a ai i+1 i

Si ha3 3 3 2−∆i = (i + 1) i = 1 + 3i + 3i2 3 − −3i = ∆i 3i 1n nX X2 3 − −3 i = ∆i 3i 1 =i=1 i=1n nXX 3 3 3 3 3 3 3 3 3 3 3− − − · · · − −∆i = (i + 1) i = 2 1 + 3 2 + + (n + 1) n = (n + 1) 1i=1 i=1

n n n(n + 1)X X 3 33 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 23 − − − −− − − 2n + 2 + 6n + 6n 2 3n 3n 2n 2n + 3n + n2(n + 1) 2 3n(n + 1) 2nX 2 = =i = 6 6 6i=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 calcolo del costo di un algoritmo:

• Il costo della procedura α, verrà indicato con [α]
• Verranno evidenziate le operazioni usate con degli opportuni simboli (operazione *, divisione /)
• Ogni operazione verrà 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].

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

N, R, R" #n nX X=x [x ]i ii=m i=m−[n!] = n 12[(a + b) ] = 4[λX] = p{x } {y },

Definition 2.3. Date due successioni , poniamo

n ndef⇔ ∃C, ∈ |x | ≤ | ∀nx = O(y ) N : C|y > NRn n n n

Usiamo la seguente convenzione: def⇔ −a = b + O(y ) a b = O(y )

n nExample 2.4. Preso k > 1 3n 3+ n = O(n ), infatti,

k 3n 3 3≤ ≤ ∀n ≥+ n n + n 2n 1k3 3 nn , infatti,+ n = Ok k √3 3nn ≤ ∀n ≥+ n 2 kk k −→ ∈

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

R, 0def⇔ ∃C, ∈ |f ≤ ∀x ∈]x −f (x) = O (g(x)) r r > 0 : (x)| C|g(x)| r, x + r[R,x 0 00

Adottiamo la seguente convenzione: def⇔f (x) = O(g(x)) f (x) = O (g(x))

02 −→ ∈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 cheRx 0 0 +0 lim k(x) = 0x→x0

Adottiamo la seguente convenzione: def⇔ (g(x))f (x) = o(g(x)) f (x) = o

3. Norme

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

R C 1 nvettore. Si può dimostrare che le seguenti funzioni sono delle norme:

• nX kvk |v |= i1 i=1v n
• uXu 2|v |kvk = it2 i=1 1!
• n 3X 3kvk |v |= i3 i=1...
• 1!n pX pkvk |v |= ip i=1kvk | |= max{|v i = 1, . . . , n}

i∞Proposition 3.2. kvk kvklim = ∞p

p→+∞Proof : Sia | | | kvk|v = max{|v i = 1, . . . , n} =k i ∞|v |i⇒ |v | ≥ |v | ∀i ⇔ ≥ ≥ ∀i1 0k i

|v |kp |v |i⇒ ≥ ≥1 lim 0

|v |p→+∞ k| {z }s in np |v |iX Xs := lim = s (1)i|v |ki=1 i=13|v | |v | 6

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

Si ha: 1 1 1 (2)! ! !n nn p pp p p

|v ||v | iiX X Xp pkvk |v | |v | |v |= = = =i k kp |v | |v |k ki=1 i=1i=11 0

kvk |v |s |v |s |v |lim = lim = =p

k k kpp→+∞ p→+∞|{z}(1),(2) 0k − k, k − k

Definition 3.3. Siano due norme. Poniamo

0 0k − k ∼ k − k ⇔ ∃m, ≤ kvk ≤ kvk ∀v ∈M > 0 : mkvk M V

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

Proof : ∼

• È riflessiva: N (−) N (−), infatti, ≤ ≤ ∀v ∈N (v) N (v) N (v) V0 0∼
• È simmetrica: N (−) N (−) N (−) N (−), infatti, 11 0 00 0 ≤ ≤∼ ⇔ ≤ ≤ ⇒ N (v) N (v) N (v)N (−) N (−) mN (v) N (v) M N (v) M m0 00 00
• ∼ ∼ ⇒ ∼3. È 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 Vdim V = n = 1 n

Definiamo la funzione: −→N : V R0 +{|v | |N (v) = max i = 1, . . . , n}0 idove con v abbiamo indicato la i-esima componente di v secondo B, ovvero:i v = ([v] )i B i

1. h1i1. è una normaN 0 ≥1. N (v) 00 ⇔2. N (v) = 0 v = 00
2. |k|N3. N (kv) = (v), infatti,0 0 {|([kv] | |k([v] | | |k|NN (kv) = max ) = ) i = 1, . . . , n} = (v)0 B i B i 0
3. ≤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
4. h1i2. Dimostriamo che una qualsiasi norma N e’ equivalente a N . Cosi’ avremo acquisito la0tesi.Basta dimostrare che ∃m, ≤ ≤ ∀∪ ∈M > 0 : mN (v) N (v) M N (v) V0 0Per v = 0 la tesi e’ vera. Consideriamo quindi solo vettori non nulli.
5. h2i1. ∃MDim. 4Sia H = max N (e )ii=1,...,n !n n n nX 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 0i=1 i=1 i=1 i=1Quindi M = nHh2i2. ∃mDim(V, d) e’ uno spazio metrico, dove −d(v, w) = N (w v)0e’ una metrica.N e’ allora una funzione dallo spazio metrico (V, d) allo spazio metrico (R, d ), dove d e’ ela norma euclidea. Possiamo quindi applicare a N i thm di analisi II.() e’ una funzione continua in V.Si prova che N 0h2i3. N () e’ continua⇒ ⇔ |N −N continua in x lim N (x) = N (x ) lim (x) N (x )| = 00 0 0 0 0 0 0x→x x→x0 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→x0 0|{z} [AII,8.27,pg.85] − −→|N (x ) N (x)| 0M 0 n 0Quindi N () e’ continua.
6. h2i4. ∃mSia data la n-sfera secondo la norma N :0{v ∈ |S = V N (v) = 1}n 0S e’ un insieme sequenzialmente compatto.n , per il thm di Weierstrass (vedi [AII,8.34,pg.88]) si haAllora, poiche’ N e’ continua in S n∃c ∃C= min N (S ), = max N (S ) > 0n nallora, v v N (v)∈ ⇒ ≥ ⇔ ≥S N c N (v) cN (v)=n 0N (v) N (v) N (v)0 0 0Quindi m = c n×m∈Definition 3.6. Sia A , utilizzando le norme viste in [3.1,pg.3], definiamoK )( kAxkdef p m×1| ∈ 6kAk x , x = 0= sup Kp,q kxk qdefkAk kAk=p p,pk − k k − kchiamata norma matriciale, indotta da , .p qDefiniamo la trasposta coniugata di una matrice complessa:τ tA = Aτ 1ovvero, A, e’ la matrice coniugata della trasposta di A. Se A e’ reale, la trasposta coniugatacoincide con la normale trasposta.1 (A) = aij ij 5Useremo anche la seguente convenzione:(√ ∈valore assoluto di a a R|a| = aa = ∈modulo di a a CDefiniamo il raggio spettrale di A: |ρ(A) = max{|λ| λ autovalore di A}nIl prodotto scalare su , con = oppure = e’ definito come:K K R K C, def1,n τ∈se x, y : x·y = x yK defn,1 τ∈se x, y : x·y = xyK2 ·) Se = si riduce al prodotto scalare standard.(Nota K R, n×m∈Proposition 3.7. Sia A , si haK n om×1kAk kAxk | ∈ kxk1. = max x , = 1Kp,q p qSupponendo = si haK R, mXkAk |a |2. = max ij∞ 1≤i≤n j=1nX |a |kAk3. = max ij1 1≤j≤m i=1tkAk k4. = Ak ∞1 p tkAk ρ( AA)5. =2 t ⇒ kAk5.1 A = A = ρ(A)2dove ρ e’ il raggio spettrale.Proof :h1i1. Dim 1.Sia kxkλ = qxx = e’ il versore di xkxk qkxk = 1 (∗)qx = λx2 le due definizione sono equivalenti: τ t t ttxy = xy = xy = x· y6Osserviamo che: kAxk kAλxk |λ|kAxk kAxkp p p p kAxk= = = = pkxk kλxk |λ|kxk kxk |{z}q q q q (∗)Quindi, basta limitarsi a considerare i versori, ovvero consideriamo tutti e soli i vettori din om×1| ∈ kxkS = x x , = 1Kn q 0 0kAxkConsideriamo la funzione N (x) = . N (x) e’ continua, perche’ composizione di funzionip 03continue . Allora, procedendo come nella dim. del thm [3.5,pg.4], deduciamo che N (x)ammette minimo e massimo su S , e quindin 0 0sup N (x) = max N (x)x∈Sx∈S nnh1i2. Dim. 2. k − kRidefiniamo S secondo la norma :n ∞ m×1 | ∈ kxkS = x x , = 1Kn ∞Si ha kAxkkAk max (2)=∞ ∞x∈S|{z} n1. mXkAxk |(Ax) | | |= max = max a x (2.1)i ij j∞ 1≤i≤n 1≤i≤n j=1h2i1. ∃c ≥ kAxk ≤ ∀x ∈0 : c S n∞∈ ⇒ kxk ⇔ |x | ⇔ |x | ≤ ∀hx S = 1 max = 1 1 = 1, 2, . . . , m (∗)n h h∞m m mX X X| | ≤ |a ||x | ≤ |a |a x =: cij j ij j ij ij=1 j=1 j=1Sia c = max cii=1,...,nkAxk ≤ max c = ci∞ 1≤i≤n|{z}(2.1)h2i2. ∃x ∈ kAxkS : = cn ∞ mX |a |c = max c = c =i k kji=1,...,n j=1mX⇒ ≥ |a | ∀ic = 1, . . . , n (3)ijj=1Scegliamo la seguente x: ( ≥1 a 0kjx = (∗∗)j −1 a < 0kjsi ha m mX X |a |(A ) = a x = = c = cx k kj j kj k|{z}j=1 j=1(∗∗)kAxk |(Ax) | ≥ |(A |= max ) = ci x k∞ 1≤i≤nkAxk ≥ c∞h2i3. Q.E.D.3 kxkAx e’ continua perche’ composizione di funzioni lineari. N (x) = e’ continua per quanto visto in [3.5,pg.4]p7Sia kAyk kAxk= max∞ ∞x∈S nh2i1Il passo implica che∀x ∈ kAxk ≤ ⇒ kAyk ≤ ⇔ kAxk ≤S c c max cn ∞ ∞ ∞x∈S nh2i2Il passo implica che ≥kAxk ≥ kAxk cmax ∞ ∞x∈S nQuindi mXkAxk ≤≥ ⇔ kAxk ⇔ kAk |a |max c max = c = c = max ij∞ ∞ ∞ i=1,...,nx∈S x∈Sn n j=1h1i3. Dim 4.Immediata conseguenza della 2., 3..h1i4. Dim 5.h2i1. Osserviamo che dati n numeri reali o complessi s , . . . , s , si ha1 n2 2 2{|s |, |s |}) |s | |s |(max . . . , = max , . . . ,1 n 1 n|s| {|s |, |s |},Infatti, sia = max . . . , allora1 n2 2 2 2 2|s| ≥ |s | ∀i ⇒ |s| ≥ |s | ∀i ⇒ |s| |s | |s |= 1, . . . , n = 1, . . . , n = max , . . . ,i i 1 nAbbiamo: {kAxk | kxkkAk max = 1}=2 2 2|{z}1.2 th2i2. kAxk ∈Dim. che = xCx, con C Sym (R)m2 kxkFissiamo adesso una x : = 1, si ha2 v nuXu 2|(Ax) |kAxk = it2 i=12 t t tkAxk = Ax·Ax = (Ax)Ax = x AAx2t m×m∈Sia C = AA . C e’ simmetrica, infatti,R t t t tC = AA = AA = CAllora per quanto visto in Geometria II: m∈ ⇒ ∃B {u }C Sym (R) = , . . . , u base ortonormale di : u sono autovettori di CR1 m im |{z}[GII,4.13,pg.72](ku k ∀i= 1 = 1, . . . , mi 2⇒B ortonormale ⊥ ⇔ ·u ∀i 6u u = 0 = ju i j i jSia λ l’autovalore di u , ovveroi i Cu = λ ui i i∈ ∀isi ha λ = 1, . . . , m.Per il lemma [GII,4.11,pg.70], Rih2i3. {|λ | |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’ il’insieme di tutti gli autovalori di C (puo’ anche darsi che λ = λ per qualche i = j).i jsi haQuindi, per definizione (vedi [3.6,pg.6]),{|λ | |max i = 1, . . . , m} = ρ(C)i≥ ∀ih2i4. 0 = 1, . . . , mλ i 2 t t tkCu 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 22 |{z}h2i2passo 2ku k kCu k ≥ ⇔ ≥λ = 0 λ 0i i i i2 2 8h2i5. Dim. che mX2 2kAxk |λ ||α |= i i2 i=1mX2 2kxk |α |= i2 i=1dove le α sono le componenti di x secondo la base Bi( mmB base ortonormale di R X⇒ x = α ui im∈x R i=1m m m m m m mX X X X X X X2 t t t t tkAxk = xCx = xCα u = (α u )Cα u = α α u Cu = α α λ u u =i i j j i i j i j i j i i j i2 |{z} |{z}i=1 i=1