How polynomial interpolation of polynomial multiplication algorithm works?

Question

I'm trying to apply the following algorithm from DPV's textbook to an example to see how it works. First, the algorithm is as following:

Algorithm [DPV, p. 60]

Input: Coefficients of two polynomials. A(x) and B(x), of degree d.

Output: Their product $C = A . B$

• Selection: Pick some points $x_0, x_1, x_2, ..., x_{n-1}$ where $n\geq 2d+1$
• Evaluation: Compute $A(x_0), A(x_1), ...., A(x_{n-1})$ and $B(x_0), B(x_1), ...., B(x_{n-1})$
• Multiplication: Compute $C(x_k)=A(x_k) \times B(x_k)$ for all $k=0, 1, ..., n-1$
• Interpolation: Recover $C(x) = c_0 + c_1 x + c_2 x^2 + .... + c_{2d} x^{2d}$

Now, I took an example $A(x) = 3x^2 -4x + 1$ and $B(x) = x-2$. The output should be $C(x) = 3x^3 - 10 x^2 + 9 x -2$. Now, the algorithm first choose an arbitrary points, so I will choose the following: $x_0 = 1, x_1 = 3, x_2=6,$ and $x_3 = 9$. Now, we evaluate the A(x_i) and B(x_i) for $i=0, 1, 2$ and 3ドル$. Thus, $A(x_0) = 0, A(x_1) = 16, A(x_2) = 85, A(x_3)=208, B(x_0) = -1, B(x_1) = -2, B(x_2) = -5,$ and $B(x_3)=-8$. Thus, we compute $C(x_i)$ for $i=0, 1, 2,$ and 3ドル$. So, we get $C(x_0) = 0, C(x_1) = -32, C(x_2)=-425,$ and $C(x_3) = -1664$.

Now, I have $x_0=1, x_1=3, x_2=6,$ and $x_3=9$ and the corresponding $C(x_0) = 0, C(x_1) = -32, C(x_2) = -425,$ and $C(x_3)=-1664$. This I will apply the polynomial interpolation to get the output. I used this page to compute the coefficients of C(x). So, I got the output as following: $-3x^3 + 7x^2 - 5x + 1$ but it should be this one: $C(x) = 3x^3 - 10 x^2 + 9 x -2$. So, where is the problem? Is it because finding interpolation cannot be in exact so the coefficient is an approximation to the exact one.

Answer 1

For testing, you can use SageMath very easily;

you had erros on

$$A(x_0) = 0, A(x_1) = 16, A(x_2) = 85, A(x_3)=208, \\B(x_0) = -1, \color{red}{B(x_1) = -2}, \color{red}{B(x_2) = -5},\color{red}{B(x_3) = 8}$$

 R = PolynomialRing(QQ, 'x')
 A = 3 *x^2-4*x+1
 B = x -2
 a0 = A(1)
 a1 = A(3)
 a2 = A(6)
 a3 = A(9)
 b0 = B(1)
 b1 = B(3)
 b2 = B(6)
 b3 = B(9)
 c0 = a0*b0
 c1 = a1*b1
 c2 = a2*b2
 c3 = a3*b3
 
 print( a0,a1,a2,a3)
 print( b0,b1,b2,b3)
 print( c0,c1,c2,c3)
 
 f = R.lagrange_polynomial([(1,c0),(3,c1),(6,c2),(9,c3)])
 f

Outputs

0 16 85 208
-1 1 4 7
0 16 340 1456
3*x^3 - 10*x^2 + 9*x - 2

• user777: Thank you Kelalaka! So it was just some wrong numbers.
• kelalaka: Yes, if you need to do only hand, double-check everything.