Error bounds for multistep methods revisited

For linear multistep methods with constant stepsize we consider error bounds in terms of weightedL ₂-norms ofh ^px^(p) rather than ofh ^px^(p+1). The bounds apply to stiff systemsx'=Ax+f(t,x) where the spectrum ofA lies in a sector andf is of moderate size.     

The Lanczos phenomenon—An interpretation based upon conjugate gradient optimization

The equivalence in exact arithmetic of the Lanczos tridiagonalization procedure and the conjugate gradient optimization procedure for solving Ax = b, where A is a real symmetric, positive definite matrix, is well known. We demonstrate that a relaxed equivalence is valid in the presence of errors. Specifically we demonstrate that local ε-orthonormality of the Lanczos vectors guarantees local ε-A-conjugacy of the direction vectors in the associated conjugate gradient procedure. Moreover we demonstrate that all the conjugate gradient relationships are satisfied approximately. Therefore, any statements valid for the conjugate gradient optimization procedure, which we show converges under very weak conditions, apply directly to the Lanczos procedure. We then use this equivalence to obtain an explanation of the Lanczos phenomenon: the empirically observed “convergence” of Lanczos eigenvalue procedures despite total loss of the global orthogonality of the Lanczos vectors.     

A computable error bound for matrix functionals

Many problems in applied mathematics require the evaluation of matrix functionals of the form F(A):=u^Tf(A)u, where A is a large symmetric matrix and u is a vector. Golub and collaborators have described how approximations of such functionals can be computed inexpensively by using the Lanczos algorithm. The present note shows that error bounds for these approximations can be computed essentially for free when bounds for derivatives of f on an interval containing the spectrum of A are available.     

Three positive solutions to a discrete focal boundary value problem

We are concerned with the discrete focal boundary value problem Δ³x(t − k) = f(x(t)), x(a) = Δx(t₂) = Δ²x(b + 1) = 0. Under various assumptions on f and the integers a, t₂, and b we prove the existence of three positive solutions of this boundary value problem. To prove our results we use fixed point theorems concerning cones in a Banach space.     

An efficient Newton's method for optimization under equality constraints

An efficient procedure for optimizing a nonlinear objective functional ?(x) under linear and/or nonlinear equality constraints is given. The linearly constrained, quadratic ?(x) case is shown to have a solution given by the explicit formula x = x_p - N(N′AN)^-1N′(Ax_p + b/2), where ?(x) = a+b′x+x′Ax(x?Rⁿ) is convex, and both x_p?R_n and N [an n×(n-r) matrix]; can be obtained simultaneously from the constraint set, Kx=c (K of rank r<n), by a single Gaussian elimination. The nonlinearly constrained, arbitrary ?(x) case is treated by an interative scheme in which the above formula is used to “project” onto approximate solutions satisfying linear approximations of the constraints. This method does not require the initial guess or the iterated values to be in the feasible region. The resulting algorithm does appear to be efficient.     

An Improved Interval Linearization for Solving Nonlinear Problems

Let f(x) denote a system of n nonlinear functions in m variables, m≥n. Recently, a linearization of f(x) in a box x has been suggested in the form L(x)=Ax+b where A is a real n×m matrix and b is an interval n-dimensional vector. Here, an improved linearization L(x,y)=Ax+By+b, x∈x, y∈y is proposed where y is a p-dimensional vector belonging to the interval vector y while A and B are real matrices of appropriate dimensions and b is a real vector. The new linearization can be employed in solving various nonlinear problems: global solution of nonlinear systems, bounding the solution set of underdetermined systems of equations or systems of equalities and inequalities, global optimization. Numerical examples illustrating the superiority of L(x,y)=Ax+By+b over L(x)=Ax+b have been solved for the case where the problem is the global solution of a system of nonlinear equations (n=m).     

Preconditioned conjugate gradient method for generalized least squares problems

A variant of the preconditioned conjugate gradient method to solve generalized least squares problems is presented. If the problem is min (Ax − b)^TW⁻¹(Ax − b) with A ∈ R^m×n and W ∈ R^m×m symmetric and positive definite, the method needs only a preconditioner A₁ ∈ R^n×n, but not the inverse of matrix W or of any of its submatrices. Freund's comparison result for regular least squares problems is extended to generalized least squares problems. An error bound is also given.     

On a particular quadratic network problem

Let c(x), d(x) and h(x) be linear functions defined over a convex polyhedron X = {x | Ax = r and 0 ⩽ x ⩽ u }, where A is the node-edge incidence matrix of a given network. Let f(x) = c(x)d(x) + h(x) be a (particular) quadratic function which we intend to minimize over X. In this paper we use the theory of multiobjective programming do develop algorithms for the semidefinite positive case (f(x) = ϱ[d(x)]² + h(x) and ϱ is a strictly postive real constant) and the semidefinite negative case (f(x) = ϱ[d(x)]² + h (x) and ϱ is a strictly negative real constant). A special indefinite case (h(x) is constant over X) is also studied.In the proposed algorithms, basic solutions are used in all the interactions with possible exception for the last one. Moreover only the concepts of the simplex method are used; consequently these algorithms can be used even when A is not the node-edge incidence matrix of a network. However they are particularly attractive for the network case. In fact, network basic solutions are efficiently manipulated when appropriated data structures are used in the computational implementation of an algorithm.     

A note on Stewart's theorem for definite matrix pairs

Let A and B be n×n Hermitian matrices. The matrix pair (A, B) is called definite pair and the corresponding eigenvalue problem βAx = αBx is definite if c(A, B) ≡ inf_{6x6= 1}{|^H(A+iB)x|} > 0. In this note we develop a uniform upper bound for differences of corresponding eigenvalues of two definite pairs and so improve a result which is obtained by G.W. Stewart [2]. Moreover, we prove that this upper bound is a projective metric in the set of n × n definite pairs.     

Nested matrices and the existence of least majorized elements

We characterize the matrices A for which X(b)={x∣x∈Rⁿ, x?0, Ax?b, σⁿ_i=1x_i=1} contains a least majorized element for all vectors b satisfying X(b)≠?.     

On boundary value problems for systems of nonlinear generalized ordinary differential equations

A general theorem (principle of a priori boundedness) on solvability of the boundary value problem dx = dA(t) · f(t, x), h(x) = 0 is established, where f: [a, b]×R ⁿ → R ⁿ is a vector-function belonging to the Carathéodory class corresponding to the matrix-function A: [a, b] → R ^n×n with bounded total variation components, and h: BV_s([a, b],R ⁿ ) → R ⁿ is a continuous operator. Basing on the mentioned principle of a priori boundedness, effective criteria are obtained for the solvability of the system under the condition x(t₁(x)) = B(x) · x(t ₂(x))+c ₀, where t _i: BV_s([a, b],R ⁿ ) → [a, b] (i = 1, 2) and B: BV_s([a, b], R ⁿ ) → R ⁿ are continuous operators, and c ₀ ∈ R ⁿ .     

A noncommutative analogue of |D(Xk|=|kXk−1|

The paper concerns alternating powers of a Hilbert space. Let ∧^k be defined by ∧^k(A)(x₁∧?∧x_k)=Ax₁∧?∧Ax_k. It is proved that the norm of the linear map D∧^k(A) depends only upon |A| and is assumed at the identity.     

Pertubation bounds for the definite generalized eigenvalue problem

Let A and B be Hermitian matrices, and let c(A, B) = inf{|x^H(A + iB)x|:6 = 1}. The eigenvalue problem Ax = λBx is called definite if c(A, B)>0. It is shown that a definite problem has a complete system of eigenvectors and that its eigenvalues are real. Under pertubations of A and B, the eigenvalues behave like the eigenvalues of a Hermitian matrix in the sense that there is a 1-1 pairing of the eigenvalues with the perturbed eigenvalues and a uniform bound for their differences (in this case in the chordal metric). Pertubation bounds are also developed for eigenvectors and eigenspaces.     

A companion matrix analogue for orthogonal polynomials

Given a set of orthogonal polynomials {P_i(x)}, it is shown that associated with a polynomial a(x)=∑a_ip_i(x) there is a matrix A which possesses several of the properties of the usual companion form matrix C. An alternative and possibly preferable form A' is also suggested. A similarity transformation between A [orA'] and C is given. If b(x) is another polynomial then the matrix b(A) [or b(A')] has properties like those of b(C), relating to the greatest common divisor of a(x) and b(x).     

A resolution method for multiobjective problems

A resolution method for multiobjective problems, based on a maximin criterion, is developed. Given the multiobjective problem Max_{Ax=b,x?0}{c_ix; i = 1,2,…,k}, we suppose that the decisor can construct, for each i, a function h_i:$\text{R}$ → $\text{R}$ (or h_i:$\text{R}$ⁿ→-$\text{R}$), such that h_i(c_i,x) is his satisfaction degree produced by the value c_ix, and we substitute the original problem by Max_{Ax=b,x?0～min_i{h_i(c_ix)}. We analize its resolution and basic properties.     

A Polynomial Time Algorithm for the Resource Allocation Problem with a Convex Objective Function

Consider the resource allocation problem:minimize ∑ⁿ_i=1 f_i(x_i) subject to ∑ⁿ_i=1 x_i = N and x_i's being nonnegative integers, where each f_i is a convex function. The well-known algorithm based on the incremental method requires O(N log n + n) time to solve this problem. We propose here a new algorithm based on the Lagrange multiplier method, requiring O[n²(log N)²] time. The latter is faster if N is much larger than n. Such a situation occurs, for example, when the optimal sample size problem related to monitoring the urban air pollution is treated.     

A new fourth-order cubic spline method for second-order nonlinear two-point boundary-value problems

Bickley [5] had suggested the use of cubic splines for the solution of general linear two-point boundary-value problems. It is well known since then that this method gives only order h² uniformly convergent approximations. But cubic spline interpolation itself is a fourth-order process. We present a new fourth-order cubic spline method for second-order nonlinear two-point boundary-value problems: y″ = f(x, y, y′), a < x < b, α₀y(a) − α₀y′(a) = A, β₀y(b) + β₁y′(b) = B. We generate the solution at the nodal points by a fourth-order method and then use ‘conditions of continuity’ to obtain smoothed approximations for the second derivatives of the solution needed for the construction of the cubic spline solution. We show that our method provides order h⁴ uniformly convergent approximations over [a, b]. The fourth order of the presented method is demonstrated computationally by two examples.     

Gradient algorithms for quadratic optimization with fast convergence rates

We propose a family of gradient algorithms for minimizing a quadratic function f(x)=(Ax,x)/2−(x,y) in ℝ ^d or a Hilbert space, with simple rules for choosing the step-size at each iteration. We show that when the step-sizes are generated by a dynamical system with ergodic distribution having the arcsine density on a subinterval of the spectrum of A, the asymptotic rate of convergence of the algorithm can approach the (tight) bound on the rate of convergence of a conjugate gradient algorithm stopped before d iterations, with d≤∞ the space dimension.     

Schauder estimates for a degenerate second order elliptic operator on a cube

In the present article we are concerned with a class of degenerate second order differential operators LA,b defined on the cube d[0,1], with d?1. Under suitable assumptions on the coefficients A and b (among them the assumption of their Hölder regularity) we show that the operator LA,b defined on C²(d[0,1]) is closable and its closure is m-dissipative. In particular, its closure is the generator of a C₀-semigroup of contractions on C(d[0,1]) and C²(d[0,1]) is a core for it. The proof of such result is obtained by studying the solvability in Hölder spaces of functions of the elliptic problem λu(x)−LA,bu(x)=f(x), x∈d[0,1], for a sufficiently large class of functions f.     

Numerical analysis and orthogonal polynomials

Two topics of general interest are investigated. First an iterative improvement algorithm is given to reduce the accumulation of truncation errors which may occur when recursion formulae are utilized. Then some properties of orthogonal polynomials are derived that allow a successful construction of Gaussian type integration formulae employing the improvement algorithm. As special examples integrals of the ∫^b_aexp(-x²)f(x)dx and ∫^b_aexp(-|x|)f(x)dx are considered, where a and/o r b may be infinite.