非线性方程的基于重新参数化的裁剪求根方式

非线性方程的求根在计算机辅助几何设计、计算机图形学、信号处理、机器人等方面有着较为广泛的应用。文中提出基于重新参数化的三次裁剪求根算法,该算法可以用于非多项式方程的求根。首先,求解出插值四点的三次多项式;然后,寻找重新参数化函数,使得复合的插值多项式也插值对应的导数,从而提升对应的逼近阶和收敛阶。与已有的三次裁剪方法相比,所提方法能达到9次或更高的收敛阶。在区间内单根且有理三次裁剪方法需要计算包围多项式的某些情形下,所提方法可以包住对应的根。实例表明,在某些Newton方法失效的情形下,该方法也可以收敛到相应的实根。     

多项式方程区间内求根基于R2空间的3次裁剪方法

多项式方程的求根问题在求交、最近距离计算等方面有着广泛的应用.3次裁剪求根方法充分利用了Bernstein基函数较好的计算稳定性,避免了数值迭代求解的不稳定性,同时具有4次收敛的速度.不同于传统的基于R1空间内的3次裁剪方法,提出了基于R2空间内的3次裁剪方法.首先引入R2空间中一条曲线(t,f(t)),在该曲线给定的区间上选取3个点,并计算这3个点及其对应的切向;然后求解3次多项式曲线Ai(u),满足同时插值这3个点及其中2个点处的切向;最后选择适当的重新参数化函数φ(t),使得Ai(φ(t))和f(t)之间具有5次逼近阶.若给定的参数区间Φ充分小,A1(φ(t))和A2(φ(t))可以在区间Φ内直接包住f(t),从而节省了用于求解包围多项式的大量计算.实例结果表明,该方法具有更好的逼近效果、更快的收敛速度和更高的计算效率.     

基于拐点分割高阶奇次贝济埃曲线降一阶逼近

给出了2m+1(m≥2)次贝济埃曲线降一阶逼近方法。该方法除了具有传统的端点约束和C1—约束外,还具有以下特点:基于欧几里德范数讨论逼近误差,更加符合人们的直观认识;对于分段降阶逼近的情形,不考虑尖点情形;首先考虑并采用了选择拐点的策略;考虑并采用了选择二重点(自交点、结点)等奇点的策略;考虑并采用了选择曲率局部极大值点的策略。数值试验表明:这几条策略的采用可以在很大程度上减少2m次贝济埃曲线段,而达到逼近2m+1次贝济埃平面曲线的容差要求。     

任意三角形Laplace特征值问题谱方法的数值对比研究

本文选取多项式、有理多项式以及三角函数等五类函数作为基函数,设计相应的谱方法逼近格式并实现相应算法,对任意三角形上Laplace特征值问题进行数值求解对比研究.比较实验结果显示,谱方法相较于经典有限差分、有限元等低阶方法有较多的可信特征值;其中的Koornwinder多项式谱方法与基于Koornwinder多项式的有理谱方法,其可信特征值的数量达到全部计算特征值的4/π~2,并且达到"指数阶收敛";而三角函数谱方法,则保持了稳定的收敛阶且有较多的可信特征值.     

用迭代法求解超越方程时重根的判别法

一、前言 对于超越方程 f(x)=0 (1)到目前为止已有许多求解的方法,对于各种方法,当所求的根为单根时,收敛性质一般都较好;当所求的根为p(p≥2)重根时,各种方法的收敛速度都要减慢,且p越大收敛越     

多层积分值三次样条拟插值

目的 在实际问题中,某些插值问题结点处的函数值往往是未知的,而仅仅知道一些连续等距区间上的积分值。为此提出了一种基于未知函数在连续等距区间上的积分值和多层样条拟插值技术来解决函数重构。该方法称之为多层积分值三次样条拟插值方法。方法 首先,利用积分值的线性组合来逼近结点处的函数值;然后,利用传统的三次B-样条拟插值和相应的误差函数来实现多层三次样条拟插值;最后,给出两层积分值三次样条拟插值算子的多项式再生性和误差估计。结果 选取无穷次可微函数对多层积分值三次样条拟插值方法和已有的积分值三次样条拟插值方法进行对比分析。数值实验印证了本文方法在逼近误差和数值收敛阶均稍占优。结论本文多层三次样条拟插值函数能够在整体上很好的逼近原始函数,一阶和二阶导函数。本文方法较之于已有的积分值三次样条拟插值方法具有更好的逼近误差和数值收敛阶。该方法对连续等距区间上积分值的函数重构具有普适性。     

带端点插值条件的Bézier曲线降多阶逼近

研究了两端点具有任意阶插值条件的Bézier曲线降多阶逼近的问题.对于给定的首末端点的各阶插值条件,给出了一种新的一次降多阶逼近算法,应用Chebyshev多项式逼近理论达到了满足端点插值条件下的近似最佳一致逼近.此算法易于实现,误差计算简单,且所得降阶曲线具有很好的逼近效果,结合分割算法,可获得相当高的误差收敛速度.     

2m次Bèzier曲线自适应降次逼近算法

给出了封闭的2m次Bèzier曲线的降次逼近公式,并讨论了相应的逼近误差。文章工作除了具有传统的端点约束、C1—约束外,还具有以下特点:首先,基于欧几里德范数讨论逼近误差,更加符合人们的认识;其次,对于分段降阶逼近的情形,首先考虑并采用了选择拐点的策略;第三,考虑并采用了选择极大值点的策略。大量数值试验表明:第二、三两条策略的采用可以在很大程度上减少了2m-1次Bèzier曲线段达到逼近2m次Bèzier平面曲线的容差要求。     

几何区间裁剪算法收敛性分析和比较

为了寻求简单、快速、稳定的求交算法来加速光线跟踪渲染三维场景,对一种快速计算2条平面曲线交点的方法--几何区间裁剪(GeoClip)算法进行了深入研究.严格证明了GeoClip算法在计算多项式的根以及计算2条平面曲线的交点中都具有三阶收敛性,该结果从理论上保证了GeoClip算法优于经典的曲线求交算法--Bézier Clipping算法;最后对GeoClip与二次裁剪(QuadClip)算法进行了比较,结果表明,虽然都是三阶收敛,但是GeoClip算法比QuadClip算法快30%左右.     

一类多项式光滑函数的逼近精度

针对一类支持向量机的多项式光滑函数,采用二分法求解它们尚未解决的逼近精度问题。为克服二分法可能会漏根的缺点,首先把多项式光滑函数的逼近精度问题表示为一个求逼近函数的最大值问题,把这个逼近函数分成4 段,分别求出每段的最大值,然后得到逼近函数在整个x轴上的最大值。并以1阶和2阶多项式光滑函数为例,用二分法解决了它们的逼近精度问题。研究表明,二分法是求解这类多项式光滑函数逼近精度的有效方法。     

An accelerated randomized Kaczmarz method via low-rank approximation

The Kaczmarz method for finding the solution to an overdetermined consistent system of linear equation Ax=b(A∈R^m×n) is an iterative algorithm that has found many applications ranging from computer tomography to digital signal processing. Recently, Strohmer and Vershynin proposed randomized Kaczmarz, and proved its exponential convergence. In this paper, motivated by idea of precondition, we present a modified version of the randomized Kaczmarz method where an orthogonal matrix was multiplied to both sides of the equation Ax=b, and the orthogonal matrix is obtained by low-rank approximation. Our approach fits the problem when m is huge and m?n. Theoretically, we improve the convergence rate of the randomized Kaczmarz method. The numerical results show that our approach is faster than the standard randomized Kaczmarz.     

Higher-order simultaneous methods for the determination of polynomial multiple zeros

Starting from Laguerre's method and using Newton's and Halley's corrections for a multiple zero, new simultaneous methods of Laguerre's type for finding multiple (real or complex) zeros of polynomials are constructed. The convergence order of the proposed methods is five and six, respectively. By applying the Gauss–Seidel approach, these methods are further accelerated. The lower bounds of the R-order of convergence of the improved (single-step) methods are derived. Faster convergence of all proposed methods is attained with negligible number of additional operations, which provides a high computational efficiency of these methods. A detailed convergence analysis and numerical results are given.     

Ostrowski-Like Method with Corrections for the Inclusion of Polynomial Zeros

In this paper we construct iterative methods of Ostrowski's type for the simultaneous inclusion of all zeros of a polynomial. Using the concept of the R-order of convergence of mutually dependent sequences, we present the convergence analysis of the total-step and the single-step methods with Newton and Halley's corrections. The case of multiple zeros is also considered. The suggested algorithms possess a great computational efficiency since the increase of the convergence rate is attained without additional calculations. Numerical examples and an analysis of computational efficiency are given.     

Generation of robust root loci for linear systems with parametric uncertainties in an ellipsoid

Given a parametric polynomial family p(s; Q) := {ⁿ _k=0 a_k (q)s^k : q ] Q}, Q R ^m , the robust root locus of p(s; Q) is defined as the two-dimensional zero set _p,Q := {s ] C:p(s; q) = 0 for some q ] Q}. In this paper we are concerned with the problem of generating robust root loci for the parametric polynomial family p(s; E) whose polynomial coefficients depend polynomially on elements of the parameter vector q ] E which lies in an m-dimensional ellipsoid E. More precisely, we present a computational technique for testing the zero inclusion/exclusion of the value set p(z; E) for a fixed point z in C, and then apply an integer-labelled pivoting procedure to generate the boundary of each subregion of the robust root locus _p,E . The proposed zero inclusion/exclusion test algorithm is based on using some simple sufficient conditions for the zero inclusion and exclusion of the value set p(z,E) and subdividing the domain E iteratively. Furthermore, an interval method is incorporated in the algorithm to speed up the process of zero inclusion/exclusion test by reducing the number of zero inclusion test operations. To illustrate the effectiveness of the proposed algorithm for the generation of robust root locus, an example is provided.     

C3连续的单位四元数插值样条曲线

目的 构造一类C³连续的单位四元数插值样条曲线,证明它的插值性和连续性,并把它应用于刚体关键帧动画设计中。方法 利用R³空间中插值样条曲线的5次多项式调配函数的累和形式构造了S³空间中单位四元数插值样条曲线,它不仅能精确通过一系列给定的方向,而且能生成C³连续的朝向曲线。结果 与Nielson的单位四元数均匀B样条插值曲线的迭代构造方法相比,所提方法避免了为获取四元数B样条曲线控制顶点对非线性方程组迭代求解的过程,提高了运算效率;与单位四元数代数三角混合插值样条曲线的构造方法（Su方法）相比,所提方法只用到多项式基,运算速度更快。本例中创建关键帧动画所需的时间与Nielson方法和Su方法相比平均下降了73%和33%。而且,相比前两种方法,所提方法产生的四元数曲线连续性更高,由C²连续提高到C³连续,这意味着动画中刚体的朝向变化更加自然。结论 仿真结果表明,本文方法对刚体关键帧动画设计是有效的,对实时性和流畅性要求高的动画设计场合尤为适用。     

On the improved Newton-like methods for the inclusion of polynomial zeros

The aim of this paper is to present some modifications of Newton's type method for the simultaneous inclusion of all simple complex zeros of a polynomial. Using the concept of the R-order of convergence of mutually dependent sequences, the convergence analysis shows that the convergence rate of the basic method is increased from 3 to 6 using Jarratt's corrections. The proposed method possesses a great computational efficiency since the acceleration of convergence is attained with only few additional calculations. Numerical results are given to demonstrate convergence properties of the considered methods.     

Completion time variance minimization in single machine and multi-machine systems

In this paper we consider the problem of minimizing the completion time variance of n jobs on a single machine with deterministic processing times. We propose a new heuristic and compare the results with existing popular heuristics for the problem. We also propose a method based on genetic algorithms to solve the problem. We present the worst case performance analysis of the proposed heuristic. We also consider the problem of minimizing the completion time variance of n jobs on m identical parallel machines in both restricted and unrestricted versions. A heuristic method and a method based on genetic algorithms are presented for both the cases and results of computational testing are provided. It is concluded that the proposed methods provide better results compared to existing methods for the single machine case as well as for the multi-machine case.     

Lp范数约束的多核半监督支持向量机学习方法

在机器学习领域,核方法是解决非线性模式识别问题的一种有效手段.目前,用多核学习方法代替传统的单核学习已经成为一个新的研究热点,它在处理异构、不规则和分布不平坦的样本数据情况下,表现出了更好的灵活性、可解释性以及更优异的泛化性能.结合有监督学习中的多核学习方法,提出了基于L_p范数约束的多核半监督支持向量机(semi-supervised support vector machine,简称S³VM)的优化模型.该模型的待优化参数包括高维空间的决策函数f_m和核组合权系数θm.同时,该模型继承了单核半监督支持向量机的非凸非平滑特性.采用双层优化过程来优化这两组参数,并采用改进的拟牛顿法和基于成对标签交换的局部搜索算法分别解决模型关于f_m的非平滑及非凸问题,以得到模型近似最优解.在多核框架中同时加入基本核和流形核,以充分利用数据的几何性质.实验结果验证了算法的有效性及较好的泛化性能.     

GENERATION OF EXACT QFT BOUNDS FOR PLANTS WITH AFFINELY DEPENDENT UNCERTAINTIES

This paper presents an efficient method for the generation of exact QFT bounds for robust sensitivity reduction and gain‐phase margin specifications for plants with affinely dependent uncertainties. It is shown that, for a plant with m affinely dependent uncertainties, the exact QFT bounds for robust sensitivity reduction and gain‐phase margin specifications at a given frequency and controller phase can be computed by solving m^2m‐1 bivariate polynomial inequalities corresponding to the edges of the parameter domain box. Moreover, the solution set for each bivariate polynomial inequality can be computed by solving for the real roots of one fourth‐order and six second‐order polynomials. This avoids the unfavorable trade‐off between the computational burden and the accuracy of QFT bounds that has arisen in the application of many existing QFT bound generation algorithms. Numerical examples are given to illustrate the proposed method and its computational superiority.