非线性约束极值问题的改进单纯形法

设有问题 minf(x) x∈k~n §1 Nelder、Mead的单纯形法设x~((0)),x~((1)),……,x~((n))为k~n中的点,由这些点作顶点形成初始单纯形。定义: f[x~((H))]=max{f[x~((i))],i=0,1,2……n}、x~((H))称为最高点; f[x~((L))]=min{f[x~((i)),i=0,1,2……n},x~((l))称为最低点; f[x~((G))]=max{f[x~((i))],i=0,1,2……n,i≠H),x~((G))称为次高点。     

由谱数据数值稳定地构造实对称带状矩阵

§1.引言 设r,n是正整数并且0r有a_(ij)=0.     

约束线性方程组通解的显式表示及Cramer法则

本文研究了一般的约束线性方程组Ax=b,x∈T, (1.1)其中A∈C~(m×n),b∈R(A),T为C~n中任意取定的子空间。给出了(1.1)有唯一解的充要条件;在有唯一解时,利用B-D逆(A~*A)_((T))~((-1))给出了唯一解的显式及cramer法则;在有解但解不唯一时,利用B-D逆(A~*A)_((?))~((-1))(这里(?)=R(R_TA~*))给出了(1.1)的通解的显式及Cramer法则。其结果改进并推广了文[2,3,4,5,6]中的有关结果。 另外,本文研究了A的T-约束M-P逆(AP_T)~+与A~*A的B-D逆(A~*A)_((?))~((-1))的关系,证明了下列事实:(AP_T)~+=(A~*A)_((?))~((-1))A~*,特别,当T∩N(A)={0}时,(AP_T)~+=(A~*A)_((?))~((-1))A~*。     

关于C*-代数Mn(A)上矩阵迹的一些不等式

C*-代数Mn(A)上矩阵迹是一个正线性映射τ∶Mn(A)→A且满足τ(u*au)=τ(a)(a∈Mn(A),u∈U(Mn(A)))及τ(a2)≤(τ(a))2(a≥0).论文讨论这种矩阵迹的一些性质,给出了若干不等式性质,并且证明:对Mn(A)中的H erm itian元a,b,当m=2k(k∈N)时,τ((ab)m)≤τ(ambm)成立.同时还证明了当m=2k(k∈N)时,对Mn(A)中任一元a,不等式τ(am(a*)m)≤τ((aa*)m)成立.     

一类奇异线性方程组的Cramer法则

在 [3]中 ,给出了一类奇异线性方程组Ax =b的唯一解x =Adb的Cramer法则。本文将其推广到带W 权Drazin逆Ad ,w,得到如下结果 :奇异线性方程组Ax =b的唯一解x =WAd,wWb的分量xj 可表示成xj=det (WA) (j→Wb) UV(j→ 0 ) 0 　det WAUV 0 　j=1,2 ,… ,n ,其中A∈Cm×n,W∈Cn×m,Ind(WA) =k1,Ind(AW ) =k2 ,rank(WA) k1=r 相似文献   

INJECTIVE MAPS ON PRIMITIVE SEQUENCES OVER Z/（p^e）

Let Z/(pe) be the integer residue ring modulo pe with p an odd prime and integer e ≥ 3. For a sequence (a) over Z/(pe), there is a unique p-adic decomposition (a) = (a)0 (a)1·p … (a)e-1 ·pe-1, where each (a)i can be regarded as a sequence over Z/(p), 0 ≤ i ≤ e - 1. Let f(x) be a primitive polynomial over Z/(pe) and G' (f(x), pe) the set of all primitive sequences generated by f(x) over Z/(pe). For μ(x) ∈ Z/(p)[x] with deg(μ(x)) ≥ 2 and gcd(1 deg(μ(x)),p- 1) = 1,set ψe-1 (x0, x1,…, xe-1) = xe-1·[ μ(xe-2) ηe-3 (x0, x1,…, xe-3)] ηe-2 (x0, x1,…, xe-2),which is a function of e variables over Z/(p). Then the compressing map ψe-1: G'(f(x),pe) → (Z/(p))∞,(a) (→)ψe-1((a)0, (a)1,… ,(a)e-1) is injective. That is, for (a), (b) ∈ G' (f(x), pe), (a) = (b) if and only if ψe - 1 ((a)0, (a)1,… , (a)e - 1) =ψe - 1 ((b)0,(b)1,… ,(b)e-1). As for the case of e = 2, similar result is also given. Furthermore, if functions ψe-1 and ψe-1 over Z/(p) are both of the above form and satisfy ψe-1((a)0,(a)1,… ,(a)e-1) = ψe-1((b)0,(b)1,… ,(b)e-1) for (a),(b) ∈ G'(f(x),pe), the relations between (a) and (b), ψe-1 and ψe-1 are discussed.     

ON UNIQUENESS OF SOLUTION TO POINTWISE LANDAU PROBLEM ON THE FINITE INTERVAL

1. Introduction Let W_∞~((r)) (β) = {f| f∈W_∞~((r)) [-1,1], ||f||_(C[-1,1]) β, ||f~((r))||_∞ 1}.In this paper, we will consider the following Landau problem:λf~((k))(ξ) + μf~((k-1)) (ξ) →inf, f∈W_∞~((r)) (β), (1.1)where ξ∈[-1,1], 1(?)k(?)r-1, and λ, μ real and not all zero, (if k=1,suppose λ≠0 in addition ). A. Pinkus studied it first. To begin with, we introduce some fundamental definitions anddenotions. The perfect spline f, which satisfies || f~((r))||_∞ = 1 andhas n knots and n+r+1 points of equioscillation in [-1,1], isdenoted by x_(nr), which is refered as Tchebyshev perfect spline. And     

Traces on an (AF)-Algebra

Let A= U A_n be an (AF)-algebra with identity e, where A_n = M(p(n)),p(n) = (p~(n)) ∈Z_(++)~(r(n)), A_n→A_(n+1), e∈A_n, n, τ(A) be the space of alltracial states on A,G(A) = lim (Z~(r(n)),φ_n) be the dimension group of A,φ_u(G) bethe state space of G(A), where u =φ_(n∞).(p(n)) is an ordered unit of G(A).     

一题两解

<正>1.问题若2x-1>m(x²-1)对满足|m|≤2的所有m都成立,则x的取值范围____.解法1(分离参数法)1°当x2-1)对满足|m|≤2的所有m都成立,则x的取值范围____.解法1(分离参数法)1°当x²-1=0,其中x=-1时,m∈φ;x=1时,对|m|≤2的所有m都成立;2°当x2-1=0,其中x=-1时,m∈φ;x=1时,对|m|≤2的所有m都成立;2°当x²-1>0时,即x<-1或x>1,此时,m<((2x-1)/(x2-1>0时,即x<-1或x>1,此时,m<((2x-1)/(x²-1)),又由题意有((2x-1)/(x2-1)),又由题意有((2x-1)/(x²-1))>     

短区间的并集中整数及其m次幂的差的均值分布

本文研究了短区间的并集中整数及其m次幂的差的均值分布问题,给出了渐近公式.具体来说,设P是奇素数,1≤H≤p,实数δ满足0 δ≤1,整数m≥2.设I~((j))是(0,p)的互不相交的子区间,1≤j≤J,满足H/2≤|I~((j))|≤H,以及(y)_p表示y在模p下的非负最小剩余.定义I=∪_(j=1)~JI~((j)),并设X是模p的Dirichlet非主特征.证明了Σ x∈1 |x-(x~m)p|δp 1=1/p∫_0~([δp]) (Σ x∈1 x≤p-1-t 1+Σ x∈1 x≥t=1 1)dt+O(mJ~(1/2)P~(1/2)log~2 plog H),以及Σ x∈1 |x-(x~m)p|δp X(x)mJ~(1/2)P~(1/2)log~2 plog H.     

CGS/GMRES(k): AN ADAPTIVE PRECONDITIONED CGS ALGORITHM FOR NONSYMMETRIC LINEAR SYSTEMS

Recently Y. Saad proposed a flexible inner-outer preconditioned GMRES algorithm for nonsymmetric linear systems [4]. Following their ideas, we suggest an adaptive preconditioned CGS method, called CGS/GMRES (k), in which the preconditioner is constructed in the iteration step of CGS, by several steps of GMRES(k). Numerical experiments show that the residual of the outer iteration decreases rapidly. We also found the interesting residual behaviour of GMRES for the skewsymmetric linear system Ax = b, which gives a convergence result for restarted GMRES (k). For convenience, we discuss real systems.     

Heavy Ball Flexible GMRES Method for Nonsymmetric Linear Systems

Flexible GMRES (FGMRES) is a variant of preconditioned GMRES, which changes preconditioners at every Arnoldi step. GMRES often has to be restarted in order to save storage and reduce orthogonalization cost in the Arnoldi process. Like restarted GMRES, FGMRES may also have to be restarted for the same reason. A major disadvantage of restarting is the loss of convergence speed. In this paper, we present a heavy ball flexible GMRES method, aiming to recoup some of the loss in convergence speed in the restarted flexible GMRES while keep the benefit of limiting memory usage and controlling orthogonalization cost. Numerical tests often demonstrate superior performance of the proposed heavy ball FGMRES to the restarted FGMRES.     

Convergence conditions for a restarted GMRES method augmented with eigenspaces

We consider the GMRES(m,k) method for the solution of linear systems Ax=b, i.e. the restarted GMRES with restart m where to the standard Krylov subspace of dimension m the other subspace of dimension k is added, resulting in an augmented Krylov subspace. This additional subspace approximates usually an A‐invariant subspace. The eigenspaces associated with the eigenvalues closest to zero are commonly used, as those are thought to hinder convergence the most. The behaviour of residual bounds is described for various situations which can arise during the GMRES(m,k) process. The obtained estimates for the norm of the residual vector suggest sufficient conditions for convergence of GMRES(m,k) and illustrate that these augmentation techniques can remove stagnation of GMRES(m) in many cases. All estimates are independent of the choice of an initial approximation. Conclusions and remarks assessing numerically the quality of proposed bounds conclude the paper. Copyright © 2004 John Wiley & Sons, Ltd.     

Steepest descent preconditioning for nonlinear GMRES optimization

Steepest descent preconditioning is considered for the recently proposed nonlinear generalized minimal residual (N‐GMRES) optimization algorithm for unconstrained nonlinear optimization. Two steepest descent preconditioning variants are proposed. The first employs a line search, whereas the second employs a predefined small step. A simple global convergence proof is provided for the N‐GMRES optimization algorithm with the first steepest descent preconditioner (with line search), under mild standard conditions on the objective function and the line search processes. Steepest descent preconditioning for N‐GMRES optimization is also motivated by relating it to standard non‐preconditioned GMRES for linear systems in the case of a standard quadratic optimization problem with symmetric positive definite operator. Numerical tests on a variety of model problems show that the N‐GMRES optimization algorithm is able to very significantly accelerate convergence of stand‐alone steepest descent optimization. Moreover, performance of steepest‐descent preconditioned N‐GMRES is shown to be competitive with standard nonlinear conjugate gradient and limited‐memory Broyden–Fletcher–Goldfarb–Shanno methods for the model problems considered. These results serve to theoretically and numerically establish steepest‐descent preconditioned N‐GMRES as a general optimization method for unconstrained nonlinear optimization, with performance that appears promising compared with established techniques. In addition, it is argued that the real potential of the N‐GMRES optimization framework lies in the fact that it can make use of problem‐dependent nonlinear preconditioners that are more powerful than steepest descent (or, equivalently, N‐GMRES can be used as a simple wrapper around any other iterative optimization process to seek acceleration of that process), and this potential is illustrated with a further application example. Copyright © 2012 John Wiley & Sons, Ltd.     

Some observations on weighted GMRES

We investigate the convergence of the weighted GMRES method for solving linear systems. Two different weighting variants are compared with unweighted GMRES for three model problems, giving a phenomenological explanation of cases where weighting improves convergence, and a case where weighting has no effect on the convergence. We also present a new alternative implementation of the weighted Arnoldi algorithm which under known circumstances will be favourable in terms of computational complexity. These implementations of weighted GMRES are compared for a large number of examples. We find that weighted GMRES may outperform unweighted GMRES for some problems, but more often this method is not competitive with other Krylov subspace methods like GMRES with deflated restarting or BICGSTAB, in particular when a preconditioner is used.     

GMRES and the minimal polynomial

We present a qualitative model for the convergence behaviour of the Generalised Minimal Residual (GMRES) method for solving nonsingular systems of linear equationsAx =b in finite and infinite dimensional spaces. One application of our methods is the solution of discretised infinite dimensional problems, such as integral equations, where the constants in the asymptotic bounds are independent of the mesh size.Our model provides simple, general bounds that explain the convergence of GMRES as follows: If the eigenvalues ofA consist of a single cluster plus outliers then the convergence factor is bounded by the cluster radius, while the asymptotic error constant reflects the non-normality ofA and the distance of the outliers from the cluster. If the eigenvalues ofA consist of several close clusters, then GMRES treats the clusters as a single big cluster, and the convergence factor is the radius of this big cluster. We exhibit matrices for which these bounds are tight.Our bounds also lead to a simpler proof of existing r-superlinear convergence results in Hilbert space.This research was partially supported by National Science Foundation grants DMS-9122745, DMS-9423705, CCR-9102853, CCR-9400921, DMS-9321938, DMS-9020915, and DMS-9403224.     

CMRH: A new method for solving nonsymmetric linear systems based on the Hessenberg reduction algorithm

The Generalized Minimal Residual (GMRES) method and the Quasi-Minimal Residual (QMR) method are two Krylov methods for solving linear systems. The main difference between these methods is the generation of the basis vectors for the Krylov subspace. The GMRES method uses the Arnoldi process while QMR uses the Lanczos algorithm for constructing a basis of the Krylov subspace. In this paper we give a new method similar to QMR but based on the Hessenberg process instead of the Lanczos process. We call the new method the CMRH method. The CMRH method is less expensive and requires slightly less storage than GMRES. Numerical experiments suggest that it has behaviour similar to GMRES. This revised version was published online in June 2006 with corrections to the Cover Date.     

Upper bounds for convergence rates of acceleration methods with initial iterations

GMRES(n,k), a version of GMRES for the solution of large sparse linear systems, is introduced. A cycle of GMRES(n,k) consists of n Richardson iterations followed by k iterations of GMRES. Such cycles can be repeated until convergence is achieved. The advantage in this approach is in the opportunity to use moderate k, which results in time and memory saving. Because the number of inner products among the vectors of iteration is about k^2/2, using a moderate k is particularly attractive on message-passing parallel architectures, where inner products require expensive global communication. The present analysis provides tight upper bounds for the convergence rates of GMRES(n,k) for problems with diagonalizable coefficient matrices whose spectra lie in an ellipse in 0. The advantage of GMRES(n,k) over GMRES(k) is illustrated numerically.     

A new adaptive GMRES algorithm for achieving high accuracy

GMRES(k) is widely used for solving non-symmetric linear systems. However, it is inadequate either when it converges only for k close to the problem size or when numerical error in the modified Gram–Schmidt process used in the GMRES orthogonalization phase dramatically affects the algorithm performance. An adaptive version of GMRES(k) which tunes the restart value k based on criteria estimating the GMRES convergence rate for the given problem is proposed here. This adaptive GMRES(k) procedure outperforms standard GMRES(k), several other GMRES-like methods, and QMR on actual large scale sparse structural mechanics postbuckling and analog circuit simulation problems. There are some applications, such as homotopy methods for high Reynolds number viscous flows, solid mechanics postbuckling analysis, and analog circuit simulation, where very high accuracy in the linear system solutions is essential. In this context, the modified Gram–Schmidt process in GMRES, can fail causing the entire GMRES iteration to fail. It is shown that the adaptive GMRES(k) with the orthogonalization performed by Householder transformations succeeds whenever GMRES(k) with the orthogonalization performed by the modified Gram–Schmidt process fails, and the extra cost of computing Householder transformations is justified for these applications. © 1998 John Wiley & Sons, Ltd.     

An Efficient Variant of the Restarted Shifted GMRES Method for Solving Shifted Linear Systems

We investigate the restart of the Restarted Shifted GMRES method for solving shifted linear systems.Recently the variant of the GMRES(m) method with the unfixed update has been proposed to improve the convergence of the GMRES(m) method for solving linear systems,and shown to have an efficient convergence property.In this paper,by applying the unfixed update to the Restarted Shifted GMRES method,we propose a variant of the Restarted Shifted GMRES method.We show a potentiality for efficient convergence within the variant by some numerical results.