Convergence Thresholds of Newton's Method for Monotone Polynomial Equations
Convergence Thresholds of Newton's Method for Monotone Polynomial Equations
复制标题
单调多项式方程牛顿法的收敛阈值
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Michael Luttenberger
中科院分区：
文献类型：
--
作者：
J. Esparza;S. Kiefer;Michael Luttenberger
多项式方程的单调系统（MSPE）是
不动点方程$X_1 = f_1（X_1，ldots，X_n），$ $ldots，X_n =
f_n（X_1，ldots，X_n）$其中每个$f_i$是一个多项式，
正的真实的系数。计算最少的问题
给定MSPE的非负解$vec X = vec f（vec X）$
在分析随机模型时自然出现，例如
随机上下文无关文法，概率下推自动机，
和后退按钮过程。Etessami和Yannakakis最近
将牛顿迭代法应用于MSPE。在以前的论文中，
我证明了存在一个阈值$k_{vec f}$为强
连接的MSPE，使得在$k_{vec f}$次迭代之后，
牛顿方法每次新的迭代计算至少1个新的比特，
解决方案然而，证明是纯粹存在的。在这
本文我们给出了一个上界$k_{vec f}$作为函数的
最小不动点的极小分支
f（vec X）$.利用这个结果，我们证明了$k_{vec f}$至多是
单指数响应强连通MSPE的线性
分别从概率下推自动机导出。从
后退按钮过程。此外，我们证明了存在一个
任意MSPE的阈值，在此之后，每次新迭代
计算解的至少$1/w2^h$新位，其中$w$和
$h$是强连通DAG的宽度和高度
件.
Monotone systems of polynomial equations (MSPEs) are systems of
fixed-point equations $X_1 = f_1(X_1, ldots, X_n),$ $ldots, X_n =
f_n(X_1, ldots, X_n)$ where each $f_i$ is a polynomial with
positive real coefficients. The question of computing the least
non-negative solution of a given MSPE $vec X = vec f(vec X)$
arises naturally in the analysis of stochastic models such as
stochastic context-free grammars, probabilistic pushdown automata,
and back-button processes. Etessami and Yannakakis have recently
adapted Newton's iterative method to MSPEs. In a previous paper we
have proved the existence of a threshold $k_{vec f}$ for strongly
connected MSPEs, such that after $k_{vec f}$ iterations of
Newton's method each new iteration computes at least 1 new bit of
the solution. However, the proof was purely existential. In this
paper we give an upper bound for $k_{vec f}$ as a function of the
minimal component of the least fixed-point $muvec f$ of $vec
f(vec X)$. Using this result we show that $k_{vec f}$ is at most
single exponential resp. linear for strongly connected MSPEs
derived from probabilistic pushdown automata resp. from
back-button processes. Further, we prove the existence of a
threshold for arbitrary MSPEs after which each new iteration
computes at least $1/w2^h$ new bits of the solution, where $w$ and
$h$ are the width and height of the DAG of strongly connected
components.
影响因子：
14.9
作者：
SAKAKIBARA, Y;BROWN, M;HAUSSLER, D
通讯作者：
HAUSSLER, D