共查询到20条相似文献,搜索用时 15 毫秒
1.
N. Mastronardi M. Van Barel R. Vandebril 《Numerical Linear Algebra with Applications》2008,15(4):327-337
Recent progress in signal processing and estimation has generated considerable interest in the problem of computing the smallest eigenvalue of a symmetric positive‐definite (SPD) Toeplitz matrix. An algorithm for computing upper and lower bounds to the smallest eigenvalue of a SPD Toeplitz matrix has been recently derived (Linear Algebra Appl. 2007; DOI: 10.1016/j.laa.2007.05.008 ). The algorithm relies on the computation of the R factor of the QR factorization of the Toeplitz matrix and the inverse of R. The simultaneous computation of R and R?1 is efficiently accomplished by the generalized Schur algorithm. In this paper, exploiting the properties of the latter algorithm, a numerical method to compute the smallest eigenvalue and the corresponding eigenvector of SPD Toeplitz matrices in an accurate way is proposed. Copyright © 2008 John Wiley & Sons, Ltd. 相似文献
2.
This note outlines an algorithm for solving the complex ‘matrix Procrustes problem’. This is a least‐squares approximation over the cone of positive semi‐definite Hermitian matrices, which has a number of applications in the areas of Optimization, Signal Processing and Control. The work generalizes the method of Allwright (SIAM J. Control Optim. 1988; 26 (3):537–556), who obtained a numerical solution to the real‐valued version of the problem. It is shown that, subject to an appropriate rank assumption, the complex problem can be formulated in a real setting using a matrix‐dilation technique, for which the method of Allwright is applicable. However, this transformation results in an over‐parametrization of the problem and, therefore, convergence to the optimal solution is slow. Here, an alternative algorithm is developed for solving the complex problem, which exploits fully the special structure of the dilated matrix. The advantages of the modified algorithm are demonstrated via a numerical example. Copyright © 2007 John Wiley & Sons, Ltd. 相似文献
3.
Xiangjian Xu 《Applied mathematics and computation》2010,217(5):1944-1948
In this paper, we present a fast algorithm for solving Symmetric penta-diagonal systems. We give the feasibility and Stability analysis of the algorithm. Moreover, parallel computations can be implemented in the algorithm. The numerical examples verify the efficiency of the algorithm. 相似文献
4.
S.S. Nemani 《Applied mathematics and computation》2010,215(11):3830-1948
In this paper a fast algorithm for solving a large system with a symmetric Toeplitz penta-diagonal coefficient matrix is presented. This efficient method is based on the idea of a system perturbation followed by corrections and is competitive with standard methods. The error analysis is also given. 相似文献
5.
A parallel algorithm for solving Toeplitz linear systems 总被引:1,自引:0,他引:1
Numerical methods of solution are considered for systems which are Toeplitz and symmetric. In our case, the coefficient matrix is essentially tridiagonal and sparse. There are two distinct approaches to be considered each of which is efficient in its own way. Here we will combine the two approaches which will allow application of the cyclic reduction method to coefficient matrices of more general forms. The convergence of the approximations to the exact solution will also be examined. Solving linear systems by the adapted cyclic reduction method can be parallel processed. 相似文献
6.
In this paper, we propose a new mean value algorithm for the Toeplitz matrix completion based on the singular value thresholding (SVT) algorithm. The completion matrices generated by the new algorithm keep a feasible Toeplitz structure. Meanwhile, we prove the convergence of the new algorithm under some reasonal conditions. Finally, we show the new algorithm is much more effective than the ALM (augmented Lagrange multiplier) algorithm through numerical experiments and image inpainting. 相似文献
7.
§ 1 IntroductionLetRn×mdenotetherealn×mmatrixspace ,Rn×mr itssubsetwhoseelementshaverankr ,ORn×nthesetofalln×northogonalmatrices,SRn×n(SRn×n≥ ,SRn×n>)thesetofalln×nrealsymmetric (symmetricpositivesemidefinite ,positivedefinite)matrices.ThenotationA>0 (≥ 0 ,<0 ,≤ 0 )m… 相似文献
8.
Many problems in mathematics and applied science lead to the solution of linear systems having circulant coefficient matrices. This paper presents a new stable method for the exact solution of non-symmetric tridiagonal circulant linear systems of equations. The method presented in this paper is quite competitive with Gaussian elimination both in terms of arithmetic operations and storage requirements. It is also competitive with the modified double sweep method. This method can be applied to solve the near-circulant tridiagonal system. In addition, the method is modified to allow for parallel processing. 相似文献
9.
Xiao-Qing Jin 《Journal of Computational and Applied Mathematics》1996,70(2):225-230
We consider the solutions of block Toeplitz systems with Toeplitz blocks by the preconditioned conjugate gradient (PCG) method. Here the block Toeplitz matrices are generated by nonnegative functions f(x,y). We use band Toeplitz matrices as preconditioners. The generating functions g(x,y) of the preconditioners are trigonometric polynomials of fixed degree and are determined by minimizing (f − g)/f∞. We prove that the condition number of the preconditioned system is O(1). An a priori bound on the number of iterations for convergence is obtained. 相似文献
10.
A good preconditioner is extremely important in order for the conjugate gradients method to converge quickly. In the case of Toeplitz matrices, a number of recent studies were made to relate approximation of functions to good preconditioners. In this paper, we present a new result relating the quality of the Toeplitz preconditionerC for the Toeplitz matrixT to the Chebyshev norm (f– g)/f, wheref and g are the generating functions forT andC, respectively. In particular, the construction of band-Toeplitz preconditioners becomes a linear minimax approximation problem. The case whenf has zeros (but is nonnegative) is especially interesting and the corresponding approximation problem becomes constrained. We show how the Remez algorithm can be modified to handle the constraints. Numerical experiments confirming the theoretical results are presented. 相似文献
11.
12.
Fast algorithm for solving the Hankel/Toeplitz Structured Total Least Squares problem 总被引:4,自引:0,他引:4
The Structured Total Least Squares (STLS) problem is a natural extension of the Total Least Squares (TLS) problem when constraints
on the matrix structure need to be imposed. Similar to the ordinary TLS approach, the STLS approach can be used to determine
the parameter vector of a linear model, given some noisy measurements. In many signal processing applications, the imposition
of this matrix structure constraint is necessary for obtaining Maximum Likelihood (ML) estimates of the parameter vector.
In this paper we consider the Toeplitz (Hankel) STLS problem (i.e., an STLS problem in which the Toeplitz (Hankel) structure
needs to be preserved). A fast implementation of an algorithm for solving this frequently occurring STLS problem is proposed.
The increased efficiency is obtained by exploiting the low displacement rank of the involved matrices and the sparsity of
the associated generators.
The fast implementation is compared to two other implementations of algorithms for solving the Toeplitz (Hankel) STLS problem.
The comparison is carried out on a recently proposed speech compression scheme. The numerical results confirm the high efficiency
of the newly proposed fast implementation: the straightforward implementations have a complexity of O((m+n)3) and O(m3) whereas the proposed implementation has a complexity of O(mn+n2).
This revised version was published online in June 2006 with corrections to the Cover Date. 相似文献
13.
Raymond H. Chan Daniel Potts Gabriele Steidl 《Numerical Linear Algebra with Applications》2001,8(2):83-98
In this paper, we construct new ω‐circulant preconditioners for non‐Hermitian Toeplitz systems, where we allow the generating function of the sequence of Toeplitz matrices to have zeros on the unit circle. We prove that the eigenvalues of the preconditioned normal equation are clustered at 1 and that for (N, N)‐Toeplitz matrices with spectral condition number 𝒪(Nα) the corresponding PCG method requires at most 𝒪(N log2 N) arithmetical operations. If the generating function of the Toeplitz sequence is a rational function then we show that our preconditioned original equation has only a fixed number of eigenvalues which are not equal to 1 such that preconditioned GMRES needs only a constant number of iteration steps independent of the dimension of the problem. Numerical tests are presented with PCG applied to the normal equation, GMRES, CGS and BICGSTAB. In particular, we apply our preconditioners to compute the stationary probability distribution vector of Markovian queuing models with batch arrival. Copyright © 2001 John Wiley & Sons, Ltd. 相似文献
14.
Vejdi Ismailov Hasanov 《Linear and Multilinear Algebra》2018,66(9):1783-1798
15.
M. Van Barel Kh. D. Ikramov A. A. Chesnokov 《Computational Mathematics and Mathematical Physics》2008,48(12):2126-2139
A fast algorithm is proposed for solving symmetric Toeplitz systems. This algorithm continuously transforms the identity matrix into the inverse of a given Toeplitz matrix T. The memory requirements for the algorithm are O(n), and its complexity is O(log κ(T)nlogn), where (T) is the condition number of T. Numerical results are presented that confirm the efficiency of the proposed algorithm. 相似文献
16.
In this paper, the feasible type SQP method is improved. A new algorithm is proposed to solve nonlinear inequality constrained problem, in which a new modified method is presented to decrease the computational complexity. It is required to solve only one QP subproblem with only a subset of the constraints estimated as active per single iteration. Moreover, a direction is generated to avoid the Maratos effect by solving a system of linear equations. The theoretical analysis shows that the algorithm has global and superlinear convergence under some suitable conditions. In the end, numerical experiments are given to show that the method in this paper is effective.This work is supported by the National Natural Science Foundation (No. 10261001) and Guangxi Science Foundation (No. 0236001 and 0249003) of China.
Acknowledgement.We would like to thank one anonymous referee for his valuable comments and suggestions, which greatly improved the quality of this paper. 相似文献
17.
18.
A SQP Method for Inequality Constrained Optimization 总被引:1,自引:0,他引:1
Ju-liang ZHANG Xiang-sun ZHANGInstitute of Applied Mathematics Academy of Mathematics System Sciences Chinese Academy of Sciences Beijing China 《应用数学学报(英文版)》2002,18(1):77-84
Abstract In this paper, a new SQP method for inequality constrained optimization is proposed and the globalconvergence is obtained under very mild conditions. 相似文献
19.
The Lanczos method with shift‐invert technique is exploited to approximate the symmetric positive semidefinite Toeplitz matrix exponential. The complexity is lowered by the Gohberg–Semencul formula and the fast Fourier transform. Application to the numerical solution of an integral equation is studied. Numerical experiments are carried out to demonstrate the effectiveness of the proposed method. Copyright © 2010 John Wiley & Sons, Ltd. 相似文献