Created
April 23, 2019 17:09
-
-
Save shotahorii/ad667f70ac59a3893057dc01df192bbb to your computer and use it in GitHub Desktop.
Gram Schmidt Process
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
{ | |
"cells": [ | |
{ | |
"cell_type": "markdown", | |
"metadata": {}, | |
"source": [ | |
"### Gram-Schmidt Process\n", | |
"- 「これなら分かる最適化数学」(金谷健一) p28-29\n", | |
"- [グラムシュミットの直交化法の意味と具体例](https://mathtrain.jp/gramschmidt)\n", | |
"- [正射影ベクトルの公式の証明と使い方](https://mathtrain.jp/projection)\n", | |
"\n", | |
"**どんな時に使う?** \n", | |
"ある線形独立なベクトルがn個与えられているとする。ただし、これらは単に線形独立であることがわかっているだけで、特に直交しているわけではない。ここで、これらの線形独立なベクトルを用いて直交するベクトルn個を得たい場合に使える。 " | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 42, | |
"metadata": { | |
"collapsed": false | |
}, | |
"outputs": [ | |
{ | |
"data": { | |
"text/latex": [ | |
"ここで、ベクトル$${\\bf x}_1,{\\bf x}_2,...,{\\bf x}_n$$が線形独立(一次独立)であるとは、どの$${\\bf x}_i\n", | |
"$$も他の$$n-1$$個の$${\\bf x}_j$$ where ($$j \\neq i$$)の線形結合で表すことができないということ。" | |
], | |
"text/plain": [ | |
"<IPython.core.display.Latex object>" | |
] | |
}, | |
"metadata": {}, | |
"output_type": "display_data" | |
} | |
], | |
"source": [ | |
"%%latex\n", | |
"ここで、ベクトル$${\\bf x}_1,{\\bf x}_2,...,{\\bf x}_n$$が線形独立(一次独立)であるとは、どの$${\\bf x}_i\n", | |
"$$も他の$$n-1$$個の$${\\bf x}_j$$ where ($$j \\neq i$$)の線形結合で表すことができないということ。" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 27, | |
"metadata": { | |
"collapsed": false | |
}, | |
"outputs": [ | |
{ | |
"data": { | |
"text/latex": [ | |
"今、線形独立なベクトルの列$${\\bf u}_1,{\\bf u}_2,...{\\bf u}_n$$が与えられたとして、これらの線形結合によって直交系\n", | |
"$${\\bf e}_1,{\\bf e}_2,...{\\bf e}_n$$を作り出したい。\n", | |
"<br><br>\n", | |
"-----<br>\n", | |
"ちなみに、ここではグラムシュミットの「直交化」だけを行う。各$${\\bf e}_i$$を単位ベクトルに正規化することで\n", | |
"正規直交系とすることができるが、(正規化の部分は単純で後から手でやれば全く問題ないので)ここでは説明に含めない。\n", | |
"正規化と直交化の手続きをまとめてグラムシュミットの正規直交化として紹介している書籍(はじパタp136)やサイトも多い。\n", | |
"<br>-----" | |
], | |
"text/plain": [ | |
"<IPython.core.display.Latex object>" | |
] | |
}, | |
"metadata": {}, | |
"output_type": "display_data" | |
} | |
], | |
"source": [ | |
"%%latex\n", | |
"今、線形独立なベクトルの列$${\\bf u}_1,{\\bf u}_2,...{\\bf u}_n$$が与えられたとして、これらの線形結合によって直交系\n", | |
"$${\\bf e}_1,{\\bf e}_2,...{\\bf e}_n$$を作り出したい。\n", | |
"<br><br>\n", | |
"-----<br>\n", | |
"ちなみに、ここではグラムシュミットの「直交化」だけを行う。各$${\\bf e}_i$$を単位ベクトルに正規化することで\n", | |
"正規直交系とすることができるが、(正規化の部分は単純で後から手でやれば全く問題ないので)ここでは説明に含めない。\n", | |
"正規化と直交化の手続きをまとめてグラムシュミットの正規直交化として紹介している書籍(はじパタp136)やサイトも多い。\n", | |
"<br>-----" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 33, | |
"metadata": { | |
"collapsed": false | |
}, | |
"outputs": [ | |
{ | |
"data": { | |
"text/latex": [ | |
"さて、まず直交系の最初のベクトル$${\\bf e}_1$$であるが、\n", | |
"この時点ではまだ直交すべき他のベクトルが何も定まっていない状態なので、単純に$${\\bf e}_1 = {\\bf u}_1$$と置く。\n", | |
"<br>\n", | |
"$${\\bf e}_2$$以降のベクトルについては一般化して以下のように求めることができる。\n", | |
"<br><br>\n", | |
"$${\\bf e}_1,{\\bf e}_2,...,{\\bf e}_k$$まで直交系ができたとき、$${\\bf e}_{k+1}$$を以下の形にとる。\n", | |
"<br><br>\n", | |
"$${\\bf e}_{k+1} = {\\bf u}_{k+1} - c_1{\\bf e}_1 - c_2{\\bf e}_2 - ... - c_k{\\bf e}_k$$\n", | |
"<br><br>\n", | |
"そして、$$c_1,c_2,...,c_k$$を$${\\bf e}_{k+1}$$が$${\\bf e}_1,{\\bf e}_2,...,{\\bf e}_k\n", | |
"$$に直交するように定める。つまり、各$${\\bf e}_i$$に対して$$({\\bf e}_i,{\\bf e}_{k+1})=0\n", | |
"$$となるような$$c_1,c_2,...,c_k$$である。<br>\n", | |
"ここで、<br><br>\n", | |
"$$({\\bf e}_i,{\\bf e}_{k+1}) = ({\\bf e}_i,{\\bf u}_{k+1} - c_1{\\bf e}_1 - c_2{\\bf e}_2 - \n", | |
" ... - c_k{\\bf e}_k)$$<br>\n", | |
"$$=({\\bf e}_i,{\\bf u}_{k+1})-c_1({\\bf e}_i,{\\bf e}_1)-c_2({\\bf e}_i,{\\bf e}_2) - \n", | |
"... -c_k({\\bf e}_i,{\\bf e}_k)$$\n", | |
"<br><br>\n", | |
"ここで、$${\\bf e}_1,{\\bf e}_2,...,{\\bf e}_k$$まではすでに直交系であるので、\n", | |
"$$({\\bf e}_i,{\\bf e}_1),({\\bf e}_i,{\\bf e}_2),...,({\\bf e}_i,{\\bf e}_k)\n", | |
"$$は、$$({\\bf e}_i,{\\bf e}_i)$$を除き全て$$0$$である。また、$$({\\bf e}_i,{\\bf e}_i)=||{\\bf e}_i||^2\n", | |
"$$であるので、上の式は以下のようになる。\n", | |
"<br><br>\n", | |
"$$({\\bf e}_i,{\\bf e}_{k+1}) = ({\\bf e}_i,{\\bf u}_{k+1}) - c_i||{\\bf e}_i||^2$$\n", | |
"<br>\n", | |
"すなわち、\n", | |
"<br>\n", | |
"$$c_i = \\frac{({\\bf e}_i,{\\bf u}_{k+1})}{||{\\bf e}_i||^2}$$\n", | |
"<br><br>\n", | |
"つまり、$${\\bf e}_{k+1}$$は以下のように定まる。\n", | |
"<br><br>\n", | |
"$${\\bf e}_{k+1} = {\\bf u}_{k+1} - c_1{\\bf e}_1 - c_2{\\bf e}_2 - ... - c_k{\\bf e}_k$$<br>\n", | |
"$${\\bf e}_{k+1} = {\\bf u}_{k+1} - \\frac{({\\bf e}_1,{\\bf u}_{k+1})}{||{\\bf e}_1||^2}{\\bf e}_1\n", | |
"- \\frac{({\\bf e}_2,{\\bf u}_{k+1})}{||{\\bf e}_2||^2}{\\bf e}_2\n", | |
"- ...\n", | |
"- \\frac{({\\bf e}_k,{\\bf u}_{k+1})}{||{\\bf e}_k||^2}{\\bf e}_k$$\n", | |
"<br><br>\n", | |
"この操作を$$k=1,2,3,...$$と順番に行う。" | |
], | |
"text/plain": [ | |
"<IPython.core.display.Latex object>" | |
] | |
}, | |
"metadata": {}, | |
"output_type": "display_data" | |
} | |
], | |
"source": [ | |
"%%latex\n", | |
"さて、まず直交系の最初のベクトル$${\\bf e}_1$$であるが、\n", | |
"この時点ではまだ直交すべき他のベクトルが何も定まっていない状態なので、単純に$${\\bf e}_1 = {\\bf u}_1$$と置く。\n", | |
"<br>\n", | |
"$${\\bf e}_2$$以降のベクトルについては一般化して以下のように求めることができる。\n", | |
"<br><br>\n", | |
"$${\\bf e}_1,{\\bf e}_2,...,{\\bf e}_k$$まで直交系ができたとき、$${\\bf e}_{k+1}$$を以下の形にとる。\n", | |
"<br><br>\n", | |
"$${\\bf e}_{k+1} = {\\bf u}_{k+1} - c_1{\\bf e}_1 - c_2{\\bf e}_2 - ... - c_k{\\bf e}_k$$\n", | |
"<br><br>\n", | |
"そして、$$c_1,c_2,...,c_k$$を$${\\bf e}_{k+1}$$が$${\\bf e}_1,{\\bf e}_2,...,{\\bf e}_k\n", | |
"$$に直交するように定める。つまり、各$${\\bf e}_i$$に対して$$({\\bf e}_i,{\\bf e}_{k+1})=0\n", | |
"$$となるような$$c_1,c_2,...,c_k$$である。<br>\n", | |
"ここで、<br><br>\n", | |
"$$({\\bf e}_i,{\\bf e}_{k+1}) = ({\\bf e}_i,{\\bf u}_{k+1} - c_1{\\bf e}_1 - c_2{\\bf e}_2 - \n", | |
" ... - c_k{\\bf e}_k)$$<br>\n", | |
"$$=({\\bf e}_i,{\\bf u}_{k+1})-c_1({\\bf e}_i,{\\bf e}_1)-c_2({\\bf e}_i,{\\bf e}_2) - \n", | |
"... -c_k({\\bf e}_i,{\\bf e}_k)$$\n", | |
"<br><br>\n", | |
"ここで、$${\\bf e}_1,{\\bf e}_2,...,{\\bf e}_k$$まではすでに直交系であるので、\n", | |
"$$({\\bf e}_i,{\\bf e}_1),({\\bf e}_i,{\\bf e}_2),...,({\\bf e}_i,{\\bf e}_k)\n", | |
"$$は、$$({\\bf e}_i,{\\bf e}_i)$$を除き全て$$0$$である。また、$$({\\bf e}_i,{\\bf e}_i)=||{\\bf e}_i||^2\n", | |
"$$であるので、上の式は以下のようになる。\n", | |
"<br><br>\n", | |
"$$({\\bf e}_i,{\\bf e}_{k+1}) = ({\\bf e}_i,{\\bf u}_{k+1}) - c_i||{\\bf e}_i||^2$$\n", | |
"<br>\n", | |
"すなわち、\n", | |
"<br>\n", | |
"$$c_i = \\frac{({\\bf e}_i,{\\bf u}_{k+1})}{||{\\bf e}_i||^2}$$\n", | |
"<br><br>\n", | |
"つまり、$${\\bf e}_{k+1}$$は以下のように定まる。\n", | |
"<br><br>\n", | |
"$${\\bf e}_{k+1} = {\\bf u}_{k+1} - c_1{\\bf e}_1 - c_2{\\bf e}_2 - ... - c_k{\\bf e}_k$$<br>\n", | |
"$${\\bf e}_{k+1} = {\\bf u}_{k+1} - \\frac{({\\bf e}_1,{\\bf u}_{k+1})}{||{\\bf e}_1||^2}{\\bf e}_1\n", | |
"- \\frac{({\\bf e}_2,{\\bf u}_{k+1})}{||{\\bf e}_2||^2}{\\bf e}_2\n", | |
"- ...\n", | |
"- \\frac{({\\bf e}_k,{\\bf u}_{k+1})}{||{\\bf e}_k||^2}{\\bf e}_k$$\n", | |
"<br><br>\n", | |
"この操作を$$k=1,2,3,...$$と順番に行う。" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 41, | |
"metadata": { | |
"collapsed": false | |
}, | |
"outputs": [ | |
{ | |
"data": { | |
"text/latex": [ | |
"ここで、この式の意味を考えてみる。<br>\n", | |
"この式の意味を理解するための下準備として、以下に正射影ベクトルの公式を記す。\n", | |
"<br><br>\n", | |
"ベクトル$${\\bf b}$$をベクトル$${\\bf a}$$が定める直線に正射影したベクトルは以下のように表される。<br>\n", | |
"$$\\frac{({\\bf a},{\\bf b})}{||{\\bf a}||^2}{\\bf a}$$\n", | |
"<br><br>\n", | |
"つまり、グラムシュミットの直交化法に出てきた<br>\n", | |
"$$\\frac{({\\bf e}_i,{\\bf u}_{k+1})}{||{\\bf e}_i||^2}{\\bf e}_i$$<br>\n", | |
"というのは、$${\\bf u}_{k+1}$$の$${\\bf e}_i$$(が定める直線)への正射影ベクトルである。\n", | |
"<br><br>\n", | |
"グラムシュミットの直交化法の式では、$${\\bf u}_{k+1}$$から、$${\\bf e}_1,...,{\\bf e}_k\n", | |
"$$の正射影ベクトルを引いている。\n", | |
"<br>\n", | |
"これはつまり、$${\\bf u}_{k+1}$$から、$${\\bf e}_1,...,{\\bf e}_k\n", | |
"$$方向の成分を順に除く操作をしていると考えることができる。" | |
], | |
"text/plain": [ | |
"<IPython.core.display.Latex object>" | |
] | |
}, | |
"metadata": {}, | |
"output_type": "display_data" | |
} | |
], | |
"source": [ | |
"%%latex\n", | |
"ここで、この式の意味を考えてみる。<br>\n", | |
"この式の意味を理解するための下準備として、以下に正射影ベクトルの公式を記す。\n", | |
"<br><br>\n", | |
"ベクトル$${\\bf b}$$をベクトル$${\\bf a}$$が定める直線に正射影したベクトルは以下のように表される。<br>\n", | |
"$$\\frac{({\\bf a},{\\bf b})}{||{\\bf a}||^2}{\\bf a}$$\n", | |
"<br><br>\n", | |
"つまり、グラムシュミットの直交化法に出てきた<br>\n", | |
"$$\\frac{({\\bf e}_i,{\\bf u}_{k+1})}{||{\\bf e}_i||^2}{\\bf e}_i$$<br>\n", | |
"というのは、$${\\bf u}_{k+1}$$の$${\\bf e}_i$$(が定める直線)への正射影ベクトルである。\n", | |
"<br><br>\n", | |
"グラムシュミットの直交化法の式では、$${\\bf u}_{k+1}$$から、$${\\bf e}_1,...,{\\bf e}_k\n", | |
"$$の正射影ベクトルを引いている。\n", | |
"<br>\n", | |
"これはつまり、$${\\bf u}_{k+1}$$から、$${\\bf e}_1,...,{\\bf e}_k\n", | |
"$$方向の成分を順に除く操作をしていると考えることができる。" | |
] | |
} | |
], | |
"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.5.2" | |
} | |
}, | |
"nbformat": 4, | |
"nbformat_minor": 0 | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment