Вычислительные методы алгебры и оценивания. И.В. Семушкин (2011) (1185350), страница 6
Текст из файла (страница 6)
На самом делестроки матрицы A(k−1) и элементы вектора f (k−1) остаются на своих местах, а переставляются только элементы дополнительного вектора, в которомхранятся номера строк исходной матрицы, соответствующие номерам строкматрицы, т. е. элементы так называемого вектора перестановок. Все обращения к элементам матриц L, U и вектора f осуществляются через векторперестановок.Стратегия II.
Следующая стратегия (по строке) заключается в выборев качестве главного элемента максимального по модулю элемента первойстроки активной подматрицы. Затем этот элемент обменивается местами сдиагональным, что соответствует перестановке столбцов матрицы A(k−1) иэлементов вектора x. Как и в предыдущем случае, реально обмениваютсятолько элементы дополнительного вектора, в котором фиксируются перестановки столбцов матрицы A. Доступ к элементам матриц L, U и вектораx осуществляется с использованием этого вектора.312 Стандартные алгоритмы LU-разложенияСтратегия III.
Последняя стратегия выбора главного элемента (поактивной подматрице) объединяет две первые стратегии. Здесь в качествеглавного выбирается максимальный по модулю элемент активной подматрицы. В общем случае, чтобы поставить этот элемент на место диагонального, требуется обменивать столбцы и строки матрицы A(k−1), что связано свведением двух дополнительных векторов: в одном хранятся перестановкистолбцов, а в другом — перестановки строк матрицы A.Приведенные выше алгоритмы LU -разложения с учетом выбора главногоэлемента преобразуются к одному из следующих вариантов.Алгоритм 1.
LŪ-разложение по методу Гауссас выбором главного элементаДля k = 1 до nВыбираем главный элемент в A(k−1).Нормируем первую строку матрицы A(k−1).Для i = k + 1 до nВычитаем первую строку матрицы A(k−1) ,(k−1)умноженную на aik , из i-й строки.Алгоритм 2. L̄U -разложение по методу Гауссас выбором главного элементаДля k = 1 до n − 1Выбираем главный элемент в A(k−1).Нормируем первый столбец матрицы A(k−1).Для i = k + 1 до nВычитаем первую строку матрицы A(k−1)(k−1)умноженную на aikиз i-й строки.Вышеприведенные алгоритмы называют исключением по столбцам, таккак они исключают xk из всей поддиагональной части k-го столбца.Замечание 2.2. Во всех алгоритмах должно быть выполнено требование к реализации: все действия должны выполняться в одном и том жемассиве чисел. Например, в Алгоритме 1 сначала A(0) = A, а в конце наместе этой матрицы получаются нетривиальные элементы матриц L и Ū .322.2 Выбор ведущего элементаЗамечание 2.3.
Под выбором главного элемента здесь и далеепонимается любая из описанных выше трех стратегий, которая применима.Замечание 2.4. При U L-разложении матрицы A все действиявыполняются аналогично, но в обратном порядке нумерации строк истолбцов: снизу-вверх и справа-налево.Наряду с гауссовым исключением по столбцам, представленным выше,возможно проводить гауссово исключение по строкам. Это такая разновидность метода Гаусса, в которой на каждом шаге исключения изменяетсяодна строка — первая строка активной подматрицы.
Рассмотрим гауссовоисключение по строкам с выбором главного элемента по строке.Выполняем i-й шаг, т. е. работаем с i-й строкой матрицы. В ней еще небыло ни одного исключения неизвестных. Первое действие: из i-й строкивычитаем первую, умноженную на ai1; затем из i-й строки вычитаем вторую,умноженную на ai2 , и так далее; в завершение этой серии вычитаний из i-йстроки вычитаем (i − 1)-ю, умноженную на ai(i−1). Второе действие: отыскиваем главный элемент в i-й строке и осуществляем (если надо) перестановкустолбцов. Третье действие: i-ю строку нормируем (делим на ведущий элемент). Повторяя этот алгоритм n раз, получим LŪ -разложение матрицыAP . При i = 1 шаг, очевидно, неполный, т. е. без вычитаний.Таким образом, отличие гауссова исключения по строкам от гауссоваисключения по столцам сводится в алгоритме к изменению порядка действий: сначала серия вычитаний, а затем — нормировка.
Такая возможность(для варианта A = LŪ) представлена в следующем алгоритме.Алгоритм 3. LŪ -разложение по методу Гаусса (по строкам)Для k = 1 до nДля i = 1 до k − 1Вычитаем i-ю строку матрицы A,умноженную на aki , из k-й строки.Выбираем главный элемент в k-й строке.Нормируем k-ю строку матрицы A.Замечание 2.5. В описаниях алгоритмов упоминаются элементыматрицы A. Естественно, речь идет о текущих, а не об исходных значе332 Стандартные алгоритмы LU-разложенияниях элементов, занимающих указанные позиции матрицы A. Это связано свыполнением требования к реализации (см.
Замечание 2.2).2.3Компактные схемыСледующей разновидностью метода Гаусса являются компактные схемы.Первая называется компактной схемой Краута, а вторую мы будем называть компактной схемой Краута «строка за строкой». В схеме Краутана каждом шаге исключения изменяются только первый столбец и перваястрока активной подматрицы. В схеме «строка за строкой» на k-м шагеизменяется только k-я строка матрицы A.Выведем формулы схемы Краута для k-го шага.
Предположим, что ужесделаны первые k −1 шагов, т. е. определены k −1 столбец матрицы L и k −1строка матрицы Ū . Из соотношения A = LŪ для (i, j)-гo элемента имеемaij =nXlip upj .(2.5)p=1В силу треугольности матриц L и Ū при p > i имеем lip = 0 и при p > jимеем upj = 0. Тогда с учетом того, что ukk = 1, для k-го столбца матрицыA находимk−1Xaik = lik +lipupk , i ≥ k.(2.6)p=1Из (2.6) следуетlik = aik −k−1Xlipupk ,p=1i ≥ k.(2.7)Следовательно, k-й столбец матрицы L становится известен. Теперь из(2.5) для k-й строки матрицы A имеемakj = lkk ukj +k−1Xlkpupj ,j > k.(2.8)p=1Из (2.8) находимukj =34akj −k−1Xp=1lkpupj!,lkk ,j > k.(2.9)2.3 Компактные схемыТаким образом, (2.9) дает способ нахождения k-й строки матрицы Ū .
Врезультате, зная первые k − 1 столбцов матрицы L и k − 1 строк матрицыŪ , мы можем по формулам (2.7) и (2.9) определить k-й столбец матрицы Lи затем k-ю строку матрицы Ū . Первый столбец матрицы L определяетсяравенствамиli1 = ai1 , i = 1, 2, . . . , n.Это следует из (2.7) и того, что первым столбцом матрицы Ū являетсяпервый координатный вектор e1 . Здесь, как обычно, предполагаем, что еслинижний предел суммирования меньше верхнего, то значение суммы равнонулю. После этого в первом столбце выбираем главный элемент. Затем поформуламu1j = a1j /l1j , j = 2, 3, .
. . , nвычисляем первую строку матрицы Ū . Повторяя указанную последовательность действий n раз, с помощью формул (2.7) и (2.9) получаемLŪ -разложение матрицы A.Алгоритм 4. LŪ -разложение по компактной схеме КраутаДля k = 1 до nПо формуле (2.7) вычисляем k-й столбец матрицы L.Выбираем среди элементов k-го столбца главный элемент.По формуле (2.9) вычисляем k-ю строку матрицы Ū .Чтобы получить метод Краута, дающий L̄U -разложение с выбором главного элемента по строке, достаточно поменять местами формулы (2.7) и(2.9), а также последовательность вычисления столбцов матрицы L̄ и строкматрицы U . Таким образом, на k-м шаге сначала по формулеukj = akj −k−1Xp=1lkp upj ,j ≥ k,(2.10)вычисляется строка матрицы U . Затем в этой строке выбирается главныйэлемент и находится столбец матрицы L̄ по следующей формуле:!,k−1Xlip upkukk , i ≥ k.(2.11)lik = aik −p=1352 Стандартные алгоритмы LU-разложенияУпражнение 2.3.
Выведите расчетные формулы компактных схем длялюбого из альтернативных вариантов разложения: A = U L̄ или A = Ū L.Что изменяется? Дайте ответы в форме условных схем алгоритмов, представленных непосредственно до и после этого упражнения.Алгоритм 5. L̄U -разложение по компактной схеме КраутаДля k = 1 до nПо формуле (2.10) вычисляем k-ю строку матрицы U .Выбираем среди элементов k-й строки главный элемент.По формуле (2.11) вычисляем k-й столбец матрицы L̄.Компактная схема «строка за строкой», дающая LŪ-разложение матрицыA, использует те же самые формулы (2.7) и (2.9). Меняется только последовательность вычисления элементов матрицы L. Рассмотрим подробнее.Пусть уже обработаны по этому методу первые k − 1 строк матрицы A.Следовательно, мы имеем k − 1 строку матрицы L и k − 1 строку матрицыŪ .
Далее по формулам (2.7) вычисляем ненулевые элементы k-й строкиматрицы L. По формулам (2.9) без деления на диагональный элемент lkkвычисляем ненулевые элементы k-й строки матрицы Ū . Затем среди вновьвычисленных элементов, от диагонального до n-го, определяем главныйэлемент, меняем его местами с диагональным и делим элементы k-й строкиматрицы Ū на этот элемент. В результате получаем требуемое разложение.Алгоритм 6. LŪ-разложение по компактной схеме«строка за строкой»Для k = 1 до nПо формуле (2.7) вычисляем элементы k-йстроки матрицы L.По формуле (2.9) без деления на диагональныйэлемент lkk , вычисляем k-ю строку матрицы Ū .Среди элементов k-й строки (от диагональногодо n-го) определяем главный элемент.Делим на главный элемент k-ю строку матрицы Ū .362.4 Алгоритмы метода Жордана2.4Алгоритмы метода ЖорданаК последней группе методов исключения относятся алгоритмы методаЖордана.
Эти алгоритмы используют те же самые формулы, что и обычныйметод Гаусса, но в отличие от него на k-м шаге метода Жордана пересчитывают все строки матрицы A, а не только строки, находящиеся ниже ведущейстроки. Это означает полное исключение i-й переменной из всех уравнений,кроме i-го. Таким образом, метод Жордана формально дает решение системы линейных алгебраических уравнений за один проход.Теорема 2.3. Выполнение действий полного исключения в том жемассиве, где первоначально располагалась матрица A, дает то же самое разложение A = LŪ , что и метод Гаусса, но существенно в другом виде, аименно: матрица L получается, как и в методе Гаусса, но матрица Ū оказывается полученной не в «чистом виде», а в виде обратной матрицы Ū −1 и стой особенностью, что все знаки элементов матрицы Ū −1 выше диагоналиимеют неправильные (противоположные) знаки.Доказательство.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
