关于二阶平稳马尔可夫过程的样本序列是否存在无后效性的讨论

本文指出了工程界关于高阶马尔可夫过程的一个错误定义,证明了(p=2)满足这个定义的平稳高斯过程是不存在的。本文还指出了,如果二阶微分方程的特征根是实的,那么由微分方程 x"(t)+α_1x′(t)+α_2x(t)=ε(t)(式中ε(t)是白噪声)描写的随机过程x(t)的平稳解的任意均匀采样序列都不可能是AR(2)序列,而由下面微分方程 x"(t)+α_1x′(t)+α_2(t)=ε′(t)+βε(t)描写的随机过程的平稳解,当β~2>max(c_1~2,c_2~2)时,(c_1,c_2是特征方程z~2+α_1z+α_2=0的根)至少存在一个采样间隔△_1,使相应的样本序列是AR(2)。如果特征方程有共轭复根。那么存在可列个离散采样间隔△_k,使方程的平稳解的相应样本序列是二阶平稳广义马尔可夫序列。     

常系数线性齐次递归式的一般解公式

本文给出常系数线性递归式 a_n=α_1a_(n-1)+α_2a_(n-2)+…+α_pa_(n-p),a_0=c_0,a_1=c_1,…,a_(p-1)=c_(p-1)的一般解公式 a_n=sum from k=0 to p-1(sum from i=k to p-1 c_iα_(p-i+k))F_(n-p-k)(n≥p),其中(?)     

线性移存器序列的伪随机特性

<正> §1.引言 线性移存器序列是指满足下面递归关系的二元序列a=(a_o,a_1,a_2…)a_i∈GF(2). a_(n+k)=c_1a_(n+k-1)+c_2a_(n+k-2)+…+c_na_k,c_i∈GF(2),(k=0,1,2,…)称f(x)=x~n+c_1x~(n-1)+…+c_n为产生序列a的线性移存器的联接多项式.以f(x)为联接多项式的线性移存器所产生的二元序列全体,形成二元域GF(2)上的线性空间,记之为G(f).本文的目的是由联接多项式f(x)的特点来刻划G(f)中非零二元周期序列的伪随机特性.     

Spectral method for solving nonlinear wave equations

In this paper,we consider the following nonlinear wave equations:(■~2φ)/(■t~2)-(■~2φ)/(■x~2)+μ~2φ+v~2x~2φ+f(|φ|~2)φ=0,(■~2x)/(■t~2-(■~2X)/(■X~2)+α~2x+α~2x+v~2x|φ|~2+g(X)=0with the periodic-initial conditions:φ(x-π,t)=φ(x+π,t),x(x-π,t)=x(x+v,t),φ(x,0)=■_0(x),φ_t(x,0)=■_1(x),X(x,0)=■_0(x),x_t(x,0)=■_1(x),-∞相似文献   

关于非线性蜕化抛物型方程解的唯一性(英文)

本文证明,在条件a(s)>0(s>0),a(0)=0,b(s)=0(a(s)~λ)(s≥0,0≤λ≤1、2),s~μ=0(a(s))(a>0,μ>0)之下,混合问题 μ_t=(a(u)u_x)_x+b(u)u_x, (x, t)∈R={(x, t)|-11时,解为唯一的,这改善了[1,2]的结果。     

平稳分枝超Lévy过程是一个随机偏微分方程的轨道唯一解

本文证明平稳(stable)分枝超Lévy过程的密度在一定条件下是如下随机偏微分方程的轨道唯一解:?/?tX_t(x)=AX_t(x)+bX_t(x)+X_(t-)(x)α/1■_t(x), t 0, x∈R,其中A是超Lévy过程底运动的生成元,α∈(1, 2)和b∈R是常数,{■_t(x):t≥0, x∈R}是一个无负跳的单边的α-平稳噪声.     

M 序列反馈函数的构造方法Ⅰ

设 f(x_0,x_1,…,x_(n-1))=x_0+f_0(x_1,…,x_(n-1))是一 n 元非奇布尔函数,其中加法是模2加.假定二元域 F_2上的无穷序列 α=(a_0,a_1,a_2,…),a_i∈F_2,i≥0,满足a_(k+n)=f(a_k,a_(k+1),…,a_(k+n-1),(?)k≥0,则称α是以 f 为反馈函数的 n 级移位寄存器序列,并以(?)(f)记所有以 f 为反馈函数的亭列组成的集合.因为 f 非奇,所以(?)(f)中的序列都是周期序列.对于 α∈(?)(f),α     

关于 Poincaré 型方程解的渐近性态的若干注记

<正> Ⅰ.引言假若 n 阶线性微分方程y~(n)+α_1(x)y~((n-1))+…+α_n(x)y=α_0(x) (**)的系数α_v(x),当 x 无限增长时渐近于常数α_v:(?)α_v(x)=α_v (v=1,2,…,n)则称方程(**)为 Poincaré 型微分方程(简称为 P 型方程).θ(λ)=λ~n+α_1λ~(n-1)+…+α_n=0称为它的特征方程.     

拟线性蜕化抛物型方程广义解的正则性和唯一性

<正> 考虑拟线性蜕化抛物型方程的混合问题: u_t=(u~m)xx+b(u)u_x,Q:{00},(1) u(0,t)=ψ_1(t),t≥0,(2) u(1,t)=ψ_2(t),t≥0,(3) u(x,0)=u_o(x),0≤x≤1,(4) 其中m>1,u_o(x),ψ_i(t)(i=1,2)适合条件:     

马氏过程的可加泛函与停时变换(Ⅱ)

定义4.1 设 X=(Ω(?),(?)_t,X_t,θ_t,P~x,T)是以(E_Δ,(?)_Δ)为状态空间的随机过程,称(Ω,(?))上的随机变量族 M={M_t,0≤t≤∞}为 X 的可乘泛函,如果(1)M_t∈(?)_t,((?)t≥0);(2)M_(s+t)=M_t(M_s(?)θ_t),((?) s、t≥0);(3)0≤M_t≤1,((?)t≥0).若 t(?)M_t 右连续(连续),则称 M 是右连续(连续)可乘泛函。对 X 的可乘泛函 M=     

A hybrid graph-genetic method for domain decomposition

A new method is developed for finite element (FE) domain decomposition. This method employs a hybrid graph-genetic algorithm for graph partitioning and correspondingly bisects finite element (FE) meshes.

A weighted incidence graph is first constructed for the FE mesh, denoted by G₀. A coarsening process is then performed using heavy-edge matching. A sequence of such operations is employed in “n” steps, which leads to the formation of G_n with a size suitable for genetic algorithm applications.

Hereafter, G_n is bisected using conventional genetic algorithm. The shortest route tree algorithm is used for the formation of the initial population in genetic algorithm. Then an uncoarsening process is performed and the results are transferred to the graph G_n−1. The initial population for genetic algorithm on G_n−1is constructed from the results of G_n. This process is repeated until G₀ is obtained in the uncoarsening operation. Employing the properties of G₁, the graph G₀ is bisected by the genetic algorithm.     

A Mehrotra-Type Predictor-Corrector Algorithm for P*(κ) Linear Complementarity Problems

Mehrotra-type predictor-corrector algorithm,as one of most efficient interior point methods,has become the backbones of most optimization packages.Salahi et al.proposed a cut strategy based algorithm for linear optimization that enjoyed polynomial complexity and maintained its efficiency in practice.We extend their algorithm to P_*（κ）linear complementarity problems.The way of choosing corrector direction for our algorithm is different from theirs. The new algorithm has been proved to have an ο(（1+4κ）（17+19κ） √（1+2κn）^3/2log[（x⁰）^Ts⁰/ε] worst case iteration complexity bound.An numerical experiment verifies the feasibility of the new algorithm.     

On embedding an outer-planar graph in a point set

Given an n-vertex outer-planar graph G and a set P of n points in the plane, we present an O(nlog³n) time and O(n) space algorithm to compute a straight-line embedding of G in P, improving upon the algorithm in [8,12] that requires O(n²) time. Our algorithm is near-optimal as there is an Ω(nlogn) lower bound for the problem [4]. We present a simpler O(nd) time and O(n) space algorithm to compute a straight-line embedding of G in P where lognd2n is the length of the longest vertex disjoint path in the dual of G. Therefore, the time complexity of the simpler algorithm varies between O(nlogn) and O(n²) depending on the value of d. More efficient algorithms are presented for certain restricted cases. If the dual of G is a path, then an optimal Θ(nlogn) time algorithm is presented. If the given point set is in convex position then we show that O(n) time suffices.     

Full transversal matroids, strict gammoids, and the matroid components problem

We provide two algorithms for finding dependence graphs both in a full transversal matroid and in its dual, a strict gammoid. The first algorithm is based on directed paths in the directed graph associated with a strict gammoid; its complexity is O(|L|(|V-L|+|E|)), where L is the link-set of the gammoid. The second algorithm is based on a special property of Gaussian elimination in a matrix of indeterminates representing a full transversal matroid; it complexity is o(m²n), where m is the rank of the matroid and n the cardinality of the underlying set. We provide an algorithm for listing all bases in, and calculating the Whitney and Tutte polynomials for, a full transversal matroid or a strict gammoid. The complexity of this algorithm is 0(N(n-m) (|E| + m²)), where N is the number of bases.     

On the algorithm of the solution of the signorini problem

An algorithm is proposed for solving the Signorini problem /1/ in the formulation of a unilateral variational problem for the boundary functional in the zone of possible contact /2/. The algorithm is based on a dual formulation of Lagrange maximin problems for whose solution a decomposition approach is used in the following sense: a Ritz process in the basis functions that satisfy the linear constraint of the problem, the differential equation in the domain, is used in solving the minimum problem (with fixed Lagrange multipliers); the maximum problem is solved by the method of descent (a generalization of the Frank-Wolf method) under convexity constraints on the Lagrange multipliers. The algorithm constructed can be conisidered as a modification of the well-known algorithm to find the Udzawa-Arrow-Hurwitz saddle points /3, 4/. The convergence of the algorithm is investigated. A numerical analysis of the algorithm is performed in the example of a classical contact problem about the insertion of a stamp in an elastic half-plane under approximation of the contact boundary by isoparametric boundary elements. The comparative efficiency of the algorithm is associated with the reduction in the dimensionality of the boundary value problem being solved and the possibility of utilizing the calculation apparatus of the method of boundary elements to realize the solution.     

求反对称阵特征值的新算法

1971年,M.H.C.Paardekooper将对称阵的Jacobi思想推广到反对称阵,给出一个求反对称阵特征值的实用算法(简称P算法).但P算法仅考虑到矩阵的反对称性,未利用其纯虚数特征值共轭成对的性质,而且也未探讨特征值共轭对相重与否对运算量的影响.鉴于此,本文提出一个新算法,其运算量比P算法少得多. 我们先用Givens相似变换(其快速算法见§3之3.2)化反对称阵A为三对角反对称     

Fast algorithm for viscous Cahn-Hilliard equation

The main purpose of this paper is to solve the viscous Cahn-Hilliard equation via a fast algorithm based on the two time-mesh (TT-M) finite element (FE) method to ease the problem caused by strong nonlinearities. The TT-M FE algorithm includes the following main computing steps. First, a nonlinear FE method is applied on a coarse time-mesh τ_c. Here, the FE method is used for spatial discretization and the implicit second-order θ scheme (containing both implicit Crank-Nicolson and second-order backward difference) is used for temporal discretization. Second, based on the chosen initial iterative value, a linearized FE system on time fine mesh is solved, where some useful coarse numerical solutions are found by Lagrange’s interpolation formula. The analysis for both stability and a priori error estimates is made in detail. Numerical examples are given to demonstrate the validity of the proposed algorithm. Our algorithm is compared with the traditional Galerkin FE method and it is evident that our fast algorithm can save computational time.     

Space reduction and an extension for a hidden line elimination algorithm

A simple intersection sensitive algorithm for the hidden line elimination problem, was presented by Nurmi in 1985. This algorithm has O((n + I) logn) time and space complexities, where n is the number of edges in the input scene and I is the number of their intersections on the projection plane. We describe a method that reduces the space requirements of the algorithm to O(n) while retaining the time complexity of O((n+I) logn). Furthermore we show that the algorithm can be easily extended to handle the more general problem of hidden surface removal.     

移动传感器网络中的最大价值路径扫描覆盖算法

扫描覆盖是当前移动传感器网络的一个重要覆盖技术,其主要通过规划移动传感器的巡逻路径对事件兴趣点（Points of Interest,POI）进行定期监测,从而以相对于普通覆盖方案更低廉的成本实现对POI监控．研究最大价值路径扫描覆盖,即使用移动传感器扫描覆盖分布在一条路径上的POI集合,使得被覆盖POI的价值总和达到最大．首先设计了一个基于线性规划随机取整的近似算法,通过将问题松弛并刻画为一个线性规划,然后对线性规划最优解取整得到一个扫描覆盖方案．该算法可在O（mn^3.5L）时间内求解,并具有可证明的近似比1-1/e．其次,通过扩展基于贪心策略的集合覆盖算法,设计了一个时间复杂度为O（m²n²）的贪心算法,其主要思想为循环选取一个单位巡逻范围覆盖POI价值最大的传感器．为优化运行时间,基于MVSCP问题的特殊结构将算法时间进一步改进至O（m log m+mn²）．最后,通过仿真实验分析所设计算法的实际性能.实验结果表明,线性规划随机取整算法运行时间低至整数规划算法的百分之一,但其所求解的质量只略低于整数规划算法;改进的贪心算法虽然不具有可证明的近似比,但其实际所求解的质量并不弱于线性规划随机取整算法,并且具有三者中最佳的运行时间．