Изогонализация


Алгоритм Грама-Шмидта получает на вход множество линейно независимых векторов $ \left\{ v_{1},v_{2},\ldots,v_{n} \right\} $ с заданным скалярным произведением и последовательно, один за другим генерирует векторы $ q_{i} $, образующие множество ортогональных векторов $ \left\{ q_{1},q_{2},\ldots,q_{n} \right\} $. Алгоритм ГШ используется в нескольких приложениях, таких как метод наименьших квадратов и проблема собственных значений. На шаге $ k+1 $ классического алгоритма ГШ ортонормированный вектор $ q_{k+1} $ определяется как

$$ q_{k+1}=\left\Vert v_{k+1}-\sum_{i=1}^{k}\mathrm{proj}_{q_{i}}v_{k+1}\right\Vert _{2}^{-1}\left(v_{k+1}-\sum_{i=1}^{k}\mathrm{proj}_{q_{i}}v_{k+1}\right), $$

где $ \mathrm{proj}_{q_{i}}v_{k+1}=\langle v_{k+1},q_{i}\rangle q_{i} $ есть проекция $ v_{k+1} $ на ранее построенный вектор $ q_{i} $.

Пусть $ S=\left[s_{1},s_{2},\ldots,s_{n}\right] $ — матрица, составленная из единичных векторов, таких что угол между любыми двумя из них равен $ \theta $. Тогда, для $ i\neq j $, $ \left\langle s_{i}^{T},s_{j} \right\rangle =\left[S^{T}S\right]_{ij}=\cos\theta $. Ниже предлагается алгоритм преобразования множества линейно независимых векторов $ \left\{ v_{1},v_{2},\ldots,v_{n}\right\} $ любого пространства со скалярным произведением в изогональную систему единичных векторов $ \left\{ s_{1},s_{2},\ldots,s_{n}\right\} $ с острым углом $ \theta $ между любыми двумя из них.


Алгоритм 1. Изогонализация


Вход: Множество линейно независимых векторов $\left\{ v_{1},v_{2},\ldots,v_{n}\right\}$, угол $ \theta\in\left(0,\frac{\pi}{2}\right] $.

Выход: Множество изогональных векторов $\left\{ s_{1},s_{2},\ldots,s_{n}\right\} $.


  1. $ s_{1}=\frac{v_{1}}{\left\Vert v_{1}\right\Vert },\;p=0,\;r=0 ; $
  2. for $ \;k=2,3,\ldots,n\; $ do
  3. $ \qquad p=p+s_{k-1};\;u=\frac{p}{\left\Vert p\right\Vert } ; $
  4. $ \qquad q=\frac{v_{k}-\left(\left\langle v_{k},u\right\rangle +r\right)}{\left\Vert v_{k}-\left(\left\langle v_{k},u\right\rangle +r\right)\right\Vert } ; $
  5. $ \qquad w=q+\sqrt{\frac{k-1}{\left(\sec\theta-1\right)\left(\sec\theta+k-1\right)}}\cdot u ; $
  6. $ \qquad s_{k}=\frac{w}{\left\Vert w\right\Vert } ; $
  7. $ \qquad $ if $ \;k<n $
  8. $ \qquad\qquad r=0 ; $
  9. $ \qquad\qquad B_{k-1}=\sum_{j=1}^{k-1}s_{j}-\left(k-1\right)s_{k} ; $
  10. $ \qquad\qquad $ for $ \;i=1,2,\ldots,k-1\; $ do
  11. $ \qquad\qquad\qquad r=r+\frac{\left\langle v_{k+1},B_{i}\right\rangle }{\left\Vert B_{i}\right\Vert ^{2}}B_{i} ; $
  12. $ \qquad\qquad $ end for
  13. $ \qquad $ end if
  14. end for

Пусть, например, $ \theta=\frac{\pi}{3} $, тогда для векторов $$ v_{1}=\left\{ 1,1,1,1\right\} , $$ $$ v_{2}=\left\{ 1,2,4,8\right\} , $$ $$ v_{3}=\left\{ 1,3,9,27\right\} , $$ $$ v_{4}=\left\{1,4,16,64\right\} $$ получаем: $$ s_{1}=\left\{ 0.5,0.5,0.5,0.5\right\} , $$ $$ s_{2}=\left\{ -0.19417,-0.03265,0.29038,0.93644\right\} , $$ $$ s_{3}=\left\{ 0.55019,0.04099,-0.34878,0.7576\right\} , $$ $$ s_{4}=\left\{ -0.12655,0.75144,-0.23016,0.60527\right\} .$$ Легко проверить, что $ \left\langle s_{i},s_{j}\right\rangle=\cos\theta=0.5,\;i\neq j $ .

Для пространства функций $$ v_{1}=t^{0},\:v_{2}=t^{1},\:v_{3}=t^{2},\:v_{4}=t^{3},\ldots $$ со скалярным произведением $$ \left\langle a\left(t\right),b\left(t\right)\right\rangle =\int_{-1}^{1}a\left(t\right)b\left(t\right)dt $$ изогональная система функций с параметром $ \theta=\frac{\pi}{3} $ следующая: $$ s_{1}=\frac{1}{\sqrt{2}} , $$ $$ s_{2}=\frac{3}{2 \sqrt{2}}t+\frac{1}{2 \sqrt{2}} , $$ $$ s_{3}=\frac{\sqrt{15}}{2}t^2+\frac{1}{2 \sqrt{2}}t+\frac{\sqrt{6}-2 \sqrt{5}}{4 \sqrt{3}} , $$ $$ s_{4}=\frac{5 \sqrt{35}}{8}t^3+\frac{\sqrt{15}}{8}t^2+\frac{1}{24} \left(6 \sqrt{2}-9 \sqrt{35}\right) t+\frac{1}{24} \left(6 \sqrt{2}-\sqrt{15}\right) , $$ $$ \ldots $$ Проверка изогональности дает $ \left\langle s_{i},s_{j}\right\rangle=\cos\theta=\frac{1}{2},\;i\neq j $.

Если параметр $ \theta=\frac{\pi}{2} $, то для любой системы линейно независимых векторов Алгоритм 1 выдает соответствующую ортонормированную систему.


09.01.2016