×

On the solution of a quadratic vector equation arising in Markovian binary trees. (English) Zbl 1265.65105

The paper is devoted to the numerical solution of a quadratic vector equation arising in Markovian binary trees (MBTs). MBTs are a family of branching processes used to model the growth of certain populations. An important issue related to MBTs is the computation of the extinction probability of the population, which is the minimal nonnegative solution \(x^\ast \in \mathbb {R}_{+}^N:=\{v\in \mathbb {R}^N\:v_i\geq 0\;(1\leq i\leq N)\}\) of the quadratic vector equation \[ x=a+b(x,x),\tag{1} \] where \(a\in \mathbb {R}_+^N\) and \(b\:\mathbb {R}_{+}^N\times \mathbb {R}_{+}^N\to \mathbb {R}_+^N\) is a bilinear form such that \(e=(1,1,\dots ,1)^T\in \mathbb {R}^N\) is always a solution of (1).
Let \(R\) be the matrix of \(\mathbb {R}_{+}^{N\times N}\) which represents the linear mapping \(b(e,\cdot )+b(\cdot ,e)\). The corresponding MBT is called subcritical, supercritical, or critical if the spectral radius \(\rho (R)\) of \(R\) is strictly less than 1, strictly greater than 1, or equal to 1, respectively. In the subcritical and critical cases, the minimal nonnegative solution \(x^\ast\) is \(e\), while in the supercritical case \(x^\ast\leq e\), \(x^\ast\neq e\). Therefore, only the supercritical case is of interest for the computation of \(x^\ast\).
Several fixed-point iterations have been considered for the solution of (1). In particular, S. Hautphenne et al. [Linear Algebra Appl. 428, No. 11–12, 2791–2804 (2008; Zbl 1155.65038)] have shown that the Newton iteration applied to (1) converges monotonically and quadratically, starting at \(x_0=(0,\dots ,0)\). However, when approaching critical problems, the convergence speed of all proposed methods degrades; in fact, in the limiting case \(\rho (R)=1\), \(x^\ast=e\), the Newton iteration converges linearly and all the other fixed-point methods converge sublinearly.
B. Meini and F. Poloni [SIAM J. Matrix Anal. Appl. 32, No. 1, 248–261 (2011; Zbl 1242.65104)] have proposed a further fixed-point iteration for the numerical solution of (1). For \(y\:=e-x\), the vector of survival probabilities \(y^\ast :=e-x^\ast\) is sought. Under the assumption \(y<e\), (1) can be rewritten in the form \(y=H_y\,y,\) where \(H_y=b(\cdot ,e)+b(e,\cdot )-b(y,\cdot )\) is a nonnegative irreducible matrix depending linearly on \(y\). In this sense, the solution \(y^\ast\) can be interpreted as a vector \(y^\ast<e\) such that \(\rho (H_{y^\ast})=1\) and \(y^\ast\) is a Perron vector of \(H_{y^\ast}\), namely an eigenvector corresponding to the eigenvalue 1. This leads the authors to propose a Perron iteration \[ y_{k+1}=\text{PV}(H_{y_k}),\tag{2} \] where \(\text{PV}\) denotes a certain normalized Perron vector of the matrix \(H_{y_k}\).
Further results concerning the Perron iteration (2) are obtained. First, the authors obtain a condition that ensures that the limit of the Perron iteration (2) is the vector \(y^\ast\) of survival probabilities, provided that such an iteration converges. Second, the authors consider the application of the Newton method to the equation \(y=\text{PV}(y)\), obtaining thus a “Newton-Perron” iteration with quadratic rate of convergence. The behavior of such a Newton-Perron iteration for close-to-critical problems is similar to that of the Perron iteration (2), namely it tends to converge faster. Finally, the authors observe that (1) depends only on the quadratic form \(b(t,t)\), and therefore several (nonnecessarily symmetric) bilinear forms \(b(s,t)\) can be considered, provided that the corresponding quadratic form is the original one. This yields modifications in the Perron iteration (2) and the Newton-Perron iteration mentioned above which are discussed.
The paper ends with a description of numerical experiments comparing the behavior of the Newton iteration, the Perron iteration (2) and the Newton-Perron iteration of the authors.

MSC:

65H10 Numerical computation of solutions to systems of equations
92D25 Population dynamics (general)
60J80 Branching processes (Galton-Watson, birth-and-death, etc.)

Software:

ARPACK
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Meini, A Perron iteration for the solution of a quadratic vector equation arising in Markovian binary trees, SIAM. J. Matrix Anal. & Appl. 32 pp 248– (2011) · Zbl 1242.65104 · doi:10.1137/100796765
[2] Bean, Markovian trees: properties and algorithms, Annals of Operations Research 160 pp 31– (2008) · Zbl 1213.60133 · doi:10.1007/s10479-007-0295-9
[3] Hautphenne, Algorithmic approach to the extinction probability of branching processes, Methodology and Computing in Applied Probability 13 (1) pp 171– (2009) · Zbl 1210.60094 · doi:10.1007/s11009-009-9141-7
[4] Poloni, Quadratic vector equations, Linear Algebra and its Applications (2011) · Zbl 1268.15014 · doi:10.1016/j.laa.2011.05.036
[5] Hautphenne, Newton’s iteration for the extinction probability of a Markovian binary tree, Linear Algebra and its Applications 428 (11-12) pp 2791– (2008) · Zbl 1155.65038 · doi:10.1016/j.laa.2007.12.024
[6] Hautphenne, On the link between Markovian trees and tree-structured Markov chains, European Journal of Operational Research 201 (3) pp 791– (2010) · Zbl 1173.90580 · doi:10.1016/j.ejor.2009.03.052
[7] Ortega, Iterative Solution Of Nonlinear Equations In Several Variables, Classics in Applied Mathematics 30 (2000) · Zbl 0949.65053 · doi:10.1137/1.9780898719468
[8] Lehoucq, Arpack User’s Guide: Solution of Large-Scale Eigenvalue Problems With Implicityly Restorted Arnoldi Methods (Software, Environments, Tools) (1997)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.