Dismiss
The Prior Art Database and Publishing service will be updated on Sunday, February 25th, from 1-3pm ET. You may experience brief service interruptions during that time.
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

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...