Complete Chapter One

ITERATIVE TOEPLITZ SYSTEM USING THE CONJUGATE GRADIENT METHOD WITH THE SUPER OPTIMAL PRECONDITIONERS.

BY

THE DEPARTMENT OF MATHEMATICS

TABLE OF CONTENTS

Title page – – – – – – – – – –

Certification – – – – – – – – –

Dedication – – – – – – – – – –

Acknowledgement – – – – – – – –

Table of contents – – – – – – – –

Abstract – – – – – – – – – –

CHAPTER ONE

1.0 Teoplitz system of equation – – – – – –

1.1 Introduction – – – – – – – –

1.2 Basic symbols – – – – – – – –

CHAPTER TWO

2.0 The conjugate Gradient method – – – – –

2.1 Introduction – – – – – – – –

2.2 Thinking with eigenvectors and eigenvalues – – –

2.2.1 Eigen do it if I try – – – – – – –

2.2.2 Jacobi iteration – – – – – – – –

2.2.3 A concrete Example – – – – – – –

2.3 Convergence Analysis of steepest descent – – –

2.3.1 Instant Result – – – – – – – –

2.3.2 General Convergence – – – – – – –

2.4 The method of conjugate directions – – – –

2.4.1 Conjugacy – – – – – – – – –

2.4.2 Gram – Schmidt conjugation – – – – –

2.4.3 Optimality of the error term – – – – – –

2.5 The Nonlinear conjugate gradient method – – –

2.5.1 Outline of the nonlinear conjugate method – – –

2.5.2 General line search – – – – – – –

2.5.3 Preconditioning – – – – – – – –

CHAPTER THREE

3.0 The spectra of super-optimal circulant preconditioned of

toepritz systems – – – – – – – —

3.1 Introduction – – – – – – – –

3.2 Properties of the circulant operator – – – –

3.3 spectra of the preconditioned system – – – –

3.4 Contraction of the super-optimal circuiting – – –

CHAPTER FOUR

4.0 Numerical Experiment – – – – – –

4.1 Conclusion – – – – – – – –

References – – – – – – – – –

ABSTRACT

The solution of Hermitian positive definite Toeplitz system An U=b by the preconditioned conjugate gradient method. The preconditioner, called the super optimal preconditioner, is the circutant matrix in that minimizes ￼ over all circulant matrices Cn

The convergence rate if known to be governed by the distribution of the eigenvalues ￼for n-by-n Toeplitz matrix an with entries being Fourier co-efficient of a positive function in the wiener class, we find the asymptotic behavior of the eigenvalue of the preconditioned matrix ￼ as n increase and prove that they are clustered around one.

CHAPTER ONE

TOEPLITZ SYSTEMS OF EQUATIONS

INTRODUCTION

The toeplitz matrix is of the following form

￼

i.e tij = ti-j and Tn is constant along it diagonals. The name Toeplitz is in memorial of otto Toeplitiz’s. Toeplitiz’s early work [78] in 1911 on bilinear form related to Laurent series. We are interested in solving the Toeplitz system

￼

Where b is known vector and a u is an unknown vector Toeplitz system arise in a variety of application in different fields of mathematics, scientific computing and engineering statistics.

These applications have motivated mathematicians, scientists, and engineers to develop specifically fast algorithms for solving Toeplitz system. Most of the early works on Toeplitz solvers were focused on direct methods. A straight forward application of the Gaussian elimination method will result in an algorithm of 0(n3) complexity. However, since Toeplitix matrices are determined by only 2n-1 entries rather than n2 entries, if is expected that the solution of Toeplitiz systems can be obtained in less than 0(n3). Levinson’s algorithm [62] proposed in 1946 is the first algorithm which reduces the complexity to 0(n2) operations. These algorithms require the invertibility. ￼ principle submatrix of Tn.

Around 1980, fast direct Toeplitz solvers of complexity 0 (n log2n) were developed system. These algorithms require the invertibility of the [n/2]-by-[n/2] principal submatrix of Tn.

The stability properties of these direct methods for symmetric positive definitive Toeplitz system are discussed in Bunch (15). It was noted that if Tn has a singular or ill conditioned principal submatrix then a breakdown (or near breakdown) can occur in these algorithm. Such breakdown will case numerical instabilities in subsequent step and result in inaccurate solutions.

T. Chan and Hanses in 1992 derived the look- a head Levinson algorithm [34). The basic idea of the algorithm is to relax the inverse triangular decomposition slightly and to compute an inverse block factorization of the Toeplitz matrices with a block diagonal matrix instead of a scalar diagonal matrix.

Strang [74] and Olkin [67] in 1986 proposed independently the use of the preconditioned conjugate gradient (PCG) method with circulant matrices as preconditioners to solve symmetric positive definite Toeplitz system. One of the main results of this iterative solver is that the complexity of solving a large class of Toeplitz system Tn u=b is only 0(n long n) operations of the direct method. The purpose of this project is to present the super optimal preconditioners and the conjugate gradient algorithm, to make use and the analysis of its rate of convergence; to design and efficiently use a preconditioner to speed up the iterative process; and to present numerical experiment based on a ill-conditioned Toeplitz system.

Basic symbols

Let R denote the set of real number and c the set of complex numbers and let ￼ Let R denote the set of a real of vector and C^ the set of complex n-vectors vectors will always be column vectors.

Let Bnαn denote the linear vector space of n-by-n real matrices and Bnxn the lineal vector space of n-by-n complex matrices.

The symbol AT denotes the transpose of a matric A, and A* denote the Cojugate transpose of A.

Let rank (A) denote the rank of a matric A.

Let δ Max (A) denote the largest singular values of A.

Let λ Min (A) and λMax (A) denote the smallest and largest eigenvalues of A respectively.

Let (2π x 2 π denote the space of all 2 π- periodic (in each direction continuous real function ￼.

To get the Full and Complete Project material, Contact Solomon on 09024640145 or send an email to mzresearchproject@gmail.com. Complete Project Material costs N3,000 naira only.