大型稀疏线性互补问题的行作用法

且引言考虑线性互补问题＊＊P（q，M）：求X二（X；，x。，…，x。厂E”使得x＞O，训x）E＊x＋g＞o，／U（X）一O（1）其中M一（m；。）为nXn矩阵（不必对称），q一切，q。，…，q。）rER“为给定常向量．通常情况下已有求解LCP（q，M）的若干著名算法［‘－’j．本文提出求解LCP（q，M）的一种新算法一行作用法，方法具有如下特点：（i）每次迭代只需n个简单的投影运算，每次投影只涉及矩阵M的一行；（n）生成新的迭代点x‘“‘时只利用前次迭代点／；（iii）对矩阵M不实施任何整体运算．因而适合于求解大型（巨型）稀疏问题，且…     

积分integral from (1/x~n 1)dx的计算

对于积分当n较小时，好计算，但当n较大时，例如n=6、7等，很难计算．现在利用橡模佛定理、欧拉公式和一些基本方法求出它的原函数，并举例说明其应用．被积函数由律模佛定理可知：方程Xn＋1=0的解为其中．因此有的计算由（1）可得又根据欧拉公式1．3化简由于方程X”＋1一0的根具有共轭性，故有若n为偶数，则上式为若n为奇数，则上式为2计算实例当n较大时，运用上述公式非常简单，现举两个例子说明．。．．。＿l‘l例呈求I＝＝＝－dXJ。x‘＋1解n二7，可列表如下：［＊。」8表示X21时＊。的值减去X一0时＊。的值，［用z亦同．例2求入。一…     

无约束非光滑优化问题的信赖域算法及收敛性

1．引言考虑下列无约束非光滑优化问题：其中f为R”上的局部LIPSChitZ函数．本文将11·112简记为11·l．信赖域算法是通过求解一系列子问题3＊B（二，凸）：来求解问题（1）的，其中拉x，·）为j在x点的一阶近似，B为nxn阶对称阵．下面给出信赖域的基本算法TRA：步1·给定...     

e~(kx)在解题过程中应用几例

在解题过程中如果能用上ekx，会使解法简单巧妙，下面的例2说明必须会用e－x构造辅助函数。例1设f（x）是定义在［0，］上的连续函数，且证二八x）在肝，音］上连续，八X）＞o，设在X。处取最大值，于是由于八x。）是最大值，人n＜八X。），这就有：用上面的方法可证出在同样可证fseo，以此类推，则有人X）三0。上面的例是我们学校的一次统考题，证法一是学生想起的。例2设人x）在「a，b］上存在n＋l阶导数，且满足广‘’（a）一月‘’（b）—0，足一0，1，2，…，n．（这里／”（a）一f（），f”’（b）一f（））．证明：目七（a，b）使…     

解非线性方程组的一类离散的Newton算法

1．引言考虑非线性方程组设xi是当前的迭代点，为计算下一个迭代点，Newton法是求解方程若用差商代替导数，离散Newton法要解如下的方程其中这里为了计算J（；；h），需计算n‘个函数值．为了提高效能，Brown方法l‘］使用代入消元的办法来减少函数值计算量．它是再通过一次内选代从h得到下一个迭代点14＋1．设n；＝（《1，…，Zn尸，t二（ti，…，t＊”，t为变量．BfOWll方法的基本思想如下．对人（x）在X；处做线性近似解出然后代入第二个函数，得到这是关于tZ，…，tn的函数．当（tZ，…，t。尸一（ZZ，…，Z。厂时，由（1．4），…     

异步并行非线性对称Gauss-Seidel迭代算法

1．引言考虑非线性方程组其中A＝（a。。）EL（＊”）为＊一矩阵，B＝（衬。）EL（＊”）为非负矩阵，呐X）一（p。（X。》，4（二）＝（吵k（kk》：＊一＊一为连续的对角映射，而6＝（6k）E＊一为已知向量．这里，什小：”一”均可微，但二者的导函数并不一定连续．这类方程组具有丰富的实际背景．例如，描述冰体溶解过程的著名的Stefan问题，就可归结为问题（1·1）的数值求解（见［l］）．为在多处理机系统上有效地求解问题（1．1），文山利用这类非线性方程组的特殊结构，建立了一类并行非线性Gauss—Seidel型迭代算法．为避免该算…     

函数的光滑性与“磨光算子”──定积分的一个应用

函数y＝f（x），如果在区间1上具有直到X（＞0）阶的连续导数，则称之为在7上是K阶光滑的。I上K阶光滑函数的全体记作C”（I）。光滑之说，有几何背景。约定函数的零阶导数为其本身；K—0对应连续曲线。KZI的对应的曲线不但处处有切线，而且切线随着切点在曲线上移动而连续地变动。K一2对应的曲线除上述几何性质外，曲率K（X）（一厂’（X）［十八X〕」‘’勾沿着曲线连续地变化而不会突变。K二3对应曲线的曲率K关于x的变化率”（X）还是连续的，认为曲线已经相当光滑了。＊＞4的高阶光滑性的几何意义已没有上述的明显，但是可以认…     

半无限规划问题的一个有效解法

1．引言在计算机辅助设计和工程设计中,经常遇到下面的两类优化问题1,2］．1．无约束半无限极大极小问题．其中外x）二——x。。Im。x。。。Yi夕（x;N）这里J二（】,2,·,｝对任何7E八岁：R－xR”。＋R是连续可微的函数,X是R”。中的一个紧子集,且VYj）一O,这里问h）表示X体积．2．约束半无限代化问题．其中I一（1,2,·．小记L二《0｝UI对任何jCL冲’（x）一max。。。Yi夕（x,yi）·这里拉：PX＊n＋R是连续可微函数,X是”。中的一个紧子集,且NU）一0·注．设Y（Z,一二切EyW一叫卜4．今后对本文用到的紧子集地做…     

一个求解互补问题的光滑Newton方法

１．引言 考虑非线性互补问题ＮＣＰ（Ｆ）：其中 Ｆ： 是连续可微函数．目前比较流行的求解ＮＣＰ（Ｆ）的方法之一是首先把它转化为一个方程组,然后通过求解方程组的方法［１］间接求解,这样的方法通常是通过Ｆｉｓｃｈｅｒ函数来完成的［２］容易验证所以求解ＮＣＰ（Ｆ）可以等价求解一个ｎ维方程组 然而函数φ有一个缺点,即它在零点不可微．这就导致Φ在某些点不可微．因此传统的求解方程组的方法并不能直接应用到Φ上．为克服这个缺点,可使用它的光滑形式［４］： 我们注意到,只要μ＞０,φμ就是可微的,而且对任意μ有所以可…     

用算子法求常系数线性非齐次方程特解

本文通过引人算子，介绍了一种能有效求出常系数线性非齐次方程特解的方法。希望对同学们有所帮助。一、有关概念引入其子，记代入系数线性非齐欢方程得简记为，称为其子多项式，记为F（D），于是方程可记为F（D）y=f（x）。通过直接运算，易知k）v（x）。二、基本运＊：设民（D）、Fi（D）为算子多项式1．加法：［凤（D）十几（＊月八X）一见（＊）八三）十几（D）八三）；2．乘法：［凤（＊）·凡（D）」八X）一只（D）［尺（＊）八X）」。易证加法和乘法满足：F（D）＋F（D）一见（D）＋F（D），F（D）·F。（D）2F（D）·F…     

Minimum relative error approximations for 1/t

Summary We give explicit solutions to the problem of minimizing the relative error for polynomial approximations to 1/t on arbitrary finite subintervals of (0, ). We give a simple algorithm, using synthetic division, for computing practical representations of the best approximating polynomials. The resulting polynomials also minimize the absolute error in a related functional equation. We show that, for any continuous function with no zeros on the interval of interest, the geometric convergence rates for best absolute error and best relative error approximants must be equal. The approximation polynomials for 1/t are useful for finding suitably precise initial approximations in iterative methods for computing reciprocals on computers.     

Parameter error estimate of near alternation approximation

In practical computation of the discrete best uniform approximation, we usually only get near best (i.e., with the -near alteration property) approximation. We need to estimate the error between the (unknown) best approximation and the achieved approximation. In this paper we estimate the parameter error by means of the generalized strong unicity constants.Visiting scholar from Department of Mathematics, Shanghai University of Science and Technology, Shanghai, P.R. China 201800.     

Pairs of integers which are mutually squares

We derived an asymptotic formula for the number of pairs of integers which are mutually squares. Earlier results dealt with pairs of integers subject to the restriction that they are both odd, co-prime and squrefree. Here we remove all these restrictions and prove (similar to the best known one with restrictions) that the number of such pair of integers upto a large real X is asymptotic to \(\frac{{c{X^2}}}{{\log X}}\) with an absolute constant c which we give explicitly. Our error term is also compatible to the best known one.     

Best Approximation and Cyclic Variation Diminishing Kernels

We study best uniform approximation of periodic functions from

Full-size image

where the kernelK(x, y) is strictly cyclic variation diminishing, and related problems including periodic generalized perfect splines. For various approximation problems of this type, we show the uniqueness of the best approximation and characterize the best approximation by extremal properties of the error function. The results are proved by using a characterization of best approximants from quasi-Chebyshev spaces and certain perturbation results.     

Polynomial approximations of a class of stochastic multiscale elasticity problems

We consider a class of elasticity equations in \({\mathbb{R}^d}\) whose elastic moduli depend on n separated microscopic scales. The moduli are random and expressed as a linear expansion of a countable sequence of random variables which are independently and identically uniformly distributed in a compact interval. The multiscale Hellinger–Reissner mixed problem that allows for computing the stress directly and the multiscale mixed problem with a penalty term for nearly incompressible isotropic materials are considered. The stochastic problems are studied via deterministic problems that depend on a countable number of real parameters which represent the probabilistic law of the stochastic equations. We study the multiscale homogenized problems that contain all the macroscopic and microscopic information. The solutions of these multiscale homogenized problems are written as generalized polynomial chaos (gpc) expansions. We approximate these solutions by semidiscrete Galerkin approximating problems that project into the spaces of functions with only a finite number of N gpc modes. Assuming summability properties for the coefficients of the elastic moduli’s expansion, we deduce bounds and summability properties for the solutions’ gpc expansion coefficients. These bounds imply explicit rates of convergence in terms of N when the gpc modes used for the Galerkin approximation are chosen to correspond to the best N terms in the gpc expansion. For the mixed problem with a penalty term for nearly incompressible materials, we show that the rate of convergence for the best N term approximation is independent of the Lamé constants’ ratio when it goes to \({\infty}\). Correctors for the homogenization problem are deduced. From these we establish correctors for the solutions of the parametric multiscale problems in terms of the semidiscrete Galerkin approximations. For two-scale problems, an explicit homogenization error which is uniform with respect to the parameters is deduced. Together with the best N term approximation error, it provides an explicit convergence rate for the correctors of the parametric multiscale problems. For nearly incompressible materials, we obtain a homogenization error that is independent of the ratio of the Lamé constants, so that the error for the corrector is also independent of this ratio.     

Best Approximation by Free Knot Splines

We consider the problem of finding the best (uniform) approximation of a given continuous function by spline functions with free knots. Our approach can be sketched as follows. By using the Gauß transform with arbitrary positive real parameter t, we map the set of splines under consideration onto a function space, which is arbitrarily close to the spline set, but satisfies the local Haar condition and also possesses other nice structural properties. This enables us to give necessary and sufficient conditions for best approximations (in terms of alternants) and, under some assumptions, even full characterizations and a uniqueness result. By letting t 0, we recover best approximation in the original spline space. Our results are illustrated by some numerical examples, which show in particular the nice alternation behavior of the error function.     

On optimal global error bounds obtained by scaled local error estimates

Summary In the second section a general method of obtaining optimal global error bounds by scaling local error estimates is developed. It is reduced to the solution of a fixpoint problem. In Sect. 3 we show more concrete error estimates reflecting a singularity of order . It is shown that under general circumstances an optimal global error bound is achieved by an (asymptotically) geometric mesh for the local error estimates. In the fourth section we specialize this to the best approximation ofg(x)x by piecewise polynomials with variable knots and degrees having a total numberN of parameters. This generalizes the result of R. DeVore and the author forg(x)=1. In the last section this problem is studied for the functione ^–x on (0, ). The exact asymptotic behaviour of the approximation withN parameters is determined toe ^qoN , whereq _o=0.895486 ....     

Hölder estimates for Green’s functions on convex polyhedral domains and their applications to finite element methods

A model second-order elliptic equation on a general convex polyhedral domain in three dimensions is considered. The aim of this paper is twofold: First sharp Hölder estimates for the corresponding Green’s function are obtained. As an applications of these estimates to finite element methods, we show the best approximation property of the error in \({W^1_{\infty}}\) . In contrast to previously known results, \({W_p^{2}}\) regularity for p > 3, which does not hold for general convex polyhedral domains, is not required. Furthermore, the new Green’s function estimates allow us to obtain localized error estimates at a point.     

Optimum quantization and its applications

Minimum sums of moments or, equivalently, distortion of optimum quantizers play an important role in several branches of mathematics. Fejes Tóth's inequality for sums of moments in the plane and Zador's asymptotic formula for minimum distortion in Euclidean d-space are the first precise pertinent results in dimension d?2. In this article these results are generalized in the form of asymptotic formulae for minimum sums of moments, resp. distortion of optimum quantizers on Riemannian d-manifolds and normed d-spaces. In addition, we provide geometric and analytic information on the structure of optimum configurations. Our results are then used to obtain information on

(i)

the minimum distortion of high-resolution vector quantization and optimum quantizers,

(ii)

the error of best approximation of probability measures by discrete measures and support sets of best approximating discrete measures,

(iii)

the minimum error of numerical integration formulae for classes of Hölder continuous functions and optimum sets of nodes,

(iv)

best volume approximation of convex bodies by circumscribed convex polytopes and the form of best approximating polytopes, and

(v)

the minimum isoperimetric quotient of convex polytopes in Minkowski spaces and the form of the minimizing polytopes.

     

Estimations des erreurs de meilleure approximation polynomiale et d'interpolation de Lagrange dans les espaces de Sobolev d'ordre non entier

Résumé On établit des majorations explicites de I'erreur de meilleure approximation polynomiale ainsi que des majorations explicites et nonexplicites de I'erreur d'interpolation de Lagrange, lorsque la fonction considérée appartient à un espace de Sobolev d'ordre non entier défini sur un ouvert borné de ⁿ .Les résultats obtenus généralisent les résultats connus dans le cas des espaces de Sobolev d'ordre entier.

---

Estimation of the best polynomial approximation error and the Lagrange interpolation error in fractional-order Ssobolev spaces

Summary Explicit bounds for the best polynomial approximation error, explicit and non-explicit bounds for the Lagrange interpolation error are derived for functions belonging to fractional order Sobolev spaces defined over a bounded open set in ⁿ .Thus the classical results of the integer order Sobolev spaces are extended.