| T.R | Title | User | Personal
Name | Date | Lines |
|---|
| 879.1 | | HPSTEK::XIA | | Thu May 26 1988 15:27 | 7 |
| Re. 0
One way to do it is to solve the characteristic equation:
Nx^N - x^(N-1) -x^(N-2) - x^(N-3) - ... - 1 = 0. I suspect that
there are not way around it. This equation might be solved, or
might not by radicals (Though I have a feeling that it can, but Gosh,
I don't want to compute the Galois group!!)
Eugene
|
| 879.2 | a hint | CLT::GILBERT | | Thu May 26 1988 18:19 | 2 |
| Hint: Let f(x , x , ..., x ) be the limit.
1 2 N
|
| 879.3 | | HPSTEK::XIA | | Thu May 26 1988 20:09 | 11 |
| Re .2
There is a classical trick one can do when one computes the limit
of a series when the series is defined recursively. For example,
If one has a recursive definition x = (x )^2 then one can let
N N-1
y be the limit (if the limit exists). Then at limit we have
y = y^2 and simply solve it. However, this trick does not work
in the nontrivial linear recursions. I am not sure if this trick
is what you are hinting, if not please inform me.
Thanks in advance.
Eugene
|
| 879.4 | | CHOVAX::YOUNG | Dumb, Expensive, Dumb ... (Pick Two) | Mon May 30 1988 02:12 | 10 |
| I may be a little brain-dead Peter, but your description seems
confusing / ambiguous to me.
I keep coming up with:
F(1) = k, F(2) = k, ... F(n) = k ... ?!?
Could you provide a *leetle beety* example please?
-- Barry
|
| 879.5 | needs proof, though | VINO::JMUNZER | | Tue May 31 1988 12:31 | 18 |
| It seems to be:
sum from 1 to N of (j * x )
j
limit = ---------------------------
sum from 1 to N of (j)
For instance, if N = 3, and you start with 0, 3, 6, you get
0, 3, 6, 3, 4, 4.33, 3.78, 4.04, 4.05, 3.95, 4.01, 4.01, 3.99, etc.,
which is
1*0 + 2*3 + 3*6
--------------- = 4
6
John
|
| 879.6 | there AREN'T N preceding numbers | VIDEO::OSMAN | type video::user$7:[osman]eric.vt240 | Tue May 31 1988 18:04 | 36 |
| > Given a list of N numbers, each successive number in the series is
> the average of the preceding N numbers. In terms of the initial
> N numbers, what is the limit of this series?
Sorry to be a stickler, but as stated, this doesn't make sense.
I interpret "given a list of N numbers" to mean that we have
a finite list for some specific positive integer N.
So, suppose N is 5. Then your statement reads:
Given a list of 5 numbers, each successive number in the series is
the average of the preceding 5 numbers. In terms of the initial
5 numbers, what is the limit of this series?
o.k. "each successive" means consider the first then the second,
then the third, then the fourth, then the fifth.
So, we want the first number in the series to be the average of
the preceding 5 numbers. But there aren't 5 preceding numbers :-(
Maybe you mean a CIRCULAR list ? Or even just a SET ?
Perhaps you mean this:
Given a set of N numbers with each being the average of
the rest, what is the limit of the values as N approaches
infinity.
Well, all the numbers might be 7, but that's uninteresting.
Please clarify...
/Eric
|
| 879.7 | restatement | ZFC::DERAMO | I am, therefore I'll think. | Tue May 31 1988 21:45 | 15 |
| What the problem means:
Given N numbers a1, ..., aN.
Define the infinite sequence x1, x2, ...
by
x1 = a1, ..., xN = aN,
x_n = (x_(n-1) + ... x_(n-N)) / N (n > N)
Describe the behavior of the sequence x1, x2, ...
(does it have limit points, does it converge, if
so to what value as a function of a1, ..., aN, etc.)
Dan
|
| 879.8 | Backward extension | TOOK::APPELLOF | Am I position independent yet? | Fri Jun 03 1988 11:13 | 6 |
| re .6
The definition in .7 should clarify things for you.
If you're worried about numbers preceding the given list,
you can always recurse backwards. That direction doesn't seem
to have a limit, though.
|
| 879.9 | Proof (most of it, anyway) | CLT::GILBERT | | Fri Jun 03 1988 12:15 | 57 |
| Let f(x , x , ..., x ) be the limit (with no proof that the limit exists).
1 2 N
We have the identity:
f(x , x , ..., x ) = f(x , x , ..., x , (x + ... + x )/N)
1 2 N 2 3 N 1 N
Now we claim (sans proof) that f is a linear function of its arguments:
N
f(x , x , ..., x ) = Sum c x
1 2 N i=1 i i
Substituting this into the above identity yields:
N N N
Sum c x = Sum c x + Sum c x / N
i=1 i i i=2 i-1 i i=1 N i
Since this is an identity in the x , we have the N equations:
i
c = c / N
1 N
c = c + c / N = c + c , 2 <= i <= N
i i-1 N i-1 1
So that
c = i c , 1 <= i <= N
i 1
And so
N
f(x , x , ..., x ) = Sum i c x
1 2 N i=1 1 i
We can determine c from the identity: f(a, a, ..., a) = a, viz:
1
N N
f(a, a, ..., a) = Sum i c a = c a Sum i = c a C(N,2) = a
i=1 1 1 i=1 1
c = 1 / C(N,2) = 2 / (N (N+1))
1
Finally,
N
f(x , x , ..., x ) = ( Sum i x ) / C(N,2)
1 2 N i=1 i
(BTW, John Munzer had the right answer in .5)
What if each next term in the series is the *negative* of the average
of the preceding N terms?
|
| 879.11 | sketch of complete proof | HERON::BUCHANAN | nihilistic technofetishist | Sun Jun 05 1988 11:25 | 84 |
| The technique that works best for this kind of problem is matrix
algebra. Define an N-dimensional vector,
u(n) = ( x(n) x(n+1) ... x(n+N-1) )'
where the ' denotes that I'm taking the transpose: i.e. it's a column
matrix not a row matrix.
I can define easily a matrix A such that
u(n) = A.u(n-1) for all n
It will look like this:
( 0 1 )
( 0 1 )
. . . .
. . . .
. . . .
( 0 1)
(1/N 1/N . . . 1/N)
Now:
u(n) = A^(n-1).u(1)
So the limiting behaviour of u(n) (and hence of x(n)) is determined by
the eigenvalues of A, i.e. the roots of the characteristic equation:
N.x^N -x^(N-1) -x^(N-2) ... -x -1
However we don't need to solve this completely. An inspection tells
us that:
(1) 1 is a root of this equation
(2) (by looking at the derivative) 1 is not a multiple root
(3) all other eigenvalues have modulus less than 1.
This is great news, because it means that only the contribution to u(n)
from the eigenvector with eigenvalue 1 is important as n goes to infinity.
The other components vanish. And now we know there's a limit.
(The Frobenius-Perron Theorem is a generalization of this notion)
The eigenvector is some multiple, c1, of (1 1 ... 1)'. It remains
to find c1. Let E be the matrix of eigenvectors written as column vectors,
with the distinguished eigenvector in the first column.
u(1) = E.c,
for some hitherto unknown vector c, of which the first value is c1, the value
that we're interested in. We could invert E to get the answer, but that would
involve knowing what the other eigenvectors are, and we only know one. We want
the first row of the inverse of E.
The way round is this. The matrix equation defining the eigenvectors
of A is:
A.E = E.D
where D is a (probably diagonal but let's not get into that) matrix of
eigenvalues. If we transpose the inverse of this equation, we get:
A~.E~ = E~.D~
where ~ denotes transpose of inverse. Remember we wanted the first row of the
inverse of E? Well that's the first column of E~, call it e, which just
happens to be an eigenvector of A~! Further the eigenvalues of A~ are the
reciprocals of the eigenvalues of A, so e has eigenvalue 1.
Note that all the other eigenvalues will have magnitude greater than
one, and so the assertion in .8, suggesting the sequence when extended to the
left diverges is correct.
A~ is easy to compute, remembering how u(n) and u(n-1) are related, and e can
found from:
(A~-I).e = 0
This is the pattern (1 2 ... N) that when normalized gives what John
Munzer spotted.
Andrew Buchanan
|
| 879.12 | Easier | HERON::BUCHANAN | nihilistic technofetishist | Sun Jun 05 1988 11:44 | 19 |
| Re: .9, if x(n) is defined to be the *negative* of the average of the preceding
N terms, then the limit is 0.
Take the same approach as before. The matrix A is identical except in
the Nth row, where all the terms are -1/N instead of 1/N. The characteristic
equation is now:
N.t^N + t^(N-1) + ... + t + 1
Once again, no eigenvalue can exceed 1 in modulus. (To see this,
view the characteristic polynomial as the sum of N terms of the form t^N + t^i
if t is greater than one in modulus, then there is no way that the t^i term
can compensate for the t^N to "drag" the poly back to the origin.)
But 1 is no longer a root of this poly. And no eigenvalue can have
modulus 1, if N>1. So all eigenvalues are smaller than one in modulus and
hence u(n) vanishes in the limit.
Andrew Buchanan
|
| 879.13 | oh well, too late | ZFC::DERAMO | I am, therefore I'll think. | Sun Jun 05 1988 23:52 | 47 |
| Re .11, good job, that covers existence and uniqueness
of the limit and its actual value.
Essentially the same proof can be given without using
matrices. If you assume a solution of the form
n
n-th term = constant times z
and plug this in to solve for z, you get the same
polynomial,
N N-1
Nz - z - ... - 1 = 0
The roots are z1 = 1, and z2, ..., zN have magnitude less
than one (the polynomial is the same as in .11 so the roots
are the same :-) and so the solution is a linear combination
of the form [assuming the roots are all distinct]
n n n
n-th term = c z + c z + ... + c z
1 1 2 2 N N
With z1 = 1, and the other terms --> 0 as n --> oo,
the limit exists and equals c1. Solving for it in terms
of the initial N terms gives the same result.
Linear recurrences can be solved like this (assume the
form of the solution, plug it in, and find the roots
of the polynomial), like in .11 (give the answer explicitly
in matrix form and explicitly compute it), by generating
functions, by .... You go through the same steps each
way but just talk to yourself differently as you do it. :-)
Dan
p.s. For a multiple root, say a root z of the polynomial
has multiplicity k, its contribution to the form for the
n-th term becomes
n n 2 n k k
c z + c nz + c n z + ... + c n z
1 2 3 k
But for z of magnitude less than one, all of these terms
still go to zero as n increases without bound.
|