Эту тему, о которой я собираюсь писать, я практически не знаю. Дискретное косинус-преобразование Фурье - это важнейшая тема из "гармонического анализа", потому что на ее основе базируются технологии цифрового спектрального преобразования изображении (jpeg) и звука (mp3), видео (avi), короче говоря, вся мультимедия. В рамках постоянного мультимедийного прогресса ДКП-Ф (Дискр.Косинус-преобр. Фурье) не столько важно, сколько "жизненно" необходимо.
Как обычно, мне лень куда-то глядеть, изучать, лишний раз напрягаться, но, с другой стороны, мне очень хотелось узнать, в чем же секрет этого ДКП-Ф. Как может целый ряд сложиться в прерывистую функцию, если ряд непрерывен? Потому, долго ломая голову, я, наконец, немного понял, но только немного, потому что способ, по которому я разлагал ряд в непрерывность, очень непродуктивен, однако ПОНЯТЬ схему этого ДКП-Ф оказалось просто.
Дана функция
F(x) = a0 + a1*cosx + a2*cos2x + a3*cos3x + ... + an*cosnx = ∑ancos(nx)
Нужно ухитриться так подобрать все значения [a], чтобы функция F(x) при x = [0..1] равнялась A0, при x = (1,2] была A1, и т.д. Это сделать, конечно, возможно... а может, нет?
Я подумал, а если взять не бесконечный ряд косинусов, а только два? И пусть тогда при x = 0 функция будет равна 1, и при x = 1 функция будет равна 8. При этом опустим a0 - все равно будет константа, и значения это число не играет в данном случае. Тогда будет:
Конечно, все эти разглагольствования и приведение примеров очень мало значат с тем, что из себя представляет вся последовательность косинусов. Подход с помощью систем уравнении не то что неправилен, нет, он может быть, но он непродуктивен, потому что решить систему уравнении с N, стремящимися к бесконечности, неизвестных, невозможно. Даже при N = 256 это уже затруднительно.
Система уравнений:
m(i,j) = K1*cos(K2*i*j),
где i - строка, j - столбец, а K1, K2 - некоторые фиксированные значения-константы. Я не помню, чему они равны, но если они равны нужным значением, поиск a1-a8 упрощается в несколько раз.
Решить ее можно методом Гаусса. Этот метод я приводить не буду, потому что решение этим методом займет огромное количество места в статье, просто скажу, что нужно привести всю матрицу к виду, где под/над главной диагональю будут 0. Любую строку можно умножить на любое число, отличное от 0, любую строку можно сложить с любой другой строкой без потерь. Таковы основные приемы метода Гаусса, хотя, честно говоря, все это проистекает из очень простых правил.
Отсюда видно, что строки "прибавились" между собой, учитывая и коэффициент K. Хотя чего объяснять, детский сад :) Еще в школе это проходили, хотя... повторить иногда нужно.
Если же [x] распределить на сегменте от 0 до 1 c шагом 1/8, можно получить более точные дискретные значения. Система уравнений будет иметь решение все равно. Теперь, если [x] распределить на сегменте, взяв при этом шаг 1/n, где n стремится к бесконечности, то система уравнений будет все большей и большей, неизвестных будет n, и их число будет стремиться к бесконечности, но, однако, решение все равно будет.
Если же [x] распределить на всей числовой оси, т.е. x=(-W,+W), где W стремится к бесконечности, а шаг будет стремится к нулю, т.е. шаг = 1/W2, то количество неизвестных при решении ДКП-матрицы будет возрастать квадратично n = W2, но, все равно, будет иметь решения. Отсюда очень интересный вывод: с помощью ДКП-Ф можно разложить абсолютно любую дискретную функцию на всей числовой оси. Хотя сейчас данный вывод плохо соотносится с компьютерной тематикой, и является, по сути, просто чистой математикой. Обычно разложения ведутся на отрезке x = [-W,W] с шагом 1, где W=128,256,512... или любые другие конечные значения, и это я назвал бы "сэмплированием".
Что-то я вроде объяснил, только не назвал самого главного - как на практике производить простое ДКП-Ф или быстрое ДКП-Ф. Для этого я бы лучше пока порекомендовал бы статью из Википедии.
Как обычно, мне лень куда-то глядеть, изучать, лишний раз напрягаться, но, с другой стороны, мне очень хотелось узнать, в чем же секрет этого ДКП-Ф. Как может целый ряд сложиться в прерывистую функцию, если ряд непрерывен? Потому, долго ломая голову, я, наконец, немного понял, но только немного, потому что способ, по которому я разлагал ряд в непрерывность, очень непродуктивен, однако ПОНЯТЬ схему этого ДКП-Ф оказалось просто.
Дана функция
F(x) = a0 + a1*cosx + a2*cos2x + a3*cos3x + ... + an*cosnx = ∑ancos(nx)
Нужно ухитриться так подобрать все значения [a], чтобы функция F(x) при x = [0..1] равнялась A0, при x = (1,2] была A1, и т.д. Это сделать, конечно, возможно... а может, нет?
Я подумал, а если взять не бесконечный ряд косинусов, а только два? И пусть тогда при x = 0 функция будет равна 1, и при x = 1 функция будет равна 8. При этом опустим a0 - все равно будет константа, и значения это число не играет в данном случае. Тогда будет:
a1*cos(1*x) + a2*cos(2*x) = 1, если x = 0, то a1*cos(1*0) + a2*cos(2*0) = 1 a1*cos(1*x) + a2*cos(2*x) = 8, если x = 1, то a1*cos(1*1) + a2*cos(2*1) = 8Полученный результат можно представить в виде системы уравнений:
a1*cos(0) + a2*cos(0) = 1 a1*cos(1) + a2*cos(2) = 8пусть a1 = x, a2 = y, в таком случае:
1*x + 1*y = 1; (1) 0,5403*x - 0,4161*y = 8; (2)Здесь нетрудно найти x и y:
- x = 1 - y, подстановка в (2) получается:
- 0,5403 - 0,5403*y - 0,4161*y = 8
- -0,9564*y = 7,4597
- y = - 7,4597 : 0,9564 = -7,799
- x = 8,799
x = 0, то 8,799*cos(0) - 7,799*cos(0) = 1 x = 1, то 8,799*cos(1) - 7,799*cos(2) = 0,5403*9,0524 + 8,0523*0,4161 = 4,89101172 + 3,2451639 = 8,136Чуть-чуть "промахнулся", конечно, в результате сильной погрешности, но это принципиально неважно, ведь глаз с трудом сможет отличить разность в 1% при более точном вычислении этого можно получить правильный результат.
Конечно, все эти разглагольствования и приведение примеров очень мало значат с тем, что из себя представляет вся последовательность косинусов. Подход с помощью систем уравнении не то что неправилен, нет, он может быть, но он непродуктивен, потому что решить систему уравнении с N, стремящимися к бесконечности, неизвестных, невозможно. Даже при N = 256 это уже затруднительно.
Система уравнений:
a1*cos(1*x) + a2*cos(2*x) + ... + a8*cos(8*x) = A1, где x = 0 a1*cos(1*x) + a2*cos(2*x) + ... + a8*cos(8*x) = A2, где x = 1 .... ... ... a1*cos(1*x) + a2*cos(2*x) + ... + a8*cos(8*x) = A7, где x = 6 a1*cos(1*x) + a2*cos(2*x) + ... + a8*cos(8*x) = A8, где x = 7Может быть представлена в виде матрицы:
a1 a2 a3 a4 a5 a6 a7 a8 | cos0 cos0 cos0 cos0 cos0 cos0 cos0 cos0 | A1 | cos1 cos2 cos3 cos4 cos5 cos6 cos7 cos8 | A2 | cos2 cos4 cos6 cos8 cos10 cos12 cos14 cos16 | A3 | cos3 cos6 cos9 cos12 cos15 cos18 cos21 cos24 | A4 | cos4 cos8 cos12 cos16 cos20 cos24 cos28 cos32 | A5 | cos5 cos10 cos15 cos20 cos25 cos30 cos35 cos40 | A6 | cos6 cos12 cos18 cos24 cos30 cos36 cos42 cos48 | A7 | cos7 cos14 cos21 cos28 cos35 cos42 cos49 cos56 | A8Как видно, нужно найти a1-a8, строки матрицы - это система коэффициентов. Здесь матрица - это всего лишь упрощенный вид системы уравнении, не больше. Самое интересное именно в этой матрице, что здесь нет ни одного значения, равное 0, ведь нет ни одного числа, который был бы кратен "пи наполовину" :) Данная матрица, правда, в некоторой весьма видоизмененной форме, называется "матрицей ДКП", и строится по формуле:
m(i,j) = K1*cos(K2*i*j),
где i - строка, j - столбец, а K1, K2 - некоторые фиксированные значения-константы. Я не помню, чему они равны, но если они равны нужным значением, поиск a1-a8 упрощается в несколько раз.
Решить ее можно методом Гаусса. Этот метод я приводить не буду, потому что решение этим методом займет огромное количество места в статье, просто скажу, что нужно привести всю матрицу к виду, где под/над главной диагональю будут 0. Любую строку можно умножить на любое число, отличное от 0, любую строку можно сложить с любой другой строкой без потерь. Таковы основные приемы метода Гаусса, хотя, честно говоря, все это проистекает из очень простых правил.
Отсюда видно, что строки "прибавились" между собой, учитывая и коэффициент K. Хотя чего объяснять, детский сад :) Еще в школе это проходили, хотя... повторить иногда нужно.
Если же [x] распределить на сегменте от 0 до 1 c шагом 1/8, можно получить более точные дискретные значения. Система уравнений будет иметь решение все равно. Теперь, если [x] распределить на сегменте, взяв при этом шаг 1/n, где n стремится к бесконечности, то система уравнений будет все большей и большей, неизвестных будет n, и их число будет стремиться к бесконечности, но, однако, решение все равно будет.
Если же [x] распределить на всей числовой оси, т.е. x=(-W,+W), где W стремится к бесконечности, а шаг будет стремится к нулю, т.е. шаг = 1/W2, то количество неизвестных при решении ДКП-матрицы будет возрастать квадратично n = W2, но, все равно, будет иметь решения. Отсюда очень интересный вывод: с помощью ДКП-Ф можно разложить абсолютно любую дискретную функцию на всей числовой оси. Хотя сейчас данный вывод плохо соотносится с компьютерной тематикой, и является, по сути, просто чистой математикой. Обычно разложения ведутся на отрезке x = [-W,W] с шагом 1, где W=128,256,512... или любые другие конечные значения, и это я назвал бы "сэмплированием".
Что-то я вроде объяснил, только не назвал самого главного - как на практике производить простое ДКП-Ф или быстрое ДКП-Ф. Для этого я бы лучше пока порекомендовал бы статью из Википедии.