Contents

• 1  Matrix conditioning
  • 1.1  Build the Vandermonde matrix and solve the system
  • 1.2  Modify some element and solve it again
  • 1.3  Condition number

Given the points:

$$ \begin{array}{|c|ccccc|} \hline k & 0 & 1 & 2 & 3 & 4 \\ \hline x & 1 & 2 & 3 & 4 & 5 \\ y & 1 & 2 & 4 & 3 & 5 \\ \hline \end{array} $$

1. Build the Vandermonde matrix for the nodes $x$ and the system that solves the problem of interpolation using this matrix for these points. Using the python command, numpy.linalg.solve, solve it.
2. Modify some element of the Vandermonde matrix and solve the system again.
3. Compute the condition number of the array using numpy.linalg.cond. Explain why this result was to be expected.

import numpy as np
import matplotlib.pyplot as plt

Matrix conditioning

Build the Vandermonde matrix and solve the system

As we saw in the interpolation unit, the system to solve to calculate the interpolation polynomial that passes through 5 points would be

$$ \left(\begin{array}{ccccc} 1 & x_{0} & x_{0}^{2} & x_{0}^{3} & x_{0}^{4}\\ 1 & x_{1} & x_{1}^{2} & x_{1}^{3} & x_{1}^{4}\\ 1 & x_{2} & x_{2}^{2} & x_{2}^{3} & x_{2}^{4}\\ 1 & x_{3} & x_{3}^{2} & x_{3}^{3} & x_{3}^{4}\\ 1 & x_{4} & x_{4}^{2} & x_{4}^{3} & x_{4}^{4} \end{array}\right)\left(\begin{array}{c} a_{0}\\ a_{1}\\ a_{2}\\ a_{3}\\ a_{4} \end{array}\right)=\left(\begin{array}{c} y_{0}\\ y_{1}\\ y_{2}\\ y_{3}\\ y_{4} \end{array}\right) $$

And its coefficient matrix is the Vandermonde matrix. For our points, the system is

$$ \left(\begin{array}{ccccc} 1 & 1 & 1 & 1 & 1\\ 1 & 2 & 4 & 8 & 16\\ 1 & 3 & 9 & 27 & 81\\ 1 & 4 & 16 & 64 & 256\\ 1 & 5 & 25 & 125 & 625 \end{array}\right)\left(\begin{array}{c} a_{0}\\ a_{1}\\ a_{2}\\ a_{3}\\ a_{4} \end{array}\right)=\left(\begin{array}{c} 1\\ 2\\ 4\\ 3\\ 5 \end{array}\right) $$

And solving it with python

A = np.array([[1.,1,1,1,1],
              [1,2,4,8,16],
              [1,3,9,27,81],
              [1,4,16,64,256],
              [1,5,25,125,625]])
b = np.array([1,2,4,3,5])
P = np.linalg.solve(A,b)
print('a = ', P)

a =  [ 15.         -28.66666667  19.08333333  -4.83333333   0.41666667]

Modify some element and solve it again

If we modify some element

$$ \left(\begin{array}{ccccc} 1 & 1 & 1 & 1 & 1\\ 1 & 2 & 4 & 8 & {\color{red}{15}}\\ 1 & 3 & 9 & 27 & 81\\ 1 & 4 & 16 & 64 & 256\\ 1 & 5 & {\color{red}{24}} & 125 & 625 \end{array}\right)\left(\begin{array}{c} a_{0}\\ a_{1}\\ a_{2}\\ a_{3}\\ a_{4} \end{array}\right)=\left(\begin{array}{c} 1\\ 2\\ 4\\ 3\\ 5 \end{array}\right) $$

now the solution is

A1 = np.array([[1,1,1,1,1],
              [1,2,4,8,15],
              [1,3,9,27,81],
              [1,4,16,64,256],
              [1,5,24,125,625]])
b1 = np.array([1,2,4,3,5])
P1 = np.linalg.solve(A1,b1)
print('a = ', P1)

a =  [ -82.          187.91666667 -145.33333333   45.25         -4.83333333]

which, as we see, is very different from the previous solution.

print('a = ', P)

a =  [ 15.         -28.66666667  19.08333333  -4.83333333   0.41666667]

We are solving the interpolation problem, that is, we are calculating the polynomial that passes through the points. Graphically, the solutions are

%run T5_Ej4_dibu

Condition number

How is the conditioning of the coefficient matrix evaluated? With the condition number

$$ \mathrm{cond}(A)=\|A\|\,\|A^{-1}\| $$

The condition number is always greater than one, but the closer to one, the better conditioned the matrix is and vice versa. In this example

print(np.linalg.cond(A))

26169.68797063433