1109. Aproksymacja Średniokwadratowa Dyskretna [MN06_7]

Zadanie:
https://pl.spoj.com/problems/MN06_7

Skrócony opis problemu:

Dla $n$ punktów reprezentowanych przez argument $x_i$, wartość $f(x_i)$ oraz wagę $w(x_i)$ oraz $m$ funkcji bazowych wyznacz funkcję aproksymującą $F(x)$. Następnie oblicz wartości tej funkcji dla danych $n'$ argumentów $x_i'$.

Rozwiązanie:

Wystarczy obliczyć dla każdej bazy jej współczynnik $a_i$ a następnie podstawić każde $x_i'$ do tej funkcji o wzorze: $$F(x_i') = \sum_{j=1}^m a_j \varphi_j(x_i')$$

Współczynniki $a_i$ obliczamy z kolei z układu równań:

$$\begin{cases}
\left<\varphi_1,\varphi_1\right>a_1+\quad \left<\varphi_1,\varphi_2\right>a_2+\quad &\ldots+\quad \left<\varphi_1,\varphi_m\right>a_m = \left<\varphi_1,f\right> \\
\left<\varphi_2,\varphi_1\right>a_1+\quad \left<\varphi_2,\varphi_2\right>a_2+\quad &\ldots+\quad \left<\varphi_2,\varphi_m\right>a_m = \left<\varphi_2,f\right> \\
&\vdots \\
\left<\varphi_m,\varphi_1\right>a_1+\quad \left<\varphi_m,\varphi_2\right>a_2+\quad &\ldots+\quad \left<\varphi_m,\varphi_m\right>a_m = \left<\varphi_m,f\right>
\end{cases}$$
$\left<a,b\right>$ to iloczyn skalarny wektorów $a$ i $b$.
Zatem:
$$\left<\varphi_j,\varphi_k\right> = \sum_{i=1}^n w(x_i) \varphi_j(x_i) \varphi_k(x_i) \\
\left<\varphi_j,f\right> = \sum_{i=1}^n w(x_i) f(x_i) \varphi_j(x_i)$$

Gdzie $f$ to funkcja, którą aproksymujemy (dostajemy ją w postaci gotowych wartości dla danego $x_i$).

Źródło:
http://www.kaims.pl/~pborowie/MN13/METNUM_w_Aproksymacja.pdf