An example may help to clarify the issues. Suppose the input is
[1 0 0 1 0 2]The parameters
cmust be chosen to minimize this function:
E = (0 - (b + c))2 + (1 - c)2
+ (0 - (a + c))2 + (2 - (b + c))2
The minimum of this function (which is quadratic and positive definite)
will occur at the place where the derivatives of
with respect to
c are zero.
These derivatives are:
dE -- = 2(a + c) da dE -- = 2(b + c) - 2(2 - (b + c)) = 4(b + c - 1) db dE -- = 2(b + c) - 2(1 - c) + 2(a + c) - 2(2 - (b + c)) = 2(a + 2b + 4c - 3) dcSolving these equations simultaneously gives
uk = auk-1 + buk-2 + c = -uk-1 + 1
The output is therefore
[-1 2 -1 2 -1]In general, we have
E = Σ1<k<n [ uk - (auk-1 + buk-2 + c)]2
So the derivatives are:
daE = Σ1<k<n
-2uk-1[ uk - (auk-1 + buk-2 + c)]
= 2[-Σuk-1uk + Σuk-12a
+ Σuk-1uk-2b + Σuk-1c]
dbE = Σ1<k<n -2uk-2[ uk - (auk-1 + buk-2 + c)] = 2[-Σuk-2uk + Σuk-2uk-1a + Σuk-22b + Σuk-2c]
dcE = Σ1<k<n -2[ uk - (auk-1 + buk-2 + c)] = 2[-Σuk + Σuk-1a + Σuk-2b + (n-2)c]
This gives three simultaneous equations,
whose coefficients can be updated for each new item in the sequence.
Solve them simultaneously and you will obtain
For the Bonus Challenge, the automarking script will try to avoid using any data that could cause a division by zero, so it shouldn't be a problem.
Although this is possible, it is not required;
i.e. you are welcome to use an array or
ArrayList, etc, if you like;
and you may assume there will be no more than 128 items in the input.