Soy nuevo en el Álgebra Lineal y el aprendizaje acerca de triangular los sistemas implementados en Julia lang. Tengo un col_bs() función que voy a mostrar aquí que tengo que hacer un matemático flop conde de. No tiene que ser super técnico, esto es con fines de aprendizaje. Traté de romper la función hacia abajo en su interior me bucle y exterior j bucle. En medio hay un recuento de cada FLOP , que supongo que es inútil, ya que las constantes son generalmente abandonado de todos modos.
También sé que la respuesta debe ser N^2, ya que es una versión invertida de la sustitución hacia adelante algoritmo, el cual es N^2 flops. He intentado mi mejor para derivar este N^2 recuento, pero cuando he intentado terminé con un extraño Nj contar. Voy a intentar dar todo el trabajo que he hecho! Gracias a cualquier persona que le ayuda.
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
$$
Lo cual significa que, si hacemos caso de las constantes de la más alta posibilidad de flops para esta fórmula sería de $n$ ( que puede ser un indicio de cuál es incorrecto con mi función, ya que debe ser $n^2$ al igual que el resto de nuestros triangular sistemas creo)
