簡単で高速なベクトルの正規直交化

簡単で高速なベクトルの正規直交化

グラム・シュミットの正規直交化法で十分じゃないか（内積の計算は非常に簡単にできる為）
と思うだろうが、実は正規直交化されたベクトル同士の内積の計算が簡単なだけで、コサインが分からないと計算できないし、何かと不便。
もっと高速に行うにはどうしたらよいか？

注意

直交化してから正規化するのは簡単なので、直交化する方法だけを論じる。

従来の方法

グラム・シュミットの正規直交化を使う。

新しい方法

直角にする方法

ベクトル$\boldsymbol{a}$と$\boldsymbol{b}$を直角にする場合、スカラー$k$を用いた$k\boldsymbol{b}$を$\boldsymbol{a}$に加える（$\boldsymbol{a}$がマイナスでもよい場合単純な加算になる）ことになる。
$\boldsymbol{a}\cdot (\boldsymbol{b}+k\boldsymbol{a})=0$
になるようなkを適当に探す。

平面の場合

角度を直角にする。

3次元の場合

角度を直角にし、その平面からもう一つのベクトルを直角にする。

一般

二つの方法がある。

1つ目

　一つずつ一つの平面に対して直角なベクトルを生やす。
　つまり、全ての平面に対して直角でなければならない。
　それでも計算量は大したことがない筈だ。

2つ目

　とにかく二つのベクトルの組を平面と見なして直角にし、その平面同士を直角にする為に回転させる。
　回転の方が計算量が少ないのでこちらのほうが優秀。
　どうしても計算が面倒なら、ある程度の所まで遺伝的アルゴリズムを用いることも考えられる。
　つまり、直角に近い角度で生えているベクトル同士を素早く直交させ、直行したベクトルの塊をどんどん作る。
　　
　また遺伝的アルゴリズムか。 　

2つ目の方法について

この方法のほうが速いことがお分かりだろうか？
重要なことは、平面同士を直交させる前も、直交させて新たに正規直交基底となるベクトルの組を作った後も、その基底の組または平面は、原点に対して必ず一通りにしか存在できない訳ではないことだ。
実は、最終的に正規直交基底を作った後で、全てのベクトルを同じ角度だけ同時に回転させることで、無限個の正規直交基底のコピーを作れる。
だから、直交させる際に適当に両方の平面を回転させることで、より素早い正規直交基底（正規直交系）の生成が可能なのである。
ここがムチャクチャ大事で、初めに作った平面を絶対に動かさないようなアルゴリズムでも解けるとは言え、解くのが遅くなってしまう。
しかも、解いてから（全てのベクトルを直交させて正規直交基底を作って、つまり完成させてから）任意の角度回転させることができるので、解く時に回転させないで解くのは何の意味もメリットもない。そこに注意すべし。