filmov
tv
C++ - designing an accelerated 'gradient descent' algorithm.

Показать описание
I need a heuristic method for determining if a cubic is a good continuation of a given four degree polynomial.
Let me explain; I have an unknown function f(x) and its derivative f'(x).
Given three x values, reasonably close together (not too far apart, not too close) give me locally a good approximation of the unknown function. Lets say these x values are `x_a`, `x_b` and `x_c`, then I also know the values of `f(x_a)`, `f(x_b)`, `f(x_c)`, `f'(x_a)`, `f'(x_b)` and `f'(x_c)` which allows me to fit a fourth degree polynomial that goes through all three points and has the the same derivatives. In fact, extending the fourth degree function is usually a good fit still even outside the x range spanned by these three points.
Lets say that `x_a < x_b < x_c < x_d` where we also know `f(x_d)` and `f'(x_d)`. Then we can fit a cubic through c and d that goes through both points and has the corresponding derivative. Most notably, the derivative in c is the same for the fourth degree fit as well as the cubic, so if we piece-wise connect the fourth degree polynomial to the cubic (switching from one to the other in c) then the whole is C1 continuous.
However, because `x_d` can be "arbitrary" far to the right, this cubic *might* have nothing else in common with the underlying function (most notably, it doesn't if it quickly deviates from the fourth degree fit to the right of c).
What is a good heuristic to determine if the cubic is a good continuation?
Let me explain; I have an unknown function f(x) and its derivative f'(x).
Given three x values, reasonably close together (not too far apart, not too close) give me locally a good approximation of the unknown function. Lets say these x values are `x_a`, `x_b` and `x_c`, then I also know the values of `f(x_a)`, `f(x_b)`, `f(x_c)`, `f'(x_a)`, `f'(x_b)` and `f'(x_c)` which allows me to fit a fourth degree polynomial that goes through all three points and has the the same derivatives. In fact, extending the fourth degree function is usually a good fit still even outside the x range spanned by these three points.
Lets say that `x_a < x_b < x_c < x_d` where we also know `f(x_d)` and `f'(x_d)`. Then we can fit a cubic through c and d that goes through both points and has the corresponding derivative. Most notably, the derivative in c is the same for the fourth degree fit as well as the cubic, so if we piece-wise connect the fourth degree polynomial to the cubic (switching from one to the other in c) then the whole is C1 continuous.
However, because `x_d` can be "arbitrary" far to the right, this cubic *might* have nothing else in common with the underlying function (most notably, it doesn't if it quickly deviates from the fourth degree fit to the right of c).
What is a good heuristic to determine if the cubic is a good continuation?