Sistemi lineari

(1)

Sistemi lineari

1. Norme:

ρ(A) = λ

M

(A) = max{|λ| | λ autoval A}

kAk

_∞

= max

1≤i≤n m

X

j=1

|a

_ij

|

kAk

₁

= k

^t

Ak

_∞

kAk

₂

= p

λ

M

(

^t

AA) kA

⁻¹

k

₂

= 1

pλ

m

(

^t

AA) A =

^t

A ⇒ kAk

₂

= |λ

M

(A)|

A =

^t

A ⇒ kA

⁻¹

k

₂

= 1

|λ

m

(A)|

ρ(A) = inf

p,q∈N^∗

kAk

_p,q

2. Triangolare superiore:

x

i

= b

i

− P

n

j=i+1

a

ij

x

j

a

ii

∀i = n, .., 1 Triangolare inferiore:

x

i

= b

i

− P

i−1 j=1

a

ij

x

j

a

ii

∀i = 1, .., n

3. Condizionamento:

A(x + ∆x) = b + ∆b k∆xk

kxk ≤ µ(A) k∆bk kbk µ

2

(A) = pλ

M

(

^t

AA)

pλ

m

(

^t

AA) A =

^t

A ⇒ µ

2

(A) = |λ

M

|

|λ

m

|

4. Gauss (pivot):

pivot riga k :

Sia i t.c. |a

_ik

| := max

i:=k,..,n

|a

_ik

| scambio righe i, k

pivot scalato k : d

i

:= |a

_ik

|

max

j=k,..,n

|a

_ij

| Sia i t.c. d

_i

= max

i=1,..,n

d

i

∀k = 1, .., n − 1 pivot k

∀i = k + 1, .., n a

_ik

:= a

ik

a

_kk

∀j = k + 1, .., n + 1 a

ij

:= a

ij

− a

_ik

a

kj

5. Fattorizzazione Cholesky

A ∈ R

^n×n

, simmetrica, definita pos.

A = R

^t

R, R ∈ R

^n×n

triang. inf.

a

ij

=

min{i,j}

X

k=1

R

ik

R

jk

∀i, j

∀j = 1, . . . , n

r

jj

:=

v u u t a

jj

−

j−1

X

k=1

r

²_jk

∀i = j + 1, . . . , n

r

ij

:= a

ij

− P

j−1 k=1

r

ik

r

jk

r

jj

6. Gershgorin-Hadamard A ∈ C

^n×n

D

i

= {z ∈ C | |z − a

ii

| ≤ R

i

} R

i

= X

j6=i

|a

ij

|

{autoval. di A } ⊆

n

[

i=1

D

i

7. Metodo delle potenze:

|λ

1

| > |λ

2

| ≥ |λ

3

| ≥ .. ≥ |λ

n

| x

0

∈ C

^n,1

, x

0

6= 0

y

k

= x

k

kx

_k

k , x

k+1

= Ay

k

σ

k

=

t

x

k

Ax

k t

x

k

x

k

=

t

y

k

x

k+1 t

y

k

y

k

z

0

= x

0

, z

k+1

= Az

k

, σ

_k⁰

=

t

z

k

Az

k t

z

k

z

k

lim

k→∞

σ

k

= lim

k→∞

σ

⁰_k

= λ

1

Crit. arresto: k(A − σ

_k

I)y

k

k σ

_k

ky

_k

k < ε oppure |σ

k+1

− σ

k

| < ε

Interpolazione

1. Lagrange:

λ

j

(x) = Y

0≤i≤n, i6=j

x − x

i

x

j

− x

i

p(x) =

n

X

j=0

y

j

λ

j

(x)

n

X

j=0

λ

j

(x)(x

j

− x)

^k

≡ (

1 k = 0 0 k > 0 λ

j

(x

i

) = δ

ij

2. Differenze divise:

f [x

0

] = f (x

0

) f [x

0

, .., x

j

] =

= f [x

1

, .., x

j

] − f [x

0

, .., x

j−1

] x

j

− x

0

f [x0] = f(x0)

f [x0, x1]

f [x1] = f(x1) f [x0, x1, x2]

f [x1, x2]

f [x2] = f(x2)

3. Newton:

w

0

(x) = 1, w

j

(x) =

j−1

Y

i=0

(x − x

i

)

p

n

(x) =

n

X

i=0

f [x

0

, . . . , x

i

]w

i

(x)

R

n

(x) = f

⁽ⁿ⁺¹⁾

(ξ) (n + 1)! ω

n+1

(x) 4. Chebyshev

t

n

(x) = cos nϕ(x) : [−1, 1] −→ R ϕ(x) = arcos x : [−1, 1] −→ [0, π]

t

0

(x) = 1, t

1

(x) = x

t

n

(x) = 2t

n−1

(x)x − t

n−2

(x) ∀n > 1 deg t

n

(x) = n ∀n ≥ 0

c

n

= 2

ⁿ⁻¹

∀n ≥ 1 radici di t

n

: α

_k

= cos “ π

2n + k π n

”

k = 0, .., n − 1

max: M

k

= cos

„ k 2π

n

«

k = 0, .., n

min: m

_k

= cos

„ k 2π

n + π n

«

k = 0, .., n 5. Polinomio di Bernstein:

B

_n,k

(x) = “ n k

”

x

^k

(1 − x)

^n−k

n

X

k=0

B

n,k

(x) = 1

B

n

(f )(x) =

n

X

k=0

f „ k n

« B

n,k

(x)

n→+∞

lim B

n

(f )

^u.

= f in [0, 1]

dove f ∈ C

⁰

([0, 1]) 6. Minimi quadrati

ϕ(x, a) =

m

X

j=1

a

j

ϕ

j

(x), φ ∈ R

^n×m

φ

jk

= ϕ

k

(x

j

),

^t

φφa =

^t

φy, det

^t

φφ 6= 0

ε(v)

i

= y

i

− ϕ(x

i

, v), kε(a)k

²₂

minima

(2)

Zeri e punti fissi

1. Newton: x

n+1

= x

n

− f (x

n

) f

⁰

(x

n

) Secanti:

x

k+1

= x

k

− f (x

k

) x

k

− x

_k−1

f (x

k

) − f (x

k−1

) Bisezione:

While : c := a + b

2 Se |b − a| < 2ε ∨ f (c) = 0 : break

Se f (c)f (a) > 0 : a := c Se f (c)f (a) < 0 : b := c α := c

2. Criterio di arresto di Aitken per suc- cessioni lineari:

Hp: x

n

= ϕ(x

n−1

) → α = ϕ(α) Hp: ϕ

⁰

(α) 6= 0, x

n

6= α ∀n

˛

˛ x

n

− x

n+1

x

n−1

− x

²_n

x

n+1

+ x

n−1

− 2x

n

˛

˛ < ε 3. Minimo di f unimodale:

While

x

1

:= a + (1 − r)(b − a) x

2

:= a + r(b − a)

Se f (x

1

) > f (x

2

) : a := x

1

Altrimenti: b := x

2

Se b − a < ε : x

∗

:= a break Integrali

1. Norma kIk =

Z

b a

w(x) dx, kI

n

k =

n

X

i=0

|w

_i

|

2. Formula interpolatoria I

n

: deg I

n

≥ n

|I(f ) − I

_n

(f )| ≤ kf − L

n

k Z

b

a

w(x) dx

w

j

= Z

b

a

w(x)λ

j

(x) dx ∀j = 0, .., n Sistema per il calcolo dei pesi:

Z

b a

w(x)x

ⁱ

dx =

n

X

j=0

w

j

x

ⁱ_j

∀i = 0, .., n

3. Cambio di pesi e nodi:

x

j

, w

j

su [α, β], x

⁰_j

, w

⁰_j

su [a, b]

w

⁰_j

= w

j

b − a β − α x

⁰_j

= b − a

β − α (x

j

− α) + a

4. Newton-Cotes: formula interpolatoria su n + 1 nodi uniformi.

Chiusa

x

0

= a, x

n

= b, h = b − a n , x

i

= a + ih i = 0, .., n Aperta

h = b − a

n + 2 , x

i

= a + (i + 1)h∀i = 0, .., n deg I

n

=

(

n n dispari n + 1 n pari

Resto:

n Chiusa Aperta

0 1

3h3 f (2) (ξ) 1 − 112h3 f (2) (ξ) 3

4h3 f (2) (ξ)

2 − 1

90h5 f (4) (ξ) 14 45h5 f (4) (ξ) 3 − 380h5 f (4) (ξ) 95

144h5 f (4) (ξ) 4 − 8945h7 f (6) (ξ) 41

140h7 f (6) (ξ)

5. Formula dei trapezi

T (f )

^def

= f (a) + f (b) 2 (b − a) w(x) ≡ 1, deg T = 1 Resto: − (b − a)

³

12 f

⁰⁰

(ξ), ξ ∈ [a, b]

Composita, con distibuzione uniforme dei nodi:

C

_N

(f ) = h f (a) + f (b)

2 +

N −1

X

i=1

f (a + ih)

!

x

i

− x

_i−1

= h = b − a N Resto: − b − a

12 h

²

f

⁰⁰

(ξ) Resto di Eulero-MacLaurin:

c

1

h

²

+ c

2

h

⁴

+ · · · + c

k

h

^2k

+ . . .

6. Cavalieri-Simpson (formula interpolatoria)

Nodi x

0

= a, x

1

= a + b 2 , x

2

= b S(f ) = b − a

6 »

f (a) + 4f „ a + b 2

« + f (b)

–

w(x) ≡ 1, deg S = 2

Resto formula composita: − b − a

2880 h

⁴

f

⁽⁴⁾

(ξ) con x

i

− x

_i−1

= h = b − a

N 7. Gauss-Chebyshev:

w(x) ≡ 1

√

1 − x

²

, [a, b] = [−1, 1], deg I

n

= 2n + 1 w

i

= π

n + 1 ∀i = 0, . . . , n x

i

= cos

» 1 n + 1

“ π 2 + iπ ” –

i = 0, . . . , n

8. Estrapolazione di Richardson:

F

1

(f, h) = I

n

(f, h), h < 1 F

_k+1

(f, h) = q

^p^k

F

k

(f, h) − F

k

(f, qh)

q

^p^k

− 1 Per la formula dei trapezi: p

k

= 2k 9. Integrazione adattiva:

IntAdattiva(α, β) : M =: I

n

(α, β) N =: I

_n⁰

(α, β) Se |M − N | < ε

b − a (β − α) I =: N

Altrimenti : I =: IntAdattiva

„ α, α + β

2 « +

+ IntAdattiva „ α + β 2 , β

«

I =: IntAdattiva(a, b)