1611688890-f641c9ec8276824e4686da772eb56520 (826652), страница 48
Текст из файла (страница 48)
Прямые методы решения линейных системкоторая отличается от единичной матрицы наличием одного дополнительного ненулевого элемента ri1 на месте (i, 1). Исключение поддиагональных элементов первого столбца матрицы СЛАУ — это последовательное домножение обеих частей этой системы слева на матрицы1 r 21 0 . . .001..0.1и так далее до11 0 r31 . . .,010 0 . .. 0rn1.11..,0100..01.11.Нетрудно убедиться, что умножение матриц выписанного выше ви-2923.
Численные методы линейной алгебрыда выполняется по простому правилу: ri11 01...1..0.1 · rk1 ri1= rk111....010...1....10101.1.Оно также остаётся верным в случае, когда у матриц-сомножителейна несовпадающих местах в первом столбце присутствует более одного ненулевого элемента. Следовательно, обнуление поддиагональныхэлементов первого столбца и соответствующие преобразования правойчасти в методе Гаусса — это не что иное, как умножение обеих частейСЛАУ слева на матрицу1 r21E1 = r31 . . .rn101010...1.(3.62)Аналогично, обнуление поддиагональных элементов j-го столбцаматрицы СЛАУ и соответствующие преобразования правой части мож-2933.6.
Прямые методы решения линейных системно интерпретировать как умножение системы слева на матрицуEj = 1..0.10rj+1,j...1...rnj1.(3.63)В целом метод Гаусса представляется как последовательность умножений обеих частей решаемой СЛАУ слева на матрицы Ej вида (3.63),j = 1, 2, . .
. , n − 1. При этом матрицей системы становится матрица(3.64)En−1 · · · E2 E1 A = U,которая является верхней треугольной матрицей.Коль скоро все Ej — нижние треугольные матрицы, их произведение также является нижним треугольным. Кроме того, все Ej неособенны (нижние треугольные с единицами по главной диагонали). Поэтомунеособенно и их произведение En−1 · · · E2 E1 .
Если определитьL = En−1 · · · E2 E1−1,то, как нетрудно понять, L — тоже нижняя треугольная матрица с единицами по главной диагонали. Для этой матрицы в силу (3.64) справедливо равенствоA = LU.Получается, что исходная матрица СЛАУ оказалась представленной в виде произведения нижней треугольной L и верхней треугольной U матриц.
Это представление называют треугольным разложением матрицы или LU-разложением.14 Соответственно, преобразованияматрицы A в прямом ходе метода Гаусса (3.59) можно трактовать какеё разложение на нижний треугольный L и верхний треугольный Uмножители.14 От английских слов lower (нижний) и upper (верхний). Нередко для обозначения этого же понятия можно встретить кальки с иностранных терминов — «LUфакторизация» и «LU-декомпозиция».2943. Численные методы линейной алгебрыОтметим, что если LU-разложение матрицы A исходной СЛАУ ужедано, то система Ax = b может быть переписана в равносильной формеL (U x) = b.Тогда её решение сводится к решению двух треугольных систем линейных алгебраических уравнений(Ly = b,(3.65)Ux = yс помощью прямой и обратной подстановок соответственно. В действительности LU-разложение, получаемое с помощью версии метода Гаусса (3.59)–(3.60), таково, что в нижней треугольной матрице L по диагонали стоят все единицы.
Тогда при реализации метода Гаусса на компьютере для экономии машинной памяти можно хранить треугольныесомножители L и U на месте A, так как диагональ L имеет фиксированный вид.3.6гМетод Гаусса с выборомведущего элементаИ в прямом, и в обратном ходе метода Гаусса встречаются операции деления, которые не выполнимы в случае, когда делитель равеннулю. Тогда не может быть выполнен и метод Гаусса в целом. Этотраздел посвящен тому, как модифицировать метод Гаусса, чтобы онбыл применим для решения любых СЛАУ с неособенными матрицами.Ведущим элементом в методе Гаусса называют элемент матрицырешаемой системы, на который выполняется деление при исключенииподдиагональных элементов очередного столбца.15 В алгоритме, описанном в §3.6б, ведущим всюду берётся фиксированный диагональныйэлемент ajj , вне зависимости от его значения, но желательно модифицировать метод Гаусса так, чтобы ведущий элемент, по возможности,всегда был отличен от нуля.
С другой стороны, при решении конкретных СЛАУ, даже в случае ajj 6= 0, по соображениям устойчивости алгоритма более предпочтительным иногда может оказаться выбор другогоэлемента в качестве ведущего.15 Иногдав русской математической литературе его назыают главным элементом.3.6. Прямые методы решения линейных систем295Отметим, что любое изменение порядка уравнений в системе приводит к равносильной системе уравнений, хотя при этом в матрицеСЛАУ переставляются строки и она существенно меняется.
Воспользуемся этим наблюдением для организации успешного выполнения метода Гаусса.Назовём активной подматрицей j-го шага прямого хода методаГаусса подматрицу исходной матрицы СЛАУ, образованную последними n−j+1 строками и столбцами. Именно эта подматрица подвергаетсяпреобразованиям на j-ом шаге прямого хода, тогда как первые j − 1строк и столбцов остаются уже неизменными.(j −1j −1(0активнаяподматрица0 j-ый столбецРис.
3.13. Структура матрицы СЛАУ перед началомj-го шага прямого хода метода Гаусса.Частичным выбором ведущего элемента на j-ом шаге прямого хода метода Гаусса называют его выбор, как максимального по модулюэлемента из всех элементов j-го столбца, лежащих не выше диагонали.Соответственно, частичный выбор ведущего элемента сопровождаетсянеобходимой перестановкой строк матрицы и компонент правой части(т. е. уравнений СЛАУ), когда этот максимальный по модулю элементстановится диагональным.
Следует пояснить, что именно максимальным по модулю, а не просто ненулевым, ведущий элемент выбираетсядля того, чтобы обеспечить наибольшую численную устойчивость алгоритма в условиях вычислений с конечной точностью.2963. Численные методы линейной алгебрыПредложение 3.6.1 Метод Гаусса с частичным выбором ведущегоэлемента всегда выполним для систем линейных алгебраических уравнений с неособенными квадратными матрицами.Доказательство. Преобразования прямого хода метода Гаусса сохраняют свойство определителя матрицы системы быть неравным нулю.Перед началом j-го шага метода Гаусса эта матрица имеет блочнотреугольный вид, изображённый на Рис.
3.13, и поэтому её определитель равен произведению определителей ведущей подматрицы порядка(j −1) и активной подматрицы порядка n−j +1. Следовательно, активная подматрица имеет ненулевой определитель, т. е. в первом её столбцеобязан найтись хотя бы один ненулевой элемент. Максимальный по модулю из этих ненулевых элементов также ненулевой, и его мы делаемведущим. Как следствие, прямой ход метода Гаусса выполним.Обратный ход также не встречает деления на нуль, поскольку полученная в прямом ходе верхняя треугольная матрица неособенна, т. е.все её диагональные элементы должны быть ненулевыми.Каково матричное представление метода Гаусса с выбором ведущегоэлемента? Введём элементарные матрицы перестановок1...0···1← i-ая строка1......P =(3.66)...1← j-ая строка1···0...1(называемые также матрицами транспозиции), которые получаютсяиз единичной матрицы перестановкой двух её строк (или столбцов) сномерами i и j.
Умножение на такую матрицу слева приводит к перестановке i-ой и j-ой строк, а умножение справа — к перестановке i-го иj-го столбцов. Тогда для метода Гаусса с частичным выбором ведущегоэлемента справедливо следующее матричное представление(En−1 Pn−1 ) · · · (E1 P1 )A = U,3.6. Прямые методы решения линейных систем297где Ej — матрицы преобразований вида (3.63), введённые в предыдущем разделе, а P1 , P2 , .
. . , Pn−1 — элементарные матрицы перестановок(3.66), при помощи которых выполняется необходимая перестановкастрок на 1-м, 2-м, . . . , (n − 1)-м шагах прямого хода метода Гаусса.Несмотря на то, что метод Гаусса с частичным выбором ведущего элемента теоретически всегда спасает положение, на практике длянекоторых «плохих» СЛАУ он всё-таки может работать недостаточноустойчиво. Это происходит в случае, когда ведущий элемент оказывается малым, и потому коэффициенты rij из прямого метода Гаусса(3.59) получаются большими по абсолютной величине. По этой причинедля обеспечения желаемой устойчивости вычислительного процесса пометоду Гаусса иногда имеет смысл выбирать ведущий элемент болеетщательно, чем это делается при описанном выше частичном выборе.Заметим, что ещё одним простым способом равносильного преобразования системы уравнений является перенумерация переменных.
Ейсоответствует перестановка столбцов матрицы, тогда как вектор правых частей при этом неизменен. Полным выбором ведущего элементаназывают способ его выбора, как максимального по модулю элементаиз всей активной подматрицы (а не только из её первого столбца, какбыло при частичном выборе). Полный выбор ведущего элемента сопровождается соответствующей перестановкой строк и столбцов матрицыи компонент правой части.
Метод Гаусса с полным выбором выдущегоэлемента имеет следующее матричное представление(En−1 P̌n−1 ) · · · (E1 P̌1 )AP̂1 · · · P̂n−1 = U,где P̌i — элементарные матрицы перестановок, при помощи которыхвыполняется перестановка строк, P̂j — элементарные матрицы перестановок, с помощью которых выполняется перестановка столбцов насоответствующих шагах прямого хода метода Гаусса.Напомним, что матрицей перестановок называется матрица, получающаяся из единичной матрицы перестановкой произвольного числаеё строк (или столбцов). Матрица перестановок может быть представлена как произведение нескольких элементарных матриц перестановоквида (3.66) (см. подробности, к примеру, в [7]).Теорема 3.6.1 Для неособенной матрицы A существуют матрицыперестановок P̌ и P̂ , такие чтоP̌ AP̂ = LU,2983.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
