Octave: Zeri di Funzioni

Octave offre due metodi per trovare gli zeri di una funzione:

Metodo 1: La funzione

[X, FVAL, INFO] = fzero(FUN, X0)

Trova uno zero per una funzione univariata e scalare
Utilizza una combinazione di metodi simili a quello della bisezione

X0 dovrebbe essere un vettore tale che...

X0(1) e X1(2) racchiudono uno zero (la funzione cambia di segno)
X0 può essere uno scalare...
...In questo caso Octave tenta di trovare l'altro punto da solo

Octave: Zeri di Funzioni

Octave offre due metodi per trovare gli zeri di una funzione:

Metodo 1: La funzione

[X, FVAL, INFO] = fzero(FUN, X0)

FUN è una funzione, passata come valore:

Se la_mia_funzione è il nome di una funzione...
...è possibile passarla ad fzero come parametro...
...Utilizzando la notazione @la_mia_funzione

Octave: Zeri di Funzioni

Octave offre due metodi per trovare gli zeri di una funzione:

Metodo 1: La funzione

[X, FVAL, INFO] = fzero(FUN, X0)

All'interno di fzero:

La funzione passata viene memorizzata nella variabile FUN
E può essere invocata con FUN(<parametri>)

Octave: Zeri di Funzioni

Octave offre due metodi per trovare gli zeri di una funzione:

Metodo 1: La funzione

[X, FVAL, INFO] = fzero(FUN, X0)

Per quanto riguarda i valori di ritorno:

X è lo zero (se si è arrivati a convergenza)
FVAL è il valore della funzione nello zero
INFO è un numero che rappresenta lo stato della soluzione
- Se vale 1, 2, 3 c'è convergenza
- Se INFO = 0 il metodo non è riuscito a convergere

Octave: Zeri di Funzioni

Octave offre due metodi per trovare gli zeri di una funzione:

Metodo 2: La funzione

[X, FVAL, INFO] = fsolve(FUN, X0)

Trova uno zero di una funzione $f : \mathbb{R}^n \rightarrow \mathbb{R}^n$

Utilizza dei metodi simili a quello di Newton-Raphson
X0 è la stima di partenza
Gli altri parametri e valori di ritorno sono come per fzero

Octave: Zeri di Funzioni

Octave offre due metodi per trovare gli zeri di una funzione:

Metodo 2: La funzione

[X, FVAL, INFO] = fsolve(FUN, X0)

Se FUN non è univariata e scalare (casi dei sistemi non lineari):

Deve avere come singolo parametro un vettore
Deve restituire come singolo parametro un vettore
fsolve cercherà un vettore di X che annulli tutte le uscite

Elementi di Informatica e
Applicazioni Numeriche T

Esercizio 1

Data una condotta per il trasporto di acqua con le seguenti proprietà:

$\begin{align} & D = 0.154 & & L = 4828 \\ & H_1 - H_2 = 6.35 & & \varepsilon = 0.045 \times 10^{-3} \end{align}$

Si determini la velocità dell'acqua nella condotta:

Utilizzando il metodo della bisezione
Utilizzando la funzione fzero di Octave

In particolare, si trovia uno zero dalla funzione:

$f(x) = H_1 - H_2 - W_{12}$

Si basi l'implementazione sullo StartKit disponibile sul sito del corso

Esercizio 1

Si implementi la funzione (nel file bisection.m):

function [X, FVAL, INFO] = bisection(f, a, b,
                                     n=1e5, tol=1e-7)

f è una funzione passata come valore
a e b sono gli estremi inziali dell'intervallo
n è il numero di iterazioni e tol è la tolleranza
Se si arriva a convergenza, si resittuisca INFO = 1...
...Altrimenti INFO = 0

Si individuino due valori di partenza a e b:

Per farlo, sarà utile disegnare la funzione $f(x)$

Elementi di Informatica e
Applicazioni Numeriche T

Esercizio 2

Si trovi una soluzione dell'equazione:

$f(x) = -\frac{1}{4} x^4 + \frac{1}{3} x^3 -\frac{3}{2} x^2 + \frac{3}{4} x + 1$

Utilizzando la funzione fsolve di Octave
Utilizzando il metodo di Newton-Raphson
- Si calcoli la derivata a partire dalla sua forma analitica

Si basi l'implementazione sullo StartKit disponibile sul sito del corso

Esercizio 2

Si codifichi la funzione:

function [fx, dfx] = target_function(x)

x è il valore (scalare) per cui fare il calcolo
fx rappresenta il valore di $f(x)$
dfx rappresenta il valore di $f'(x)$

Si disegni la funzione in un intervallo che contiene uno zero.

Esercizio 2

Si codifichi poi la funzione (nel file newton_raphson_d.m):

function [X, FVAL, INFO] = newton_raphson_d(f, x,
                                    n=1e5, tol=1e-7)

Che esegue il metodo di Newton-Raphson
f è una funzione passata come valore
- HP: f restituisce sia il valore di $f(x)$ che di $f'(x)$
x è il valore da cui partire
Gli altri parametri sono come per fsolve

Elementi di Informatica e
Applicazioni Numeriche T

Esercizio 3

Data la condotta per il trasporto di acqua dell'esercizio 1, con:

$\begin{align} & D = 0.154 & & L = 4828 \\ & H_1 - H_2 = 6.35 & & \varepsilon = 0.045 \times 10^{-3} \end{align}$

Si determini la velocità dell'acqua nella condotta:

Utilizzando la funzione fsolve di Octave
Utilizzando il metodo di Newton-Raphson
- Si approssimi la derivata utilizzando un rapporto incrementale

Si basi l'implementazione sullo StartKit disponibile sul sito del corso

Esercizio 3

Si codifichi la funzione (nel file newton_raphson.m):

function [X, FVAL, STATUS] = newton_raphson(f, x,
                                    n=1e5, tol=1e-7)

f è una funzione passata come valore e restituisce $f(x)$

Si codifichi la sottofunzione:

function y = df(f, x, tol=1e-7)

Che deve restituire il valore approssimato di $f'(x)$
Il valore dell'epsilon di macchina è ottenibile con eps

Elementi di Informatica e
Applicazioni Numeriche T

Esercizio 4

Si risolva il sistema non lineare:

$\begin{align} & x^2 + y^2 = 1 \\ & \sqrt{y} = \sin(x) \end{align}$

Utilizzando la funzione fsolve di Octave.

Si basi l'implementazione sullo StartKit disponibile sul sito del corso

In particolare, si implementi in modo opportuno:

function z = target_function(x)

Elementi di Informatica e
Applicazioni Numeriche T

Esercizio 5

Data una condotta in due tratte con le seguenti proprietà:

$\begin{align} & D_A = 0.20 & & D_B = 0.30 \\ & \nu = 1\times 10^{-6} & & \varepsilon = 0.010 \end{align}$

Si determini la portata della condotta:

Utilizzando la funzione fsolve di Octave
Utilizzando l'IPF

In particolare, si utilizzi la relazione:

$Q = \sqrt{\frac{18}{175.7 + 103,388\, f_A + 34,037\, f_B}}$

Esercizio 5

Si basi l'implementazione sullo StartKit disponibile sul sito del corso

L'algoritmo IPF è disponibile nel file ipf.m
Per il calcolo di $f_A$ e $f_B$ si utilizzi l'equazione di Churchill...
...disponibile nel file churchill.m

Si implementino le funzioni:

function z = transition_function(Q)
function z = target_function(Q)

Usate rispettivamente da IPF e fsolve

Scelta del valore di x iniziale in NR Funzioni anonime Plotting? Linspace figure salvare figure Piano (Vecchia lezione): Tipi di convergenza: [SPOSTARE DOPO IL CASO NON-LINEARE] - Lineare, sublineare, superlineare Differenze con il caso lineare: - Bacini di attrazione (sono un casino: possono essere discontinui...) Un caso particolare: radici di polinomi - Per adesso focalizziamoci sul trovare una sola radice - Primo approccio: riduzione al caso non lineare + Problema: condizioni di convergenza - Secondo approccio: + Usiamo la matrice compagna + Se troviamo gli autovalori, troviamo le radici + Come è definito un autovalore? + Facile, ma c'è lambda tra le scatole + Eliminiamolo + Rinunciamo a trovare l'autovettore: ci accontentiamo di un suo multiplo (che ha lo stesso comportamento) + Alé! Possiamo applicare l'iterazione di punto fisso + Alla fine troviamo un vettore unitario con la stessa direzione di un autovettore + Come trovare l'autovalore? Rapporto tra i coefficienti di due vettori successivi (qualunque coefficiente, basta che sia non nullo) + Osservazione: riduzione ad un caso non lineare + Converge? Condizioni + Produce sempre l'autovalore con valore assoluto più grande - Trovare tutte le radici: regola di Ruffini (divisione sintetica) Fix-point iteration Fix-point iteration - Calcolo della radice quadrata? Attrattori? - Punti fissi attrattivi - Bacino di attrazione Teorema del punto fisso di Banach? Power iteration/power method - Condizioni di convergenza? - Dim. di convergenza all'autovalore maggiore? - Non è che a loro interessi tanto... Bracketing methods Teorema del punto intermedio Ricerca lineare Metodo di bisezione Regula falsi NOTA: non sono riducibili a fix-point iteration Non-bracketing methods Metodo delle secanti Metodo di Newton Radici di un polinomio? - Metodo di Horner + Newton - Companion matrix + power method? Errori? Calcolo della derivata Cancellazioni? Evitate nella regula falsi Remeber to explain: Multi variate functions applied to vectors subfunctions array concatenation memorizzazione delle matrici in memoria continue (magari nella lezione sull'ottimizzazione) trattamento degli argomenti non specificati return Gestione errori (error/warning) Debugging Prossime volte: determinant computation (recursive!) factorial computation (recursive!) matrix argument to vector operation - a good occasion to explain multiple functions in a single file sieve of erathostenes other algorithms to find prime numbers? permutations - Permute vectors - Permute rows/columns of a matrix Taylor series expansion? convolution? bubble sort / naive sort comparison functions set operations - intersection - union - substract? - powerset? continued fraction expansion Coordinate conversion (cartesian, polar) Some matrix factorizations/decompositions? - Choleski - LU decomposition - QR factorization - Singular Value Decomposition Gradient descent Newton method Fixed point iteration Bisection method - bracket a zero - convex optimization Minimization by repeated evaluation Golden section search Numeric gradient/Jacobian/Hessian Nelder-Mead? RNG algorithms (something simple) Using diagonal matrices for scaling Integration methods: - Numerical integration based on Gaussian quadrature. - Numerical integration using an adaptive vectorized Simpson’s rule. - Numerical integration using an adaptive Lobatto rule. - Numerical integration using an adaptive Gauss-Konrod rule. - Numerical integration using adaptive Clenshaw-Curtis rules. - Numerical integration of data using the trapezoidal method. Multi-dimensional integration? - Recursive appraoch - Orthogonal collocation ODE - algo? - reduction to first order Optimization? - LP, QP (null-space active-set method)... the algos are too complex - QP: basic method for convex problems? Zero-gradient - NLP via sequential quadratic programming - Least Square method? Descriptive statistics - Mean - Median - Variance - Stdev (second moment, statistic bias -- maybe this one later) - Mode? - Quartiles, quantiles - Explain histograms, too? - Histogram count computation - correlation/covariance? "True" statistics & probability theory - stat plots - unbiased estimators - some probability distributions - central limit theorem - Distributions - pdf, cdf, quantiles - One or two stat tests? - Confidence intervals? Generate permutations? Centering / Normalization Polynomials - Representation? - Horner's method? - Roots of a polynomial: Frobenius companion matrix, eigenavalues - poles? Interpolation - Nope - Use variable transformation for power law fitting Verifica stato di un elemento di un array Sort by argument Calcolo della radice quadrata Serie di Taylor (per calcolare una funzione) I/O semplice + disp + printf? Per stampare con precisione alta Goal: algoritmi + complessi ed esempi di propagazione degli errori valutazione di un polinomio (trivial) valutazione di un polinomio (Horner) Somme: - Somma "normale" - Somma gerarchica - Somma di Kahan Numeri interi - identificazione di numeri primi - fattorizzazione in numeri primi (trial division) Algoritmi di ordinamento: - Solo naive sort e bubble sort RNG - un algoritmo semplice - esempi di utilizzo di RNG in Octave Valutazione di una funzione a gradini - Lookup in una tabella chiave-valore - Valutazione in punti multipli Numeri interi ed algoritmi - Interi in Octaves - Promozione/demozione? - sieve of erathostenes (magari nella lezione 3) - fattorizzazione in numeri primi (trial division) - GCD GCD: q = gcd a = n_a q // q è il GCD di a e b b = n_b q // q è il GCD di a e b a = p b + r // divisione di a per b Quindi: n_a q = a = p b + r = p n_b q + r Quindi n_a = p n_b + r / q Deve venire un intero => r/q deve essere intero => r è divisibile per q * Si dovrebbe poter fare lo stesso ragionamento anche per la sottrazione

Elementi di Informatica e Applicazioni Numeriche T

Octave: Zeri di Funzioni

Elementi di Informatica e
Applicazioni Numeriche T