Существует две разные формы разложения Холецкого:
A = M * ctranspose (M)
и форма ЛПНП
A = L * D * ctranspose (L)
где ctranspose - сложное транспонирование.
Я хочу знать количество операций с плавающей запятой для каждой формы. Википедия ссылается на статью Инверсия матрицы с использованием разложения Холецкого, в которой говорится
При эффективной реализации сложность разложения LDL такая же (sic), что и разложения Холецкого.
В документе говорится, что разложение Холецкого требует n^3/6 + O(n^2) операций. Однако Википедия говорит, что число операций с плавающей запятой равно n^3/3, и мои собственные вычисления получают это также для первой формы. В основном это сводится к сумме чисел треугольника, которая:
n*(n+1)*(n+2)/6.
Вот где, я думаю, газета попадает n^3/6. Но для первой формы член в самой тройной внутренней сумме равен a[i][k]*a[j][k], что по сути является скалярным произведением. В сумме получается 2 * n операций с плавающей запятой. Таким образом, операции с плавающим указателем должны быть n^3/3 + O(n^2). И если вы посмотрите на форму LDL, член в самой внутренней сумме будет a[i][k]*a[j][k]*d[k]. Это 3 * n операций с плавающим указателем (2 умножения и 1 сложение). Таким образом, операции с плавающей запятой должны бытьn^3/2 + O(n^2).
Другими словами, LDL-форме требуется на 50% больше операций с плавающей запятой. Я прав? Я думаю, что статья неправильная (хотя они не определяют, что они имеют в виду под операция). Это важно, потому что я реализую модифицированную форму разложения холекси на основе формы ЛПНП и хочу оценить эффективность своего алгоритма.
Возможно, этот вопрос больше подходит для https://math.stackexchange.com/
