алгебра - Разложение матрицы вида $%A = B B^T$%

Алгоритмов здесь довольно много, поэтому я опишу какой-нибудь самый простой, для которого легко обосновывается корректность.

Пусть дана положительно определённая квадратная матрица $%A$% порядка $%n$%. Она задаёт структуру скалярного произведения на $%{\mathbb R}^n$% по правилу $%(x,y)=x^TAy$%, где $%x,y$% -- векторы-столбцы. В частности, $%(e_i,e_j)=a_{ij}$%, то есть скалярное произведение двух единичных векторов равно соответствующему матричному элементу.

Идея состоит в том, чтобы применить процесс ортогонализации Грама -- Шмидта и преобразовать базис $%e_1$%, ..., $%e_n$% в ортонормированный (относительно скалярного произведения, задаваемого матрицей $%A$%). Это хорошо известный алгоритм, который можно описать в общем виде.

Итак, пусть дано $%n$%-мерное векторное пространство $%V$% с базисом $%v_1$%, ..., $%v_n$%, и пусть на $%V$% задана структура евклидова пространства, то есть определено скалярное произведение $%(\cdot,\cdot)$%. Построим ортогональный базис $%w_1$%, ..., $%w_n$% следующим образом.

Сначала полагаем $%w_1=v_1$%. Далее ищем следующий вектор в виде $%w_2=v_2+aw_1$% с неопределённым коэффициентом $%a$%. Нам нужно, чтобы вектор $%w_2$% был ортогонален $%w_1$%, то есть $%(w_1,w_2)=0$%. Этому условию удовлетворяет число $%a=-(v_2,w_1)/(w_1,w_1)$%. Скалярное произведение мы находить умеем, поэтому вектор $%w_2$% нам теперь известен. При вычислениях на практике, работая с целыми числами, мы можем избегать появления дробей, домножая векторы на подходящие коэффициенты. Свойство ортогональности базиса от этого не меняется.

На следующем шаге находим вектор $%w_3=v_3+bw_1+cw_2$% с неопределёнными коэффициентами $%b,c$%. От этого вектора требуется, чтобы он был ортогонален как $%w_1$%, так и $%w_2$%. Это приводит к двум уравнениям: $%(w_1,w_3)=0$% и $%(w_2,w_3)=0$%. Из первого уравнения находится $%b$% по формуле $%b=-(w_1,v_3)/(w_1,w_1)$%, а из второго находим $%c=-(w_2,v_3)/(w_2,w_2)$%. Здесь надо заметить, что слагаемые типа $%(w_1,w_2)$% и $%(w_2,w_1)$% исчезают, так как они равны нулю в силу ортогональности системы.

Дальше процесс устроен аналогично, то есть $%w_4$% ищем как сумму $%v_4$% и линейной комбинации уже построенных векторов $%w_1$%, $%w_2$%, $%w_3$% с неопределёнными коэффициентами, которые находятся из соображений ортогональности по аналогичным простым формулам.

Теперь, когда система $%w_1$%, ..., $%w_n$% построена, то надо каждый из векторов $%w_i$% разделить на его длину, то есть на $%\sqrt{(w_i,w_i)}$%. Это даст ортонормированную систему $%w_1'$%, ..., $%w_n'$%.

Теперь надо найти матрицу линейного преобразования, которое выражает векторы одного базиса через векторы другого. В данном случае нам нужно знать, как векторы старого базиса, то есть $%e_1$%, ..., $%e_n$%, выражаются через векторы нового базиса $%w_1'$%, ..., $%w_n'$%. Получить эти формулы можно, прослеживая ход преобразований на каждом из шагов, и подставляя одни выражения в другие. Можно также на каждом из шагов запоминать матрицы преобразований (они имеют простой вид), а затем их перемножить в нужном порядке.

Так или иначе, мы здесь получаем матрицу $%C$% такую, что $%(w_1',\ldots,w_n')C=(e_1,\ldots,e_n)$% в формально-символической записи. Это означает, что в столбцы матрицы $%C$% мы записали координаты векторов старого базиса в новом базисе. Отсюда следует, что $%A=C^TC$%, так как скалярные произведения векторов ортонормированного базиса находятся умножением строки на столбец. Поэтому, с одной стороны, произведение $%(e_i,e_j)$% было равно $%a_{ij}$%, а с другой, оно же равно произведению $%i$%-й строки $%C^T$% на $%j$%-й столбец $%C$%. Это приводит к соответствующему матричному равенству.

В качестве упражнения для отработки можно сделать следующее: взять какую-то невырожденную матрицу $%B$% (например, из элементов $%1$%, $%2$%, $%3$%, $%4$%) и положить $%A=B^TB$%. Далее сделать всё то, что описано выше. Алгоритм здесь однозначен, и он должен привести к ответу, состоящему из матрицы $%C$%, элементы которой равны $%\sqrt{5}, 11/\sqrt{5}, 0, 2/\sqrt{5}$% (я называю их подряд, чтобы не писать здесь матрицу). Легко проверяется, что $%C^TC=A$% -- при том, что $%C$% вовсе не равно $%B$%. Последнее говорит о том, что таких матриц в принципе может быть много, но здесь ставилась задача указать алгоритм нахождения какой-то из них (с обоснованием).