О скорости сходимости

[kisupov]

Имеется два итерационных процесса: $y_i=f(y_{i-1})$ и $z_i=g(z_{i-1})$. Результатом обоих является некое число $c$. Первый требует выполнения $n$ элементарных арифметических операций для результативного завершения, второй - $m$ операций, причем $n = 3m$. Как правильно сказать:

- скорость сходимости процесса $z_i=g(z_{i-1})$ выше в 3 раза, чем скорость сходимости процесса $y_i=f(y_{i-1})$
или
- процесс $z_i=g(z_{i-1})$ сходится в 3 раза быстрее, чем $y_i=f(y_{i-1})$

И можно ли вообще сопоставлять скорость сходимости двух процессов по числу элементарных операций?

[мат-ламер]

kisupov в сообщении #766191 писал(а):

И можно ли вообще сопоставлять скорость сходимости двух процессов по числу элементарных операций?

А почему бы не сравнивать по количеству итераций? Есть такое понятие, как линейная сходимость или сходимость со скоростью геометрической прогрессии с показателем $q$. Можно сравнивать эти показатели.

[ewert]

kisupov в сообщении #766191 писал(а):

И можно ли вообще сопоставлять скорость сходимости двух процессов по числу элементарных операций?

Нельзя. Т.е. можно, но это уже не будет скоростью в общепринятом понимании. Принято считать, что скорость одного алгоритма выше скорости другого, если для его реализации требуется много меньше операций при условии, что объём задачи неограниченно возрастает. Для любого конечного объёма соотношение, разумеется, запросто может оказаться и противоположным.

[kisupov]

В оценках $m$ и $n$ уже заложено кол-во итераций, т.е. они имеют вид: $m=q_1 \cdot t_1$, $n = q_2 \cdot t_2$, где $q_1$ и $q_2$ --- количество итераций первого и второго процессов, а $t_1$ и $t_2$ --- количество операций на каждой итерации.


При этом $m$ и $n$ могут быть сколь угодно большими (в зависимости от условий задачи), но соотношение $n = 3m$ сохраняется. В таком случае корректно будет сказать, что второй процесс сходится в 3 раза быстрее первого (в общепринятом смысле)? Или все же нужно оценивать погрешности приближений (как тут: http://ru.wikipedia.org/wiki/%D0%A1%D0% ... 1%82%D0%B8)?

[мат-ламер]

kisupov в сообщении #766371 писал(а):

В таком случае корректно будет сказать, что второй процесс сходится в 3 раза быстрее первого (в общепринятом смысле)?

Я думаю, что да.