0
$\begingroup$

find interpolation polynomial for $f(x) = x^4+3x^2$ of degree $\le3$ , such that $max_{x\in[-1,1]}|f(x)-p(x)|$ is minimal.

Well I think I don't understand Chebyshev's interpolation points correctly, I tried to take Chebyshev's polynomial of order 4 ($T_4(x)$), to get 4 roots (interpolation points): $\{x_k:=cos(\frac{\pi}{8} +\frac{\pi}{4}k) :k=0,1,2,3 \}$, Yet when calculating $f[x_0],f[x_0,x_1],f[x_0,x_1,x_2], f[x_0,x_1,x_2,x_3]$ in order to get the interpolation polynomial, due to the fact that the roots are $x_0 = -x_3 , x_1 =-x_2$ and the function $x^4+3x^2$, calculated in $x_0,x_1,x_2,x_3$ leads to $f[x_0]=f[x_3] , f[x_1]=f[x_2]$ , thus $f[x_0,x_1,x_2,x_3] =0 $ and I get a interpolation polynomial of order 2, which doesn't best approximate $f(x)$. I was sure that Chebyshev's roots are the only interpolation points which solves the min-max problem of $|f(x)-p(x)|$, but I feel that, there is something which I don't fully understand here.

Any help or reference would be appreciated.

$\endgroup$
  • $\begingroup$ Could the mention of the function $x^4-3x^2$ in the description of the interpolation process be more than just a typo? $\endgroup$ – random Jan 2 at 12:38
  • $\begingroup$ @random nop,sorry just a typo $\endgroup$ – dan Jan 2 at 16:19
2
$\begingroup$

The interpolation method finds the unique polynomial of degree 3 or less that has the same value as $f(x)$ at $x_0,x_1,x_2$ and $x_3$, the roots of $T_4(x)=8x^4-8x^2+1$.

Since $f(x)$ is a polynomial of degree 4, it can be written as $\sum_{i=0}^4 a_i T_i(x)$, where comparison of the coefficients shows that $a_4=\frac18$.

Therefore the required approximation is $f(x)-\frac 18 T_4(x)$.

$\endgroup$
  • $\begingroup$ rethinking about this problem, If I use $T_4$ roots $x_0 ,x_1,x_2,x_3$ to calculate $p$ the interpolation polynomial using newton method. Am I suppose to get $f(x)-\frac{1}{8}T_4(x)$ ? if so, why? otherwise, why $p$ is not the best approximation for $f$? $\endgroup$ – dan Feb 18 at 11:31
  • 1
    $\begingroup$ You are supposed to get $f(x)-\frac{1}{8}T_4(x)$ because the candidates are all polynomials of degree 3 or less, so the remaining error can be any polynomial of degree 4 with leading term $x^4$. It can be shown that among those remaining error polyomials $\frac 18T_4(x)$ is the one with the smallest maximum absolute value on $[-1,1]$. $\endgroup$ – random Feb 23 at 13:49
  • $\begingroup$ yes, you are absolutely right I figured out how to show that for every monic polynomial of degree $n$ , $max\{|p(x)| : x\in[-1,1]\} \ge \frac{1}{2^n}$ so $T_n (x)$ indeed solves the min-max problem $\endgroup$ – dan Feb 23 at 14:11
1
$\begingroup$

The solution to the uniform approximation problem will need to satisfy the Haar conditions $$ f(x_k)-p(x_k)=(-1)^kr $$ for 5 distinct points in the interval which also realize the maximum $|r|$ of $|f(x)-p(x)|$. The Chebyshev approximation usually provides a good starting point for the Remez exchange algorithm. It may be useful to compute the further stages still in terms of the Chebyshev polynomials as basis.


As result of solving this as general non-linear problem I get the results

xr = -0.707106947599892  -1.1668963128834e-16     0.707106947599893
r =   0.125000072497002
p =  -4.05725754051219e-17  4   2.33379262604217e-16  -0.125000072497002

essentially replacing $x^4$ with $x^2-\frac18$. The plots confirm the solution and Haar conditions

enter image description here

using octave/matlab's fsolve

function eqn = haar(u, f)
    x = sort(u(1:3)); r = u(4); p = u(5:8);
    df = polyder(f); dp=polyder(p);

    fp = @(x) polyval(f,x)-polyval(p,x);
    dfp = @(x) polyval(df,x)-polyval(dp,x);
    eqn = [ fp(-1)-r,
            fp(x(1))+r,
            fp(x(2))-r,
            fp(x(3))+r,
            fp(1)-r,
            dfp(x(1)),
            dfp(x(2)),
            dfp(x(3))
          ];
end

f = [1,0,3,0,0];
u = fsolve(@(u) haar(u,f), [-0.8,0.0, 0.8, 1, 0, 0, 0, 0]);     
xr = u(1:3)
r = u(4)
p = u(5:8)
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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