On Meinardus' examples for the conjugate gradient method

The conjugate gradient (CG) method is widely used to solve a positive definite linear system of order . It is well known that the relative residual of the th approximate solution by CG (with the initial approximation ) is bounded above by

   with

where is 's spectral condition number. In 1963, Meinardus (Numer. Math., 5 (1963), pp. 14-23) gave an example to achieve this bound for but without saying anything about all other . This very example can be used to show that the bound is sharp for any given by constructing examples to attain the bound, but such examples depend on and for them the th residual is exactly zero. Therefore it would be interesting to know if there is any example on which the CG relative residuals are comparable to the bound for all . There are two contributions in this paper:

1. A closed formula for the CG residuals for all on Meinardus' example is obtained, and in particular it implies that the bound is always within a factor of of the actual residuals;
2. A complete characterization of extreme positive linear systems for which the th CG residual achieves the bound is also presented.

     

The convergence of conjugate gradient method with nonmonotone line search

The conjugate gradient method is a useful and powerful approach for solving large-scale minimization problems. Liu and Storey developed a conjugate gradient method, which has good numerical performance but no global convergence under traditional line searches such as Armijo line search, Wolfe line search, and Goldstein line search. In this paper we propose a new nonmonotone line search for Liu-Storey conjugate gradient method (LS in short). The new nonmonotone line search can guarantee the global convergence of LS method and has a good numerical performance. By estimating the Lipschitz constant of the derivative of objective functions in the new nonmonotone line search, we can find an adequate step size and substantially decrease the number of functional evaluations at each iteration. Numerical results show that the new approach is effective in practical computation.     

New results on the convergence of the conjugate gradient method

This paper is concerned with proving theoretical results related to the convergence of the conjugate gradient (CG) method for solving positive definite symmetric linear systems. Considering the inverse of the projection of the inverse of the matrix, new relations for ratios of the A‐norm of the error and the norm of the residual are provided, starting from some earlier results of Sadok (Numer. Algorithms 2005; 40 :201–216). The proofs of our results rely on the well‐known correspondence between the CG method and the Lanczos algorithm. Copyright © 2008 John Wiley & Sons, Ltd.     

On sequences of Hurwitz polynomials related to orthogonal polynomials

ABSTRACT

In this contribution, we explore the well-known connection between Hurwitz and orthogonal polynomials. Namely, given a Hurwitz polynomial, it is shown that it can be decomposed into two parts: a polynomial that is orthogonal with respect to some positive measure supported in the positive real axis and its corresponding second-kind polynomial. Conversely, given a sequence of orthogonal polynomials with respect to a positive measure supported in the positive real axis, a sequence of Hurwitz polynomials can be constructed. Based on that connection, we construct sequences of Hurwitz polynomials that satisfy a recurrence relation, in a similar way as the orthogonal polynomials do. Even more, we present a way to construct families of Hurwitz polynomials using two sequences of parameters and a recurrence relation that constitutes an analogue of Favard's theorem in the theory of orthogonal polynomials.     

On the linear functionals associated to linearly related sequences of orthogonal polynomials

An inverse problem is solved, by stating that the regular linear functionals u and v associated to linearly related sequences of monic orthogonal polynomials n(Pn) and n(Qn), respectively, in the sense

     

一个充分下降的有效共轭梯度法

对于大规模无约束优化问题,本文提出了一个充分下降的共轭梯度法公式,并建立相应的算法.该算法在不依赖于任何线搜索条件下,每步迭代都能产生一个充分下降方向.若采用标准Wolfe非精确线搜索求步长,则在常规假设条件下可获得算法良好的全局收敛性最后,对算法进行大规模数值试验,并采用Dolan和More的性能图对试验效果进行刻画,结果表明该算法是有效的.     

On a set of orthogonal polynomials associated with a quantized physical model

In this paper we investigate a set of orthogonal polynomials. We relate the polynomials to the Biconfluent Heun equation and present an explicit expression for the polynomials in terms of the classical Hermite polynomials. The orthogonality with a varying measure and the recurrence relation are also presented.     

A modified PRP conjugate gradient method

This paper gives a modified PRP method which possesses the global convergence of nonconvex function and the R-linear convergence rate of uniformly convex function. Furthermore, the presented method has sufficiently descent property and characteristic of automatically being in a trust region without carrying out any line search technique. Numerical results indicate that the new method is interesting for the given test problems. This work is supported by Guangxi University SF grands X061041 and China NSF grands 10761001.     

A proof of a conjecture about a symmetric system of orthogonal polynomials

ABSTRACT

The purpose of this note is to give an affirmative answer to a conjecture appearing in Berg [Open problems. Integral Transforms Spec Funct. 2015;26(2):90–95].     

A globally convergent version of the Polak-Ribière conjugate gradient method

In this paper we propose a new line search algorithm that ensures global convergence of the Polak-Ribière conjugate gradient method for the unconstrained minimization of nonconvex differentiable functions. In particular, we show that with this line search every limit point produced by the Polak-Ribière iteration is a stationary point of the objective function. Moreover, we define adaptive rules for the choice of the parameters in a way that the first stationary point along a search direction can be eventually accepted when the algorithm is converging to a minimum point with positive definite Hessian matrix. Under strong convexity assumptions, the known global convergence results can be reobtained as a special case. From a computational point of view, we may expect that an algorithm incorporating the step-size acceptance rules proposed here will retain the same good features of the Polak-Ribière method, while avoiding pathological situations. This research was supported by Agenzia Spaziale Italiana, Rome, Italy.     

On linearly related sequences of derivatives of orthogonal polynomials

We discuss an inverse problem in the theory of (standard) orthogonal polynomials involving two orthogonal polynomial families (P_n)_n and (Q_n)_n whose derivatives of higher orders m and k (resp.) are connected by a linear algebraic structure relation such as

for all n=0,1,2,…, where M and N are fixed nonnegative integer numbers, and r_i,n and s_i,n are given complex parameters satisfying some natural conditions. Let u and v be the moment regular functionals associated with (P_n)_n and (Q_n)_n (resp.). Assuming 0mk, we prove the existence of four polynomials Φ_M+m+i and Ψ_N+k+i, of degrees M+m+i and N+k+i (resp.), such that

the (k−m)th-derivative, as well as the left-product of a functional by a polynomial, being defined in the usual sense of the theory of distributions. If k=m, then u and v are connected by a rational modification. If k=m+1, then both u and v are semiclassical linear functionals, which are also connected by a rational modification. When k>m, the Stieltjes transform associated with u satisfies a non-homogeneous linear ordinary differential equation of order k−m with polynomial coefficients.     

Jacobi-Sobolev-type orthogonal polynomials: Second-order differential equation and zeros

We obtain an explicit expression for the Sobolev-type orthogonal polynomials {Q_n} associated with the inner product

, where p(x) = (1 − x)(1 + x)^β is the Jacobi weight function, ,β> − 1, A₁,B₁,A₂,B₂0 and p, q P, the linear space of polynomials with real coefficients. The hypergeometric representation (₆F₅) and the second-order linear differential equation that such polynomials satisfy are also obtained. The asymptotic behaviour of such polynomials in [−1, 1] is studied. Furthermore, we obtain some estimates for the largest zero of Q_n(x). Such a zero is located outside the interval [−1, 1]. We deduce his dependence of the masses. Finally, the WKB analysis for the distribution of zeros is presented.     

A conjugate gradient method with descent direction for unconstrained optimization

A modified conjugate gradient method is presented for solving unconstrained optimization problems, which possesses the following properties: (i) The sufficient descent property is satisfied without any line search; (ii) The search direction will be in a trust region automatically; (iii) The Zoutendijk condition holds for the Wolfe–Powell line search technique; (iv) This method inherits an important property of the well-known Polak–Ribière–Polyak (PRP) method: the tendency to turn towards the steepest descent direction if a small step is generated away from the solution, preventing a sequence of tiny steps from happening. The global convergence and the linearly convergent rate of the given method are established. Numerical results show that this method is interesting.     

On oscillatory properties of the Bernstein-Szegö orthogonal polynomials

The paper considers the mutual relationship of oscillations of the Bernstein-Szegö orthogonal polynomials of different kinds in the boundaries that are determined by the weight functions with indication of Chebyshev's alternances.     

Asymptotics for polynomials orthogonal over the unit disk with respect to a positive polynomial weight

We derive asymptotics for polynomials orthogonal over the complex unit disk with respect to a weight of the form ²|h(z)|, with h(z) a polynomial without zeros in |z|<1. The behavior of the polynomials is established at every point of the complex plane. The proofs are based on adapting to the unit disk a technique of J. Szabados for the asymptotic analysis of polynomials orthogonal over the unit circle with respect to the same type of weight.     

Orthogonal polynomials and analytic functions associated to positive definite matrices

For a positive definite infinite matrix A, we study the relationship between its associated sequence of orthonormal polynomials and the asymptotic behaviour of the smallest eigenvalue of its truncation An of size n×n. For the particular case of A being a Hankel or a Hankel block matrix, our results lead to a characterization of positive measures with finite index of determinacy and of completely indeterminate matrix moment problems, respectively.     

Splitting-based conjugate gradient method for a multi-dimensional linear inverse heat conduction problem

In this paper we consider a multi-dimensional inverse heat conduction problem with time-dependent coefficients in a box, which is well-known to be severely ill-posed, by a variational method. The gradient of the functional to be minimized is obtained by the aid of an adjoint problem, and the conjugate gradient method with a stopping rule is then applied to this ill-posed optimization problem. To enhance the stability and the accuracy of the numerical solution to the problem, we apply this scheme to the discretized inverse problem rather than to the continuous one. The difficulties with large dimensions of discretized problems are overcome by a splitting method which only requires the solution of easy-to-solve one-dimensional problems. The numerical results provided by our method are very good and the techniques seem to be very promising.