#Nathan Fox
#Homework 7
#I give permission for this work to be posted online

#Read procedures from class
read(`C7.txt`):

Help:=proc():
    print(` Problem2(n) , InterPolFast(L, x) , Problem5(n) `):
    print(` ChebyshevInterp(f, x, n `):
end:

##PROBLEM 2##

Problem2:=proc(n) local x, y, z, i, f:
    f:=InterPol([seq([x[i], y[i]], i=1..n)], z):
    return seq(factor(coeff(f, y[i], 1)), i=1..n):
end:

#CONJECTURE (which I know is correct since I
#know Lagrange interpolation)
#
#f(z)=add(y[j]*mul(z-x[i],i<>j)/mul(x[j]-x[i], i<>j), j=1..n)

##PROBLEM 3##

#See hw7.pdf

##PROBLEM 4##

#Fast interpolation
InterPolFast:=proc(L, x) local S, i, n:
    n:=nops(L):
    S:={seq(i, i=1..n)}:
    return add(L[j][2]*mul((x-L[i][1])/(L[j][1]-L[i][1]),
        i in S minus {j}), j=1..n):
end:

#time(InterPolFast([seq([a[i],b[i]],i=1..10)],x)); returned 0.003
#I had to kill InterPol([seq([a[i],b[i]],i=1..10)],x); before it
#finished
#I didn't bother timing the other ones
#
#Note: adding a simplify into the InterPolFast slows it
#down significantly

##PROBLEM 5##

Problem5:=proc(n) local i, x:
    plot(eval(InterPolF(abs(x),x,[seq(i/n,i=-n..n)]))
        -eval(abs(x)),x=-1..1);
end:

#See hw7p5n5.gif, hw7p5n10.gif, hw7p5n15.gif
#for the plots

##PROBLEM 6##

#This procedure fixes the problems
ChebyshevInterp:=proc(f, x, n) local k, L:
    L:=[seq(cos((k+1/2)*Pi/(n+1)), k=0..n)]:
    return InterPolF(f, x, L):
end: