Fondamenti di informatica T - domande e risposte

Domande teoriche

Cose da sapere

Per determinare la funzione f, quando le nostre misure sono in numero elevato (m >> 1), si usa il metodo dei minimi quadrati per la ricerca dei coefficienti di un polinomio di grado g < 2m, perché quando m è molto grande, il polinomio è oscillante.

La rappresentazione del numero reale 1254,3 in virgola mobile normalizzata è 0,12543 * 10⁴. Motivazione: ogni numero reale "a" può essere scritto nella forma a = p * N^q dove p è un numero reale, "N" la base del sistema di numerazione scelto e q è un intero positivo, negativo o nullo. La rappresentazione di a ≠ 0 si dice normalizzata quando N^-1 ≤ |p| < 1 (esempio con base 10 → 10^-2 ≤ |p| < 1) ossia quando la prima cifra di p (dopo il punto decimale) è diversa da zero.

Possibile ampliamento matrice caratteri e massimale (omissis)

La norma due/norma spettrale di una matrice quadrata è

√(MAX(ABS(EIG(A^T*A))))

Motivazione: A è una qualunque matrice quadrata. A^T è la matrice trasposta di A, ottenuta scambiando le righe con le colonne. A^T*A è il prodotto delle due matrici (se sono quadrate sono compatibili). EIG(A^T*A) ci dà gli autovalori. ABS(EIG(A^T*A)) ci dà gli autovalori in valore assoluto. MAX(ABS(EIG(A^T*A))) ci dà il massimo degli autovalori presi in valore assoluto. SQRT è il comando per la radice quadrata.

Il raggio spettrale di una matrice quadrata è MAX(ABS(EIG(A))). Motivazione: il raggio spettrale di una matrice quadrata A è il massimo degli autovalori di A presi in valore assoluto. In MATLAB, il comando EIG(A) calcola gli autovalori di A, il comando ABS(EIG(A)) individua i valori assoluti degli autovalori di A, e il comando MAX(ABS(EIG(A))) individua il massimo tra i valori assoluti degli autovalori di A.

La cancellazione numerica avviene quando si fa la sottrazione tra due numeri simili. Motivazione: a = 0, b = 0, |a-b| = 10^q. Il computer non lo vede così, ma così: |a-b| = 10^m. C'è una perdita d'informazione.

Per applicare il metodo di bisezione occorre che f(a)f(b) < 0 e che la funzione sia continua. Motivazione: avere agli estremi due segni diversi ci garantisce che la funzione intersechi l'asse x in quell'intervallo e che abbia almeno una radice. L'ipotesi di funzione continua ci evita i casi in cui ci sia un "sacco" della funzione, e che l'asse x venga effettivamente intersecata.

Ricavare il numero di condizionamento di una matrice a partire dalla perturbazione del termine noto, ma non della matrice:

• Ax = b sistema lineare non omogeneo
• C'è il problema numerico esatto A(x+δx) = b+δb problema numerico perturbato
• ASx = δb
• detA ≠ 0
• ∃! Sx
• Sx = A^-1 δb
• Passo in norma associata ‖Sx‖ = ‖A^-1 δb‖
• Teorema: ‖Sx‖ = ‖A^-1δb‖ ≤ ‖A^-1‖‖δb‖
• Passo alla norma relativa ‖Sx‖/‖Ax‖ ≤ ‖A^-1‖‖δb‖/‖b‖ ⇒ ‖Sx‖/‖x‖ ≤ ‖A‖‖A^-1‖‖δb‖/‖b‖ K(A)

Stabilire il range del numero di condizionamento

K(A) = ‖A‖‖A^-1‖ ≥ 1. Se K(A) > 1 il problema è ben condizionato, mentre se K(A) >> 1 il problema è mal condizionato.

Formula di Simpson ripetuta in funzione di a, b, M:

a = x₁
b = x_m+1
M = numero di intervalli
h = (b - a)/M
x_i = a + ((b - a)/M)(i - 1)
i = 1, 2, 3, .... , m + 1

I = ∫_a^bf(x) dx = ∑_i=1^MI_i

I ≈ (b - a)/(6M) { f(a) + f(b) + ∑_i=2^M2f(a + ((b - a)/M)(i - 1)) + ∑_i=1^M+14f(a + ((b - a)/M)(i - 1) + (b - a)/(2M))}

Calcolare EPS (precisione di macchina)

Attraverso metodi di arrotondamento conosciuti:

Sia a = p · N^q un numero reale e sia a^* = p* · N^q il corrispondente numero di macchina ottenuto mediante una delle due tecniche di arrotondamento. Poiché: | p - p* | ≤ N^−ε tronca...

FORMULA DI SIMPSON RIPETUTA IN FUNZIONE DI a, b, M

a = x₁

b = x_m+1

M = Numero di intervalli

h = (b - a)/M

x_i = a + (b - a)/M(i - 1)

i = 1, 2, 3, .... , m + 1

I = ∫_a^bf(x) dx = ∑_i=1^MI_i

I = (x₂ - a)/6 [f(a) + 4f((a + x₂)/2) + f(x₂)] ++ (x₃ - x₂)/6 [f(x₂) + 4f((x₂ + x₃)/2) + f(x₃)] + ... ++ (b - x_m)/6 [f(x_m) + 4f((b + x_m)/2) + f(b)] ==

(b - a)/6M { f(a) + ∑_i=2^M2f(x_i) + ∑_i=1^M+14f((x_i + x_i+1)/2) + f(b)}

Se non si mette anche la fortuca di Simpson con la sommatoria (l'ultimo passaggio) non si ottiene il massimo del punteggio.

Calcolare EPS (precisione di macchina)

Attraverso metodi di arrotondamento conosciuti:

• Sia a = p · N^q un numero reale e sia a^* = p* · N^q il corrispondente numero di macchina ottenuto mediante una delle due tecniche di arrotondamento. Poiché: | p - p* | ≤ N^−ε
• Troncamento: 1/2 N^−ε arrotondamento
• Per gli errori, assoluto e relativo, associati ad a^* abbiamo:
• | a - a^* | ≤ N^q−ε (1/2 N^q−ε)
• | a - a^* | / |a| ≤ ρN^q−ε (1/2 N^q−ε / p N^q)

La quantità EPS = N^1−ε nel primo caso ed EPS = 1/2 N^1−ε nel secondo, definiscono la precisione di macchina.

Fare uno script che calcoli EPS

Format long

Epsilon=1

While (1+epsilon)>1

Epsilon=epsilon/2;

End

EPS = 2*Epsilon

Metodo iterativo di Newton

Si parte dalla formula di Taylor:

• f(x) = f(x₀) + f'(x₀)(x-x₀) + f''(x₀)(x-x₀)² / 2!
• Si linearizza: f(x) = f(x₀) + f'(x₀)(x-x₀)
• Ricerca dello zero: f(x) = 0
• f(x₀) + f'(x₀)(x₁-x₀) = 0 ⇒ (x₁-x₀) = - f(x₀) / f'(x₀)

Allo step m:

x₀ = x_m

x₁ = x_m+1

⇒ x_m+1 = x_m - f(x_m) / f'(x_m)

Dire se le funzioni sono calcolabili esattamente

I = ∫_a^b f(x) dx ≈ _i=1^N Σ w_i f(x_i) = Ǐ

Per la formula di Simpson, il grado di precisione è N-1, quindi tale formula fornisce risultati esatti per polinomi di grado minore o uguale a N-1.

• Esempio: f(x) = x + sen(x) non è calcolabile esattamente. Motivazione: f(x) non è un polinomio, è presente il sen(x)
• Esempio: f(x) = x³ + 2x con Ǐ = _i=1⁴ Σ w_i f(x_i) è calcolabile esattamente. Motivazione: Il grado di precisione è N-1, quindi in questo caso 4-1=3; la formula fornisce risultati esatti per polinomi di grado ≤ 3
• Esempio: f(x) = x⁴ + 3x² + x con Ǐ = _i=1⁵ Σ w_i f(x_i) è calcolabile esattamente. Motivazione: Il grado di precisione è N-1, quindi in questo caso 5-1=4; la formula restituisce risultati esatti per polinomi di grado ≤ 4
• Esempio: f(x) = ln x + 3x² + e^x non è calcolabile esattamente. Motivazione: f(x) non è un polinomio; è presente il logaritmo e un esponenziale
• Esempio: f(x) = x⁴ + cos x non è calcolabile esattamente. Motivazione: f(x) non è un polinomio, è presente il coseno

Metodo punto fisso (fare lo script)

f(x)=0   ln x + x = 0

Strada sbagliata: ln x + x = 0ln x + 2x = -xg(x) = 1/x + 2 > 1   NON ACCETTABILE

Strada accettabile: ln x + x = 0 -ln x = xg^'(x) = -1/x < 1   MA NON POSITIVO

(QUESTO COMPORTA CHE LA FUNZIONE È OSCILLANTE)

Strada migliore: ln x + x = 0 ln x - x = -2x ln x - x/2 = -x x - ln x/2 = xg(x) g^'(x) = 1/2 (1 - 1/x) < 1   ACCETTABILE

g^'(x) positivo e sempre minore di 1

Function della doppia passata

Function dei minimi quadrati

Trovare un polinomio di terzo grado che approssima i punti nell'intervallo [0,5]:

• (x₁, y₁) = (0, 16)
• (x₂, y₂) = (1, 25)
• (x₃, y₃) = (3, 32)
• (x₄, y₄) = (4, 29)
• (x₅, y₅) = (5, 12)

Fare un grafico mostrando l'andamento del numero di condizionamento di una matrice di Vandermonde al variare di M da 2 a 20, sapendo che:

• V(i, j) = x(i)^(j-1) con _{i, j = 1,...,m}
• Con _{m = 2,...,20}

Usare i minimi quadrati per trovare un polinomio di terzo grado nell'intervallo [-5,12] usando i seguenti punti:

• (x₁, y₁) = (-5,1)
• (x₂, y₂) = (0,-2)
• (x₃, y₃) = (2,-3)
• (x₄, y₄) = (4,8)
• (x₅, y₅) = (10,12)

Trovare il valore di X e il numero di iterazioni a convergenza usando Jacobi, sapendo che:

x_old = (0 0 0 0)^T

ERR = 10^-5