Approximate a function over the interval $[0, 1]$ by a polynomial of degree $n$ (or less).

Question

To approximate a function $G$ over the interval $[0,1]$ by a polynomial $P$ of degree $n$ (or less), we minimize the function $f:R^{n+1} \to R$ given by $F(a) = \int_0^1 (G(x) - P_a(x))^2\,dx$, where $P_a(x) = a_nx^n+a_{n-1}x^{n-1}+\cdots+a_0$ and $a = (a_0,a_1,\ldots,a_n)$.

Find the equation satisfied by the optimal coefficients $a_*$ (necessary condition). Show that this equation can by written as a linear equation of the form $Ma_* = B$ for some vector $B$ in $R^{n+1}$ and some symmetric matrix $M$ in $R^{(n+1)\times(n+1)}$.

To be honest, I have never seen a question of this type and don't know where to start, any help in regards to the thought process would be appreciated.

Thanks

Answer 1

Note that $P_{a+tb}=P_a+tP_b$ hence $$ F(a+tb)=F(a)-2t\int_0^1 (G-P_a)P_b+t^2\int_0^1 P_b^2. $$A necessary condition for $F(a+tb)\geqslant F(a)$ to hold for every $t$ in a neighborhood of $0$ is that $$ \int_0^1 (G-P_a)P_b=0. $$ Using this for each $P_b(x)=x^k$ with $0\leqslant k\leqslant n$ yields the conditions $$ \sum_{i=0}^na_i\int_0^1 x^{i+k}\mathrm dx=\int_0^1 G(x)x^{k}\mathrm dx. $$ You might want to deduce $M$ and $B$ from here...

Answer 2

Expand the square $$ (G(x)-P_a(x))^2 = G(x)^2 + 2\sum_{0 \leq i < j \leq n}a_ia_jx^{i+j} + \sum_{i=0}^n(a_ix^i)^2 - 2G(x)\sum_{i=0}^na_ix^i. $$

Integrating we get $$ F(a) = F(0) + 2\sum_{i<j}\frac{a_ia_j}{i+j+1} + \sum_{i=0}^n \frac{a_i^2}{2i+1} - 2\sum_{n=0}^\infty a_i\int_0^1x^iG(x)dx. $$

This is a polynomial (thus $\mathscr{C}^\infty$) function of the coefficients. The optimal coefficients (they exists according to the orthogonal projection theorem) must satisfy the equation $\nabla F(a)=0$: $$ \sum_{j\neq i}\frac{a_j}{i+j+1} + \frac{a_i}{2i+1} - \int_0^1 x^iG(x)dx = 0,\qquad0 \leq i \leq n. $$

Answer 3

$M$ is equal to the Hilbert matrix $M_{i,k}=\int_0^1 x^{i+k}dx$.

Answer 4

This is an optimization problem (you can actually find it in Luenberger's book "Linear and Nonlinear Programming" in the exercises of Chapter 7 (3rd edition)).

The necessary optimality conditions state that in order for $a_*$ to be optimal, it must satisfy $\nabla_a F(a_*)=0$, in other words, we must have $\frac{\partial F}{\partial a_i}(a_*)=0,~\forall i=0,\ldots,n$. The partial derivatives of $F$ with respect to the $a_i$ are given by: \begin{align*} \frac{\partial F}{\partial a_i}(a)&=\frac{\partial }{\partial a_i}\left(\int_0^1 (G(x)-P_a(x))^2 dx\right)\\ &=\int_0^1 \frac{\partial }{\partial a_i}(G(x)-P_a(x))^2 dx\\ &=-2\int_0^1 x^i (G(x)-P_a(x)) dx \end{align*} Setting these derivatives to 0 yields: \begin{align*} \forall i=0,\ldots,n\quad \int_0^1 x^i G(x)dx &=\int_0^1 x^i P_a(x)dx \\ &=\sum_{j=0}^n a_j \left(\int_0^1 x^{j+i}dx\right)\\ &=\sum_{j=0}^n a_j\times \frac{1}{1+i+j} \end{align*} We can rewrite these last equalities in matrix form as: \begin{equation*} \begin{pmatrix} 1 & \frac{1}{2} & \frac{1}{3} & \ldots & \frac{1}{n+1}\\ \frac{1}{2} & \frac{1}{3} & \frac{1}{4} & \ldots & \frac{1}{n+2}\\ \frac{1}{3} & \frac{1}{4} & \frac{1}{5} & \ldots & \frac{1}{n+3}\\ \vdots & & & &\vdots\\ \frac{1}{n+1}& \frac{1}{n+2} & \frac{1}{n+3} & \ldots & \frac{1}{2n+1} \end{pmatrix} \begin{pmatrix} a_0\\a_1\\a_2\\ \vdots \\ a_n \end{pmatrix}= \begin{pmatrix} \int_0^1 G(x)dx\\ \int_0^1 x G(x)dx\\ \int_0^1 x^2 G(x)dx\\ \vdots\\ \int_0^1 x^n G(x)dx \end{pmatrix} \end{equation*} whence you can identify $M$, $a$ and $B$. Note that as Ana pointed out, $M$ is the Hilbert matrix.