Vandermonde matrix

𝑴=𝑳𝑼

Mathematica

In[29]:= 
V[n_]:=Table[Subscript[x, i]^j,{i, 0, n},{j, 0, n}];
n=3; n1=n+1; M=V[n]

( 1 x0 x02 x03 1 x1 x12 x13 1 x2 x22 x23 1 x3 x32 x33 )

In[30]:= 
LU=Simplify[LUDecomposition[M]][[1]]

( 1 x0 x02 x03 1 x1-x0 x12-x02 x13-x03 1 x0-x2x0-x1 (x0-x2)(x1-x2) (x0-x2)(x1-x2)(x0+x1+x2) 1 x0-x3x0-x1 (x0-x3)(x3-x1)(x0-x2)(x2-x1) -((x0-x3)(x3-x1)(x3-x2)) )

In[31]:= 
L=Table[ If[i<j,LU[[j,i]], If[i==j, 1, 0]],{j,1,n1},{i,1,n1}]

( 1 0 0 0 1 1 0 0 1 x0-x2x0-x1 1 0 1 x0-x3x0-x1 (x0-x3)(x3-x1)(x0-x2)(x2-x1) 1 )

In[32]:= 
U=Table[ If[i>=j,LU[[j,i]], 0],{j,1,n1},{i,1,n1}]

( 1 x0 x02 x03 0 x1-x0 x12-x02 x13-x03 0 0 (x0-x2)(x1-x2) (x0-x2)(x1-x2)(x0+x1+x2) 0 0 0 -((x0-x3)(x3-x1)(x3-x2)) )

In[33]:= 
Simplify[Expand[L.U]]

( 1 x0 x02 x03 1 x1 x12 x13 1 x2 x22 x23 1 x3 x32 x33 )

In[36]:= 
Linv=Simplify[Inverse[L]]

( 1 0 0 0 -1 1 0 0 x1-x2x0-x1 x2-x0x0-x1 1 0 (x1-x3)(x3-x2)(x0-x1)(x0-x2) (x0-x3)(x2-x3)(x0-x1)(x1-x2) (x0-x3)(x1-x3)(x0-x2)(x2-x1) 1 )

In[37]:= 
Uinv=Simplify[Inverse[U]]

( 1 x0x0-x1 -x0x1(x0-x2)(x2-x1) x0x1x2(x0-x3)(x3-x1)(x3-x2) 0 1x1-x0 x0+x1(x0-x2)(x2-x1) -x1x2+x0(x1+x2)(x0-x3)(x3-x1)(x3-x2) 0 0 1(x0-x2)(x1-x2) x0+x1+x2(x0-x3)(x3-x1)(x3-x2) 0 0 0 -1(x0-x3)(x3-x1)(x3-x2) )

In[43]:= 
Simplify[{1,x,x^2,x^3}.Uinv]

{1,x0-xx0-x1,-(x-x0)(x-x1)(x0-x2)(x2-x1),-(x-x0)(x-x1)(x-x2)(x0-x3)(x3-x1)(x3-x2)}

In[44]:= 
Simplify[{1,x,x^2,x^3}.Uinv.Linv]

{(x-x1)(x-x2)(x-x3)(x0-x1)(x0-x2)(x0-x3),-(x-x0)(x-x2)(x-x3)(x0-x1)(x1-x2)(x1-x3),-(x-x0)(x-x1)(x-x3)(x0-x2)(x2-x1)(x2-x3),-(x-x0)(x-x1)(x-x2)(x0-x3)(x3-x1)(x3-x2)}

In[45]:= 

Transpose Vandermonde matrix

𝑴T=(𝑳𝑼)T
In[2]:= 
MT=Transpose[M]

( 1 1 1 1 x0 x1 x2 x3 x02 x12 x22 x32 x03 x13 x23 x33 )

In[7]:= 
LUT=Simplify[LUDecomposition[MT]][[1]]

( 1 1 1 1 x0 x1-x0 x2-x0 x3-x0 x02 x0+x1 (x0-x2)(x1-x2) (x0-x3)(x1-x3) x03 x02+x1x0+x12 x0+x1+x2 -((x0-x3)(x3-x1)(x3-x2)) )

In[8]:= 
LT=Table[ If[i<j,LUT[[j,i]], If[i==j, 1, 0]],{j,1,n1},{i,1,n1}]

( 1 0 0 0 x0 1 0 0 x02 x0+x1 1 0 x03 x02+x1x0+x12 x0+x1+x2 1 )

In[9]:= 
UT=Table[ If[i>=j,LUT[[j,i]], 0],{j,1,n1},{i,1,n1}]

( 1 1 1 1 0 x1-x0 x2-x0 x3-x0 0 0 (x0-x2)(x1-x2) (x0-x3)(x1-x3) 0 0 0 -((x0-x3)(x3-x1)(x3-x2)) )

In[12]:= 
Simplify[Expand[LT.UT]]

( 1 1 1 1 x0 x1 x2 x3 x02 x12 x22 x32 x03 x13 x23 x33 )

In[13]:= 
LTinv=Simplify[Inverse[LT]]

( 1 0 0 0 -x0 1 0 0 x0x1 -x0-x1 1 0 -x0x1x2 x1x2+x0(x1+x2) -x0-x1-x2 1 )

In[14]:= 
Factor /@ Evaluate[LTinv.{1,x,x^2,x^3}]

{1,x-x0,(x-x0)(x-x1),(x-x0)(x-x1)(x-x2)}

In[15]:= 

Compare factorizations of M,MT

In[17]:= 
L

( 1 0 0 0 1 1 0 0 1 x0-x2x0-x1 1 0 1 x0-x3x0-x1 (x0-x3)(x3-x1)(x0-x2)(x2-x1) 1 )

In[18]:= 
LT

( 1 0 0 0 x0 1 0 0 x02 x0+x1 1 0 x03 x02+x1x0+x12 x0+x1+x2 1 )

In[19]:= 
U

( 1 x0 x02 x03 0 x1-x0 x12-x02 x13-x03 0 0 (x0-x2)(x1-x2) (x0-x2)(x1-x2)(x0+x1+x2) 0 0 0 -((x0-x3)(x3-x1)(x3-x2)) )

In[20]:= 
Transpose[U]

( 1 0 0 0 x0 x1-x0 0 0 x02 x12-x02 (x0-x2)(x1-x2) 0 x03 x13-x03 (x0-x2)(x1-x2)(x0+x1+x2) -((x0-x3)(x3-x1)(x3-x2)) )

In[21]:= 
L

( 1 0 0 0 1 1 0 0 1 x0-x2x0-x1 1 0 1 x0-x3x0-x1 (x0-x3)(x3-x1)(x0-x2)(x2-x1) 1 )

In[22]:= 

( 1 x0 x02 x03 1 x1 x12 x13 1 x2 x22 x23 1 x3 x32 x33 )=( 1 0 0 0 1 1 0 0 1 x0-x2x0-x1 1 0 1 x0-x3x0-x1 (x0-x3)(x3-x1)(x0-x2)(x2-x1) 1 )( 1 x0 x02 x03 0 x1-x0 x12-x02 x13-x03 0 0 (x0-x2)(x1-x2) (x0-x2)(x1-x2)(x0+x1+x2) 0 0 0 -((x0-x3)(x3-x1)(x3-x2)) )

Mathematica

In[22]:= 
V[n_]:=Table[Subscript[x, i]^j,{i, 0, n},{j, 0, n}];
n=1; n1=n+1; B=V[n]

( 1 x0 1 x1 )

In[24]:= 
GaussJordan[B_]:=Module[{BI,m=Length[B],I},
  BI = Transpose[Catenate[{Transpose[B],IdentityMatrix[m]}]];
  For[k=1, k<m, k++,
    For[i=k+1, i<=m, i++,
      lik = -BI[[i,k]]/BI[[k,k]];
      For[j=1, j<=2m, j++,
        BI[[i,j]] = Simplify[BI[[i,j]] + lik BI[[k,j]]]
      ];
    ];
  ];
  For[k=m, k>1, k--,
    For[i=1, i<k, i++,
      lik = -BI[[i,k]]/BI[[k,k]];
      For[j=1, j<=2m, j++,
        BI[[i,j]] = Simplify[BI[[i,j]] + lik BI[[k,j]]]
      ];
    ];
  ];
  Return[BI]
];
GaussJordan[B]
In[16]:= 
I=2

Set::wrsym: Symbol I is Protected.2

In[25]:= 
V[3]

( 1 x0 x02 x03 1 x1 x12 x13 1 x2 x22 x23 1 x3 x32 x33 )

In[26]:= 
V[2]

( 1 x0 x02 1 x1 x12 1 x2 x22 )

In[28]:= 
Inverse[V[1]]

( x1x1-x0 -x0x1-x0 -1x1-x0 1x1-x0 )

In[29]:= 

The observations that lead to the Newton basis are also recovered by symbolic computation software that readily carries out the requisite LU calculations, exemplified here for n=3,

( 1 x0 x02 x03 1 x1 x12 x13 1 x2 x22 x23 1 x3 x32 x33 )=( 1 0 0 0 1 1 0 0 1 x0-x2x0-x1 1 0 1 x0-x3x0-x1 (x0-x3)(x3-x1)(x0-x2)(x2-x1) 1 )( 1 x0 x02 x03 0 x1-x0 x12-x02 x13-x03 0 0 (x0-x2)(x1-x2) (x0-x2)(x1-x2)(x0+x1+x2) 0 0 0 -((x0-x3)(x3-x1)(x3-x2)) ).
In[77]:= 
V[n_]:=Table[Subscript[x, i]^j,{i, 0, n},{j, 0, n}];
n=3; n1=n+1; M=V[n]; MT=Transpose[V[n]]

( 1 1 1 1 x0 x1 x2 x3 x02 x12 x22 x32 x03 x13 x23 x33 )

In[78]:= 
LU=Simplify[LUDecomposition[M]][[1]]

( 1 x0 x02 x03 1 x1-x0 x12-x02 x13-x03 1 x0-x2x0-x1 (x0-x2)(x1-x2) (x0-x2)(x1-x2)(x0+x1+x2) 1 x0-x3x0-x1 (x0-x3)(x3-x1)(x0-x2)(x2-x1) -((x0-x3)(x3-x1)(x3-x2)) )

In[79]:= 
L=Table[ If[i<j,LU[[j,i]], If[i==j, 1, 0]],{j,1,n1},{i,1,n1}]

( 1 0 0 0 1 1 0 0 1 x0-x2x0-x1 1 0 1 x0-x3x0-x1 (x0-x3)(x3-x1)(x0-x2)(x2-x1) 1 )

In[80]:= 
U=Table[ If[i>=j,LU[[j,i]], 0],{j,1,n1},{i,1,n1}]

( 1 x0 x02 x03 0 x1-x0 x12-x02 x13-x03 0 0 (x0-x2)(x1-x2) (x0-x2)(x1-x2)(x0+x1+x2) 0 0 0 -((x0-x3)(x3-x1)(x3-x2)) )

In[81]:= 
Simplify[Expand[L.U]]

( 1 x0 x02 x03 1 x1 x12 x13 1 x2 x22 x23 1 x3 x32 x33 )

In[59]:= 
Linv=Simplify[Inverse[L]]

( 1 0 0 0 -x0 1 0 0 x0x1 -x0-x1 1 0 -x0x1x2 x1x2+x0(x1+x2) -x0-x1-x2 1 )

In[74]:= 
n=Factor /@ Evaluate[Linv.{1,x,x^2,x^3}]

{1,x-x0,(x-x0)(x-x1),(x-x0)(x-x1)(x-x2)}

In[73]:= 
Uinv=Simplify[Inverse[U]]

( 1 1x0-x1 1(x0-x1)(x0-x2) 1(x0-x1)(x0-x2)(x0-x3) 0 1x1-x0 -1(x0-x1)(x1-x2) -1(x0-x1)(x1-x2)(x1-x3) 0 0 1(x0-x2)(x1-x2) -1(x0-x2)(x2-x1)(x2-x3) 0 0 0 -1(x0-x3)(x3-x1)(x3-x2) )

In[76]:= 
Together /@ Evaluate[Uinv . n]

{(x-x1)(x-x2)(x-x3)(x0-x1)(x0-x2)(x0-x3),-(x-x0)(x-x2)(x-x3)(x0-x1)(x1-x2)(x1-x3),-(x-x0)(x-x1)(x-x3)(x0-x2)(x2-x1)(x2-x3),-(x-x0)(x-x1)(x-x2)(x0-x3)(x3-x1)(x3-x2)}

In[77]:=