UVa 1074 Net Loss - とどの日記

多項式を区分的線形関数で近似する問題．お気に入りというわけではないが，ちょっと面白かった．

便宜上，求める関数を
[tex:g(x)=\begin{cases}a_1(x-c)+b & (xc) \end{cases}]
とする．
$\int_{-1}^{1}(p(x)-g(x))^{2}dx$
をどうにかしたい．ポイントは，2つ．

bを決めるとa1とa2は独立に求まる
bの値はそれほど大きくならない

後者は，積分範囲・係数が[-1,1]に収まることから類推できる．

というわけで，bを固定して上の積分をa1，a2でそれぞれ偏微分する．ここで最強のテクニック「積分記号下での微分」を使う（単純に積分の偏微分を偏微分の積分にする）．

$\frac{\partial}{\partial a_1}\int_{-1}^{1}(p(x)-g(x))^{2}dx = \int_{-1}^{1}\frac{\partial}{\partial a_1}(p(x)-g(x))^{2}dx = 0$
として計算すると，
$a_1=\frac{\int_{-1}^{c}(x-c)(p(x)-b)dx}{\int_{-1}^{c}(x-c)^2dx}$
となる．a2についても同様（積分区間が変わる）．

あとは，もう一度元の積分を計算し，最も自乗誤差の小さいa1,a2,bを出力する．

bは，[-2,2]を0.0001にしたら通った．