Riassunto esame, Calcolo Numerico - Tutto l'esame in 30 pagine, prof. Politi

Teorema di rappresentabilità universale

Sia β ∈ ℕ_β > 1 allora ogni numero reale x (x ≠ 0) può essere univocamente rappresentato in base β nel seguente modo:

x = ± β^e∑_i=1^td_iβ^-i

dove {z}_i, t, e ∈ ℕ (detti anche), verifichiamo le seguenti proprietà:

1. d_i ∈ {0, 1, 2, ..., β - 1}
2. t è detto in base β detto aritmetica
3. e deve essere, sono definiti come, uguale o (β - 1), cioè assegno e limito assioma della rappresentazione

Rappresentazione in base β di x:

x ∈ ℝ, x ≠ 0

x = β^P (O, d₁d₂d_k...) dove O, d₁d₂d_k... è detta mantissa (d_k ≠ 0)

L'insieme dei numeri macchina

f(β, t, m_v, M₁)

Siamo β, t, m_v, M ∈ ℕ con β ≥ 2, t ≥ 1, m_v > 0. Si dice, insieme dei numeri macchina con rappresentazione normalizzata in base β con e cifre significative e l'insieme:

f(β, t, m_v, M) = {x ∈ ℝ : x = ± β^f∑_i=0^td_iβ^-i} ∪ {β^f}

dove:

1. t = ≥ 0, β > 1
2. d_i ∈ {0, 1, 2, ..., β - 1}
3. d_j ≠ 0
4. P ∈ ℤ, - m_v ∈ P ≤ M
5. La rappresentazione dello zero segue: è necessario aggiungerlo analiticamente

Rappresentazione nell'elaboratore

• 1 campo di memoria per il segno [___]
• t campi di memoria che possono assumere della mantissa con configurazioni per la memorizzazione
• Campi di memoria per la mem. di p, un totale di parametru m_v+M+1 con configurazioni
• Osservat.: il più piccolo e positivo rappresentabile
• X = o₁ β^-m_v
• il grande ""
• X = o₂ (β - 1) (β^-1)... β^M

Proprietà dei numeri macchina

1. L'insieme è discreto.
2. I numeri rappresentabili sono solo una piccola parte di R.
3. La distanza tra due numeri x₁ consecutivi è β^1-t.

Infatti sia x un numero: x = β^t (0,d₀d₁...d_t-1) Le successive numero macchina sia x̄ = β^t (0,d₀,...d_t-1,(d_t +1)) La differenza pertanto; x̄ - x = β^t(0,0,...0,1) = β^t . 1 . 10 . β^1-t = β^1-t

Standard IEEE di rappresentabilità

Esercizi di rappresentazione

Sia x ∈ R, caratterizzato da una base β_i di segni significati, esponente p. Quale elemento x̄ d f(β,t,m,n) assocni ad x in modo da commettere il minor error?

• Supposto x = β^m ∑ d_i β^-i con d_i ≠ 0 m ≠ t Allora x ∈ f(β,t,m,n) ovvero x = x̄
• Supposto x = β^P ∑ d_i β^-i m ≠ t, ma:
  1. p < -m → x ﻚ più piccolo del più piccolo numero macchina rappresentabile. UNDERFLOW
  2. p > M → x ﻚ più grande del più grande numero macchina rappresentabile. OVERFLOW

Arrotondamento e troncamento

x ≐ x = β^m ∑ d_i β^-i con -w ≤ p ≤ m ma t < m ed esiste un t ≤ K ≤ m tale che d_k ≠ 0 allura x ∈ f(β,t,m,M) Però ha pi evone significative pi prelie previste. Per la rappresentazione di x possiam utilizzere 2 techniche di approssimazione:

1. Arrotondamento di x alla t-esima cigna:

   x̄ = trx(x) = β^x (0,d₀,d₁,...,d_t) dove d_t+1 = t

2. Arrotondamento alla t-esima cigna:

   x̄ = arro(x) = β^x (x,d₀,d_t)

Metodo della falsa posizione

f: [a,b] → ℝ è continua f(a)f(b) ≤ 0

Ad un generico passo si definisce la retta che va dal punto (a_k, f(a_k)) al (b_k, f(b_k)) y = f(a_k) + _{(f(ak) - f(bk)) / (ak - bk)} x - 1 Questo ci pone [a_k, x_k] x_k = b_k - c(x_k se f(a_k)f(x_k)<0 Iterando ↦ convergiamo a α, zero della funzione

Vantaggi:

1. semplicità
2. ipotesi non restrittive

Svantaggi:

1. Il metodo utilizza solo il segno, non il valore della funzione
2. L'errore si riduce di ^1/10 ogni 3,32 iterazioni. È lento!

Metodi di iterazione funzionale

metodi di iterazione funzionale sono del tipo X_n+1 = g(X_n) k = 0,1,...

dove x₀ è un assegnato valore iniziale e forniscono un'approssimazione della soluzione dell'equazione x = g(x)

Il punto fisso di: f(x) ⇔ f(b) = b

Se f: [a₁, b₁] → ℝ, h(x): ℝ → ℝ, h(x) ≠ 0 ∀ x ∈ [a₁, b₁], ponendo:

g(x) = x - ^f(x)/_h'(x) dove ogni punto fisso di g è zero di f e viceversa

Teorema:

g ∈ C([a_k, b₁]) X_n+1 = g(X_n), {x_k} ⊂ [a,b],

Se {x_k} converge α è punto fisso di g.

dimo_str.

d = lim X_n+1 = lim_k→∞ g(X_n) = lim_k→∞ g(x)

Teorema:

d punto fisso di g, g ∈ C([d-p, i+p]) p > 0, Scelto x₀ t.c.: |x₀ - d| ≤ p

per la successione {X_n]_k=0 sì, ha che |g'(x) < 1| per |x - d| ≤ p, per ogni k, e {X_k} converge a d.

Metodo di Newton-Raphson direzione costante

Se applicando ripetutamente (Newton-Raphson) f’(x) si mantiene costante allora si può porre: M = f’(x) e il metodo diviene: x_k+1 = x_k - f(x_k)/M Iterato: g(x) = x - f(x)/M

Il metodo è convergente se \( |x - \frac{f(x)}{M}| < 1 \) da cui si deduce che è necessario che M e f(x) abbiano stesso segno.

Vantaggi (rispetto Newton-Raphson)

Svantaggi: 1. La convezione è più lenta

Metodo della secante

Il metodo è definito dalla relazione: x_k+1 = x_k - f(x_k)(x_n - c) / (f’(x_k) - f(c))

Newton a doppio passo (solo per polinomi)

Polinomio \( p(x) = \sum_{i=0}^{m} a_i x^i; \ a_i \in \mathbb{R} \ \forall \ i ; \ m \geq 1 \)

Sia \(\{ \ d_1, d_2, ..., d_m \ \} \)

Schema iterativo di Newton: x_k+1 = x_k - p(x_k) / p’(x_k) \hspace{20px} k = 0,1,2,...

Teorema: in una situazione generica descritta il metodo di Newton genera una successione \( \{\ x_k \ \}\ \\ \) decrescente di approssimazioni convergente verso Per \( m \geq 2 \) la successione delle \( \ x_k \ \) è strettamente monotona decrescente.

Tuttavia, scelto un \( \ x_0 \ \) molto lontano da \ a_1 \ \ il metodo procede molto lentamente. Per \ x₀ molto grande infatti:

\[ x_k+1 = x_k - \frac{a_0 x_k}{m a_m x^{m-1}_1} \ \cong x_k ( 1 - \frac{1}{m} ) \]

Per tale ragione è utile il metodo di Newton a doppio passo, definito: \[ x_k+1 = x_k - 2 P_i (x_k) \hspace{20px} K=0,1,2,...? \] \[ p’(x_k) \]

Questo metodo NON converge ad a₁ ma può essere usato solo per avvicinarsi a d_1. Tuttavia, per un certo indice m accade che: \[ P(x_j)P(x_j - 1){x_j > 0} \ \ \ j = 1, 2, ..., m-1 \] \[ P(x_m) P(x_m - 1) < 0 \]

e questo vuol dire che \ ( x_m < a_1 < x_{sm.2.} \ \ \ x_1 \ = x-0. Caril \ si dimostra che \( \ x_m\ \) può scavalcando i normali scavalo il punto \ ( x \ comprresso tra x_m \ ed x_m-2.

Tale che \( P(x_j) = 0 \).

La successione \(\ \{x_k\}\) così ottenuta converge ad a_1.