Разработка и исследование схем применения сортировки для поиска нулей и особенностей функций с приложением к идентификации плоских изображений

• Автор: Тюшнякова, Ирина Анатольевна
• Шифр специальности: 05.13.17, 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2006
• Место защиты: Таганрог
• Количество страниц: 197 с. : ил.

ВВЕДЕНИЕ
ГЛАВА 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. Анализ цифровых фильтров с помощью обратного гпреобразования.
2.5.2. Анализ временной функции линейной динамической системы
2.5.3. Анализ устойчивости дискретной цепи.
2.6. Сравнение метода вычисления нулей и полюсов функций на основе
сортировки с существующими методами.
2.7. Выводы.
ГЛАВА 3. АВТОМАТИЧЕСКАЯ ЛОКАЛИЗАЦИЯ СОБСТВЕННЫХ ЗНАЧЕНИЙ
МАТРИЦ НА ОСНОВЕ СОРТИРОВКИ
С ПРИЛОЖЕНИЕМ К РАСПОЗНАВАНИЮ ПЛОСКИХ ИЗОБРАЖЕНИЙ
3.1. Метод локализации и приближенного вычисления собственных значений
матриц на основе сортировки.
3.2 Приложение метода локализации собственных значений матриц на основе сортировки к экономическим исследованиям.
3.3. Алгоритм построения на основе сортировки жордановой формы матрицы.
3.3.1. Алгоритм нахождения элементарных делителей матрицы.
3.3.2. Уточнение алгоритма программного построения формы Жордана
3.4. Оценка временной сложности параллельного построения канонической формы Жордана.
3.5. Приложение метода нахождения спектра матрицы на основе сортировки к распознаванию плоских изображений.
3.5.1. Распознавание двуцветного изображения.
3.5.2. Видоизменение идентификации изображений для случая подобных матриц
3.5.3. Идентификация отпечатков пальцев.
3.5.4. Видоизменение схемы распознавания для случая цветного изображения
3.5.5. Видоизменение схемы распознавания на случай изображений произвольного размера.
3.6. Выводы.
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА


Рих а аУх. В процессе квадрирования возможны различные случаи, в зависимости от которых делается вывод о характере нулей, и производятся вычисления по заданным формулам 8. Для нахождения нулей полинома и функции х используются различные итерационные схемы 8,,, суть которых заключается в следующем. Пусть известен малый промежуток ,, в котором содержится единственный нуль х Т функции х. Ьхк еЛГ. ДЧГТТГ1 пео,у. Для упрощения положим 4х яд, гх х У1 . Уравнение х ргх имеет корень х а. Положив хп ргхп, где п О, 1,. Метод Эйткена 8 позволяет получить из данной итерации или из двух данных итераций одного и того же порядка итерации более высокого порядка следующим образом. Тогда итерация ,, Фхг имеет порядок выше г, если только выполнено условие р а л 1 0. Проблемы сходимости и единственности численного решения при использовании данной группы методов решаются и исследуются с помощью понятия о сжимающем отображении и теоремы о достаточном условии сходимости метода . Наиболее распространенными методами поиска нулей являются метод Ньютона и его модификации . Обычно за начальное приближение х берут один из концов отрезка а, Ь. Последовательность 6 будет сходиться, т. Последнее означает, что если х0 выбрано из малой окрестности нуля, то 1. МММ2. Метод Ньютона характеризуется вторым порядком сходимости вблизи нуля и первым порядком вдали от него. Метод является локально сходящимся, так как он сходится с определенной скоростью к истинному решению при условии, что стартует в достаточной близости от этого решения. Метод секущих сходится медленнее метода Ньютона хотя скорость сходимости выше линейной, однако в 7 вычисляется только функция, а в 6 надо находить и функцию, и ее производную. Поэтому объем вычислений на каждой итерации в методе секущих, вообще говоря, меньше. Идея метода секущих развивается в методе Мюллера , который заключается в построении интерполяционного полинома второй степени по трем точкам, взятым вблизи нуля. Положение минимума полинома принимается в качестве нового приближения к искомой точке нуля функции. Пусть 1,2з значения функции х в точках Х,Х2 и Х3 соответственно. Повторяя шаг, найдем новое приближение с помощью квадратичной интерполяции, оставим три ближайшие к минимуму точки и т. Процесс заканчивают, когда длина интервала неопределенности, либо относительное понижение значения функции на двух последовательных шагах становятся меньше заданной величины. Метод Мюллера в достаточной близости от нуля обладает квадратичной сходимостью. Однако, если начальный интервал неопределенности велик, аппроксимация функции с помощью полинома второй степени может оказаться слишком грубой, что приведет к замедлению сходимости. На практике чаще всего пользуются комбинированным методом Брента. На первом этапе положение нуля уточняют с помощью метода золотого сечения , гарантирующего постоянную скорость сокращения интервала неопределенности, а когда этот интервал станет достаточно малым, переходят к квадратичной интерполяции, быстро приводящей к конечному результату. Метод Брента характеризуется квадратичной скоростью сходимости в окрестностях минимума гладких функций и гарантированной линейной скоростью сходимости в случае, если попадется негладкая функция или функция с очень сложным рельефом. При применении методов выделения множителей приходится выполнять многократно деление полинома на полином. Если делитель имеет первую степень, то это удобно выполнять по схеме Горнера . Метод Лина выделения множителя x степени т из полинома 9 состоит в следующем. За следующее приближение берется этот остаток, деленный на приведенный предпоследний остаток, далее процесс повторяется до тех пор, пока коэффициенты двух последовательных приближений будут совпадать в пределах заданной точности. Условия сходимости процесса представлены в . Отыскание каждого приближения по методу Фридмана требует более чем в два раза больше операций, чем в методе Лина, но в некоторых случаях метод Фридмана имеет значительно лучшую сходимость, чем метод Лина. Рх х1 хх2. Х, xx,xX2.