A note on the convergence of the two-grid method for Toeplitz systems

Hai Wei SUN*, R. H. CHAN, Qian Shun CHANG

*Corresponding author for this work

Research output: Journal PublicationsJournal Article (refereed)peer-review

15 Citations (Scopus)


In this paper, we consider solutions of Toeplitz systems Au = b where the Toeplitz matrices A are generated by nonnegative functions with zeros. Since the matrices A are ill-conditioned, the convergence factor of classical iterative methods, such as the Richardson method, will approach 1 as the size n of the matrices becomes large. In [1,2], convergence of the two-grid method with Richardson method as smoother was proved for band τ matrices and it was conjectured that this convergence result can be carried to Toeplitz systems. In this paper, we show that the two-grid method with Richardson smoother indeed converges for Toeplitz systems that are generated by functions with zeros, provided that the order of the zeros are less than or equal to 2. However, we illustrate by examples that the convergence results of the two-grid method cannot be readily extended to multigrid method for n that are not of the form 2 - 1.

Original languageEnglish
Pages (from-to)11-18
Number of pages8
JournalComputers and Mathematics with Applications
Issue number1
Publication statusPublished - Jul 1997
Externally publishedYes


  • Damped-Jacobi method
  • Multigrid method
  • Richardson method
  • Toeplitz matrices


Dive into the research topics of 'A note on the convergence of the two-grid method for Toeplitz systems'. Together they form a unique fingerprint.

Cite this