julia - 基于列的反向替换函数的数学失败计数(Julia)

Question

我是线性代数的新手，正在学习用 Julia lang 实现的三角系统。我有一个col_bs() 函数 我将在此处展示我需要对 flop 进行数学计算。它不一定是 super 技术，这是为了学习目的。我试图将函数分解为内部 i 循环和外部 j 循环。中间是每个 FLOP 的计数，我认为这是无用的，因为常量通常都会被丢弃。

我也知道答案应该是 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$，就像其余的一样我相信我们的三角系统)

Answer 1

将您的代码简化为这种形式:

for j = n:-1:2
   ...
   for i = 1:j-1
      ... do k FLOPs
   end
end

内循环取k*(j-1)拖鞋。因此，外循环的成本是

既然你知道 j <= n ，你知道这个总和小于 (n-1)^2这对大 O 来说已经足够了。

不过其实你应该也能想通