Generalized Eigenvector - Motivation of The Procedure - Ordinary Linear Difference Equations

Ordinary Linear Difference Equations

Ordinary linear difference equations are equations of the sort:
yn = a yn−1 + b
yn = a yn−1 + b yn−2 + c
or more generally,
yn = amyn−1 + am−1yn−2 + ... + a2yn−m + 1 + a1yn−m + a0
with initial conditions
y0, y1, y2, ..., ym−2, ym−1.

A case with a1 = 0 can be excluded, since it represents an equation of less degree.

They have a characteristic polynomial
p(x) = xm − amxm−1 − am−1xm−2 − ... − a2x − a1.
To solve a difference equation it is first observed, if yn and zn are both solutions,
then (yn − zn) is a solution of the homogeneous equation:
yn = amyn−1 + am−1yn−2 + ... + a2yn−m + 1 + a1yn−m.

So a particular solution to the difference equation must be found together with
all solutions of the homogeneous equation to get the general solution for the
difference equation. Another observation to make is that, if yn is a solution to
the inhomogeneous equation, then
zn = yn+1 − yn
is also a solution to the homogeneous equation.
So all solutions of the homogeneous equation will be found first.

When β is a root of p(x) = 0, then it is easily seen
yn = βn is a solution to the homogeneous equation since
yn − amyn−1 − am−1yn−2 − ... − a2yn−m + 1 − a1yn−m,
becomes upon the substitution yn = βn,
βn − amβn−1 − am−1βn−2 − ... − a2βn−m + 1 − a1βn−m
= βn−m(βm − amβm−1 − am−1βm−2 − ... − a2β − a1)
= βn−mp(β) = 0.

When β is a repeated root of p(x) = 0, then
yn = nβn−1 is a solution to the homogeneous equation since
nβn−1 − am(n−1)βn−2 − am−1(n−2)βn−3 − ... − a2(n−m + 1)βn−m − a1(n−m)βn−m − 1
= (n−m)βn−m − 1(βm − amβm−1 − am−1βm−2 − ... − a2β − a1)
+ βn−m − 1(mβm−1 − (m−1)amβm−2 − (m−2)am−1βm−3 − ... − 2a3β − a2)
== (n−m)βn−m − 1p(β) + βn−m − 1p′(β) == 0.

After reaching this point in the calculation the mystery is solved. Just notice when
β is a root of p(x) = 0 with mutiplicity k, then for s = 1, 2, ..., k−1
ds(βn−mp(β))/dβs = 0.
Referring this back to the original equation
βn − amβn−1 − am−1βn−2 − ... − a2βn−m + 1 − a1βn−m
it is seen that
yn = ds(βn)/dβs
are solutions to the homogeneous equation. For example, if β is a root of
multiplicity 3, then yn = n(n−1)βn−2 is a solution. In any case this gives m
linearly independent solutions to the homogeneous equation.

To look for a particular solution first consider the simpliest equation.
yn = a yn−1 + b.
It has a particular solution yp,n given by
yp,0 = 0, yp,1 = b, yp,2 = (1 + a)b, ..., yp,n = (1 + a + a2 + ... + an−1)b, ..., .
It's homogeneous equation yn = a yn−1 has solutions yn = any0.
So zn = yn+1 − yn = anb
can be telescoped to get
yn = (yn − yn−1) + (yn−1 − yn−2) + ... + (y2 − y1) + (y1 − y0) + y0
= zn−1 + zn−2 + ... + z1 + z0 + y0
= (1 + a + a2 + ... + an−1)b ,
the particular solution with y0 = 0.

Now, returning to the general problem, the equation
yn = amyn−1 + am−1yn−2 + ... + a2yn−m + 1 + a1yn−m + a0.
When yp,n is a particular solution with yp,0 = 0, then
zn = yp,n+1 − yp,n
is a solution to the homogeneous equation with z0 = yp,1 .
So zn = yp,n+1 − yp,n
can be telescoped to get
yp,n = (yp,n − yp,n−1) + (yp,n−1 − yp,n−2) + ... + (yp,2 − yp,1) + (yp,1 − yp,0) + yp,0
= zn−1 + zn−2 + ... + z1 + z0
Considering
yp,m = amyp,m−1 + am−1yp,m−2 + ... + a2yp,1 + a1yp,0 + a0.
and rewriting the equation in the zi
zm−1 + zm−2 + ... + z1 + z0
= (am) ( zm−2 + zm−3 + ... + z1 + z0) + (am−1) ( zm−3 + zm−4 + ... + z1 + z0)
+ (am−2) ( zm−4 + zm−5 + ... + z1 + z0)
+ · · ·
+ (a3) ( z1 + z0) + (a2) ( z0) + (a0)
and
zm−1
= (am − 1) zm−2 + (am + am−1 − 1) zm−3 + (am + am−1 + am−2 − 1) zm−4
+ · · ·
+ (am + am−1 + ... + a4 + a3 − 1) z1 + (am + am−1 + ... + a3 + a2 − 1) z0
+ (a0).

Since a solution of the homogeneous equation can be found for any initial conditions
z0, z1, z2, ..., zm−2, zm−1.
reasoning conversely find such zi satisfying the equation,
just before and define yp,n by the relation
yp,0 = 0, yp,n = zn−1 + zn−2 + ... + z1 + z0

One choice is, for example, zm−1 = a0, z0 = z1 = z2 = ... = zm−2 = 0.
This solution solves the problem for all initial values equal to zero.

The general solution to the inhomogeneous equation is given by
yn = yp,n + γ1 w(1)n + γ2 w(2)n + ... + γm−1 w(m−1)n + γm w(m)n
where
w(1)n, w(2)n, ..., w(m−1)n, w(m)n
are a basis for the homogeneous equation, and
γ1, γ2, ..., γm−1, γm
are scalars.

example

yn = 8 yn−1 − 25 yn−2 + 38 yn−3 − 28 yn−4 + 8 yn−5 + 1
with initial conditions
y0 = 0, y1 = 0, y2 = 0, y3 = 0, and y4 = 0.

The characteristic polynomial for the equation is
p(x) = x5 − 8x4 + 25x3 − 38x2 + 28x − 8 = (x − 1)2(x − 2)3.

The homogeneous equation has independent solutions
w1n = 1n = 1, w2n = n·1n−1 = n, and
w3n = 2n, w4n = n·2n−1, w5n = n(n−1)·2n−2.
The solution to the homogeneous equation
zn = −3 w1n − w2n + 3 w3n − 2 w4n + ½ w5n
satisfies the initial conditions
z4 = 1, z0 = z1 = z2 = z3 = 0.
A particular solution can be found by
yp,0 = 0, yp,n = zn−1 + zn−2 + ... + z1 + z0 .

Calculating sums:
∑w1 = w1n−1 + w1n−2 + ... + w11 + w10 = n .
∑w2 = w2n−1 + w2n−2 + ... + w21 + w20 = (n−1)n / 2 .
∑w3 = w3n−1 + w3n−2 + ... + w31 + w30 = 2n − 1 .
Sums of these kinds are found by differentiating (xn − 1) / (x − 1).
∑w4 = w4n−1 + w4n−2 + ... + w41 + w40 = (n−2)2n−1 + 1 .
∑w5 = w5n−1 + w5n−2 + ... + w51 + w50 = (n2 − 5n + 8)2n−2 − 2 .

Now,
yp,n = −3 ∑w1n − ∑w2n + 3 ∑w3n − 2 ∑w4n + ½ ∑w5n
solves the initial value problem of this example.

At this point it is worthwhile to notice that all the terms that are combinations of
scalar multiples of basis elements can be removed. These are any multiples of
1, n, 2n, n·2n−1, and n2·2n−2.
So instead the particular solution next, may be preferred.
yp,n = −½ n2 .
This solution has non zero initial values, which must be taken into account.
y0 = 0, y1 = −1 ⁄ 2, y2 = −2, y3 = −9 ⁄ 2, and y4 = −8.

Read more about this topic:  Generalized Eigenvector, Motivation of The Procedure

Famous quotes containing the words ordinary and/or difference:

    I have spent so long erecting partitions around the part of me that writes—learning how to close the door on it when ordinary life intervenes, how to close the door on ordinary life when it’s time to start writing again—that I’m not sure I could fit the two parts of me back together now.
    Anne Tyler (b. 1941)

    I parted from my beloved because there was one thing which I had to tell her. She questioned me. She should have known all by sympathy. That I had to tell her it was the difference between us,—the misunderstanding.
    Henry David Thoreau (1817–1862)