#Hw7 #Sunday 2/16/14 #Ha Luu ##################################### #Problem 2 # Since for f:=InterPol([[x1,y1],[x2,y2],[x3,y3],[x4,y4]],x); #factor(coeff(f,y1,1)); #(x-x4)*(x-x3)*(x-x2)/((x1-x4)*(x1-x3)*(x1-x2)) # A general formula for the unique polynomial P # sum(((product(x-xi))/(product(xj-xi)),i=1 to n,i is not equal to j)*yj,j=1..n) ##################################### #Problem 4 #InterPolFast(L,x) : input the same thins as InterPol(L,x) but use the ready made Lagrange Interpolation Formula InterPolFast:=proc(L,x) local P,n,i,a,eq: if not (type(L,list) and {seq(type(L[i],list),i=1..nops(L))}={true} and {seq(nops(L[i])-2,i=1..nops(L))}={0} ) then print(`The first argument`, L, `should be a list of pairs`): RETURN(FAIL): fi: n:=nops(L): eq:=numer(sum(L[j][2]*Multiply(product(x-L[i][1],i=1..(j-1)),product(x-L[i][1],i=j+1..n))/(Multiply(product(L[j][1]-L[i][1],i=1..(j-1)),product(L[j][1]-L[i][1],i=j+1..n))),j=1..n)): if eq=NULL then RETURN(FAIL): else RETURN(eq): fi: end: ### Note: the disadvantage of this function is what happen if the list have two exactly same points #time(InterPolFast([seq([i,i^2],i=1..100)],x)); #.156 #time(InterPol([seq([i,i^2],i=1..100)],x)); #.390 #The InterPolFast is significantly twice as fast as InterPol #However, both InterPol and InterPolFast for([seq([a[i],b[i]],i=1..10)],x) cause my system to freeze. ###################################################### #Problem 3: # Lemma: Supposed P(x) vanished at n distinct place. # By the Remainder Theorem, for any a, P(x)=(x-a)P'(x)+b # Thus if a is a root of P(x) then b = 0, the (x-a) divides P(x) # For a <>b , (x-a) does not divides (x-b). # Thus for the set of n root {x1,x2,..xn}, we can write P(x) as # P(x)=(x-x1)(x-x2)..(x-xn)P'(x) (*) # P(x) has less than degree n iff P'(x)=0 # a polynomial of degree less than n that vanishes at n distinct places must be the zero prolynomial # I have trouble proving the proof using euclidean algorithm ############################################### #C7.txt (virtual class, distance learning) Help:=proc(): print(`InterPol(L,x), InterPolF(f,x,L) , AllPols(x,d,M) `): print(`BestMonic(x,d,M)`): end: #InterPol(L,x): #inputs a list of pairs [[x1,y1],[x2,y2], ..., [xn,yn]] of numbers (or symbols)! #and a variable name x,and outputs the unique polynomial of degree <= n-1 , #let's call it P(x), such that #P(x1)=y1, P(x2)=y2, ..., P(xn)=yn, #For example, InterPol([1,3],x); should give 3. InterPol:=proc(L,x) local P,n,i,a,var,eq: if not (type(L,list) and {seq(type(L[i],list),i=1..nops(L))}={true} and {seq(nops(L[i])-2,i=1..nops(L))}={0} ) then print(`The first argument`, L, `should be a list of pairs`): RETURN(FAIL): fi: n:=nops(L): P:=add(a[i]*x^i,i=0..n-1): var:={seq(a[i],i=0..n-1)}: eq:={seq(numer(subs(x=L[i][1],P)-L[i][2])=0,i=1..nops(L))}: var:=solve(eq,var): if var=NULL then RETURN(FAIL): else RETURN(subs(var,P)): fi: end: #InterPolF(f,x,L): #inputs an expression f, in the variable x, representing #a function, and a list L=[x1,...,xn], of numbers (or symbols) #outputs the unique polynomial of degree<= n-1, #let's call it P(x), such that #P(x1)=f(x1), ..., P(xn)=f(xn). For example, #InterPolF(x^3,[1,2,3,4],x); should return x^3 InterPolF:=proc(f,x,L) local i: InterPol([seq([L[i],subs(x=L[i],f)], i=1..nops(L))], x): end: