20161023発表.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Cubic Splines"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "flexibiliyとsimplicityが大きいが、連続な1次導関数、2次導関数を持つ。  \n",
    "そのため、関数も1次、2次導関数も十分に近似できる。  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The Basis Function"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The basis functions for an n-degree cubic spline with evenly spaced breakpoints on the interval [a, b]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The n-2 breakpoints　　"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$𝑣_𝑗=𝑎+ℎ(𝑗−1),  𝑗=1, 2,…, 𝑛−2$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$ℎ=\\frac{𝑏−𝑎}{𝑛−3}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "breakpoints (generic function with 1 method)"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function breakpoints(a::Real, b::Real, n::Real)\n",
    "    v = zeros(n-2)\n",
    "    h = (b - a) / (n - 3)\n",
    "    for j in 1:n-2\n",
    "        v[j] = a + h * (j - 1)\n",
    "    end\n",
    "    return v\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "ename": "LoadError",
     "evalue": "LoadError: UndefVarError: a not defined\nwhile loading In[16], in expression starting on line 1",
     "output_type": "error",
     "traceback": [
      "LoadError: UndefVarError: a not defined\nwhile loading In[16], in expression starting on line 1",
      ""
     ]
    }
   ],
   "source": [
    "x = linspace(a, b, n)\n",
    "\n",
    "function basis_func(a, b, n, x)\n",
    "    b = Array(Float64, n, n-2)\n",
    "    \n",
    "    for i in 1:n\n",
    "        b[i, 0] = b[i, n] = 0\n",
    "    end\n",
    "    \n",
    "    for i in 1:n\n",
    "        for j in 1:n-2\n",
    "            b[i, j] = ((x[i] - v[j-3]) * b[i, j-1]) / (v[j] - v[j-3]) + ((v[j+1] - x[i]) * b[])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "また、曲率が最も大きい範囲にbreakpointsを集めれば曲率による近似の困難さをうまく乗り切れることがしばしばある。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Runge’s function "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$𝑓(𝑥)= (1 +25𝑥^2)^{-1}, 𝑥∈[−5, 5]$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Runge's functionが高い曲率を示している範囲（0付近）にbreakpointsを集めた場合、breakpointsを均等に配置した場合よりもApproximation errorsは小さくなる。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "通常k次のスプラインはbreakpointsにおいてk-1次まで連続な導関数を持つ。  \n",
    "q個のbreakpointsを積み重ねることで、そのbreakpointにおいてk-q次まで連続な導関数を持つことができる。  \n",
    "ある点でkinkを持つことが分かっていればbreakpointsの積み重ねが役立つ。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### important and useful properties"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "basis functionの値が0にならない点は限られているので、sparse matrix methodを使ってspline interpolation matricesを記憶・操作できる。  \n",
    "sparse matrixとは成分のほとんどが0である行列のこと。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "スプラインの値は有界なのでscaling effectsによって数値計算上の困難が起こる可能性は低い"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### Inverse"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "特に行列が大きいとき、spline interpolation matrixを逆行列にするとsparsity構造が壊れてしまう。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 6.4   Piecewise Linear Basis Functions  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "近似される関数がスムーズでなく不連続のときでさえlinear splineを使えばかなり近似できる。  \n",
    "ただし、導関数は区分分けされた定数関数で、不連続。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "導関数近似の有力候補は有限差分近似を使ったlinear spline"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "もともとのn個のbreakpointsの中点に新しくn-1個のbreakpointをつくる。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$𝑧_𝑖=  \\frac{𝑣_𝑖 + 𝑣_{𝑖+1}}{2},  𝑖=1, …,𝑛-1 $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "新しいbreakpointsにおける微分の近似"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$𝑓^′ (𝑧_𝑖 ) \\approx  \\frac{𝑓(𝑣_{𝑖+1}) − 𝑓(𝑣_𝑖)}{𝑣_{𝑖+1} − 𝑣_𝑖}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$z_i$の間または外側の値は線形補間または外挿によって得る"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "積分近似ではもともとのbreakpointsの範囲を超えて外挿した値も使う"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$𝑧_1= \\frac{3𝑣_1−𝑣_2}{2}$$  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$𝑧_{𝑛+1}= \\frac{3𝑣_𝑛 − 𝑣_{𝑛−1}}{2}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "積分"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$F(x) = \\int_{v_1}^{x}f(x)dx$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "を新しいbreakpointsで近似"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$F(z_i) = F(z_{i-1}) + (z_i - z_{i-1})f(v_{i-1})$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "ただし"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$F(z_1) = \\frac{1}{2}(v_1 - v_2)f(v_1)$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "この定義によって得られる積分近似はもともとのbreakpointsにおいては台形則によって得られる近似に等しい。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\\int_{𝑣_𝑖}^{𝑣_{𝑖+1}}f(x)dx \\approx \\frac{1}{2}(𝑣_{𝑖+1}−𝑣_𝑖)[𝑓(𝑣_{𝑖+1})+𝑓(𝑣_𝑖)]$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "検証？"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "これらの近似関数によって得られる\"derivatives\"や\"integrals\"は近似とみなしてよいが、polynomialやspline関数の場合はダメ。  \n",
    "しかし、もしも$\\phi(X)c$の導関数を$\\phi^{'}(X)c$のように定義したならばこれらの近似を使って得られるpiecewise linear functionsも同様に微分作用・積分作用について閉じている。（$\\phi^{'}(X)c$集合に属する？）  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "splineでは微分・積分はpiecewise segmentsの次数を増減させ、breakpoint sequenceは変化させない。  \n",
    "piecewise linear familyは逆。  \n",
    "finite difference operatorsを使った計算が楽。  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Julia 0.4.6",
   "language": "julia",
   "name": "julia-0.4"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "0.4.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}