On the convergence of Newton's method for monotone systems of polynomial equations
On the convergence of Newton's method for monotone systems of polynomial equations
复制标题
论多项式方程单调系统牛顿法的收敛性
DOI：
10.1145/1250790.1250822
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
J. Esparza
中科院分区：
文献类型：
--
作者：
S. Kiefer;Michael Luttenberger;J. Esparza
多项式方程的单调系统（MSPE）是固定点方程X1 = f1（X1，...，Xn），...，Xn = fn（X1，...，其中每个fi是具有正的真实的系数的多项式。计算给定MSPE X = f（X）的最小非负解的问题自然出现在随机上下文无关文法、递归马尔可夫链和概率下推自动机的分析中。而Kleene序列f（0），f（f（0）），.总是收敛到最小解μ.f，如果它存在，计算μ.f的前i位所需的迭代次数可能在i中呈指数增长。Etessami和Yannakakis最近将牛顿的迭代方法应用于MSPE，并证明牛顿序列的收敛速度至少与Kleene序列一样快，并且在许多情况下呈指数增长。他们推测，给定大小为m的MSPE，获得μ f的i个精确比特所需的牛顿迭代次数在i和m中多项式增长。在本文中，我们表明，迭代次数线性增长的强连接MSPE的i和一般MSPE的m可能呈指数增长。
Monotone systems of polynomial equations (MSPEs) are systems of fixed-point equations X1 = f1(X1, ..., Xn), ..., Xn = fn(X1, ..., Xn) where each fi is a polynomial with positive real coefficients. The question of computing the least non-negative solution of a given MSPE X = f(X) arises naturally in the analysis of stochastic context-free grammars, recursive Markov chains, and probabilistic pushdown automata. While the Kleene sequence f(0), f(f(0)), ... always converges to the least solution mu.f, if it exists, the number of iterations needed to compute the first i bits of mu.f may grow exponentially in i.Etessami and Yannakakis have recently adapted Newton's iterative method to MSPEs and proved that the Newton sequence converges at least as fast as the Kleene sequence and exponentially faster in many cases.They conjecture that, given an MSPE of size m, the number of Newton iterations needed to obtain i accurate bits of mu.f grows polynomially in i and m. In this paper we show that the number of iterations grows linearly in i for strongly connected MSPEs and may grow exponentially in m for general MSPEs.
日本儿童和学生对 TIMSS 科学论文式任务的反应特征 (7) - 9 项任务分析结果的趋势 -
DOI：
--
发表时间：
2005
期刊：
日本科学教育学会年会論文集 第29号
影响因子：
--
作者：
中山 迅;大場裕子;猿田祐嗣
通讯作者：
猿田祐嗣