Struttura dell'Esame Scritto

Indicativamente, l'esame scritto conterrà:

• Un esercizio di modellazione
• Due/tre esercizi di
  • Analisi di codice, codifica di algoritmi noti, esecuzione di algoritmi, rappresentazione dei numeri
• Alcune domande di teoria brevi

Sono possibili (ma improbabili) variazioni

• Il tempo disponibile sarà di due ore
• Il punteggio massimo sarà superiore a 30...
• Quindi si può superare l'esame a pieni voti anche con alcuni errori

Elementi di Informatica e
Applicazioni Numeriche T

Esercizio 1 (modellazione)

Esercizio 1

Si vuole progettare parte di un circuito automobilistico:

• Il tratto deve essere descrivibile con una curva polinomiale
• Il tratto deve passare per i punti $a, b, c$
• La posizione di $a, b, c$ è nota
• La tangente in $b$ deve essere orientata secondo la freccia rossa

Esercizio 1

Si considerino i seguenti problemi:

• Q1: Come si può ottenere l'equazione del circuito?
• Q2: Come si può calcolare la lunghezza del tratto?
• Q3: Sia $d$ un terzo punto sulla curva
  • Per quali coordinate di $d$ la distanza tra $a$ e $d$...
  • ...È pari ad un dato valore $\lambda$?

NOTA: La domanda Q3 è tendenzialmente la più complessa

• Non spaventatevi: ragionate più che potete
• Non è necessario fare un compito perfetto per avere 30!

Soluzione (Q1)

Innanzitutto ci serve un sistema di riferimento:

A questo punto possiamo riferirci alle posizioni di $a, b, c$ con:

$$\begin{align} & a \leftrightarrow (x_a, y_a) & & b \leftrightarrow (x_b, y_b) & & c \leftrightarrow (x_c, y_c) & \end{align}$$

Soluzione (Q1)

La curva è descritta da una funzione polinomiale:

$$\begin{align} & f_\beta(x) = \sum_{j = 0}^n \beta_j x^{(n-j)} \end{align}$$

Possiamo determinare i coefficienti risolvendo:

$$\begin{align} & f_\beta(x_a) = y_a \\ & f_\beta(x_b) = y_b \\ & f_\beta(x_c) = y_c \\ & f_\beta'(x_b) = 0 \end{align}$$

• Ci sono 4 equazioni, quindi $f$ deve essere almeno di 3° grado
• Il sistema è lineare in $\beta$

Soluzione (Q1)

Poiché $f$ è di 4° grado, posso scrivere:

$$f_\beta(x) = \beta_0 x^3 + \beta_1 x^2 + \beta_2 x + \beta_3$$

Mentre la derivata è data da:

$$f_\beta'(x) = 3\,\beta_0 x^2 + 2\,\beta_1 x + \beta_2$$

NOTA: $\beta$ è il vettore dei coefficienti

• Li consideriamo come parametri
• Di fatto, sono delle variabili, ma variabili "secondarie"
• Di solito, le variabili principali (e.g. $x$) vanno tra parentesi...
• ...Ed i parametri si riportano a pedice

Soluzione (Q1)

Poiché $f$ è di 4° grado, posso scrivere:

$$f_\beta(x) = \beta_0 x^3 + \beta_1 x^2 + \beta_2 x + \beta_3$$

Mentre la derivata è data da:

$$f_\beta'(x) = 3\,\beta_0 x^2 + 2\,\beta_1 x + \beta_2$$

NOTA 2: D'ora in avanti, i parametri $\beta$ saranno fissi:

• Per semplicità, li possiamo omettere
• Quindi possiamo scrivere semplicemente $f(x), f'(x)$
• Quando si fa un cambio di notazione, bisogna indicarlo

Soluzione (Q2)

La lunghezza della curva è data da:

$$L = \int_{x_a}^{x_c} \sqrt{1 + f'(x)^2} dx$$

Dove $\sqrt{1 + f'(x)^2} dx$ corrisponde a:

• La lunghezza di un segmento infinitesimo...
• ...Orientato secondo la tangente

Soluzione (Q3)

Definisco una funzione $L(x)$ che corrisponde a:

$$L(x) = \int_{x_a}^{x} \sqrt{1 + f'(x)^2} dx$$

La coordinata $x_d$ del punto $d$ è determinata risolvendo:

$$L(x) = \lambda$$

• Si può usare il metodo della bisezione o quello di Newton-Raphson
• La derivata può essere approssimata numericamente

La coordinata $y_d$ del punto $d$ è ora data da:

$$y_d = f(x_d)$$

Elementi di Informatica e
Applicazioni Numeriche T

Esercizio 2 (modellazione)

Esercizio 2

Un'automobile avanza a motore spento su un rettilineo:

• L'auto ha una velocità iniziale $v_0$
• L'auto è soggetta alla forza di attrito aerodinamico, data da: $$F_d = \frac{1}{2}\rho v^2 C_D A$$
  • $v$ è la velocità dell'auto
  • $\rho, A, C_D$ sono parametri noti
• Fintanto che avanza, l'auto è soggetta all'attrito volvente delle ruote: $$F_r = C_r m g$$
  • $C_r$ è un coefficiente di attrito volvente (noto)
  • $m$ è la massa dell'automobile (nota)
  • $g$ è l'accelerazione di gravità

Esercizio 2

Si considerino i seguenti problemi:

• Q1: Come varia la velocità dell'auto nel tempo?
• Q2: Dopo quanta strada l'auto si ferma?
• Q3: Che massa deve avere l'auto per arrestarsi in una distanza $\lambda$?

NOTA: La domanda Q3 è tendenzialmente la più complessa

• Non spaventatevi: ragionate più che potete
• Non è necessario fare un compito perfetto per avere 30!

Soluzione (Q1)

Innanzitutto dobbiamo capire come descrivere lo stato:

Ci interessa la velocità dell'auto, su un rettilineo:

• Possiamo descrivere la velocità con uno scalare $v$

Le forze che agiscono sull'auto determinano $\dot{v}$:

• Quindi possiamo descrivere il sistema con una EDO:
• In prima approssimazione potremmo scrivere:

$$\dot{v} = - \frac{1}{m} (F_d + F_r)$$

• C'è però una particolarità importante...

Soluzione (Q1)

L'attrito volvente delle ruote è attivo solo finché l'auto si muove:

• Quindi l'equazione precedente va modificata:

$$\begin{align} &\dot{v} = - \frac{1}{m} (F_d + \hat{F}_r) & \text{con: } & \hat{F}_r = \left\{\begin{aligned} & F_r && \text{se } v > 0\\ & 0 && \text{altrimenti} \end{aligned}\right. \end{align}$$

Possiamo risolverla con un metodo numerico per $v(0) = v_0$

• Poiché usiamo un metodo numerico...
• ...La presenza di due case in $\hat{F}_r$ non è un problema!
  • Ci basta usare un "if"
• La soluzione è il valore di $v(t)$, per valori di $t$ selezionabili
• La soluzione della EDO risponde a Q1

Soluzione (Q2)

Per rispondere a Q2 abbiamo bisogno della posizione dell'auto:

• Siamo su un rettilineo: quindi possiamo usare uno scalare $x$
• Assumiamo che la posizione iniziale sia $0$
• La velocità corrisponde a $\dot{x}$

Quindi, includendo la posizione, il sistema è definito da:

$$\begin{align} & \dot{x} = v \\ & \dot{v} = - \frac{1}{m} (F_d + \hat{F}_r) \end{align}$$

• Da risolvere per $v(0) = v_0, x(0) = 0$
• La soluzione sono i valori di $x(t), v(t)$, per valori di $t$ selezionabili

Soluzione (Q2)

Per rispondere al quesito 2:

• Determiniamo il primo valore di $t^*$ tale che $v(t^*) \simeq 0$
• Approssimiamo il valore di $x(t^*)$ (e.g. interpolazione lineare)
• Il valore di $x(t^*)$ risponde al quesito

Soluzione (Q3)

Per risponere a Q3, consideriamo la massa $m$ come un parametro

• Siano $x_m(t), v_m(t)$ le soluzioni della EDO...
• ...per un dato valore di $m$
• Possono essere calcolate come nel caso precedente

A questo punto, per rispondere a Q3 dobbiamo risolvere:

$$\begin{align} & x_m(t) = \lambda \\ & v_m(t) = 0 \end{align}$$

• Il sistema va risolto in $t$ e $m$ (vanno determinate entrambe)
• In teoria si potrebbe usare il metodo di Newton-Raphson...
• ...in pratica è meglio un approccio diverso (vedere prossima slide)

Soluzione (Q3)

In pratica, per rispondere a Q2 abbiamo visto come ottenere:

• Un valore $t^*$ tale che $v(t^*) \simeq 0$
• Ed il valore di $x$ corrispondente a $t^*$

Possiamo incapsulare questo calcolo in una funzione $G(m)$

• Dato un valore di massa $m$...
• ...$G(m)$ trova $t^*$ e denota $x(t^*)$

A questo punto dobbiamo risolvere solo una equzione:

$$G(m) = \lambda$$

• E questo può essere fatto tranquillamente con il metodo di Newton

Elementi di Informatica e
Applicazioni Numeriche T

Esercizio 3 (Analisi)

Esercizio 3

Si consideri lo script seguente:

function y = f(x)
    y(1, :) = x(2:2:end);
    y(2, :) = x(1:2:end);
end

y = f([1, 2, 3, 4])
z = y(1, :) + y(2, :)
w = sum(z)

• Che cosa stampa?
• Si motivi (intuitivamente) la risposta

Soluzione

function y = f(x)
    y(1, :) = x(2:2:end);
    y(2, :) = x(1:2:end);
end
% y(1, :) contiene i valori di x in posizione pari
% y(2, :) contiene i valori di x in posizione dispari
% quindi; y = [2, 4;
%              1, 3]
y = f([1, 2, 3, 4])
% Sommando le due righe di y abbiamo z = [3, 7]
z = y(1, :) + y(2, :)
% w contiene la somma di tutti i valori in x: w = 10
w = sum(z)

Elementi di Informatica e
Applicazioni Numeriche T

Esercizio 4 (codifica)

Esercizio 4

Si codifichi la funzione:

function x = eulero(f, x0, t)

Che risolve una EDO con il metodo di Eulero.

• f è una funzione che calcola la derivata dello stato corrente:

  function  dx = f(x, t)
  

  • x è lo stato (uno scalare), t è l'istante di tempo corrente
• x0 è il valore iniziale dello stato (uno scalare)
• t è il vettore dei tempi per cui va determinato lo stato

Si discuta brevemente il metodo

Soluzione

Il metodo di Eulero risolve una EDO in base all'iterazione fondamentale:

$$x^{(k+1)} = x^{(k)} + (t^{(k+1)} - t^{(k)})\, f(x^{(k)}, t^{(k)})$$

Una possibile codifica:

function x = eulero(f, x0, t)
    x(1) = x0;
    for ii = 1:length(t)-1
        dt = t(ii+1) - t(ii);
        x(ii+1) = x(ii) + dt .* f(x(ii), t(ii));
    end
end

Elementi di Informatica e
Applicazioni Numeriche T

Esercizio 5 (codifica)

Esercizio 5

Si discuta brevemente il metodo di Newton-Raphson e si codifichi:

function x = newton_raphson(f, df, x0)

Ossia una funzione che esegue il metodo. I parametri sono:

• f è la funzione (scalare) da annullare:

  function  y = f(x)
  

• df è una funzione che calcola la derivata di f

  function  y = df(x)
  

• x0 è valore di x da cui partire

Soluzione

Il metodo di Newton-Raphson trova lo zero di una funzione:

• Utilizzando ripetutamente una approssimazione lineare
• Da cui si deriva l'iterazione fondamentale:

$$x^{(k+1)} = x^{(k)} - \frac{f(x^{(k)})}{f'(x^{(k)})}$$

Soluzione

Una possibile codifica:

function x = newton_raphson(f, df, x0)
    for ii = 1:1000
        x_old = x0;
        x = x_old - f(x_old) ./ df(x_old);
        if abs(x - x_old) < 1e-5
            break
        end
    end
end

• Il numero massimo di iterazioni è stato posto a 1000
• La convergenza è verificata sul valore di x
• È stata usata una tolleranza di $10^{-5}$

Elementi di Informatica e
Applicazioni Numeriche T

Esercizio 6 (Rappresentazione dei Numeri)

Esercizio 6

Un calcolatore rappresenta i numeri in virgola mobile utilizzando:

• Una rappresentazione in base 10 (per semplicità)
• Mantisse normalizzate in modo che la parte intera sia sempre 0
• Tre cifre decimali per la mantissa
• Una cifra decimale per l'esponente

Si calcoli il risultato delle somme:

$$\begin{align} & 0.122\times10^{-1} + 0.430\times10^{-2} \\ & 0.120\times10^{-1} + 0.432\times10^{-2} \\ \end{align}$$

Si evidenzino eventuali errori di cancellazione

Soluzione

• Per sommare i numeri, gli esponenti devono essere resi identici
• Le mantisse devono rimanere normalizzate
• Quindi ci si riduce sempre all'esponente più grande

Consideriamo la prima somma:

$$0.122\times10^{-1} + 0.430\times10^{-2}$$

• Uguagliando gli esponenti si ottiene:

$$0.122\times10^{-1} + 0.043\times10^{-1} = 0.165\times10^{-1}$$

• Il risultato è esatto

Soluzione

• Per sommare i numeri, gli esponenti devono essere resi identici
• Le mantisse devono rimanere normalizzate
• Quindi ci si riduce sempre all'esponente più grande

Consideriamo la seconda somma:

$$0.120\times10^{-1} + 0.432\times10^{-2}$$

• Uguagliando gli esponenti si ottiene:

$$0.120\times10^{-1} + 0.043\times10^{-1} = 0.163\times10^{-1}$$

• Una cifra del secondo termine è stata cancellata
• Il risultato corretto sarebbe $0.1632\times10^{-1}$

Elementi di Informatica e
Applicazioni Numeriche T

Esercizio 7 (Rappresentazione dei Numeri)

Esercizio 7

Un calcolatore rappresenta i numeri in virgola mobile utilizzando:

• Una rappresentazione in base 10 (per semplicità)
• Mantisse normalizzate in modo che la parte intera sia sempre 0
• Quattro cifre decimali per la mantissa
• Una cifra decimale per l'esponente

Si calcoli il risultato delle somme:

$$\begin{align} & 0.0702\times10^{4} + 0.1001\times10^{2} \\ & 0.0702\times10^{4} + 0.0085\times10^{2} \\ \end{align}$$

Si evidenzino eventuali errori di cancellazione

Soluzione

• Per sommare i numeri, gli esponenti devono essere resi identici
• Le mantisse devono rimanere normalizzate
• Quindi ci si riduce sempre all'esponente più grande

Consideriamo la prima somma:

$$0.0702\times10^{4} + 0.1001\times10^{2}$$

• Uguagliando gli esponenti si ottiene:

$$0.0702\times10^{4} + 0.0010\times10^{4} = 0.0712\times10^{4}$$

• C'è un errore di cancellazione
• Il risultato corretto è $0.071201\times10^{4}$

Soluzione

• Per sommare i numeri, gli esponenti devono essere resi identici
• Le mantisse devono rimanere normalizzate
• Quindi ci si riduce sempre all'esponente più grande

Consideriamo la seconda somma:

$$0.0702\times10^{4} + 0.0085\times10^{2}$$

• Uguagliando gli esponenti si ottiene:

$$0.0702\times10^{4} + 0.0000\times10^{4} = 0.0702\times10^{4}$$

• C'è un errore di cancellazione
• Il risultato corretto è $0.070285\times10^{4}$