Browse Prior Art Database

Algorithm with Controlled Feedback for System of Equations with Stochastic Matrix

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

Publishing Venue

IBM

Related People

Verkhovsky, BS: AUTHOR

Abstract

This algorithm has immediate application to a variety of dynamic programming problems. (Image Omitted)

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 98% of the total text.

Page 1 of 2

Algorithm with Controlled Feedback for System of Equations with Stochastic Matrix

This algorithm has immediate application to a variety of dynamic programming problems.

(Image Omitted)

This algorithm provides an efficient procedure for finding the solution for a system of equations: (**) V = b + Beta Av, where V is the M-dimensional unknown

vector.

The Algorithm
1.

(Image Omitted)

(a) e = (1,1,...,1) (M dimensions);

(b) a(n) is the controlled feedback power;
2. V/n+1/ = (b + Gamma(n) Beta Av/n/)

Note
1. Process (1)-(2) converges to the solution of the system (**) if for all n;

ev/n/ Not = 1 and V/o/> 0
2. The algorithm when programmed on the APL yielded considerable reduction of iterations over conventional methods, particularly for the case when Beta is very close to 1. For example, for M = 50, Beta = .9, a(n) = const = 10, the algorithm gives the solution V/n/ for 14-16 iterations with accuracy Epsilon = 10/-10/ where: Epsilon = max 3 b + Beta Av/n/ - v/n/3

i
3. From computer experiments, for the case when a(n) = a, the best a = 2 Beta-1 over 1-Beta (see table below)

(Image Omitted)

4. More general case:

1) A is any nonnegative matrix,

2) Psi = c over cb, where c > o

3) V(n+1) = b + Gamma(n) A V(n)

4) Gamma(n) = (Psi A V(n) over Psi V(n)-1)/a/

5) a = 2 Lambda(1)-1 over 1 - Lambda(1), where Lambda(1) is

the largest eigenvalue of A. The best

Psi has to be very close to an eigenvector corresponding

to eigenvalue Lambda(1).

1

Page 2 of 2

2

[This page contains 2 pic...