Вычислительные методы алгебры и оценивания. И.В. Семушкин (2011) (1185350), страница 9
Текст из файла (страница 9)
Для этого их необходимо записать в текстовый файл.2.8 Варианты задания на лабораторный проект № 1Графики для обращения матриц:•зависимость реального и оценочного числа операций от порядка матрицы (для разных графиков использовать разные цвета);•зависимость времени обращения первым и вторым способом от порядкаматриц;•зависимость точности обращения первым и вторым способом от порядкаматриц.2.8Варианты задания на лабораторный проект № 11. LŪ-разложение на основе гауссова исключения по столбцам с выборомглавного элемента по столбцу.2. LŪ-разложение на основе гауссова исключения по столбцам с выборомглавного элемента по строке.3.
LŪ-разложение на основе гауссова исключения по столбцам с выборомглавного элемента по активной подматрице.4. L̄U -разложение на основе гауссова исключения по столбцам с выборомглавного элемента по столбцу.5. L̄U -разложение на основе гауссова исключения по столбцам с выборомглавного элемента по строке.6. L̄U -разложение на основе гауссова исключения по столбцам с выборомглавного элемента по активной подматрице.7. LŪ -разложение на основе гауссова исключения по строкам с выборомглавного элемента по строке.8.
LŪ -разложение по компактной схеме Краута с выбором главного элемента по столбцу.9. L̄U -разложение по компактной схеме Краута с выбором главного элемента по строке.10. LŪ -разложение по компактной схеме «строка за строкой» с выборомглавного элемента по строке.11. LŪ −1-разложение A = LŪ на основе жорданова исключения с выбором главного элемента по столбцу.12. LŪ −1-разложение A = LŪ на основе жорданова исключения с выбором главного элемента по строке.13. LŪ −1-разложение A = LŪ на основе жорданова исключения с выбором главного элемента по активной подматрице.512 Стандартные алгоритмы LU-разложения14. Ū L-разложение на основе гауссова исключения по столбцам с выборомглавного элемента по столбцу.15.
Ū L-разложение на основе гауссова исключения по столбцам с выборомглавного элемента по строке.16. Ū L-разложение на основе гауссова исключения по столбцам с выборомглавного элемента по активной подматрице.17. U L̄-разложение на основе гауссова исключения по столбцам с выборомглавного элемента по столбцу.18. U L̄-разложение на основе гауссова исключения по столбцам с выборомглавного элемента по строке.19.
U L̄-разложение на основе гауссова исключения по столбцам с выборомглавного элемента по активной подматрице.20. U L̄-разложение на основе гауссова исключения по строкам с выборомглавного элемента па строке.21. U L̄-разложение по компактной схеме Краута с выбором главного элемента по столбцу.22. Ū L-разложение по компактной схеме Краута с выбором главного элемента по строке.23. U L̄-разложение по компактной схеме «строка за строкой» с выборомглавного элемента по строке.24.
L̄−1U -разложение A = L̄U на основе жорданова исключения с выбором главного элемента по столбцу.25. L̄−1U -разложение A = L̄U на основе жорданова исключения с выбором главного элемента по строке.26. L̄−1U -разложение A = L̄U на основе жорданова исключения с выбором главного элемента по активной подматрице.Если нет других указаний преподавателя, выбирайте ваш вариант по вашему номеру в журнале студенческой группы.523Векторно-ориентированныеалгоритмы LU -разложения3.1Гауссово исключение и ijk-алгоритмыРассмотрим систему линейных уравненийAx = b(3.1)с невырожденной матрицей A размера (n × n).
Мы считаем A заполненнойматрицей. Разреженные матрицы расматриваются в разд. 5.Как изложено в подразд. 2.1, наиболее известной формой гауссова исключения является та, в которой система (3.1) приводится к верхнетреугольномувиду путем вычитания одних уравнений, умноженных на подходящие числа,из других уравнений; полученная треугольная система решается с помощьюобратной подстановки. Математически все это эквивалентно тому, что вначале строится разложение матрицы A, например вида A = L̄U , где L̄ является нижнетреугольной матрицей с единицами на главной диагонали, а U —верхнетреугольная матрица с ненулевыми элементами на диагонали.
Затемрешаются треугольные системыL̄y = b,U x = y.(3.2)Процесс их решения называется, соответственно, прямой и обратной подстановками.Мы сосредоточимся вначале на L̄U -разложении, поглощающем большуючасть времени всего процесса, а затем вернемся к решению треугольныхсистем. Псевдокод разложения приведен на рис. 3.1.В цикле j на рис. 3.1 кратные k-й строки текущей матрицы A вычитаютсяиз расположенных ниже строк. Эти операции представляют собой триады,в которых векторами являются строки матрицы A [8].3 Векторно-ориентированные алгоритмы LU-разложенияДля k = 1 до n − 1Для i = k + 1 до nlik = aik /akkДля j = k + 1 до naij = aij − lik akjРис. 3.1.
Строчно ориентированнаясхема L̄U-разложенияДля k = 1 до n − 1Для s = k + 1 до nlsk = ask /akkДля j = k + 1 до nДля i = k + 1 до naij = aij − lik akjРис. 3.2. Столбцово ориентированнаясхема L̄U-разложенияОпределение 3.1. Триадой называют операцию вида a + αb, где a иb суть векторы, а α — скаляр 1.Определение триады появилось в связи с использованием векторных компьютеров 2 , требующих, чтобы векторы располагались в последовательноадресуемых ячейках памяти. Для алгоритма на рис. 3.1 удобно предположить, что A хранится по строкам.
Соответственно этому, схема на рис. 3.1названа строчно ориентированной. В ней посредством триад осуществляется модификация (т. е. обновление) строк матрицы A; на это приходитсяосновная часть работы в LU -разложении.Реальные задачи, как правило, требуют выбора главного элемента, и этоеще сильнее уменьшает скорость.
При использовании одной из стратегийчастичного выбора мы должны на первом шаге просмотреть первый столбец в поисках максимального по модулю элемента. Эта стратегия, соответственно, называется выбором главного элемента по столбцу, и она приводит к перестановке строк 3 . Как только положение максимального элементаопределено, соответствующую строку можно переставить с первой (точнее,текущей ведущей) строкой или изменить порядок индексации строк. Второйвариант называют неявной перестановкой строк. Как именно реализуетсястратегия выбора главного элемента, зависит от вашего варианта задания.Однако во всех вариантах лабораторных работ физическая, т.
е. явная перестановка строк (или столбцов) запрещена и должна быть заменена изменением порядка нумерации строк (или столбцов), т. е. неявной перестановкой.Это требование соответствует реальным пакетам вычислительной линейнойалгебры. т.е. так в реальности всегда и делают. В схеме на рис. 3.1 возможнывсе три стратегии выбора главного элемента (см.
подразд. 2.2).1В зарубежной литературе триаду называют также saxpy, что обозначает операцию y := ax + y изаменяет фразу: Single precision (с обычной точностью) ax Plus y.2По поводу триады и векторных компьютеров см. подразд. 3.2 и 3.3.3Подробнее о стратегиях выбора главного элемента см. подразд. 2.2.543.2 Распараллеливание вычисленийПравая часть b системы (3.1) также может обрабатываться в ходе приведения системы к треугольному виду, благодаря чему осуществляется этаппрямой подстановки в равенствах (3.2). Такая обработка правой части b,выполняемая одновременно с приведением матрицы A к треугольному виду,также запрещена во всех вариантах лабораторных работ (проектов). Этотребование тоже отвечает реальности, так как позволяет экономить значительное время в условиях, когда требуется решать одну и ту же систему(3.1) с различными правыми частями. Ситуация такого рода — обращениематрицы с помощью решения матричного уравнения AX = I, где I — единичная матрица, т.
е. нахождение X = A−1. В этом случае правые части bвводятся в уравнения (3.2) последовательно. При вычислении i-го столбцаматрицы X = A−1 каждая правая часть равна очередному (i-му) столбцуединичной матрицы. Для каждого b в (3.2) сначала решают первую систему,т.е. вычисляют y, а затем — вторую систему, т.е. вычисляют x.
Существенно,что для хранения ни y, ни x затрат памяти не требуется: их можно хранитьтам же, куда был введен вектор b.Если A хранится по столбцам, то мы изменим алгоритм LU -разложения,как это показано на рис. 3.2. На k-м шаге измененного алгоритма сначалаформируется k-й столбец матрицы L; это достигается векторной операциейделения. В самом внутреннем цикле (цикле по i) k-й столбец L, умноженныйна число, вычитается из j-го столбца текущей матрицы A; длина столбцовравна n − k.
Таким образом, основной векторной операцией снова являетсятриада, но теперь в качестве векторов выступают столбцы матрицы L итекущей матрицы A. В данный алгоритм также возможно внедрить любуюиз трех стратегий выбора главного элемента (см. подразд. 2.2).3.2Распараллеливание вычисленийВ этом разделе мы, следуя [8], излагаем некоторые понятия параллельныхвычислений, которые в практике решения линейных систем имеют большоезначение.Параллельные вычисления реализуются не на обычных (скалярных) компьютерах, какими являются все персональные компьютеры, а на векторныхили параллельных компьютерах.
Их отличает то, что операндами командкопьютера являются не отдельные числовые величины (скаляры), а целыегруппы таких величин, объединяемых в векторы или матрицы. Поэтомувекторно-матричные операции для своего выполнения требуют вызова всего553 Векторно-ориентированные алгоритмы LU-разложениялишь одной команды. Выполнение таких команд начинается, как обычно, сзагрузки операндов из памяти в векторно-матричный процессор и завершается обратным действием — записью результата операции в память. Впромежутке между этими действиями операции реализуются на аппаратном уровне в процессоре.Векторные компьютеры. В основе таких компьютеров лежит концепция конвейеризации. Это означает явное сегментирование процессора наотдельные части (сегменты), каждая из которых выполняет свою вычислительную подзадачу независимо для соответствующих частей операндов.Например, сумматор процессора для чисел с плавающей точкой разделенна шесть сегментов; каждый сегмент занят реализацией своей части операции сложения чисел.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
