Vandermonde Matrix

Introduction

Alexander Theophilus Vandermonde (28 February 1735 – 1 January 1796) was a French musician and mathematician, known for his work in higher algebra.

For a long time, Vandermonde's main hobby was only music, but by the age of 35, the young scientist turned to mathematics. First, he conducted a study of symmetric functions and the solution of circular polynomials, after which he published three articles: on the knight's move problem, on combinatorics, and on the foundations of the theory of determinants.

A special class of matrices was named after Alexander Theophilus – Vandermonde matriceswhich will be discussed in this article. [1]

In linear algebra, a Vandermonde matrix is a matrix with terms of a geometric progression in each row.

Let's look at the nodes Where $x_i =\frac{i}{n}$ For

Then the first column of the matrix will be completely filled. the same ; the second column will be filled third – and so on. General view of the matrix:

$\begin{bmatrix} 1 & x_0 & x_0^2 & ... & x_0^n\\ 1 & x_1 & x_1^2 & ...& x_1^n \\ 1 & x_2 & x_2^2 & ... & x_2^n\\ ... & ... & ... &... &... \\ ... &... & ... &... &x_n^n \end{bmatrix}$

Application – interpolation

The interpolation problem is to find a polynomial of the form:

which satisfies the condition:

This can be done using the Vandermonde matrix, following the formula:

Where – Vandermonde matrix, – vector of coefficients and – vector of values. [2]

$\begin{bmatrix} 1 & x_0 & x_0^2 & ... & x_0^n\\ 1 & x_1 & x_1^2 & ...& x_1^n \\ 1 & x_2 & x_2^2 & ... & x_2^n\\ ... & ... & ... &... &... \\ ... &... & ... &... &x_n^n \end{bmatrix} \begin{bmatrix} a_0 \\ a_1 \\ ... \\ a_n \end{bmatrix} =\begin{bmatrix} y_0 \\ y_1 \\ ... \\ y_n \end{bmatrix}$

Example

Three points are given: you need to find a polynomial of the form

passing through these points.

First, let's construct the Vandermonde matrix.

$\begin{bmatrix} 1 & 1 & 1 \\ 1 & 3 & 9 \\ 1 & 2 & 4 \end{bmatrix}$

Next, we expand the matrix with the values of the vector

$\begin{bmatrix} 1 & 1 & 1 &| & 2 \\ 1 & 3 & 9 & | & 4 \\ 1 & 2 & 4 & | & 3 \end{bmatrix}$

Using the rules for adding and subtracting matrix rows, we simplify it to the form:

$\begin{bmatrix} 1 & 0 & 0 & | & 1 \\ 0 & 1 & 0 & | & 1 \\ 0 & 0 & 1 & | & 0\end{bmatrix}$

Next, we solve the system using the substitution method,

So ours polynomial equal

Code

We will create our own function vandermonde_matrix,which calculates the matrix

Vandermonde with knotsWhere $x_i =\frac{i}{n}$ For .

The input data of the function is the degree the desired polynomial, and the output data is a matrix.

import numpy as np

def vandermonde_matrix(n):
    A=np.zeros((n+1,n+1)) 
    for i in range (n+1):
        for j in range (n+1): 
            A[i][j]=(i/n)**j if n !=0 else 1
    return A

print(vandermonde_matrix(3)) #пример

code run result (4x4 matrix) — code run result (4×4 matrix)

Condition number

In numerical analysis condition number of a function shows how much the value of a function can change with a small change in the argument. The condition number reflects how sensitive the function is to changes or errors in the input and how much of the output error is a result of the input error. [3]

The condition number for the Vandermonde matrix will be calculated as product of two norms – norms of the Vandermonde matrix and norms of the inverse Vandermonde matrix.

Code

For we will construct the Vandermonde matrix

we will calculate the condition number of the matrix and plot a graph of the dependence of the condition number of the Vandermonde matrix on .

import numpy as np
import matplotlib.pyplot as plt


def vandermonde_matrix(n):
    A=np.zeros((n+1,n+1)) 
    for i in range (n+1):
        for j in range (n+1): 
            A[i][j]=(i/n)**j if n !=0 else 1
    return A

cond_vandermonde=np.zeros(101)

for i in range (1, 101):
    matrix=vandermonde_matrix(i)
    matrix_inv=np.linalg.inv(matrix)
    cond_vandermonde[i]=np.array(np.linalg.norm(matrix)*np.linalg.norm(matrix_inv))
    
n_values=np.zeros(101)

for i in range(1, 101):
    n_values[i]=np.array(i)
plt.semilogy(n_values, cond_vandermonde)
plt.ylabel('n')
plt.xlabel('Число Обусловленности')
plt.title('Зависимость числа обусловленности от n') 
plt.show()

We can notice that when the size increases matrices, condition number Also is increasing. This is due to the fact that the Vandermonde matrix contains larger and larger differences in the elements, which leads to an increase in the values of the determinant.

Because the determinant of the Vandermonde matrix can increase greatly with increasing matrix size, numerical instabilities and losses in calculation accuracy occur. Thanks to which we can summarize.

Conclusion

The interpolation method using the Vandermonde matrix is effective for a small number of points when it is necessary to construct a matrix small sizeHowever, for large data or cases with high sensitivity to accuracy, more robust methods may be required.

Vandermonde Matrix

Introduction