1611688847-5b7354cc83380cb6c671f7c9dd5f83f8 (826648), страница 11

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 11)

е. x⊤Ax > 0.Положительная определённость различных матриц, встречающихсяпри математическом моделировании естественнонаучных процессов,следует из свойств самих моделей.Например, если некоторая матрица участвует в квадратичнойформе, выражающей энергию системы.Разложение ХолесскогоТеорема о разложении ХолесскогоМатрица A является симметричной положительно определённойтогда и только тогда, когда существует неособенная нижняятреугольная матрица C, такая чтоA = CC ⊤ .При этом матрица C из выписанного представления единственна.Разложение ХолесскогоТеорема о разложении ХолесскогоМатрица A является симметричной положительно определённойтогда и только тогда, когда существует неособенная нижняятреугольная матрица C, такая чтоA = CC ⊤ .При этом матрица C из выписанного представления единственна.ОпределениеПредставление A = CC ⊤ , где C — нижняя треугольная матрица,называется разложением Холесского, а сама матрица 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 симмметрична по построению.Доказательство:Пусть 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 симмметрична по построению.Итак, 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 симмметрична по построению.Итак, A — симметричная положительно определённая матрица.Это рассуждение не использует треугольность C и обосновываетболее общее утверждение: если G — квадратная матрица, то GG⊤— симметричная положительно определённая матрица.Обратно, пусть матрица A — симметричная и положительноопределённая.Обратно, пусть матрица A — симметричная и положительноопределённая.По критерию Сильвестера все её ведущие миноры положительны,а потому на основании теоремы о существовании LU-разложенияA = LUдля некоторых неособенных нижней треугольной матрицы L = (lij )и верхней треугольной матрицы U .Обратно, пусть матрица A — симметричная и положительноопределённая.По критерию Сильвестера все её ведущие миноры положительны,а потому на основании теоремы о существовании LU-разложенияA = LUдля некоторых неособенных нижней треугольной матрицы L = (lij )и верхней треугольной матрицы U .Дополнительно потребуем, чтобы все диагональные элементы liiв L были единицами, так что это разложение будет однозначноопределённым.Так какLU = A = A⊤ = LUто⊤= U ⊤ L⊤ ,U = L−1 U ⊤ L⊤ ,и далееU L⊤−1= L−1 U ⊤ .Слева в полученном равенствестоит произведение верхних треугольных матриц,а справа — произведение нижних треугольных.(1)РавенствоU L⊤−1= L−1 U ⊤ ,следовательно, возможно лишь в случае, когда левая и правая егочасти — это диагональная матрица, которую мы обозначим черезD := diag {d1 , d2 , .

. . , dn } = U L⊤−1= L−1 U ⊤ .РавенствоU L⊤−1= L−1 U ⊤ ,следовательно, возможно лишь в случае, когда левая и правая егочасти — это диагональная матрица, которую мы обозначим черезD := diag {d1 , d2 , . . . , dn } = U L⊤−1Тогда из (1) вытекаетU = L−1 U ⊤ L⊤ = DL⊤ ,и потомуA = LU = LDL⊤ .= L−1 U ⊤ .РавенствоU L⊤−1= L−1 U ⊤ ,следовательно, возможно лишь в случае, когда левая и правая егочасти — это диагональная матрица, которую мы обозначим черезD := diag {d1 , d2 , .

. . , dn } = U L⊤−1= L−1 U ⊤ .Тогда из (1) вытекаетU = L−1 U ⊤ L⊤ = DL⊤ ,и потомуA = LU = LDL⊤ .Ясно, что в силу неособенности L и U матрица D также неособенна,так что по диагонали у неё стоят элементы di 6= 0, i = 1, 2, . . . , n.Более того, мы покажем, что все di положительны.Более того, мы покажем, что все di положительны.ИзA = LU = LDL⊤следует, чтоD = L−1 A (L⊤ )−1 = L−1 A (L−1 )⊤ .Более того, мы покажем, что все di положительны.ИзA = LU = LDL⊤следует, что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 )⊤ .Более того, мы покажем, что все di положительны.ИзA = LU = LDL⊤следует, что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.Но тогда диагональные элементы в Dобязаны быть положительными.Но тогда диагональные элементы в Dобязаны быть положительными.В противном случае, если di ≤ 0 для некоторого i, то, беря вектор xравным i-му столбцу единичной матрицы, получимhDx, xi = (Dx)⊤x = x⊤Dx = di ≤ 0.Это противоречит положительной определённости матрицы D.Но тогда диагональные элементы в Dобязаны быть положительными.В противном случае, если di ≤ 0 для некоторого i, то, беря вектор xравным i-му столбцу единичной матрицы, получимhDx, xi = (Dx)⊤x = x⊤Dx = di ≤ 0.Это противоречит положительной определённости матрицы D.Как следствие, из диагональных элементов матрицы Dможно извлекать квадратные корни.Если обозначить получающуюся при этом диагональную матрицучерезp pp√D := diag { d1 , d2 , .

. . , dn },√то окончательно можем взять C = L D.Если обозначить получающуюся при этом диагональную матрицучерезp pp√D := diag { d1 , d2 , . . . , dn },√то окончательно можем взять C = L D.Это представление для множителя Холесского единственно,так как по A при сделанных предположениях единственнымобразом определяется матрица L, а матричные преобразования,приведшие к формулеU L⊤−1= L−1 U ⊤ ,и её следствиям, обратимы и также дают однозначно определённыйрезультат.Если обозначить получающуюся при этом диагональную матрицучерезp pp√D := diag { d1 , d2 , .

. . , dn },√то окончательно можем взять C = L D.Это представление для множителя Холесского единственно,так как по A при сделанных предположениях единственнымобразом определяется матрица L, а матричные преобразования,приведшие к формулеU L⊤−1= L−1 U ⊤ ,и её следствиям, обратимы и также дают однозначно определённыйрезультат.Теорема доказана.Метод ХолесскогоЕсли найдено разложение Холесского для матрицы A, то решениесистемы Ax = b равносильно системеCC ⊤ x = bи сводится к решению двух треугольных систем линейныхуравнений:(C y = b,C ⊤x = y.Метод ХолесскогоЕсли найдено разложение Холесского для матрицы A, то решениесистемы Ax = b равносильно системеCC ⊤ x = bи сводится к решению двух треугольных систем линейныхуравнений:(C y = b,C ⊤x = y.Для решения первой системы применяем алгоритм прямойподстановки, а для решения второй системы — обратнуюподстановку.Метод ХолесскогоЕсли найдено разложение Холесского для матрицы A, то решениесистемы Ax = b равносильно системеCC ⊤ x = bи сводится к решению двух треугольных систем линейныхуравнений:(C y = b,C ⊤x = y.Для решения первой системы применяем алгоритм прямойподстановки, а для решения второй системы — обратнуюподстановку.Но как практически найти разложение Холесского?Выпишем равенство A = CC ⊤ , определяющее множительХолесского, в развёрнутой форме с учётом симметричности A:a11 a21 a22 ..=.... ...▽an1 an2c11 c21 . . .c22...cn1 cn2 0...···...cnn  ·  c11annc21c220······...cn1(2)cn2 ..

,. cnnЗнак «▽» означает симметричные относительно главной диагоналиэлементы матрицы, которые далее несущественны.Это равенство — система уравнений относительно неизвестныхпеременных c11 , c21 , c22 , . . . , cnn — элементов нижнего треугольникамножителя Холесского.Это равенство — система уравнений относительно неизвестныхпеременных c11 , c21 , c22 , .

. . , cnn — элементов нижнего треугольникамножителя Холесского.Всего их 1 + 2 + . . . + n =12n(n + 1) штук.Это равенство — система уравнений относительно неизвестныхпеременных c11 , c21 , c22 , . . . , cnn — элементов нижнего треугольникамножителя Холесского.Всего их 1 + 2 + . . .

+ n =12n(n + 1) штук.Для их определения имеем столько же соотношений, вытекающихв матричном равенстве (2) из выражений для элементов aij , i ≥ j,которые образуют нижний треугольник симметричной матрицыA = (aij ).В поэлементной форме система уравнений (2) имеет вид,определяемый правилом умножения матриц и симметричностью A:aij =jXk=1cik cjkпри i ≥ j.(3)В поэлементной форме система уравнений (2) имеет вид,определяемый правилом умножения матриц и симметричностью A:aij =jXk=1cik cjkпри i ≥ j.Выписанные соотношения образуют, фактически, двумерныймассив, в котором уравнения имеют двойные индексы — i и j.(3)В поэлементной форме система уравнений (2) имеет вид,определяемый правилом умножения матриц и симметричностью A:aij =jXk=1cik cjkпри i ≥ j.(3)Выписанные соотношения образуют, фактически, двумерныймассив, в котором уравнения имеют двойные индексы — i и j.Но их можно линейно упорядочить таким образом, что системауравнений (3) получит специальный вид, очень напоминающийтреугольные линейные системы.Далее эта система может быть решена с помощью процесса,сходного с прямой подстановкой для треугольных систем линейныхалгебраических уравнений.C = ↓↓↓↓...↓...y....0..y ···↓y ×Схема определения элементов треугольного множителяпри построении разложения Холесского.Если выписывать выражения для элементов aij по столбцамматрицы A, начиная с диагонального элемента ajj и идя сверхувниз до ajn , то все уравнения из (3) разбиваются на n следующихгрупп, которые занумеруем столбцовым индексом j = 1, 2 .

. . , n:(c211 = a11 ,для j = 1ci1 c11 = ai1 ,i = 2, 3, . . . , n,для j = 2(для j = 3(···c221 + c222 = a22 ,ci1 c21 + ci2 c22 = ai2 ,i = 3, 4, . . . , n,c231 + c232 + c233 = a33 ,ci1 c31 + ci2 c32 + ci3 c33 = ai3 ,···.i = 4, 5, . . . , n,В краткой записи получающаяся система может быть записана так: (c2j1 + c2j2 + . . .

+ c2j,j−1 + c2jj = ajj ,ci1 cj1 + ci2 cj2 + . . . + cij cjj = aij , i = j + 1, . . . , n,(4)j = 1, 2, . . . , n.где считается, что cji = 0 при j < i.Получается, что в уравнениях из (4) для j-го столбца множителяХолесского присутствуют все элементы j-го и предшествующихстолбцов.В краткой записи получающаяся система может быть записана так: (c2j1 + c2j2 + . . . + c2j,j−1 + c2jj = ajj ,ci1 cj1 + ci2 cj2 + . . .

Характеристики

Список файлов лекций