Я новичок в линейной алгебре и изучаю треугольные системы, реализованные в Джулии Лэнг. У меня есть функция col_bs (), которую я покажу здесь, для которой мне нужно выполнить математический подсчет флопов. Это не обязательно должно быть супер-техническим, это для учебных целей. Я попытался разбить функцию на внутренний цикл i и внешний цикл j. Между ними идет подсчет каждого ФЛОПА , который, я полагаю, бесполезен, так как константы обычно все равно отбрасываются.
Я также знаю, что ответ должен быть N^2, так как это обратная версия алгоритма прямой замены, которая составляет N^2 провалов. Я изо всех сил старался вывести это количество N^2, но когда я попытался, у меня получилось странное количество Nj. Я постараюсь выполнить всю проделанную мной работу! Спасибо всем, кто помогает.
function col_bs(U, b)
n = length(b)
x = copy(b)
for j = n:-1:2
if U[j,j] == 0
error("Error: Matrix U is singular.")
end
x[j] = x[j]/U[j,j]
for i=1:j-1
x[i] = x[i] - x[j] * U[i , j ]
end
end
x[1] = x[1]/U[1,1]
return x
end
1: To start 2 flops for the addition and multiplication x[i] - x[j] * U[i , j ]
The $i$ loop does: $$ \sum_{i=1}^{j-1} 2$$
2: 1 flop for the division $$ x[j] / = U[j,j] $$
3: Inside the for $j$ loop in total does: $$ 1 + \sum_{i=1}^{j-1} 2$$
4:The $j$ loop itself does:$$\sum_{j=2}^n ( 1 + \sum_{i=1}^{j-1} 2)) $$
5: Then one final flop for $$ x[1] = x[1]/U[1,1].$$
6: Finally we have
$$\\ 1 + (\sum_{j=2}^n ( 1 + \sum_{i=1}^{j-1} 2))) .$$
Which we can now break down.
If we distribute and simplify
$$\\ 1 + (\sum_{j=2}^n + \sum_{j=2}^n \sum_{i=1}^{j-1} 2) .$$
We can look at only the significant variables and ignore constants,
$$\\
\\ 1 + (n + n(j-1))
\\ n + nj - n
\\ nj
$$
Что тогда означает, что если мы проигнорируем константы, то наибольшая вероятность провалов для этой формулы составит $n$ ( что может быть намеком на то, что не так с моей функцией, поскольку она должна быть $n^2$, как и остальные наши треугольные системы, я полагаю)