ГАЗ-67 писал(а):
Попробуйте прологарифмировать числитель и знаменатель…
Для «грязных» данных это не поможет.
ГАЗ-67 писал(а):
А какие проблемы возникают со сплайнами?
Интерполирующий сплайн на грязных данных работает плохо. А сглаживающий тяжело строить, особенно на большом массиве данных. И тот, и другой почти невозможно в реальном времени.
slbel писал(а):
Как этот метод называется? Если можно, нормальную ссылку в инете на описание метода.
Метод наименьших квадратов?
![Smile :)](./images/smilies/icon_smile.gif)
Бог с ним, с названием.
Давайте разберемся по существу. Мы взяли
![$2 n + 1$ $2 n + 1$](https://dxdy-02.korotkov.co.uk/f/1/2/7/127d776c3a02707e6bd1f402b14d1da182.png)
точку, и пытаемся аппроксимировать МНК:
![$\min \sum\limits_{k=-n}^{n} (y_{m+k}- (a x_{m+k}^3+b x_{m+k}^2+c x_{m+k} + d))^2$ $\min \sum\limits_{k=-n}^{n} (y_{m+k}- (a x_{m+k}^3+b x_{m+k}^2+c x_{m+k} + d))^2$](https://dxdy-01.korotkov.co.uk/f/4/d/0/4d0c93280092871cbd0ac9c4be96a29582.png)
. С таким же успехом мы можем сдвинуть координату на
![$x_m$ $x_m$](https://dxdy-01.korotkov.co.uk/f/4/1/d/41de77e8c40f1407903ba5a5ddbe6fc682.png)
, и получить новый полином (с другими
![$a, b, c, d$ $a, b, c, d$](https://dxdy-03.korotkov.co.uk/f/6/e/6/6e65e6daf30040bd6302da423026043782.png)
):
![$ y = a (x-x_m)^3+b (x-x_m)^2+c (x-x_m)+d$ $ y = a (x-x_m)^3+b (x-x_m)^2+c (x-x_m)+d$](https://dxdy-02.korotkov.co.uk/f/9/c/4/9c44f188ba83f0f1f987cbc26835e21982.png)
. Но! МНК станет:
![$\min \sum\limits_{k=-n}^{n} (y_{m+k}- (a (x_{m+k}-x_m)^3+b (x_{m+k}-x_m)^2+c (x_{m+k}-x_m) + d))^2$ $\min \sum\limits_{k=-n}^{n} (y_{m+k}- (a (x_{m+k}-x_m)^3+b (x_{m+k}-x_m)^2+c (x_{m+k}-x_m) + d))^2$](https://dxdy-01.korotkov.co.uk/f/0/0/f/00fc9696f383babf8fdb186dda152dca82.png)
. А, поскольку узлы равноотстоящие, мы имеем
![$x_{m+k}-x_m = \delta k$ $x_{m+k}-x_m = \delta k$](https://dxdy-04.korotkov.co.uk/f/f/1/f/f1f1ac6899915ec6c72ee37a8481470382.png)
, и, соответственно,
![$\min \sum\limits_{k=-n}^{n} (y_{m+k}- (a \delta^3 k^3+b \delta^2 k^2+c \delta k+ d))^2$ $\min \sum\limits_{k=-n}^{n} (y_{m+k}- (a \delta^3 k^3+b \delta^2 k^2+c \delta k+ d))^2$](https://dxdy-01.korotkov.co.uk/f/4/8/c/48c39eb88469baac6cb647624d3a36c882.png)
. Или, обозначая
![$A = a \delta^3$ $A = a \delta^3$](https://dxdy-01.korotkov.co.uk/f/c/9/c/c9cdb1a40c845bbd3905c1474f1f484582.png)
,
![$B = B \delta^2$ $B = B \delta^2$](https://dxdy-04.korotkov.co.uk/f/7/8/d/78df2aacb1452e32f8cec4efce317d0582.png)
,
![$C = C \delta$ $C = C \delta$](https://dxdy-04.korotkov.co.uk/f/3/f/1/3f1b2055f2ac1fc141be037ff08c304582.png)
,
![$D = d$ $D = d$](https://dxdy-04.korotkov.co.uk/f/b/7/3/b7382bca89e0635f3cb862b26f9003ec82.png)
,
![$\min \sum\limits_{k=-n}^{n} (y_{m+k}- (A k^3+B k^2+C k+ D))^2$ $\min \sum\limits_{k=-n}^{n} (y_{m+k}- (A k^3+B k^2+C k+ D))^2$](https://dxdy-03.korotkov.co.uk/f/e/c/e/ece66270b142a51af0b1489e7b3416f782.png)
. При этом наш интерполяционный полином станет
![$ y = A (\frac{x-x_m}{\delta})^3+B (\frac{x-x_m}{\delta})^2+C (\frac{x-x_m}{\delta})+D$ $ y = A (\frac{x-x_m}{\delta})^3+B (\frac{x-x_m}{\delta})^2+C (\frac{x-x_m}{\delta})+D$](https://dxdy-01.korotkov.co.uk/f/c/d/9/cd9a82605459811095bae2e430a2d1a682.png)
.
Теперь дифференцируем по
![$A, B, C, D$ $A, B, C, D$](https://dxdy-01.korotkov.co.uk/f/0/5/1/051acf589afb511be499207cfe411f5382.png)
и получаем уравнения:
![$A \sum k^3 + B \sum k^2 + C \sum k + D \sum 1 = \sum_k y_{m+k}$ $A \sum k^3 + B \sum k^2 + C \sum k + D \sum 1 = \sum_k y_{m+k}$](https://dxdy-01.korotkov.co.uk/f/c/a/2/ca2fd9f68d4b47b07ea5af28e58433b082.png)
,
![$A \sum k^4 + B \sum k^3 + C \sum k^2 + D \sum k = \sum_k k y_{m+k} $ $A \sum k^4 + B \sum k^3 + C \sum k^2 + D \sum k = \sum_k k y_{m+k} $](https://dxdy-02.korotkov.co.uk/f/1/1/c/11c3deab1b70ff9b006e4d56ec8172be82.png)
,
![$A \sum k^5 + B \sum k^4 + C \sum k^3 + D \sum k^2 = \sum_k k^2 y_{m+k} $ $A \sum k^5 + B \sum k^4 + C \sum k^3 + D \sum k^2 = \sum_k k^2 y_{m+k} $](https://dxdy-04.korotkov.co.uk/f/b/f/8/bf8514aa05e7d2da02506a85646cbc1282.png)
,
![$A \sum k^6 + B \sum k^5 + C \sum k^4 + D \sum k^3 = \sum_k k^3 y_{m+k} $ $A \sum k^6 + B \sum k^5 + C \sum k^4 + D \sum k^3 = \sum_k k^3 y_{m+k} $](https://dxdy-01.korotkov.co.uk/f/8/4/4/844f24e714b8829953a7ca4630e978b582.png)
.
(1) Очевидно, что матрица системы постоянна, в смысле от
![$m$ $m$](https://dxdy-01.korotkov.co.uk/f/0/e/5/0e51a2dede42189d77627c4d742822c382.png)
не зависит. Более того, она легко и непринужденно точно обращается любой системой компьютерной алгебры. Не хочется вбивать формулы — тоже неплохо. Можно вычислить и обратить в программе.
(2) Таким образом, вычисление сводится к подсчету сумм в правой части и умножению на обратную матрицу.
(3) Следующий фокус позволяет резко сократить объем вычислений при переходе от
![$m \to m+1$ $m \to m+1$](https://dxdy-02.korotkov.co.uk/f/d/6/1/d6156efe608351fcc3efd42dd9f51b8682.png)
. Обозначим
![$z_{m}^{(p)} \to \sum\limits_{k=-n}^{n}k^p y_{m+k}$ $z_{m}^{(p)} \to \sum\limits_{k=-n}^{n}k^p y_{m+k}$](https://dxdy-04.korotkov.co.uk/f/f/4/9/f498bed1ccd4022da4a56abf32c7912182.png)
.
Действительно, например,
![$ z_{m}^{(0)}+y_{m+n}-y_{m-n}$ $ z_{m}^{(0)}+y_{m+n}-y_{m-n}$](https://dxdy-03.korotkov.co.uk/f/a/1/8/a181b8961963b0ad3cec726fec2796ea82.png)
. Таким образом, мы за два сложения смогли перевычислить
![$z^{(0)}$ $z^{(0)}$](https://dxdy-01.korotkov.co.uk/f/c/b/4/cb49d75b6990bfcf45d925acdafb780a82.png)
.
![$\sum\limits_{j=-0}^{p} (-1)^p C^j_p z_{m}^{(p)} + n^p y_{m+1+n} -(-n-1)^p y_{m-n} $ $\sum\limits_{j=-0}^{p} (-1)^p C^j_p z_{m}^{(p)} + n^p y_{m+1+n} -(-n-1)^p y_{m-n} $](https://dxdy-04.korotkov.co.uk/f/f/5/7/f579de9a9a5ba83f1b84a1a2f69138ae82.png)
.
“All together now”: за весьма ограниченное и независящее от
![$n$ $n$](https://dxdy-02.korotkov.co.uk/f/5/5/a/55a049b8f161ae7cfeb0197d75aff96782.png)
количество сложений/умножений мы можем перейти от интерполяционного полинома в
![$m$ $m$](https://dxdy-01.korotkov.co.uk/f/0/e/5/0e51a2dede42189d77627c4d742822c382.png)
к полиному в
![$m+1$ $m+1$](https://dxdy-01.korotkov.co.uk/f/4/6/8/468c63cefe623320eeebfe059e5f840882.png)
. Это дает основание считать производные при
![Smile :)](./images/smilies/icon_smile.gif)
(первая
![$B$ $B$](https://dxdy-03.korotkov.co.uk/f/6/1/e/61e84f854bc6258d4108d08d4c4a085282.png)
, вторая —
![$2 C$ $2 C$](https://dxdy-03.korotkov.co.uk/f/6/4/0/640791f2fdffc1bdd31c8652ca9fe9e782.png)
) и переходить к следующему полиному.
Бич этого подхода — накопление ошибки. Всё точно складывается и вычитается только на бумаге. Реально необходимо по крайней мере двойная точность (double).