Solving a kind of boundary-value problem for ordinary differential equations using Fermi—The next generation CUDA computing architecture

The aim of this paper is to show that a special kind of boundary value problem for solving second-order ordinary differential equations can be efficiently solved on modern heterogeneous computer architectures based on CPU and GPU Fermi processors. Such a problem reduces to the problem of solving a large tridiagonal system of linear equations with an almost Toeplitz structure. The considered algorithm is based on the recently developed divide and conquer method for solving linear recurrence systems with constant coefficients.     

On the numerical solution of loaded systems of ordinary differential equations with nonseparated multipoint and integral conditions

We propose a numerical method of solving systems of loaded linear nonautonomous ordinary differential equations with nonseparated multipoint and integral conditions. This method is based on the convolution of integral conditions to obtain local conditions. This approach allows one to reduce solving the original problem to solving a Cauchy problem for a system of ordinary differential equations and linear algebraic equations. Numerous computational experiments on several test problems with the formulas and schemes proposed for the numerical solution have been carried out. The results of the experiments show that the approach is reasonably efficient.     

An algorithm for linear least squares problems with equality and nonnegativity constraints

We present a new algorithm for solving a linear least squares problem with linear constraints. These are equality constraint equations and nonnegativity constraints on selected variables. This problem, while appearing to be quite special, is the core problem arising in the solution of the general linearly constrained linear least squares problem. The reduction process of the general problem to the core problem can be done in many ways. We discuss three such techniques.The method employed for solving the core problem is based on combining the equality constraints with differentially weighted least squares equations to form an augmented least squares system. This weighted least squares system, which is equivalent to a penalty function method, is solved with nonnegativity constraints on selected variables.Three types of examples are presented that illustrate applications of the algorithm. The first is rank deficient, constrained least squares curve fitting. The second is concerned with solving linear systems of algebraic equations with Hilbert matrices and bounds on the variables. The third illustrates a constrained curve fitting problem with inconsistent inequality constraints.     

On the solution of boundary value problems with nonseparated multipoint and integral conditions

We suggest a numerical method for solving systems of linear nonautonomous ordinary differential equations with nonseparated multipoint and integral conditions. By using this method, which is based on the operation of convolution of integral conditions into local ones, one can reduce the solution of the original problem to the solution of a Cauchy problem for systems of ordinary differential equations and linear algebraic equations. We establish bounded linear growth of the error of the suggested numerical schemes. Numerical experiments were carried out for specially constructed test problems.     

Factorization method for linear and quasilinear singularly perturbed boundary value problems for ordinary differential equations

For linear singularly perturbed boundary value problems, we come up with a method that reduces solving a differential problem to a discrete (difference) problem. Difference equations, which are an exact analog of differential equations, are constructed by the factorization method. Coefficients of difference equations are calculated by solving Cauchy problems for first-order differential equations. In this case nonlinear Ricatti equations with a small parameter are solved by asymptotic methods, and solving linear equations reduces to computing quadratures. A solution for quasilinear singularly perturbed equations is obtained by means of an implicit relaxation method. A solution to a linearized problem is calculated by analogy with a linear problem at each iterative step. The method is tested against solutions to the known Lagerstrom-Cole problem.     

Numerical method of solution to loaded nonlocal boundary value problems for ordinary differential equations

A numerical method is suggested for solving systems of nonautonomous loaded linear ordinary differential equations with nonseparated multipoint and integral conditions. The method is based on the convolution of integral conditions into local ones. As a result, the original problem is reduced to an initial value (Cauchy) problem for systems of ordinary differential equations and linear algebraic equations. The approach proposed is used in combination with the linearization method to solve systems of loaded nonlinear ordinary differential equations with nonlocal conditions. An example of a loaded parabolic equation with nonlocal initial and boundary conditions is used to show that the approach can be applied to partial differential equations. Numerous numerical experiments on test problems were performed with the use of the numerical formulas and schemes proposed.     

Computational methods of solving the boundary value problems for the loaded differential and Fredholm integro‐differential equations

The article presents a new general solution to a loaded differential equation and describes its properties. Solving a linear boundary value problem for loaded differential equation is reduced to the solving a system of linear algebraic equations with respect to the arbitrary vectors of general solution introduced. The system's coefficients and right sides are computed by solving the Cauchy problems for ordinary differential equations. Algorithms of constructing a new general solution and solving a linear boundary value problem for loaded differential equation are offered. Linear boundary value problem for the Fredholm integro‐differential equation is approximated by the linear boundary value problem for loaded differential equation. A mutual relationship between the qualitative properties of original and approximate problems is obtained, and the estimates for differences between their solutions are given. The paper proposes numerical and approximate methods of solving a linear boundary value problem for the Fredholm integro‐differential equation and examines their convergence, stability, and accuracy.     

Global optimization of polynomial-expressed nonlinear optimal control problems with semidefinite programming relaxation

In this paper, we propose a new deterministic global optimization method for solving nonlinear optimal control problems in which the constraint conditions of differential equations and the performance index are expressed as polynomials of the state and control functions. The nonlinear optimal control problem is transformed into a relaxed optimal control problem with linear constraint conditions of differential equations, a linear performance index, and a matrix inequality condition with semidefinite programming relaxation. In the process of introducing the relaxed optimal control problem, we discuss the duality theory of optimal control problems, polynomial expression of the approximated value function, and sum-of-squares representation of a non-negative polynomial. By solving the relaxed optimal control problem, we can obtain the approximated global optimal solutions of the control and state functions based on the degree of relaxation. Finally, the proposed global optimization method is explained, and its efficacy is proved using an example of its application.     

Operator splitting methods for pricing American options under stochastic volatility

We consider the numerical pricing of American options under Heston’s stochastic volatility model. The price is given by a linear complementarity problem with a two-dimensional parabolic partial differential operator. We propose operator splitting methods for performing time stepping after a finite difference space discretization. The idea is to decouple the treatment of the early exercise constraint and the solution of the system of linear equations into separate fractional time steps. With this approach an efficient numerical method can be chosen for solving the system of linear equations in the first fractional step before making a simple update to satisfy the early exercise constraint. Our analysis suggests that the Crank–Nicolson method and the operator splitting method based on it have the same asymptotic order of accuracy. The numerical experiments show that the operator splitting methods have comparable discretization errors. They also demonstrate the efficiency of the operator splitting methods when a multigrid method is used for solving the systems of linear equations.     

Minimal residual methods for large scale Lyapunov equations

Projection methods have emerged as competitive techniques for solving large scale matrix Lyapunov equations. We explore the numerical solution of this class of linear matrix equations when a Minimal Residual (MR) condition is used during the projection step. We derive both a new direct method, and a preconditioned operator-oriented iterative solver based on CGLS, for solving the projected reduced least squares problem. Numerical experiments with benchmark problems show the effectiveness of an MR approach over a Galerkin procedure using the same approximation space.     

Problem of reconstructing a disturbance in a linear stochastic equation: The case of incomplete information

The problem of reconstructing an unknown deterministic disturbance characterizing the level of random noise in a linear stochastic second-order equation is investigated based on the approach of dynamic inversion theory. The reconstruction is performed with the use of discrete information on a number of realizations of one coordinate of the stochastic process. The problem under consideration is reduced to an inverse problem for a system of ordinary differential equations describing the covariance matrix of the original process. A finite-step solving algorithm based on the method of auxiliary controlled models is suggested. Its convergence rate with respect to the number of measured realizations is estimated.     

求解特征值互补问题的一类ABS算法

ABS算法是20世纪80年代初,由Abaffy,Broyden和Spedicato完成的用于求解线性方程组的含有三个参量的投影算法,是一类有限次迭代直接法。目前,ABS算法不仅可以求解线性与非线性方程组,还可以求解线性规划和具有线性约束的非线性规划等问题。本文即是利用ABS算法求解特征值互补问题的一种尝试,构造了求解特征值互补问题的ABS算法,证明了求解特征值互补问题的ABS算法的收敛性。数值例子充分验证了求解特征值互补问题的ABS算法的有效性。     

Numerical method for the simultaneous determination of the hydraulic properties of unsaturated porous media

This paper presents a numerical algorithm for solving the inverse coefficient problem for nonlinear parabolic equations. This problem arises in simultaneous determination of the hydraulic properties of unsaturated porous media from a simple outflow experiment. The novel feature of the method is that it is not based on output least squares. In this method, the unknown functions are represented as polygons (continuous and piecewise linear functions) every new linear pieces that are determined in each time step by using information based only on previous time intervals. The results of some numerical experiments are displayed.     

An extension of the Tau numerical algorithm for the solution of linear and nonlinear Lane–Emden equations

The purpose of this paper is to present a numerical algorithm for solving the Lane–Emden equations as singular initial value problems. The proposed algorithm is based on an operational Tau method (OTM). The main idea behind the OTM is to convert the desired problem to some operational matrices. Firstly, we use a special integral operator and convert the Lane–Emden equations to integral equations. Then, we use OTM to linearize the integral equations to some operational matrices and convert the problem to an algebraic system. The concepts, properties, and advantages of OTM and its application for solving Lane–Emden equations are presented. Some orthogonal polynomials are also used to reduce the volume of computations. Finally, several experiments of Lane–Emden equations including linear and nonlinear terms are given to illustrate the validity and efficiency of the proposed algorithm. Copyright © 2012 John Wiley & Sons, Ltd.     

Solving some problems for systems of linear ordinary differential equations with redundant conditions

Numerical methods are proposed for solving some problems for a system of linear ordinary differential equations in which the basic conditions (which are generally nonlocal ones specified by a Stieltjes integral) are supplemented with redundant (possibly nonlocal) conditions. The system of equations is considered on a finite or infinite interval. The problem of solving the inhomogeneous system of equations and a nonlinear eigenvalue problem are considered. Additionally, the special case of a self-adjoint eigenvalue problem for a Hamiltonian system is addressed. In the general case, these problems have no solutions. A principle for constructing an auxiliary system that replaces the original one and is normally consistent with all specified conditions is proposed. For each problem, a numerical method for solving the corresponding auxiliary problem is described. The method is numerically stable if so is the constructed auxiliary problem.     

求解摩擦接触问题的一个非内点光滑化算法

给出了一个求解三维弹性有摩擦接触问题的新算法,即基于NCP函数的非内点光滑化算法．首先通过参变量变分原理和参数二次规划法,将三维弹性有摩擦接触问题的分析归结为线性互补问题的求解;然后利用NCP函数,将互补问题的求解转换为非光滑方程组的求解;再用凝聚函数对其进行光滑化,最后用NEWTON法解所得到的光滑非线性方程组．方法具有易于理解及实现方便等特点．通过线性互补问题的数值算例及接触问题实例证实了该算法的可靠性与有效性．     

超定线性方程极大极小解的一种近似算法

本文通过构造一个无约束凸规划问题,建立了求超定线性方程组的极大极小解的一种近似算法,证明了算法的收剑性,并给出了初步的数值结果.     

基于对称化原理的对称区域分裂法

本文利用对称化原理,讨论了一种只需在子区域上计算两个完全独立子问题就可得到原问题解的对称区域分裂法,并用此方法求解线性算子方程和线性透射问题.此方法可作为并行算法在MIMD计算机上使用.     

Generalized implicit function theorem and its application to parametric optimal control problems

Many problems in physics and mathematics may be reduced to solving equations depending on a parameter. The justification of the existence of solutions to the equations and the sensitivity analysis may be conducted based on Implicit Function Theorem (IFT) under certain regularity assumptions. Provided the regularity assumptions do not hold, generalizations of IFT are needed in order to study solutions to the equations. The paper focuses on a particular generalization of IFT which is then applied to a parametric linear time-optimal control problem.     

二阶锥线性互补问题的低阶罚函数算法

本文研究了二阶锥线性互补问题的低阶罚函数算法.利用低阶罚函数算法将二阶锥线性互补问题转化为低阶罚函数方程组,获得了低阶罚函数方程组的解序列在特定条件下以指数速度收敛于二阶锥线性互补问题解的结果,推广了二阶锥线性互补问题的幂罚函数算法.数值实验结果验证了算法的有效性.