Вычислительные методы алгебры и оценивания. И.В. Семушкин (2011) (1185350), страница 15
Текст из файла (страница 15)
Это связанос тем, что поиск (i, j)-гo элемента матрицы A в упакованной форме требуетсущественных затрат машинного времени. Следовательно, при написанииоптимальной по времени счета программы таких действий надо избегать.855 Разреженные формы LU-разложенияЭто можно сделать, если применить метод Гаусса непосредственно к упакованной форме хранения матрицы A, т. е. только к ее ненулевым элементам.Поскольку стандартный метод Гаусса (см. подразд. 3.1) оперирует состроками матрицы A, разреженные матрицы удобно хранить по строкам.Это позволит эффективно организовать такие операции, как нормировкастроки, умножение строки на число, вычитание строки, потому что в этомслучае все ненулевые элементы каждой строки матрицы A в упакованной форме хранения образуют непрерывную последовательность.
Следовательно, операции нормировки, умножения и вычитания строки можно проводить только для ненулевых элементов.Такой подход подразумевает, что ненулевые элементы матрицы A модифицируются в том порядке, в котором они хранятся в упакованной форме,что исключает затраты на поиск нужного элемента. Модификация происходит следующим образом.
Берется очередной ненулевой элемент матрицыA. Определяется его местоположение в матрице, т. е. индексы i и j. Затемс помощью дополнительных массивов обратных перестановок определяетсяместоположение этого элемента в матрице с переставленными столбцами истроками. Если в результате этот элемент лежит в активной подматрице,то он изменяется по известным формулам метода Гаусса. Здесь надо предусмотреть процедуру вставки элемента на случай появления нового ненулевого элемента и процедуру удаления элемента из упакованной формы, еслиненулевой элемент стал нулевым.
После этого обрабатывается следующийненулевой элемент матрицы A.Оптимизация по времени процедуры решения системы линейных алгебраических уравнений позволяет значительно повысить эффективность программы. Однако этого недостаточно. Оптимальной по быстродействию будетлишь та программа, где дополнительно оптимизирована процедура выбораглавного элемента. Во-первых, надо подумать над эффективным вычислением элементов матрицы Gk (или Ĝk ). Во-вторых, надо организовать вычисление этой матрицы так, чтобы исключить поиск элементов в упакованнойформе.
Только учет всех этих особенностей решения систем линейных алгебраических уравнений с разреженной матрицей коэффициентов позволитнаписать эффективную по затратам машинного времени программу.865.3 Задание на лабораторный проект № 45.3Задание на лабораторный проект № 4Написать и отладить программу, реализующую заданный вариант методаисключения с заданной схемой хранения разреженных матриц и заданнойстратегией выбора главного элемента, для численного решения систем видаAx = f . Отделить основные части программы:а) подпрограмму упаковки матрицы A;б) подпрограмму метода исключения;в) подпрограмму выбора главного элемента;г) сервисные подпрограммы.Уделить особое внимание эффективности программы (в смысле скорости счета).
Программа должна решать систему линейных алгебраическихуравнений порядка n = 200 не более чем за 3 минуты (для персональногокомпьютера 486 AT с сопроцессором). Предусмотреть пошаговое выполнениеалгоритма исключения с выводом результата на экран.Выполнить следующие пункты задания:1.
Для заданной матрицы A выдать на экран упакованную форму в соответствии со своим вариантом, построить таблицу зависимости оценочногои реального локального заполнения от номера шага исключения (для этогопредусмотреть ввод матрицы с экрана).2. Оценить точность решения систем линейных алгебраических уравнений, имеющих порядок n от 100 до 200 (через 5). Для этого сгенерироватьслучайные матрицы A (не более 10 ненулевых элементов в строке), выбратьx∗ — точное решение и образовать правые части f = Ax∗.
Провести анализточности решения как функцию от n. Результаты вывести в таблицу и награфик.Для случайного заполнения матрицы A использовать алгоритм:(а) Ненулевыми целыми числами, выбранными случайным образом изинтервала [−100; 100], заполнить обратную диагональ матрицы A.(б) В каждой строке случайным образом выбрать количество ненулевыхэлементов (от 1 до 10 с учетом элементов по пункту (а)), их местоположение(номер столбца от 1 до n) и значение (ненулевые целые числа, лежащие винтервале от −100 до 100).В качестве точного решения взять вектор x∗ = (1, 2, .
. . , n). Если прирешении системы Ax = f выяснится, что матрица A вырождена (плохо обусловлена), сгенерировать новую матрицу того же порядка и решить системулинейных алгебраических уравнений с новой матрицей A и новой правой875 Разреженные формы LU-разложениячастью. Для оценки точности решения использовать норму вектора по формуле (4.5).3. Определить скорость решения систем из пункта 2. Результаты вывестив таблицу и на график.4. Системы из пункта 2 решить методом исключения переменных двумяспособами: способ 1 — из лабораторного проекта № 1, способ 2 — излабораторного проекта № 2 (в соответствии со своим вариантом по лабораторному проекту № 1 или № 2).
В этом случае разреженная матрицадолжна размещаться в памяти ЭВМ полностью (в распакованном виде).Сравнить точность решения и затраты машинного времени, получаемые, содной стороны, в лабораторном проекте № 1 (или № 2) и, с другой стороны,в лабораторном проекте № 4.Замечание 5.1. По ходу проведения численных экспериментов наэкран дисплея должны выводиться таблицы следующего вида.Решение систем линейных алгебраических уравненийПорядокматрицыВремяТочностьЗаполненная Разреженная Заполненная РазреженнаяматрицаматрицаматрицаматрицаЗамечание 5.2.
Некоторые результаты экспериментов необходимосохранять в текстовый файл, чтобы затем вывести на экран в виде графиков.Графики решения систем линейных алгебраических уравнений:••••88зависимость точности решения от порядка матриц для способа 1ния (см. п. 4);зависимость точности решения от порядка матриц для способа 2ния (см. п. 4);зависимость времени решения от порядка матриц для способа 1ния (см.
п. 4);зависимость времени решения от порядка матриц для способа 2ния (см. п. 4).решерешерешереше-5.4 Варианты задания на лабораторный проект № 4Таблица 5.1. Варианты задания на лабораторный проект № 4Видразложенияa5.4Стратегия IIabcdabcdA = L̄U12345678A = LŪ910 11 12 13 1415 16A = Ū L17 18 19 20 21 2223 24A = U L̄25 26 27 28 29 3031 32A = LŪ в виде L, Ū −133 34 35 36 37 3839 40A = U L̄ в виде L̄−1 , U41 42 43 44 45 4647 48——c—d—bСтратегия Iсхемасхемасхемасхема1234храненияхраненияхраненияхраненияразреженнойразреженнойразреженнойразреженнойматрицыматрицыматрицыматрицыA;A;A;A.Варианты задания на лабораторный проект № 4Студент определяет номер свого варианта по табл.
5.1 (см. выше) соответственно своему порядковому номеру в списке учебной группы. В таблицеприведены 48 номеров вариантов задания на лабораторный проект № 4. Всеварианты различаются по следующим признакам:•стратегии I или II выбора главного элемента;•четыре схемы упаковки и хранения разреженной матрицы A;•шесть вариантов метода исключения, определяемых видом разложенияматрицы.896Разложения Холесского6.1Положительно определенные матрицыОпределение 6.1. Симметрическая матрица P , P (n, n)1, называетсяположительно определенной (ПО), если и только если xT P x > 0 для всехn-векторов x с kxk > 0.В определении 6.1 выражение xT P x есть квадратичная форма в терминахпеременных элементов некоторого (произвольного) вектора x ∈ Rn . Например, для размерности n = 3 этого вектора имеемxT P x =nPp(i, j)xixj =i,j=1= p(1, 1)x21 + 2p(1, 2)x1x2 + 2p(1, 3)x1x3 ++ p(2, 2)x22 + 2p(2, 3)x2x3 ++ p(3, 3)x23 .Этот очевидный способ раскрытия формулы для xT P x справелив и вобщем случае (для любого целого n ≥ 2), — он обобщает формулу квадратасуммы двух или более чисел.Свойства ПО матрицКогда P есть симметрическая матрица, обозначение P > 0 означает, чтоP является положительно определенной.Свойство A.
P > 0 тогда и только тогда, когда все собственные числаматрицы P положительны.1Т. е. P имеет размер (n × n).6.2 Квадратные корни из P и алгоритмы ХолесскогоСвойство B. Если P > 0, то все диагональные элементы матрицы Pположительны.Свойство C. Если матрица M невырожденная и P > 0, то M T P M > 0.Свойство D. Если P > 0, то P −1 существует и P −1 > 0.Свойство E.
Если P > 0, то матрица, полученная вычеркиванием i-йстроки и i-го столбца, также является положительно определенной.Свойство F. Если P > 0 и ρ(i, j) = p(i, j)/[p(i, i)p(j, j)]1/2 с индексами элементов i, j = 1, . . . , n при i 6= j, то |ρ(i, j)| < 1, при этом ρ(i, j)называются коэффициентами корреляции.Признаки положительной определенности матрицКритерий Сильвестра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
