超乎想象的"幂"结果

有这样一个问题:有一种细菌每20分钟分裂1次,9个小时后,它能分裂出多少个?初次看到这个题目的我不假思索地想道:"能有多少个呢!"虽然此时心里还没有具体的计算过程,但我想它的结果应该不会很大.可事实并非如此,且看下面的分析过程和计算结果.     

求解PageRank问题改进的多分裂迭代法

引用两种加速计算PageRank的算法,分别为内外迭代法和多分裂迭代算法.从这两种方法中,得到改进的多分裂迭代方法.首先,详细介绍了算法实施过程.然后,对此算法的收敛性进行证明,并且将此算法的谱半径与原有的多分裂迭代算法的谱半径进行比较.最后,数值实验说明我们的算法的计算速度比原有的多分裂迭代法要快.     

一种求解两两合作轮流博弈问题的混合分裂算法

提出了一种求解两两合作轮流博弈的四人博弈问题的混合分裂算法.为了模拟实际博弈过程,该算法由两个组内平行分裂算法和一个组间交替极小化算法构成.算法允许对博弈子问题非精确求解,反映了实际博弈中参与人的有限理性,即允许参与人在博弈过程中出现满足一定条件的误差.在适当条件下,证明了所提出的混合分裂算法全局地收敛到所考虑博弈的Nash平衡.     

两个油藏模型特征数值模拟算法的结果比较

使用双Level Set方法重新表示油藏模型特征中的渗透率,并且渗透率可以通过解一个转化过的最优化问题得到.这个最优化问题是一个无限制的Lagrangian型鞍点问题.在复杂区域的数值模拟表明使用算子分裂格式的Uzawas算法解这个鞍点问题比使用梯度下降格式的Uzawas算法高效稳定.     

方向选择约束单纯形算法

一、引言人们一直致力于求解线性规划的单纯形算法的改进工作.1976年,Powell 发表过降低基维数的改进单纯形算法,这个算法是将基矩阵的一个块用基矩阵的其它块的乘积来表示,虽然实现了降低基维数,节省了存贮空间,却增加了计算次数,减慢了计算速度.Sethi and Thompson 针对线性规划问题也提出过竞争和非竞争约束(candidate andnoncandidate constraints)的概念.他们发现,随机生成的实验问题,其总约束中大约只有15%—25%是竞争约束,并提出了一个仅对竞争约束进行旋转运算的单纯形算法.他们的算法,对某些特殊的线性规划提高了求解速度,但并不减少基的维数,并不节省内存空间,增加了程序复杂性.1984年,Sethi and Thompson 又提出 PAPA 算法,再次利用线性规划问题通常只有少量竞争约束这个事实来提高求解速度.但 PAPA 算法往往要在原问题的可行域外运行.况且,上面提到的各种算法,均不能从理论上表明,它们较标准改进单纯形算法到底节省了多少存贮单元和节省了多少计算次数.     

求解PageRank问题的多步幂法修正的内外迭代法

引用两种加速计算PageRank的算法,分别为内外迭代法和两步分裂迭代算法.从这两种方法中,得到多步幂法修正的内外迭代方法.首先,详细介绍了算法实施过程.然后,对此算法的收敛性进行证明,并且将此算法的谱半径与两步分裂迭代算法的谱半径进行比较.最后,数值试验说明该算法的计算速度比两步分裂迭代法要快.     

单体型装配问题及其算法

单核苷酸多态性(SNP)单体型装配问题就是从给定的来自某人染色体的SNP片段中去除错误,重构出尽可能与原来片段一致的单体型.这个问题有几个不同的模型最少片段去除(MFR)问题,最少SNP去除(MSR)问题以及最少错误纠正(MEC)问题.前两个问题的复杂性与算法已有一些学者研究过.第三个问题已被证明是NP完全问题,但这个问题的实际算法还没有.该文对MEC问题给出了一个分支定界算法,这个算法能得到问题的全局最优解.通过这个算法对实际数据的计算说明了MEC模型的合理性,即在一定条件下,通过修正最少的错误重构出的单体型确实是真实的单体型.由于分支定界算法对这样一个NP完全问题不能在可接受的时间内解规模较大的问题,文中又给出了求解MEC问题的两个基于动态聚类的算法,以便对规模较大的问题在可接受的时间内得到近似最优解.数值实际表明这两个算法很快,很有效.这两个算法总能得到与分支定界找到的全局最优解很接近的近似最优解.鉴于MEC问题是NP完全的,这两个算法是有效的、实际的算法.     

非光滑最优控制问题的一种数值解法

针对非光滑最优控制问题提出一种分段数值解法.首先对问题进行全局拟谱离散,然后选取分点,将时间区域进行剖分,在每段区域上对问题进行离散,离散过程采用Chebyshev-Legendre拟谱方法,可以有效借助快速Legendre变换提高算法的运算效率,比现有算法在很大程度上节省了计算时间.给出了相关的理论分析,数值结果表明方法的高精度和有效性.     

多集分裂等式问题的逐次松弛投影算法

多集分裂等式问题是分裂可行性问题的拓展问题,在图像重建、语言处理、地震探测等实际问题中具有广泛的应用.为了解决这个问题,提出了逐次松弛投影算法,设计了变化的步长,使其充分利用当前迭代点的信息且不需要算子范数的计算,证明了算法的弱收敛性.数值算例验证了算法在迭代次数与运行时间等方面的优越性.     

一种求解合作博弈最公平核心的非精确平行分裂算法

针对合作博弈核心和Shapley值的特点, 将最公平核心问题转化为带有两个变 量的可分离凸优化问题, 引入结构变分不等式的算子分裂方法框架, 提出了求解最公平核心的一种非精确平行分裂算法. 而且, 该算法充分利用了所求解问题的可行域的简单闭凸性, 子问题的非精确求解是容易的. 最后, 简单算例的数值实验表明了算法的收敛性和有效性.     

Graeffe's, Chebyshev-like, and Cardinal's Processes for Splitting a Polynomial into Factors

Numerical splitting of a real or complex univariate polynomial into factors is the basic step of the divide-and-conquer algorithms for approximating complex polynomial zeros. Such algorithms are optimal (up to polylogarithmic factors) and are quite promising for practical computations. In this paper, we develop some new techniques, which enable us to improve numerical analysis, performance, and computational cost bounds of the known splitting algorithms. In particular, we study a Chebyshev-like modification of Graeffe's lifting iteration (which is a basic block of the splitting algorithms, as well as of several other known algorithms for approximating polynomial zeros), analyze its numerical performance, compare it with Graeffe's, prove some results on numerical stability of both lifting processes (that is, Graeffe's and Chebyshev-like), study their incorporation into polynomial root-finding algorithms, and propose some improvements of Cardinal's recent effective technique for numerical splitting of a polynomial into factors. Our improvement relies, in particular, on a modification of the matrix sign iteration, based on the analysis of some conformal mappings of the complex plane and of techniques of recursive lifting/recursive descending. The latter analysis reveals some otherwise hidden correlations among Graeffe's, Chebyshev-like, and Cardinal's iterative processes, and we exploit these correlations in order to arrive at our improvement of Cardinal's algorithm. Our work may also be of some independent interest for the study of applications of conformal maps of the complex plane to polynomial root-finding and of numerical properties of the fundamental techniques for polynomial root-finding such as Graeffe's and Chebyshev-like iterations.     

Some issues related to double rounding

Double rounding is a phenomenon that may occur when different floating-point precisions are available on the same system. Although double rounding is, in general, innocuous, it may change the behavior of some useful small floating-point algorithms. We analyze the potential influence of double rounding on the Fast2Sum and 2Sum algorithms, on some summation algorithms, and Veltkamp’s splitting.     

On splitting schemes in the mixed finite element method

Within the research into some geothermal modes, a 3D heat transfer process was described by a first-order system of differential equations (in terms of “temperature-heat-flow”). This system was solved by an explicit scheme for the mixed finite element spatial approximations based on the Raviart-Thomas degrees of freedom. In this paper, several algorithms based on the splitting technique for the vector heat-flow equation are proposed. Some comparison results of accuracy of the algorithms proposed are presented.     

A Class of Fejér Convergent Algorithms,Approximate Resolvents and the Hybrid Proximal-Extragradient Method

A new framework for analyzing Fejér convergent algorithms is presented. Using this framework, we define a very general class of Fejér convergent algorithms and establish its convergence properties. We also introduce a new definition of approximations of resolvents, which preserves some useful features of the exact resolvent and use this concept to present an unifying view of the Forward-Backward splitting method, Tseng’s Modified Forward-Backward splitting method, and Korpelevich’s method. We show that methods, based on families of approximate resolvents, fall within the aforementioned class of Fejér convergent methods. We prove that such approximate resolvents are the iteration maps of the Hybrid Proximal-Extragradient method, which is a generalization of the classical Proximal Point Algorithm.     

一种求解鞍点问题的广义对称超松弛迭代法

本文研究了鞍点问题的迭代算法.利用新的待定参数加速迭代格式并结合SSOR分裂的方法,获得了有两个参数的广义对称超松弛迭代法及其收敛性条件.数值例子表明选择适当的参数值可以提高算法的收敛效率,推广和改进了SOR-like迭代法.     

Splitting Patterns and Invariants of Quadratic Forms

Let φ be an anisotropic quadratic form over a field F of characteristic not 2. The splitting pattern of φ is defined to be the increasing sequence of nonnegative integers obtained by considering the Witt indices i_W(φ_k) of φ over K where K ranges over all field extensions of F. Restating earlier results by HURRELBRINK and REHMANN , we show how the index of the Clifford algebra of φ influences the splitting pattern. In the case where F is formally real, we investigate how the signatures of φ influence the splitting behaviour. This enables us to construct certain splitting patterns which have been known to exist, but now over much “simpler” fields like formally real global fields or ?(t). We also give a full classification of splitting patterns of forms of dimension less than or equal to 9 in terms of properties of the determinant and Clifford invariant. Partial results for splitting patterns in dimensions 10 and 11 are also provided. Finally, we consider two anisotropic forms φ and φ of the same dimension m with φ ? ? φ ∈ Iⁿ F and give some bounds on m depending on n which assure that they have the same splitting pattern.     

The modulus‐based matrix splitting algorithms for a class of weakly nonlinear complementarity problems

In this paper, we study a class of weakly nonlinear complementarity problems arising from the discretization of free boundary problems. By reformulating the complementarity problems as implicit fixed‐point equations based on splitting of the system matrices, we propose a class of modulus‐based matrix splitting algorithms. We show their convergence by assuming that the system matrix is positive definite. Moreover, we give several kinds of typical practical choices of the modulus‐based matrix splitting iteration methods based on the different splitting of the system matrix. Numerical experiments on two model problems are presented to illustrate the theoretical results and examine the numerical effectiveness of our modulus‐based matrix splitting algorithms. Copyright © 2016 John Wiley & Sons, Ltd.     

Splitting extragradient-like algorithms for strongly pseudomonotone equilibrium problems

In this paper, two splitting extragradient-like algorithms for solving strongly pseudomonotone equilibrium problems given by a sum of two bifunctions are proposed. The convergence of the proposed methods is analyzed and the R-linear rate of convergence under suitable assumptions on bifunctions is established. Moreover, a noisy data case, when a part of the bifunction is contaminated by errors, is studied. Finally, some numerical experiments are given to demonstrate the efficiency of our algorithms.     

The method of fractional steps for conservation laws

Summary The stability, accuracy, and convergence of the basic fractional step algorithms are analyzed when these algorithms are used to compute discontinuous solutions of scalar conservation laws. In particular, it is proved that both first order splitting and Strang splitting algorithms always converge to the unique weak solution satisfying the entropy condition. Examples of discontinuous solutions are presented where both Strang-type splitting algorithms are only first order accurate but one of the standard first order algorithms is infinite order accurate. Various aspects of the accuracy, convergence, and correct entropy production are also studied when each split step is discretized via monotone schemes, Lax-Wendroff schemes, and the Glimm scheme.Partially supported by an Alfred Sloan Foundation fellowship and N.S.F. grant MCS-76-10227Sponsored by US Army under contract No. DAA 629-75-0-0024     

Idempotent Block Splitting on Partial Partitions,I: Isotone Operators

Image segmentation algorithms can be modelled as image-guided operators (maps) on the complete lattice of partitions of space, or on the one of partial partitions (i.e., partitions of subsets of the space). In particular region-splitting segmentation algorithms correspond to block splitting operators on the lattice of partial partitions, in other words anti-extensive operators that act by splitting each block independently. This first paper studies in detail block splitting operators and their lattice-theoretical and monoid properties; in particular we consider their idempotence (a requirement in image segmentation). We characterize block splitting openings (kernel operators) as operators splitting each block into its connected components according to a partial connection; furthermore, block splitting openings constitute a complete sublattice of the complete lattice of all openings on partial partitions. Our results underlie the connective approach to image segmentation introduced by Serra. The second paper will study two classes of non-isotone idempotent block splitting operators, that are also relevant to image segmentation.