Super-fast validated solution of linear systems

Validated solution of a problem means to compute error bounds for a solution in finite precision. This includes the proof of existence of a solution. The computed error bounds are to be correct including all possible effects of rounding errors. The fastest known validation algorithm for the solution of a system of linear equations requires twice the computing time of a standard (purely) numerical algorithm. In this paper we present a super-fast validation algorithm for linear systems with symmetric positive definite matrix. This means that the entire computing time for the validation algorithm including computation of an approximated solution is the same as for a standard numerical algorithm. Numerical results are presented.     

Reconstruction of controls in exponentially stable linear systems subjected to small perturbations

The problem of the dynamical reconstruction of the variable input of an exponentially stable linear system subjected to small non-linear perturbations is considered. In the case of inaccurate observations of its phase trajectory, an algorithm for solving this problem is given, based on the method of control with a model. The algorithm is stable to data interference and computation errors. General constructions are illustrated by an example in which the problem of reconstructing the input of an oscillatory section is discussed.     

On the reconstruction of inputs in linear parabolic equations

The problem of reconstructing distributed inputs in linear parabolic equations is investigated. The algorithm proposed for solving this problem is stable with respect to informational disturbances and computational errors. It is based on the combination of methods from the theory of ill-posed problems and from the theory of positional control. The process of reconstructing unknown inputs implemented by the algorithm employs inaccurate measurements of phase coordinates of the system at discrete sufficiently frequent times. In the case when the input is a function of bounded variation, an upper estimate is established for the convergence rate.     

Using the Sherman-Morrison-Woodbury inversion formula for a fast solution of tridiagonal block Toeplitz systems

A fast numerical algorithm for solving systems of linear equations with tridiagonal block Toeplitz matrices is presented. The algorithm is based on a preliminary factorization of the generating quadratic matrix polynomial associated with the Toeplitz matrix, followed by the Sherman-Morrison-Woodbury inversion formula and solution of two bidiagonal and one diagonal block Toeplitz systems. Tight estimates of the condition numbers are provided for the matrix system and the main matrix systems generated during the preliminary factorization. The emphasis is put on rigorous stability analysis to rounding errors of the Sherman-Morrison-Woodbury inversion. Numerical experiments are provided to illustrate the theory.     

Invasive weed optimization for model order reduction of linear MIMO systems

In this work, a model order reduction (MOR) technique for a linear multivariable system is proposed using invasive weed optimization (IWO). This technique is applied with the combined advantages of retaining the dominant poles and the error minimization. The state space matrices of the reduced order system are chosen such that the dominant eigenvalues of the full order system are unchanged. The other system parameters are chosen using the invasive weed optimization with objective function to minimize the mean squared errors between the outputs of the full order system and the outputs of the reduced order model when the inputs are unit step. The proposed algorithm has been applied successfully, a 10th order Multiple-Input–Multiple-Output (MIMO) linear model for a practical power system was reduced to a 3rd order and compared with recently published work.     

Solving a system of linear inequalities for generating test data

Data Flow Analysis can be used to find some of the errors in a computer program and gives as output a set of dubious paths of the investigated program, which have to be checked for executability. This can be done by solving a system of inequalities in order to obtain input data for that path. This article discusses how to obtain a reliable solution of this system in the linear case, when rounding effects are taken into account. The method is based on the simplex algorithm from linear programming, and returns a solution in the middle of the feasible region. The general nonlinear case is much more difficult to handle.     

A time-decomposition algorithm for a stiff linear two-point boundary-value problem and its application to a nonlinear optimal control problem

An algorithm is proposed to solve a stiff linear two-point boundary-value problem (TPBVP). In a stiff problem, since some particular solutions of the system equation increase and others decrease rapidly as the independent variable changes, the integration of the system equation suffers from numerical errors. In the proposed algorithm, first, the overall interval of integration is divided into several subintervals; then, in each subinterval a sub-TPBVP with arbitrarily chosen boundary values is solved. Second, the exact boundary values which guarantee the continuity of the solution are determined algebraically. Owing to the division of the integration interval, the numerical error is effectively reduced in spite of the stiffness of the system equation. It is also shown that the algorithm is successfully imbedded into an interaction-coordination algorithm for solving a nonlinear optimal control problem.The authors would like to thank Mr. T. Sera and Mr. H. Miyake for their help with the calculations.     

Numerical differentiation – a general purpose algorithm

A general algorithm for finding finite-difference approximations to derivatives is presented. The algorithm uses a linear combination of suitable Taylor expansions, and is sufficiently general to cater for non-equispaced nodes. It also provides analytical expressions for truncation and round-off errors.     

Grammatical Verification for Mathematical Formula Recognition Based on Context-Free Tree Grammar

This paper proposes the use of a formal grammar for the verification of mathematical formulae for a practical mathematical OCR system. Like a C compiler detecting syntax errors in a source file, we want to have a verification mechanism to find errors in the output of mathematical OCR. A linear monadic context-free tree grammar (LM-CFTG) is employed as a formal framework to define “well-formed” mathematical formulae. A cubic time parsing algorithm for LM-CFTGs is presented. For the purpose of practical evaluation, a verification system for mathematical OCR is developed, and the effectiveness of the system is demonstrated by using the ground-truthed mathematical document database InftyCDB-1 and a misrecognition database newly constructed for this study.     

Spectral properties of MCMC algorithms for Bayesian linear regression with generalized hyperbolic errors

We study MCMC algorithms for Bayesian analysis of a linear regression model with generalized hyperbolic errors. The Markov operators associated with the standard data augmentation algorithm and a sandwich variant of that algorithm are shown to be trace-class.     

A second-order accurate three sub-step composite algorithm for structural dynamics

In this paper, a novel three sub-step composite algorithm with desired numerical properties is developed. The proposed method is a self-starting, unconditionally stable and second-order accurate implicit algorithm without overshoot. Particularly, the second-order accuracy in time is achieved in its final form, but it is not required in each sub-step. Its unique algorithmic parameter is analyzed to achieve the unconditional stability and it shares the identical effective stiffness matrix inside three sub-steps to save the computational cost in linear analyses. The same as the Bathe algorithm, the proposed algorithm is always L-stable, meaning that the spurious high-frequency modes can be effectively eliminated. Three numerical examples are simulated to illustrate the superiority of the proposed algorithm over some existing implicit algorithms. The first numerical simulation, solving a linear single-degree-of-freedom system, shows less period elongation errors and the second-order accuracy of the present scheme. The second one, a clamped-free bar excited by the end load, shows the ability of effectively damping out the unexpected high-frequency modes. The last example solves the nonlinear mass-spring system with variable degree-of-freedoms and illustrates that the composite sub-step algorithm can save more computational cost than the traditional implicit algorithm when the integration step size is selected appropriately.     

Optimal Conditional Estimation: Average Case Setting

We consider an estimation problem which appears in the identification of systems by means of restricted complexity models: find the optimal approximation to an element of a linear normed space (a system) based on noisy information, subject to the restriction that approximations (models) can be selected from a prescribed subspace M of the problem element space. In contrast to the worst-case optimization criterion, which may be pessimistic, in this paper the quality of an identification algorithm is measured by its local average performance. Two types of local average errors are considered: for a given information (measurement) y and for a given unknown element x, the latter in two versions. For a wide spectrum of norms in the measurement space, we define an optimal algorithm and give expressions for its average errors which show the dependence on information, information errors, unmodelled dynamics, and norm in the measurement space.     

块循环矩阵方程组的新算法

1　基本概念形如 A=a1 a2 … a Na N a1 … a N- 1?彙?廰2 a3 … a1的矩阵称为由 a1 ,a2 ,… ,a N 生成的循环矩阵 .力学和工程中的轴对称结构的计算产生上述循环矩阵 [2 - 3] .以循环矩阵A为系数矩阵的方程组 ,称为循环矩阵方程组 .已有的求解循环矩阵方程组的办法主要是各种迭代法 ,如递推法及 SOR,SSOR,SAOR超松弛迭代法[2 - 6] 等 .定义 1　形如A =A1 A2 … ANAN A1… AN- 1?彙?廇2 A3… A1　 (Ai,i =1 ,2 ,… ,N为 m阶矩阵 )的矩阵称为由 A1 ,A2 ,… ,AN 生成的块循环矩阵 .定义 2　系数矩阵 A为块循环矩阵的方程组AX …     

Stable computation of solutions of unstable linear initial value recursions

An algorithm is given for approximating dominated solutions of linear recursions, when some initial conditions are given. The stability of this algorithm is investigated and expressions for the truncation and rounding errors are derived. A number of practical questions concerning the algorithm is considered, and several numerical examples sustain the theory.     

Solution of an Overdetermined System of Linear Equations in $L_2$, $L_∞$, $L_P$ Norm Using L.S. Techniques

A lot of curve fitting problems of experiment data lead to solution of an overdetermined system of linear equations. But it is not clear prior to that whether the data are exact or contaminated with errors of an unknown nature. Consequently we need to use not only $L_2$-solution of the system but also $L_{\infty}$- or $L_p$-solution. In this paper, we propose a universal algorithm called the Directional Perturbation Least Squares (DPLS) Algorithm, which can give optimal solutions of an overdetermined system of linear equations in $L_2$, $L_{\infty}$,$L_p (1\leq p＜2)$ norms using only L.S. techniques (in $\S$2). Theoretical principle of the algorithm is given in $\S$ 3. Two examples are given in the end.     

Comments on practical implementation of Gomory's fractional algorithm

Gomory's fractional algorithm is widely used for solving integer linear programming problems. It is strongly influenced by round off errors and consequently has the disadvantage that in many cases the optimal solution is not reached. The present note describes a simple modification of this algorithm. The essential feature of this modification consists in conserving the integral structure of the problem. Thus the influence of round off errors is avoided. The power of our method is illustrated by a numerical example.     

A direct error analysis for least squares

A direct error analysis is given for orthogonal factorization methods for calculating the least squares solution of an overdetermined system of linear equations. The direct method has the interesting advantage in that it permits the separation of errors occurring in the transformation and back-substitution phases of solution. This shows the partial elimination of potentially significant terms occurring in different stages of the algorithm. Presumably it is prudent to minimize the error at each stage of the algorithm, so it is significant that numerical evidence shows column pivoting can reduce the magnitude of these terms. This is offered as an explanation for the common observation that column pivoting is beneficial in least squares calculations. We also summarize the corresponding error analysis for the calculation of the minimum norm solution of an underdetermined system using orthogonal transformations.     

Dual regularization and Pontryagin’s maximum principle in a problem of optimal boundary control for a parabolic equation with nondifferentiable functionals

A problem of optimal boundary control is considered for a divergent linear parabolic equation. Equality constraints of the problem are given by nondifferentiable functionals. A dual regularization algorithm stable to errors in initial data is constructed for solving the problem. Pontryagin’s maximum principle plays the key role in this algorithm.     

Approximate decoupling of multivariate polynomials using weighted tensor decomposition

Many scientific and engineering disciplines use multivariate polynomials. Decomposing a multivariate polynomial vector function into a sandwiched structure of univariate polynomials surrounded by linear transformations can provide useful insight into the function while reducing the number of parameters. Such a decoupled representation can be realized with techniques based on tensor decomposition methods, but these techniques have only been studied in the exact case. Generalizing the existing techniques to the noisy case is an important next step for the decoupling problem. For this extension, we have considered a weight factor during the tensor decomposition process, leading to an alternating weighted least squares scheme. In addition, we applied the proposed weighted decoupling algorithm in the area of system identification, and we observed smaller model errors with the weighted decoupling algorithm than those with the unweighted decoupling algorithm.     

线性Errors-in-Variables模型在确定汶川地震主震断层面中的应用

首先介绍线性Errors-in-Variables模型,给出求解回归系数的奇异值分解(SVD)算法和MATLAB源代码,其次指出在模型中所有变量均具有不可忽略的误差时,全最小二乘法得到回归系数估计更接近于模型中的真实系数,并通过理论分析和计算机仿真说明了这一结果,最后将线性模型和算法用于确定汶川大地震主震断层面,取得了与震源机制解一致的结果,说明了模型和算法的有效性。