Appendix B: Nth Order Recurrence Formulas 

In Sections 2 and 3 of this document the optimum recurrence formulas for first and second order response were derived based on the assumption that the input function x(t) was the first or seconddegree polynomial (respectively) that passes through the given discrete values of x(t). In this appendix we generalize this method to Nth order response. 

Let x(t) and y(t) denote continuous functions of time, related according to the Nth order differential equation 

_{} 

where the coefficients a_{k} and b_{k} are constants. We will denote by r_{1}, r_{2},..., r_{N} the roots of the characteristic polynomial of the left hand side of this differential equation. 

For some instant t_{0} we are given the discrete values x(t_{0}), x(t_{0}+Dt), x(t_{0}+2Dt), ..., x(t_{0}+NDt) and y(t_{0}), y(t_{0}+Dt), y(t_{0}+2Dt), ..., y(t_{0}+(N1)Dt) , where Dt is the execution interval of the simulation. For brevity we will denote y(t_{0}+kDt) by y_{k} and x(t_{0}+kDt) by x_{k}. Our objective is to determine the value of y_{N} based on the assumption that the function x(t) over the time interval from t_{0} to t_{0}+NDt is identical to the Nth degree polynomial that passes through the given discrete values of x(t). 

Define the N“1 column vector Y and the (N+1)“1 column vector X as follows: 

_{} _{} 

Then define the square (N+1) “ (N+1) matrices A, B, and T such that the elements in the jth columns of the ith rows are as follows 

_{} 

where i and j range from 0 to N. Then define the 1 “ (N+1) and 1 “ N row vectors 

_{} 

where s_{k} denotes (1)^{k} times the kth elementary symmetric function of the quantities _{}, i = 1,2,..,N. For example, if N = 3 we have 

_{} 

In terms of the matrices defined above, the value of y_{N} can now be expressed as 

_{} 

Letting g_{i} denote the ith element of the row vector given by STA^{1}BT^{1}, we have the explicit recurrence formula 

_{} 

The values of s_{k} are always purely real for real coefficients a_{k}, even when the roots r_{1},r_{2},.., r_{N} are complex. Also, for reasons discussed in Section 2.2.5, the values of s_{k} are the exact yterm coefficients, regardless of how the x(t) function is interpolated. Only the gk coefficients would be affected if we changed our assumption as to the form of x(t) (that is, if we identified x(t) with a function different from the Nth order polynomial fit through the discrete values). 

One way of computing s_{k} is to solve the characteristic equation 

_{} 

for all the roots r_{j}, j=1 to N, and then directly compute the symmetric functions of the exponentials. However, finding all the (complex) roots of an Nth degree polynomial can be computationally laborious and involves numerous special cases. Another approach, one that avoids having to explicitly determine all the roots of the characteristic polynomial, is to use "Newton's sums". For any nonnegative integer k, let w(k) denote the sum of the kth powers of the roots r_{1},r_{2},..,r_{N}. Clearly w(0) = N. The values of w(k) for k = 1, 2, ... can be found using the identities 

_{} 

for k < N, and the recurrence 

_{} 

for all k ³ N. Now let E(k) denote the sum of the kth powers of the values of _{}, i = 1, 2, .., N. The Taylor series expansion gives 

_{} 

The values of s_{k} can now be computed using the identities 

_{} 
