Finding roots of polynomials by simplicial algorithms using the structured programming language pascal

’!This project is to find the roots of apolynomial by a simplicialalgorithm using the structured programming language Pascal.The simplicial algorithm was developed by Kuh n [SJ [9J. Thealgorithm is based on Brouwer’s fixed point theorem (1912). Brouwer’sfixed point theorem is concerned with the existence of a fixed point ofa continuous function from a compact, convex set into itself.Brouwer’s TheoremLet fIn + In be continuous, then there is a point u* £ Insuch thatf(u*) u*whereIn 1*1 .....• *1n timeswith I the unit interval [0, IJ’!he original proof of this theorem was non constructive. It isonly recently that algorithms have been developed to compute approximateBrouwer fixed points.The first constructive proof of Brouwer’s fixed point theoremwas given by Scarf in 1967 [12J, who introduced an algorithm on the unitsimplex Sn. His algorithm generates a path of adjacent so-calledprimitive sets. This path starts in a corner of Sn and terminateswitha completely labelled primitive set yielding an approximatefixed point.An essential part of Scarf’s algorithm is the unique replacementstep by which it can be proved that the algori thm always terminates wi thina finite number of steps. This proof is based on the work of Lemkeand How s on [lOJ, who developed an algorithm to compute an equilibriumstrategy for two person Bimatrix games. They used for the first timea combinatoral convergence argument.In 1968 Hansen improved Scarf’s algorithm by developing an efficientand simple scheme for the replacement step. Scarf’s algorithm andHansen’s further development are based on the notion of a ”primitive set” [13J.Almost all recent fixed point algorithms are based on the oldermathematical concept of a triangulation of a set. A good introductionfor fixed point algorithms is [14J. Recent developments and referenceson fixed point algorithms can be found in [6J.In 1974 [8J and 1976 [9J H.W. Kuhn published an algorithm forfinding all n roots of a polynomlal of degree n. His algorithm isbased on previous developments in fixed point algorithms.