The Routh-Hurwitz is a criteria which serves to prove or disprove the stability of an electric control system.
Given a system which has an equation of the form
Q(s) are polynomials of any degree, it is said to be stable if all the roots of the polynomial
Q(s) are in the left half of the complex plane, which means the real part of the root is negative.
For polynomials of degree less than or equal to 2, it is trivial to determine the roots and notice whether or not the system is stable. For polynomials
Q(s) of higher degrees, the Routh–Hurwitz theorem can be useful to determine whether the system is Hurwitz-stable or not.
One of the methods to apply this theorem for any degree is described on Wikipedia that consists of performing operations on rows of a table, then counting the number of sign changes in the first column of the table. It goes as follows:
- Fill the first two rows with the coefficients of the polynomial, in the following pattern: 1st row consists of the even coefficients
s^0; 2nd row consists of the odd coefficients
Keep calculating the following rows by calculating the determinant of the matrix (last 2 rows of the first column, last 2 rows of the next column) divided by (the value of the first column on the row above); it is detailed in this part of the Wikipedia article.
If you encounter a row full of zeros, set it to the derivative of the polynomial that the row above it represents. Depending on the row it is on, the number on each cell represents a coefficient. It is illustrated in the example later.
If you encounter a zero with other non-zero values, the system is not stable: you can stop there. (You could continue but you'll get the same result). A zero on the first column would mean a root of real value 0, which renders the system unstable.
Otherwise, continue until the end. Then, if not all the values in the first column are of the same sign, the system is not stable.
Here are some examples of that process:
# Polynomial: 1 3 6 12 8.00 s^4 1 6 8 s^3 3 12 0 s^2 2 8 0 s^1--0-0--0-- < Row of zero - replace it by: s^1 4 0 0 < Derivative 2*s^2 + 8*s^0 = 4*s^1 (between each 2 columns the power of s is lowered by 2) s^0 8 0 0 < Continue normally # Sign Changes: 0 (equivalent to no root in the right half plane) # Stable: Yes
s^2 1 -2 s^1 1 0 s^0 -2 0 # Sign Changes: 1 (equivalent to 1 root in the right half plane) # Stable: No
The program will keep reading polynomials from standard input until a blank line, and output
1for stable/non-stable respectively for each polynomial on a new line.
The program can read the polynomial coefficients in any form. It could be
1 3 6 12 8for the first example (it suits this problem better, but it doesn't really matter in the end).
It has to handle cases where
0in the first column, or
0in the following columns, or a row full of
0is encountered properly. (Note: just in case, no need to see how many roots are in rhp/lhp/jw axis).
It can short-circuit the process at any time if a condition is met, there is no need to show the RH table in the end.
You do not have to use this method. Any method which will determine whether or not a system is Hurwitz-stable can do the job.
It doesn't matter which language you chose to do it with, as long as it's not done in one single built-in function call. I did mine in Python, I'll post it soon.
This is a code golf. The shortest code wins.
Here's a sample input/output (given in the above mentioned way) to test your program with:
#input: 1 12 6 10 10 6 14 1 1 -2 1 2 1 2 1 3 1 3 16 1 2 3 6 2 1 1 2 14 88 200 800 1 2 3 6 2 1 1 3 6 12 8 1 4 5 2 4 16 20 8 #output: 0 0 1 0 0 0 0 1 0
If you need more clarifications, let me know, I'll do my best to clarify.