Универсальные разреженные методы (стр. 1 )

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

«КУБАНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»

(ФГБОУ ВПО «КубГУ»)

Кафедра вычислительных технологий

УНИВЕРСАЛЬНЫЕ РАЗРЕЖЕННЫЕ МЕТОДЫ

Краснодар 2014

СОДЕРЖАНИЕ

ВВЕДЕНИЕ………………………………………………………………………..5

ГЛАВА 1. Системы линейных алгебраических уравнений…………………….6

1.1 Задача решения системы линейных алгебраических уравнений……6

1.2 Методы решения систем линейных алгебраических уравнений…....7

1.3 Итерационные методы…………………………………………………8

1.3.1 Метод Якоби…………………………………………………...9

1.3.2 Метод Гаусса – Зейделя……………………………………...10

1.4 Прямые методы………………………………………………………..11

1.4.1 Матричный метод…………………………………………….12

1.4.2 Метод гауссова исключения………………………………...13

1.4.3 Метод Холецкого…………………………………………….15

ГЛАВА 2. Применение метода Холецкого для решения СЛАУ……………..16

2.1 Положительно-определенные и неопределенные задачи ………….16

2.2 Разложение Холецкого…………………………………………...…..17

2.3 Метод внешних произведений……………………………………….19

2.4 Применение метода Холецкого к решению разреженных систем...21

2.5 Задача перестановки…………………………………………………..23

ГЛАВА 3. Теория графов и связь с матрицами………………………………..24

3.1 Некоторые сведения из теории графов……………………………...24

3.2 Способы представления графа……………………………………….25

3.3 Ассоциирование графов и матриц…………………………………...26

ГЛАВА 4. Графовая модель разложения Холецкого………………………….28

4.1 Разложение Холецкого и соответствующие изменения в графе…..28

4.2 Универсальные методы………………………………………………30

4.3 Алгоритм минимальной степени…………………………………….31

4.4 Основной алгоритм…………………………………………………...32

4.5 Практическая реализация для исследования………………………..33

4.6 Пример исследования заполнения матрицы………………………...34

4.7 Явление заполнения в матрицах с графами – деревьями…………..36

4.8 Явление заполнения в матрицах с графами специального вида…...37

4.9 Экспериментальный анализ………………………………………….39

4.10 Численный эксперимент…………………………………………….41

ЗАКЛЮЧЕНИЕ………………………………………………………………….45

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ………………………………46

ПРИЛОЖЕНИЯ…………………………………………………………………….48

ВВЕДЕНИЕ

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

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

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

ГЛАВА 1. Системы линейных алгебраических уравнений

1.1 Задача решения системы линейных алгебраических уравнений

Системой линейных алгебраических уравнений (СЛАУ) называется система уравнений вида

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

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

Или, если записать в матричных формулах,

Здесь A называется матрицей системы, ­x – столбец неизвестных, b – столбец свободных членов. В случае, когда количество свободных членов равно количеству неизвестных, матрица системы является квадратной. Такую систему линейных алгебраических уравнений называют квадратной.

1.2 Методы решения систем линейных алгебраических уравнений

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

1.3 Итерационные методы

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

Основная суть таких методов – это поиск неподвижной точки некоторого матричного уравнения

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

На основании применяемого подхода, принято итерационные методы можно поделить на следующие типы:

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

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

3.  Проекционного типа. В данном случае задача решения системы сводится к задаче проектирования неизвестного вектора на некоторое пространство оптимально относительно другого некоторого пространства.

1.3.1 Метод Якоби

Данный метод является методом простой итерации для решения системы линейных алгебраических уравнений. Назван в честь Карла Густава Якоби.

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

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

Например, этого можно добиться, введя замену

Здесь E­ – единичная матрица, D – диагональная матрица, главная диагональ которой точно совпадает с главной диагональю матрицы A. Отметим необходимость неравенства нулю всех диагональных элементов матрицы A. Этого можно добиться, произведя необходимую замену переменных. Далее, итеративный процесс строится по формуле

Условием остановки алгоритма можно положить выполнение неравенства

В данном случае q можно оценить как операторную норму матрицы B, то есть

1.3.2 Метод Гаусса – Зейделя

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

В данном методе матрица системы линейных уравнений

представляется в виде суммы

Здесь матрица D – диагональная, содержащая в точности главную диагональ матрицы A. Матрицы L и U являются соответственно нижнетреугольной и верхнетреугольной, причем диагональные элементы у обеих из них – нулевые.

Итерационный процесс в методе Гаусса – Зейделя строится по формуле

Условием остановки итерационного процесса служит оценка