Namespaces
Variants
Actions

Difference between revisions of "Schur stability of polynomials and matrices"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m
Line 1: Line 1:
Consider the linear discrete-time [[Dynamical system|dynamical system]] described by the difference equation
+
Consider the linear discrete-time
 +
[[Dynamical system|dynamical system]] described by the difference
 +
equation  
 +
$$x_{t+1} = Ax_t,\; t=0,1,2,\dots,$$
 +
where $x_t\in \R^n$ and $A=(a_{ij})$, $i,j=1,\dots,n$, is an $(n\times n)$-matrix with real
 +
coefficients. Let $w(z)=a_0z^n+\cdots+a_{n-1}z+a_n = \det(zE_n - A)$ be the
 +
[[Characteristic polynomial|characteristic polynomial]] for the
 +
dynamical system. The polynomial $w(z)$ (or, equivalently, the
 +
[[Matrix|matrix]] $A$) is said to be stable if all its roots are
 +
inside the unit circle on the complex plane. Similarly, the dynamical
 +
system is said to be asymptotically stable if its characteristic
 +
polynomial $w(z)$ is stable
 +
[[#References|[a2]]].
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130150/s1301501.png" /></td> </tr></table>
+
Asymptotic stability of the polynomial or dynamical system is strongly
 +
connected with Schur matrices and Schur's theorem. A Schur matrix is a
 +
square matrix with real entries and with eigenvalues (cf. also
 +
[[Eigen value|Eigen value]]) of absolute value less than one
 +
[[#References|[a1]]],
 +
[[#References|[a4]]]. Schur's theorem states that every matrix is
 +
unitarily similar to a triangular matrix. It has been noted that the
 +
triangular matrix is not unique
 +
[[#References|[a1]]].
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130150/s1301502.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130150/s1301503.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130150/s1301504.png" />, is an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130150/s1301505.png" />-matrix with real coefficients. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130150/s1301506.png" /> be the [[Characteristic polynomial|characteristic polynomial]] for the dynamical system. The polynomial <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130150/s1301507.png" /> (or, equivalently, the [[Matrix|matrix]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130150/s1301508.png" />) is said to be stable if all its roots are inside the unit circle on the complex plane. Similarly, the dynamical system is said to be asymptotically stable if its characteristic polynomial <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130150/s1301509.png" /> is stable [[#References|[a2]]].
+
A consequence of this theorem is the following. Let a matrix $A$ have
 +
eigenvalues $s_1,\dots,s_n$. Then
 +
$$\sum_{k=1}^n |s_k|^2 \le \sum_{i,j=1}^n |a_{ij}|,$$
 +
with equality if and only if $A$ is normal
 +
(cf. also
 +
[[Normal matrix|Normal matrix]]). This leads to the estimate
 +
$$|s_k| \le n\max_{i,j} | a_{ij}|,$$
 +
which can be directly used in asymptotic stability investigations for
 +
the dynamical system.
  
Asymptotic stability of the polynomial or dynamical system is strongly connected with Schur matrices and Schur's theorem. A Schur matrix is a square matrix with real entries and with eigenvalues (cf. also [[Eigen value|Eigen value]]) of absolute value less than one [[#References|[a1]]], [[#References|[a4]]]. Schur's theorem states that every matrix is unitarily similar to a triangular matrix. It has been noted that the triangular matrix is not unique [[#References|[a1]]].
+
However, it should be stressed that it is possible to use also a
 +
different method in asymptotic stability considerations. Namely, it is
 +
possible to associate to the characteristic polynomial $w(z)$ the
 +
symmetric matrix $\def\tr{\mathrm{tr}} P = S_1^\tr S_1-S_2^\tr S_2$, where
 +
[[#References|[a2]]]:
 +
$$S_1=\begin{pmatrix}a_0 & \dots &a_{n-2}&a_{n-1}\\
 +
0&\ddots&\vdots&a_{n-2}\\
 +
\vdots&\ddots&\ddots&\vdots\\
 +
0 & \dots & 0 & a_0 \end{pmatrix}$$
  
A consequence of this theorem is the following. Let a matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130150/s13015010.png" /> have eigenvalues <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130150/s13015011.png" />. Then
+
$$S_2=\begin{pmatrix}a_n & \dots &a_{2}&a_{1}\\
 +
0&\ddots&\vdots&a_{2}\\
 +
\vdots&\ddots&\ddots&\vdots\\
 +
0 & \dots & 0 & a_n \end{pmatrix}$$
 +
and the symbol $\tr$ denotes transposition. Therefore, the matrix
 +
$P=(p_{ij})$, $i=1,\dots,n$, where
 +
$$p_{ij} = \sum_{t=0}^{i-1}(a_{i-t-1}a_{j-t-1} -  a_{n+t-i+1}a_{n+t-j+1},\; j\ge i.$$
 +
The following main stability theorem holds
 +
[[#References|[a2]]]: The polynomial $w(z)$ is asymptotically stable if
 +
and only if the matrix $P$ is positive definite, i.e. $P_k > 0$ for $k=1,\dots,n$,
 +
where
 +
$$P_1 = p_{11},\;
 +
P_2 = \det\begin{pmatrix}p_{11} & p_{12}\\p_{21}&p_{22}\end{pmatrix},\dots$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130150/s13015012.png" /></td> </tr></table>
+
$$\dots, P_k = \det\begin{pmatrix}p_{11} & \dots & p_{1k}\\
 +
\vdots& \dots & \vdots\\
 +
p_{k1} & \dots & p_{kk}\end{pmatrix},\dots, P_n = \det P.$$
 +
Using this theorem, one can prove
 +
[[#References|[a2]]] that if $P_k \ne 0$ for $k=1,\dots,n$, then the characteristic
 +
polynomial $w(z)$ has $m$ roots inside and $n-m$ roots outside the unit
 +
circle, where $m = n-v(1,P_1,\dots,P_n)$ and $v$ denotes the number of sign changes in the
 +
sequence $1,P_1,\dots,P_n$.
  
with equality if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130150/s13015013.png" /> is normal (cf. also [[Normal matrix|Normal matrix]]). This leads to the estimate
+
Moreover, it should be pointed out that Schur's matrix and Schur's
 
+
theorem can be also used in the solution of the
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130150/s13015014.png" /></td> </tr></table>
+
[[Pole assignment problem|pole assignment problem]] for linear control
 
+
systems
which can be directly used in asymptotic stability investigations for the dynamical system.
+
[[#References|[a3]]].
 
 
However, it should be stressed that it is possible to use also a different method in asymptotic stability considerations. Namely, it is possible to associate to the characteristic polynomial <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130150/s13015015.png" /> the symmetric matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130150/s13015016.png" />, where [[#References|[a2]]]:
 
 
 
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130150/s13015017.png" /></td> </tr></table>
 
 
 
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130150/s13015018.png" /></td> </tr></table>
 
 
 
and the symbol <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130150/s13015019.png" /> denotes transposition. Therefore, the matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130150/s13015020.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130150/s13015021.png" />, where
 
 
 
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130150/s13015022.png" /></td> </tr></table>
 
 
 
The following main stability theorem holds [[#References|[a2]]]: The polynomial <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130150/s13015023.png" /> is asymptotically stable if and only if the matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130150/s13015024.png" /> is positive definite, i.e. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130150/s13015025.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130150/s13015026.png" />, where
 
 
 
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130150/s13015027.png" /></td> </tr></table>
 
 
 
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130150/s13015028.png" /></td> </tr></table>
 
 
 
Using this theorem, one can prove [[#References|[a2]]] that if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130150/s13015029.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130150/s13015030.png" />, then the characteristic polynomial <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130150/s13015031.png" /> has <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130150/s13015032.png" /> roots inside and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130150/s13015033.png" /> roots outside the unit circle, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130150/s13015034.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130150/s13015035.png" /> denotes the number of sign changes in the sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130150/s13015036.png" />.
 
 
 
Moreover, it should be pointed out that Schur's matrix and Schur's theorem can be also used in the solution of the [[Pole assignment problem|pole assignment problem]] for linear control systems [[#References|[a3]]].
 
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top"> R. Bhatia,   "Matrix analysis" , Springer (1997)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top"> T. Kaczorek,   "Theory of control and systems" , PWN (1993) (In Polish)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top"> A. Varga,   "A Schur method for pole assignment" ''IEEE Trans. Autom. Control'' , '''AC-26''' : 2 (1981) pp. 517–519</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top"> "Comprehensive dictionary of electrical engineering" , CRC (1999) (Dictionary)</TD></TR></table>
+
<table><TR><TD valign="top">[a1]</TD>
 +
<TD valign="top"> R. Bhatia, "Matrix analysis" , Springer (1997)</TD>
 +
</TR><TR><TD valign="top">[a2]</TD>
 +
<TD valign="top"> T. Kaczorek, "Theory of control and systems" , PWN (1993) (In Polish)</TD>
 +
</TR><TR><TD valign="top">[a3]</TD>
 +
<TD valign="top"> A. Varga, "A Schur method for pole assignment" ''IEEE Trans. Autom. Control'' , '''AC-26''' : 2 (1981) pp. 517–519</TD>
 +
</TR><TR><TD valign="top">[a4]</TD>
 +
<TD valign="top"> "Comprehensive dictionary of electrical engineering" , CRC (1999) (Dictionary)</TD>
 +
</TR></table>

Revision as of 17:46, 20 November 2011

Consider the linear discrete-time dynamical system described by the difference equation $$x_{t+1} = Ax_t,\; t=0,1,2,\dots,$$ where $x_t\in \R^n$ and $A=(a_{ij})$, $i,j=1,\dots,n$, is an $(n\times n)$-matrix with real coefficients. Let $w(z)=a_0z^n+\cdots+a_{n-1}z+a_n = \det(zE_n - A)$ be the characteristic polynomial for the dynamical system. The polynomial $w(z)$ (or, equivalently, the matrix $A$) is said to be stable if all its roots are inside the unit circle on the complex plane. Similarly, the dynamical system is said to be asymptotically stable if its characteristic polynomial $w(z)$ is stable [a2].

Asymptotic stability of the polynomial or dynamical system is strongly connected with Schur matrices and Schur's theorem. A Schur matrix is a square matrix with real entries and with eigenvalues (cf. also Eigen value) of absolute value less than one [a1], [a4]. Schur's theorem states that every matrix is unitarily similar to a triangular matrix. It has been noted that the triangular matrix is not unique [a1].

A consequence of this theorem is the following. Let a matrix $A$ have eigenvalues $s_1,\dots,s_n$. Then $$\sum_{k=1}^n |s_k|^2 \le \sum_{i,j=1}^n |a_{ij}|,$$ with equality if and only if $A$ is normal (cf. also Normal matrix). This leads to the estimate $$|s_k| \le n\max_{i,j} | a_{ij}|,$$ which can be directly used in asymptotic stability investigations for the dynamical system.

However, it should be stressed that it is possible to use also a different method in asymptotic stability considerations. Namely, it is possible to associate to the characteristic polynomial $w(z)$ the symmetric matrix $\def\tr{\mathrm{tr}} P = S_1^\tr S_1-S_2^\tr S_2$, where [a2]: $$S_1=\begin{pmatrix}a_0 & \dots &a_{n-2}&a_{n-1}\\ 0&\ddots&\vdots&a_{n-2}\\ \vdots&\ddots&\ddots&\vdots\\ 0 & \dots & 0 & a_0 \end{pmatrix}$$

$$S_2=\begin{pmatrix}a_n & \dots &a_{2}&a_{1}\\ 0&\ddots&\vdots&a_{2}\\ \vdots&\ddots&\ddots&\vdots\\ 0 & \dots & 0 & a_n \end{pmatrix}$$ and the symbol $\tr$ denotes transposition. Therefore, the matrix $P=(p_{ij})$, $i=1,\dots,n$, where $$p_{ij} = \sum_{t=0}^{i-1}(a_{i-t-1}a_{j-t-1} - a_{n+t-i+1}a_{n+t-j+1},\; j\ge i.$$ The following main stability theorem holds [a2]: The polynomial $w(z)$ is asymptotically stable if and only if the matrix $P$ is positive definite, i.e. $P_k > 0$ for $k=1,\dots,n$, where $$P_1 = p_{11},\; P_2 = \det\begin{pmatrix}p_{11} & p_{12}\\p_{21}&p_{22}\end{pmatrix},\dots$$

$$\dots, P_k = \det\begin{pmatrix}p_{11} & \dots & p_{1k}\\ \vdots& \dots & \vdots\\ p_{k1} & \dots & p_{kk}\end{pmatrix},\dots, P_n = \det P.$$ Using this theorem, one can prove [a2] that if $P_k \ne 0$ for $k=1,\dots,n$, then the characteristic polynomial $w(z)$ has $m$ roots inside and $n-m$ roots outside the unit circle, where $m = n-v(1,P_1,\dots,P_n)$ and $v$ denotes the number of sign changes in the sequence $1,P_1,\dots,P_n$.

Moreover, it should be pointed out that Schur's matrix and Schur's theorem can be also used in the solution of the pole assignment problem for linear control systems [a3].

References

[a1] R. Bhatia, "Matrix analysis" , Springer (1997)
[a2] T. Kaczorek, "Theory of control and systems" , PWN (1993) (In Polish)
[a3] A. Varga, "A Schur method for pole assignment" IEEE Trans. Autom. Control , AC-26 : 2 (1981) pp. 517–519
[a4] "Comprehensive dictionary of electrical engineering" , CRC (1999) (Dictionary)
How to Cite This Entry:
Schur stability of polynomials and matrices. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Schur_stability_of_polynomials_and_matrices&oldid=19657
This article was adapted from an original article by J. Klamka (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article