Multilinear Interpolation Over the Boolean Hypercube
Answer
f ~ ( x 1 , x 2 , x 3 ) = 16 x 1 + 2 x 2 + 3 x 1 x 2 + 6 x 3 + 9 x 1 x 3 + 6 x 2 x 3 + 6 x 1 x 2 x 3 + 3 \tilde f(x_1,x_2,x_3) = 16x_{1} +2x_{2} +3x_{1}x_{2} +6x_{3} +9x_{1}x_{3} +6x_{2}x_{3} +6x_{1}x_{2}x_{3} + 3 f ~ ( x 1 , x 2 , x 3 ) = 16 x 1 + 2 x 2 + 3 x 1 x 2 + 6 x 3 + 9 x 1 x 3 + 6 x 2 x 3 + 6 x 1 x 2 x 3 + 3 Step by Step Solution
General Form
f ~ ( x 1 , . . . , x n ) = ∑ w ∈ { 0 , 1 } n f ( w ) . L w ( x 1 , . . . , x n ) \tilde f(x_1, ..., x_n) = \sum _{w \in \{0, 1\}^n} f(w).L_w(x_1, ..., x_n) f ~ ( x 1 , ... , x n ) = w ∈ { 0 , 1 } n ∑ f ( w ) . L w ( x 1 , ... , x n ) w = ( w 1 , . . . , w v ) w = (w_1, ..., w_v) w = ( w 1 , ... , w v ) L w ( x 1 , . . . . , x n ) = ∏ i = 1 n L i L_w(x_1, ...., x_n) = \prod_{i = 1}^n L_i L w ( x 1 , .... , x n ) = i = 1 ∏ n L i L i = ∏ j = 0 , j ≠ i n − 1 ( x − x j x i − x j ) L_i = \prod_{j=0, j \neq i}^{n - 1}(\dfrac{x-x_j}{x_i-x_j}) L i = j = 0 , j = i ∏ n − 1 ( x i − x j x − x j ) L 0 = ( 1 − x i ) L_0 = (1 - x_i) L 0 = ( 1 − x i ) L 1 = x i L_1 = x_i L 1 = x i Finding the Lagrange Polynomials
=
( L 0 ) ( L 0 ) ( L 0 ) (L_0)(L_0)(L_0) ( L 0 ) ( L 0 ) ( L 0 )
=
( 1 − x 1 ) ( 1 − x 2 ) ( 1 − x 3 ) (1 - x_{1})(1 - x_{2})(1 - x_{3}) ( 1 − x 1 ) ( 1 − x 2 ) ( 1 − x 3 )
=
16 x 1 + 16 x 2 + x 1 x 2 + 16 x 3 + x 1 x 3 + x 2 x 3 + 16 x 1 x 2 x 3 + 1 16x_{1} +16x_{2} +x_{1}x_{2} +16x_{3} +x_{1}x_{3} +x_{2}x_{3} +16x_{1}x_{2}x_{3} + 1 16 x 1 + 16 x 2 + x 1 x 2 + 16 x 3 + x 1 x 3 + x 2 x 3 + 16 x 1 x 2 x 3 + 1 =
( L 0 ) ( L 0 ) ( L 1 ) (L_0)(L_0)(L_1) ( L 0 ) ( L 0 ) ( L 1 )
=
( 1 − x 1 ) ( 1 − x 2 ) ( x 3 ) (1 - x_{1})(1 - x_{2})(x_{3}) ( 1 − x 1 ) ( 1 − x 2 ) ( x 3 )
=
x 1 + 16 x 1 x 2 + 16 x 1 x 3 + x 1 x 2 x 3 x_{1} +16x_{1}x_{2} +16x_{1}x_{3} +x_{1}x_{2}x_{3} x 1 + 16 x 1 x 2 + 16 x 1 x 3 + x 1 x 2 x 3 =
( L 0 ) ( L 1 ) ( L 0 ) (L_0)(L_1)(L_0) ( L 0 ) ( L 1 ) ( L 0 )
=
( 1 − x 1 ) ( x 2 ) ( 1 − x 3 ) (1 - x_{1})(x_{2})(1 - x_{3}) ( 1 − x 1 ) ( x 2 ) ( 1 − x 3 )
=
x 2 + 16 x 1 x 2 + 16 x 2 x 3 + x 1 x 2 x 3 x_{2} +16x_{1}x_{2} +16x_{2}x_{3} +x_{1}x_{2}x_{3} x 2 + 16 x 1 x 2 + 16 x 2 x 3 + x 1 x 2 x 3 =
( L 0 ) ( L 1 ) ( L 1 ) (L_0)(L_1)(L_1) ( L 0 ) ( L 1 ) ( L 1 )
=
( 1 − x 1 ) ( x 2 ) ( x 3 ) (1 - x_{1})(x_{2})(x_{3}) ( 1 − x 1 ) ( x 2 ) ( x 3 )
=
x 1 x 2 + 16 x 1 x 2 x 3 x_{1}x_{2} + 16x_{1}x_{2}x_{3} x 1 x 2 + 16 x 1 x 2 x 3 =
( L 1 ) ( L 0 ) ( L 0 ) (L_1)(L_0)(L_0) ( L 1 ) ( L 0 ) ( L 0 )
=
( x 1 ) ( 1 − x 2 ) ( 1 − x 3 ) (x_{1})(1 - x_{2})(1 - x_{3}) ( x 1 ) ( 1 − x 2 ) ( 1 − x 3 )
=
x 3 + 16 x 1 x 3 + 16 x 2 x 3 + x 1 x 2 x 3 x_{3} +16x_{1}x_{3} +16x_{2}x_{3} +x_{1}x_{2}x_{3} x 3 + 16 x 1 x 3 + 16 x 2 x 3 + x 1 x 2 x 3 =
( L 1 ) ( L 0 ) ( L 1 ) (L_1)(L_0)(L_1) ( L 1 ) ( L 0 ) ( L 1 )
=
( x 1 ) ( 1 − x 2 ) ( x 3 ) (x_{1})(1 - x_{2})(x_{3}) ( x 1 ) ( 1 − x 2 ) ( x 3 )
=
x 1 x 3 + 16 x 1 x 2 x 3 x_{1}x_{3} +16x_{1}x_{2}x_{3} x 1 x 3 + 16 x 1 x 2 x 3 =
( L 1 ) ( L 1 ) ( L 0 ) (L_1)(L_1)(L_0) ( L 1 ) ( L 1 ) ( L 0 )
=
( x 1 ) ( x 2 ) ( 1 − x 3 ) (x_{1})(x_{2})(1 - x_{3}) ( x 1 ) ( x 2 ) ( 1 − x 3 )
=
x 2 x 3 + 16 x 1 x 2 x 3 x_{2}x_{3} +16x_{1}x_{2}x_{3} x 2 x 3 + 16 x 1 x 2 x 3 =
( L 1 ) ( L 1 ) ( L 1 ) (L_1)(L_1)(L_1) ( L 1 ) ( L 1 ) ( L 1 )
=
( x 1 ) ( x 2 ) ( x 3 ) (x_{1})(x_{2})(x_{3}) ( x 1 ) ( x 2 ) ( x 3 )
=
x 1 x 2 x 3 x_{1}x_{2}x_{3} x 1 x 2 x 3 Get the final Polynomial
f ~ ( x 1 , x 2 , x 3 ) = 3 ( 16 x 1 + 16 x 2 + x 1 x 2 + 16 x 3 + x 1 x 3 + x 2 x 3 + 16 x 1 x 2 x 3 + 1 ) + 2 ( x 1 + 16 x 1 x 2 + 16 x 1 x 3 + x 1 x 2 x 3 ) + 5 ( x 2 + 16 x 1 x 2 + 16 x 2 x 3 + x 1 x 2 x 3 ) + 7 ( x 1 x 2 + 16 x 1 x 2 x 3 ) + 9 ( x 3 + 16 x 1 x 3 + 16 x 2 x 3 + x 1 x 2 x 3 ) + 0 ( x 1 x 3 + 16 x 1 x 2 x 3 ) + 0 ( x 2 x 3 + 16 x 1 x 2 x 3 ) + 0 ( x 1 x 2 x 3 ) \tilde f(x_1,x_2,x_3) = 3(16x_{1} +16x_{2} +x_{1}x_{2} +16x_{3} +x_{1}x_{3} +x_{2}x_{3} +16x_{1}x_{2}x_{3} +1) +2(x_{1} +16x_{1}x_{2} +16x_{1}x_{3} +x_{1}x_{2}x_{3} ) +5(x_{2} +16x_{1}x_{2} +16x_{2}x_{3} +x_{1}x_{2}x_{3} ) +7(x_{1}x_{2} +16x_{1}x_{2}x_{3} ) +9(x_{3} +16x_{1}x_{3} +16x_{2}x_{3} +x_{1}x_{2}x_{3} ) +0(x_{1}x_{3} +16x_{1}x_{2}x_{3} ) +0(x_{2}x_{3} +16x_{1}x_{2}x_{3} ) +0(x_{1}x_{2}x_{3} ) f ~ ( x 1 , x 2 , x 3 ) = 3 ( 16 x 1 + 16 x 2 + x 1 x 2 + 16 x 3 + x 1 x 3 + x 2 x 3 + 16 x 1 x 2 x 3 + 1 ) + 2 ( x 1 + 16 x 1 x 2 + 16 x 1 x 3 + x 1 x 2 x 3 ) + 5 ( x 2 + 16 x 1 x 2 + 16 x 2 x 3 + x 1 x 2 x 3 ) + 7 ( x 1 x 2 + 16 x 1 x 2 x 3 ) + 9 ( x 3 + 16 x 1 x 3 + 16 x 2 x 3 + x 1 x 2 x 3 ) + 0 ( x 1 x 3 + 16 x 1 x 2 x 3 ) + 0 ( x 2 x 3 + 16 x 1 x 2 x 3 ) + 0 ( x 1 x 2 x 3 ) f ~ ( x 1 , x 2 , x 3 ) = 16 x 1 + 2 x 2 + 3 x 1 x 2 + 6 x 3 + 9 x 1 x 3 + 6 x 2 x 3 + 6 x 1 x 2 x 3 + 3 \tilde f(x_1,x_2,x_3) = 16x_{1} + 2x_{2} +3x_{1}x_{2} + 6x_{3} + 9x_{1}x_{3} +6x_{2}x_{3} + 6x_{1}x_{2}x_{3} + 3 f ~ ( x 1 , x 2 , x 3 ) = 16 x 1 + 2 x 2 + 3 x 1 x 2 + 6 x 3 + 9 x 1 x 3 + 6 x 2 x 3 + 6 x 1 x 2 x 3 + 3 Evaluations
f ~ ( 0 , 0 , 0 ) = 3 \tilde f(0,0,0) = 3 f ~ ( 0 , 0 , 0 ) = 3 f ~ ( 0 , 0 , 1 ) = 2 \tilde f(0,0,1) = 2 f ~ ( 0 , 0 , 1 ) = 2 f ~ ( 0 , 1 , 0 ) = 5 \tilde f(0,1,0) = 5 f ~ ( 0 , 1 , 0 ) = 5 f ~ ( 0 , 1 , 1 ) = 7 \tilde f(0,1,1) = 7 f ~ ( 0 , 1 , 1 ) = 7 f ~ ( 1 , 0 , 0 ) = 9 \tilde f(1,0,0) = 9 f ~ ( 1 , 0 , 0 ) = 9 f ~ ( 1 , 0 , 1 ) = 0 \tilde f(1,0,1) = 0 f ~ ( 1 , 0 , 1 ) = 0 f ~ ( 1 , 1 , 0 ) = 0 \tilde f(1,1,0) = 0 f ~ ( 1 , 1 , 0 ) = 0 f ~ ( 1 , 1 , 1 ) = 0 \tilde f(1,1,1) = 0 f ~ ( 1 , 1 , 1 ) = 0 © 2024 Omimi Labs. All rights reserved.