Browse Prior Art Database

Algorithm for System of Equations with Stochastic Matrix

IP.com Disclosure Number: IPCOM000085350D
Original Publication Date: 1976-Mar-01
Included in the Prior Art Database: 2005-Mar-02
Document File: 1 page(s) / 12K

Publishing Venue

IBM

Related People

Verkhovsky, BS: AUTHOR

Abstract

The present algorithm has immediate application to a variety of dynamic programming problems, multivariable systems, and input-output analysis. While other procedures have been used for such problems, the present algorithm is believed to be more efficient. (Image Omitted)

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 88% of the total text.

Page 1 of 1

Algorithm for System of Equations with Stochastic Matrix

The present algorithm has immediate application to a variety of dynamic programming problems, multivariable systems, and input-output analysis. While other procedures have been used for such problems, the present algorithm is believed to be more efficient.

(Image Omitted)

The subject of the algorithm is an efficient procedure for finding the solution for a system of equations:. (*) V = b + Beta A V, where V is the M-dimensional unknown vector. The Algorithm
(a) Gamma(n) = [e(I-A) V/n/]/-1/] where e = (1,1,...,1)

(M-dimensional vector)
(b) V/n+1/ = Gamma(n) (b + Av/n/).

Note: Process (a) - (b) converges to the solution of the system
(*) if for all n,

e (I-A) V/n/ not = 0 and eV/o/ not = 0.

The algorithm when programmed on the APL yielded considerable reduction of iterations over conventional methods. For example, for M = 50, Beta = .95 the algorithm gives the solution V/n/ less than for 10 iterations with accuracy Epsilon = 10/-10/ where: Epsilon = max 3b + Beta Av/n/ - v/n/3

1 </- i </- M.

References

1. Leontieff, W. W. The Structure of the American Economy, 1919-1920. Oxford, University Press, N.Y. 1931.

2. Denarco, Eric V. "On Linear Programming in a Marcov Decision Problem", Manag. Sci. 16, NS, 1970, 281-288.

3. Meerov, M.V., Litvak, B.L., "Static Optimization of High-Dimensionality Multivariable Systems", IFAC Kyoto Symposium of Systems Engineering Approach to Computer Control, August 1970, Kyoto, Japan...