linalg::vandermondeSolve
-- solve a
linear Vandermonde systemlinalg::vandermondeSolve
(v, y)
returns the
solution x of the linear Vandermonde system
sum(v[i]^(j-1)*x[j], j=1..n) = y[i] for i=1..n.
linalg::vandermondeSolve(v, y)
linalg::vandermondeSolve(v, y, Transposed)
v |
- | a vector with distinct elements (a vector is an n
x 1 or 1 x n matrix of category Cat::Matrix ) |
y |
- | a vector of the same dimension and domain type as
v |
Transposed |
- | returns the solution x of the transposed system sum(v[j]^(i-1)*x[j], j=1..n) = y[i] for i=1..n. |
a vector of the same domain type as y
.
solve
, linsolve
, linalg::matlinsolve
, numeric::lagrange
, numeric::linsolve
, numeric::matlinsolve
linalg::vandermondeSolve
uses O(n^2)
elementary operations to solve the Vandermonde system. It is faster
than the general system solver solve
and the solver linsolve
, numeric::linsolve
, linalg::matlinsolve
and numeric::matlinsolve
for
linear systems.yields the coefficients of the polynomial p(v)=x1+x2*v+..+xn*v^n-1 interpolating the data table (v1,y1), ..., (vn,yn), i.e.,linalg::vandermondeSolve
([vi $i=1..n], [yi $i=1..n])
p(v0)=y0,..,p(vn)=yn .See example 1.
The Vandermonde points v and the right hand side y of the linear system are entered as vectors:
>> delete y0, y1, y2: v := matrix([[0, 1, 2]]); y:= matrix([[y0, y1, y2]])
+- -+ | 0, 1, 2 | +- -+ +- -+ | y0, y1, y2 | +- -+
The solution vector is:
>> x := linalg::vandermondeSolve(v, y)
+- -+ | 3 y0 y2 y0 y2 | | y0, - ---- + 2 y1 - --, -- - y1 + -- | | 2 2 2 2 | +- -+
The solution yields the coefficients of the interpolating polynomial:
>> P := v -> _plus(x[i+1]*v^i $ i=0..2):
through the points (0,y0), (1,y1), (2,y2):
>> P(v[1]), P(v[2]), P(v[3])
y0, y1, y2
With the optional argument Transposed, the linear system with the transposed
Vandermonde matrix corresponding to v
is solved:
>> linalg::vandermondeSolve(v, y, Transposed)
+- -+ | 3 y1 y2 y1 y2 | | y0 - ---- + --, 2 y1 - y2, - -- + -- | | 2 2 2 2 | +- -+
The Vandermonde points v and the right hand side y of the linear system are entered as 2 x 1 matrices:
>> Mat := Dom::Matrix(Dom::ExpressionField(normal)):
>> delete v1, v2, y1, y2: v := Mat([v1, v2]): y:= Mat([y1, y2]):
We define the vectors over the domain Dom::ExpressionField(normal)
in
order to simplify intermediate computations.
Next, we compute the solution of the corresponding Vandermonde system:
>> x := linalg::vandermondeSolve(v, y)
+- -+ | - v1 y2 + v2 y1 | | --------------- | | - v1 + v2 | | | | - y1 + y2 | | --------- | | - v1 + v2 | +- -+
We construct the Vandermonde matrix V
and
verify the result:
>> V := Mat([[1, v[1]], [1, v[2]]])
+- -+ | 1, v1 | | | | 1, v2 | +- -+
>> V * x
+- -+ | y1 | | | | y2 | +- -+
We solve a Vandermonde system over the field
Z7 (the integers modulo 7) represented by the domain
Dom::IntegerMod(7)
:
>> MatZ7 := Dom::Matrix(Dom::IntegerMod(7)): v := MatZ7([1, 2, 3]): y := MatZ7([0, 1, 2]):
>> linalg::vandermondeSolve(v, y)
+- -+ | 6 mod 7 | | | | 1 mod 7 | | | | 0 mod 7 | +- -+
( 1 v[1] v[1]^2 .. v[1]^(n-1) ) ( 1 v[2] v[2]^2 .. v[2]^(n-1) ) V = ( .. .. .. .. .. ) ( 1 v[n] v[n]^2 .. v[n]^(n-1) )generated by v=[v[1],..,v[n]] is invertible if and only if the v[i] are distinct.
linalg::vandermondeSolve
(x, y)
solves
V*x=y and is unique.linalg::vandermondeSolve
(x, y, Transposed)
solves transpose(V)*x=y and is unique.