Разработка и исследование схем применения сортировки для поиска нулей и особенностей функций с приложением к идентификации плоских изображений тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат технических наук Тюшнякова, Ирина Анатольевна

• Тюшнякова, Ирина Анатольевна
• кандидат технических наук
• 2006

Оглавление диссертации кандидат технических наук Тюшнякова, Ирина Анатольевна

ВВЕДЕНИЕ.

ГЛАВА 1. ПРИМЕНЕНИЕ АЛГОРИТМОВ УСТОЙЧИВОЙ ПАРАЛЛЕЛЬНОЙ СОРТИРОВКИ ДЛЯ ВЫЧИСЛЕНИЯ НУЛЕЙ ПОЛИНОМОВ С УЧЕТОМ КРАТНОСТИ.

1.1. Адресные параллельные сортировки.

1.2. Применение адресной сортировки для нахождения экстремальных элементов последовательности.

1.3. Подход к локализации и вычислению нулей полиномов на основе сортировки

1.4. Схема применения сортировки для вычисления комплексных нулей полиномов с учетом кратности.

1.5. Поиск нулей полиномов с учетом кратности в произвольной области комплексной плоскости.

1.6. Временная сложность максимально параллельного алгоритма нахождения нулей полиномов с учетом кратности.

1.7. Выводы.

ГЛАВА 2. ПРИМЕНЕНИЕ СОРТИРОВКИ ДЛЯ ВЫЧИСЛЕНИЯ ПОЛЮСОВ И ВЫЧЕТОВ ФУНКЦИЙ С ПРИЛОЖЕНИЕМ К АНАЛИЗУ ЦИФРОВЫХ ФИЛЬТРОВ.~.

2.1. Вычисление полюсов комплексной функции с учетом порядка на основе сортировки.

2.2. Вычисление вычетов функций в действительных полюсах на основе сортировки.

2.2.1. Алгоритм приближенного вычисления коэффициентов ряда Лорана на основе сортировки.

2.2.2. Алгоритм вычисления коэффициентов ряда Лорана с использованием дополнительной функции.

2.2.3. Метод вычисления коэффициентов ряда Лорана с повышенной точностью

2.3. Параллельная схема определения вычетов функций в комплексных полюсах на основе сортировки.

2.4. Схема приближенного вычисления интегралов по замкнутому контуру на основе сортировки.

2.5. Схемы анализа цифровых фильтров с использованием сортировки.

2.5.1. Анализ цифровых фильтров с помощью обратного z-преобразования.

2.5.2. Анализ временной функции линейной динамической системы.

2.5.3. Анализ устойчивости дискретной цепи.

2.6. Сравнение метода вычисления нулей и полюсов функций на основе сортировки с существующими методами.

2.7. Выводы.

ГЛАВА 3. АВТОМАТИЧЕСКАЯ ЛОКАЛИЗАЦИЯ СОБСТВЕННЫХ ЗНАЧЕНИЙ

МАТРИЦ НА ОСНОВЕ СОРТИРОВКИ.

Введение диссертации (часть автореферата) на тему «Разработка и исследование схем применения сортировки для поиска нулей и особенностей функций с приложением к идентификации плоских изображений»

Актуальность проблемы. Использование средств вычислительной техники для решения задач численного анализа - развивающееся направление в области построения приближенных методов. Как правило, известные схемы опираются на методы приближенных вычислений, включающие математические приемы, открытые до появления компьютеров и ориентированные на ручное вычисление. Программная реализация таких методов зачастую сталкивается с принципиальными трудностями.

Трудности применения схем компьютерных вычислений обусловлены, во-первых, особенностями архитектуры вычислительных систем и процессоров. Общепринятым средством выполнения научных и инженерных вычислений на компьютерах является арифметика чисел с плавающей точкой. Эта арифметика обеспечивает максимальный диапазон представления числовых данных, но специфика фиксированных границ разрядной сетки влечет существенное накопление погрешности арифметических операций, при котором, в частности, результат двух или нескольких последовательных операций может не содержать уже ни одной верной цифры [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.

Классификация основных методов сортировки

Методы сортировки

Рис. 1.

Временная сложность алгоритмов будет измеряться количеством последовательных шагов их выполнения. В частности, временная сложность последовательной сортировки измеряется числом выполняемых сравнений.

Временная сложность параллельных алгоритмов будет оцениваться на модели неветвящихся параллельных программ без учета обмена. В частности, временная сложность параллельной сортировки будет оцениваться количеством последовательных сравнений с использованием обозначения T(R) = k т, где х время бинарного сравнения, k - количество последовательных сравнений, R -число используемых процессорных элементов (при описании параллельных сортировок иногда их называют компараторами).

Сортировка вставками (включением) [46] (временная сложность Ч 2

Г(1) = 0(N ), где 0(f) - класс функций, растущих не быстрее /) сортирует список, вставляя очередной элемент в нужное место уже отсортированного списка. о

Пузырьковая сортировка (T(Y) = 0(N )) сравнивает элементы попарно, переставляя между собой элементы тех пар, порядок в которых нарушен.

Сортировка Шелла [133] (r(l) = 0(iV1,5)) представляет собой многопроходную сортировку, при которой список разбивается на подсписки, каждый из которых сортируется отдельно (сортировкой вставками), причем на каждом проходе число подсписков уменьшается, а их длина растет.

Пример сортировки методом Шелла

Группы D=4

D=2 D=1

154 61 503 87 612 170 765 275

61 | | 87 154 | | 170 | | 275 503 612 765

Рис. 2.

При корневой сортировке (поразрядная сортировка, Г(1) = 0(N) [46] при условии, что длина ключа невелика по сравнению с числом ключей) список разбивается на стопки, и при каждом проходе используется отдельная часть ключа. Относительно приведенной оценки временной сложности следует сделать некоторые оговорки. Ключевым препятствием в реализации корневой сортировки служит неэффективность по памяти. Реализация стопок массивами приводит к необходимости выделения дополнительного объема памяти под 10N записей для числовых ключей, 26N записей для буквенных ключей, причем этот объем увеличивается, если в ключ могут входить произвольные символы или в буквенных ключах учитывается регистр. Кроме того, при использовании массивов требуется значительное время на копирование записей в стопки.

Пирамидальная сортировка (Г(1) = 0(N log2 N)) строит бинарное дерево, значение каждого узла в котором превышает значение потомков.

Пирамида и ее списочное представление

12110111 5 9 | 8 1 6 1 1 2 j 7 1 3 | Л

1 2 3 4 5 6 7 8 9 10 11 12 Рис. 3.

В результате наибольший элемент списка помещается в корень, при его удалении и выборе очередной пирамиды в корне оказывается следующий по величине элемент. Процесс повторяется, пока все элементы не окажутся в отсортированном списке. Сортировка слиянием (!Г(1) = 0(.ЛПо£2АО) берет два уже отсортированных списка и создает, сливая их, новый отсортированный список. 2

При сортировке подсчетом (Г(1) = 0{N )) определяются номера мест элементов множества, расстановка по которым дает сортированное множество. Быстрая сортировка (сортировка Хоара, в наихудшем случае Г(1) = 0{N ), в среднем случае Г(1) = 0(N log2 N)) представляет собой рекурсивный алгоритм, который выбирает в списке осевой элемент, а затем разбивает список на две части, состоящие из элементов соответственно меньших или больших выбранного.

Пример быстрой сортировки исходный список ттттглттгл

Ось в ячейке 6: Ось в ячейке 5: Ось в ячейке 3: Ось в ячейке 1: Ось в ячейке 8:

ШШШШШШШШ шшшшшшшш

ШШШШШШШШ шшшшшшшш шшшшшшшш

Рис. 4.

Современные методы последовательных сортировок обсуждаются в работах [99,104,130,137].

Касаясь отдельно аспекта параллелизма сортировок, отметим, что среди известных схем выделяются параллельная сортировка Бэтчера [36]

T(N)=0{\og2N)); сортировка на линейных сетях [46] (T(N)=0(N))\ четнонечетная сортировка перестановками [46] (T(N /2) = 0(N)); асинхронная конвейерная сортировка альтернативными вставками [96]. В дальнейшем в работе будут существенно использованы параллельные варианты сортировок подсчетом

58] (г(/У2/2)= 0(1)) и слиянием [61-63] (T(N2 / 4)=0(log2 N)).

Принцип построения параллельных схем сортировки можно пояснить на схеме известной сортировки деревом (рис. 5).

Каждый из текущих минимальных элементов можно найти на <п/2 процессорах за время 0{\о%2п)• После п просеиваний найденных минимумов, получаем отсортированный массив.

Помимо отмеченных, современное состояние проблем параллельных сортировок освящено в [65,94, 103, 124,131,135], где, в частности, приводятся схемы с временной сложностью Т(п) = 0(log2 п ).

Пример распараллеливания этапа сортировки деревом п элементов

Немаловажным качеством сортировок является их устойчивость. Сортировка называется устойчивой, если она обладает свойством сохранения порядка записей с одинаковыми ключами [36]. К числу устойчивых относятся, например, сортировка вставками, к числу неустойчивых - корневая, пирамидальная, быстрая. В [64] предложены такие параллельные модификации известных схем сортировок, при которых модифицированные сортировки приобретают устойчивость, включая параллельное видоизменение сортировок подсчетом и слиянием.

В рассматриваемом контексте можно поставить вопрос о применении сортировки для построения схем локализации и устойчивого вычисления нулей полиномов и функций.

Данная задача актуальна сама по себе, на ее основе решается проблема приближенного вычисления полюсов функций [48]. Аналитические функции с кратными полюсами имеют приложения в гидродинамике при рассмотрении обтекания тел возмущенным потоком [18]. Расчет нулей и полюсов функций является одной из важных задач цифровой обработки сигналов [2,12,16,21, 52]. Например, в зависимости от расположения нулей и полюсов на комплексной плоскости осуществляется анализ временных функций линейной динамической системы (рис. 6).

Значения нулей и особенностей функций требуется знать при цифровой обработке в таких областях [53,78], как акустика, звуковая локация, радиолокация, сейсмология, связь, системы передачи данных, ядерная техника и др. Области применения цифровой обработки сигналов постоянно расширяются.

Положение полюсов и соответствующие им временные функции

Задача вычисления нулей полиномов тесно связана с задачей нахождения собственных чисел матрицы (полная проблема собственных значений). На этой основе дается классическое решение задачи об устойчивости линейной системы дифференциальных уравнений с постоянной матрицей коэффициентов [17].

Приближенное нахождение нулей характеристического полинома матрицы А позволяет определить все ее собственные значения Л. Многие научно-технические задачи (физики, механики, астрономии, экономики, теории управления, радиоэлектроники) приводят к проблеме отыскания нетривиального решения однородной системы линейных алгебраических уравнений вида Ах= Лх и тех значений числового параметра Л, при которых такое решение существует [38]. Во всех явлениях неустойчивых колебаний и вибраций [34] (например, при анализе поведения мостов, зданий, летательных аппаратов и других конструкций,

Рис. 6. характеризующихся малыми смещениями от положения равновесия) проблема собственных значений играет важную роль, так как частота колебаний определяется собственными значениями некоторой матрицы, а форму этих колебаний указывают собственные векторы этой матрицы. Задачи по вычислению собственных значений матриц имеют место на этапе оптимизации одномерных систем обработки сигналов [49]. Определение спектра матрицы также необходимо при анализе некоторых экономических моделей [31,43,81].

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

Известные классические и современные методы вычисления нулей полиномов и функций [8,32,34,40] можно кратко систематизировать следующим образом.

Как правило, отыскание нулей полиномов и функций осуществляется в два этапа [8]:

1. Отделение (локализация) нулей, т.е. нахождение достаточно малых областей, в каждой из которых заключен один и только один нуль полинома. По существу это означает некоторое приближение каждого из нулей.

2. Полученное приближенное значение каждого нуля уточняется до заданной границы погрешности путем последовательных приближений.

Способы отыскания границ нулей полинома ад (1)

1=0 обусловлены рядом положений. Для нахождения границы всех нулей (действительных и комплексных) используются: теорема о числе корней алгебраического уравнения Pn{z) = 0, теорема о свойстве парной сопряженности комплексных нулей (1) [34], теорема об оценке модулей нулей полинома [8]. Границы действительных нулей возможно найти с помощью теоремы Лагранжа о верхней границе положительных нулей полинома, теоремы о нижних и верхних границах положительных и отрицательных корней алгебраического уравнения Рп{:с) = 0, теоремы Гюа о необходимом условии действительности всех корней алгебраического уравнения [34]. Точное число действительных нулей полинома

1), заключенных в данных пределах, может быть определено с помощью теорем Декарта, Штурма и Бюдана [8].

Задача отделения нулей полинома (1) заключается в том, чтобы каждый из них заключить в интервал, не содержащий других нулей полинома. Для отделения действительных нулей полинома (1) применяют способ Фурье, основанный на теореме Бюдана. Способ отделения комплексных нулей полинома (1), подробно описанный в [8], использует понятие индекса полинома относительно некоторой заданной прямой в комплексной плоскости и позволяет отделить комплексные нули, расположенные в некоторой полосе. Программная реализация схемы отделения комплексных нулей затруднительна.

Ниже приводится сравнительная характеристика наиболее часто применяемых методов вычисления нулей полиномов и функций. 1. Метод Лобачевского

Этот метод [8] позволяет найти все нули полинома п-й степени, не требуя их предварительного отделения. и

Пусть требуется найти все нули полинома Рп(х)= ^а^х , о которых 0 априори известно, что они удовлетворяют условию | Xj |>| x<i |>.>| хп |. При этом если нули сильно разделены, т.е. * = т0 на основании известных соотношений между нулями и коэффициентами полинома -xi я-сц/aQ, х2 *-a2/ai,., хп *-ап1ап\.

В случае, когда нули не разделены сильно, их возводят в высокие степени, добиваясь тем самым их сильного разделения.

Для этого проводят процесс квадрирования нулей, т.е. строят полином

Р \п (х) = с$хп + в® 1*л1 + • • • + «о!) > С) нулями которого являются квадраты нулей исходного полинома со знаком минус

11 2 ~х„), а коэффициенты данного полинома находятся по соотношению: aV=af+2i(-\yaHai+J. (3)

7=1

При этом предполагается, что dj= 0, если j<О или j>n. Преобразовав коэффициенты (2) по формуле (3), получаем полином, нулями которого являются

4 4 4 тт Х\, Х2,., хп. Продолжая этот процесс j раз, получим полином

Р^(х) = а^х" + (4) с нулями (— l)yjcf", (~\)Jх™, (-tyх™, где m = 2J, которые сильно разделены.

В процессе квадрирования возможны различные случаи, в зависимости от которых делается вывод о характере нулей, и производятся вычисления по заданным формулам [8]. Так, например, при квадрировании, признаком существования комплексных нулей является то, что коэффициент будет менять знак после некоторого шага. 2. Итерационные методы

Для нахождения нулей полинома и функции f(x) используются различные итерационные схемы [8,24,75], суть которых заключается в следующем. Пусть известен малый промежуток [cc,fi\, в котором содержится единственный нуль х = т} функции f(x). Очевидно, что нули функции f(x) будут являться корнями уравнения = 0. (5)

Из малой окрестности нуля выбирается произвольно начальное приближение Xq к корню (5) и строится последовательность х\,х2,.,хп,. с помощью соотношения: хк = (рк (х0 ), (JceN). Последовательность точек должна сходиться к нулю, что обеспечивается выбором . 2.1. Метод Чебышева

В основе метода Чебышева [8] построения итераций высших порядков для отыскания действительных корней (5) лежит представление функции x = F{y), обратной к у - fix), по формуле Тейлора, которая дает: k=l кгде а - корень (5) на отрезке [a, b\; Rr+\ - остаточный член разложения:

D / 1Л/-+1 r +1)!

Для упрощения положим i7^[/(*)] = я* (*)> (-1)* . k=1 kl

Уравнение x = (pr(x) имеет корень x = a. Положив xn+\ =(pr{xn), где n= 0, 1,., jc0 e[a,b], получим итерационный метод (г +1)- го порядка, так как р?\сс) = 0, / = 1,2,., г.

2.2. Метод Эйткена

Метод Эйткена [8] позволяет получить из данной итерации или из двух данных итераций одного и того же порядка итерации более высокого порядка следующим образом.

Пусть имеются итерации порядка г, сходящиеся к Jt = а. Построим функцию Ф(х): x-<pi(x)~ <р2(х) + (*)]' Тогда итерация = Ф(л:/2|) имеет порядок выше г, если только выполнено условие [(р[(а) - 1] [$>(«) - Ч ^ 0 •

Проблемы сходимости и единственности численного решения при использовании данной группы методов решаются и исследуются с помощью понятия о сжимающем отображении и теоремы о достаточном условии сходимости метода [34].

2.3. Метод Ньютона

Наиболее распространенными методами поиска нулей являются метод Ньютона и его модификации [24].

Однако данный метод эффективен при весьма жестких ограничениях на характер функции /(х), нули которой необходимо найти: существование второй производной функции f{x) на интервале (а,Ь)\ удовлетворение первой производной условию /'(х)ф0 для всех хе(а,Ь); знакопостоянство f'(x), f"(x) для всех х € (а,Ь).

Обычно за начальное приближение jcq берут один из концов отрезка [а, Ь\. Итерационная последовательность строится по формуле: хк = хк-1 ~ ^г/"1? »2> — • (6) f{* к) fix) fix)

Последовательность (6) будет сходиться, т. к. (р\х) = , = 0. if'ix))2

Последнее означает, что если Xq выбрано из малой окрестности нуля, то (р\х) < 1. При произвольном jc0 итерации будут сходиться, если всюду fix)f\x)\<(f\x))2.

Метод Ньютона характеризуется вторым порядком сходимости вблизи нуля и первым порядком вдали от него. Метод является локально сходящимся, так как он сходится с определенной скоростью к истинному решению при условии, что стартует в достаточной близости от этого решения.

2.4. Метод секущих

Одной из модификаций метода Ньютона является метод секущих [75], в котором производная функции /(jc) подсчитывается с помощью конечно-разностных соотношений: fixk)ixk~xk-\) / 1 о /"п **+1=*<~/(**)-/(**-,),4=1,. (7)

Метод секущих сходится медленнее метода Ньютона (хотя скорость сходимости выше линейной), однако в (7) вычисляется только функция, а в (6) надо находить и функцию, и ее производную. Поэтому объем вычислений на каждой итерации в методе секущих, вообще говоря, меньше.

2.5. Метод Мюллера

Идея метода секущих развивается в методе Мюллера [79], который заключается в построении интерполяционного полинома второй степени по трем точкам, взятым вблизи нуля. Положение минимума полинома принимается в качестве нового приближения к искомой точке нуля функции.

Пусть /1,/2,/з - значения функции f(x) в точках Х\,Х2 и JC3 соответственно. Запишем интерполяционный полином в форме Лагранжа: р2= (*-*2)(*~*з) + (*-*l)(*-*3) ^ + (*-*l)(*-*2> f

Дифференцируя это выражение и приравнивая производную к нулю, найдем положение минимума Р2 (х)

1 (*2 ~ 4)/\ + ~ *x)h + (*? ~ *2 )/3 m х----. (8)

1 (х2 ~ х3 )/l + (*3 ~ Х1 )/2 + (*1 ~ *2 )/з

Обозначим через Х4 приближение к точке минимума, рассчитанное по формуле (8). Отбросим одну из прежних точек так, чтобы оставшиеся три точки (включая новую) ограничивали минимум. Повторяя шаг, найдем новое приближение с помощью квадратичной интерполяции, оставим три ближайшие к минимуму точки и т.д. Процесс заканчивают, когда длина интервала неопределенности, либо относительное понижение значения функции на двух последовательных шагах становятся меньше заданной величины.

Метод Мюллера в достаточной близости от нуля обладает квадратичной сходимостью. Однако, если начальный интервал неопределенности велик, аппроксимация функции с помощью полинома второй степени может оказаться слишком грубой, что приведет к замедлению сходимости.

3. Метод Брента

На практике чаще всего пользуются комбинированным методом Брента. На первом этапе положение нуля уточняют с помощью метода золотого сечения [32], гарантирующего постоянную скорость сокращения интервала неопределенности, а когда этот интервал станет достаточно малым, переходят к квадратичной интерполяции, быстро приводящей к конечному результату.

Метод Брента характеризуется квадратичной скоростью сходимости в окрестностях минимума гладких функций и гарантированной линейной скоростью сходимости в случае, если попадется негладкая функция или функция с очень сложным рельефом.

Существует ряд методов выделения множителей [8] полинома q(x) = xn +а\хп~1 + . + ап\Х + ап (9) с действительными коэффициентами, позволяющих свести задачу отыскания нулей полинома (9) к решению простейших уравнений. При применении методов выделения множителей приходится выполнять многократно деление полинома на полином. Если делитель имеет первую степень, то это удобно выполнять по схеме Горнера [46].

4. Метод Лина

Метод Лина выделения множителя gm(x) степени т из полинома (9) состоит в следующем. За начальное приближение gm(x) берется некоторый полином степени т: gml=xm + b^xm~l +. + Z>(1) х + Ь® (Ю)

1,1 1 т-1 и производится деление (9) на (10) до тех пор, пока в остатке получится полином степени т - предпоследний остаток. За следующее приближение берется этот остаток, деленный на приведенный предпоследний остаток, далее процесс повторяется до тех пор, пока коэффициенты двух последовательных приближений будут совпадать в пределах заданной точности. Условия сходимости процесса представлены в [38].

5. Метод Фридмана

В методе Фридмана выделения множителя gm(x) полинома (9), если

Sm,k(x) есть приближение искомого множителя gm(x), для получения к + \)- го приближения поступают следующим образом: делят полином (9) на

Sm,k(x) так же> как и в методе Лина, но только до получения последнего остатка; полученное частное располагают по возрастающим степеням х и делят на него полином (9), расположенный также по возрастающим степеням х, до тех пор, пока в частном получится полином степени т; это частное, деленное на коэффициент при хт, и принимают за •

Отыскание каждого приближения по методу Фридмана требует более чем в два раза больше операций, чем в методе Лина, но в некоторых случаях метод Фридмана имеет значительно лучшую сходимость, чем метод Лина.

6. Метод Лагерра

Метод Лагерра [79] основывается на следующих соотношениях для полиномов:

Р„(х) = (x-xi)(x-x2).(x-x„), In|Р„(х)|= lnjjc — jcjlnjx — x21 +. + ln|x-x„|, d\n\P„(x)\ 1 1 1

I I 9 t • I

Pn yPnJ п\Рп(х)\ 1 1 1 ' л 2 tt

Рп Рп

Рп Н, dx (x-xi) (х~~хп)

Предполагают, что нуль х^ находится на расстоянии а от текущего приближения, в то время как все другие нули находятся на расстоянии Ь: x-xl = a, x-xi = b , если /= 2,3,п. Тогда п

1 п-1 - 1 п-1 тт

- + ——-G , -у + —= Н, откуда а =-, = а 6 а ^ G±-y](n-l)(nH-G2)

Знак перед корнем выбирают с таким расчетом, чтобы получить наибольшее значение знаменателя.

Метод Лагерра имеет кубическую сходимость для изолированных нулей и линейную сходимость для кратных нулей [83]. 7. Метод сопровождающей матрицы Можно доказать, что сопровождающая матрица

А = ап-1 ап-2 я ап ап

1 0 . 0 0

0 1 . . 0 0

0 0 • • . 1 0 для полинома Р(х) = ^Д/х' имеет собственные значения равные нулям 0 полинома. Именно такая вычислительная схема используется для определения нулей полиномов в пакете Maple [20,27].

Не детализируя затруднения известных математических методов, отметим, что с их помощью не удается справиться с принципиальной практической трудностью - крайне чувствительной зависимостью нулей от значений

19 коэффициентов [83]. Например, при изменении коэффициента при х на величину 2 полинома не зависимо от способа вычисления 1 теряется половина его действительных нулей [90]. Данный пример с подробностями приведен в прил. 3.3.

20

В своем большинстве математические методы имеют локальный характер, т.е. обеспечивают сходимость к решению лишь в некоторой (иногда достаточно малой) окрестности этого решения. К тому же гарантированные оценки погрешности найденного приближения к решению дать весьма непросто. Практически все классические методы предполагают большой объем вычислений, к тому же в периодической литературе их параллельные варианты отсутствуют.

8. Интервальные методы

В числе современных подходов к решению различных задач численного анализа, в том числе вычислению нулей полиномов и функций, находятся интервальные методы [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]. Не останавливаясь на всех аспектах этой широкой и актуальной тематики, охарактеризуем состояние исследований в области распознавания плоских изображений.

По классификации [39] методы распознавания представляются схемой, представленной на рис. 7.

Классификацш методов распознавания

Рис. 7.

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

Геометрический метод распознавания основан на использовании некоторой функции подобия (принадлежности) S объекта данному классу. Эта функция определяет некоторую меру близости объекта bj с координатами х = {х\,х2,.хп) к множеству эталонов ут = \у™, у™ Уп )• За меру близости принимается среднеквадратическое расстояние sL ут )= — £ (х, ут )• мт=1

Метрика d (метод измерения расстояния) в каждом отдельном случае может быть разной. Однако она должна удовлетворять условиям: d(a,b)=d(b,a); d(a,c)<d(a,b)+d(b,c); d(a,b)>0; d(a,b) = 0 при a = b. Обучение при геометрическом подходе можно трактовать как задачу определения такой оптимальной метрики, при которой минимизировалось бы среднеквадратическое расстояние l( \ 1 MmMm 2( \ d Mm{Mm-l)hfJ K-'^Hin, где ут. - /-й эталон т-то класса. Как правило, рассматривается такой класс метрик,

N ~ который описывается формулой d(a, b)= ^а)„(а„-b„) ■

Требуется найти коэффициенты оп, чтобы последнее выражение стало минимальным. При этом физический смысл коэффициентов чаще всего имеет эвристическое содержание. В общем случае схема распознавания весьма сложна. Как отмечается в [39], вследствие сложности вычислений геометрические методы обучения не находят широкого применения, а служат, в основном, для интерпретации других методов.

Одной из наиболее распространенных концепций распознавания является байесовская, она заимствуется из теории статистических решений. Применительно к задаче распознавания эта концепция может быть сформулирована следующим образом.

Имеется полная группа несовместных гипотез, роль которых при распознавании выполняют образы: А\, А2,. Л/,. А^.

Известны априорные распределения вероятностей этих гипотез, то есть известно, с какой вероятностью появляется данный образ: м

Р{А\ ),Р(А2 ),., Р(Ам ), причем, так как группа полная, то £ Р(А[)=1. 1

В результате опыта наблюдается какое-то событие j. В данном случае таким событием является появление конкретной реализации объекта. Требуется определить, как изменяется вероятность появления образов после этого опыта.

В общем случае считаются заданными условные вероятности Pibj/Ail 1 = 1,2,.,Д/, j = \,2,.,Т, требуется определить вероятность Р[А; jbj).

В [39] отмечается, что реализовать строго байесовский алгоритм обучения практически невозможно, поскольку для этого требуется запоминать многомерные законы распределения вероятностей, которые в общем случае имеют бесконечные интервалы. Поэтому на практике многомерные законы условных вероятностей аппроксимируются какими-нибудь более простыми функциями, которые легко запомнить в вычислительной машине. Тогда, по существу, получается метод дискриминантных функций. Кроме того, на практике могут применяться другие частные методы типа корреляционного и регрессионного.

Не детализируя базовые соотношения байесовского метода, подробно описанные в [39], остановимся на основных положениях метода дискриминантных функций. Этот метод имеет две модификации: метод решающих функций и метод потенциальных функций, однако идея у этих модификаций одна. Считается, что существуют поверхности условных плотностей распределения вероятностей Р(х/Aj)= РА.(х), то есть вероятностей появления значений признака х при условии, что объект принадлежит к классу А. Для упрощения запоминания этой многомерной функции ее аппроксимируют функциями, которые и называются решающими, потенциальными или дискриминантными функциями Название метода в определённой степени связано со следующей аналогией (для простоты будем считать, что распознаётся два образа). Пусть объекты являются точками xj некоторого пространства X. В эти точки будем помещать заряды + qj, если объект принадлежит образу Jj, и ~<}j, если объект принадлежит образу S2 (рис. 8).

Иллюстрация синтеза потенциальной функции в процессе обучения

- потенциальная функция, порождаемая одиночным объектом; —— суммарная потенциальная функция, порожденная обучающей последовательностью

Рис. 8.

Функцию, описывающую распределение электростатического потенциала в таком поле, можно использовать в качестве решающего правила (или для его построения). Если потенциал точки х, создаваемый единичным зарядом, находящимся в xj, равен K(x, xj), то общий потенциал в х, создаваемый п зарядами, равен g(x)= £ Я jK(x,xi), где К(х,х,) - потенциальная функция, которая убывает с ростом евклидова расстояния между х и Xj. Чаще всего в качестве потенциальной используется функция, имеющая максимум при x = xj и монотонно убывающая до нуля при

X-Xj

->оо.

Практически задача заключается в разработке методов построения потенциальных функций, если заданы набор эталонов или обучающая последовательность. Сами функции должны выбираться так, чтобы облегчить процесс их практического получения. Эта постановка задачи характерна для вероятностного распознавания. При детерминированном распознавании задается некоторое количество эталонов и требуется любой новый объект отнести к определенному классу. Здесь предполагается существование разделительных поверхностей. На этом множестве эталонов определяются потенциальные функции gi(x). Разделительная поверхность определяется из уравнений g,(x)= gj(x\ у. В методе дискриминантных функций в качестве решающего правила выбирают знак разности Agy = gt - gj. Если эта величина положительна, то объект относят к классу /, если отрицательна - к классу j.

Разделяющие функции, как правило, полагаются линейными, квадратичными или кусочно-линейными. Соответственно этому различают линейное, квадратичное и кусочно-линейное распознавание. Для линейного распознавания в общем случае разделяющая поверхность может быть записана в виде g(x) = ацх\ + о) 2х2 + • • • + сопхп + .

Процесс обучения заключается в определении коэффициентов щ.

Общей чертой разновидностей метода дискриминантных функций является некоторая неопределенность при выборе аппроксимирующих функций и эталонных последовательностей.

К числу распространенных методов распознавания образов относятся нейросетевые методы - это методы, базирующиеся на применении различных типов нейронных сетей (НС). НС в области распознавания образов и изображений находят применение для извлечения ключевых характеристик или признаков заданных образов; для классификации самих образов или уже извлечённых из них характеристик [22,41, 51,95, 101,117].

НС состоит из элементов, называемых формальными нейронами (рис. 9), которые сами по себе очень просты и связаны с другими нейронами.

Формальный нейрон х. w.

NET Г

OUT о

Рис. 9.

Каждый нейрон преобразует набор сигналов, поступающих к нему на вход, в выходной сигнал. Именно связи между нейронами, кодируемые весами, играют ключевую роль. Одним из преимуществ НС является возможность функционирования всех элементов параллельно, тем самым существенно повышается эффективность решения задачи обработки изображения. Кроме того, что НС позволяют эффективно решать многие задачи, они предоставляют мощные гибкие и универсальные механизмы обучения, что также является их преимуществом перед другими методами [110]. Обучение избавляет от необходимости выбирать ключевые признаки, их значимость и отношения между признаками. Но, тем не менее, выбор исходного представления входных данных (вектор в «-мерном пространстве, частотные характеристики, вэйвлеты и т.п.), существенно влияет на качество решения. Функционирование нейрона определяется формулами:

NET = ZwiXi, OUT = F(NET - в), i где Xj - входные сигналы, совокупность которых образует вектор х; щ - весовые коэффициенты, совокупность которых образует вектор весов w; NET -взвешенная сумма входных сигналов (значение передается на нелинейный элемент); в - пороговый уровень данного нейрона; F - нелинейная функция, называемая функцией активации.

Некоторые виды функций активации представлены ниже [85].

1. Жесткая ступенька

OUT Го, NET<e, UU NET>Q.

NUTjT

Нейроны с такой нелинейностью требуют малых вычислительных затрат. Эта функция не позволяет моделировать схемы с непрерывными сигналами. Отсутствие первой производной затрудняет применение градиентных методов для обучения таких нейронов.

2. Логистическая функция (сигмоида)

OUT оит=1

1 + е

-NET

HNET

Применяется для сетей с непрерывными сигналами, позволяет обучать сеть градиентными методами. Диапазон выходных значений от 0 до 1 несимметричен, из-за этого обучение значительно замедляется. 3. Гиперболический тангенс

OUT 1т

OUT =

NET -NET e —e

NET , -NET e +e

HNET

Также применяется для сетей с непрерывными сигналами. Функция симметрична относительно точки (0, 0), это преимущество по сравнению с сигмоидой.

4. Пологая ступенька оит=\

О,

NET-в А !

1,

NET< 0, e<NET<0 + A, о., NET>0 + А.

Функция рассчитывается легко, но имеет разрывную производную, что усложняет алгоритм обучения. 5. SOFTMAX - функция

OUT = eNET »NET'

Здесь суммирование производится по всем нейронам данного слоя сети. Такой выбор функции обеспечивает сумму выходов слоя, равную единице при любых значениях сигналов NET} данного слоя, что позволяет трактовать OUT} как вероятности событий, совокупность которых образует полную группу.

Нейроны могут объединяться в сети различным образом. Самым распространенным видом сети является многослойный перцептрон (рис. 10).

Многослойный перцептрон

Рис. 10.

Различные модификации многослойных машин различаются числом слоев, количеством пороговых логических блоков в каждом слое и степенью настраиваемости этих блоков для каждого слоя [102,114]. Проблематична сходимость алгоритмов обучения в общем случае, однако эмпирически установлено, что если машина плохо обучается, то путем увеличения числа пороговых логических блоков первого слоя всегда можно добиться того, чтобы классы образов хорошо разделялись. Следует заметить, что нет строго определенной процедуры для выбора количества нейронов и слоев в сети. Если в сети слишком мало нейронов или слоев, то сеть не обучится и ошибка при работе сети останется большой; на выходе сети не будут передаваться резкие колебания аппроксимируемой функции. Если нейронов или слоев слишком много, то быстродействие будет низким, а памяти потребуется много; сеть переобучится (выходной вектор будет передавать, например, шум или ошибочные данные); зависимость выхода от входа окажется резко нелинейной; сеть будет неспособна к обобщению.

В методах распознавания активно используется лингвистическая модель. Изображения рассматриваются состоящими из ряда частей, в качестве которых выступают их геометрические характеристики. На первом этапе производится выделение этих характеристик (рис. 11), затем составляется логическое описание изображения, в котором элементами являются характеристики форм частей изображения и характеристики из взаимного расположения.

Изображение (а) и его иерархическое структурное описание (б) р Изображение а

- 0- / И окружность О прямоугольник И

Ь е дуга а дуга b / \ 4SSy\ отрезок отрезок отрезок отрезок прямой с прямой d прямой е прямой f а) б)

Рис. 11.

Совокупность геометрических характеристик изображения и множество правил их соединения представляют собой специальный язык PDL (picture description language). Его синтаксис, приводимый в [91], имеет графическую интерпретацию, на основе которой строится распознавание. Лингвистическое распознавание часто называют структурным. Конечная цель процедур структурного распознавания - это получение структурных описаний входных объектов и, в частности, изображений. Рассматриваемый язык используется в рамках иерархического описания изображений. Простейшие элементы, из которых строятся слова, а затем и предложения, принято называть непроизводными элементами. Правила конструирования композиций из непроизводных'элементов задаются с помощью специальных грамматик, называемых грамматиками описания изображений.

Например, для т классов изображений Р], Г2,., Vm можно построить т соответствующих грамматик Gl,G2,.,Gm, таких, что цепочки, порожденные грамматикой Gj, будут представлять изображения только из класса Vj. Тогда для произвольного изображения, описываемого цепочкой X, задача распознавания сводится к вопросу: верно ли, что

XeL(Gj\ y = l,2,.,w.

Алгоритм распознавания описывается в виде

XeVj, если X е l(Gj) l(G,).

Здесь L[Gj) - язык, порожденный грамматикой Gj.

Самый простой способ распознавания состоит в сопоставлении входной цепочки, соответствующей распознаваемому изображению, с эталоном каждого образа. Цепочка X относится к тому образу, из которого взята эталонная цепочка, наилучшим образом согласующаяся с цепочкой X. В этом случае требуется либо точное совпадение цепочки X с эталоном, либо выполнения подходящего критерия согласования. Описанный подход относительно прост, однако струюурная синтаксическая информация при таком подходе используется не полностью.

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

Наиболее близким по построению к излагаемому в гл. 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. В учебном процессе кафедры информатики Таганрогского государственного педагогического института в рамках курсов «Информатика», «Информационные технологии в математике», «Численные методы», «Элементы абстрактной и компьютерной алгебры».

Апробация работы. Основные результаты работы докладывались на:

I международной научно-практической конференции «Текст в системе высшего профессионального образования» (Таганрог, 11 'ПИ, 2003 г.);

X, XI международных конференциях «Математические модели физических процессов» (Таганрог, ТГПИ, 2004,2005 гг.);

IV международной научно-практической конференции по программированию УкрПРОГ' 2004 (Украина, Киев, 2004 г.)

VII, VIII международных научно-практических конференциях «Фундаментальные и прикладные проблемы приборостроения, информатики, экономики и права» (Москва, МГАПИ, 2004,2005 гг.);

VI научно-практической конференции преподавателей, студентов, аспирантов и молодых ученых (Таганрог, ТИУиЭ, 2005 г.);

IV-й международной научно-практической конференции «Проблемы регионального управления, экономики, права и инновационных процессов в образовании» (Таганрог, ТИУиЭ, 2005 г.);

III межрегиональной научно-практической конференции студентов, аспирантов и молодых ученых «Молодежь XXI века - будущее российской науки» (Ростов, РГУ, 2005г.); международной научно-практической конференции «Модернизация отечественного педагогического образования: проблемы, подходы, решения» (Таганрог, ТГПИ, 2005 г.)

Публикации. По материалам диссертационной работы опубликовано 16 печатных работ с общим объёмом 18,9 печатных листов.

Структура и объём работы. Диссертационная работа состоит из введения, 3 глав основного раздела, списка литературы и 4 приложений. Основное содержание работы изложено на 156 страницах, включая список литературы из 137 наименований.

Заключение диссертации по теме «Теоретические основы информатики», Тюшнякова, Ирина Анатольевна

3.6. Выводы

1. Предложен метод применения сортировки для приближенного решения полной проблемы собственных значений. Схема использует метод Леверье для развертывания характеристического полинома матрицы, собственные значения автоматически идентифицируются как нули характеристического полинома на основе сортировки и программного оператора локализации минимумов по индексам отсортированных элементов.

2. На основе сортировки определяются элементарные делители матрицы и строится каноническая форма Жордана. Даны оценки временной сложности максимально параллельного алгоритма построения формы Жордана.

3. Показана применимость метода для решения оптимизационных задач и для анализа экономических моделей. Областью применения, вычислительной устойчивостью и параллелизмом предложенный метод отличается от известных.

4. Оцифрованная матрица пикселей плоского изображения рассматривается в качестве алгебраической матрицы, для которой вектор распознавания составляется из диагональных клеток жордановой формы матрицы. Помимо отличия по построению, схема дает квадратичное сжатие исходного изображения за счет диагонализации матрицы.

5. На данной основе разработана схема идентификации плоских двуцветных и цветных изображений в каноническом расположении. Схема отличается параллелизмом, применимостью к произвольному геометрическому месту точек на плоскости и позволяет идентифицировать характерные фрагменты изображения.

6. Схема распознавания модифицирована на случай изображений, матрицы которых подобны, и на случай изображений произвольного размера.

145

ЗАКЛЮЧЕНИЕ

Основной результат диссертационной работы заключается в разработке единого распараллеливаемого метода применения сортировки для поиска нулей, особенностей функций и идентификации плоских изображений.

Работа включает следующие научные результаты.

1. Разработан распараллеливаемый метод применения сортировки для устойчивой автоматической идентификации нулей полиномов с учетом их кратности, инвариантный относительно области поиска и взаимного расположения нулей.

2. Метод модифицирован для приближенного вычисления полюсов и вычетов функций и на этой основе распространяется на вычисление криволинейных интегралов по замкнутому контуру.

3. На основе сортировки разработан распараллеливаемый метод автоматической идентификации спектра матрицы, который модифицирован в метод построения канонической формы Жордана.

4. Представлено применение предложенных методов для цифровой обработки сигналов и моделей экономических исследований.

5. Разработан метод и представлена программная модель распознавания цветных изображений на основе нахождения спектра оцифрованной матрицы изображения при помощи сортировки.

6. Дано видоизменение метода распознавания на случай изображений, матрицы которых подобны, и на случай идентификации фрагментов изображений произвольного размера.

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

1. Предложенный метод применения сортировки для вычисления нулей полиномов с учетом их кратности отличается от известных по построению на основе сортировки, свойством автоматической локализации области всех нулей и каждого нуля в отдельности, параллелизмом, а также вычислительной устойчивостью.

2. Разработанная схема приближенного вычисления полюсов комплексных функций с учетом порядка использует обработку индексов отсортированных элементов, в результате не вносится вычислительная погрешность, метод достигает устойчивости, не включает ограничений на вид входной функции, отличаясь этим от известных аналогов.

3. Построенные на данной основе алгоритмы приближенного вычисления вычетов функций в полюсах отличаются от известных методов вычислительной устойчивостью и параллелизмом.

4. Предложенный метод решения полной проблемы собственных значений автоматически идентифицирует собственные значения как нули характеристического полинома на основе сортировки и программного оператора локализации минимумов по индексам отсортированных элементов.

5. Предложенная схема распознавания плоских изображений использует диагональ жордановой формы матрицы в качестве вектора распознавания, отличается от известных по построению и дает квадратичное сжатие исходного изображения за счет диагонализации матрицы.

6. Разработанная схема идентификации плоских двуцветных и цветных изображений в каноническом расположении отличается от известных параллелизмом, качеством применимости к произвольному геометрическому месту точек на плоскости и позволяет идентифицировать характерные фрагменты изображения.

Разработанные схемы заимствуют конструкцию автоматической идентификации нулей функций на основе сортировки, что означает ее применение в качестве единой основы метода, влечет устойчивость и параллелизм предложенных алгоритмов.

Практическая ценность диссертационного исследования заключается в прикладном характере предложенных методов и алгоритмов. Все предложенные методы ориентированы на компьютерную реализацию и актуальны для решения научно-технических задач в различных областях. В частности, методы приближенного вычисления нулей, полюсов и вычетов функций используются для анализа цифровых фильтров. На основе предложенных в работе схем распознавания изображений могут создаваться новые системы распознавания, ориентированные на конкретное практическое применение.

Практическое использование результатов работы.

1. В ОАО «Таганрогский завод «Прибой» для создания алгоритмического и программного обеспечения анализа гидроакустических изображений, получаемых от антенных систем высокого разрешения.

2. В госбюджетной НИР «Математические методы устойчивой параллельной обработки, поиска и распознавания», код ГРНТИ 28.23.15, регистрационный номер 01.2.00106436.

3. В учебном процессе кафедры информатики Таганрогского государственного педагогического института в рамках курсов «Информатика», «Информационные технологии в математике», «Численные методы», «Элементы абстрактной и компьютерной алгебры».

147

Список литературы диссертационного исследования кандидат технических наук Тюшнякова, Ирина Анатольевна, 2006 год

1. Алефельд Г., Херцбергер Ю. Введение в интервальные вычисления. - М.: Мир, 1987.-278 с.

2. Антонью А. Цифровые фильтры: анализ и проектирование. М.: Радио и связь, 1983.-320 с.

3. АхоА.В., Хопкрофт Д.Э., Ульман Д.Д. Структуры данных и алгоритмы. -М.: Вильяме, 2000. 384 с.

4. Барабаш Ю.Л. Вопросы статистической теории распознавания. // Под ред. Б.В. Барского. М.: Советское радио, 1967. - 400с.

5. Баскаков С.И. Радиотехнические цепи и сигналы. М.: Высшая школа, 2003. -462 с.

6. Белоусов В.А., Калядин Н.И. Обобщенная симультанная модель распознавания изображений. В кн.: Тез. докладов Всесоюзной конференции «Методы и средства обработки сложной графической информации». - Горький. - 1988. - С. 34-35.

7. Белоусов В.А., Калядин Н.И., Шумилов Е.Е. Игровые решающие правила для отношений и распознавания конечных множеств / Москва, 1996. 16 с. - Деп. в ВИНИТИ, №333-В96.

8. Березин И.С., Жидков Н.П. Методы вычислений. Т. 2. - М.: Государственное издательство физико-математической литературы, 1962. - 640 с.

9. Вайнцвайг М.Н., Полякова М.П. Ассоциативная память и пирамидальный алгоритм установления поточечного соответствия изображений // Recognition and Image Analysis, 1995,5(2), МАИК Наука/Интерпериодика, Москва.

10. Васильев В.И. Распознающие системы: Справочник. Киев: Наукова думка, 1983.-230с.

11. Введение в цифровую фильтрацию // Под ред. Р. Богнера, А. Константинидиса. -М.: Мир, 1976.-215 с.

12. Вирт Н. Алгоритмы и структуры данных. М. Мир, 1989. - 352 с.

13. ВороновскийГ.К., МахотилоК.В., Петрашев С.Н., Сергеев С.А. Генетические алгоритмы, искусственные нейронные сети и проблемы виртуальной реальности. -Харьков: ОСНОВА, 1997.

14. ГалисеевГ.В. Программирование в среде Delphi 7. Самоучитель. М.: Диалектика, 2003. - 288 с.

15. Танеев Р.М. Математические модели в задачах обработки сигналов. М.: Горячая линия - Телеком, 2002. - 83 с.

16. Гантмахер Ф.Р. Теория матриц: 5-е изд. М.: Физматлит, 2004. - 560 с.

17. Гермогенова Т.А., Терентьев А.Г. Аналитические функции с кратными полюсами на бесконечности, их приложение в гидродинамике. // Труды Математического центра им. Лобачевского. Казань, 2001.-Т.8. - С. 72-73.

18. Гиренко А.В., ЛяшенкоВ.В., Машталир В.П., Путятин Е.П. Методы корреляционного обнаружения объектов. Харьков: АО "БизнесИнформ", 1996. -112 с.

19. Говорухин В., ЦибулинВ. Компьютер в математическом исследовании. Учебный курс. СПб.: Питер, 2001. - 624 с.

20. ГолдБ., РэйдерЧ. Цифровая обработка сигналов. М.: «Сов. радио», 1973. -368 с.

21. Головко В.А. Нейроинтеллекг: Теория и применения. Книга 1. Организация и обучение нейронных сетей с прямыми и обратными связями Брест: БПИ, 1999. -260 с.

22. Горелик А.Л., СкрипкинВ.А. Методы распознавания. М.: Высшая школа, 1984.-219 с.

23. Демидович Б.П., Марон И.А. Основы вычислительной математики. Учебное пособие: М.: Наука, 1970. 664 с.

24. Денис Дж. мл., ШнабельР. Численные методы безусловной оптимизации и решения уравнений. М.: Мир, 1988. - 384 с.

25. Дуда Р., ХартП. Распознавание образов и анализ сцен. // Пер.с англ. -М.: Мир, 1978.-510 с.

26. Дьяконов В. Maple 9 в математике, физике и образовании. М.: СОЛОН, 2004. -688 с.

27. Дьяконов В. Mathcad 2001: специальный справочник. СПб.: Питер, 2002. -832 с.

28. Журавлев Ю.И., Никифоров В.В. Алгоритмы распознавания, основанные на вычислении оценок//Кибернетика.-1971.-№3.-С. 1-11.

29. Задорожный В.В. Идентификация по отпечаткам пальцев. Часть 2. / PC Magazine.Russian Edition № 2,2004.

30. Замков О.О., ТолстопятенкоА.В., ЧеремныхЮ.Н. Математические методы в экономике. М.: ДИС, 1997. - 311 с.

31. Калиткин Н.Н. Численные методы. М.: Наука, 1978. - 512 с.

32. Калмыков С.А., Шокин Ю.И., Юлдашев З.Х. Методы интервального анализа. -Новосибирск: Наука, 1986.-493 с.

33. Киреев В.И., Пантелеев А.В. Численные методы в примерах и задачах. М.: Высш. шк., 2004.-480 с.

34. Климова JI.M. Pascal 7.0. Практическое программирование. Решение типовых задач. М.: КУДИЦ-ОБРАЗ, 2000. - 528 с.

35. Кнут Д. Искусство программирования. Т.З. Сортировка и поиск (второе издание). -М.: Вильяме, 2000. 844 с.

36. Кострикин А.И. Введение в алгебру. Часть II. Основы алгебры. 2-е изд., исправл. -М.: Физико-математическая литература, 2001. - 368 с.

37. Крылов В.И., Бобков В.В., Монастырный П.И. Вычислительные методы высшей математики. Т.1. / Под ред. И.П. Мысовских. Минск: «Вышэйша школа», 1972. -584 с.

38. Кузин JI.T. Основы кибернетики: в 2-х т. Т.2. М.: Энергия, 1979. - 584 с.

39. Кулиш У., РацД., ХаммерР., ХоксМ. Достоверные вычисления. Базовые численные методы. М.: РХД, 2005. - 495 с.

40. КурейчикВ.М., Лебедев Б.К., БожичВ.И. Обучение нейронных сетей методами генетического поиска. В кн.: Труды Всероссийской конференции «Интеллектуальные информационные системы». - Воронеж. - 1999.

41. Курош А.Г. Курс высшей алгебры. М.: Наука, 1971. - 430 с.

42. Леонтьев В.В. Межотраслевая экономика. -М.: Экономика, 1997.-468 с.

43. Лорин Г. Сортировка и системы сортировки. М.: Наука, 1983. - 384 с.

44. ЛуценкоЕ.В. Теоретические основы и технология адаптивного семантического анализа в поддержке принятия решений (на примере универсальной автоматизированной системы распознавания образов "ЭЙДОС-5Л"). Краснодар: КЮИ МВД РФ, 1996. - 280с.

45. Макконнелл Дж. Анализ алгоритмов. Вводный курс. М.: Техносфера, 2002. -304 с.

46. Мальцев А.И. Основы линейной алгебры. М.: Наука, 1975. - 400 с.

47. Маркушевич А.И. Краткий курс теории аналитических функций. М.: Наука, 1978.-416 с.

48. Миронов В.Г., НемовЮ.Н. Некоторые задачи оптимизации при проектировании электронных цепей и систем. М., Вестник МЭИ, №3, 2000. -С. 82-87.

49. Назаров С.В., Мельников П.П. Программирование на MS Visual Basic. М.: Финансы и статистика, 2001. - 320 с.

50. Обработка изображений и цифровая фильтрация. / Под ред. Т. Хуанга. М.: Мир, 1979.-397 с.53.0ппенгейм А.В., Шафер Р.В. Цифровая обработка сигналов: Пер. с англ. / Под ред. СЛ. Шаца. -М.: Связь, 1979.-416 с.

51. Очков В.Ф. Mathcad 12 для студентов и инженеров. СПб.: БХВ - Санкт-Петербург, 2005. - 464 с.

52. Перегудов Ф.И., Тарасенко Ф.П. Введение в системный анализ. М.: Высшая школа, 1989.-367с.

53. Поспелов Д.А. Моделирование человеческих рассуждений в интеллектуальных системах //Лекции Всесоюз. шк. по основным проблемам искуственного интелекта и интелектуальным системам. Ч. 1. Тверь: Центр программных систем, 1990.

54. Путятин Е.П., Аверин С.И. Обработка изображений в робототехнике. М: Машиностроение, 1990. - 320 с.

55. РоммЯ.Е. Бесконфликтные и устойчивые методы детерминированной параллельной обработки / Диссертация на соискание ученой степени доктора технических наук. Таганрог: ТРТУ. - 1998. - 546 с.; ВНТИ Центр. - № 05.990.001006.

56. РоммЯ.Е. Метод вычисления нулей и экстремумов функций на основе сортировки с приложением к поиску и распознаванию. I // Кибернетика и системный анализ. -2001. -№ 4. С. 142 - 159.

57. РоммЯ.Е. Метод вычисления нулей и экстремумов функций на основе сортировки с приложением к поиску и распознаванию. II // Кибернетика и системный анализ.-2001.-№5.-С. 81 -101.

58. РоммЯ.Е. Параллельная сортировка слиянием по матрицам сравнений. I // Кибернетика и системный анализ. 1994. - № 5. - С. 3 - 23.

59. РоммЯ.Е. Параллельная сортировка слиянием по матрицам сравнений. II // Кибернетика и системный анализ. 1995. - № 4. - С. 13 - 37.

60. РоммЯ.Е. Параллельная сортировка слиянием. Приложение к вычислению нулей, экстремумов функций и распознаванию образов. Таганрог: Изд-во ТГПИ, 1998.- 190 с.

61. РоммЯ.Е., Виноградский В.В. Преобразование сортировок в форму устойчивых схем со свойствами прямой и обратной адресности / ТГПИ. Таганрог, 2003. -43 с. Деп. в ВИНИТИ 8.12.2003, № 2130-В2003.

62. РоммЯ.Е., Виноградский В.В. Преобразование сортировок к устойчивой форме без перемещения элементов и параллельное видоизменение сортировки Хоара / ТГПИ. Таганрог, 2004. - 44 с. Деп. в ВИНИТИ 17.06.2004, № 1020-В2004.

63. РоммЯ.Е., Гуревич М.Ю., Белоконова С.С., Соловьёва И.А. Вычисление нулей и полюсов функций на основе устойчивой адресной сортировки с приложением к поиску и распознаванию. // Проблемы программирования. 2004. - №2-3. - С. 462472.

64. РоммЯ.Е., Заика И.В., Соловьева И.А. Метод программной оптимизации в приложении к математическим моделям экономики. / «Проблемы регионального управления, экономики, права и инновационных процессов в образовании». Т.2. -Таганрог. 2005. - С. 17 - 26.

65. РоммЯ.Е., Соловьёва И.А. Вычисление собственных значений матриц на основе сортировки с приложением к построению нормальной жордановой формы / ТГПИ. Таганрог, 2005. - 32 с. Деп. в ВИНИТИ 17.05.2005, № 710-В2005.

66. РоммЯ.Е., Соловьева И.А. Метод вычисления нулей и полюсов функций одной комплексной переменной с учетом их кратности на основе сортировки. / ТГПИ. -Таганрог, 2003. 27 с. Деп. в ВИНИТИ 04.08.2003, № 1525-В2003.

67. РоммЯ.Е., Соловьёва И.А. Метод вычисления нулей и полюсов функции с учетом кратности на основе сортировки с приложением к приближенному вычислению интегралов по замкнутому контуру / ТГПИ. Таганрог, 2004. - 59 с. Деп. в ВИНИТИ 29.04.2004, № 730-В2004.

68. РоммЯ.Е., Соловьёва И.А. Приближенное вычисление собственных значений матриц на основе сортировки в приложении к распознаванию изображений / ТГПИ. Таганрог, 2005. - 45 с. Деп. в ВИНИТИ от 17.11.2005, № 1497-В2005.

69. РоммЯ.Е., Соловьёва И.А. Распараллеливаемый метод вычисления нулей полиномов в произвольной области комплексной плоскости / ТГПИ. Таганрог, 2005. - 51 с. Деп. в ВИНИТИ 14.02.2005, № 210-В2005.

70. РоммЯ.Е., Тюшнякова И.А. Метод вычисления собственных значений матриц на основе сортировки в приложении к распознаванию изображений // Изв. вузов. Сев.-Кавк. регион. Техн. науки. 2006. - Прил. №1. - С. 11 - 20.

71. Рудаков П.И., Сафонов В.И. "Обработка сигналов и изображений". М.: ДИАЛОГ-МИФИ, 2000. - 416 с.

72. Самарский А.А. Введение в численные методы. М.: Наука, 1987. -288 с.

73. Славин О.А., Корольков Г.В., Болотин П.В. Методы распознавания грубых объектов. В сб. "Развитие безбумажных технологий в организациях", 1999.- С. 290311.

74. Солодовников В.И. Верхние оценки сложности решения систем линейных уравнений. В кн.: Теория сложности вычислений. I: Записки научных семинаров ЛОМИ АН СССР.-Л., 1982, т. 118.-С. 159- 187.

75. Солонина А.И., Улахович Д.А., Арбузов С.М., Соловьева Е.Б. Основы цифровой обработки сигналов: 2-е изд. СПб.: БХВ - Санкт-Петербург, 2005. - 768 с.

76. Тарасевич Ю.Ю. Информационные технологии в математике. М.: СОЛОН-Пресс, 2003.- 144 с.

77. Темников Ф.Е. Теоретические основы информационной техники. -М.: Энергия, 1979.-511 с.

78. Торопцев Е.Л. Моделирование процессов экономической динамики макросистем. С.Пб.: Изд-во Гос. университета экономики и финансов, 2001. -284 с.

79. Ту Дж., Гонсалес Р. Принципы распознавания образов. М.: Мир, 1978. - 321 с.

80. Уилкинсон Дж. X. Алгебраическая проблема собственных значений. М.: Наука, 1970.-564 с.

81. Уинстон П., Искусственный интеллект. // Пер.с англ. М.: Мир, 1980. - 520 с.

82. Уоссермен Ф. Нейрокомпьютерная техника: Теория и практика, 1992. 184 с.

83. Фаддеев Д.К. Лекции по алгебре. М.: наука, 1984. - 416 с.

84. Фаддеев Д.К., ФадцееваВ.Н. Вычислительные методы линейной алгебры. -СПб: Лань, 2002.-736 с.

85. Фаронов В.В. Delphi 2005. Язык, среда, разработка приложений. СПб.: Питер, 2005.-560 с.

86. Федотов Н.Г. Методы стохастической геометрии в распознавании образов. М.: Радио и связь, 1990. - 299 с.

87. Форсайт Д.Э., Малькольм М., МоулерК. Машинные методы математических вычислений. М.: Мир, 1980. - 279 с.

88. Фу К. Структурные методы в распознавании образов. /Пер.с англ. М.: Мир, 1977.-320 с.

89. Цейтлин Г.Е. Алгоритмы адаптивной сортировки и их классификация. 4.2 // Пробл. упр. и информат. 1995. -№ 3. - С. 95-103.

90. Цейтлин Г.Е. Введение в алгоритмику. Киев: Сфера, 1998. 473 с.

91. Цейтлин Г.Е. Распараллеливание алгоритмов сортировки // Кибернетика 1989. -№ 6.-С. 67-74.

92. ЧернухинЮ.В. Искусственный интеллект и нейрокомпьютеры. Таганрог: ТРТУ, 1997.

93. ЯценкоЕ.А., МохницаА.С. Инструментальные средства конструирования синтаксически правильных параллельных алгоритмов и программ. // Проблемы программирования. 2004. - №2-3. - С. 444 - 450.

94. Arvesu J., Marcellan F., Alvarez-Nodarse R. On a modification of the Jacobi linear functional: asymptotic properties and zeroes of the corresponding orthogonal polynomials // Acta appl. math. 2002. - 71, № 2, P. 127 - 158.

95. Baase S., Van Gelder A. Computer Algorithms, Addison-Wesley Longman, Reading, MA, 2000.-436 p.

96. Biedl Th., Chan Т., DemaineE.D., Fleischer R., GolinM., King J.A., MunroJ. I. Fun-Sort —or the chaos of unordered binary search. Discrete Applied Mathematics, Volume 144, Issue 3 ,15 December 2004. - P. 231-236.

97. Bursky D. Programmable data paths speed computations // Electron Des. 1995. -43, №9.-P. 169- 170.

98. Chernukhin Y.V., SamarinM.A. Program environment for neural network modeling. Proceedings int. KRINC/LACOS Work-shop on Robot Vision, Rostov-on-Don, Russia, 21-23 May, 1996. P. 105-109.

99. FengShauhui, ShenDongri, ChenYijun. Метод идентификации на основе однослойного перцептрона // Fushun shiyou xueyuan xuebao = J. Fushun Petrol. Inst. -1999.- 19, №2-P. 58-61.

100. GasarchW., GolubE., KruskalC. Constant time parallel sorting: an empirical view. Journal of Computer and System Sciences, Volume 67, Issue 1 , August 2003, P. 63-91.

101. Gerbessiotis A.V., SiniolakisC. J. Probabilistic integer sorting. Information Processing Letters, Volume 90, Issue 4,31 May 2004.-P. 187-193.

102. Handbook of pattern recognition and computer vision / Chen C.H., Rau L.F. and WangP.S.P. (eds.). Singapore-New Jersey-London-Hong Kong: World Scientific Publishing Co. Pte. Ltd., 1995. - 984 p.

103. Hansen E.R., SenguptaS. Bounding solutions of system of equations using interval analysis // BIT. -1981.- Vol. 21. P. 203-211.

104. Hansen E.R., WalsterG.B. Global optimization using interval analysis. New York: Marcel Dekker, 2003. - 463 p.

105. Hockney Roger W. The communication challenge for MPP: Intel Paragon and Melko CS-2 // Parallel. Comput. -1994. 20, № 3. -P. 389 - 398.

106. Iannello Giulio, Mazzeo Antonino, Mazzocca Nicola. Performance analysis of distributed memory computers with parallel node architecture // J. Syst. and Software. -1995. -29, №2. -P. 107- 120.

107. Jacobsen X., Zscherpel U. and Perner P. A Comparison between Neural Networks and Decision Trees. Lecture Notes in Artificial Intelligence Machine Learning and Data Mining in Pattern Recognition, 1999. - P. 144-158.

108. JaulinL., KiefFerM., DidritO., Walter E. Applied interval analysis. London: Springer-Verlag, 2001. - 379 p.

109. Kalinina E.A., Uteshev A. Yu. Determination of the Number of Roots of a Polynomial Lying in a Given Algebraic Domain // Linear Algebra and its Applications. -1993, V.185.-P. 61 81.

110. Kobayashi Norihiko, Iwata Akira. Multimodule neural network model for higher order association // Proc. Int. Jt. Cont. Neural Networks, Nagoya, 1993. P. 233-236.

111. KohE., MetaxasD., BaldevN. Hierarchical shape representation using locally adaptive finite elements // Lect. Notes Comput. Sci. 1994. -№300. -P. 441-446.

112. KrawczykR. Newton-Algorithmen zur Besstimmung von Nullstellen mit Fehlerschranken //Computing. -1969. Vol. 4. - P. 187-201.

113. KuchariewG., Forczmanski P. Hierarchical method of Reduction of Features Dimensionality for Image Recognition and Graphical Data Retrieval // Pattern Recognition and Image Processing, 2002. Vol. 1. - P. 57-72.

114. Li S.Z. The role of key-points in finding contours // Lect. Notes Comput. Sci. -1994.-№300.-P. 371-382.

115. Miller R., Boxer L. A Unified Approach to Sequential and Parallel Algorithms. -Prentice Hall Inc., Upper Saddle River, NJ, 2000. 465 p.

116. Mills R.L. Novel method and system for pattern recognition and processing using data encoded as Fourier series in Fourier space. Engineering Applications of Artificial Intelligence, Volume 19, Issue 2, March 2006. - P. 219-234.

117. Moore R.E. Methods and applications of interval analysis. Philadelphia: SIAM, 1979.-315 p.

118. Nanni L., Lumini A. A novel method for fingerprint verification that approaches the problem as a two-class pattern recognition problem. Neurocomputing, Volume 69, Issues 7-9, March 2006, P. 846-849.

119. Nanni L., Lumini A. Two-class fingerprint matcher. Pattern Recognition, Volume 39, Issue 4, April 2006. - P. 714-716.

120. Nardelli E., Proietti G. Efficient unbalanced merge-sort. Information Sciences, Volume 176, Issue 10,22 May 2006.-P. 1321-1337.

121. Neumaier A. On Shary's algebraic approach for linear interval equations // SIAM Journal on Matrix Analysis and Applications. 2000. - Vol. 21. - P. 1156-1162.

122. Nickel К. Can we trust the results of our computing? // Mathematics for Computer Scienc; Proc. Symposium held in Paris, March 16-18, 1982. S.I.; Association francaise pour la cybernetique et technique (AFCET), 1982. - P. 167-175.

123. Paglieroni David W., Ford Gary E., Tsujimoto Eric M. The position-orientation masking approach to parametric search for template matching // IEEE Trans. Pattern Anal. And Mach. Intell. 1994. - 16, №7. - P. 740-747.

124. Petrou M. Learning in Pattern Recognition. Lecture Notes in Artificial Intelligence Machine Learning and Data Mining in Pattern Recognition, 1999. - P. 1-12.

125. Plamondon R, Srinari S. On-Line and Off-Line Handwriting Recognition: A Comprehensive Survey. IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.22, № 1, January 2000.

126. Sanguthevar Rajasekaran, Sandeep Sen. A generalization of the 0-1 principle for sorting. Information Processing Letters, Volume 94, Issue 1,15 April 2005. - P. 43-47.

127. Seiferas J. Networks for sorting multitonic sequences. Journal of Parallel and Distributed Computing,Volume 65, Issue 12, December 2005. - P. 1601-1606.

128. Semerdziev Khr. Iteration methods for simultaneous finding all roots of generalized polynomial equations // Math. Balkan. 1994. - 8, № 4. - P. 311 - 335.

129. Shell D.L. A High-Speed Sorting Procedure, Communications of the ACM, 2(7), 1959.-P. 30-32.

130. SikorskiK.A. Optimal solution of nonlinear equations. London: Oxford University Press, 2000. - 197 p.

131. Taniar D., Rahayu J.W. Parallel database sorting. Information Sciences, Volume 146, Issues 1-4, October 2002. - P. 171-219.

132. Yang Jenn-Hwai, Yang Miin-Shen. A control chart pattern recognition system using a statistical correlation coefficient method. Computers & Industrial Engineering, Volume 48, Issue 2, March 2005. - P. 205-221.

133. Yijie Han. Deterministic sorting in 0(n\og\ogn) time and linear space. Journal of Algorithms, Volume 50, Issue 1, January 2004. - P. 96-105.