大型稀疏无约束最优化的列分划校正Cholesky因子算法

我们考虑求解无约束优化问题1引言(?)f(x),(1)其中f：D(?)R~n→R为R~n上的二次连续可微函数,且f(x)的二阶Hesse阵H(x)稀疏、正定．为了求解问题(1),我们考虑下列Newton型方法x~(k 1)=x~k-(B~k)~(-1)▽f(x~k),k=0,1,…,(2)其中B~k是和Hesse阵H(x~k)具有相同稀疏性的近似．由于Hesse阵对称,我们假定B~k对称．为了具体说明给定矩阵B的稀疏性,我们使用M来定义指标对(i,j)的集合,其     

求複數根的舗D法

<正> 一. 引言 代數方程f(x)=0的實數根的逐步接近法已有多種,其中計算簡單收斂最快的是用牛頓公式     

A novel fast overrelaxation updating method for continuous-discontinuous cellular automaton

Because of its local property, cellular automaton method has been widely applied in different subjects, but the main problem is that the cellular updating is time-consuming. In order to improve its calculation efficiency, a fast successive relaxation updating method is proposed in this paper. Firstly, an accelerating factor ω is defined, and a fast successive relaxation updating theory and its corresponding convergence conditions are developed. In each updating step, the displacement increment is enlarged ω times as a new increment to replace the old one, similarly, the nodal forces for its neighbors caused by this displacement increment are also enlarged by the same accelerating factor, and do those updating operations until the convergence is achieved. By this method, the convergence rate is greatly improved, by a suitable accelerating factor, 90 to 98% of iteration steps are decreased compared to that of the traditional method. Besides, the influence factors for the accelerating factor are studied, and numerical studies show that the suitable accelerating factor is 1.85 < ω < 1.99, which is greatly influenced by cell stiffness, and the optimal accelerating factor is 1.96 < ω < 1.99. Finally, numerical examples are given to illustrate that the present method is effective and high convergence rate compared to the traditional method.     

一类预条件AOR迭代法及其收敛性

给出了一类预条件的AOR迭代法及其收敛性,并给出了松驰因子ω与加速因子γ的选取对收敛速度的影响,同时通过数值实例验证了主要结果.     

Convergence analysis of multigrid methods with residual scaling techniques

In this paper, multigrid methods with residual scaling techniques for symmetric positive definite linear systems are considered. The idea of perturbed two-grid methods proposed in [7] is used to estimate the convergence factor of multigrid methods with residual scaled by positive constant scaling factors. We will show that if the convergence factors of the two-grid methods are uniformly bounded by σ (σ<0.5), then the convergence factors of the W-cycle multigrid methods are uniformly bounded by σ/(1−σ), whether the residuals are scaled at some or all levels. This result extends Notay’s Theorem 3.1 in [7] to more general cases. The result also confirms the viewpoint that the W-cycle multigrid method will converge sufficiently well as long as the convergence factor of the two-grid method is small enough. In the case where the convergence factor of the two-grid method is not small enough, by appropriate choice of the cycle index γ, we can guarantee that the convergence factor of the multigrid methods with residual scaling techniques still has a uniform bound less than σ/(1−σ). Numerical experiments are provided to show that the performance of multigrid methods can be improved by scaling the residual with a constant factor. The convergence rates of the two-grid methods and the multigrid methods show that the W-cycle multigrid methods perform better if the convergence rate of the two-grid method becomes smaller. These numerical experiments support the proposed theoretical results in this paper.     

三维Poisson方程的一个块松弛法

在许多物理、工程问题中,都涉及到Poisson方程的数值求解。在二维情形,人们已经对规则区域研究出一些快速求解方法(如快速富氏变换,循环约简算法等)。这些算法具有稳定、计算量小等优点。特别是循环约简算法,更充分地体现了这些优点。我们曾在每秒五万次左右的机器上用此方法求解了1200多阶的方程组,仅用50秒便得准确结果,足见其计算量之少。但如何将此方法应用于一般区域,尚待进一步研究。在将循环约简     

Proximal Methods in View of Interior-Point Strategies

This paper deals with regularized penalty-barrier methods for convex programming problems. In the spirit of an iterative proximal regularization approach, an interior-point method is constructed, in which at each step a strongly convex function has to be minimized and the prox-term can be scaled by a variable scaling factor. The convergence of the method is studied for an axiomatically given class of barrier functions. According to the results, a wide class of barrier functions (in particular, logarithmic and exponential functions) can be applied to design special algorithms. For the method with a logarithmic barrier, the rate of convergence is investigated and assumptions that ensure linear convergence are given.     

一类各向异性外问题的非重叠型区域分解算法

In this paper, based on the natural integral operator on elliptic boundary, a nonoverlapping domain decomposition method is presented for a kind of anisotropic elliptic problem with constant coefficients in an exterior domain, and the convergence of the method is analyzed. The choice of the relaxition factor is discussed.Some numerical examples are given. Theoretical analysis as well as numerical examples show that our method is performance.     

关于PageRank的广义二级分裂迭代方法

本文研究计算PageRank的迭代法,在Gleich等人提出的内/外迭代方法的基础上,提出了具有三个参数的广义二级分裂迭代法,该方法包含了内/外迭代法和幂迭代法,并研究了该方法的收敛性.基于该方法的收缩因子的计算公式,讨论了迭代参数可能的选择,通过参数的选择能有效提高内/外迭代法的收敛效率.     

关于加权差分方法的一点注记

在这篇短文中,对奇异摄动问题引进了新的差分逼近并证明了一致收敛的必要条件。选择适当的权因子可得到用Ilin方法所得的相同的差分格式。     

一种改进灰狼优化算法研究及应用

针对灰狼算法易陷入局部最优、收敛精度不高、收敛速度慢等缺点,提出一种改进的灰狼算法.引入莱维飞行,扩大搜索范围,增强全局搜索能力,避免陷入局部最优;引入贪婪原理,提升种群优良性以提高算法收敛精度;引入自适应收敛因子,加快收敛速度;引入动态权重策略,制约全局搜索与局部搜索的相互影响.将改进算法与其他四种算法作对比,实验表明,改进算法在收敛速度与收敛精度上都有更好的性能.最后,应用于图像多阈值分割中,采用GWO-Otsu法可以克服传统Otsu法在多阈值分割时计算量大,实时性差的特点,不但能够取得最优解,且明显缩减计算时间.     

A Note on a Practical Technique for Solving Elliptic Equations

In this paper, we propose a new method which is the SOR methodwithout the knowledge of the optimum accelerating factor, andthis method is compared with the optimum SOR method concernedwith the convergence rate.     

On SSOR iteration method for a class of block two-by-two linear systems

In this paper, the optimal iteration parameters of the symmetric successive overrelaxation (SSOR) method for a class of block two-by-two linear systems are obtained, which result in optimal convergence factor. An accelerated variant of the SSOR (ASSOR) method is presented, which significantly improves the convergence rate of the SSOR method. Furthermore, a more practical way to choose iteration parameters for the ASSOR method has also been proposed. Numerical experiments demonstrate the efficiency of the SSOR and ASSOR methods for solving a class of block two-by-two linear systems with the optimal parameters.     

Self-Adaptive Extrapolated Gauss-Seidel Iterative Methods

In this paper, we consider a self-adaptive extrapolated Gauss-Seidel method for solving the Hermitian positive definite linear systems. Based on optimization models, self-adaptive optimal factor is given. Moreover, we prove the convergence of the self-adaptive extrapolated Gauss-Seidel method without any constraints on optimal factor. Finally, the numerical examples show that the self-adaptive extrapolated Gauss-Seidel method is effective and practical in iteration number.     

无界区域Stokes 问题非重叠型区域分解算法及其收敛性

本文研究无界区域Stokes方程外问题的利用有限元法和自然边界归化的非蕈叠型区域分解算法,此方法对无界区域Stokes问题非常有效.给出连续和离散情形的D-N算法及其收敛性分析,得到算法收敛的充要条件及充分条件,并得到最优的松弛因子和压缩因子,最后给出数值算例予以验证.     

无界区域上基于自然边界归化的一种区域分解算法

无界区域上基于自然边界归化的一种区域分解算法余德浩（中国科学院计算中心）ＡＤＯＭＡＩＮＤＥＣＯＭＰＯＳＩＴＩＯＮＭＥＴＨＯＤＢＡＳＥＤＯＮＴＨＥＮＡＴＵＲＡＬＢＯＵＮＤＡＲＹＲＥＤＵＣＴＩＯＮＯＶＥＲＵＮＢＯＵＮＤＥＤＤＯＭＡＩＮ￥ＹｕＤｅ－ｈａｏ（...     

On the geometric convergence of optimized Schwarz methods with applications to elliptic problems

The Schwarz method can be used for the iterative solution of elliptic boundary value problems on a large domain Ω. One subdivides Ω into smaller, more manageable, subdomains and solves the differential equation in these subdomains using appropriate boundary conditions. Optimized Schwarz Methods use Robin conditions on the artificial interfaces for information exchange at each iteration, and for which one can optimize the Robin parameters. While the convergence theory of classical Schwarz methods (with Dirichlet conditions on the artificial interface) is well understood, the overlapping Optimized Schwarz Methods still lack a complete theory. In this paper, an abstract Hilbert space version of the Optimized Schwarz Method (OSM) is presented, together with an analysis of conditions for its geometric convergence. It is also shown that if the overlap is relatively uniform, these convergence conditions are met for Optimized Schwarz Methods for two-dimensional elliptic problems, for any positive Robin parameter. In the discrete setting, we obtain that the convergence factor ρ(h) varies like a polylogarithm of h. Numerical experiments show that the methods work well and that the convergence factor does not appear to depend on h.     

关于Schwarz交替法的拟边界松弛方法

§1.松弛方法 我们讨论二阶自共轭椭圆型方程的Dirichlet问题.设Ω?R~2为一多边形区域. a(u,v)=(f,v),v∈H_0~1(Ω),f∈H~(-1)(Ω), u∈H_0~1(Ω)是定义在其上的边值问题的变分形式,这里取齐次边界条件仅为叙述问题方便.双线性型a(·,·)满足:     

Radius of analyticity and exponential convergence for spectral projections of the generalized KdV equation

In this paper an exponential convergence rate for a spectral projection of the periodic initial-value problem for the generalized KdV equation is proved. Based on this convergence result, a method for determining the radius of analyticity of solutions of the generalized KdV equation is derived. Results from the new method and a similar method are compared.     

关于Brown方法的半局部收敛性

在本文中,我们讨论解非线性方程组的Brown方法的半局部收敛性。通过对Brown方法的算法结构作深入的分析,我们将Brown方法变换成带有特殊误差项的近似Newton法,基于这种等价变形,我们建立了Brown方法的半局部收敛定理,从而完善了Brown方法的收敛理论。