An optimal regularizing algorithm for the recovery of functionals in linear inverse problems with sourcewise represented solution

A linear operator equation with a sourcewise represented exact solution is solved approximately. To this end, the method of extending compacts developed in an earlier work is applied. Based on this method, a new algorithm is proposed for recovering the value of a linear functional at the solution of the linear operator equation. This algorithm is shown to be an optimal regularizing one.     

Perturbation analysis and condition numbers of scaled total least squares problems

The standard approaches to solving an overdetermined linear system Ax ≈ b find minimal corrections to the vector b and/or the matrix A such that the corrected system is consistent, such as the least squares (LS), the data least squares (DLS) and the total least squares (TLS). The scaled total least squares (STLS) method unifies the LS, DLS and TLS methods. The classical normwise condition numbers for the LS problem have been widely studied. However, there are no such similar results for the TLS and the STLS problems. In this paper, we first present a perturbation analysis of the STLS problem, which is a generalization of the TLS problem, and give a normwise condition number for the STLS problem. Different from normwise condition numbers, which measure the sizes of both input perturbations and output errors using some norms, componentwise condition numbers take into account the relation of each data component, and possible data sparsity. Then in this paper we give explicit expressions for the estimates of the mixed and componentwise condition numbers for the STLS problem. Since the TLS problem is a special case of the STLS problem, the condition numbers for the TLS problem follow immediately from our STLS results. All the discussions in this paper are under the Golub-Van Loan condition for the existence and uniqueness of the STLS solution. Yimin Wei is supported by the National Natural Science Foundation of China under grant 10871051, Shanghai Science & Technology Committee under grant 08DZ2271900 and Shanghai Education Committee under grant 08SG01. Sanzheng Qiao is partially supported by Shanghai Key Laboratory of Contemporary Applied Mathematics of Fudan University during his visiting.     

On the perturbation of least squares problems with equality constraints

Some new perturbation results are presented for least squares problems with equality constraints, in which relative errors are obtained on perturbed solutions, least squares residuals, and vectors of Lagrange multipliers of the problem, based on the equivalence of the problem to a usual least squares problem and optimal perturbation results for orthogonal projections.     

The Lagrange principle in the problem of optimal inversion of linear operators in finite-dimensional spaces with a priori information about its solution

The problem of solving a system of linear algebraic equations is examined. An application of the Lagrange principle to the optimal recovery in this problem is described. New optimal methods that use available information about the errors in the data and a priori information about the solution are proposed for solving such systems.     

On the variational process in optimal control theory

The variational process is established and applied to the development of the second variation for the free-final-time optimal control problem. First, it is shown that, given a change in the control (the independent variable), the change in the state (the dependent variable) consists of all orders of the change in the control. Hence, the change in the state is a total change. This implies that variations of dependent variations exist. Next, the variational relationship between time-constant and time-free variations is developed, and the formula for taking the variation of an integral is presented. The results are used to derive the second variation following three different approaches: taking the variation of the first variation after performing the integration by parts; taking the variation of the first variation before performing the integration by parts; and using the Taylor series approach. The ability to get the same result requires the existence of the total change in the state or of the variation of the state variation. Finally, if the nominal path is not an extremal, this process gives extra terms in the second variation.     

On the condition number of linear least squares problems in a weighted Frobenius norm

LetA be anm × n, m n full rank real matrix andb a real vector of sizem. We give in this paper an explicit formula for the condition number of the linear least squares problem (LLSP) defined by min Ax–b₂,x ⁿ . Let and be two positive real numbers, we choose the weighted Frobenius norm [A, b] _F on the data and the usual Euclidean norm on the solution. A straightforward generalization of the backward error of [9] to this norm is also provided. This allows us to carry out a first order estimate of the forward error for the LLSP with this norm. This enables us to perform a complete backward error analysis in the chosen norms.Finally, some numerical results are presented in the last section on matrices from the collection of [5]. Three algorithms have been tested: the QR factorization, the Normal Equations (NE), the Semi-Normal Equations (SNE).     

On optimal parameter estimation in credibility

The present paper is concerned with optimal estimation of the 1st and 2nd order structural moments appearing in credibility formulas. In a recent paper De Vylder has treated the problem in the case of multinormal conditional distributions under quite restrictive assumptions. He minimizes, within a certain restricted class of unbiased estimators, the variance (or the sum of variances if the estimand is a matrix) and next replaces all structural moments (up to fourth order) in the solution by estimates based on the data. This paper is an attempt to simplify the method and extend it so as to make it applicable in more general situations. By suitable choice of a (sufficient) set of statistics and a suitable parametrization, the powerful theory of estimation in linear models can be employed, which makes cumbersome minimization procedures superfluous. The theory is applied to the cases with binomial. Poisson, compound Poisson, and multinormal conditional distributions. Some simulation studies have been performed to assess the performance of the estimators.     

Highly accurate numerical solutions with repeated Richardson extrapolation for 2D laplace equation

A theoretical basis is presented for the repeated Richardson extrapolation (RRE) to reduce and estimate the discretization error of numerical solutions for heat conduction. An example application is described for the 2D Laplace equation using the finite difference method, a domain discretized with uniform grids, second-order accurate approximations, several variables of interest, Dirichlet boundary conditions, grids with up to 8,193 × 8,193 nodes, a multigrid method, single, double and quadruple precisions and up to twelve Richardson extrapolations. It was found that: (1) RRE significantly reduces the discretization error (for example, from 2.25E-07 to 3.19E-32 with nine extrapolations and a 1,025 × 1,025 grid, yielding an order of accuracy of 19.1); (2) the Richardson error estimator works for numerical results obtained with RRE; (3) a higher reduction of the discretization error with RRE is achieved by using higher calculation precision, a larger number of extrapolations, a larger number of grids and correct error orders; and (4) to obtain a given value error, much less CPU time and RAM memory are required for the solution with RRE than without it.     

Optimal recovery of interpolation operators in Hardy spaces

We continue studies begun by C.A. Micchelli and T.J. Rivlin on optimal recovery in H^p spaces. The feature operators are various interpolation operators drawn from the theory of Walsh equiconvergence, as are the information sets. The theory is of interest in that it identifies linear algorithms which might not otherwise be isolated for study or used as approximations of the feature operators. In some cases, we can identify the optimal algorithm although we cannot explicitly determine the exact order of the approximation that it achieves. For Charles Micchelli on his sixtieth birthday, with appreciation Mathematics subject classifications (2000) 41A05, 30B30. A. Sharma: Deceased.     

The Lawson-Hanson algorithm with deviation maximization: Finite convergence and sparse recovery

The Lawson-Hanson with Deviation Maximization (LHDM) method is a block algorithm for the solution of NonNegative Least Squares (NNLS) problems. In this work we devise an improved version of LHDM and we show that it terminates in a finite number of steps, unlike the previous version, originally developed for a special class of matrices. Moreover, we are concerned with finding sparse solutions of underdetermined linear systems by means of NNLS. An extensive campaign of experiments is performed in order to evaluate the performance gain with respect to the standard Lawson-Hanson algorithm. We also show the ability of LHDM to retrieve sparse solutions, comparing it against several ${\ell }_1$-minimization solvers in terms of solution quality and time-to-solution on a large set of dense instances.     

On equivalence of moduli of smoothness of polynomials in ,

It is well known that for functions , 1p∞. For general functions fL_p, it does not hold for 0<p<1, and its inverse is not true for any p in general. It has been shown in the literature, however, that for certain classes of functions the inverse is true, and the terms in the inequalities are all equivalent. Recently, Zhou and Zhou proved the equivalence for polynomials with p=∞. Using a technique by Ditzian, Hristov and Ivanov, we give a simpler proof to their result and extend it to the L_p space for 0<p∞. We then show its analogues for the Ditzian–Totik modulus of smoothness and the weighted Ditzian–Totik modulus of smoothness for polynomials with .     

Optimal recovery on the classes of functions with bounded mixed derivative

Temlyakov considered the optimal recovery on the classes of functions with bounded mixed derivative in the Lp metrics and gave the upper estimates of the optimal recovery errors. In this paper, we determine the asymptotic orders of the optimal recovery in Sobolev spaces by standard information, i.e., function values, and give the nearly optimal algorithms which attain the asymptotic orders of the optimal recovery.