notebooks/LA_normed_linear_space.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# ノルム線形空間\n",
    "\n",
    "参考：\n",
    "* [Markov Decision Processes: Discrete Stochastic Dynamic Programming](https://onlinelibrary.wiley.com/doi/book/10.1002/9780470316887)のAppendix C\n",
    "\n",
    "$V$を$S$上の有界な実数関数の集合とします．つまり，$v \\in V$について，$|v(s)| \\leq K_v$となる$K_v$が存在します．\n",
    "また，$sup_{v \\in V} K_v=+\\infty$かもしれないことには注意しましょう．\n",
    "\n",
    "それぞれの$v\\in V$について，$v$のノルムを\n",
    "$$\n",
    "\\|v\\|=\\sup _{s \\in S}|v(s)|\n",
    "$$\n",
    "とします．これをsupノルムと呼ぶことにします．\n",
    "このとき，$V$は和，スカラー積について閉じており，そしてノルムが定義されているので，これはノルム線形空間です．\n",
    "\n",
    "---\n",
    "\n",
    "**コーシー列と完備空間**\n",
    "\n",
    "系列$\\{v_n\\} \\subset V$は，次を満たすときにコーシー列であるといいます：\n",
    "\n",
    "* 任意の$\\varepsilon > 0$について，次を満たす$N$が存在する．$n > N$および$m > N$なら，$\\|v_n - v_m\\| < \\varepsilon$．\n",
    "\n",
    "つまり，コーシー列においてインデックスを増やすとその差がどんどん小さくなります．また，任意のコーシー列が極限を持つとき，その空間は「完備」であるといいます．\n",
    "普通に考える空間は完備ですが，例えば有理数の空間などは完備ではありません：[https://mathlandscape.com/complete-space/](https://mathlandscape.com/complete-space/)参照．\n",
    "\n",
    "ノルム線形空間かつ完備な空間をバナッハ空間といいます．\n",
    "\n",
    "---\n",
    "\n",
    "MDPでは$V$は例えば意思決定ルールや報酬，価値関数に相当します．\n",
    "$\\{v_n\\}$を$V$中の系列としましょう．次を満たすとき，$v_n$は$v$に収束する，といいます．\n",
    "\n",
    "$$\n",
    "\\lim _{n \\rightarrow \\infty}\\left\\|v_n-v\\right\\|=0\n",
    "$$\n",
    "\n",
    "これは一様収束する，といいます（ノルムが収束することに注意しましょう）．\n",
    "一方で，それぞれの$v_n(s)$が$v(s)$に収束する場合は各点収束する，といいます．[一様収束と各点収束参照](https://mathlandscape.com/uniformly-pointwise-convergence/)\n",
    "\n",
    "---\n",
    "\n",
    "$V$は半順序集合であるとします．（定義はググってください）\n",
    "このとき，$V$は半順序ノルム線形空間と呼びます．\n",
    "\n",
    "---\n",
    "\n",
    "$Q$を$V$上の線形作用素とします（例えば遷移行列みたいな）．\n",
    "例えば$S$が離散であれば，これは行列として問題ありません．次を満たすとき，$V$上の変換$Q$は有界であるといいます．任意の$v \\in V$で，次を満たす$K > 0$が存在する：\n",
    "\n",
    "$$\n",
    "\\|Q v\\| \\leq K\\|v\\| .\n",
    "$$\n",
    "\n",
    "続いて，$Q$のノルムを次で定義しましょう：\n",
    "$$\n",
    "\\|Q\\|=\\sup \\{\\|Q v\\|:\\|v\\| \\leq 1, v \\in V)\n",
    "$$\n",
    "\n",
    "定義から，$\\|Q v\\| \\leq\\|Q\\|\\|v\\|$が成り立ちます．特に$S$が離散であれば，つまり$Q$が行列なら，\n",
    "\n",
    "$$\n",
    "\\|Q\\|=\\sup _{s \\in S} \\sum_{j \\in S}|q(j \\mid s)|\n",
    "$$\n",
    "\n",
    "と同じです．また，有界な線形作用素$P$と$Q$について，\n",
    "$$\n",
    "\\|P Q\\| \\leq\\|P\\|\\|Q\\|\n",
    "$$\n",
    "も一般に成り立ちます．\n",
    "\n",
    "$L(V)$を$V$上の有界な線形作用素の集合とします．\n",
    "線形作用素についてのノルムを考えると，次が成立します．\n",
    "\n",
    "「$V$がバナッハ空間ならば，$L(V)$もバナッハ空間である．」\n",
    "\n",
    "つまり，$V$が線形かつ完備なら，$L(V)$も線形かつ完備です．\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 固有値について\n",
    "\n",
    "$$\n",
    "(Q-\\nu I) v=0 .\n",
    "$$\n",
    "を満たす$v \\neq 0$が存在するとき，$\\nu$は線形作用素$Q \\in L(V)$の固有値といいます．\n",
    "また，それを満たす$v \\neq 0$を固有ベクトルといいます．\n",
    "\n",
    "複素数$\\nu$は，$(\\nu I-Q)^{-1}$が存在するとき，$Q$のレゾルベント集合$\\rho(Q)$に含まれる，といいます．\n",
    "また，このとき$(\\nu I-Q)^{-1}$のことを$Q$のレゾルベント，と呼びます．\n",
    "レゾルベント集合は，線形作用素が良い性質を持つことを保証するための集合です．\n",
    "\n",
    "ここで，$s(Q)$を，$Q$についてのスペクトルとよび，$\\rho(Q)$の補集合とします．\n",
    "$S$が有限ならば，$s(Q)$は$Q$の固有値の集合になります．\n",
    "次で定義される量のことを$Q$についてのスペクトル半径と呼びます\n",
    "\n",
    "$$\n",
    "\\sigma(Q) \\equiv \\lim _{n \\rightarrow \\infty}\\left\\|Q^n\\right\\|^{1 / n}\n",
    "$$\n",
    "\n",
    "$Q \\in L(V)$なら，この極限は存在します．また，この値は$\\sigma(Q)=\\sup_{\\nu \\in s(Q)}|\\nu|$と一致します．$S$が有限であれば，これは行列$Q$の最大の固有値です．\n",
    "\n",
    "ちなみに$\\left\\|Q^n\\right\\|^{1 / n} \\leq\\|Q\\|$なので，$\\sigma(Q) \\leq\\|Q\\|$が成立します．\n",
    "\n",
    "もっと一般的には，スペクトル半径は任意の行列ノルムの下界です：（参考： https://power-of-awareness.com/entry/2022/09/02/050000 ）\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 逆行列の展開\n",
    "\n",
    "\n",
    "次が成立します：\n",
    "\n",
    "---\n",
    "\n",
    "$Q$をバナッハ空間$V$上の有界な線形作用素とします．\n",
    "また，$\\sigma(I - Q) < 1$とします．このとき，$Q^{-1}$が存在し，\n",
    "\n",
    "$$\n",
    "Q^{-1}=\\lim _{N \\rightarrow \\infty} \\sum_{n=0}^N(I-Q)^n\n",
    "$$\n",
    "\n",
    "が成立します．こういう級数展開のことをノイマン級数展開と呼びます．これはOccupancy measureなどを考えるときにめっちゃ便利です．\n",
    "\n",
    "**証明**\n",
    "\n",
    "仮定より，$\\sigma(I - Q) < b < 1$を満たす$b < 1$が存在します．\n",
    "$\\sigma(Q)$と$\\lim$の定義より，与えられた$\\varepsilon > 0$に対して，次を満たす$N^*$が存在します：\n",
    "\n",
    "任意の$n \\geq N^*$について，\n",
    "\n",
    "$$\n",
    "\\left\\|(I-Q)^n\\right\\|^{1 / n}<b+\\varepsilon<1\n",
    "$$\n",
    "\n",
    "よって，\n",
    "$$\n",
    "\\left\\|(I-Q)^n\\right\\|<(b+\\varepsilon)^n\n",
    "$$\n",
    "が成立します．ここで，$U_N=\\sum_{n=0}^N(I-Q)^n$としましょう．このとき，任意の$N>M \\geq N^*$について，\n",
    "$$\n",
    "\\left\\|U_N-U_M\\right\\|=\\left\\|\\sum_{n=M+1}^N(I-Q)^n\\right\\| \\leq \\sum_{n=M+1}^N\\left\\|(I-Q)^n\\right\\| \\leq \\sum_{n=M+1}^N(b+\\varepsilon)^{\\prime}\n",
    "$$\n",
    "が成り立ちます．よって，$b < 1$なので，$U_N$はコーシー列です．\n",
    "また，$L(V)$はバナッハ空間なので，次を満たす$U^*$が$L(V)$に存在します：\n",
    "\n",
    "$$\n",
    "\\lim_{N\\to \\infty}\\left\\|U_N-U^*\\right\\|=0\n",
    "$$\n",
    "\n",
    "この極限が$Q^{-1}$と同じであることを示しましょう．\n",
    "$$\n",
    "\\left\\|I-Q U_N\\right\\|=\\left\\|I-\\left[I-(I-Q)^{N+1}\\right]\\right\\| \\leq\\left\\|(I-Q)^{N+1}\\right\\|\n",
    "$$\n",
    "なので，\n",
    "$\\left\\|(I-Q)^n\\right\\|<(b+\\varepsilon)^n$から，\n",
    "$$\n",
    "\\left\\|I-Q U^*\\right\\|=\\lim _{N \\rightarrow \\infty}\\left\\|I-Q U_N\\right\\|=0\n",
    "$$\n",
    "が成り立ちます．同じように，$\\left\\|I-U^* Q\\right\\|=0$です．よって，$U=Q^*$です．\n",
    "\n",
    "---\n",
    "\n",
    "また，$\\sigma(Q) \\leq\\|Q\\|$であるから，$\\sigma(Q)$であれば，$(I-Q)^{-1}$は存在します．\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}