Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
3  
It’s extremely bad form to vandalize a question, especially after it’s been answered. –  Brian M. Scott Jan 18 '13 at 22:58
    
@BrianM.Scott sorry, how do i delete this question? –  user5208 Jan 18 '13 at 23:39
3  
Once a question has at least one upvoted answer, it can’t be deleted (except by a moderator). –  Brian M. Scott Jan 18 '13 at 23:47

4 Answers 4

up vote 3 down vote accepted

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...

share|improve this answer
    
did, by what reasoning did you derive the necessary condition mentioned in your post? –  114 Jan 19 '13 at 19:11
    
By the fact that the only functions $t\mapsto At^2+Bt+C$ with a (local) maximum at $t=0$ are such that $B=0$ (and that $A\gt0$, but here this condition always holds). –  Did Jan 19 '13 at 23:00

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. $$

share|improve this answer

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

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.