Помогите опознать алгоритм Опции

[ataradov]

Помогите опознать алгоритм пожалуйста.

Для размерности 3 выглядит вот так:

CODE

      a0[0] = a[1] * a[2];
      a0[1] = b[1] * a[2] + a[1] * b[2];
      a0[2] = b[1] * b[2];

      a0[0] += a[0] * a[2];
      a0[1] += b[0] * a[2] + a[0] * b[2];
      a0[2] += b[0] * b[2];

      a0[0] += a[0] * a[1];
      a0[1] += b[0] * a[1] + a[0] * b[1];
      a0[2] += b[0] * b[1];

a, b - исходные векторы размерности 3, a0 - результат.

В коде видны явные закономерности, похоже на какую-то стандартную операцию над векторами, но не могу понять какую именно.

[ataradov]

Вот более полный код, для N=3 эквивалентен вышеприведеному, за исключением посленей части:

CODE

  for (int k = 0; k < N; k++)
  {
    a1[0] = 1.0; a1[1] = a1[2] = a1[3] = 0.0;

    for (int j = 0; j < N; j++)
    {
      if (j == k)
        continue;

      a1_old = 0.0;
      for (int i = 0; i < N+1; i++)
      {
        t = a1[i] * a[j] + a1_old * b[j];
        a1_old = a1[i];
        a1[i] = t;
      }
    }

    for (int i = 0; i < N+1; i++)
      a0[i] += a1[i];
  }

  a1_old = 0.0;
  for (int i = 0; i < N+1; i++)
  {
    t = a1[i] * a[N-2] + a1_old * b[N-1];
    a1_old = a1[i];
    a1[i] = t;
  }

Это кусок мат. модели, векторы a и b вычисляются из физических параметров системы.

После этого из массивов а0 и a1 формируются коэфициенты полинома (комплексные):

CODE

  for (int i = 0; i < N+1; i++)
  {
    c[i].real= t0 * a1[i];
    c[i].imag = t1 * a1[i];

    if (i > 0)
      c[i].imag -= a0[i-1];
  }

t0 и t1 - тоже вычисляются из параметров, представляют собой выражения вида t0 = A * sin(W), t1 = A * cos(W).

После этого находятся корни полинома, и они используются дальше в модели.

Сообщение отредактировал Taradov Alexander - Oct 10 2011, 12:14

[iiv]

a1 инициализирован только в первых 4 элементах. А дальше, в общем случае, тоже нули или модель просто не гоняли? Циклы в общем случае по i,j,k всегда до одного и того же N бегут? С виду очень походе на линейное предсказание с преобразованием исходных реальных векторов в комплексные, но и на сто процентов сказать не могу, если есть еще какая-то информация об алгоритме, говорите!

[ataradov]

a1 инициализирован только в первых 4 элементах. А дальше, в общем случае, тоже нули или модель просто не гоняли?

Да, нули. Но в жизни он будет использоваться только с 2 и 3 элементами.

Циклы в общем случае по i,j,k всегда до одного и того же N бегут? С виду очень походе на линейное предсказание с преобразованием исходных реальных векторов в комплексные, но и на сто процентов сказать не могу, если есть еще какая-то информация об алгоритме, говорите!

Да, до одного (иногда до N, иногда до N+1).

Это куски мат. модели колеблющейся струны. Но это не физическая модель, а имитация, возможно имеющая какие-то корни в физике.

Вот код инициализации a[] и b[]:

CODE

  avg = 0.0;
  for (int i = 0; i < N; i++)
    avg += arr[i];
  avg = avg / N;

  a[N] = b[N] = 0.0;
  for (int i = 0; i < N; i++)
  {
    a[i] = (2.0 - arr[i] / avg) / (2.0 * avg);
    b[i] = (1.0 - arr[i] / avg) * overtone * M_PI;
  }

Тут arr[] - массив немного отличающихся частот, имитация 3 немного расстоенных струн в хоре одной клавиши, похоже. overtone - номер текущего обертона.

На выходе (после нахождения корней полинома) получается 3 комплексных числа, действительная часть которых деленная на 2*pi равна "настоящему" (тому что используется непостредственно при синтезе) смещению частоты от центральной (частоты ноты), а мнимая - напрямую скорости затухания струны (показателю экспоненты).

Массив arr[] получается путем сравнительно сложных табличных преобразований, но это не важно, можно просто считать, что он содержит числа примерно равные частоте струн данной ноты, с небольшой расстройкой. Расстройка растет с номером гармоники, на выходе получается похожая расстройка (тоже растет с номером гармоники), но большая по абсолютной величине.

PS: Вообще похоже, что это оптимизация какой-то очень простой операции (типа свертки, реализуемой через Фурье), так как вся остальная модель примитивна, а тут прямо обилие новых алгоритмов. Корни полинома с комплексными коэффициентами ищутся через QR-разложение, которое тоже не сахар.
Но результат - напрямую частоты и экспоненты, говорит о том, что используются какие-то свойства этого полинома и его корней.

PPS: В худшем случае я просто выкину все эти пробразования, заменив их на таблицы/аппроксимации, но интересно будет понять что-же тут происходит, может когда пригодится еще.

Сообщение отредактировал Taradov Alexander - Oct 10 2011, 15:43