I do not actually understand how it appears over and over again. But, I see two ways to get it. Suppose an equation an+1=3an+2. You can get an using generating functions.
That is, recurrence an+1=3an+2 turns into
a(x)−a0x=3a(x)+21−x
or
a(x)=11−3x(2x1−x+a0)=a0+11−3x−11−x=(a0+1)∑03nxn−∑0xn
which determines an=(a0+1)3n−1.
Please note that we had characteristic polynomial (1−3x)(1−x) in the denominator. The eignevalues are also obvious from the system graph:
Feedback s=3 exponentiates the node a while feedback s=1 keeps input 2 constant. But, though 2/(1−x) comes up from the very beginning, we had to solve for a(x) for the second eigenvalue, 1−3x to appear in the equation.
Alternatively, xn+1=3xn+2 can be written as a system
[x21]=[3201]=[x11]=s[x11]
The eigenvalues, s, can be found solving
|3−s201−s|=0=(3−s)(1−s)
yeilding two eigenvalues. With corresponding eigenvectors, [10] and [−11], we can form the eigenmatrix S=[1−101] and its inverse S−1=[1101]. This allows to compute n-th vector quickly:
[xn1]=Xn=[3201]nX0=SΛnS−1X0=
=[1−101][3n001n][1−101]X0=[3n3n−101n][x01]
This gives the same result, xn=x03n+3n−1=(x0+1)3n−1 you've seen above.
This time, characteristic polynomial appeared because of A−λI matrix determinant.
In generating functions
Let ∑0anxn=a(x). Then, left hand turns into ∑0an+1xn=∑0an+1xn+1x=∑1anxnx=∑0anxn−a0x=(a(x)−a0)/x and 2+2x+2x2+⋯=2∑0xn=21−x.That is, recurrence an+1=3an+2 turns into
a(x)−a0x=3a(x)+21−x
or
a(x)=11−3x(2x1−x+a0)=a0+11−3x−11−x=(a0+1)∑03nxn−∑0xn
which determines an=(a0+1)3n−1.
Please note that we had characteristic polynomial (1−3x)(1−x) in the denominator. The eignevalues are also obvious from the system graph:
Feedback s=3 exponentiates the node a while feedback s=1 keeps input 2 constant. But, though 2/(1−x) comes up from the very beginning, we had to solve for a(x) for the second eigenvalue, 1−3x to appear in the equation.
As matrix eigenvalues
Alternatively, xn+1=3xn+2 can be written as a system
[x21]=[3201]=[x11]=s[x11]
The eigenvalues, s, can be found solving
|3−s201−s|=0=(3−s)(1−s)
yeilding two eigenvalues. With corresponding eigenvectors, [10] and [−11], we can form the eigenmatrix S=[1−101] and its inverse S−1=[1101]. This allows to compute n-th vector quickly:
[xn1]=Xn=[3201]nX0=SΛnS−1X0=
=[1−101][3n001n][1−101]X0=[3n3n−101n][x01]
This gives the same result, xn=x03n+3n−1=(x0+1)3n−1 you've seen above.
This time, characteristic polynomial appeared because of A−λI matrix determinant.
Analysys
In either case we have obtained an=(a0+1)3n−1n. This corresponds to the idea that solution is a combination of eigenvalues, xn=x01λn1+x02λn2+⋯, similarly to n-th order matrix, →xn=An→x0=An[x01→e1+x02→e2+⋯]= =x01λn1→e1+x02λn2→e2+⋯=SΛnS−1→x0. . I've used x0i for coefficients in order to highlight that they are determined by initial value). The polynomials are not exactly equal, though. The polynomial (1-3x)(1-x), which appears in the denominator of generating function a(x)is not equal to the determinant of the matrix, (3−s)(1−s). The roots x, 1/3 and 1, are reciprocal of the real eigenvalues s = 3 and 1. The coefficients next to x are the eigenvalues. GENERATING FUNCTIONS by MIGUEL A. LERMA calls the (1-3x)(1-x) = 1-4x+3x² a reciprocal of the characteristic polynomial 3-4s+2s². The reference is worth to read because it provides a way of spotting the sequence an generating function instead of building it. The reciprocal polynomials are also called (clique or dependence polynomials) You get it by (3-4s+2s²)x² = (3-4x⁻¹+2x⁻²)x² = 3x²-4x¹+2.
If the characteristic polynomial is a determinant of the matrix |A-sI|, the reciprocal polynomial is determinant of the matrix |I-xA|.
If the characteristic polynomial is a determinant of the matrix |A-sI|, the reciprocal polynomial is determinant of the matrix |I-xA|.
No comments:
Post a Comment