Faster least squares approximation

Least squares approximation is a technique to find an approximate solution to a system of linear equations that has no exact solution. In a typical setting, one lets n be the number of constraints and d be the number of variables, with n >> d{n \gg d}. Then, existing exact methods find a solution vector in O(nd ²) time. We present two randomized algorithms that provide accurate relative-error approximations to the optimal value and the solution vector of a least squares approximation problem more rapidly than existing exact algorithms. Both of our algorithms preprocess the data with the Randomized Hadamard transform. One then uniformly randomly samples constraints and solves the smaller problem on those constraints, and the other performs a sparse random projection and solves the smaller problem on those projected coordinates. In both cases, solving the smaller problem provides relative-error approximations, and, if n is sufficiently larger than d, the approximate solution can be computed in O(nd ln d) time.     

MULTILEVEL AUGMENTATION METHODS FOR SOLVING OPERATOR EQUATIONS

We introduce multilevel augmentation methods for solving operator equations based on direct sum decompositions of the range space of the operator and the solution space of the operator equation and a matrix splitting scheme. We establish a general setting for the analysis of these methods, showing that the methods yield approximate solutions of the same convergence order as the best approximation from the subspace. These augmentation methods allow us to develop fast, accurate and stable nonconventional numerical algorithms for solving operator equations. In particular, for second kind equations, special splitting techniques are proposed to develop such algorithms. These algorithms are then applied to solve the linear systems resulting from matrix compression schemes using wavelet-like functions for solving Fredholm integral equations of the second kind. For this special case, a complete analysis for computational complexity and convergence order is presented. Numerical examples are included to demonstra     

Numerical solution of a free boundary problem associated to investments with instantaneous irreversible environmental effects

In this work, some numerical methods are proposed to solve a problem which models the joint utility of starting at optimal time an industrial process that provides some benefits but also implies some irreversible effects on the environment. The mathematical model is posed in terms of an obstacle problem associated to an elliptic equation on an unbounded domain. First, following Díaz and Faghloumi [5], an equivalent formulation on a bounded domain is proposed by means of adequate changes of variables and unknown. Next, projected Gauss-Seidel and Lions-Mercier type algorithms to solve the finite elements discretized problem are proposed; the latter is combined with multigrid techniques and adaptive refinement. The algorithms efficiency is first illustrated by some numerical tests on examples with known analytical solution or theoretically stated properties. Finally, some more realistic examples are presented for which there are not known properties of the solution.     

Lattice Approximations for Stochastic Quasi-Linear Parabolic Partial Differential Equations Driven by Space-Time White Noise I

We approximate quasi-linear parabolic SPDEs substituting the derivatives in the space variable with finite differences. When the nonlinear terms in the equation are Lipschitz continuous we estimate the rate of L^p convergence of the approximations and we also prove their almost sure uniform convergence to the solution. When the nonlinear terms are not Lipschitz continuous we obtain this convergence in probability, if the pathwise uniqueness for the equation holds.     

Time-marching algorithms for initial-boundary value problems based upon “approximate approximations”

New time marching algorithms for solving initial-boundary value problems for semi-linear parabolic and hyperbolic equations are described. With respect to the space variable the discretization is based upon a method of approximate approximation proposed by the second author. We use approximate approximations of the fourth order. In time the algorithms are finite-difference schemes of either first or second approximation order. At each time step the approximate solution is represented by an explicit analytic formula. The algorithms are stable under mild restrictions to the time step which come from the non-linear part of the equation. Some computational results and hints on crucial implementation issues are provided.Supported by the Center for Applied and Industrial Mathematics, Department of Mathematics, Linköping University, Sweden.     

On efficient numerical methods for an initial-boundary value problem with nonlocal boundary conditions

Many physical phenomena are modeled by nonclassical hyperbolic boundary value problems with nonlocal boundary conditions. In this paper, the problem of solving the one-dimensional wave equation subject to given initial and non-local boundary conditions is considered. These non-local conditions arise mainly when the data on the boundary cannot be measured directly. Several finite difference methods with low order have been proposed in other papers for the numerical solution of this one dimensional non-classic boundary value problem. Here, we derive a new family of efficient three-level algorithms with higher order to solve the wave equation and also use a Simpson formula with higher order to approximate the integral conditions. Additionally, the fourth-order formula is also adapted to nonlinear equations, in particular to the well-known nonlinear Klein–Gordon equations which many physical problems can be modeled with. Numerical results are presented and are compared with some existing methods showing the efficiency of the new algorithms.     

Approximations of Solutions to Abstract Neutral Functional Differential Equation

In the present work, we study the approximations of solutions to the abstract neutral functional differential equations with bounded delay. We consider an associated integral equation and a sequence of approximate integral equations. We establish the existence and uniqueness of the solutions to every approximate integral equation using the fixed point arguments. We then prove the convergence of the solutions of the approximate integral equations to the solution of the associated integral equation. Next, we consider the Faedo–Galerkin approximations of the solutions and prove some convergence results. Finally, we demonstrate the application of the results established.     

A new stable,explicit, and generic third-order method for simulating conductive heat transfer

In this paper we introduce a new type of explicit numerical algorithm to solve the spatially discretized linear heat or diffusion equation. After discretizing the space variables as in standard finite difference methods, this novel method does not approximate the time derivatives by finite differences, but use three stage constant-neighbor and linear neighbor approximations to decouple the ordinary differential equations and solve them analytically. In the final expression for the new values of the variable, the time step size appears not in polynomial or rational, but in exponential form with negative coefficients, which can guarantee unconditional stability. The scheme contains a free parameter p. We show that the convergence of the method is third-order in the time step size regardless of the values of p, and, according to von Neumann stability analysis, the method is stable for a wide range of p. We validate the new method by testing the results in a case where the analytical solution exists, then we demonstrate the competitiveness by comparing its performance with several other numerical solvers.     

Solving Schrödinger equation by using modified variational iteration and homotopy analysis methods

In this paper, a nonlinear Schr ö dinger equation is solved by using the variational iteration method (VIM), modified variational iteration method (MVIM) and homotopy analysis method (HAM) numerically. For each method, the approximate solution of this equation is calculated based on a recursive relation which its components are computed easily. The existence and uniqueness of the solution and the convergence of the proposed methods are proved. A numerical example is studied to demonstrate the accuracy of the given algorithms     

An optimal Gauss–Markov approximation for a process with stochastic drift and applications

We consider a linear stochastic differential equation with stochastic drift. We study the problem of approximating the solution of such equation through an Ornstein–Uhlenbeck type process, by using direct methods of calculus of variations. We show that general power cost functionals satisfy the conditions for existence and uniqueness of the approximation. We provide some examples of general interest and we give bounds on the goodness of the corresponding approximations. Finally, we focus on a model of a neuron embedded in a simple network and we study the approximation of its activity, by exploiting the aforementioned results.     

Application of homotopy-perturbation and variational iteration methods to nonlinear heat transfer and porous media equations

Perturbation methods depend on a small parameter which is difficult to be found for real-life nonlinear problems. To overcome this shortcoming, two new but powerful analytical methods are introduced to solve nonlinear heat transfer problems in this article; one is He's variational iteration method (VIM) and the other is the homotopy-perturbation method (HPM). The VIM is to construct correction functionals using general Lagrange multipliers identified optimally via the variational theory, and the initial approximations can be freely chosen with unknown constants. The HPM deforms a difficult problem into a simple problem which can be easily solved. Nonlinear convective–radiative cooling equation, nonlinear heat equation (porous media equation) and nonlinear heat equation with cubic nonlinearity are used as examples to illustrate the simple solution procedures. Comparison of the applied methods with exact solutions reveals that both methods are tremendously effective.     

Efficient numerical methods for radiation in gas turbines

Numerical methods for radiative heat transfer equations coupled to a temperature equation are considered. Efficient solution methods and approximate equations for this system are investigated and a comparative numerical study of the different approximations is given. The approximate equations considered in this paper include moment methods and diffusive approximations. Fast iterative solvers for the problem like multilevel methods with suitable preconditioning are considered in detail. Numerical experiments and comparisons in different space dimensions and for various physical situations are presented.     

Adaptive multilevel methods in space and time for parabolic problems-the periodic case

The aim of this paper is to display numerical results that show the interest of some multilevel methods for problems of parabolic type. These schemes are based on multilevel spatial splittings and the use of different time steps for the various spatial components. The spatial discretization we investigate is of spectral Fourier type, so the approximate solution naturally splits into the sum of a low frequency component and a high frequency one. The time discretization is of implicit/explicit Euler type for each spatial component. Based on a posteriori estimates, we introduce adaptive one-level and multilevel algorithms. Two problems are considered: the heat equation and a nonlinear problem. Numerical experiments are conducted for both problems using the one-level and the multilevel algorithms. The multilevel method is up to 70% faster than the one-level method.

     

Rational interpolation and approximate solution of integral equations

In the space of continuous periodic functions, we construct interpolation rational operators, use them to obtain quadrature formulas with positive coefficients which are exact on rational trigonometric functions of order 2n, and suggest an algorithm for an approximate solution of integral equations of the second kind. We estimate the accuracy of the approximate solution via the best trigonometric rational approximations to the kernel and the right-hand side of the integral equation.     

A level set approach for computing discontinuous solutions of Hamilton-Jacobi equations

We introduce two types of finite difference methods to compute the L-solution and the proper viscosity solution recently proposed by the second author for semi-discontinuous solutions to a class of Hamilton-Jacobi equations. By regarding the graph of the solution as the zero level curve of a continuous function in one dimension higher, we can treat the corresponding level set equation using the viscosity theory introduced by Crandall and Lions. However, we need to pay special attention both analytically and numerically to prevent the zero level curve from overturning so that it can be interpreted as the graph of a function. We demonstrate our Lax-Friedrichs type numerical methods for computing the L-solution using its original level set formulation. In addition, we couple our numerical methods with a singular diffusive term which is essential to computing solutions to a more general class of HJ equations that includes conservation laws. With this singular viscosity, our numerical methods do not require the divergence structure of equations and do apply to more general equations developing shocks other than conservation laws. These numerical methods are generalized to higher order accuracy using weighted ENO local Lax-Friedrichs methods as developed recently by Jiang and Peng. We verify that our numerical solutions approximate the proper viscosity solutions obtained by the second author in a recent Hokkaido University preprint. Finally, since the solution of scalar conservation law equations can be constructed using existing numerical techniques, we use it to verify that our numerical solution approximates the entropy solution.

     

A Class of Fejér Convergent Algorithms,Approximate Resolvents and the Hybrid Proximal-Extragradient Method

A new framework for analyzing Fejér convergent algorithms is presented. Using this framework, we define a very general class of Fejér convergent algorithms and establish its convergence properties. We also introduce a new definition of approximations of resolvents, which preserves some useful features of the exact resolvent and use this concept to present an unifying view of the Forward-Backward splitting method, Tseng’s Modified Forward-Backward splitting method, and Korpelevich’s method. We show that methods, based on families of approximate resolvents, fall within the aforementioned class of Fejér convergent methods. We prove that such approximate resolvents are the iteration maps of the Hybrid Proximal-Extragradient method, which is a generalization of the classical Proximal Point Algorithm.     

Numerical solutions of integro-differential equations and application of a population model with an improved Legendre method

In this paper, an improved Legendre collocation method is presented for a class of integro-differential equations which involves a population model. This improvement is made by using the residual function of the operator equation. The error differential equation, gained by residual function, has been solved by the Legendre collocation method (LCM). By summing the approximate solution of the error differential equation with the approximate solution of the problem, a better approximate solution is obtained. We give the illustrative examples to demonstrate the efficiency of the method. Also we compare our results with the results of the known some methods. In addition, an application of the population model is made.     

An approximation method using approximate approximations

The aim of this article is to extend the method of approximate approximations to boundary value problems. This method was introduced by V. Maz'ya in 1991 and has been used until now for the approximation of smooth functions defined on the whole space and for the approximation of volume potentials. In the present article we develop an approximation procedure for the solution of the interior Dirichlet problem for the Laplace equation in two dimensions using approximate approximations. The procedure is based on potential theoretical considerations in connection with a boundary integral equations method and consists of three approximation steps as follows. In the first step, the unknown source density in the potential representation of the solution is replaced by approximate approximations. In the second, the decay behavior of the generating functions is used to gain a suitable approximation for the potential kernel, and in the third, Nyström's method leads to a linear algebraic system for the approximate source density. For every step a convergence analysis is established and corresponding error estimates are given.     

A theoretical analysis of a new finite volume scheme for second order hyperbolic equations on general nonconforming multidimensional spatial meshes

We consider the wave equation, on a multidimensional spatial domain. The discretization of the spatial domain is performed using a general class of nonconforming meshes which has been recently studied for stationary anisotropic heterogeneous diffusion problems, see Eymard et al. (IMAJ Numer Anal 30 (2010), 1009–1043). The discretization in time is performed using a uniform mesh. We derive a new implicit finite volume scheme approximating the wave equation and we prove error estimates of the finite volume approximate solution in several norms which allow us to derive error estimates for the approximations of the exact solution and its first derivatives. We prove in particular, when the discrete flux is calculated using a stabilized discrete gradient, the convergence order is \begin{align*} h_\mathcal{D}\end{align*} (resp. k) is the mesh size of the spatial (resp. time) discretization. This estimate is valid under the regularity assumption \begin{align*}u\in C^3(\lbrack 0,T\rbrack;C^2(\overline{\Omega}))\end{align*} for the exact solution u. The proof of these error estimates is based essentially on a comparison between the finite volume approximate solution and an auxiliary finite volume approximation. © 2012 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2013     

Mesh adaptation based on functional a posteriori estimates with Raviart-Thomas approximation

Adaptive algorithms based on functional a posteriori estimates for the Dirichlet problem for the stationary diffusion equation with jump discontinuities in the equation coefficients are compared. The algorithms have been implemented in MATLAB with the use of both standard finite element approximations and the zero-order Raviart-Thomas approximation. The adaptation results are analyzed using indicators of the local error distribution. Specifically, sequences of finite-element partitions, effectivity indices of estimates, and relative errors of approximate solutions are compared.