非线性算子方程的泰勒展式算法

本文的目的是给出一种解Ｈｉｌｂｅｒｔ空间中非线性方程的ｋ阶泰勒展式算法（ｋ１）．标准Ｇａｌｅｒｋｉｎ方法可以看作１阶泰勒展式算法，而最优非线性Ｇａｌｅｒｋｉｎ方法可视为２阶泰勒展式算法．我们应用这种算法于定常的Ｎａｖｉｅｒ－Ｓｔｏｋｅｓ方程的数值逼近．在一定情景下，最优非线性Ｇａｌｅｒｋｉｎ方法提供比标准Ｇａｌｅｒｋｉｎ方法和非线性Ｇａｌｅｒｋｉｎ方法更高阶的收敛速度．     

基于遗传算法与牛顿法的联合算法在地表发射率反演中的应用

结合遗传算法全局高效搜索和牛顿法局部细致搜索的优势,充分利用一种算法的优点弥补另一种算法的不足,进而引入一种基于遗传算法和牛顿法的联合算法,并将联合算法应用于反演地表发射率的函数关系中.结果表明,联合算法中由遗传算法提供的初始值使得牛顿法下降的速度快,且很快趋于稳定,达到精度要求;而由任意初始值提供给牛顿法,目标函数下降到一定阶段后反而有所回升,然后才保持稳定,且经和联合算法迭代相同的次数后,目标函数的值仍然非常大,远远达不到要求.因此,从可行性、计算效率上看,联合算法均优于单纯的牛顿法,是一种性能稳定,计算高效的下降方法.     

A convergent multigrid cycle for the hybridized mixed method

We consider the application of a variable V‐cycle multigrid algorithm for the hybridized mixed method for second‐order elliptic boundary‐value problems. Our algorithm differs from the previous works on multigrid for the mixed method in that it is targeted at efficiently solving the matrix system for the Lagrange multiplier of the method. Since the mixed method is best implemented by first solving for the Lagrange multiplier and recovering the remaining unknowns locally, our algorithm is more useful in practice. The critical ingredient in the algorithm is a suitable intergrid transfer operator. We design such an operator and prove mesh‐independent convergence of the variable V‐cycle algorithm. Numerical experiments indicating the asymptotically optimal performance of our algorithm, as well as the failure of certain seemingly plausible intergrid transfer operators, are presented. Copyright © 2009 John Wiley & Sons, Ltd.     

Application of the dual active set algorithm to quadratic network optimization

A new algorithm, the dual active set algorithm, is presented for solving a minimization problem with equality constraints and bounds on the variables. The algorithm identifies the active bound constraints by maximizing an unconstrained dual function in a finite number of iterations. Convergence of the method is established, and it is applied to convex quadratic programming. In its implementable form, the algorithm is combined with the proximal point method. A computational study of large-scale quadratic network problems compares the algorithm to a coordinate ascent method and to conjugate gradient methods for the dual problem. This study shows that combining the new algorithm with the nonlinear conjugate gradient method is particularly effective on difficult network problems from the literature.     

服从OldroydB型微分模型的粘弹性流体问题的数值解法

本文对服从OldroydB型微分模型的粘弹性流体问题给出了一种数值逼近算法．该算法对压力方程采用标准混合有限元方法,对速度方程采用并行非重叠区域分解方法和特征线法．这种并行算法在子区域上用Galerkin方法,通过积分平均方法显式地给出内边界的数值流．在本文最后还给出了该算法的最优L^2。一误差估计．     

Accelerating the convergence in the single-source and multi-source Weber problems

The modified Weiszfeld method [Y. Vardi, C.H. Zhang, A modified Weiszfeld algorithm for the Fermat-Weber location problem, Mathematical Programming 90 (2001) 559-566] is perhaps the most widely-used algorithm for the single-source Weber problem (SWP). In this paper, in order to accelerate the efficiency for solving SWP, a new numerical method, called Weiszfeld-Newton method, is developed by combining the modified Weiszfeld method with the well-known Newton method. Global convergence of the new Weiszfeld-Newton method is proved under mild assumptions. For the multi-source Weber problem (MWP), a new location-allocation heuristic, Cooper-Weiszfeld-Newton method, is presented in the spirit of Cooper algorithm [L. Cooper, Heuristic methods for location-allocation problems, SIAM Review 6 (1964) 37-53], using the new Weiszfeld-Newton method in the location phase to locate facilities and adopting the nearest center reclassification algorithm (NCRA) in the allocation phase to allocate the customers. Preliminary numerical results are reported to verify the evident effectiveness of Weiszfeld-Newton method for SWP and Cooper-Weiszfeld-Newton method for MWP.     

Condition number based complexity estimate for computing local extrema

In this paper, we present a new algorithm for computing local extrema by modifying and combining algorithms in symbolic and numerical computation. This new algorithm improves the classical steepest descent method that may not terminate, by combining a Sturm’s theorem based separation method and a sufficient condition on infeasibility. In addition, we incorporate a grid subdivision method into our algorithm to approximate all local extrema. The complexity of our algorithm is polynomial in a newly defined condition number, and singly exponential in the number of variables.     

快速幂法子空间跟踪

子空间跟踪算法是许多工程计算问题的核心.Hua等人将计算特征值问题的幂法扩展为自然幂法子空间跟踪算法.在指出基于秩1矩阵更新的自然幂法的快速实现方案NP3不收敛的同时,应用矩阵求逆引理给出了一种新的快速子空间跟踪算法:快速幂法子空间跟踪算法.仿真实验表明,所提算法是收敛与稳定的,其性能优于或相当于几种常见的快速子空间跟踪算法.     

An Arnoldi-Extrapolation algorithm for computing PageRank

The Arnoldi-type algorithm proposed by Golub and Greif [G. Golub, C. Greif, An Arnoldi-type algorithm for computing PageRank, BIT 46 (2006) 759-771] is a restarted Krylov subspace method for computing PageRank. However, this algorithm may not be efficient when the damping factor is high and the dimension of the search subspace is small. In this paper, we first develop an extrapolation method based on Ritz values. We then consider how to periodically knit this extrapolation method together with the Arnoldi-type algorithm. The resulting algorithm is the Arnoldi-Extrapolation algorithm. The convergence of the new algorithm is analyzed. Numerical experiments demonstrate the numerical behavior of this algorithm.     

关于构造数学物理中非线性发展方程组孤波解的一种新算法

根据改进的sine-cosine法和吴文俊消元法,给出了一种构造非线性发展方程组孤波解的新算法。这种算法比已知的双曲函数法有更好的结论,并且在使用的过程中更简单。借助于MATH-EMATICA软件,这一算法能够在计算机上实现。     

TWO ALGORITHMS FOR SYMMETRIC LINEAR SYSTEMS WITH MULTIPLE RIGHT-HAND SIDES

1　ＩｎｔｒｏｄｕｃｔｉｏｎＩｎｍａｎｙａｐｐｌｉｃａｔｉｏｎｓｗｅｎｅｅｄｔｏｓｏｌｖｅｍｕｌｔｉｐｌｅｓｙｓｔｅｍｓｏｆｌｉｎｅａｒｅｑｕａｔｉｏｎｓＡｘ(ｉ) =ｂ(ｉ) ,ｉ=1,… ,ｓ (1)ｗｉｔｈｔｈｅｓａｍｅｎ×ｎｒｅａｌｓｙｍｍｅｔｒｉｃｃｏｅｆｆｉｃｉｅｎｔｍａｔｒｉｘＡ ,ｂｕｔｓｄｉｆｆｅｒｅｎｔｒｉｇｈｔ ｈａｎｄｓｉｄｅｓｂ(ｉ) (ｉ=1,… ,ｓ) .Ｉｆａｌｌｏｆｔｈｅｒｉｇｈｔ ｈａｎｄｓｉｄｅｓａｒｅａｖａｉｌａｂｌｅｓｉｍｕｌｔａｎｅｏｕｓｌｙ ,ｔｈｅｎｔｈｅｓｅｓｌｉｎｅａｒｓｙｓｔｅ…     

An approximate subgradient algorithm for unconstrained nonsmooth,nonconvex optimization

In this paper a new algorithm for minimizing locally Lipschitz functions is developed. Descent directions in this algorithm are computed by solving a system of linear inequalities. The convergence of the algorithm is proved for quasidifferentiable semismooth functions. We present the results of numerical experiments with both regular and nonregular objective functions. We also compare the proposed algorithm with two different versions of the subgradient method using the results of numerical experiments. These results demonstrate the superiority of the proposed algorithm over the subgradient method.      

一维流动的Boussinesq方程渗流系数反演的变分伴随方法研究

利用偏微分方程最优控制中的伴随方法讨论一维Boussinesq方程渗流系数反演问题的数值解法.吸收正则化思想改造最小二乘方法,利用变分伴随思想构造新迭代算法.迭代过程中首次搜索方向采用泛函下降最快的负梯度方向,第二次及以后搜索方向采用一种新的全局收敛的下降算法(Pan-Chen算法).与共轭梯度法比较,新算法具有更好的收敛性.数值模拟结果验证了理论算法的可靠性.     

Hybrid methods with regularization for minimization problems and asymptotically strict pseudocontractive mappings in the intermediate sense

In this paper we introduce an iterative algorithm for finding a common element of the fixed point set of an asymptotically strict pseudocontractive mapping S in the intermediate sense and the solution set of the minimization problem (MP) for a convex and continuously Frechet differentiable functional in Hilbert space. The iterative algorithm is based on several well-known methods including the extragradient method, CQ method, Mann-type iterative method and hybrid gradient projection algorithm with regularization. We obtain a strong convergence theorem for three sequences generated by our iterative algorithm. In addition, we also prove a new weak convergence theorem by a modified extragradient method with regularization for the MP and the mapping S.     

Interpolation algorithm of Leverrier–Faddev type for polynomial matrices

We investigated an interpolation algorithm for computing outer inverses of a given polynomial matrix, based on the Leverrier–Faddeev method. This algorithm is a continuation of the finite algorithm for computing generalized inverses of a given polynomial matrix, introduced in [11]. Also, a method for estimating the degrees of polynomial matrices arising from the Leverrier–Faddeev algorithm is given as the improvement of the interpolation algorithm. Based on similar idea, we introduced methods for computing rank and index of polynomial matrix. All algorithms are implemented in the symbolic programming language MATHEMATICA , and tested on several different classes of test examples.     

A new shrinking gradient-like projection method for equilibrium problems

The paper proposes a new shrinking gradient-like projection method for solving equilibrium problems. The algorithm combines the generalized gradient-like projection method with the monotone hybrid method. Only one optimization program is solved onto the feasible set at each iteration in our algorithm without any extra-step dealing with the feasible set. The absence of an optimization problem in the algorithm is explained by constructing slightly different cutting-halfspace in the monotone hybrid method. Theorem of strong convergence is established under standard assumptions imposed on equilibrium bifunctions. An application of the proposed algorithm to multivalued variational inequality problems (MVIP) is presented. Finally, another algorithm is introduced for MVIPs in which we only use a value of main operator at the current approximation to construct the next approximation. Some preliminary numerical experiments are implemented to illustrate the convergence and computational performance of our algorithms over others.     

Euclid's algorithm and the Lanczos method over finite fields

This paper shows that there is a close relationship between the Euclidean algorithm for polynomials and the Lanczos method for solving sparse linear systems, especially when working over finite fields. It uses this relationship to account rigorously for the appearance of self-orthogonal vectors arising in the course of the Lanczos algorithm. It presents an improved Lanczos method which overcomes problems with self-orthogonality and compares this improved algorithm with the Euclidean algorithm.

     

An algorithm for finding equilibrium in the linear exchange model with fixed budgets

We propose a new method for finding equilibrium in a linear exchange model with fixed budgets. The algorithm rests on consideration of the two dual polyhedral complexes generated by an associated transportation problem of the model. The algorithm uses the thoroughly developed fragments of the method of potentials for a transportation problem, which enables us to considering only systems of linear equations with a triangular matrix at every step. The algorithm admits starting with an arbitrary initial price vector. We prove the finiteness of the algorithm.     

An iterative penalty method for the least squares solution of boundary value problems

This article is concerned with iterative techniques for linear systems of equations arising from a least squares formulation of boundary value problems. In its classical form, the solution of the least squares method is obtained by solving the traditional normal equation. However, for nonsmooth boundary conditions or in the case of refinement at a selected set of interior points, the matrix associated with the normal equation tends to be ill-conditioned. In this case, the least squares method may be formulated as a Powell multiplier method and the equations solved iteratively. Therein we use and compare two different iterative algorithms. The first algorithm is the preconditioned conjugate gradient method applied to the normal equation, while the second is a new algorithm based on the Powell method and formulated on the stabilized dual problem. The two algorithms are first compared on a one-dimensional problem with poorly conditioned matrices. Results show that, for such problems, the new algorithm gives more accurate results. The new algorithm is then applied to a two-dimensional steady state diffusion problem and a boundary layer problem. A comparison between the least squares method of Bramble and Schatz and the new algorithm demonstrates the ability of the new method to give highly accurate results on the boundary, or at a set of given interior collocation points without the deterioration of the condition number of the matrix. Conditions for convergence of the proposed algorithm are discussed. © 1997 John Wiley & Sons, Inc.     

Relative and absolute error control in a finite-difference method solution of Poisson's equation

An algorithm for error control (absolute and relative) in the five-point finite-difference method applied to Poisson's equation is described. The algorithm is based on discretization of the domain of the problem by means of three rectilinear grids, each of different resolution. We discuss some hardware limitations associated with the algorithm, which are mainly due to its second-order nature. A generalization of the algorithm for finite-difference methods of arbitrary order is presented. We believe that the algorithm is a valuable addition to typical textbook discussions of the five-point finite-difference method for Poisson's equation.