Convergence of some problems of positive type and a theorem of Fill (Q1340549)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Convergence of some problems of positive type and a theorem of Fill |
scientific article |
Statements
Convergence of some problems of positive type and a theorem of Fill (English)
0 references
22 May 1995
0 references
Let \(B\) be an irreducible nonnegative matrix with Perron-Frobenius eigenvalue \(\lambda\) and corresponding positive right and left eigenvectors \(\xi=\{\xi_ i\}\) and \(\eta = \{\eta_ i\}\), normed so that \(\xi^ T\eta = 1\). The authors consider the iterates \(u^{k + 1} = Bu^ k\) where \(u^ k = \{u_ j^ k\}\). By extending a procedure for stochastic matrices of \textit{J. A. Fill} [Ann. Appl. Prob. 1, No. 1, 62-87 (1991; Zbl 0726.60069)] they show that \[ \left( \sum_ j (\eta_ j/ \xi_ j) (u^ k_ j)^ 2 \right)^{1/2} \leq \lambda^ k \left( \sum_ j (\eta_ j/ \xi_ j) (u^ 0_ j)^ 2 \right)^{1/2} \] thus obtaining a weighted \(\ell_ 2\) norm with precisely the correct convergence rate. For convergence to the normed Perron eigenvector the authors obtain \[ \left( \sum_ j (\eta_ j/ \xi_ j) (\alpha_ k u^ k_ j - \xi_ j)^ 2 \right)^{1/2} \leq \text{Const. } \omega^ k \] where \(0 < \omega < 1\), and \(\alpha_ k\) is a norming constant. Three applications are made: 1) to the Gauss-Seidel iterations of a discrete convection-diffusion equation in two different cases; 2) to a system of linear ordinary differential equations with constant coefficients; and 3) to a parabolic initial-boundary value problem. For nonnegative matrices it is generally easier to work with \(\ell_ 1\)- type rather than \(\ell_ 2\)-type norms. Thus if \(u^ 0 \geq 0\), \(u^ 0 \neq 0\) we have in parallel to the above, in terms of a weighted \(\ell_ 1\) norm: \[ \sum_ j \eta_ j u^ k_ j = \lambda^ k \sum_ j \eta_ j u^ 0_ j; \quad \sum_ j \eta_ j | \beta_ k u^ k_ j - \xi_ j | \leq \tau^ k_ 1 (Y^{-1} B^ T Y/ \lambda) \] where \(Y = \text{diag} \eta_ i\), \(\beta_ k^{-1} = \| Yu^ k \|_ 1\). This comes from considering the stochastic matrix \(P = Y^{-1} B^ TY/ \lambda\) and the \(\tau_ 1\) ergodicity coefficient [e.g. \textit{E. Seneta}, Contemporary Mathematics 149, 189-199 (1993; Zbl 0784.60065), Theorem 2.1).
0 references
irreducible nonnegative matrix
0 references
Perron-Frobenius eigenvalue
0 references
stochastic matrices
0 references
convergence
0 references
Perron eigenvector
0 references
Gauss-Seidel iterations
0 references
discrete convection-diffusion equation
0 references
parabolic initial-boundary value problem
0 references