Abstract
In this paper it is demonstrated how the probabilistic concept of a stopping time in a random process may be used to generate an iterative method for solving a system of linear equations. Actually all known iterative approximation methods for solving linear equations are generated by various choices of a stopping time e. g. the point and block Jacobi methods, the point and block Gauss-Seidel Methods and overrelaxation methods are covered.
The probabilistic approach offers—in a natural way—the possibility of adapting the solution technique to the special structure of the problem. Moreover, posterior bounds for the solution are constructed, which lead to faster convergence of the approximations than with usual prior bounds.
Zusammenfassung
Es wird gezeigt, wie das probabilistische Konzept der Stoppzeit eines Zufallsprozesses für eine iterative Methode zur Lösung eines Systems linearer Gleichungen herangezogen werden kann. Alle bekannten iterativen Näherungsmethoden zur Lösung linearer Gleichungssysteme, wie z. B. die Blockmethoden nach Jakobi und Gauss-Seidel und Überrelaxationsmethoden, entsprechen verschieden gewählten Stoppzeiten.
Das probabilistische Verfahren bietet die Möglichkeit, Lösungstechniken für die spezielle Struktur des Problems zu adaptieren. Darüber hinaus führen die vorgeschlagenen Methoden zu einer schnelleren Konvergenz.
Similar content being viewed by others
References
Hübner, G.: Improved procedures for eliminating suboptimal actions in Markov programming by the use of contraction properties. In: Transactions of the 7th Prague conference on stochastic processes, Vol. A, pp. 257–263. Prag: Academia 1977.
MacQueen, J.: A modified dynamic programming method for Markovian decision problems. J. Math. Anal. Appl.14, 38–43 (1966).
Morton, T., Wecker, W.: Discounting, ergodicity and convergence for Markov decision process. Man. Sci.23, 890–900 (1977).
Nunen, J. A. E. E. van: Contracting Markov decision processes. Mathematical centre tract no. 71. Math. Centre Amsterdam, 1976.
Nunen, J. A. E. E. van: A set of successive approximation methods for discounted Markov decision problems. Zeitschrift für Oper. Res.20, 203–208 (1976).
Nunen, J. A. E. E. van, Stidham, jr., S.: Action dependent stopping times and Markov decisions, processes with unbounded reward (to appear in O. R. spectrum 1981).
Porteus, E. L.: Bounds and transformations for discounted finite Markov decision chains. Oper. Res.23, 761–784 (1975).
Seneta, E.: Nonnegative matrices. Londen: Allyn and Bacon 1973.
Varga, R. S.: Matrix iterative analysis. Englewood Cliffs, N. J.: Prentice-Hall 1962.
Wessels, J.: Stopping times and Markov programming. In: Transactions of the 7th Prague conference on stochastic processes etc., Vol. A, pp. 575–585. Prag: Academia 1977.
Wessels, J.: Markov programming by successive approximate with aspect to weighted supremum norm. J. Math. Anal. Appl.58, 326–335 (1977).
Schweitzer, P.: Iterative solution of the functional equations of undiscounted Markov renewal programming. J. Math. Anal. Appl.34, 495–501 (1971).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
van Nunen, J., Wessels, J. Solving linear systems by methods based on a probabilistic interpretation. Computing 26, 209–225 (1981). https://doi.org/10.1007/BF02243479
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02243479