Содержание к диссертации
Введение
Глава 1. Применение алгоритмов устойчивой параллельной сортировки для вычисления нулей полиномов с учетом кратности 36
1.1. Адресные параллельные сортировки 37
1.2. Применение адресной сортировки для нахождения экстремальных элементов последовательности 48
1.3. Подход к локализации и вычислению нулей полиномов на основе сортировки 50
1.4. Схема применения сортировки для вычисления комплексных нулей полиномов с учетом кратности 53
1.5. Поиск нулей полиномов с учетом кратности в произвольной области комплексной плоскости 60
1.6. Временная сложность максимально параллельного алгоритма нахождения нулей полиномов с учетом кратности 63
1.7. Выводы 66
Глава 2. Применение сортировки для вычисления полюсов и вычетов функций с приложением к анализу цифровых фильтров 68
2.1. Вычисление полюсов комплексной функции с учетом порядка на основе сортировки 69
2.2. Вычисление вычетов функций в действительных полюсах на основе сортировки 74
2.2.1. Алгоритм приближенного вычисления коэффициентов ряда Лорана на основе сортировки 76
2.2.2. Алгоритм вычисления коэффициентов ряда Лорана с использованием дополнительной функции 81
2.2.3. Метод вычисления коэффициентов ряда Лорана с повышенной точностью 84
2.3. Параллельная схема определения вычетов функций в комплексных полюсах на основе сортировки 85
2.4. Схема приближенного вычисления интегралов по замкнутому контуру на основе сортировки 90
2.5. Схемы анализа цифровых фильтров с использованием сортировки 94
2.5.1. Анализ цифровых фильтров с помощью обратного z-преобразования 94
2.5.2. Анализ временной функции линейной динамической системы 96
2.5.3. Анализ устойчивости дискретной цепи 97
2.6. Сравнение метода вычисления нулей и полюсов функций на основе сортировки с существующими методами 100
2.7. Выводы 107
Глава 3. Автоматическая локализация собственных значений матриц на основе сортировки с приложением к распознаванию плоских изображений 108
3.1. Метод локализации и приближенного вычисления собственных значений матриц на основе сортировки 109
3.2 Приложение метода локализации собственных значений матриц на основе сортировки к экономическим исследованиям 112
3.3. Алгоритм построения на основе сортировки жордановой формы матрицы. 115
3.3.1. Алгоритм нахождения элементарных делителей матрицы 116
3.3.2. Уточнение алгоритма программного построения формы Жордана 122
3.4. Оценка временной сложности параллельного построения канонической формы Жордана 124
3.5. Приложение метода нахождения спектра матрицы на основе сортировки к распознаванию плоских изображений 126
3.5.1. Распознавание двуцветного изображения 127
3.5.2. Видоизменение идентификации изображений для случая подобных матриц 131
3.5.3. Идентификация отпечатков пальцев 134
3.5.4. Видоизменение схемы распознавания для случая цветного изображения 137
3.5.5. Видоизменение схемы распознавания на случай изображений произвольного размера 140
3.6. Выводы 143
Заключение 145
Литература 147
Приложение 1 157
Приложение 2 165
Приложение 3 168
Приложение 4 194
- Применение адресной сортировки для нахождения экстремальных элементов последовательности
- Временная сложность максимально параллельного алгоритма нахождения нулей полиномов с учетом кратности
- Алгоритм вычисления коэффициентов ряда Лорана с использованием дополнительной функции
- Приложение метода локализации собственных значений матриц на основе сортировки к экономическим исследованиям
Введение к работе
Использование средств вычислительной техники для решения задач численного анализа - развивающееся направление в области построения приближенных методов. Как правило, известные схемы опираются на методы приближенных вычислений, включающие математические приемы, открытые до появления компьютеров и ориентированные на ручное вычисление. Программная реализация таких методов зачастую сталкивается с принципиальными трудностями.
Трудности применения схем компьютерных вычислений обусловлены, во-первых, особенностями архитектуры вычислительных систем и процессоров. Общепринятым средством выполнения научных и инженерных вычислений на компьютерах является арифметика чисел с плавающей точкой. Эта арифметика обеспечивает максимальный диапазон представления числовых данных, но специфика фиксированных границ разрядной сетки влечет существенное накопление погрешности арифметических операций, при котором, в частности, результат двух или нескольких последовательных операций может не содержать уже ни одной верной цифры [126]. Современные компьютеры выполняют в секунду до І7«10 ) операций [40] с плавающей точкой, поэтому достоверность вычисляемых результатов становится предметом особого внимания.
Во-вторых, особенности конкретных языков программирования также создают определенную трудность, влияя на точность вычислений. Например, в языке Object Pascal [35] используется вещественный тип данных «extended», характеризующийся разрядностью десятичной мантиссы 19..20 и диапазоном десятичного порядка -4932.. + 4932, в то время как в Visual Basic [50] аналогичный тип отсутствует. Наивысшая точность вычислений в Visual Basic достигается при использовании типа «double», разрядность десятичной мантиссы которого оценивается в пределах 15..16, а диапазон десятичного порядка -324.. + 308.
К трудностям применения компьютеров для реализации приближенных методов можно отнести специфику различных архитектур вычислительных систем, которые накладывают ограничения на объем памяти и скорость выполнения программ. Использование параллельных архитектур позволяет значительно увеличить скорость выполнения программ по сравнению с последовательными архитектурами, но при этом меняются алгоритмы вычислений и характер накопления погрешности. Все эти архитектурные особенности инициируют видоизменения вычислительных алгоритмов и соответственные изменения характера накопления погрешности на выходе этих алгоритмов. Существует ряд внутренних проблем параллельной обработки, их техническая сущность заключается в способах и средствах осуществления обмена, алгоритмическая - в проблеме минимизации времени обмена [100,108,109,119]. Решение этих проблем также требует адаптации алгоритмов и влечет изменение роста погрешности.
Отмеченные трудности в полной мере относятся к классическим задачам оптимизации, решению алгебраических, трансцендентных уравнений и полной проблемы собственных значений. В то же время, к их решению сводится большой объем вычислительных задач прикладной математики, теоретической и экспериментальной физики, технической кибернетики, сложность которых продолжает возрастать.
На основании изложенного необходима разработка машинных методов приближенных вычислений, учитывающих архитектуру компьютера и использующих средства информатики.
Целесообразно при этом принять во внимание тот аспект возможного использования сортировки для приближенных вычислений, что алгоритмы ее выполнения позволяют минимизировать количество формул и методов традиционной математики. Применение сортировки опирается на упорядочение информации при вычислениях и включает только операции сравнения. Как следствие, можно ожидать снижение роста погрешности при решении задач с ее применением.
Сортировка [3,13,35,36,44] является одной из основных процедур нечисловой обработки данных, которая используется в задачах, связанных с системами автоматизированного управления и с информационно-поисковыми системами, включая экономику, медицину, систему образования, библиотечное дело, бронирование и продажу билетов на транспорте и т.д.
Сортировка нужна для того, чтобы обеспечить эффективную обработку (например, поиск) в больших наборах данных; представить массивы данных в форме, удобной для анализа; группировать элементы по некоторому признаку; строить гистограммы распределения данных и др.
В числе современных подходов к решению различных задач численного анализа, в том числе вычислению нулей полиномов и функций, находятся интервальные методы [1,33,40,98]. Они основаны на специфическом аппарате интервального анализа, который сложился на стыке вычислительной математики и информатики, с их помощью автоматически проверяется корректность результатов вычислений. Вычисление нулей функций с помощью интервальных методов рассматривается в работах [33,40,106].
Суть интервального подхода состоит в том, что неизвестное точное значение заменяется конечно-представимым множеством элементов, содержащим в себе этот неизвестный элемент. Интервал, представляемый обычно парой рациональных чисел-границ, является простейшим видом конечно-представимого множества, локализующего простейший абстрактный объект - вещественное число. В рамках интервального подхода исходные данные и промежуточные результаты представляются граничными значениями, над которыми и производятся все операции. При этом сами операции определяются таким образом [40], что результат соответствующей точной операции обязательно лежит внутри вычисляемых границ. Возникающая при вычислении границ погрешность учитывается с помощью направленных округлений: меньшая из вычисленных границ получается округлением до ближайшего машинного числа с недостатком, а большая - с избытком. Интервальный подход позволяет учесть все виды погрешностей вычислительного процесса: приближенно известные исходные данные заключаются в гарантированно содержащие точное значение границы, погрешности округлений лишь несколько расширяют границы промежуточных результатов, а сам численный метод строится так, чтобы погрешность метода (вызванная, например, остановкой бесконечно сходящегося процесса) также включалась в вычисленные границы конечного результата. Главные преимущества интервального подхода - автоматический учет всех видов погрешностей в процессе самого вычисления и гарантированная точность результата. Если одна и та же задача решается различными численными методами, то результаты вычислений можно пересекать в теоретико-множественном смысле -с тем чтобы отобрать более точный метод; сделать окончательный результат (собственно пересечение) более точным, чем полученный любым из методов в отдельности; проконтролировать разработку и программирование методов (пустота пересечения свидетельствует об ошибке).
Внутри интервальной математики существует тенденция к комбинированию в одном методе традиционных (классических) и интервальных вычислений. Осуществляется такое комбинирование следующим образом: сначала из интервалов с исходными данными берутся числа-представители и с помощью традиционных вычислений находится приближенное (в классическом смысле) решение задачи, затем это решение с помощью интервальных вычислений расширяется на всю область определения исходных данных. В [107, 121,125,134] такие методы получили название inclusion methods - «методы включения». Для отыскания нулей функций используются интервальные аналоги метода Ньютона в форме Мура [121], Хансена-Сенгупты [106], Кравчика [116] и др.
Общим недостатком интервальных методов является наличие в некоторых случаях слишком широких интервальных оценок результата [111], что не всегда приемлемо для проведения практических расчетов. Поэтому интервальные алгоритмы требуют больше времени, чем их традиционные аналоги. Иногда приходится разбивать интервал на подинтервалы, что может вызывать необходимость большего объема машинной памяти.
Известны различные системы компьютерной математики [20,27,28,54], реализующие разнообразные методы вычисления нулей полиномов и функций. В частности, в Mathcad для определения нулей функций и полиномов реализованы методы секущих, Брента, Лагерра и сопровождающей матрицы [79]. В пакете аналитических вычислений Maple нули полиномов вычисляются как собственные числа матрицы Фробениуса [27].
Схемы, реализованные в этих пакетах, не предполагают автоматической идентификации области нулей, иногда требуют начального приближения, соответственно они игнорируют наличие нулей в некоторых сложных случаях, либо не достигают в этих случаях требуемой точности вычислений. Рассматриваемые схемы могут проявлять неустойчивость при поиске нулей трансцендентных функций.
В этом контексте актуальна разработка программного метода локализации нулей полиномов и функций, который бы выполнял автоматическую идентификацию области каждого нуля и отличался бы существенным ограничением роста погрешности при его вычислении.
В основу метода целесообразно положить алгоритмы сортировки, поскольку, как отмечалось, они включают лишь операции сравнения и сами по себе не накапливают погрешность.
Сортировки традиционно применяются для поиска и моделирования методов теоретической информатики [92,93]. Положительный опыт применения сортировки именно для рассматриваемых схем вычислений описан в [58-60,66-73]. При этом параллелизм сортировки [61-62] влечет возможность построения параллельных схем определения нулей в целом.
Необходимо заметить, что традиционная для теоретической информатики схема исследования инициирует задачу совмещения подхода - с другой традиционной тематикой в данной области. Именно, возникает задача синтеза схем вычисления и распознавания на основе сортировки. При этом требуется осуществить ряд упрощений распознавания на основе упорядочения обработки информации с помощью алгоритмов сортировки.
Использование сортировки для данной цели предпринималось в [92,93,96]. Алгоритмы сортировки в этих работах представлены в несколько вспомогательном контексте с целью упорядочения информации. В дальнейшем будет поставлена цель применить сортировку в данном аспекте как конструктивную часть метода распознавания.
В целом, к одной из целей диссертационной работы относится исследование границ применимости сортировки как в области схем вычислений, так и в области распознавания, классификации и идентификации.
Конкретно, затрагивается проблема распознавания и идентификации плоских изображений. При этом подход к этой проблеме осуществляется непосредственно из применения сортировки для решения полной проблемы собственных значений, где роль матрицы играет матрица оцифрованных значений пикселей растрового изображения.
На сегодняшний день известны многочисленные методы обработки изображений, успешно применяемые в различных областях научных исследований. В [4,10,23,26,55, 80,82,84] представлена различная типология методов распознавания образов.
Общее состояние проблем распознавания изображений освящено в [57,74,128,129]. Традиционные методы стохастической геометрии в распознавании образов освещены в [89]. Технические аспекты идентификации отпечатков пальцев рассмотрены в [30,122,123]. Использование в современных методах распознавания рядов Фурье описано в [120], корреляционные методы освещены в [11,19,136], нейросетевые методы в [101,114]. Не останавливаясь на всех аспектах этой широкой и актуальной тематики, охарактеризуем состояние исследований в области распознавания плоских изображений.
Наиболее близким по построению к излагаемому в гл. 3 методу является метод, использующий вычисление собственных значений матриц для реставрации изображений [49]. Реставрация изображений представляет собой выполнение обращения искажений, внесенных в оригинал, и использует псевдообращение матриц, для чего необходимо прибегнуть к расщеплению их спектра. Другим, сходным по построению с излагаемым в дальнейшем методом является метод, описанный в [113], который использует спектр лапласиана Дирихле для получения трех различных топологических характеристик (вращение, сдвиг, масштабирование) для распознавания формы и классификации бинарных изображений. С помощью данного метода с вероятностью от 88.9% до 99.2% идентифицируются геометрические фигуры, изображенные от руки или с помощью графического редактора. Классификация осуществляется по нескольким характеристикам с использованием нейронной сети с механизмом прогнозирования событий.
Помимо обозначенных выше, основы существующих методов распознавания составляют схемы, использующие: локальные адаптивные элементы [115], выделение ключевых точек контуров [118], параметрический поиск [3]. Применяются: симультанная модель распознавания [6]; алгоритмы, основанные на вычислении оценок [29]; стохастические методы [89]; алгоритмы на основе решающих правил [7]. Для решения прикладных задач распознавания успешно используются методы, основанные на комбинаторном анализе признаковых описаний объектов [9].
На основе изложенного, а также согласно [39], можно утверждать, что в охарактеризованных методах распознавания имеют место неопределенности как в построении распознающих схем, так и в выборе эталонных последовательностей, при этом рассматриваемые схемы отличает существенная вычислительная сложность.
С целью исследования возможности разрешения отмеченных трудностей в диссертационной работе ставится задача построения метода распознавания плоских изображений в каноническом расположении с относительно упрощенной конструкцией алгоритмической схемы распознавания. Вектор распознавания состоит из диагональных клеток жордановой формы оцифрованной матрицы изображения, что обеспечивает квадратичное сжатие изображения и определяет выбор эталонной последовательности. В качестве основы алгоритмической схемы используется схема адресной параллельной сортировки. В результате достигается устойчивость распознавания и идентификации, которая сохраняется для класса изображений, определяемого как геометрическое место точек в ограниченной области плоскости.
Требования устойчивости и быстродействия распознавания обеспечиваются за счет построения и параллелизма схем на основе сортировки.
На основании изложенного целесообразно исследовать возможность построения единого метода, объединяющего алгоритмы решения некоторых математических задач (линейной алгебры и анализа) и задач искусственного интеллекта (распознавания изображений) на общей основе. Общей основой может служить использование алгоритмов распараллеливаемых сортировок.
Их построение актуально само по себе и находит разнообразное применение в системах программирования, в программном обеспечении, в системах обработки информации, управления базами данных, а также существенно используется в архитектуре современных ЭВМ.
Цель диссертационной работы заключается в разработке и исследовании единого метода применения сортировки для решения охарактеризованного круга вычислительных задач и распознавания плоских изображений. Сюда относятся методы идентификации нулей полиномов и функций; их особенностей, включая определение вычетов с приложением к вычислению криволинейных интегралов. На основе идентификации нулей характеристического полинома требуется дать решение полной проблемы собственных значений, выполнить построение нормальной формы Жордана для матрицы общего вида. Плоское изображение рассматривается как оцифрованная матрица пикселей, для его идентификации ставится цель применить перечисленные схемы с использованием сортировки. Метод должен отличаться единством конструкции, устойчивостью и параллелизмом.
Для достижения поставленной цели в диссертационной работе решаются следующие задачи: 1. Разработать и исследовать распараллеливаемый метод применения сортировки для устойчивой автоматической идентификации нулей полиномов с учетом их кратности, инвариантный относительно области поиска нулей. Произвести оценки временной сложности максимально параллельного варианта метода.
2. Перенести метод на приближенное вычисление полюсов и вычетов функций и применить его для вычисления криволинейных интегралов по замкнутому контуру. Исследовать применение метода для анализа цифровых фильтров с помощью обратного z-преобразования, для анализа временной функции линейной динамической системы и для анализа устойчивости дискретной цепи.
3. На основе сортировки разработать распараллеливаемый метод автоматической идентификации спектра матрицы и распространить его на определение элементарных делителей и построение канонической формы Жордана, дать оценки временной сложности предложенных параллельных методов.
4. Разработать метод и программную модель распознавания двуцветных и цветных изображений на основе нахождения спектра оцифрованной матрицы изображения при помощи сортировки.
5. Модифицировать метод на случай изображений, матрицы которых подобны, и на случай фрагментов изображений произвольного размера.
6. Провести программный и численный эксперименты, выполнить сравнительный анализ устойчивости и корректности предложенных методов.
Методы исследования опираются на теоретические основы информатики, численный анализ, теорию сложности, используют методы прикладной информатики, распознавания образов, современные информационные технологии.
Достоверность результатов вытекает из их математического обоснования, подтверждается оценками временной сложности, а также результатами программного моделирования и численного эксперимента.
Научная новизна диссертационной работы заключается в построении обобщенного метода применения сортировки для вычисления нулей полиномов и функций, а также особенностей функций с приложением к анализу цифровых фильтров и идентификации плоских изображений. Конкретно, научная новизна характеризуется следующим образом:
1. На основе сортировки синтезированы схемы устойчивой локализации и вычисления нулей полиномов и функций одной и двух переменных с учетом их кратности. Схемы отличаются от известных по построению на основе сортировки, свойством автоматической локализации области всех нулей и каждого нуля в отдельности, параллелизмом, а также вычислительной устойчивостью.
2. На основе сортировки разработана схема приближенного вычисления полюсов комплексных функций с учетом порядка. Схема использует обработку индексов отсортированных элементов, в результате не вносится вычислительная погрешность, метод достигает устойчивости, не включает ограничений на вид входной функции, отличаясь этим от известных аналогов.
3. Предложены алгоритмы приближенного вычисления вычетов функций в полюсах с использованием сортировки и, на этой основе, схема приближенного вычисления криволинейных интегралов по замкнутому контуру. Помимо построения на основе сортировки, алгоритмы отличаются вычислительной устойчивостью и параллелизмом.
4. Схемы применения сортировки распространены на решение полной проблемы собственных значений, собственные значения автоматически идентифицируются как нули характеристического полинома на основе программного оператора локализации минимумов по индексам отсортированных элементов.
5. На основе сортировки синтезированы схемы определения элементарных делителей матрицы и построения канонической формы Жордана. Даны оценки временной сложности максимально параллельного выполнения алгоритма построения формы Жордана.
6. Оцифрованная матрица пикселей плоского изображения рассматривается в качестве алгебраической матрицы, для которой вектор распознавания составляется из диагональных клеток жордановой формы матрицы. Схема распознавания отличается по построению и дает квадратичное сжатие исходного изображения за счет диагонализации матрицы.
7. На основе жордановой формы оцифрованной матрицы растрового изображения разработана схема идентификации плоских двуцветных и цветных изображений в каноническом расположении. Схема отличается от известных применимостью к произвольному геометрическому месту точек на плоскости и позволяет идентифицировать характерные фрагменты изображения.
Разработанные схемы идентификации изображений заимствуют конструкцию автоматической идентификации нулей функций на основе сортировки, что означает ее использование в качестве общей основы метода, влечет устойчивость и параллелизм предложенных алгоритмов. Основные положения, выносимые на защиту:
1. Метод применения сортировки для автоматической программной локализации и приближенного вычисления нулей полиномов и функций с учетом кратности.
2. Схемы идентификации полюсов функций, вычетов функций в полюсах и приближенного вычисления криволинейных интегралов по замкнутому контуру на основе сортировки с приложением к анализу цифровых фильтров.
3. Метод программной идентификации спектра матрицы общего вида и построения на его основе канонической формы Жордана с приложением к оцифрованной матрице растрового изображения.
4. Метод распознавания и идентификации плоских изображений в каноническом расположении, использующий автоматическую локализацию собственных значений матриц на основе сортировки.
5. Схемы распознавания изображений, алгебраические матрицы которых подобны, и идентификации фрагментов изображений произвольного размера.
Практическая ценность диссертационного исследования заключается в прикладном характере предложенных методов и алгоритмов. Все предложенные методы ориентированы на компьютерную реализацию и актуальны для решения научно-технических задач в различных областях. В частности, методы приближенного вычисления нулей, полюсов и вычетов функций используются для анализа цифровых фильтров. На основе предложенных в работе схем распознавания изображений могут создаваться новые системы распознавания, ориентированные на конкретное практическое применение.
Внедрение и использование результатов работы. Полученные в работе результаты использованы
1. В ОАО «Таганрогский завод «Прибой» для создания алгоритмического и программного обеспечения анализа гидроакустических изображений, получаемых от антенных систем высокого разрешения.
2. В госбюджетной НИР «Математические методы устойчивой параллельной обработки, поиска и распознавания», код ГРНТИ 28.23.15, регистрационный номер 01.2.00106436.
3. В учебном процессе кафедры информатики Таганрогского государственного педагогического института в рамках курсов «Информатика», «Информационные технологии в математике», «Численные методы», «Элементы абстрактной и компьютерной алгебры».
Применение адресной сортировки для нахождения экстремальных элементов последовательности
Под экстремальными элементами последовательности понимаются локально минимальные и локально максимальные элементы. Локально минимальный элемент последовательности в точности меньше предыдущего и не больше последующего элементов, локально максимальный элемент строго больше предшествующего, но не меньше последующего элементов.
Для нахождения экстремальных элементов последовательности используется адресная сортировка ее элементов, осуществляемая одним из описанных выше способов. К выходу процедуры сортировки подсоединяется условный оператор, локализующий все минимумы или максимумы среди этих значений [59,60].
Оператор локализации находит минимальные (максимальные) элементы последовательности по смыслу своего построения. Работая после сортировки, он для текущего элемента, определяемого индексом, записанным в е[к], находит каждый элемент, в е/иО-окрестности которого нет элементов, доставляющих значения элементов входной последовательности, предшествующие (последующие) с[е[к]] в отсортированном массиве. Среди элементов последовательности с равными значениями оператор локализации минимума (максимума) фиксирует элемент, соответствующий первому в порядке нумерации элементу отсортированного массива. Этот факт опирается на устойчивость используемой сортировки. Локализовать экстремальные элементы в рассматриваемом смысле предлагаемым способом можно только при сохранении обратных адресов на выходе сортировки, причем строго в том порядке, в каком располагаются отсортированные элементы.
В этом программном фрагменте п- число узлов, совпадающее с числом сортируемых элементов, h- шаг равномерной сетки, epsO - константа, равная радиусу е/иО-окрестности текущего узла (вдоль оси ОХ). Эта константа выбирается априори таким образом, чтобы не превысить половины числа узлов, отсчитываемых вдоль этой оси между ближайшими друг к другу нулями полинома.
Оператор локализации для текущего узла, определяемого индексом, записанным в еЗ[к], находит каждый узел Jc0 + e3[&] /z такой, что модуль полинома в этом узле не больше значений в остальных узлах его проекции epsO окрестности на ось ОХ, точнее, - строго меньше, или это значение является первым слева направо среди равных элементов на выходе отсортированного массива.
Значение локализованной абсциссы точки минимума хк := х0 + еЗ[к\ h дает привязку к локализуемой точке двумерного минимума. Оно фиксируется и аналогичным образом локализуется ордината yk:=y0 + e33[klj h, в которой достигается приближение к минимальному значению f(x,y) из (1.19). Теперь осталось выполнить спуск к наименьшему значению в окрестности локализованной точки. Он осуществляется с помощью выбора наименьшего значения в сужаемой окрестности с фиксированным числом элементов в сетке, пока не будет достигнута требуемая точность.
Для вычисления кратности нулей функции, и, как следствие, кратности нулей полинома, описанная выше схема циклически возобновляется несколько раз. Число повторных шагов пропорционально кратности каждого найденного нуля и фиксируется переменной ff (необходимо отметить, что все имена массивов и переменных, используемые здесь и далее совпадают с соответствующими именами в программах, представленных ниже).
В основе идеи определения кратности нулей лежит деление функции, нули которой уже найдены, на циклически подсчитываемое выражение рр := рр (sqr (х - ког х) + sqr {у - ког у)), (1-21) где число шагов цикла равно текущему счетчику кратности, a korx+i kory текущий корень. После деления исходной функции на выражение (1.21) программа заново выполняет нахождение всех нулей полученной в результате деления функции, при этом кратность текущего нуля на единицу меньше предыдущей.
В ходе реализации этой идеи возникла следующая трудность: если делитель обращается в машинный нуль рр- 0, что возникает, если найденный нуль «практически совпадает» с одним из первоначально вычисленных (когх, ког у), то программа выдает ошибку деления на нуль и прерывает свою работу. Эту трудность удается обойти делением исходной функции на другое, отличное от близкого к нулю, циклически подсчитываемое выражение - ррр := ррр eps, где число шагов цикла совпадает с текущим значением порядка найденных нулей, а eps - наперед заданная погрешность вычислений. Условие, при котором близкий к нулю делитель заменяется данным выражением, заключается в следующей проверке: if abs(sqr(x-korx)+sqr(y-kory)) eps then func := abs(p/(pp)) else begin ppp := 1; for і 1 := 1 to param do ppp := ppp eps; func :=abs(p/ppp);end где p - модуль полинома или функции, нули которого требуется вычислить, рр из (1.21).
В блоке констант раздела описаний данной функции под многоточием понимаются конкретные числовые массивы, количество элементов в которых равно пр. При этом пр - старшая степень полинома, нули которого требуется найти. В случае поиска нулей функции, конструкция которой отличается от произведения сомножителей, пр - произвольное число, заведомо большее кратности любого нуля этой функции.
Полный текст программы для нахождения нулей полинома с учетом их кратности приведен в приложении 1.2. В программной реализации кроме описанной выше функции func(xk,yk,korx,kory,r,param) используется функция func 00 (х,у) (являющаяся её частным случаем) лишь для того, чтобы проверить, что найденные нули действительно являются таковыми (в смысле приближения с точностью до є), т.е. проверить выполнение условия func 00 (х,у) = б, где є - наперед заданное, достаточно малое действительное число. Технически, func 00 (х,у) и func {xk,yk,korx,kory,r,param) можно было бы совместить.
Для вычисления кратности нулей формируется суперпозиция исходного полинома и произвольного одночлена, имеющего нуль, отличный от нулей исходного полинома и принадлежащий заданной области поиска. Необходимо также помнить о выполнении условия, наложенного на константу epsO.
Замечание 1.4. Необходимость формирования произведения входной функции на весовую обнаружилась в ходе численного эксперимента. Без использования весовой функции схема определения кратности нулей, описанная в [69], работала недостаточно устойчиво. Точнее, неустойчивость обнаруживалась в случае полиномов и функций, имеющих единственные многократные нули.
Временная сложность максимально параллельного алгоритма нахождения нулей полиномов с учетом кратности
Длительность работы программы, реализующей алгоритм нахождения комплексных нулей полиномов с учетом кратности, может компенсироваться параллелизмом изложенного метода. На основе взаимной независимости рассматриваемого алгоритма по всем фрагментам в произвольно выбранном прямоугольном разбиении области произведем оценку параллельного по данным фрагментам выполнения предложенного алгоритма (листинг примера 1.3).
Для оценки временной сложности (времени выполнения) параллельного алгоритма ниже используется модель неветвящейся параллельной программы без учета обмена. Формально такая модель определяется как последовательность параллельных алгоритмических команд, при этом команды отождествляются с арифметическими операциями. Предполагается, что параллельные команды исполняют параллельно работающие процессоры, которые при необходимости обмениваются вычисленными значениями, но в рамках модели обмен между процессорами не учитывается. Время выполнения измеряется числом последовательных шагов алгоритма.
При нахождении точек локальных минимумов х (в программе xk:=xO+E3[K] h), на промежутке длины hh сортировка может быть выполнена п2 параллельно на 0(—) процессорах за время 0(log2«). Это количество процессоров достаточно для обеих параллельных операций с суммарной оценкой времени 0(\og2n)- Последующее условие локализации минимума состоит из взаимно независимых сравнений с каждым значением 3[&] и выполнимо за и-1 п2 время 0(1) на Х = — процессорах. Повторное выполнение локализации k=\ 2 минимума по ординате ур (в программе yk:=yO+E33[Kl] h) производится при фиксировании хк с аналогичными оценками. Если предположить, что число локальных минимумов п\ лежит в интервале (пр,п), где пр- программный идентификатор степени полинома, то в такой пропорции возрастет число процессоров для рассматриваемой модификации программы.
Данные оценки соответствуют максимально параллельному варианту метода, показывая потенциал быстродействия рассмотренной схемы. При распараллеливании временная сложность схемы не будет критичной в сравнительно больших областях поиска нулей, включая случай их плохой отделенности.
Данные оценки показывают возможность эффективно распараллелить программу с помощью компьютерных MIMD систем [46], когда мы имеем дело с несколькими процессорами, каждый из которых способен выполнять свою инструкцию; кроме того, имеется несколько потоков данных, и каждый процессор может работать со своим набором данных. То есть MIMD система может выполнять на каждом процессоре свою программу или отдельные части одной и той же программы.
1. Предложен метод применения сортировки для приближенного вычисления нулей полиномов с учетом их кратности, отличающийся от известных по построению и автоматической программной локализацией всех нулей.
2. Предложена схема вычисления кратности нулей полиномов, основанная на рекуррентном повторении алгоритма нахождения нулей при помощи сортировки. Схема отличается от известных отсутствием необходимости отделения нулей и тем, что не требует поиска первого приближения к нулю и дифференцирования полинома.
3. Метод модифицирован на случай области комплексной плоскости, границы которой не фиксированы, в частности, они могут не примыкать к области всех нулей полинома и отделяться от нее произвольно большим расстоянием.
4. Исследован параллелизм метода, даны оценки временной сложности максимально параллельного его выполнения в произвольном прямоугольном разбиении комплексной области.
5. Отличия предложенного метода являются следствием алгоритмического подхода на основе сортировки, в частности, компьютерная реализация на этой основе автоматизирует локализацию нулей, базовые схемы реализуются в форме стандартных подпрограмм, на вход которых достаточно подать значения полинома.
Постановка вопроса. Изложенный в предыдущей главе метод ниже модифицируется для автоматической идентификации полюсов комплексных функций с учетом их порядка. Полюсы исходной функции ищутся как нули обратной ей функции, что позволяет осуществить перенос схемы нахождения нулей на данный случай.
Схема распространяется на вычисление вычетов комплексных функций, имеющих в качестве особенностей полюсы, с последующим вычислением криволинейных интегралов по замкнутому контуру. Для этой цели реализуется рекуррентное определение последующих коэффициентов ряда Лорана через предыдущие с априори заданной границей погрешности, что позволяет вычислить требуемое количество коэффициентов при отрицательных степенях ряда Лорана. Коэффициенты вычисляются при повторном применении схемы вычисления нулей в месте спуска к наименьшему значению в окрестности локализованной точки с некоторыми алгоритмическими дополнениями.
Следует отметить, что описываемые ниже схемы заимствуют конструкцию схемы предыдущей главы с использованием сортировки в качестве основы метода. Первым следствием этого является минимальное накопление вычислительной погрешности и устойчивая локализация искомых особенностей, включая случаи их плохой отделенности. Второе следствие - минимум математических ограничений на вид входных функций. Кроме того, излагаемый метод инвариантен относительно области определения функций и области, включающей искомые особенности.
Алгоритм вычисления коэффициентов ряда Лорана с использованием дополнительной функции
Для более точного (в сравнении с описанным выше) вычисления вычетов функции в полюсах необходима реализация следующих этапов. 1) Определяются все полюсы Z функции f(z) с учетом их порядка с использованием сортировки в качестве основы метода. 2) Для определения вычета функции в первом из найденных полюсов ZQ порядка п точно вычисляется коэффициент ряда Лорана С_п с наименьшей отрицательной степенью с помощью предельного перехода или способом, описанным в 2.2.1. 3) Коэффициент C_n+i вычисляется при повторном применении схемы вычисления полюсов функции, но уже не исходной /(z), а функции с_ Л (z) = f(z) — в месте спуска к наименьшему значению в окрестности ( - о)я локализованной точки. При этом для функции f\(z) полюс Z = ZQ имеет порядок равный п-\, а коэффициент С_п+\ для f(z) совпадает с коэффициентом с наименьшей отрицательной степенью для функции f\(z), который возможно вычислить фактически без погрешности одним из двух методов пункта 2. 4) Коэффициент С_п+2 вычисляется при повторном применении схемы с с вычисления полюсов функции /2( ) = /(2) — При этом (z-zk)n (z-zk)"-1 для функции fiiz) полюс Z = ZQ имеет порядок равный и-2, а коэффициент С_„+2 для f(z) совпадает с коэффициентом с наименьшей отрицательной степенью для функции /2(z), который вычисляется фактически без погрешности. 5) Процесс, описанный в пунктах 3 и 4, повторяется до тех пор, пока не будет вычислен коэффициент при первой отрицательной степени в разложении функции в ряд Лорана в окрестности точки ZQ . 6) Пункты 2-5 повторяются для всех найденных полюсов до тех пор, пока не будет установлен вычет в каждом полюсе.
Последний способ нахождения коэффициентов ряда Лорана, и как следствие, вычета функции в полюсе, представляется наиболее предпочтительным, несмотря на необходимые алгебраические преобразования, поскольку он дает наиболее точный результат, к тому же представляется возможной программная реализация таких преобразований ввиду их простоты. Рекуррентное вычисление последующих коэффициентов ряда Лорана через предыдущие последним способом с априори заданной точностью позволяет определить требуемое количество коэффициентов при отрицательных степенях ряда Лорана.
Алгоритмически схемы определения вычетов функций в комплексных полюсах практически не отличаются от схем для действительного случая, представленных в разделе 2.2, являясь их обобщением на случай комплексного переменного. Вычисление комплексных вычетов основано на следующем алгоритме.
1) С помощью сортировки идентифицируются действительные и мнимые части всех полюсов z функции f(x,y) из (2.1) с учетом их порядка.
2) Для определения вычета функции в первом из найденных полюсов ZQ порядка п точно вычисляется коэффициент ряда Лорана С_л с наименьшей отрицательной степенью при повторном применении схемы вычисления комплексных полюсов исходной функции в месте спуска к наименьшему значению в окрестности локализованной точки при существенном сужении области поиска вокруг найденного значения полюса. Программная реализация использует алгоритм, изображенный на рис. 1.4. На рис. 2.5 более детально рассмотрен блок спуска к наименьшему значению в окрестности локализованной точки в этом случае.
Действительные и мнимые части приближений к коэффициенту ряда Лорана, вычисляемому по соответствующей формуле из (2.5), заносятся в массивы wx и vyv соответственно, после чего искомый коэффициент представляется как комплексное число, действительная и мнимая части которого равны среднему арифметическому значений первых десяти элементов этих массивов соответственно.
Необходимо отметить, что временные затраты на работу программы покрываются возможностью параллельного выполнения изложенного метода вычисления вычетов в полюсах в целом. Параллельно может выполняться сортировка, на параллельные фрагменты могут разделяться области поиска полюсов. Существует возможность сократить время работы программы, если параллельно делить на все возможные порядки полюсов. Оценки максимально параллельного варианта метода вычисления полюсов с учетом порядка совпадают с оценками, произведенными в разделе 1.6. Следует заметить, что осуществимо взаимно независимое определение коэффициентов ряда Лорана в различных полюсах. Поскольку данный фрагмент программы является не самостоятельным, а лишь частью процедуры спуска, к тому же для вычисления коэффициентов не используются дополнительные циклы и сравнения, то рассматриваемая оценка максимально параллельного варианта метода раздела 1.6 не изменится.
Поэтому, вычислив вычеты исходной функции по изложенной выше схеме, автоматически (лишь с некоторыми формальными оговорками) можно перейти к вычислению интеграла по замкнутому контуру. Следует отметить, что этот переход будет возможен в случае вычисления вычетов в полюсах, находящихся только лишь внутри области D, поэтому необходимо верное программное представление этой области.
Приложение метода локализации собственных значений матриц на основе сортировки к экономическим исследованиям
Собственные векторы и собственные значения матриц имеют широкий круг приложений, в том числе и в социально-экономических исследованиях. Описанный метод нахождения собственных значений матрицы может использоваться, например, в динамической модели В. Леонтьева [43], определяющей траектории сбалансированного экономического развития. Качественные свойства этих траекторий зависят от матрицы G = [Е - А - В], где А- матрица прямых затрат, В - матрица коэффициентов капиталоемкости, Е -единичная матрица. При некоторых условиях [43] величина, обратная наибольшему собственному значению Лтдйі (числу Фробениуса-Перрона) матрицы определяет максимально возможный («технологический») темп прироста экономики, а соответствующий этому значению собственный вектор (вектор Фробениуса-Перрона) характеризует необходимые пропорции между объемами производства продукции на «магистральном» (с максимальным темпом прироста) участке экономического развития.
Таким образом, для оценки допустимых темпов роста в динамической модели Леонтьева необходимо вычислить число Фробениуса-Перрона матрицы. Для этой цели достаточно применить описанный выше программный метод нахождения всех собственных значений Л матрицы G. Для нахождения собственных векторов матрицы G в векторное уравнение (G - ЛЕ)Х = О нужно подставить найденные собственные значения и решать его обычным образом (например, методом Гаусса).
В математической экономике большую роль играют так называемые продуктивные матрицы. Программное вычисление собственных значений некоторой матрицы А позволит сделать вывод о продуктивности этой матрицы, согласно положению [31] - матрица А является продуктивной тогда и только тогда, когда все собственные значения этой матрицы по модулю меньше единицы, т.е. (Лщах Ь Данный факт является критерием статической устойчивости макроэкономической системы. Система находится на границе устойчивости, если Лтах = 1 и неустойчива (экономический рост) при \Лтах\ 1.
Описанный метод позволяет осуществлять управление макроэкономической системой. Например [31], по условию максимума правого вещественного нуля характеристического полинома можно управлять увеличением темпов экономического роста. При этом в качестве варьируемых параметров могут быть приняты элементы вектора конечного спроса. Вычисление матрицы В при вариации компонент вектора конечного спроса позволяет получить траекторию движения величины Лтах. В результате возможно найти точки границ областей, определяющих темпы развития экономики по точкам пересечения величины Лщах с окружностями равного качества переходного процесса в макроэкономической системе.
Для анализа экономических моделей традиционно используются задачи оптимизации [25,31]. Описанный в работе метод, в той его части, где он идентифицирует экстремумы, может быть применен, например, для решения задач линейного программирования. К их числу относятся задачи на рациональное использование сырья и оборудования, на составление оптимального плана перевозок, работы транспорта и многие другие, принадлежащие сфере оптимального планирования. Для отыскания наименьших и наибольших значений применяется схема, использующая сортировку и условия локализации минимума (1.16) и соответственно максимума (1.17). При этом на вход метода необходимо подавать исходную функцию, а не ее модуль (как в случае определения нулей функции). Таким образом, для отыскания экстремумов функции двух переменных сохраняется схема, детально описанная в гл. 1. Схема идентификации экстремумов на основе сортировки распространяется на случай функции многих переменных [67], соответственно, в качестве целевой функции может выступать функция трех и более переменных.
Система элементарных делителей характеристической матрицы жордановой матрицы состоит из элементарных делителей ее клеток Жордана и определяет вид жордановой матрицы однозначно с точностью до порядка следования клеток по главной диагонали.
Описанный процесс нахождения элементарных делителей и инвариантных множителей не является необходимым для построения жордановой формы матрицы. Для этой цели требуется лишь дополнительно выполнить проверку, какие из кратных собственных значений матрицы (3.1) являются нулями инвариантных множителей и какова их кратность в этом случае.
Предлагается следующая схема проверки. Если определитель выделенной матрицы (содержащей на диагонали Я) преобразовать по схеме метода Леверье в полином М(Я), то последовательной подстановкой кратных собственных значений в полученный полином непосредственно проверяется является ли данное число нулем полинома М(Я) или. нет. В случае если при подстановке собственного значения Я кратности щ в полином М(Я), определяющий минор, делитель которого мы ищем, окажется, что Я/с является его нулем, то для проверки является ли Л нулем кратности 2 полинома М{Х), подставим его в первую производную М\Я). Аналогичной подстановкой в производные более высокого порядка устанавливается конкретное значения кратности нуля Я . Затем осуществляется переход к следующему собственному значению, пока не будут проверены все Я.
