Esercizio sulla sequenza di fibonacci

[natia88]

Si consideri l'equazione alle differenze ${u(n)=1/2*u(n-1)+3/2*u(n-2), u(1)=1, u(2)=1}$. Costruire un M-file (matlab) che indichi il primo degli $n\in NN$ tale che |u(n)| risulti maggiore di $10^12$; posto $d(n)=u(n)-u(n-1)$, n=2,3,... indichi il primo degli $n\in NN$ tale che |u(n)| e |d(n)| risultino maggiori di $10^12$.



Io ho costruito questo M-file:
u(1)=1;
u(2)=1;
d(2)=u(2)-u(1);
while abs(u(n))>10^12 and abs(d(n))>10^12
u(n)=1/2*u(n-1)+3/2*u(n-2)
d(n)=u(n)-u(n-1)
end
disp(n,u(n));

ma mi dice che devo specificare n! dove lo specifico e cosa ci devo scrivere?

[vict85]

Quella trasformazione è lineare, con l'utilizzo delle matrici e le potenze veloci potresti renderlo più efficiente. Anche se penso che $10^12$ sia troppo piccolo per essere un miglioramento notevole delle performance.

[itpareid]

lo inizializzi a $3$ fuori dal ciclo e dentro al ciclo lo incrementi, poi mi sa che nel while devi cambiare il segno della disuguaglianza sulle condizioni

[natia88]

itpareid, se lo inizializzo a 3 mi da questo errore ??? Attempted to access u(3); index out of bounds because numel(u)=2.
e se cambio segno della disuguaglianza mi da anche errore! però anche coll'altro segno mi da lo stesso errore...non è che ho sbagliato qualcosa nell'impostazione?

[itpareid]

non sono molto pratico di matlab, forse devi prima dichiarare ed inizializzare i vettori, ma lascio la parola a chi ne sa più di me

[natia88]

ok, sperando che qualcuno risponda...comunque grazie lo stesso!

[apatriarca]

Prima di tutto non hai bisogno di memorizzare tutti i valori. Sono infatti sufficienti gli ultimi due. Solo gli ultimi due valori sono infatti necessari per calcolare il valore successivo sia della successione u, che di d. Un metodo abbastanza elegante in matlab potrebbe essere quello di usare le matrici (ma non è ovviamente necessario) e quindi avere un vettore U = [u(n), u(n-1)] che mantiene lo stato attuale a usare la matrice A = [1/2, 3/2; 1, 0] che è la trasformazione lineare per passare allo stato successivo. Più esplicitamente sfrutto il fatto che

$((u(n+1)), (u(n))) = ((0.5, 1.5), (1, 0))*((u(n)), (u(n-1)))$

Passando al codice diventerebbe qualcosa come il seguente (uso raramente Matlab e quindi non sono certo della sintassi):

function [m, n] = fun()

A = [0.5, 1.5; 1, 0];
U = [1; 1];
n = 2;

while abs(U(1) - U(2)) < 10^12
    U = A*U;
    n = n+1;
    if abs(U(1)) > 10^12
        m = n;
    end
end

m ed n sono i due numeri che ti chiede nell'esercizio. m è il più piccolo numero tale che $|u(n)| > 10^{12}$ mentre n è il più piccolo intero tale che $|d(n)| > 10^{12}$ e $|u(n)| > 10^12$. Siccome $d(n) < u(n)$ per ogni $n$ è sufficiente testare la prima condizione.

EDIT: Una piccola dimostrazione dell'affermazione secondo cui $d(n) < u(n)$ per ogni $n$ (per il quale esistono entrambe le successioni..). Siccome $d(n) = u(n) - u(n-1)$ è sufficiente dimostrare che u(n-1) sia una quantità positiva. Ma questo è immediato perché $u(n)$ è combinazione lineare (con termini tutti positivi) delle condizioni iniziali $u(1) = u(2) = 1$. Ogni coefficiente che compare nella somma è infatti della forma $(0.5)^s(1.5)^r$.

EDIT2: Corretto una cosa nel codice.

[itpareid]

molto bella ed elegante questa implementazione! complimenti!

[natia88]

grazie apratiarca! funziona! ed è abbastanza elegante!