Вычислительная сложность алгоритма ортогонализации Грэма-Шмидта

Question

Какова вычислительная сложность алгоритма ортогонализации Грам-Шмидта?

Предположим, что матрица из m строк и k столбцов, сколько операций требуется для вычисления ортогонализации?

Если возможно, я хотел бы иметь точное количество умножений и дополнений.

EDIT: Мне кажется, что общее количество операций (умножение + добавление) равно 3/2k^2m + 3/2mk +k^2/2 +k/2.
Я хотел бы знать, если это правильно, и если есть более быстрая версия.

Answer 1

Продукт Dot принимает m-1 дополнений и m умножает.

Вектор нормализации занимает 1 вектор квадрат (точка продукта), 1 квадратного корня и м делений т.е.

m-1 +, m *, m /, 1 √ 

Вычитание вектора проекции занимает 1 скалярное произведение, м умножает и м дополнения, т.е.

2m-1 +, 2m * 

Вычисления -го вектора принимает (J-1) вычитания выступов, за которыми следует нормализации, т.е.

(2m-1)(j-1)+m-1 +, 2m(j-1)+m *, m /, 1 √ 

Вы вычислить векторы из J = 1 к, так факторов (J-1) стать треугольное число (K-1) к/2 и условия, не зависящие от J умножаются на к:

(2m-1)(k-1)k/2+(m-1)k +, 2m(k-1)k/2+mk *, mk /, k √ 

В продукте точки, в м подразделение может быть обменено на м размножаются инверсией, получая

(2m-1)(k-1)k/2+(m-1)k +, 2m(k-1)k/2+2mk *, k /, k √ 

Так по существу 2mk² операции.

Answer 2

Общая сложность алгоритма Гр-Шмидт представляет собой О (тк^2):

Этого процесс должен быть применен к раз и каждому ортогонализация занимает O (Mk) операции (умножения и сложения), так вообще она делает вывод (mk^2) сложность