Appunti esame: Calcolo numerico

CALCOLO NUMERICO

Nel calcolo numerico siamo interessati all'accuratezza dei dati, questo perché in calcolatore elettronico opera mediante l'aritmetica di precisione finita.

Errore assoluto: sia x ∈ ℝ e x̄ ∈ ℝ un'approssimazione di x.

_ea = |x - x̄| (errore sempre positivo, al più nullo)

Dipende dall'ordine di grandezza dei dati

Errore relativo: _er = |x - x̄| / |x|, x ≠ 0

Nella pratica, in generale, _ea e _er non sono noti, dato che non conosciamo x ma solo x̄.

Sarà necessario trovare delle limitazioni superiori all'errore relativo (o assoluto).

• Es₁: x = 10000, x̄ = 10001, _er < 10^-4 se è più accurato
• x = 10, x̄ = 11, _er > 10^-1

Rappresentazione in virgola mobile normalizzata dei numeri reali (floating point): β-base del sistema di numerazione

x ∈ ℝ, x = ±0.a₁a₂ ... a_nβ^j, a₁ ≠ 0

• β ∈ { 2, 3, ... } e a_i ∈ { 0, 1, ..., β-1}
• mantissa caratteristica
• Standard per definire unicamente un numero reale

Es₂: x = 25.35 = 0.2535·10² = 253.2·10^-1

rappresentazione floating point

Es₃: x = 58594 = 0.58594·10⁵

- 58590 = 0.58590·10⁵ 4 cifre esatte

- 58594 ≠ 7·10⁵ < 10⁴

Es₄: x = 10000

x̄ = 9999

0 cifre esatte

_er = 1 / 10000 = 10^-4

Cifre significative: siano x e x̄ espressi in virgola mobile normalizzata. Allora se _er = |x - x̄| / |x| ≤ 10^-k,

• k ∈ ℤ
• x̄ ha almeno k cifre significative (certe o altrimenti esatte)

Es x = 0,42563

e_r = 4.10^-3 < 10^-2 → x ha 2 cifre significative

Norme di vettori:

||x||₂ x ∈ ℝⁿ = √x_i = √∑_i=1ⁿx_i²

Una norma in ℝⁿ

• ||x||:ℝⁿ→ℝ che associa ad ogni x ∈ ℝⁿ un numero ||x|| tale che:
• 1) ||x|| ≥ 0 ∀ x ∈ ℝⁿ
• ||x|| = 0 ↔ x = 0 vectore nullo → x_i = 0, i = 1, ..., n
• 2) ||α x|| = |α| · ||x|| ∀ α ∈ ℝ ∀ x ∈ ℝⁿ
• 3) ||x + y|| ≤ ||x|| + ||y|| ∀ x, y ∈ ℝⁿ, disuguaglianza triangolare

sono proprietà naturali quando si vuole misurare una lunghezza

• 1) sempre positiva e si annulla solo quando il vettore è nullo
• 2) una lunghezza di un vettore doppio è il doppio di quella di partenza
• 3) la lunghezza di un lato non può essere maggiore della somma degli altri due (in un triangolo)

La norma 2 (euclidea) definita come ||x||₂ = (∑_i=1ⁿ x_i² )^1/2 soddisfa le 3 proprietà

Norma p, p ∈ ℤ, p ≥ 1: ||x||_p = (∑_i=1ⁿ |x_i|^p)^1/p |(x₁, x₂, ..., x_n)|^p)^1/p

x = (x₁, x₂, ..., x_n) oppure

p > 1 la funzione ||· ||₂: ℝⁿ → ℝ è una norma su ℝⁿ

Norme più usate:

• p = 1, ||x||₁ = ∑_i=1ⁿ |x_i|
• p = 2, ||x||₂ = √ ∑_i=1ⁿ x_i²
• p = ∞ ||x||_∞ = lim_{p → ∞} ||x||_p lim_{p → ∞} (∑_i=1ⁿ |x_i|^p)^1/p = max |x_i| i : 1, 2, ..., n

Boccia: (insieme dei vettori la cui norma è uguale a un numero)

Norma 2: n - 1 somme

n prodotti

1 radice quadrata

la più costosa

Norma 1: n - 1 somme, la meno costosa

Norma ∞: n - 1 confronti

Algoritmo del prodotto:

dati n numeri a₁,...,a_n calcola S=∏a_i

• S=1
• for i=1,...,n
• S=S*a_i

Algoritmo del massimo:

dati a₁,...,a_n calcola M=max a_i

• M=a₁
• for i=2,...,n
• if M<a_i
• M=a_i

Con M=0 l'algoritmo si potrebbe applicare a vettori non negativi, l'algoritmo sarebbe non generale, cioè non applicabile a tutta una classe di problemi.

Algoritmo per ||A||₁=max ∑|a_ij|:

• M=0
• for j=1,...,n
• S=0
• for i=1,...,n
• S=S+|a_ij|
• if M<S
• M=S

Algoritmo del prodotto matrice-vettore:

dati A∈ℝ^m×n, x∈ℝⁿ calcolare y=A*x

• for i=1,...,m
• S=0
• for j=1,...,n
• S=S+a_ij*x_j
• y_i=S

Mantissa per gli standard IEEE:

1) Precisione semplice:

• ho a disposizione m = 23 bit per la mantissa. Tuttavia il primo bit è sempre uguale a 1 (bit noto, bit fantasma).
• si guadagna un bit (24 cifre in tutto).

Tecnica di approssimazione: "rounding to even"

• E_s, β = 2, m = 6
• • 0.101001₁ · 2² → 0.101010 · 2² rounding=round to even
  • 0.101001₂ · 2² → 0.101000 · 2² rounding=round to even pari (quindi si lascia così)
• Anche per il rounding to even, ε_s = 1, β^–m + 1 · 2^–24 = 2^–24 ≈ 5.96 · 10^–8

2) Precisione doppia:

• ε_n–1/2^–53 = 2^–53 ≈ 1.1 · 10^–16

Operazioni in macchina:

• Somma algebrica fra due numeri reali: x ⊕ y, x ⊗ y
• • L₁ si trasforma il numero con caratteristica minore in modo che le caratteristiche dei due numeri coincidano (uno dei due perderà la forma in virgola mobile normalizzata).
  • L₂ si sommano le mantisse.
  • L'operazione di floating del risultato (si normalizza il risultato e lo si tronca/arrotonda ove necessario).

E₅

• β = 10, m = 5, arrotondamento
• x = 0.64937 · 10⁵
• y = 0.53726 · 10⁴
• L₁(x) = 0.64937 · 10⁵
• L₁(y) = 0.53726 · 10⁴
• 0.64937(0.0053726) · 10^[0.00053726] = 0.64985276 · 10⁵ → 0.64986 · 10⁵ arrotondamento

E₅

• β = 10, m = 5, arrotondamento
• x = 0.64937 · 10⁵
• y = 0.53726 · 10⁴
• x ⊕ y = 1.18663 · 10⁵ ≈ 0.118663 · 10⁻⁸ = 0.11863 · 10² arrotondamento

E₅

• β = 10, m = 4, troncamento
• x = ∗10^* · 0.1000 · 10⁰
• y = 0.00054

Esempio

(x-1)⁴ = 0   x=1 radice con molteplicità 4

(x-1)⁴ - 10^-8

x = 1 ± 10^-2; 1 ± i10^-2

ε_r| x | _{= 1} = 10^-2

ε_x > 10^-1; 0.1 - 0.1 (perturbazione su dati)

ε_x > ε_r Il problema è mal condizionato

Sistemi Lineari

A x = b   A ∈ ℝ^nxn   b ∈ ℝⁿ   det(A) ≠ 0 ⇒ A x = b ammette una ed una sola

         soluzione x = A^-1 b

• Perturbazione alla soluzione

A (x + δx) = b + δb

• Perturbazione su dati

A = ^(835 667)_(333 266)   b = ⁽¹⁶⁸⁾₍₆₇₎

b + δb = ⁽¹⁶⁸⁾₍₆₆₎

∣∣b - (b + δb)∣∣∞  =  ∣∣(1)

∣∣b∣∣∞    (1)

≥ 168

x = A^-1b = ⁽¹⁾_(-1)

x + δx = A^-1(b + δb) = ^(-666)₍₈₃₄₎

∣∣x - (x + δx)∣∣∞  = 835 ≥ 835

∣∣x∣∣∞         1

≥ 1 Il problema è mal condizionato

Vogliamo trovare una relazione tra

∣∣x - (x + δx)∣∣^{⇒   ∣∣b - (b + δb)∣∣}_{∣∣x∣∣     ∣∣b∣∣}

Non è nota in generale

Teorema (Condizionamento di un sistema lineare)

Si consideri A x = b sistema lineare con A ∈ ℝ^nxn b ∈ ℝⁿ det(A)≠0

Si consideri il sistema perturbato A (x + δx) = b + δb Allora,

∣∣∣Δx∣∣∣≤ κ(A) ∣∣∣A^-1∣∣∣∣∣∣∣Δb∣∣∣  Δ sulla soluzione

∣∣∣x | x∣∣∣ ε_x su dati

dove ∣∣∣. nel caso, qualsiasi norma vattoriale sia che consideri un vettore, mentre indica la norma matriciale indotta e applicata ad una matrice

Numero di condizionamento: κ(A)   ≥ κ(A) ≥1 ∀ A ∈ ℝ^nxn