Воспользуйтесь поиском к примеру Реферат        Грубый поиск Точный поиск
Вхід в абонемент


Интернет реклама УБС






Реферат на тему:

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

всего разработанным методом решения проблем в рамках автоматизации обработки информации в сложных информационных системах является ве-лики разреженные системы линейных алгебраических уравнений (ВР СЛАУ). И в практике разработки автоматизированных систем обработки информации, которые подлежит-ют анализа, существует поляна, что влияет на разработку и создание алгоритмов и программного обеспечения-для решения краевых и динамических бага-томирних полевых задач, имеющих место при решении сложных научно -инженерных проблем, распознавания образов, извлечения знаний и т.п.. С этой целью необходимо рассмотреть вопрос как теоретического обоснования методов дискретизации, так и их практической реализации с учетом: порядка аппроксимации решения и сходимости вычислительных алгоритмов. Среди множества существующих методов решения указанного класса задач особое место занимают проекционные методы. Благодаря своей достаточной универсальности, а также - ряде достоинств, проекционные методы завоевывают все большую популярность [1]. Наиболее известные из них - это методы Ритца и Галеркина [2]. Применение [3] позволяет сохранить в приближенной задачи важные свойства исходной краевой задачи, в частности, симметрии, положительной определенности, свойств теплицевих матриц и др.. Для проекционных методов решения хорошо разработана теория исследования погрешностей приближенных решений.

Как известно [1], требование задачи в пространстве скалярного произведения, нормы и свойств аддитивности и однородности приводит к определению гильбертова пространства. Рассмотрим в абстрактном гильбертовом пространстве Н с определенным скалярным добуткомом (*, *) операторной уравнение

A * x = b, (1)

где А - линейный оператор

b - заданный элемент пространства H

x - неизвестный элемент.

Пусть DAH - область определения оператора A, а HNDA - подпространство пространства Н с ограниченной размерностью. Приближенным решением уравнения (1) назовем такой элемент xHN, для которого невязка (Ax - b) ортогональная любому элементу yHN, есть

(Ax - b, y) = 0, yHN. (2)

Это соотношение, так же как и соотношение (1), позволяет получить систему алгебраических уравнений для определения приближенного решения. Действительно, пусть 1, 2, ..., N, - базис в пространстве НN. Приближенное решение будем искать в виде

где ck (k = 1, 2, ..., N) - неизвестное число.

Подставляя это представление x в (2) и полагая y последовательно равным 1, 2, ..., N, получим систему для определения ck, т.е.

i = 1, 2, ..., N. (3)

Описанный процесс поиска приближенного решения уравнения (3) называется методом Галеркина. Функции 1, 2, ..., N называются координатными функциями проекционного метода [1].

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

За последние десятилетия отношение к проекционных методов изменилось. Широкий интерес к ним был вызван созданием нового метода - метода конечных элементов. Этот метод можно рассматривать как результат синтеза двух методов - метода конечных разностей и метода Галеркина. Этот метод нашел особенно широкое применение при расчетах на прочность и продолжительность деталей, конструкций и сооружений.

За повышение сложности задачи и точности ее решения приходится расплачиваться. Одним из таких расчетов является необходимость решения больших систем линейных алгебраических уравнений (СЛАУ), возникающие в процессе применения вариационных методов. Особенностями получаемых СЛАУ являются: разреженность, положительная уверенность, симметричность (не всегда) и большой порядок.

На сегодняшний день разработано несколько достаточно мощных методов решения "Обязательства больших разреженных СЛАУ, учитывающие те или иные особенности матриц симметричность, положительную определенность, теплица матрицы и др.. Такими методами, в частности, является так называемые методы параллельных связей, неявной схемы древовидной разбивки и др.. Роззлянемо метод сечений с точки зрения метода минимизации заполнения матрицы.

Общая идея метода вложенных сечений заключается в следующем 4. Пусть А - симметричная матрица, GA - ассоциированный с ней неориенований граф. Рассмотрим разделитель S, удаление которого разбивает граф GA на две части, множества узлов чем суть С1 и С2. Если узлы S нумеровать после нумерации узлов С1 и С2, то это индуцирует разбиение соответствующим образом упорядоченной матрицы, форма которого показана на рис. 1. Сделаем теперь ключевое замечание: нулевой блок матрицы остается нулевым и после разложения. Поскольку одной из главных целей при исследовании разреженных матричных вычислений является хранение по возможности большего числа нулевых элементов или, другими словами, минимизировать заполнения матрицы, то использование разделителей указанным средством приобретает важное значение. При соответствующем их выборе можно надеяться на получение большой подматрицы, что гарантировано остается нулевой. Ту же идею можно применять и рекурсивно, сохраняя аналогичным средством нули в подматрицы.

Рекурсивное применение этой основной идеи приводит к методу, за которым закрепилась название метода вложенных сечений. В частности, эта техника была использована для разреженных систем, ассоциированные с регулярными NN-сетками, состоящие из (N-1) 2 малых элементов [4].

Рис. 1. Схема использования разделителя.

Пусть Х - множество вершин регулярной (nn)-сетки. Через S0 обозначим множество узлов сеточной линии, разделяет Х на две по возможности равные части R1 и R2. На рис. 2 изображен случай n = 10. Если сначала перечислить построчно узлы компонентов R1 и R2, а затем - узлы S0, тогда получим матричную структуру [4], изображенную на рис. 3.

86 87 88 89 90 100 40 39 38 37

81 82 83 84 85 99 36 35 34 33

76 77 78 79 80 98 32 31 30 29

71 72 73 74 75 97 28 27 26 25

66 67 68 69 70 96 24 23 22 21

61 62 63 64 65 95 20 19 18 17

56 57 58 59 60 94 16 15 14 13

51 52 53 54 55 93 12 11 10 9

46 47 48 49 50 92 8 7 6 5

41 42 43 44 45 91 4 3 2 1

Рис. 2. Одноуровневое упорядочения Рис. 3. Структура матрицы, соответствует

с помощью связей сетки (1010) одноуровневом упорядочению за. помощью сечений.

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

Sj Rj,


Страницы: 1 2