{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Condition number of Vandermonde matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Consider $N+1$ unformly spaced distinct points\n",
    "$$\n",
    "-1 = x_0 < x_1 < \\ldots < x_N = 1.0\n",
    "$$\n",
    "Their Vandermonde matrix is\n",
    "$$\n",
    "\\begin{bmatrix}\n",
    "1 & x_0 & x_0^2 & \\ldots & x_0^N \\\\\n",
    "1 & x_1 & x_1^2 & \\ldots & x_1^N \\\\\n",
    "\\vdots & \\vdots & \\vdots &  & \\vdots\\\\\n",
    "1 & x_N & x_N^2 & \\ldots & x_N^N\n",
    "\\end{bmatrix}\n",
    "$$\n",
    "We will use the cond function from numpy.linalg to compute the condition number. By default, it uses the 2-norm."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "from numpy import linspace,zeros\n",
    "from numpy.linalg import cond"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "       1       1.00000000e+00\n",
      "       2       3.22550493e+00\n",
      "       3       8.01156105e+00\n",
      "       4       2.35309087e+01\n",
      "       5       6.38272826e+01\n",
      "       6       1.89814113e+02\n",
      "       7       5.35353118e+02\n",
      "       8       1.60544370e+03\n",
      "       9       4.62644992e+03\n",
      "      10       1.39516269e+04\n",
      "      11       4.07548818e+04\n",
      "      12       1.23389738e+05\n",
      "      13       3.63830758e+05\n",
      "      14       1.10480853e+06\n",
      "      15       3.28003166e+06\n",
      "      16       9.98312389e+06\n",
      "      17       2.97935974e+07\n",
      "      18       9.08473096e+07\n",
      "      19       2.72240824e+08\n",
      "      20       8.31377050e+08\n",
      "      21       2.49966299e+09\n",
      "      22       7.64316645e+09\n",
      "      23       2.30433941e+10\n",
      "      24       7.05345370e+10\n",
      "      25       2.13143827e+11\n",
      "      26       6.53020161e+11\n",
      "      27       1.97722392e+12\n",
      "      28       6.06236493e+12\n",
      "      29       1.83901872e+13\n"
     ]
    }
   ],
   "source": [
    "for N in range(1,30):\n",
    "    x = linspace(-1.0,+1.0,N+1)\n",
    "    V = zeros((N+1,N+1))\n",
    "    for j in range(0,N+1):\n",
    "        V[j][:] = x**j # This is transpose of V as defined above.\n",
    "    print(\"%8d %20.8e\" % (N,cond(V.T)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As $N$ increases, the condition number of the Vandermonde matrix is increasing, and the condition number is quite large for even moderate values of $N$ like $N=30$."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}