1611688890-f641c9ec8276824e4686da772eb56520 (826652), страница 49
Текст из файла (страница 49)
Численные методы линейной алгебрыгде L, U — нижняя и верхняя треугольные матрицы, причём диагональными элементами в L являются единицы. В этом представленииможно ограничиться лишь одной из матриц P̌ или P̂ .Этот результат показывает, что можно один раз переставить строкии столбцы в исходной матрице и потом уже выполнять LU-разложениепрямым ходом метода Гаусса без какого-либо специального выбора ведущего элемента. Доказательство теоремы можно найти в [11, 13, 36].3.6дСуществование LU-разложенияВ методе Гаусса с выбором ведущего элемента перестановка строки столбцов приводит к существенному изменению исходной матрицысистемы, что не всегда желательно.
Естественно задаться вопросом одостаточных условиях реализуемости метода Гаусса без перестановкистрок и столбцов. Этот вопрос тесно связан с условиями полученияLU-разложения матрицы посредством прямого хода «немодифицированного» метода Гаусса, изложенного в §3.6б.Теорема 3.6.2 Если A = (aij ) — квадратная n × n-матрица, у которой все ведущие миноры порядков от 1 до (n − 1) отличны от нуля,т. е.a11 a126= 0,...
,a11 6= 0,deta21 a22a11a12...a1,n−1 a21a22...a2,n−1 det . 6= 0........ ....an−1,1 an−1,2 . . . an−1,n−1то для A существует LU-разложение, т. е. представление её в видеA = LU— произведения нижней треугольной n×n-матрицы L и верхней треугольной n × n-матрицы U . Это LU-разложение для A единственнопри условии, что диагональными элементами в L являются единицы.Доказательство проводится индукцией по порядку n матрицы A.3.6. Прямые методы решения линейных систем299Если n = 1, то утверждение теоремы очевидно.
Тогда искомые матрицы L = (lij ) и U = (uij ) являются просто числами, и достаточновзять l11 = 1 и u11 = a11 .Пусть теорема верна для матриц размера (n − 1) × (n − 1). Тогдапредставим n × n-матрицу A в блочном виде:a11 a12 . . . a1n! a21 a22 . . . a2n An−1z,A= ... =.... ..vann..
.an1 an2 . . . annгде An−1 — ведущая (n − 1) × (n − 1)-подматрица A,z — вектор-столбец размера n − 1,v — вектор-строка размера n − 1,такие чтоa1n a2n z = . ,v = an1 an2 . . . an,n−1 .. . an−1,nТребование разложения A на треугольные множители диктует равенство!!!An−1zLn−1 0Un−1yA==·,vannxlnn0unnгде Ln−1 , Un−1 — нижняя и верхняя треугольные(n − 1) × (n − 1)-матрицы,x — вектор-строка размера n − 1,y — вектор-столбец размера n − 1.Следовательно, используя правила перемножения матриц по блокам,необходимо имеемAn−1 = Ln−1 Un−1 ,(3.67)z = Ln−1 y,(3.68)v = x Un−1 ,(3.69)ann = xy + lnn unn .(3.70)3003. Численные методы линейной алгебрыПервое из полученных соотношений выполнено в силу индукционного предположения, причём оно должно однозначно определять Ln−1и Un−1 , если потребовать по диагонали в Ln−1 единичные элементы.Далее, по условию теоремы det An−1 6= 0, а потому матрицы Ln−1 иUn−1 также должны быть неособенны.
По этой причине системы линейных уравнений относительно x и y —x Un−1 = vиLn−1 y = z,которыми являются равенства (3.68)–(3.69), однозначно разрешимы.Стоит отметить, что именно в этом месте доказательства индукционный переход неявно опирается на условие теоремы, которое требует,чтобы в матрице A все ведущие миноры порядков, меньших чем n,были ненулевыми.Найдя из (3.68)–(3.69), векторы x и y, мы сможем из соотношения(3.70) восстановить lnn и unn .
Если дополнительно потребовать lnn = 1,то значение unn находится однозначно и равно (ann − xy).В Теореме 3.6.2 не требуется неособенность всей матрицы A. Издоказательства нетрудно видеть, что при наложенных на A условияхеё LU -разложение будет существовать даже при det A = 0, но тогда вматрице U последний элемент unn будет равен нулю.В связи с матрицами, имеющими ненулевые ведущие миноры, полезно следующееОпределение 3.6.1 Квадратная n × n-матрица A = (aij ) называется строго регулярной (или строго неособенной), если все её ведущиеминоры, включая и определитель самой матрицы, отличны от нуля,т.
е.a11 a12a11 6= 0,det6= 0,... ,det A 6= 0.a21 a22Теорема 3.6.3 Пусть A — квадратная неособенная матрица. Для существования её LU-разложения необходимо и достаточно, чтобы онабыла строго регулярной.Доказательство. Достаточность мы доказали в Теореме 3.6.2.3013.6. Прямые методы решения линейных систем=00Рис. 3.14. Блочное умножение в LU-разложении матрицы.Для доказательства необходимости привлечём блочное представление треугольного разложения A = LU (см. Рис.
3.14). Задавая различные размеры ведущих подматриц, т. е. квадратных блоков, расположенных в матрицах A, L и U слева сверху, получим равенства, аналогичные (3.67). Они означают, что любая ведущая подматрица в Aесть произведение ведущих подматриц соответствующих размеров изL и U.Но L и U — неособенные треугольные матрицы, так что все их ведущие подматрицы также неособенны. Отсюда можно заключить неособенность всех ведущих подматриц в A, т. е.
строгую регулярность матрицы A.В формулировке Теоремы 3.6.2 ничего не говорится о том, реализуем ли метод Гаусса для соответствующей системы линейных алгебраических уравнений. Но нетрудно понять, что в действительности требуемое Теоремой 3.6.2 условие отличия от нуля ведущих миноров в матрице СЛАУ является достаточным для выполнимости рассмотренногов §3.6б варианта метода Гаусса.Предложение 3.6.2 Если в системе линейных алгебраических уравнений Ax = b матрица A — квадратная и строго регулярная, то метод Гаусса реализуем в применении к этой системе без перестановкистрок и столбцов.Доказательство.
В самом деле, к началу j-го шага прямого хода, накотором предстоит обнулить поддиагональные элементы j-го столбцаматрицы СЛАУ, её ведущей j × j-подматрицей является треугольная3023. Численные методы линейной алгебрыj(j(0← j-ая строка0↑ j-ый столбецРис. 3.15. Структура матрицы СЛАУ перед началомj-го шага прямого хода метода Гаусса: другой вид.матрица, которая получена из исходной ведущей подматрицы преобразованиями предыдущих j − 1 шагов метода Гаусса (см. Рис. 3.15).Эти преобразования — линейное комбинирование строк — не изменяют свойство определителя матрицы быть неравным нулю. Поэтому отличие от нуля какого-либо ведущего минора влечёт отличие от нулявсех диагональных элементов ведущей треугольной подматрицы тогоже размера в преобразованной матрице СЛАУ.
В частности, при этомвсегда ajj 6= 0, так что деление на этот элемент в алгоритмах (3.59) и(3.60) выполнимо.В общем случае проверка условий Теоремы 3.6.2 или строгой регулярности матрицы являются весьма непростыми, поскольку вычисление ведущих миноров матрицы требует немалых трудозатрат, и, посуществу, ничуть не проще самого метода Гаусса. Тем не менее, условияТеоремы 3.6.2 заведомо выполнены, к примеру, в двух важных частныхслучаях:• для СЛАУ с положительно определёнными матрицами в силу известного критерия Сильвестера,• для СЛАУ с матрицами, имеющими диагональное преобладание,в силу признака Адамара, см. §3.2е (если исходная матрица имеет3.6. Прямые методы решения линейных систем303диагональное преобладание, то его также имеют ведущие подматрицы).3.6еРазложение ХолесскогоНапомним, что квадратная n× n-матрица называется положительно определённой, если hAx, xi > 0 для любых n-векторов x.
Ясно, чтоположительно-определённые матрицы неособенны.Теорема 3.6.4 Матрица A является симметричной положительноопределённой тогда и только тогда, когда существует неособеннаянижняя треугольная матрица C, такая что A = CC ⊤ . При этомматрица C из выписанного представления единственна.Определение 3.6.2 Представление A = CC ⊤ называется разложением Холесского, а нижняя треугольная матрица C — множителемХолесского для A.Доказательство.
Пусть A = CC ⊤ и C неособенна. Тогда неособеннаматрица C ⊤ , и для любого ненулевого вектора x ∈ Rn имеем⊤hAx, xi = (Ax)⊤ x = CC ⊤ x x= x⊤ CC ⊤ x = (C ⊤ x)⊤ (C ⊤ x) = kC ⊤ xk22 > 0,поскольку C ⊤ x 6= 0. Кроме того, A симмметрична по построению. Таким образом, она является симметричной положительно определённойматрицей.16Обратно, пусть матрица A симметрична и положительно определена. В силу критерия Сильвестера все её ведущие миноры положительны, а потому на основании Теоремы 3.6.2 о существовании LUразложения мы можем заключить, что A = LU для некоторых неособенных нижней треугольной матрицы L = (lij ) и верхней треугольнойматрицы U .
Мы дополнительно потребуем, чтобы все диагональныеэлементы lii в L были единицами, так что это разложение будет дажеоднозначно определённым.16 Это рассуждение никак не использует факт треугольности C и на самом делеобосновывает более общее утверждение: произведение матрицы на её транспонированную является симметричной положительно определённой матрицей.3043. Численные методы линейной алгебрыТак какLU = A = A⊤ = LUто⊤= U ⊤ L⊤ ,U = L−1 U ⊤ L⊤ ,и далееU L⊤−1(3.71)= L−1 U ⊤ .Слева в этом равенстве стоит произведение верхних треугольных матриц, а справа — произведение нижних треугольных.
Равенство, следовательно, возможно лишь в случае, когда левая и правая его части — это диагональная матрица, которую мы обозначим через D :=diag {d1 , d2 , . . . , dn }. Тогда из (3.71) вытекаетU = L−1 U ⊤ L⊤ = DL⊤ ,и потомуA = LU = LDL⊤ .(3.72)Ясно, что в силу неособенности L и U матрица D также неособенна,так что по диагонали у неё стоят ненулевые элементы di , i = 1, 2, . . . , n.Более того, мы покажем, что все di положительны.Из (3.72) следует, что D = L−1 A (L⊤ )−1 = L−1 A (L−1 )⊤ .
Следовательно, для любого ненулевого вектора xhDx, xi = x⊤ Dx = x⊤ L−1 A (L−1 )⊤ x⊤= (L−1 )⊤ x A (L−1 )⊤ x = hA(L−1 )⊤ x, (L−1 )⊤ x i > 0,так как (L−1 )⊤ x 6= 0 в силу неособенности матрицы (L−1 )⊤ . Инымисловами, диагональная матрица D положительно определена одновременно с A. Но тогда её диагональные элементы обязаны быть положительными, так как в противном случае, если предположить, что di ≤ 0для некоторого i, то, беря вектор x равным i-му столбцу единичнойматрицы, получимhDx, xi = (Dx)⊤x = x⊤Dx = di ≤ 0.Это противоречит положительной определённости матрицы D.Как следствие, из диагональных элементов матрицы D можно извлекать квадратные корни.
Если обозначить получающуюся при этом3.6. Прямые методы решения линейных систем305√√ √√диагональную матрицу через √D := diag { d1 , d2 , . . . , dn }, то окончательно можем взять C = L D. Это представление для множителяХолесского, в действительности, единственно, так как по A при сделанных нами предположениях единственным образом определяется нижняя треугольная матрица L, а матричные преобразования, приведшиек формуле (3.72) и её следствиям, обратимы и также дают однозначноопределённый результат.3.6жМетод ХолесскогоОсновной результат предшествующего раздела мотивирует прямойметод решения систем линейных уравнений, который аналогичен методу (3.65) на основе LU-разложения. Именно, если найдено разложениеХолесского для матрицы A, то решение системы Ax = b, равносильнойCC ⊤ x = b, сводится к решению двух треугольных систем линейныхуравнений:(C y = b,C ⊤x = y.(3.73)Для решения первой системы применяем алгоритм прямой подстановки (3.57), а для решения второй системы — обратную подстановку(3.58).Но как практически найти разложение Холесского? Теорема 3.6.4носит конструктивный характер и в принципе может служить основойдля соответствующего алгоритма.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
