2
$\begingroup$

Assume that $f(x)$ has a minimum in the interval $x_{n-1}\leq x\leq x_{n+1}$ where $x_k=x_0+kh$, $k$ being an integer. Show that the interpolation of $f(x)$ by a polynomial of second degree yields the approximation $$f_n-\frac{1}{8}\left[\frac{(f_{n+1} - f_{n-1})^2}{f_{n+1} -2f_{n}+f_{n-1}}\right],$$ $f_k=f(x_k)$.

I know that the error term for second degree polynomial approximation

$$error \leq \frac{M_{3}}{(3)!}\max_{x\in[x_{k-1},x_{k+1}]}|(x-x_{k-1})(x-x_{k})(x-x_{k+1})|$$ where $$M_3=\max_{\xi\in[x_{k-1},x_{k+1}]}|f^3(\xi)|$$

Please help me to solve the problem.

$\endgroup$
8
  • $\begingroup$ First the formula $x_{n-1}\leq k\leq x_{n+1}$. Shouldn't that be $x_{n-1}\leq x_k\leq x_{n+1}$ or rather $x_{n-1}\leq x\leq x_{n+1}$? And then an approximation of what? An approximation of the minimum? $\endgroup$ Oct 29, 2015 at 15:37
  • $\begingroup$ @HandeBruijn Yes. That is $x$. I shall edit. $\endgroup$ Oct 29, 2015 at 15:47
  • $\begingroup$ Still don't see what you want to approximate. The minimum? $\endgroup$ Oct 29, 2015 at 15:50
  • $\begingroup$ @HandeBruijn Here the approximation means the approximation of the unknown function $f(x)$ by a polynomial of 2nd degree, say, $P_2(x)$ such that $f(x_i)=P_2(x_i)$, $i$ runs over the arguments. Polynomial approximation obeys the Weierstrass theorem of approximation i.e $|f(x)-P_2(x)|<\epsilon$. Or expanding, $f(x)=P_2(x)+R_2(x)$ where $R_2(x)$ is the error term whose maximum value is given above with the actual question. $\endgroup$ Oct 29, 2015 at 15:52
  • $\begingroup$ @HandeBruijn Is my explanation is clear? $\endgroup$ Oct 29, 2015 at 16:00

1 Answer 1

2
+50
$\begingroup$

The function is approximated by a second order polynomial. Let: $$ f(x) = a(x-x_n)^2+b(x-x_n)+c $$ Specify for the points $x_k$ with $k=n-1,n,n+1$ , with $x_{n+1}-x_n=h$ and $x_{n-1}-x_n=-h$ : $$ \begin{array}{l} f_{n-1} = a h^2 - b h + c \\ f_{n} = c \\ f_{n+1} = a h^2 + b h + c \end{array} $$ Subtract the first equation from the last one: $$ f_{n+1} - f_{n-1} = 2 b h \quad \Longrightarrow \quad b = \frac{f_{n+1} - f_{n-1}}{2h} $$ Substitute this and $\,c\,$ into the last equation: $$ f_{n+1} = a h^2 + \frac{f_{n+1} - f_{n-1}}{2h} h + f_{n} \quad \Longrightarrow \quad a = \frac{f_{n+1} -2 f_n + f_{n-1}}{2h^2} $$ The minimum of $f(x)$ - find it e.g. by differentiation - is obtained for $x-x_n = -b/(2a)$ .
And the minimum is: $$ f(x_n-b/(2a)) = a\left[-\frac{b}{2a}\right]^2 + b\left[-\frac{b}{2a}\right] + c = c-\frac{b^2}{4a} $$ Now substitute the values found for $\{a,b,c\}$ and you're done.

EDIT. Combine the condition $x_{n-1}\leq x\leq x_{n+1}$ with the place of the minimum: $$ x-x_n = -b/(2a) = -\frac{(f_{n+1}-f_{n-1})/(2h)}{2(f_{n+1} -2 f_n + f_{n-1})/(2h^2)} \quad \Longrightarrow \\ x_{n-1} \leq x_n-\frac{f_{n+1}-f_{n-1}}{f_{n+1} -2 f_n + f_{n-1}} \frac{1}{2} h \leq x_{n+1} \quad \Longrightarrow \\ -h \leq \frac{f_{n+1}-f_{n-1}}{f_{n+1} -2 f_n + f_{n-1}} \frac{1}{2} h \leq +h \quad \Longrightarrow \\ \left| f_{n+1}-f_{n-1} \right| \leq 2\left|f_{n+1} -2 f_n + f_{n-1}\right| $$ Unless $f$ is a constant, this ensures that the denominator is nonzero in: $$ f_n-\frac{1}{8}\left[\frac{(f_{n+1} - f_{n-1})^2}{f_{n+1} -2f_{n}+f_{n-1}}\right] $$ Also note that still there can be a maximum instead of a minimum, all depending on the sign of the denominator (which is $\sim$ the discretization of the second order derivative). From the question as it is formulated therefore can be concluded that $f_{n+1} -2f_{n}+f_{n-1}$ is positive, or: $$ f_n < \frac{f_{n+1}+f_{n-1}}{2} $$ So $f_n$ is smaller than the mean of its neighbors. If $f_n$ is itself the minimum, then its neighbors are equal: $f_{n-1}=f_{n+1}$ . If not, then the minimum is $< f_n$ .

$\endgroup$
3
  • $\begingroup$ For minimum values of $f(x)$, $f''(x)$ should be +ve. We have $f''(x)=2A$. Also from second last inequality that you have done, one can get $$-h\leq \frac{B}{2A}\leq h$$ But this expression does not show that $A>0$. Then how to modify it to get the minimum value by second differentiation method? $\endgroup$ Oct 31, 2015 at 18:21
  • $\begingroup$ A=a, B=b (considered) $\endgroup$ Oct 31, 2015 at 18:47
  • $\begingroup$ @user1942348: Indeed this has not been covered. I've adapted the last lines of the answer according to your comment. $\endgroup$ Nov 2, 2015 at 12:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .