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

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

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

В этомпредставлении можно оставить лишь одну из матриц P̌ или P̂ .Связь с LU-разложением матрицыТеоремаДля неособенной матрицы A существуют матрицы перестановок P̌и P̂ , такие чтоP̌ AP̂ = LU,где L, U — нижняя и верхняя треугольные матрицы, причёмдиагональными элементами в L являются единицы. В этомпредставлении можно оставить лишь одну из матриц P̌ или P̂ .Доказательство опускаетсяСвязь с LU-разложением матрицыТеоремаДля неособенной матрицы A существуют матрицы перестановок P̌и P̂ , такие чтоP̌ AP̂ = LU,где L, U — нижняя и верхняя треугольные матрицы, причёмдиагональными элементами в L являются единицы. В этомпредставлении можно оставить лишь одну из матриц P̌ или P̂ .Доказательство опускаетсяЭтот результат показывает, что можно один раз переставитьстроки и столбцы в исходной матрице и потом уже выполнятьLU-разложение прямым ходом метода Гаусса без какого-либоспециального выбора ведущего элемента.Существование LU-разложенияВ методе Гаусса с выбором ведущего элемента перестановка строк истолбцов приводит к существенному изменению исходной матрицысистемы, что не всегда желательно.Существование LU-разложенияВ методе Гаусса с выбором ведущего элемента перестановка строк истолбцов приводит к существенному изменению исходной матрицысистемы, что не всегда желательно.Когда метода Гаусса может быть выполненбез перестановки строк и столбцов?Существование LU-разложенияВ методе Гаусса с выбором ведущего элемента перестановка строк истолбцов приводит к существенному изменению исходной матрицысистемы, что не всегда желательно.Когда метода Гаусса может быть выполненбез перестановки строк и столбцов?Этот вопрос связан с условиями получения LU-разложенияматрицы посредством прямого хода метода Гаусса без выбораведущего элемента.ТеоремаЕсли A = (aij ) — квадратная n × n-матрица, у которой все ведущиеминоры порядков от 1 до (n − 1) отличны от нуля, т.

е.a11 6= 0,deta11 a12a21 a226= 0,... ,a11a21...a12a22............a1,n−1a2,n−1...det  6= 0.an−1,1 an−1,2 . . . an−1,n−1то для A существует LU-разложение, т. е. представление её в видеA = LU,где L — нижняя треугольная, U — верхняя треугольнаяn × n-матрицы. Это LU-разложение для A единственно приусловии, что диагональные элементы в L — единицы.ДоказательствоПроводится индукцией по порядку n матрицы A.ДоказательствоПроводится индукцией по порядку n матрицы A.Если n = 1, то утверждение теоремы очевидно.Тогда искомые матрицы L = (lij ) и U = (uij ) являются просточислами, и достаточно взятьl11 = 1иu11 = a11 .ДоказательствоПроводится индукцией по порядку n матрицы A.Если n = 1, то утверждение теоремы очевидно.Тогда искомые матрицы L = (lij ) и U = (uij ) являются просточислами, и достаточно взятьl11 = 1иu11 = a11 .Пусть теорема верна для матриц размера (n − 1) × (n − 1).Тогда представим n × n-матрицу A в блочном виде:гдеA = a11a21...an1a12 .

. . a1na22 . . . a2n.........an2 . . . ann=An−1zvann!An−1—ведущая (n − 1) × (n − 1)-подматрица A,zv——вектор-столбец размера n − 1,вектор-строка размера n − 1,такие чтоz=a1na2n...an−1,n,v=an1 an2 . . . an,n−1 .,Разложения A на треугольные множители диктует равенствоA =An−1zvann!=Ln−10xlnn!·Un−1y0unn!,где Ln−1 , Un−1 — нижняя и верхняятреугольные (n − 1)×(n − 1)-матрицы,x — вектор-строка размера n − 1,y — вектор-столбец размера n − 1.Разложения A на треугольные множители диктует равенствоA =An−1zvann!=Ln−10xlnn!·Un−1y0unn!,где Ln−1 , Un−1 — нижняя и верхняятреугольные (n − 1)×(n − 1)-матрицы,x — вектор-строка размера n − 1,y — вектор-столбец размера n − 1.Следовательно, используя правилаперемножения матриц по блокам, необходимо имеемAn−1 = Ln−1 Un−1 ,(1)z = Ln−1 y,(2)v = x Un−1 ,(3)ann = xy + lnn unn .(4)Первое из полученных соотношений —An−1 = Ln−1 Un−1— выполнено в силу индукционного предположения.Первое из полученных соотношений —An−1 = Ln−1 Un−1— выполнено в силу индукционного предположения.Оно должно однозначно определять Ln−1 и Un−1 , если потребоватьпо диагонали в Ln−1 единичные элементы.Первое из полученных соотношений —An−1 = Ln−1 Un−1— выполнено в силу индукционного предположения.Оно должно однозначно определять Ln−1 и Un−1 , если потребоватьпо диагонали в Ln−1 единичные элементы.По условию теоремы det An−1 6= 0, а потому матрицы Ln−1 и Un−1также должны быть неособенны, т.

е. det Ln−1 6= 0 и det Un−1 6= 0.Первое из полученных соотношений —An−1 = Ln−1 Un−1— выполнено в силу индукционного предположения.Оно должно однозначно определять Ln−1 и Un−1 , если потребоватьпо диагонали в Ln−1 единичные элементы.По условию теоремы det An−1 6= 0, а потому матрицы Ln−1 и Un−1также должны быть неособенны, т. е. det Ln−1 6= 0 и det Un−1 6= 0.По этой причине равенства (2)–(3) —x Un−1 = vиLn−1 y = z,которые являются системами линейных алгебраических уравненийотносительно x и y, однозначно разрешимы.Найдя из соотношенийz = Ln−1 y,v = x Un−1 ,векторы x и y, мы сможем из уравненияann = xy + lnn unnвосстановить lnn и unn .Найдя из соотношенийz = Ln−1 y,v = x Un−1 ,векторы x и y, мы сможем из уравненияann = xy + lnn unnвосстановить lnn и unn .Если дополнительно потребовать lnn = 1, то значение unn находитсяоднозначно и равно (ann − xy).Найдя из соотношенийz = Ln−1 y,v = x Un−1 ,векторы x и y, мы сможем из уравненияann = xy + lnn unnвосстановить lnn и unn .Если дополнительно потребовать lnn = 1, то значение unn находитсяоднозначно и равно (ann − xy).Доказательство завершено.Сильно регулярные матрицыОпределениеКвадратная n × n-матрица A = (aij ) называется сильно регулярной(или сильно неособенной), если все её ведущие миноры, включая иопределитель самой матрицы, отличны от нуля, т.

е.a11 a12deta11 6= 0,6= 0,... ,det A 6= 0.a21 a22Сильно регулярные матрицыОпределениеКвадратная n × n-матрица A = (aij ) называется сильно регулярной(или сильно неособенной), если все её ведущие миноры, включая иопределитель самой матрицы, отличны от нуля, т. е.a11 a12deta11 6= 0,6= 0,... ,det A 6= 0.a21 a22Strongly regular matrix,strongly nonsingular matrixСильно регулярные матрицыТеоремаПусть A — квадратная неособенная матрица.Для существования её LU-разложения необходимо и достаточно,чтобы она была сильно регулярной.Сильно регулярные матрицыТеоремаПусть A — квадратная неособенная матрица.Для существования её LU-разложения необходимо и достаточно,чтобы она была сильно регулярной.Доказательство.Достаточность была доказана в теоремео достаточных условиях существования LU-разложения.Для доказательства необходимости рассмотримблочное представление треугольного разложения A = LU .=00Задавая различные размеры ведущих подматриц, т.

е. квадратныхблоков, расположенных в матрицах A, L и U слева сверху, получимравенства, аналогичные (1).Они означают, что любая ведущая подматрица в Aесть произведение ведущих подматриц соответствующих размеровиз L и U .Задавая различные размеры ведущих подматриц, т. е. квадратныхблоков, расположенных в матрицах A, L и U слева сверху, получимравенства, аналогичные (1).Они означают, что любая ведущая подматрица в Aесть произведение ведущих подматриц соответствующих размеровиз L и U .Но L и U — неособенные треугольные матрицы, так что все ихведущие подматрицы также неособенны.Отсюда можно заключить неособенность всех ведущих подматрицв A, т. е. строгую регулярность матрицы A.Теорема доказана.Сильно регулярные матрицыВ формулировке Теоремы ничего не говорится о том, реализуем лиметод Гаусса для соответствующей системы линейныхалгебраических уравнений.Сильно регулярные матрицыВ формулировке Теоремы ничего не говорится о том, реализуем лиметод Гаусса для соответствующей системы линейныхалгебраических уравнений.ПредложениеЕсли в системе линейных алгебраических уравнений Ax = bматрица A — квадратная и сильно регулярная, то метод Гауссареализуем в применении к этой системе без перестановки строк истолбцов.Доказательство.j((j0← j-ая строка0↑ j-ый столбецСтруктура матрицы системы перед началом j-го шагапрямого хода метода Гаусса: другой взгляд.К началу j-го шага прямого хода, на котором предстоит обнулитьподдиагональные элементы j-го столбца матрицы СЛАУ, еёведущей j × j-подматрицей является треугольная матрица, котораяполучена из исходной ведущей подматрицы преобразованиямипредыдущих j − 1 шагов метода Гаусса.Эти преобразования — линейное комбинирование строк — неизменяют свойство определителя матрицы быть неравным нулю.К началу j-го шага прямого хода, на котором предстоит обнулитьподдиагональные элементы j-го столбца матрицы СЛАУ, еёведущей j × j-подматрицей является треугольная матрица, котораяполучена из исходной ведущей подматрицы преобразованиямипредыдущих j − 1 шагов метода Гаусса.Эти преобразования — линейное комбинирование строк — неизменяют свойство определителя матрицы быть неравным нулю.Поэтому отличие от нуля какого-либо ведущего минора влечётотличие от нуля всех диагональных элементов ведущей треугольнойподматрицы того же размера в преобразованной матрице СЛАУ.В частности, при этом всегда ajj 6= 0, так что деление на этотэлемент в алгоритмах прямого хода и обратного хода метода Гауссавыполнимо.К началу j-го шага прямого хода, на котором предстоит обнулитьподдиагональные элементы j-го столбца матрицы СЛАУ, еёведущей j × j-подматрицей является треугольная матрица, котораяполучена из исходной ведущей подматрицы преобразованиямипредыдущих j − 1 шагов метода Гаусса.Эти преобразования — линейное комбинирование строк — неизменяют свойство определителя матрицы быть неравным нулю.Поэтому отличие от нуля какого-либо ведущего минора влечётотличие от нуля всех диагональных элементов ведущей треугольнойподматрицы того же размера в преобразованной матрице СЛАУ.В частности, при этом всегда ajj 6= 0, так что деление на этотэлемент в алгоритмах прямого хода и обратного хода метода Гауссавыполнимо.Предложение доказано.В общем случае проверка сильной регулярности матрицы являютсянепростой, поскольку вычисление ведущих миноров матрицытребует немалых трудозатрат, и, по существу, ничуть не прощесамого метода Гаусса.В общем случае проверка сильной регулярности матрицы являютсянепростой, поскольку вычисление ведущих миноров матрицытребует немалых трудозатрат, и, по существу, ничуть не прощесамого метода Гаусса.Тем не менее, сильно регулярными матрицами являются, кпримеру, два важных класса матриц:положительно определённые матрицы в силу известногокритерия Сильвестера,В общем случае проверка сильной регулярности матрицы являютсянепростой, поскольку вычисление ведущих миноров матрицытребует немалых трудозатрат, и, по существу, ничуть не прощесамого метода Гаусса.Тем не менее, сильно регулярными матрицами являются, кпримеру, два важных класса матриц:положительно определённые матрицы в силу известногокритерия Сильвестера,матрицы, имеющими диагональное преобладание, в силупризнака Адамара (если исходная матрица имеет диагональноепреобладание, то его также имеют ведущие подматрицы).Вычислительные методыанализа и линейной алгебрыКурс лекцийС.П.

ШарыйКафедра математического моделирования НГУЛекция 1 декабря 2017 г.Разложение ХолесскогоОпределениеКвадратная матрица A называется положительно определённой,если для любых векторов x, x 6= 0, справедливо неравенствоhAx, xi > 0,т. е. x⊤Ax > 0.Разложение ХолесскогоОпределениеКвадратная матрица A называется положительно определённой,если для любых векторов x, x 6= 0, справедливо неравенствоhAx, xi > 0,т.

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

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