自由项在W_1~r([0,1])上的第二类Fredholm积分方程的计算复杂性

本文研究了近似求解自由项f∈W_1([0,1])的第二类Fredholm积分方程u-T_ku=f的计算复杂性.首先,证明此问题的第n信息半径具有弱渐近式r(n)=θ(n～(-r))(n→∞).然后证明了利用f与次数为k的有限元子空间的基的内积为信息的有限元方法(FEM)具有几乎最优误差的充要条件是k≥r-1.在这两个结果的基础上得出如下结论:问题的固有ε复杂性为comp(ε)=θ(ε～(-1/r))(ε→0+),而FEM的ε复杂性为FEM(ε)=θ(ε~(-1/μ))(ε→0+),其中μ=min(k+1,r).对于f∈W_p~r([0,1])(1相似文献   

Viscoelastic properties of amorphous polymers. 5. A coupling model analysis of the thermorheological complexity of polyisobutylene in the glass-rubber softening dispersion

Isothermal data of high molecular weight polyisobutylene obtained by mechanical measurements with a spectral range over eight decades and additional photon correlation measurements have found that there are three distinct viscoelastic mechanisms in the glass-rubber transition zone. Theoretical considerations have helped to identify these three mechanisms to originate separately from local segmental (α) modes, sub-Rouse (sR) modes, and Rouse (R) modes. The temperature dependences of the shift factors of these mechanisms, a_T,α, a_T,sR and a_T,R, determined over a common temperature range are found to be all different. The differences in temperature dependences are explained quantitatively by the coupling model. The local segmental motion contributes to compliances ranging from the glassy compliance, J_g, up to 10^−8.5 Pa⁻¹. The sub-Rouse modes contribute in the compliance range, 10^−8.5 ≤ J(t) ≤ 10⁻⁷ Pa⁻¹. The Rouse modes account for the compliances in the range of 10⁻⁷ Pa⁻¹ ≤ J(t) ≤ J_plateau, where J_plateau is the plateau compliance. The magnitudes of the bounds given here are only rough estimates. Shift factors, a_T, obtained by time-temperature superpositioning of viscoelastic data taken in the softening transition over a limited experimental window are shown to be a combination of the three individual shifts factors, a_T,α, a_T,sR, and a_T,R. Consequently, care must be exercised in interpreting or using the WLF equation that fits the shift factors of the entire softening dispersion, because the latter do not describe the temperature dependence of any one of the three viscoelastic mechanisms. © 1997 John Wiley & Sons, Inc. J Polym Sci B: Polym Phys, 35: 599–614, 1997     

The Computational Complexity of Sandpiles

Journal of Statistical Physics - Given an initial distribution of sand in an Abelian sandpile, what final state does it relax to after all possible avalanches have taken place? In d≥3, we...     

An analytical study of a periodically driven laser with a saturable absorber

We consider the rate equations for a laser with an intracavity saturable absorber and subject to a periodically modulated pump. By deriving simplified equations for a map valid for strongly pulsating regimes, analytical conditions are determined that specify the properties of both frequency-locked and unlocked behaviors. As the strength of the modulation is increased, quasiperiodic and period-doubling bifurcations are predicted. However, only the transition from locking to non-locking through a quasiperiodic bifurcation is possible for realistic values of the parameters. Our results are consistent with previous numerical and experimental studies of modulated lasers with a saturable absorber. Received 10 March 2001     

Uniform Families of Polynomial Equations Over a Finite Field and Structures Admitting an Euler Characteristic of Definable Sets

Over a fixed finite field F_p, families of polynomial equations for i = 1,..., k_N, that areuniformly determined by a parameter N, are considered. The notionof a uniform family is defined in terms of first-order logic.A notion of an abstract Euler characteristic is used to givesense to a statement that the system has a solution for infiniteN, and a statement linking the solvability of a linear systemfor infinite N with its solvability for finite N is proved.This characterisation is used to formulate a criterion yieldingdegree lower bounds for various ideal membership proof systems(for example, Nullstellensatz and the polynomial calculus).Further, several results about Euler structures (structureswith an abstract Euler characteristic) are proved, and the caseof fields, in particular, is investigated more closely. 1991Mathematics Subject Classification: primary 03F20, 12L12, 15A06;secondary 03C99, 12E12, 68Q15, 13L05.     

Polynomial convergence of primal-dual algorithms for the second-order cone program based on the MZ-family of directions

In this paper we study primal-dual path-following algorithms for the second-order cone programming (SOCP) based on a family of directions that is a natural extension of the Monteiro-Zhang (MZ) family for semidefinite programming. We show that the polynomial iteration-complexity bounds of two well-known algorithms for linear programming, namely the short-step path-following algorithm of Kojima et al. and Monteiro and Adler, and the predictor-corrector algorithm of Mizuno et al., carry over to the context of SOCP, that is they have an O( logε^-1) iteration-complexity to reduce the duality gap by a factor of ε, where n is the number of second-order cones. Since the MZ-type family studied in this paper includes an analogue of the Alizadeh, Haeberly and Overton pure Newton direction, we establish for the first time the polynomial convergence of primal-dual algorithms for SOCP based on this search direction. Received: June 5, 1998 / Accepted: September 8, 1999?Published online April 20, 2000     

一类变工时的单机排序问题

提出了一类可变加工时间的单台机器排序问题,着重考虑如下的目标函数：最小化工件排序长度、完工时间之和误工工件数等等,且用受束的等规模划分问题证明了可变加工时间的单台机器排序问题是ＮＰ－完全的。     

基于自组织理论的GMDH神经网络算法及应用

本文在自组织控制论的基础上提出了成组数据处理的神经网络算法— GMDH算法 ,通过寻找最优复杂性 ,实现变量的自动筛选并得到明确的模型结构 .文章还给出了 GMDH网络用于分析和预测四川省电力需求状况的一个实例     

A Minimal-Automaton-Based Algorithm for the Reliability of Con(d,k, n) Systems

A d-within-consecutive-k-out-of-n system, abbreviated as Con(d, k, n), is a linear system of n components in a line which fails if and only if there exists a set of k consecutive components containing at least d failed ones. So far the fastest algorithm to compute the reliability of Con(d, k, n) is Hwang and Wright's algorithm published in 1997, where . In this paper we use automata theory to reduce to . For d small or close to k, we have reduced from exponentially many (in k) to polynomially many. The computational complexity of our final algorithm is , where .     

组织智能与组织生存能力

从宏观的角度，组织具有有机生命物的特征，不但能够对外界环境的变化和刺激能够作出反应。而且还能意识到环境的变化并预先作出某种安排。即，体现出某种智能特性。在激烈的竞争和复杂多变的环境中组织如何能够生存下来并取得发展的问题，一直得到管理科学学的密切关注，也是研究的热点之一。按照复杂科学和当代管理科学的理论，并结合心理科学领域中的一般智能理论，本讨论了组织智能的一些理论基础，初步探讨了组织智能与组织生存的关系。