ABSTRACT (original article): Single-input eigenvalue assignment problem (SEVAS) for dense (non-sparse) weakly controllable pairs A,B using Ackermann’s formula is revisited. Factorizations are presented that are interpreted using quotient (factor) vector spaces. Depending on the representations chosen for the equivalence class (given as specific projections by real orthogonal matrices), the numerical behavior of pole placement scheme can be enhanced. One version operates by placing one pole at a time (with complex conjugate poles grouped together to avoid complex arithmetic). Another version operates with the coefficients of the characteristic polynomial directly. The latter version uses orthogoanl real matrices. In both cases, there are no constraint on the number of identical poles. A version of the algorithm uses only ring arithmetic. The algorithms are compared with numerically stable algorithms that appeared in the literature, such as the Miminis-Paige algorithm or the Varga pole shifting method. In case of real distinct eigenvalues to be placed, a geometrical interpretation as the interesection of affine hyperplanes provides the value of the gain vector, which seems a novel interpretation. CITATION (original article): Philippe Müllhaupt, A quotient framework for single-input pole placement and associated algorithms, arXiv:2311.05750. https://doi.org/10.48550/arXiv.2311.05750
Pole placement using only ring operations in ( Z, +, *), in the ring of integers.
All entries in the A and B matrices are integers and the values of characteristic polynomial to be placed are integers.
The method is described in the arXiv paper arXiv:2311.05750.
The proposed algorithm PlaceAlg works with infinite precision contrary to the classical pole placement algorithms that are essentially numerical methods. To achieve this, rather than working with a limited precision using floating point numbers, the initial entries in both the A matrix and the B vector are rational expressions (fractions) of rational integers. The coefficients of the characteristic polynomial associated to the eigenvalues to be placed are fractions of rational integers as well. Exact computation without roundoff or cancellation is guaranteed and integer explosion is limited compared with more traditional determinant computations.
The name of the notebook stems from the origin of the idea of this algorithm which are specific Algebroids in the nonlinear setting, see the paper arXiv:2311.05750.
All entries in the A and B matrices are integers and the values of characteristic polynomial to be placed are integers.
The method is described in the arXiv paper arXiv:2311.05750.
The proposed algorithm PlaceAlg works with infinite precision contrary to the classical pole placement algorithms that are essentially numerical methods. To achieve this, rather than working with a limited precision using floating point numbers, the initial entries in both the A matrix and the B vector are rational expressions (fractions) of rational integers. The coefficients of the characteristic polynomial associated to the eigenvalues to be placed are fractions of rational integers as well. Exact computation without roundoff or cancellation is guaranteed and integer explosion is limited compared with more traditional determinant computations.
The name of the notebook stems from the origin of the idea of this algorithm which are specific Algebroids in the nonlinear setting, see the paper arXiv:2311.05750.
PlaceAlg[A, B, P] is called with all entries in the ring of rational integers.
A the system matrix n x n
B the input matrix (column vector n x 1)
P a vector (list) of the coefficients of the characteristic polynomial to be assigned
it returns a vector of gains given with entries as fractions of rational integers.
The algorithm uses only ring arithmetic in Z (rational integers); hence, both the A matrix and the B vector entries are rational integers. The eigenvalues to be assigned should lead to a characteristic polynomial with rational integers as coefficients as well. To pass from fraction entries description to the rational integer entries description, the A matrix, the B vector, and the eigenvalues to be assigned are multiplied by the least common multiple of all divisors of all fraction entries, that is all entries of the A matrix, all entries of the B vector and all coefficients of the characteristic polynomial associated to the eigenvalues to be assigned. Once the conversion is complete, PlaceAlg can tackle the pole placement problem using the ring of rational integers. The gain vector is then computed as a row of rational integers and a divisor (common to all the rational integer gains). This gain vector which is then a row of fractions of rational integers, computed with placeAlg using the data provided as rational integers, then works for the original problem with entries in fractions of integers.
A the system matrix n x n
B the input matrix (column vector n x 1)
P a vector (list) of the coefficients of the characteristic polynomial to be assigned
it returns a vector of gains given with entries as fractions of rational integers.
The algorithm uses only ring arithmetic in Z (rational integers); hence, both the A matrix and the B vector entries are rational integers. The eigenvalues to be assigned should lead to a characteristic polynomial with rational integers as coefficients as well. To pass from fraction entries description to the rational integer entries description, the A matrix, the B vector, and the eigenvalues to be assigned are multiplied by the least common multiple of all divisors of all fraction entries, that is all entries of the A matrix, all entries of the B vector and all coefficients of the characteristic polynomial associated to the eigenvalues to be assigned. Once the conversion is complete, PlaceAlg can tackle the pole placement problem using the ring of rational integers. The gain vector is then computed as a row of rational integers and a divisor (common to all the rational integer gains). This gain vector which is then a row of fractions of rational integers, computed with placeAlg using the data provided as rational integers, then works for the original problem with entries in fractions of integers.
Description of the problem that can be solved with PlaceAlg.nb
Description of the problem that can be solved with PlaceAlg.nb
An arbitrary n x n, A matrix is initially given. The number n is the size of the matrix.
A column n x 1 vector is also part of the initial data of the problem written B.
A column n x 1 vector is also part of the initial data of the problem written B.
Underlying the description given by A and B, there is either a linear continuous-time system
′
x
or a discrete time system
x(k+1)Ax(k)+Bu(k)
The purpose of pole placement with constant feedback is to find a vector of gains K such that after setting u = - K x, the transformed matrix A - B K has a new set of eigenvalues chosen by the designer. Pole placement can be used to stabilize the initial system (placing the eigenvalues in the safe region, the stability region, which is the left hand - side complex plane (negative real part) for a continuous-time system, or within the unit circle in the complex plane for a discrete-time system. The assumption is that the system is controllable with a single input so that all eigenvalues can be chosen at will. The history of this problem and state-of-the-art algorithms are given in the arXiv paper. Some of them are common knowledge for a graduate in control systems. Current fashionable numerical computer software provides numerical placement algorithms for doing this. In Mathematica, one can use the following commands :
In[]:=
sspec=<|"InputModel"->StateSpaceModel[{{{0,1},{1,2}},{{1,0},{1,2}},{{0,1}},{{0,0}}},SamplingPeriod->None,SystemsModelLabels->{{uf,ue}}],"FeedbackInputs"->1|>;
In[]:=
sspec=<|"InputModel"->StateSpaceModel[{{{0,1},{1,2}},{{1,0},{1,2}},{{0,1}},{{0,0}}},SamplingPeriod->None,SystemsModelLabels->{{uf,ue}}],"FeedbackInputs"->1|>;
In[]:=
Let us choose the closed - loop poles to be set to be
In[]:=
p={-4+3I,-4-3I};
The Mathematica command (provided in Mathematica 12 for instance)
In[]:=
K=StateFeedbackGains[sspec,p]
Out[]=
{{-8,18}}
In[]:=
A={{0,1},{1,2}}
Out[]=
{{0,1},{1,2}}
In[]:=
B={{1,1}}
Out[]=
{{1,1}}
In[]:=
B.Transpose[K]
Out[]=
{{10}}
In[]:=
Eigenvalues[A-Transpose[B].K]
Out[]=
{-4+3,-4-3}
The algorithm PlaceAlg
The algorithm PlaceAlg
In[]:=
PlaceAlg[A_,B_,P_]:=Module[{Ab,Bb,anb,As,Bs,ans,PP,KK},Ab=IdentityMatrix[Length[A]];Bb=B;As={Ab};Bs={Bb};ans={};PP=P;KK=IdentityMatrix[Length[A]]*First[PP];PP=Rest[PP];Do[Block[{},anb=NullSpace[Transpose[Bb]];As=Append[As,Ab];Bs=Append[Bs,Bb];ans=Append[ans,anb];Bb=anb.Ab.A.B;Ab=anb.Ab.A;KK=First[PP]Ab+anb.KK;PP=Rest[PP]];,Length[A]-1];KK=KK+Ab.A;{(Ab.B//Flatten//Part[#,1]&),KK}];
Examples and usage of PlaceAlg
Examples and usage of PlaceAlg
The following example shows how to apply the previous algorithm to a system described by a matrix A and an input vector B with the elements of the matrix A and vector B belonging to the field of fractions of rational integers.
In[]:=
A={{3/4,5/13,23/2},{78/17,5/27,2},{1/3,2/5,7/12}}
Out[]=
,,,,,2,,,
3
4
5
13
23
2
78
17
5
27
1
3
2
5
7
12
In[]:=
B={{1/2,3/7,2/13}}
Out[]=
,,
1
2
3
7
2
13
The eigenvalues to be assigned are set in this example to be
In[]:=
lam=-{{1/3,2/5,8/9}}
Out[]=
-,-,-
1
3
2
5
8
9
Before calling PlaceAlg, both the A matrix and the B vector and the eigenvalues to be assigned are scaled to clear all denominators
In[]:=
lcm1=Apply[LCM,Denominator[#]&/@Flatten[Flatten[#]&/@{A,B,lam}]]
Out[]=
835380
The new values are called An, Bn, and lamn, once A, B, lam are scaled with the least common multiple of all denominators which is lcm1
In[]:=
An=A*lcm1
Out[]=
{{626535,321300,9606870},{3832920,154700,1670760},{278460,334152,487305}}
In[]:=
Bn=B*lcm1
Out[]=
{{417690,358020,128520}}
In[]:=
lamn=lam*lcm1
Out[]=
{{-278460,-334152,-742560}}
In[]:=
An
Out[]=
{{626535,321300,9606870},{3832920,154700,1670760},{278460,334152,487305}}
In[]:=
Bn
Out[]=
{{417690,358020,128520}}
In[]:=
Pn=CoefficientList[Fold[(x-#2)#1&,1,Flatten[lamn]]//Expand,x];
Pn contains the coefficients of the characteristic polynomial in reversed order . Notice that all coefficients are rational integers .
In[]:=
Pn
Out[]=
{69093697573555200,547949132640,1355172,1}
The data are ready for an invocation to PlaceAlg :
In[]:=
Kn=PlaceAlg[An,Transpose[Bn],Pn]
Out[]=
{19560842794480316227353000,{{-7882585345911236437304100,38140950263261379318057000,318699595626146629112570625}}}
PlaceAlg returns a list with the first element being the denominator of the row of gains given in the list returned as the second element by PlaceAlg . There can be some simplification possible when forming the quotients, hence we use Mathematica Simplify[] command.
In[]:=
Knrat=Kn[[2]]/Kn[[1]]//Simplify
Out[]=
-,,
103651648008727
257214289869910
4062412855827599
2083435747946271
10057737208820665
617314295687784
In[]:=
Knc=Knrat//N
Out[]=
{{-0.402978,1.94986,16.2927}}
Cross checking the result :
In[]:=
Eigenvalues[A-Transpose[B].Knc]
Out[]=
{-0.888889,-0.4,-0.333333}
In[]:=
lam//N
Out[]=
{{-0.333333,-0.4,-0.888889}}
Hence the computed eigenvalues after pole placement match the desired eigenvalues.
More involved examples
More involved examples
We now illustrate PlaceAlg with more complex examples. The first one is one that appears in the literature relating to the robustness of Hessenberg reduction.
In[]:=
PP8=CoefficientList[Fold[(x-#2)#1&,1,Table[-i,{i,1,8}]]//Expand,x];
In[]:=
AA8={{1,2,3,4,5,6,7,8},{1,0,0,0,0,0,0,1},{-1,1,0,0,0,0,0,1},{-1,0,1,0,0,0,0,1},{-1,0,0,1,0,0,0,1},{-1,0,0,0,1,0,0,1},{-1,0,0,0,0,1,0,1},{-1,0,0,0,0,0,1,1}};BB8={{1},{1},{1},{1},{1},{1},{1},{1}};K8=PlaceAlg[AA8,BB8,PP8]Krat8=K8[[2]]/K8[[1]]//Simplify
Out[]=
{3407407992753,{{48314914555761,193274610540774,874180560098772,2221158158155641,2568160156085529,-359250021764376,-3420003852743262,-1996353021204225}}}
Out[]=
,,,,,-,-,-
519515210277
36638795621
2078221618718
36638795621
9399790968804
36638795621
23883421055437
36638795621
27614625334253
36638795621
3862903459832
36638795621
36774234975734
36638795621
21466161518325
36638795621
One sees that the eigenvalues have been properly placed.
The following example is one that rapidly becomes ill - conditioned when the dimension n increases .
Now let us check what happens when rounding off the rational expressions and using floating point numbers.
We see that this is far from the desired eigenvalues
We can conclude a couple of things. The numerical floating point result is not convincing since there are two sources of errors, the rounding off of gains and the computation of the eigenvalues, both are discussed in the arXiv paper . PlaceAlg computes exactly the solution given by Krat above and is not subject to any of the rounding off errors. There is of course an argument on the integer explosion which is true. However, as the example illustrate, this happens much later (as the dimension n increases) than the critical rounding off problems encountered using floating point numbers.
CITE THIS NOTEBOOK
CITE THIS NOTEBOOK
A quotient framework for single-input pole placement and associated algorithms
by Philippe Mullhaupt
Wolfram Community, STAFF PICKS, June 4, 2024
https://community.wolfram.com/groups/-/m/t/3187701
by Philippe Mullhaupt
Wolfram Community, STAFF PICKS, June 4, 2024
https://community.wolfram.com/groups/-/m/t/3187701