Число провалов в гауссовом уклоне Matlab code

Мне трудно понять, почему этот код Matlab для выполнения гауссовой элиминации без поворота с использованием LU-факторизации принимает (2/3) * n^3 flops. (FLOPs: операции с плавающей точкой и не САЛЬТО: операции с плавающей запятой в секунду)Число провалов в гауссовом уклоне Matlab code

function x = GaussianElimination(A,b) 

n = length(b); 
for k = 1:n-1 
    for i = k+1:n 
     mult = A(i,k)/A(k,k); 
     A(i,k+1:n) = A(i,k+1:n)-mult*A(k,k+1:n); 
     b(i) = b(i) - mult*b(k); 
    end 
end 

x = zeros(n,1); 
x(n) = b(n)/A(n,n); 

for k = n-1:-1:1 
    x(k) = (b(k) - A(k,k+1:n)*x(k+1:n))/A(k,k); 
end 

end

Если кто-нибудь может объяснить мне, как шлепанцы подсчитываются для тех вложенных циклов, которые начинаются в k+1 я был бы признателен.

PS: Я не говорю об алгоритмической сложности здесь.

источник

2013-10-12 hazer_drum

Вы говорите об алгоритмической сложности? Мое понимание термина «флопы» является аббревиатурой «Операции с плавающей точкой в секунду», как правило, выражается в виде мегафлопсов, гигафлоп, терафлоп и т. Д. Но здесь появляется вопрос о сложности алгоритма, который Я никогда не видел выраженного в «флопе». ??? –

Нет, flops = операции с плавающей запятой. Вот почему это меня путает, потому что это не считается такой же, как алгоритмическая сложность. –

Очевидно, что инструкции по информатике прошли мимо меня, и мои знания больше не полезны. Удачи. –

Я, наконец, понял это сам.

FLOPs считаются немного отличающимися от алгоритмической сложности в том смысле, что члены нижнего порядка по-прежнему игнорируются, но коэффициент перед старшим членом имеет значение.

В этом конкретном примере, поскольку мы игнорируем члены младшего порядка, мы рассматриваем только операции +, -, *, / в тройном вложенном цикле и игнорируем другие операции с плавающей запятой в остальной части алгоритма. т.е. следующая строка

A(i,k+1:n) = A(i,k+1:n)-mult*A(k,k+1:n);

первый цикл выполняется от 1 до п
второй цикл выполняется от к до п
третий контур проходит от к до п (неявного в Matlab кода с использованием :)

Таким образом, эта линия проходит почти n^3 раз и точно n*n + (n-1)*(n-1) + ... + 2*2 + 1*1 раз, что эквивалентно (1/3)*n^3 плюхается при игнорировании нижнего порядка сроки.

Однако эта линия имеет две операции с плавающей запятой: операция - и операция *.

Следовательно, это дает (2/3)*n^3.

источник

2013-10-15 01:13:56

Число провалов в гауссовом уклоне Matlab code

ответ

Смежные вопросы