Metodi numerici
per catene di Markov - laboratorio
Docente:
Beatrice Meini
Lezione 5: I metodi Logarithmic Reduction e Cyclic Reduction
La function [G, vres] = lr(A, tol, maxiter) calcola la matrice G per un QBD mediante la Logarithmic Reduction.
La function [G, vres] = cr(A, tol, maxiter) calcola la matrice G per un QBD mediante la Cyclic Reduction.
La function X=bgth(P,u,v,B) risolve il sistema lineare AX=B, dove A e' una M-matrice espressa nella forma, A= "matrice diagonale" - P, con P non negativa, e u,v vettori positivi tali che Au=v.
La function G = lr_ye(A, tol, maxiter) calcola la matrice G per un QBD mediante la Logarithmic Reduction, usando l'aggiustamento diagonale, implementato dalla function bgth.
Sperimentazione:
Calcolare la matrice G degli esempi di QBD visti alla lezione precedente con la Logarithmic Reduction, scegliendo ad esempio tol=1.e-13 e maxiter=30. Disegnare in scala semilogaritmica il vettore dei residui. Stessa cosa con Cyclic Reduction. Generare anche i dati con la function A=genera_qbd_circ(k,m), dove k e m sono 2 interi, k rappresenta la dimensione a blocchi e m la dimensione dei blocchetti di ciascun A_i ( provare ad esempio k=2, m=10 e poi aumentare le dimensioni).
Utilizzare la Logarithmic Reduction con aggiustamento diagonale. La maggiore robustezza dell'aggiustamento diagonale si osserva nell'esempio 4, scegliendo tol=1.e-16 e maxiter=30; infatti lr restituisce NaN, mentre lr_ye restituisce una buona approssimazione.
La velocita' di convergenza, e
l'accuratezza, di LR e CR sono legate alla vicinanza a 1 degli autovalori del polinomio quadratico associato all'equazione matriciale. Calcolare questi autovalori mediante i comandi
k=size(A,1);
Am1=A(:,:,1); A0=A(:,:,2); A1=A(:,:,3);
polyeig(-Am1, eye(k)-A0, A1)