logo SBA

ETD

Archivio digitale delle tesi discusse presso l’Università di Pisa

Tesi etd-06052008-110213


Tipo di tesi
Tesi di laurea specialistica
Autore
MORINI, EMILIANO
URN
etd-06052008-110213
Titolo
Metodi numerici per la probabilita' di estinzione di un Markovian Binary Tree
Dipartimento
SCIENZE MATEMATICHE, FISICHE E NATURALI
Corso di studi
MATEMATICA
Relatori
Relatore Prof.ssa Meini, Beatrice
Relatore Prof. Bini, Dario Andrea
Parole chiave
  • Branching processes
  • Extinction probability
  • Matrix analytic methods
Data inizio appello
27/06/2008
Consultabilità
Completa
Riassunto
In questa tesi consideriamo il problema computazionale della ricerca della soluzione minimale non negativa $\q$ dell'equazione
\begin{equation}\label{eqn intro eqn estinzione}
\x-\ve{a}-\Psi(\x \oti \x)=\0,
\end{equation}
dove $\x, \ve{a}\in \R^n$, $\Psi \in \R^{n \times n^2}$, $\0 \leq \ve{a} \leq \ve{e}$, $\ve{e}=(1,1,\dots,1)^T$, $0\leq \Psi_{i,jk}\leq 1$ per ogni $i,j,k=1,\dots, n$, e
$$
\ve{e}-\ve{a}-\Psi(\ve{e} \oti \ve{e})=\0.
$$
% Siamo interessati a calcolare la sua soluzione minimale non negativa, cio\`e il vettore $\q$ tale che
% $$
% \ve{q}-\ve{a}-\Psi(\ve{q} \oti \ve{q})=\0
% $$
% e $\0 \leq \q \leq \y$ per ogni altra soluzione $\y$ non negativa di (\ref{eqn intro eqn estinzione}), dove le disuguaglianze sono fatte componente per componente. L'esistenza di $\q$ \`e dimostrata in \cite{Athreya}.
Questa equazione \`e strettamente collegata ad un particolare processo di diramazione, il
% i quali hanno proposto diversi algoritmi per affrontare il problema, adattando metodi gi\`a noti in letteratura.
%
% L'importanza di (\ref{eqn intro eqn estinzione}) \`e dovuta al fatto che la soluzione $\q$ che si vuole calcolare ha un significato probabilistico molto interessante nelle applicazioni. Infatti, l'equazione analizzata \`e strettamente collegata al
\emph{Markovian Binary Tree (MBT)}, introdotto recentemente in letteratura. %studiato negli ultimi anni da diversi matematici del settore probabilistico-numerico (\cite{MT: prop e algo}, \cite{p2p}). Il MBT risulta essere

Dopo una breve descrizione del MBT, illustriamo gli algoritmi noti per calcolare $\q$, e generalizziamo questi risultati introducendo una famiglia di nuovi metodi iterativi dipendenti da alcuni parametri. Per ogni metodo della famiglia \`e possibile dimostrare interessanti propriet\`a di convergenza.

Effettuiamo inoltre uno studio dettagliato della successione che si ottiene applicando ad $(\ref{eqn intro eqn estinzione})$ una variante del metodo di Newton, dimostrando che con questo metodo la convergenza \`e pi\`u veloce.

In this work, we examine the computational problem of finding the minimal non-negative solution $\q$ of the equation
\begin{equation}\label{eqn intro eqn estinzione}
\x-\ve{a}-\Psi(\x \oti \x)=\0,
\end{equation}
where $\x, \ve{a}\in \R^n$, $\Psi \in \R^{n \times n^2}$, $\0 \leq \ve{a} \leq \ve{e}$, $\ve{e}=(1,1,\dots,1)^T$, $0\leq \Psi_{i,jk}\leq 1$ for each $i,j,k=1,\dots, n$, and
$$
\ve{e}-\ve{a}-\Psi(\ve{e} \oti \ve{e})=\0.
$$
This equation arises from a special kind of branching process, called Markovian Binary Tree (MBT),
recently introduced in the literature.
%introduced by Kontoleon in his PhD thesis.

After a brief description of the MBT, we focus our attention on some available methods %described in literature
for calculating $\q$, and we generalize these results by introducing a new family of iterative algorithms depending on some parameters. We can prove some interesting convergence properties valid for each method of this family.

In addition, we analyze the sequence obtained applying a variant of Newton's methods to this problem, by showing that in this case the convergence is faster.
File