Зазначено, що стійке адресне сортування використовується для приблизного обчислювання нулів та екстремумів функцій однієї та двох змінних. Висвітлено новий метод локалізації та приблизного обчислювання всіх коренів багаточлена довільного ступеня. Метод включає випадок погано відділених коренів, відрізняється обчислювальною стійкістю та максимальним паралелзімом.

Індекс рубрикатора НБУВ: З973.41-01

Шифр НБУВ: Ж29114 Пошук видання у каталогах НБУВ 

The article is devoted to program method of application parallelizing internal sorting on a key for localization and the approximate computation of polynomials' zeroes with the appendix to search and recognition. The method defines multiplicity of zeroes, it is spreaded to calculation of functions' poles taking into account its order and it is applicable to determination of functions' extremes and extremal elements of numerical sequences. Search patterns and recognition of images to extreme attributes are under construction on this basis. Time complexity of consecutive and parallel realization of method is estimated. Stability of the offered patterns is proved and verified experimentally.

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

Ключ. слова: параллельные алгоритмы, временная сложность, линейная алгебра, линейные дифференциальные уравнения, устойчивость
Індекс рубрикатора НБУВ: В192.18

Рубрики:

Метод ітерації

Шифр НБУВ: Ж29144 Пошук видання у каталогах НБУВ 

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

Викладено метод застосування стійкого адресного сортування для локалізації та наближеного обчислення дійсних і комплексних нулів багаточленів. У довільній області метод дозволяє програмно локалізувати і з високою точністю наближення обчислити всі нулі багаточлена, включаючи випадок їх поганої взаємної відокремленості. У процесі локалізації меж області всіх нулів динамічно звужується окіл кожного нуля. Алгоритми формально описано мовою Object Pascal і реалізовано в середовищі Delphi 7. Наведено деякі верхні оцінки рівнобіжної версії методу.

Обговорено стійкість заснованої на сортуванні схеми локалізації і обчислення нулів багаточлена у разі збурення його коефіцієнтів. На випадок, коли схема втрачає частину нулів, запропоновано програмний спосіб відновлення коефіцієнтів багаточлена за значеннями його нулів. Метод переноситься на розпізнавання образів. Показано, що ознакова інформація про розпізнавальний об'єкт грунтується на підстановці, яку формує сортування із вхідних і вихідних індексів масиву його індентифікаторів.

До комп'ютерного аналізу стійкості за Ляпуновим запропоновано мультиплікативні критерії на основі різницевого наближення розв'язку задачі Коші. Критерії можна застосовувати до звичайних диференціальних рівнянь у нормальній формі, вони містять необхідні та достатні умови стійкості. Для системи лінійних рівнянь з постійними коефіцієнтами не використовується інформація про характеристичний багаточлен матриці коефіцієнтів і його коренях. Аналіз стійкості зіставляється з різницевим розв'язком моделювання накопичення похибки.

Індекс рубрикатора НБУВ: З970.6-015.1

Рубрики:

Системи оброблення даних

Шифр НБУВ: Ж16833 Пошук видання у каталогах НБУВ 

Розглянуто розпаралелювальні алгоритми локалізації та обчислення екстремумів функцій для знаходження наближених розв'язків систем нелінійних рівнянь, а також алгоритми обчислювання екстремумів різницевих розв'язків систем звичайних диференціальних рівнянь і для аналізу стійкості за Ляпуновим. Алгоритми побудовано на основі сортування послідовності зі взаємно однозначною відповідністю вхідних і вихідних індексів, екстремуми локалізуються шляхом порівняння індексів без нагромадження похибки.

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

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