Вычислительные методы алгебры и оценивания. И.В. Семушкин (2011) (1185350), страница 14
Текст из файла (страница 14)
2 спос. 1 спос. 2 теорет.Замечание 4.2. Результаты экспериментов необходимо вывести наэкран в форме следующих графиков. Для случая обращения матриц припостроении графиков использовать данные из второй таблицы.Графики решения систем линейных алгебраических уравнений:80•зависимость реального и оценочного числа операций от порядка матрицы (для разных графиков использовать разные цвета);•зависимость времени решения от порядка матриц;•зависимость точности решения от порядка матриц. При построении графиков использовать данные из первой таблицы. Для этого их необходимо записать в текстовый файл.4.5 Варианты задания на лабораторный проект № 3Графики для обращения матриц:•зависимость реального и оценочного числа операций от порядка матрицы (для разных графиков использовать разные цвета);•зависимость времени обращения первым и вторым способом от порядкаматриц;•зависимость точности обращения первым и вторым способом от порядкаматриц.4.5Варианты задания на лабораторный проект № 3В табл.
4.3 приведены 16 номеров вариантов задания на лабораторнуюработу (проект) № 3.Если нет других указаний преподавателя, выбирайте ваш вариант по вашему номеру в журнале студенческой группы.Таблица 4.3. Варианты задания на лабораторный проект № 3Видразложенияα——a—b—c—βОкаймлениеАлгоритмaОкаймлениеαАлгоритмbАлгоритмcβАлгоритмA = L̄U1234A = LŪ5678A = Ū L9101112A = U L̄13141516bизвестной части разложения;неизвестной части разложения;столбцовый;скалярных произведений;линейных комбинаций.815Разреженные формы LU -разложения5.1Упакованные формы хранения матрицДля решения систем линейных алгебраических уравнений с разреженными матрицами используются те же самые методы гауссова исключения,что и для линейных систем с заполненными матрицами. Отличие состоиттолько в выборе главного элемента и в способе хранения матрицы коэффициентов системы уравнений [10].Так как разреженные матрицы имеют небольшое число ненулевых элементов, в целях экономии оперативной памяти ЭВМ такие матрицы хранятв упакованном виде.
Рассмотрим четыре наиболее употребимых способа упаковки, используемых для хранения произвольных разреженных матриц.Пример 5.1. В качестве примера возьмем квадратную матрицу Aпорядка 6 с тринадцатью ненулевыми элементами: a11 = 1, a13 = 3, a14 = −2,a21 = 1, a25 = 5, a33 = 7, a34 = 2, a42 = −3, a46 = −1, a51 = 1, a54 = 3, a65 = 2,a66 = 2.В излагаемых ниже схемах хранения разреженной матрицы A упаковкаосуществляется по строкам.Схема 1. Каждому ненулевому элементу матрицы A ставится в соответствие запись, состоящая из двух полей. Первое поле записи содержитномер столбца, а второе — значение элемента.
Нуль во втором поле означает начало новой строки. В этом случае первое поле содержит номер новойстроки. Нули в обоих полях записи указывают на конец массива, хранящегоданную разреженную матрицу A. В соответствии с этой схемой матрица Aпримера 5.1 будет храниться в виде следующего массива:5.1 Упакованные формы хранения матриц1 0 1 1.0 3 3.0 4 −2.0 2 0 1 1.0 5 5.0 ⇒3 0 3 7.0 4 2.0 4 0 2 −3.0 6 −1.0 5 0 ⇒1 1.0 4 3.0 6 0 5 2.0 6 2.0 0 0Схема 2. Информация о матрице хранится в трех массивах. В массивеa хранятся ненулевые элементы матрицы A. В массиве b хранятся индексыстолбцов, а в массиве c — указатели индексов строк, т.
е. на k-м месте вмассиве c хранится местоположение первого ненулевого элемента k-й строкив массиве a. В соответствии с этой схемой матрица A примера 5.1 будетхраниться в виде трех массивовa = (1.0, 3.0, −2.0, 1.0, 5.0, 7.0, 2.0, −3.0, −1.0, 1.0, 3.0, 2.0, 2.0),b = (1, 3, 4, 1, 5, 3, 4, 2, 6, 1, 4, 5, 6),c = (1, 4, 6, 8, 10, 12).Схема 3.
Каждому ненулевому элементу данной матрицы однозначноставится в соответствие целое число видаλ(i, j) = (i − 1)n + j ,aij 6= 0 .(5.1)Хранение ненулевых элементов разреженной матрицы обеспечиваетсядвумя массивами. В массиве a хранятся ненулевые элементы матрицы, вмассиве b хранятся соответствующие им числа λ(i, j). В соответствии с этойсхемой матрица A примера 5.1 будет храниться в виде двух массивов:a = (1.0, 3.0, −2.0, 1.0, 5.0, 7.0, 2.0, −3.0, −1.0, 1.0, 3.0, 2.0, 2.0),b = (1, 3, 4, 7, 11, 15, 16, 20, 24, 25, 28, 35, 36).Исходная матрица по этой схеме хранения может быть восстановлена следующим образом.
Сначала определяем i как такое наименьшее целое число,чтоi ≥ λ(i, j)/n .Затем, зная i, с учетом (5.1) находим jj = λ(i, j) − (i − 1)n .(5.2)Схема 4. Для хранения каждого ненулевого элемента матрицы используется запись, состоящая из трех полей. В первом поле хранится номерстолбца, в котором стоит этот ненулевой элемент. Во втором поле хранится значение элемента, а в третьем — указатель на следующий ненулевой элемент строки или nil, если это последний ненулевой элемент в строке.835 Разреженные формы LU-разложенияТаким образом, разреженная матрица хранится в виде массива указателейна списки, а каждый список содержит все ненулевые элементы одной строки.Упакованную форму матрицы A примера 5.1 в этом случае можно схематично изобразить следующим образом.1234565.2→→→→→→1 1.01 1.03 7.02 −3.01 1.05 2.0→→→→→→3 3.05 5.04 2.06 −1.04 3.06 2.0→ 4 −2.0→ nil→ nil→ nil→ nil→ nil→ nilВыбор ведущего элементаСпособы 1–4 упаковки матриц позволяют компактно хранить матрицу Aкоэффициентов системы Ax = f .
Однако при использовании метода Гаусса(или ему подобных) в результате модификации элементов матрицы A можетзначительно возрасти число ненулевых элементов. С одной стороны, это требует дополнительной памяти для хранения новых ненулевых элементов, а сдругой — приводит к возрастанию числа арифметических операций, что влечет накопление ошибок округления.
В связи с этим обстоятельством былипредложены стратегии выбора главного элемента, позволяющие минимизировать число новых ненулевых элементов на каждом шаге метода Гаусса.Назовем локальным заполнением на (k + 1)-м шаге метода Гаусса числоэлементов матрицы A, которые были нулевыми после k-го шага и сталиненулевыми после (k + 1)-го шага метода Гаусса. Таким образом, задача заключается в выборе в качестве главного элемента такого элемента матрицыA(k) , который минимизирует локальное заполнение матрицы A на (k + 1)-мшаге (как и прежде, A(k) — активная подматрица матрицы A). При этом,чем больше множество элементов, среди которых выбирается главный, темменьше локальное заполнение. Но, с другой стороны, в качестве главногоможно брать только ненулевой элемент.
Поэтому вводится понятие допустимого элемента.Допустимым элементом на (k + 1)-м шаге метода Гаусса называется такой элемент активной подматрицы A(k) , который удовлетворяет неравенству (k) aij > ε,845.2 Выбор ведущего элементагде ε — некоторое наперед заданное положительное число. В лабораторном проекте № 4, описание которого дано ниже, надо взять ε = 10−3, еслииспользуется тип real, или ε = 10−5, если используется тип extended.Итак, среди элементов активной подматрицы A(k) в соответствии с критерием (5.2) выбирается множество допустимых элементов, а затем среди нихотыскивается элемент, минимизирующий локальное заполнение на текущемшаге.
Для этого используются следующие две стратегии выбора оптимального ведущего элемента.Стратегия I. Локальное заполнение на (k + 1)-м шаге метода Гауссабудет минимальным, если в качестве главного (ведущего) выбрать элемент(k)ast на позиции s = α + k, t = β + k, где α и β определяются из формулы (k)(k+1)Tgαβ = min{ei Gk+1 ej } для всех ai+k,j+k > ε.i,jЗдесь Gk+1 = Bk B̄kT Bk , где Bk — матрица, полученная из A(k) путем заменыненулевых элементов единицами, а B̄k = M − Bk (M — матрица, состоящаяиз единиц).
Согласно стратегии I, в качестве главного берется тот из числадопустимых элементов активной подматрицы A(k) , которому в матрице Gk+1соответствует наименьший элемент.Стратегия II. Локальное заполнение на k + 1-м шаге метода Гаусса(k)будет небольшим, если в качестве главного (ведущего) выбрать элемент ast ,на позиции s = α + k, t = β + k, где α и β определяются из формулы (k)(k+1)Tgαβ = min{ei Ĝk+1 ej } для всех ai+k,j+k > ε.i,jЗдесь Ĝk+1 = (Bk − In−k )M(Bk − In−k ), где матрицы M и Bk имеют тотже самый смысл, что и в стратегии I, а In−k обозначает единичную матрицуразмера n−k.
Хотя стратегия II не обеспечивает минимальное заполнение натекущем шаге, она очень просто реализуется на практике, и ее применениеприводит к сравнительно небольшому числу новых ненулевых элементов.Использование упакованной формы хранения матрицы A и более сложной процедуры выбора главного элемента требует значительного увеличениязатрат машинного времени, поэтому перенос процедур и функций из лабораторного проекта № 1, осуществляющих решение системы линейных алгебраических уравнений, не даст оптимальный по времени результат.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
