1611688890-f641c9ec8276824e4686da772eb56520 (826652), страница 41
Текст из файла (страница 41)
. , v)k′≤ kAk′ · k(v, v, . . . , v)k′ = kAk′ · kvk,так что требуемое согласование действительно будет достигнуто.3.3гПодчинённые матричные нормыВ предшествующем пункте мы могли видеть, что с заданной векторной нормой могут быть согласованы различные матричные нормы.И наоборот, для матричной нормы возможна согласованность со многими векторными нормами. В этих условиях при проведении различных преобразований и выводе оценок наиболее выгодно оперироватьсогласованными матричными нормами, которые принимают как можно меньшие значения.
Тогда неравенства, получающиеся в результате2483. Численные методы линейной алгебрыприменения в выкладках соотношения (3.23), будут более точными ипозволят получить более тонкие оценки результата. Например, конкретная оценка нормы погрешности может оказать сильное влияниена количество итераций, которые мы вынуждены будем сделать в итерационном численном методе для достижения той или иной точностиприближённого решения.Пусть дана векторная норма k · k и зафиксирована матрица A.
Изтребования согласованности (3.23) вытекает неравенство для согласованной нормы матрицы kAk:kAk ≥ kAxk/kxk,(3.24)где x — произвольный вектор. Как следствие, значения всех матричныхнорм от A, согласованных с данной векторной нормой k · k, ограниченыснизу выражениемkAxksup,x6=0 kxkколь скоро (3.24) должно быть справедливым для любого ненулевоговектора x.Предложение 3.3.5 Для любой фиксированной векторной нормы k·kсоотношениемkAxkkAk′ = sup(3.25)x6=0 kxkзадаётся матричная норма.Доказательство.
Отметим прежде всего, что в случае конечномерных векторных пространств Rn и Cn вместо «sup» в выражении (3.25)можно брать «max». В самом деле, x kAxk = sup kAyk,sup= sup Akxk x6=0 kxkx6=0kyk=1а задаваемая условием kyk = 1 единичная сфера любой нормы замкнута и ограничена, т. е. компактна в Rn или Cn [40, 50]. Непрерывнаяфункция kAyk достигает на этом компактном множестве своего максимума. Таким образом, в действительностиkAk′ = maxx6=0kAxk= max kAyk.kxkkyk=12493.3. Нормы векторов и матрицПроверим теперь для нашей конструкции выполнение аксиом нормы. Если A 6= 0, то найдётся ненулевой вектор y, такой что Ay 6= 0.Ясно, что его можно считать нормированным, т. е. kyk = 1. ТогдаkAyk > 0, и потому maxkyk=1 kAyk > 0, что доказывает для k·k′ первуюаксиому нормы.Абсолютная однородность для k · k′ доказывается тривиально. Покажем для (3.25) справедливость неравенства треугольника.
Очевидно,k(A + B)yk ≤ kAyk + kByk,и потомуmax k(A + B)yk ≤ max kAyk + kBykkyk=1kyk=1≤ max kAyk + max kByk,kyk=1kyk=1что и требовалось.Приступая к обоснованию субмультипликативности, отметим, чтопо самому построению kAxk ≤ kAk′ kxk для любого вектора x. По этойпричинеkABk′ = max k(AB)yk = kABzk для некоторого z с kzk = 1kyk=1≤ kAk′ · kBzk ≤ kAk′ · max kBzk = kAk′ kBk′ .kzk=1Это завершает доказательство предложения.Доказанный результат мотивируетОпределение 3.3.5 Для заданной векторной нормы k · k матричнаянорма k · k′ , определяемая какkAk′ = maxx6=0kAxk= max kAyk,kxkkyk=1называется подчинённой к k · k матричной нормой (или индуцированной, или операторной нормой).Последний термин — операторная норма — популярен потому, чтоконструкция этой нормы хорошо отражает взгляд на матрицу как на2503.
Численные методы линейной алгебрыоператор, задающий отображения линейных векторных пространств.Операторная норма показывает максимальную величину растяженияпо норме, которую получает в сравнении с исходным вектором его образ при действии данного оператора. На основе рассмотренной конструкции можно также определять подчинённые нормы для прямоугольных матриц: для этого требуется взять две векторные нормы — впространствах, соответствующих строчной и столбцовой размерностиматрицы.Несмотря на хорошие свойства подчинённых матричных норм, ихопределение не отличается большой конструктивностью, так как привлекает операцию взятия максимума.
Естественно задаться вопросомо том, существуют ли вообще достаточно простые и обозримые выражения для матричных норм, подчинённых тем или иным векторнымнормам. Какими являются подчинённые матричные нормы для рассмотренных выше векторных норм k · k1 , k · k2 и k · k∞ ? С другой стороны, являются ли матричные нормы kAkF (фробениусова) и kAkmaxподчинёнными для каких-либо векторных норм?Ответ на последний вопрос отрицателен. В самом деле, для единичной n × n-матрицы I имеем√kIkmax = n,kIkF = n,тогда как из определения подчинённой нормы следует, что должнобытьkIk = sup kIyk = max kyk = 1.(3.26)kyk=1kyk=1Ответом на первые два вопроса являетсяПредложение 3.3.6 Для векторной 1-нормы подчинённой матричной нормой для m × n-матриц является!mX|aij |kAk1 = max1≤j≤ni=1— максимальная сумма модулей элементов по столбцам.Для чебышёвской векторной нормы (∞-нормы) подчинённой матричной нормой для m × n-матриц является!nX|aij |kAk∞ = max1≤i≤mj=12513.3.
Нормы векторов и матриц— максимальная сумма модулей элементов по строкам.Матричная норма, подчинённая евклидовой норме векторов kxk2 ,есть kAk2 = σmax (A) — наибольшее сингулярное число матрицы A.Доказательство. Для обоснования первой части предложения выпишем следующую цепочку преобразований и оценокkAxk1m Xnm XmXXX n ≤| aij xj |ax(Ax)i ==ijj=m XnXi=1 j=1≤maxn XmX| aij | | xj | =1≤j≤nmXi=1| aij |!i=1 j=1j=1i=1i=1j=1 i=1·nXj=1| aij | | xj | =mn XX| aij || xj |j=1| xj | = kAk1 kxk1 ,i=1(3.27)из которой вытекаетkAxk1≤ kAk1 .kxk1При этом все неравенства в цепочке (3.27) обращаются в равенства длявектора x в виде столбца единичнойn × n-матрицы с тем номером j, наP|a|.
Как следствие, на этом векторекотором достигается max j miji=1достигается наибольшее значение отношения kAxk1 /kxk1 из определения подчинённой матричной нормы.Аналогичным образом доказывается и вторая часть предложения,касающаяся k · k∞ .Приступая к обоснованию последней части предложения рассмотрим n × n-матрицу A∗A. Она является эрмитовой, её собственные числа вещественны и неотрицательны, будучи квадратами сингулярныхчисел матрицы A и, возможно, ещё нулями (см. Предложение 3.2.4).Унитарным преобразованием подобия (ортогональными в вещественном случае) матрица A∗A может быть приведена к диагональному виду: A∗A = U ∗Λ U , где U — унитарная n × n-матрица, Λ — диагональнаяn× n-матрица, имеющая на диагонали числа σi2 , i = 1, 2, .
. . , min{m, n},т. е. квадраты сингулярных чисел σi матрицы A, и, возможно, ещё нулив случае m < n.2523. Численные методы линейной алгебрыДалее имеемkAk2√√x∗A∗A xx∗ U ∗ΛU x√√=maxx6=0x∗ xx∗ U ∗ U xsPp√22(U x)∗Λ(U x)z ∗Λ zi σi |zi |P= max p= max= max √ ∗2x6=0z6=0z6=0z z(U x)∗ U xi |zi |kAxk2= max= maxx6=0 kxk2x6=0≤ max σmax (A)z6=0sP|zi |22i |zi |Pi!= σmax (A),где в выкладках применена замена переменных z = U x. Кроме того,полученная для kAk2 оценка достижима: достаточно взять в качествевектора z столбец единичной n × n-матрицы с номером, равным ме2сту элемента σmax(A) на диагонали в Λ, а в самом начале выкладокположить x = U ∗ z.Норму матриц k · k2 , подчинённую евклидовой векторной норме, часто называют также спектральной нормой матриц.
Для симметричныхматриц она равна наибольшему из модулей собственных чисел и совпадает с так называемым спектральным радиусом матрицы (см. 3.3ж).Отметим, что спектральная норма матриц не является абсолютнойнормой (см. Пример 3.2.3), т. е. она зависит не только от абсолютныхзначений элементов матрицы. В то же время, k · k1 и k · k∞ — этоабсолютные матричные нормы, что следует из вида их выражений.3.3дТопология на множествах матрицСовершенно аналогично случаю векторов можно рассмотреть топологическую структуру на множестве матриц.
Будем говорить, чтоматричная переменная A сходится к пределу A⋆ относительно фиксированной нормы матриц (сходится по норме), если kA − A⋆ k → 0.Матричные нормы назовём топологически эквивалентными (или просто эквивалентными), если предельный переход в одной норме влечётсуществование предела в другой, и обратно. Опять таки, в силу известного факта из математического анализа в конечномерном линейном пространстве всех m × n-матриц все нормы эквивалентны. Тем неменее, конкретные константы эквивалентности играют огромную роль2533.3. Нормы векторов и матрицпри выводе различных оценок, и их значения для важнейших нормдаёт следующееПредложение 3.3.7 Для квадратных n × n-матриц√1√ kAk2 ≤ kAk1 ≤ n kAk2 ,n√1√ kAk∞ ≤ kAk2 ≤ n kAk∞ ,n1kAk1 ≤ kAk∞ ≤ n kAk1 .nДоказательство.
Докажем первое двустороннее неравенство. Имеетместо очевидная оценка√kAk1 = max kAyk1 ≤ maxn kAyk2kyk1 ≤1kyk1 ≤1в силу первого неравенства из Предложения 3.3.2. Кроме того, из негоследует, что множество векторов y, удовлетворяющих kyk1 ≤ 1, включается во множество векторов, определяемых условием kyk2 ≤ 1. Поэтой причинеmax kAyk2 ≤kyk1 ≤1max kAyk2 = kAk2 ,kyk2 ≤1√так что в целом действительно kAk1 ≤ n kAk2 .С другой стороны, в силу того же первого неравенства из Предложения 3.3.2kAk1 = max kAyk1 ≥ max kAyk2 .kyk1 ≤1kyk1 ≤1√Но множество векторов kyk1 ≤ 1 не более, чем в n меньше, чем множество векторов, удовлетворяющих kyk2 ≤ 1. Как следствие,11max kAyk2 = √ kAk2 .max kAyk2 ≥ √n kyk2 ≤1nkyk1 ≤1Объединяя два выписанных неравенства, получаем требуемое.Доказательства второго и третьего двусторонних неравенств аналогичны, они следуют из двусторонних неравенств для соответствующихвекторных норм.2543.
Численные методы линейной алгебрыКак и для векторов, помимо сходимости по норме введём также поэлементную сходимость матриц, при которой одна матрица сходитсяк другой тогда и только тогда, когда все элементы первой матрицысходятся к соответствующим элементам второй:A = ( aij ) → A⋆ = ( a⋆ij ) поэлементно в Rm×n или Cm×naij →a⋆ijmв R или C для всех индексов i, j.Из эквивалентности матричных норм следует существование для любой нормы k · k такой константы C, что!mX|aij | = kAk1 ≤ CkAkmax |aij | ≤ maxi,j1≤j≤ni=1(вместо 1-нормы матриц в этой выкладке можно было бы взять, кпримеру, ∞-норму). Поэтому для любых индексов i и j верна оценка|aij | ≤ CkAk. Как следствие, сходимость последовательности матрицв любой норме влечёт поэлементную сходимость этой последовательности. Доказательство обратной импликации, т. е.
того факта, что изпоэлементной сходимости матриц следует сходимость по норме, совершенно аналогично первой части Предложения 3.3.3 (см. §3.3б).В целом для любой матричной нормы множество матриц с введённым на нём посредством (3.22) расстоянием является полным метрическим пространством, т. е.