next up previous
Next: Fast Cholesky factorization Up: Classical Foundations of Algorithms Previous: Introduction

Schur's Algorithm and the Carathéodory --Toeplitz Theorem

The original mathematical importance of positive definite Toeplitz matrices is in the solution of the classical Carathéodory coefficient problem, proved independently by Toeplitz and Carathéodory in 1911. An analytic mapping of the unit disk |z|<1 into the closed right half-plane is said to be a Carathéodory function, or a function in the class C.

In 1917, Schur gave a constructive proof of the Carathéodory-Toeplitz theorem via his study of analytic functions bounded in the unit disk [35]. In particular, Schur gave a procedure for determining when a given function maps |z|<1 analytically into . Such a function is now called a Schur function, or a function in the class S.

Schur showed that the function class S can be parameterized by certain sequences of complex numbers , known as Schur parameters. They determine a continued fraction representation of the given Schur function . Schur gave the following procedure for constructing these parameters.

The initial function is a Schur function if and only if one of the following holds:

(1) for ;
(2) for , , and .

If condition (2) holds, then is a rational Schur function.

It is natural to view the Schur functions generated by the algorithm as ratios of formal power series,

In terms of these power series, we can restate Schur's algorithm as

 

If we partially normalize the initial ratio so that , then the constant terms of the denominators are related by

so that is a Schur function if and only if is a nonnegative, nonincreasing sequence that is infinite, or finite and terminating with .

Schur gave explicit determinantal formulas for the numerators and denominators in (2.1), and using the the correspondence

between the algebra of formal power series and the algebra of singly infinite triangular Toeplitz matrices, he concluded that

where and are the leading principal submatrices of and . This gives the following characterization of Schur functions.

 

The Carathéodory-Toeplitz theorem follows directly from this result. In particular, the power series of Theorem 1 is in the class C if and only if

is in the class S. By Theorem 2.2, this is true if and only if the matrix

is nonnegative definite for every n.



next up previous
Next: Fast Cholesky factorization Up: Classical Foundations of Algorithms Previous: Introduction



Greg Ammar
Thu Sep 18 20:40:30 CDT 1997