Раздел: Документация
0 ... 14 15 16 17 18 19 20 ... 78 5.4.2. Оценка сложности вычислений После соответствующего преобразования входные сигналы полагаются комплексными в полосе частот (-В, В). Отсчеты сигналов берутся с частотой 2,5 В. Обработка входных данных. Спектральный анализ осуществляется на базе процедуры усреднения периодограмм. Пусть Д/ = 1/Т - требуемая спектральная разрешающая способность. Если обозначить через L число анализируемых элементов разрешения по частоте (положительных частот), то L = =B/Af. Если спектральный анализ выполняется с периодом Т/2, то ТУ БПФ на 2,5/, точек должны вычисляться за время Т/2. Оценки МВСП Г(/е) вычисляются для каждого элемента разрешения по частоте. Поскольку Г(/е) является эрмитовой матрицей, процедура оценки потребует выполнения L идентичных операций, состоящих из PN[(N+1)/2] операций комплексного умножения и сложения. Эти вычисления выполняются за время РТ/4. Специфические вычисления метода ВРС. В первую очередь вычисляются собственные значения и собственные векторы матриц. Сложность вычислений зависит от размера матриц (т.е. от числа элементов антенной решетки N), требуемой точности и числа самих матриц. Обычно для вычисления собственных значений при 32 элементах решетки требуется около 105 операций умножения и сложения, а для расчетов собственных значений и собственных векторов - примерно 2Х105 аналогичных операций. Эти значения изменяются примерно пропорционально Л/25. Для устойчивости вычислений должны использоваться 32-разрядные вычислительные устройства с плавающей запятой. 1. Оценка параметра пространственной когерентности фонового шума. Для L элементов разрешения по частоте и М значений параметров должны вычисляться: матрица Тсп (fe, m), что потребует около Л° (3/V+1)/2 операций комплексного умножения и сложения; собственные значения Tcn(fe, m), что потребует около 20N25 операций умножения и сложения. При оценке параметров фонового шума потребуется пренебрежимо малое число операций по сравнению с их числом в предыдущих расчетах. Эти ML идентичных операций выполняются последовательно с периодом, равным времени стационарности фонового игума; этот период, как правило, больше периода оценивания РТ/4 матрицы Г (fe). 2. Определение подпространства сигналов и его ортогонального дополнения. Дл.я L элементов разрешения по частоте должны выполняться следующие операции с периодом РТ/4: вычисление матрицы Tcn(fe, m0), что потребует /У2(ЗЛ/+1)/2 операций комплексного умножения и сложения; вычисление собственных значений и собственных векторов этой матрицы, что потребует около 20N2tS операций умножения и сложения; оценка числа источников сигналов, что потребует пренебрежимо малого числа операций по сравнению с их числом в предыдущих расчетах. 106 Оценка параметров источников сигналов. Более трудно оценить вычислительную сложность процедуры оценивания параметров источников сигналов. Это объясняется тем, что она зависит от числа неизвестных параметров среды распространения. Но эти параметры в общем случае требуют вычисления скалярных произведений комплексных векторов. Примером одного из простейших методов является метод ортогонального подпространства без использования параметров среды распространения. При выполнении процедуры просмотра значений для каждого элемента разрешения по частоте потребуется около [N- K(fe)] (N+l)& операций комплексного умножения и сложения, где © - число значений 0. Если же для повышения эффективности системы учитываются параметры среды распространения, то объем вычислений должен существенно возрасти. В этом случае можно обратиться к более подходящим методам поиска. 5.5. ЗАКЛЮЧЕНИЕ Методы, обеспечивающие высокую разрешающую способность, могут применяться для решения задач приема акустических сигналов под водой с помощью пассивной антенной решетки благодаря их более высокой разрешающей способности, чем при обычных и адаптивных методах формирования луча. Однако при этом необходимо тщательнее моделировать среду распространения, что требует введения дополнительных параметров и их последующей оценки. Появление этих новых методов привело к разработке устройств новой архитектуры, характеризуемых двумя основными особенностями. Первая состоит в значительном увеличении сложности вычислений по сравнению с их сложностью в обычной диаграммообразующей схеме. Если в обычном устройстве обработки диаграмма формируется сразу же после осуществления на входе БПФ, то методы высокой разрешающей способности требуют дополнительных операций оценки матрицы взаимной спектральной плотности и решения проблемы нахождения собственных значений этой матрицы. Вторая особенность заключается в том, что большинство вычислительных операций относится к матричным операциям: вычисление скалярных произведений комплексных векторов, умножение комплексных матриц и получение собственных значений эрмитовых матриц. Поэтому новые методы параллельных вычислений, такие как обработка сигналов с помощью систолических процессорных структур [11], могут обеспечить приемлемое решение задач пространственно-временной обработки сигналов элементов антенной решетки. СПИСОК ЛИТЕРАТУРЫ [1] W. S. Ligget, "Passive Sonar: Fitting Models to Multiple Time Series" Proc. NATO ASI Signal Process., Academic Press, Loughborough, U.K., 1972, pp. 327-345. [2] H. Mermoz, "Imagerie, correlation et modeles," Ann. Telecommun., i/( 1-2): 17-36, (jan.-fev. 1976). [3] N. L. Owsley, "A Recent Trend in Adaptive Spatial Processing for Sensor Arrays," Proc. NATO ASl Signal Process., Academic Press, Loughborough, U.K., 1972, pp. 131-164. [4] N. L. Owsley, and J. F. Law, "Dominant Mode Power Spectrum Estimation," Proc. ICASSP 82, Paris, May 3-5, 1982, pp. 775-778. [5] G. Bienvenu, "Influence of the Spatial Coherence of the Background Noise on High Resolution Passive Methods," Proc. 1CASPP 79, Washington, D.C., Apr. 2-4, 1979, pp. 306-309. [6] R. Schmidt, "Multiple Emitter Location and Signal Parameter Estimation," Proc. RADC Spectrum Estimation Workshop, Oct. 1979, pp. 243-258. [7] G. Bienvenu and L. Kopp, "Source Power Estimation Method Associated with High Resolution Bearing Estimation," Proc. ICASSP 81, Atlanta, Ga., Mar. 1981, pp. 153- 156. [8] G. Bienvenu and L. Kopp, "Optimality of High Resolution Array Processing Using Eigensystem," IEEE Trans. Acoust. Speech Signal Process., Oct. 1983, pp. 1235-1248. [9] G. Bienvenu and L. Kopp, "Adaptivity of Background Noise Spatial Coherence for High Resolution Passive Methods," Proc. ICASSP 80, Denver, Colo., Apr. 9-11 1980 pp. 307-310. [10] S. N. Franklin, Matrix Theory, Prentice-Hall, Englewood Cliffs, N.J., 1968. [11] K. Bromley, I. J. Symanski, J. M. Speiser, and. J. H. Whitehouse, "Systolic Array Processor Developments," Proc. CMV Conf. VLSI Syst. Сотр., Carnegie-Mellon University, Pittsburg, Pa., Oct. 19-21,1981. 6 ЗАМЕЧАНИЯ ПО ПОВОДУ ВЫЧИСЛЕНИЯ СОБСТВЕННЫХ ЗНАЧЕНИЙ МАТРИЦ Б. Ларлетт1 6.1. ВВЕДЕНИЕ Как показано в предыдущих главах этой книги, вычисления собственных значений матриц начинают играть важную роль в современной обработке сигналов. С другой стороны, есть ученые и инженеры, которые тратят значительные суммы денег (миллионы долларов) и большую часть своей творческой жизни на вычисления собственных векторов и собственных значений матриц. Инженерам-разработчикам структур необходимо знать собственные частоты и оптимальные режимы; специалисты квантовой химии рассчитывают вывести химические свойства молекул, зная их возможные состояния и соответствующие им энергии; океанографы могут оценить эффективность своих моделей, сравнивая предсказанные приливы и отливы с результатами наблюдений. Использование СБИС для расчета собственных значений матриц поможет расширить исследования в некоторых из перечисленных на- 1 Калифорнийский университет, Беркли, Калифорния. правлений. В конце главы кратко рассмотрим влияние новой технологии на разработку перспективных алгоритмов, а пока вернемся к началу. Какова на сегодняшний день обстановка с последовательными и векторными компьютерами? В последующих разделах попытаемся изложить основные особенности, не вдаваясь в детали и без особого педантизма. Всю проблему следует разделить на две части в соответствии с двумя очевидными, но неодинаково осознанными критериями. Матрицы могут быть большими и малыми (см. разд. 6.3), и их собственные значения могут быть действительными или комплексными. Более того, свойством, которое порождает действительные собственные значения, в большинстве случаев является симметрия действительной матрицы. В данной главе прописными буквами будут обозначены матрицы, строчными - векторы. Мы старались симметричными буквами обозначать симметричные матрицы, строчными греческими буквами - порядковые номера. 6.2. ПРИВЕДЕНИЕ К СТАНДАРТНОМУ ВИДУ В большинстве случаев симметричные матрицы, для которых используются программы вычисления собственных значений, не должны были бы появляться в реальных задачах. Это можно объяснить следующим. Во многих случаях требуется найти решение (X, z) уравнения вида (H-AM)z =0, где Н и М - действительные симметричные матрицы и одна из них (или некоторая линейная комбинация из них) положительно определена. Целеустремленный пользователь послушно преобразует Н и М в одну симметричную матрицу в соответствии с рекомендациями, данными специалистами в их книгах и статьях [12, 20]. Наиболее распространенная методика преобразования для положительно определенной матрицы М состоит в ее разложении по Холецкому: М = II/, где t - знак транспонирования; L - нижняя треугольная матрица. Затем формируется матрица A = L"1H(L)"1 и исходное уравнение приводится к виду (A-AI)y = 0,y=Lfz. Теперь понятно, что эта процедура почти всегда плохая. Почему плохая? Если кратко, то потому, что А обычно намного больше Н и М (по норме), и потому, что, как правило, требуется только несколько наименьших собственных значений матрицы А. Когда матрица А имеет большой размер (например, 1000X1000), это плохо. Во-первых, существуют фундаментальные ограничения на относительную точность, с которой могут быть вычислены наименьшие собственные значения матрицы. Во-вторых, их труднее вычислить; чем большие собственные значения. В-третьих, любая структура 109 расположения нулевых элементов матриц Н и М будет утрачена при конструировании матрицы А. Предположим, что необходимо найти только собственные значения матриц Н и М, близкие а. Правильная процедура состоит в определении (но не формировании) матрицы А=М1/2 (Н-оМ)~1М1!2 . Но, пожалуйста, не обращайте матрицу! Чтобы сформировать вектор х = Av при любом векторе v, необходимо только решить линейную систему вида (H--aM)x = M1/2v относительно х, как бы это ни было трудно. Для этого можно воспользоваться алгоритмом определения наибольших собственных значений матрицы А. Они связаны с искомыми собственными значениями (Н, М) простыми зависимостями (см. [6 или 12, стр. 325]). Теперь вернемся к рассмотрению одной матрицы. 6.3. ВОЗМОЖНОСТИ СОВРЕМЕННЫХ ПРОГРАММ Определение. Матрица размера пХп считается малой (в данной вычислительной системе), если эта матрица и матрица, составленная из ее собственных значений, могут быть записаны в оперативном запоминающем устройстве (с произвольной выборкой) как обычные квадратные таблицы. В противном случае матрица считается большой. Это очень полезное различие. Существует глубокое различие между методами, используемыми в этих двух случаях (для больших и малых матриц), а также между самими проблемами, которые приводят к матрицам. Для больших вычислительных систем (типов CDC 7600, 6600, IBM 370/195, 165) матрица размера 100X100 элементов считается малой. Для мини-ЭВМ матрица размера 50X50 элементов может оказаться- большой. Тем не менее можно с уверенностью сказать, что матрица размера 1000Х XI000 элементов является большой, и следует заметить, что специалисты по квантовой физике хотели бы рассчитывать спектры матриц размера 2Р, где р достигает значений 20, 30, 40 и даже больше. Многие специалисты по численному анализу считают, что задача определения собственных значений для малых матриц решена. Есть одна нерешенная теоретически задача (сходимость смещенных QR-разложений для матриц, отличных от нормальной) , и я не осведомлен о каких-либо других узких местах в вычислениях. Несколько цифр могут подтвердить это мнение. На ЭВМ IBM 370/165 все собственные значения и все собственные векторы случайной симметричной матрицы размера 80X80 могут быть вычислены за 5,25 с. Интересно, что расчет одного наибольшего собственного значения занимает почти 1 с (0,88 с). Для несколько устаревшей модели ЭВМ CDC 6400 вместо 5,25 с требуется уже 32,64с, т.е. более полминуты. Следует добавить, что эти 80 собственных векторов будут ортогональны с достаточной для практических расчетов точностью. Ошибки вычислений собственных значений матрицы лежат в пределах нескольких единиц младшего разряда для наибольшего записанного в памяти ЭВМ собственного значения. Интересно было бы узнать о тех важных вычислительных задачах, для которых такая скорость вычислений недостаточна. На ум приходят только задачи вычисления в реальном масштабе времени. ПО Другим поводом для размышлений является то, что для малых матриц нет смысла использовать специальную структуру нулевых элементов (их так называемую структуру разрешениести). Единственное исключение составляет случай, когда матрица имеет очень малую ширину ленты (например, трехдиагональная, пятидиагональная). Другими словами, при использовании малых матриц имеется достаточный запас вычислительной мощности, который не требует анализа специальных свойств матриц (за исключением трехдиагональности и теплицевости). Что еще удивляет многих, так это то, что вычислять все собственные начения малой заполненной действительной симметричной матрицы (с «> 30) так же просто, как и умножать эту симметричную матрицу на другую! Короче, собственные значения матрицы вычислить проще, чем осуществить умножение. Точнее, требуется п3 операций скалярного умножения для получения результата. Допустим, что в предыдущем абзаце мы опустили прилагательное "симметричный". Тогда утверждение неправильно, но не полностью. Конечно, собственные значения могут быть комплексными. Тем не менее они все могут быть вычислены за время, меньшее того, которое необходимо для получения пяти произведений матрицы на матрицу (т.е. 5и3 операций действительного умножения). Опять-таки значение п должно быть достаточно велико, чтобы главные члены преобладали над другими, например п = 20, но все еще должно оставаться малым. Такое положение дел было бы невероятно в 1955 г. В чем же дело? Совместные усилия небольшой группы специалистов в период с 1958 г. по 1970 г. позволили сделать доступными библиотеки программ: EISPACK [5, 16] для задач вычисления собственных значений матриц, UNPACK [4] для решения линейных уравнений и задач вычислений по методу наименьших квадратов, IMSL [9] и NAG ([11] в Европе) для любых задач. Пакеты программ хорошо документированы и прошли надежное тестирование. Я считаю, что точность вычислений с помощью, скажем, программ EISPACK так высока, как только можно пожелать. Это может вызвать недоумение у тех, кто знаком с чрезвычайными трудностями вычисления канонической формы Жордано, когда она содержит блоки размера больше чем 1X1. Важно объяснить эту загадку. Коды программ EISPACK обеспечивают получение собственных векторов и собственных значений матриц, которые не точно равны собственным векторам и собственным значениям заданной матрицы, а с некоторой погрешностью. Если матрица в имеет размер пХп, то выходной результат в действительности соответствует матрице в-е, где е - неизвестная матрица, но е <и е в. Это существенное ограничение связано с тем, что при использовании ЭВМ осуществляются не точные арифметические вычисления. Специалисты по численному анализу предусмотрели алгоритмы, неопределенность результатов вычислений которых не больше, чем в п раз, превышает неопределенность при запоминании исходной матрицы. Так что внимание следует сосредоточить на влиянии неопределенности в численных значениях элементов матрицы на собственные значения. 0 ... 14 15 16 17 18 19 20 ... 78
|
