Simplicial and continuation methods for approximating fixed points and solutions to systems of equations as well as their computational complexity problems are active topics ofrecent research.The starting point ofthe complexity theory in numerical methods in the elegant paper entitled "The fundamental theorem of algebra and complexity theory" by S.Smale.Since that,among others there are two main developments:complexity theories of simplical (or piecewise linear) homotopy methods and complexity theories of incremental algorithms or global Newton methods.This monograph provides a systemstical and self-contained presentation of the developments.Extra efforts have been paid upon its clarity. Researchers and postgraduate students interested in computational mathematics and computer science.
暂时还没有任何用户评论
全部咨询(共0条问答)
暂时还没有任何用户咨询内容
目录
Chpater 1 Kuhn's algorithm for algebraic equations §1.Triangulation and labelling §2.Complementary pivoting algorithm §3.Convergence,I §4.Convergence,II Chapter 2 Efficiency of Kuhn’S algorithm §1.Error estimate §2.Cost estimate §3.Monotonicity problem §4.Results on monotonicity Chapter 3 Newton method and approximate zeros §1.Approximate zeros §2.Coefficients of polynomials §3. One step of Newton iteration §4.Conditions for approximate zeros Chapter 4 A complexity comparison of Kuhn's algorithm and Newton method §1.Smale’S work on the complexity of Newton method §2.Set of bad polynomials and its volume estimate §3.Locate approximate zeros by Kuhn's algorithm §4.Some remarks Chapter 5 Incremental algorithms and cost theory §1. Incremental algorithms Ih,f §2.Euler's algorithm is of efficiency k §3.Generalized approximate zeros §4.Ek iteration §5.Cost theory of Ek as an Euler's algorithm §6.Incremental algorithms of efficiency k Chapter 6 Homotopy algorithms §1. Homotopies and Index Theorem §2. Degree and its invariance §3. Jacobian of polynomial mappings §4. Conditions for boundedness of solutions Chapter 7 Probabilistic discussion on zeros of polynomial mappings §1. Number of zeros of polynomial mappings §2.Isolated zeros §3.Locating zeros of analytic functions in bounded regions Chapter 8 Piecewise linear algorithms §1.Zeros of PL mapping and their indexes §2.PL approximations §3.PL homotopy algorithms work with probability one References Index Acknowledgments