## Thesis etd-09072023-031853 |

Link copiato negli appunti

Thesis type

Tesi di laurea magistrale

Author

DENISKIN, NIKITA

URN

etd-09072023-031853

Thesis title

Numerical Inverse Laplace Transform applied to Markov Chains

Department

MATEMATICA

Course of study

MATEMATICA

Supervisors

**relatore**Prof. Poloni, Federico

**relatore**Prof. Benzi, Michele

Keywords

- Abate-Whitt method
- Inverse Laplace Transform
- Markov chain
- Markovian Fluid Flow Model
- Numerical Analysis

Graduation session start date

22/09/2023

Availability

Full

Summary

In this thesis, we study the Numerical Inverse of the Laplace Transform with Abate-Whitt methods, with applications to queueing theory.

The Laplace Transform is an integral transform; it has a wide range of applications, ranging from solution of differential equations to signal processing and study of electrical circuits. The Inverse Laplace Transform has similar applications, but they have a significant practical difference: the computation of the Laplace Transform is well-behaved, whereas the computation of the Inverse Laplace Transform is a highly unstable problem. Small perturbation of the input data can be greatly amplified by the procedure; therefore, it is important to develop algorithms that are as much accurate as possible.

The Inverse Laplace Transform arises naturally in the study of Markovian Fluid Flow Models. They can be thought of as the continuous limit case of a queueing model. A Markovian Fluid Flow Model is composed by a continuous-time Markov chain, and a random variable representing the fluid level, which increases or decreases depending on the state of the Markov chain. The matrix Psi(t) indicates the return probability of the fluid to the starting level in a time less than t. However, Psi(t) is difficult to calculate in a direct way. The standard approach is to calculate its Laplace Transform by solving a non-symmetric algebraic Riccati equation, and then apply the Inverse Laplace Transform.

We focus on inversion methods of the Abate-Whitt framework. The general structure of the methods is similar to quadrature of the Bromwich Integral: the original function valued at a given point, is approximated by a linear combination of the Laplace Transform valued at the node points.

We do a comparative study of different Abate-Whitt methods, using Markovian Fluid Flow Models and continuous-time Markov chains as test problems. We analyze the Euler, Gaver-Stehfest, and Talbot methods, which are the most commonly used; the CME method, which has been developed more recently and is more oriented to solve problems with empirical data; the Zakian-Padé method, which predates all the other methods but has been overlooked in the literature. Furthermore, we propose a new method, which we call AAAME. Like the Zakian-Padé method, it is based on approximating the exponential function with a sum of resolvents; instead of using Padé approximants, we propose to solve this subproblem by using the AAA algorithm.

We found that all methods except CME present numerical instability, as the number of nodes grows. Among the classical methods, Talbot has the best performance, followed by the Euler method. The Zakian-Padé method has the fastest convergence rate, but suffers greatly from instability. Our new method, AAAME, provides errors similar to the Talbot and Zakian-Padé methods, being faster than Talbot but slower than Zakian-Padé. The method has many adjustable parameters, namely the training set used in the AAA algorithm, and by choosing it appropriately, we found that the AAAME method can achieve consistently good results.

The Laplace Transform is an integral transform; it has a wide range of applications, ranging from solution of differential equations to signal processing and study of electrical circuits. The Inverse Laplace Transform has similar applications, but they have a significant practical difference: the computation of the Laplace Transform is well-behaved, whereas the computation of the Inverse Laplace Transform is a highly unstable problem. Small perturbation of the input data can be greatly amplified by the procedure; therefore, it is important to develop algorithms that are as much accurate as possible.

The Inverse Laplace Transform arises naturally in the study of Markovian Fluid Flow Models. They can be thought of as the continuous limit case of a queueing model. A Markovian Fluid Flow Model is composed by a continuous-time Markov chain, and a random variable representing the fluid level, which increases or decreases depending on the state of the Markov chain. The matrix Psi(t) indicates the return probability of the fluid to the starting level in a time less than t. However, Psi(t) is difficult to calculate in a direct way. The standard approach is to calculate its Laplace Transform by solving a non-symmetric algebraic Riccati equation, and then apply the Inverse Laplace Transform.

We focus on inversion methods of the Abate-Whitt framework. The general structure of the methods is similar to quadrature of the Bromwich Integral: the original function valued at a given point, is approximated by a linear combination of the Laplace Transform valued at the node points.

We do a comparative study of different Abate-Whitt methods, using Markovian Fluid Flow Models and continuous-time Markov chains as test problems. We analyze the Euler, Gaver-Stehfest, and Talbot methods, which are the most commonly used; the CME method, which has been developed more recently and is more oriented to solve problems with empirical data; the Zakian-Padé method, which predates all the other methods but has been overlooked in the literature. Furthermore, we propose a new method, which we call AAAME. Like the Zakian-Padé method, it is based on approximating the exponential function with a sum of resolvents; instead of using Padé approximants, we propose to solve this subproblem by using the AAA algorithm.

We found that all methods except CME present numerical instability, as the number of nodes grows. Among the classical methods, Talbot has the best performance, followed by the Euler method. The Zakian-Padé method has the fastest convergence rate, but suffers greatly from instability. Our new method, AAAME, provides errors similar to the Talbot and Zakian-Padé methods, being faster than Talbot but slower than Zakian-Padé. The method has many adjustable parameters, namely the training set used in the AAA algorithm, and by choosing it appropriately, we found that the AAAME method can achieve consistently good results.

File

Nome file | Dimensione |
---|---|

Deniskin...trale.pdf | 3.93 Mb |

Contatta l’autore |