Monday, August 23, 2010

Routh array, Routh Criterion and how to calculate the Routh Hurwitz array

The post is available also in PDF format here[mirror].

Trying to find a reasonable explanation of how to calculate Routh array, I found one here (while in book are usually given cryptic and tricky ways, even in Goodwin-Graebe).

Routh criterion

The Routh-Hurwitz stability criterion is a necessary (and frequently sufficient) method to establish the stability of a single-input, single-output (SISO), linear time invariant (LTI) control system.

One of the most popular algorithms to determine whether or not a polynomial is strictly Hurwitz, is Routh's algorithm. Consider a polynomial and its associated Routh array (see below). Then the number of roots with real part greater than zero is equal to the number of sign changes in the first column of the array.

Routh array

A tabular method of Routh criterion can be used to determine the stability when the roots of a higher order characteristic polynomial are difficult to obtain. Consider the polynomial

. The first two rows (two highest ones) of the Routh's array are formed using coefficients

in the increasing order:

Row	Power	First column	Second column	Third column
n				...
n-1	$s^{n-1}$			...

If there are no more coefficients then just add zeros in the table.

Then for each row after third row we need to calculate , , and so on. Now starting from row 3, each row contains the b's, c's, d's and so on as follows:

Row	Power	First column	Second column	Third column
n				...
n-1	$s^{n-1}$			...
n-2	$s^{n-2}$			...
n-3	$s^{n-3}$			...
n-4	$s^{n-4}$			...
&vellip#vdots;
0	$s^{0}$		0	0

Now we need to calculate the coefficients and so on. That can be done using the following determinants formulas:

and so on until . Remember to add zeros in the table when no more coefficients left - it will alleviate the calculations and make them more straightforward. The principle is the following: when one calculates , the first column in the determinant is always [column_1; row_1, row_2]"/> of the Routh table, e.g. .

Second column in the determinant contains , e.g. for calculations of .

The following illustration shows the principle:

Here dark-green rectangle depicts the first column of the determinant in the calculations of

, dark-green circle - denominator in the equation for

. Bright-green rectangle depicts the second column in the determinant for calculations of

. In the same fashion, dark-blue rectangle depicts the first column of the determinant in the calculations of

, dark-blue circle - denominator in the equation for

. Bright-blue rectangle depicts the second column in the determinant for calculations of

, and so on.

Example of calculation of Routh array

Consider the polynomial

. As above, the first two rows of the Routh's array are formed using coefficients

in the increasing order:

Row	Power	First column	Second column	Third column
n		1	3	1
n-1	$s^{3}$	1	2	0 ...

Now we need to calculate using mentioned above equations.

Thus our table will look like:

Row	Power	First column	Second column	Third column
n		1	3	1
n-1	$s^{3}$	1	2	0 ...
n-2	$s^{2}$	1	1	0 ...
n-3	$s^{1}$	1	0	0 ...
n-4	$s^{0}$	1	0	0 ...

From the array we note that there are no sign changes in the first column. According to Routh's criterion, this means that is a strictly Hurwitz polynomial.

Tuesday, April 20, 2010

Linear Algebra: small survey of books

It is sometimes useful to repeat some fundamentals of mathematics, especially when it has not been used for a long time. For the study of coherence estimation in complex-valued data I had to review and refresh my Linear Algebra skills. For that I needed to study several topics and the result of it will be this small survey of books, handbooks and articles that helped me in such challenging study.

General-purpose books

First of all, one need a good general-purpose books for initial refresh of Linear Algebra. I think that Gilbert Strang's book [1] is among the best for systematic study. Although sometimes (especially in the appendices) book became too verbose (lots of exotic examples) or too brief (the reader must guess of how to actually calculated many types of decompositions), Strang's book is a good starting point anyway. It covers all basic topics except quadratic forms; very short introduction to SVD and Pseudo-Inverse. It is noticeable that Strang's video lectures are sometimes way better than his own book.

The book ``Linear Algebra'' written by J. Hefferon [2] is great for start and initial understanding of Linear Algebra. Clearly written and with lost of examples, it is a must-read book to quickly remember some base material of Linear Algebra. Moreover, there are some applications after each chapter. The textbook [2] is useful as a teaching material because a lot of examples and deductive approach of material's explaining. Examples in this book are very insightful (least-squares, crystals, economic examples and so on). Coverage stretches from basic to eigenvalue decomposition that is not enough (no SVD, Pseudo-Inverse and Quadratic forms at all).

Specialised books

One of the most necessary books for me is Matrix Algebra from a statistical perspective [3] written by D. Harville. The book contains most of necessary topics for Linear Algebra applications from the statistical and engineering point of view. For instance, the book contains insightful chapters about matrix differentiating (Chapter 14) that is very helpful.

The book written by Hoffman and Kunze [4] is a good starting point of studying bilinear and quadratic forms. The book of Marcus and Ming [5] is a good reference for matrix inequalities and other special topics of algebra. A very good book [6] written by Gene H. Golub contains interesting topics and discussion of Schur decomposition and Pseudoinverse.

For several advanced topics and pure mathematical proofs, I want to mention Radjendra Bhatia's Matrix Analysis [7] book. The questions such as Spectral variations of Normal matrices and Majorization were helpful for me.

Articles and notes

Many properties of product and sum of pseudoinverse matrix are described in articles. One particular article that discuss the properties of product of pseudoinverse that is (AB)^+ =A^+B^+ is Taussky's article [8].

A very good introduction to differentiating of matrices is written in small ``Notes on Matrix Calculus'' [9] by Paul L. Fackler from North Carolina State University. That is one os the most easy, clear and bright introduction to matrix differentiating that I could found.

The small book about Toeplitz and Circulant matrices with very good introduction is written by [10] (can be download from the Internet). This book allows to use the necessary properties of Toeplitz matrices in applied science without digging in pure mathematical folios. Writing style is clear and shiny with reasonable amount of examples in statistics and signal processing.

And of course, one should definitely read Schur's original paper (available in digital form) about Schur decomposition [11].

Reference books and Handbooks

A truly great reference is Leslie Hogben's handbook [12] that contains the most of material of Linear Algebra. Very concentrated material, with numerous links to other books and articles, ``Handbook of Linear Algebra'' is indispensable on reference and quick recalling some additional properties and relations of Algebra's objects.

Although the book by Horn& Johnson [13] ``Matrix Analysis'' appears in practically any reference sources, it is not an easy reading material. One should not read it from front to back, but rather selected topics. The material is well organised but is very dense: Horn&Johnson book is rather handbook than a textbook.

Useful and helpful handbook that contains many inequalities and interesting properties of Linear Algebra's objects is The Matrix Cookbook [14] written by K. B. Petersen and M. S. Pedersen. Although there are mentions the the Cookbook contains many mistakes and inaccuracies, it is useful and may be utilised as quick reference. For instance, it contains short but bright description of the matrix differentiating.

Bibliography

1: Gilber Strang.
Linear Algebra and its Applications.
Thomson Learning, 1988, 3^d Edition.
2: Jim Hefferon.
Linear Algebra.
2000.
3: D.A. Harville.
Matrix algebra from a statistician's perspective.
Springer Verlag, 2008.
4: K. Hoffman and R. Kunze.
Linear Algebra.
Prentice-Hall, Englewood Cliffs, NJ, 1971.
5: M. Marcus and H. Minc.
A survey of matrix theory and matrix inequalities.
Allyn and Bacon, Boston, 1964.
6: G.H. Golub and C.F. Van Loan.
Matrix computations, 1996.
7: R. Bhatia.
Matrix analysis.
Springer Verlag, 1997.
8: O. Taussky.
Commutativity in finite matrices.
American Mathematical Monthly, 64(4):229-235, 1957.
9: Paul L. Fackler.
Notes on matrix calculus.
North Carolina State University, 2005.
10: R.M. Gray.
Toeplitz and circulant matrices: A review.
2006.
11: I. Schur.
On the characteristic roots of a linear substitution with an application to the theory of integral equations.
Math. Ann, 66:488-510, 1909.
12: L. Hogben.
Handbook of linear algebra.
CRC Press, 2007.
13: Roger A. Horn and Charles R. Johnson.
Matrix Analysis.
Cambridge University Press, 1985.
14: K.B. Petersen and M.S. Pedersen.
The Matrix Cookbook.
Technical University of Denmark, 2008.
20081110.