曲边三角形及曲边四边形上的混合函数插值格式

一、引言 二元函数在标准三角形上的混合函数插值格式在许多文献,例如,Birkhofft,Barnhill,Gordon及Gregory等的文章中都有讨论。在三角形周边上对高阶偏导数进行插值,而且计算比较简单的是J.A.Gregory的文章中所给出的一种混合函数插值格式。这种格式是由简单函数的线性组合所构成的,而且格式是对称的,因此计算比较简便。但是J.A.Gregory只是对直边三角形给出了格式。本文企图推广Gregory的格式,给出曲边三角形上对高阶偏导数进行插值的插值格式。我们还进一步给出了曲边四边形上     

A new augmented immersed finite element method without using SVD interpolations

Augmented immersed interface methods have been developed recently for interface problems and problems on irregular domains including CFD applications with free boundaries and moving interfaces. In an augmented method, one or several augmented variables are introduced along the interface or boundary so that one can get efficient discretizations. The augmented variables should be chosen such that the interface or boundary conditions are satisfied. The key to the success of the augmented methods often relies on the interpolation scheme to couple the augmented variables with the governing differential equations through the interface or boundary conditions. This has been done using a least squares interpolation (under-determined) for which the singular value decomposition (SVD) is used to solve for the interpolation coefficients. In this paper, based on properties of the finite element method, a new augmented immersed finite element method (IFEM) that does not need the interpolations is proposed for elliptic interface problems that have a piecewise constant coefficient. Thus the new augmented method is more efficient and simple than the old one that uses interpolations. The method then is extended to Poisson equations on irregular domains with a Dirichlet boundary condition. Numerical experiments with arbitrary interfaces/irregular domains and large jump ratios are provided to demonstrate the accuracy and the efficiency of the new augmented methods. Numerical results also show that the number of GMRES iterations is independent of the mesh size and nearly independent of the jump in the coefficient.     

Recursive polynomial curve schemes and computer-aided geometric design

A class of polynomial curve schemes is introduced that may have widespread application to CAGD (computer-aided geometric design), and which contains many well-known curve schemes, including Bézier curves, Lagrange polynomials, B-spline curve (segments), and Catmull-Rom spline (segments). The curves in this class can be characterized by a simple recursion formula. They are also shown to have many properties desirable for CAGD; in particular they are affine invariant, have the convex hull property, and possess a recursive evaluation algorithm. Further, these curves have shape parameters which may be used as a design tool for introducing such geometric effects as tautness, bias, or interpolation. The link between probability theory and this class of curves is also discussed.Communicated by Klaus Höllig.     

C2 Continuous Quartic Hermite Spline Curves with Shape Parameters

In order to relieve the deficiency of the usual cubic Hermite spline curves, the quartic Hermite spline curves with shape parameters is further studied in this work. The interpolation error and estimator of the quartic Hermite spline curves are given. And the characteristics of the quartic Hermite spline curves are discussed. The quartic Hermite spline curves not only have the same interpolation and conti-nuity properties of the usual cubic Hermite spline curves, but also can achieve local or global shape adjustment and C2 continuity by the shape parameters when the interpolation conditions are fixed.     

Coaxing a planar curve to comply

A long-standing problem in computer graphics is to find a planar curve that is shaped the way you want it to be shaped. A selection of various methods for achieving this goal is presented. The focus is on mathematical conditions that we can use to control curves while still allowing the curves some freedom. We start with methods invented by Newton (1643–1727) and Lagrange (1736–1813) and proceed to recent methods that are the subject of current research. We illustrate almost all the methods discussed with diagrams. Three methods of control that are of special interest are interpolation methods, global minimization methods (such as least squares), and (Bézier) control points. We concentrate on the first of these, interpolation methods.     

轴对称弹性动力学问题的重构核插值法

重构核插值法是近年来提出的一种新型无网格方法.该方法的形函数具有点插值性和高阶光滑性,不仅能够直接施加本质边界条件,而且能保证较高的计算精度.为了更有效地求解三维轴对称弹性动力学问题,对重构核插值法(reproducing kernel interpolation method, RKIM)应用于此类问题进行了研究,并发展了相应的数值模拟方法.由于几何形状和边界条件的轴对称性,计算时只需要横截面上离散节点的信息,因而前处理变得简单.采用Newmark-β法进行了时域积分.数值算例表明,轴对称弹性动力学分析的重构核插值法既有无网格方法的优势,又有较高的计算精度.     

Generation of efficient frontiers in multi-objective optimization problems by generalized data envelopment analysis

In many practical problems such as engineering design problems, criteria functions cannot be given explicitly in terms of design variables. Under this circumstance, values of criteria functions for given values of design variables are usually obtained by some analyses such as structural analysis, thermodynamical analysis or fluid mechanical analysis. These analyses require considerably much computation time. Therefore, it is not unrealistic to apply existing interactive optimization methods to those problems. On the other hand, there have been many trials using genetic algorithms (GA) for generating efficient frontiers in multi-objective optimization problems. This approach is effective in problems with two or three objective functions. However, these methods cannot usually provide a good approximation to the exact efficient frontiers within a small number of generations in spite of our time limitation. The present paper proposes a method combining generalized data envelopment analysis (GDEA) and GA for generating efficient frontiers in multi-objective optimization problems. GDEA removes dominated design alternatives faster than methods based on only GA. The proposed method can yield desirable efficient frontiers even in non-convex problems as well as convex problems. The effectiveness of the proposed method will be shown through several numerical examples.     

参数保形插值中决定切矢的方法

由分段三次参数多项式曲线拼合成的Ｃ１插值曲线的形状与数据点处的切矢有很大关系．基于对保形插值曲线特点的分析，本文提出了估计数据点处切矢的一种方法：采用使构造的插值曲线的长度尽可能短的思想估计数据点处的切矢，并且通过四组有代表性的数据对本方法和已有的三种方法进行了比较．     

利用近似能量极小构造平面C1三次Hermite插值曲线

研究了利用近似能量极小构造平面$C^1$三次Hermite插值曲线的方法.该方法的主要的目是求出$C^1$三次Hermite插值曲线的最佳切矢.通过将应变能、曲率变化能和组合能的近似函数极小化,得到了求解最佳切矢的线性方程组.通过求解发现,近似曲率变化能极小不存在唯一解, 而近似应变能极小和近似组合能极小由于方程系统的系数矩阵为严格对角占优故都存在唯一解.最后, 通过实例表明了本文方法构造平面$C^1$三次Hermite插值曲线的有效性.     

Convection-diffusion-reaction problems on a B-type mesh

One-dimensional singularly perturbed problems with two small parameters are considered. Numerical methods for such problems are discussed in several papers, but on a Shishkin-type mesh. The first optimal result of convergence in an energy norm on a Bakhvalov-type mesh for one-dimensional convection-diffusion problem was given by Roos in [9]. In this paper we analyze Galerkin finite element method on a Bakhvalov-type mesh for two-parameter convection-diffusion-reaction problems. In the interpolation error analysis, instead of the usual interpolation operator in the finite element space we use a quasi-interpolant with improved stability properties. We prove that the finite element method for these problems is uniformly convergent in the energy norm. Numerical results confirm our theoretical analysis and show first-order convergence rate. (© 2013 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Rational radial basis function interpolation with applications to antenna design

Functions with poles occur in many branches of applied mathematics which involve resonance phenomena. Such functions are challenging to interpolate, in particular in higher dimensions. In this paper we develop a technique for interpolation with quotients of two radial basis function (RBF) expansions to approximate such functions as an alternative to rational approximation. Since the quotient is not uniquely determined we introduce an additional constraint, the sum of the RBF-norms of the numerator and denominator squared should be minimal subjected to a norm condition on the function values. The method was designed for antenna design applications and we show by examples that the scattering matrix for a patch antenna as a function of some design parameters can be approximated accurately with the new method. In many cases, e.g. in antenna optimization, the function evaluations are time consuming, and therefore it is important to reduce the number of evaluations but still obtain a good approximation. A sensitivity analysis of the new interpolation technique is carried out and it gives indications how efficient adaptation methods could be devised. A family of such methods are evaluated on antenna data and the results show that much performance can be gained by choosing the right method.     

求解变延迟微分方程的一类线性多步方法的收缩性

This paper presents a sufficient condition on the contractivity of theoretical solution for a class of nonlinear systems of delay differential equations with many variable delays(MDDEs), which is weak,compared with the sufficient condition of previous articles.In addition,it discusses the numerical stability properties of a class of special linear nmltistep methods for this class nonlinear problems.And it is pointed out that not only the backwm‘d Euler method but also this class of linear multistep methods are GRNm-stable if linear interpolation is used.     

Precomputing strategy for Hamiltonian Monte Carlo method based on regularity in parameter space

Markov Chain Monte Carlo (MCMC) algorithms play an important role in statistical inference problems dealing with intractable probability distributions. Recently, many MCMC algorithms such as Hamiltonian Monte Carlo (HMC) and Riemannian Manifold HMC have been proposed to provide distant proposals with high acceptance rate. These algorithms, however, tend to be computationally intensive which could limit their usefulness, especially for big data problems due to repetitive evaluations of functions and statistical quantities that depend on the data. This issue occurs in many statistic computing problems. In this paper, we propose a novel strategy that exploits smoothness (regularity) in parameter space to improve computational efficiency of MCMC algorithms. When evaluation of functions or statistical quantities are needed at a point in parameter space, interpolation from precomputed values or previous computed values is used. More specifically, we focus on HMC algorithms that use geometric information for faster exploration of probability distributions. Our proposed method is based on precomputing the required geometric information on a set of grids before running sampling algorithm and approximating the geometric information for the current location of the sampler using the precomputed information at nearby grids at each iteration of HMC. Sparse grid interpolation method is used for high dimensional problems. Tests on computational examples are shown to illustrate the advantages of our method.     

Scattered data fitting of Hermite type by a weighted meshless method

In many practical problems, it is often desirable to interpolate not only the function values but also the values of derivatives up to certain order, as in the Hermite interpolation. The Hermite interpolation method by radial basis functions is used widely for solving scattered Hermite data approximation problems. However, sometimes it makes more sense to approximate the solution by a least squares fit. This is particularly true when the data are contaminated with noise. In this paper, a weighted meshless method is presented to solve least squares problems with noise. The weighted meshless method by Gaussian radial basis functions is proposed to fit scattered Hermite data with noise in certain local regions of the problem’s domain. Existence and uniqueness of the solution is proved. This approach has one parameter which can adjust the accuracy according to the size of the noise. Another advantage of the weighted meshless method is that it can be used for problems in high dimensions with nonregular domains. The numerical experiments show that our weighted meshless method has better performance than the traditional least squares method in the case of noisy Hermite data.     

Computing parallel curves on parametric surfaces

Generating parallel curves on parametric surfaces is an important issue in many industrial settings. Given an initial curve (called the base curve or generator) on a parametric surface, the goal is to obtain curves on the surface that are parallel to the generator. By parallel curves we mean curves that are at a given distance from the generator, where distance is measured point-wise along certain characteristic curves (on the surface) orthogonal to the generator. Except for a few particular cases, computing these parallel curves is a very difficult and challenging problem. In fact, only partial, incomplete solutions have been reported so far in the literature. In this paper we introduce a simple yet efficient method to fill this gap. In clear contrast with other existing techniques, the most important feature of our method is its generality: it can be successfully applied to any differentiable parametric surface and to any kind of characteristic curves on surfaces. To evaluate our proposal, some illustrative examples (not addressed with previous methods) for the cases of section, vector-field, and geodesic parallels are discussed. Our experimental results show the excellent performance of the method even for the complex case of NURBS surfaces.     

Global optimization using special ordered sets

The task of finding global optima to general classes of nonconvex optimization problem is attracting increasing attention. McCormick [4] points out that many such problems can conveniently be expressed in separable form, when they can be tackled by the special methods of Falk and Soland [2] or Soland [6], or by Special Ordered Sets. Special Ordered Sets, introduced by Beale and Tomlin [1], have lived up to their early promise of being useful for a wide range of practical problems. Forrest, Hirst and Tomlin [3] show how they have benefitted from the vast improvements in branch and bound integer programming capabilities over the last few years, as a result of being incorporated in a general mathematical programming system.Nevertheless, Special Ordered Sets in their original form require that any continuous functions arising in the problem be approximated by piecewise linear functions at the start of the analysis. The motivation for the new work described in this paper is the relaxation of this requirement by allowing automatic interpolation of additional relevant points in the course of the analysis.This is similar to an interpolation scheme as used in separable programming, but its incorporation in a branch and bound method for global optimization is not entirely straightforward. Two by-products of the work are of interest. One is an improved branching strategy for general special-ordered-set problems. The other is a method for finding a global minimum of a function of a scalar variable in a finite interval, assuming that one can calculate function values and first derivatives, and also bounds on the second derivatives within any subinterval.The paper describes these methods, their implementation in the UMPIRE system, and preliminary computational experience.     

Constrained variational refinement

A non-uniform, variational refinement scheme is presented for computing piecewise linear curves that minimize a certain discrete energy functional subject to convex constraints on the error from interpolation. Optimality conditions are derived for both the fixed and free-knot problems. These conditions are expressed in terms of jumps in certain (discrete) derivatives. A computational algorithm is given that applies to constraints whose boundaries are either piecewise linear or spherical. The results are applied to closed periodic curves, open curves with various boundary conditions, and (approximate) Hermite interpolation.     

Conservative Velocity Interpolation for PDF Methods

In many particle methods the accurate interpolation of a velocity field represented on a computational grid to arbitrary positions is crucial [2, 5]. Here, the importance of mass conservation and order of the interpolation scheme were analyzed. Initially equally distributed particles were tracked in a stationary, incompressible 2d flow field using different interpolation schemes. It could be demonstrated that especially mass conservation is of great importance, in particular in the case of complex flow patterns. The ideas presented in this paper are more general and the methods can be extended for unsteady, compressible 3d flow problems. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

An Improved Linearity-Preserving Cell-Centered Scheme for Nonlinear Diffusion Problems on General Meshes

In this paper, we suggest a new vertex interpolation algorithm to improve an existing cell-centered finite volume scheme for nonlinear diffusion problems on general meshes. The new vertex interpolation algorithm is derived by applying a special limit procedure to the well-known MPFA-O method. Since the MPFA-O method for 3D cases has been addressed in some studies, the new vertex interpolation algorithm can be extended to 3D cases naturally. More interesting is that the solvability of the corresponding local system is proved under some assumptions. Additionally, we modify the edge flux approximation by an edge-based discretization of diffusion coefficient, and thus the improved scheme is free of the so-called numerical heat-barrier issue suffered by many existing cell-centered or hybrid schemes. The final scheme allows arbitrary continuous or discontinuous diffusion coefficients and can be applicable to arbitrary star-shaped polygonal meshes. A second-order convergence rate for the approximate solution and a first-order accuracy for the flux are observed in numerical experiments. In the comparative experiments with some existing vertex interpolation algorithms, the new algorithm shows obvious improvement on highly distorted meshes.     

Two-Dimensional Reproducing Kernel and Surface Interpolation

One-dimensional polynomial interpolation does not guarantee the convergency and the stability during numerical computation. For two (or multi)-dimensional interpolation, difficulties are much more raising. There are many fundamental problems, which are left open. In this paper,we begin with the discussion of reproducing kernel in two variables. With its help we deduce a two-dimensional interpolation formula. According to this formula, the process of interpolation will converge uniformly, whenever the knot system is thickened in finitely. We have also proven that the error function will decrease monotonically in the norm when the number of knot points is increased. In our formula, knot points may be chosen arbitrarily without any request of regularity about their arrangement. We also do not impose any restriction on the number of knot points. For the case of multi-dimensional interpolation, these features may be important and essential.