Алгоритмы - построение и анализ (1021735), страница 170
Текст из файла (страница 170)
Процедура Млтщх Мя.тп'и' из раздела 25.1 реализует матричное умножение квадратных матриц (т = и = р) непосредственно по формуле (28.3). Для умножения матриц размером и х и процедура Млтих Мщ.тички выполняет пз умножений и пз (и — 1) сложений, так что время ее работы равно 9 (пз). Матрицы обладают многими (но не всеми) алгебраическими свойствами, присущими обычным числам. Единичная матрица является нейтральным элементом Элементами матриц и векторов служат элементы некоторой числовой системы, такие как действительные числа, комплексные числа или, например, целые числа по модулю простого числа. Числовая система определяет, каким образом должны складываться и перемножаться числа.
Эти определения можно распространить н на матрицы. Определим сложение матриц (шап1х айЫоп) следующим образом. Если А = (а; ) и В = (6; ) — матрицы размером т х и, то их суммой является матрица С = (с;.) = А+ В размером т х и, определяемая соотношением су = а, + 6; для г = 1, 2,..., т и у = 1, 2,..., и.
Другими словами, сложение матриц выполняется поэлементно. Нулевая матрица нейтральна по отношению к сложению матриц: Часть ЧП. Избранные темы 828 по отношению к умножению: 1,„А = А1„= А для любой матрицы А размером гп х гг. Умножение на нулевую матрицу дает нулевую матрицу: АО=ОА=О. Умножение матриц ассоциативно: А(ВС) = (АВ)С (28А) для любых совместимых матриц А, В и С. Умножение матриц дистрибутивно относительно сложения: А(В+С) = АВ+АС, (В + С) О = В12 + СВ.
(28.5) Для и ) 1 умножение матриц размером и х и не коммутативно. Например, если А = (о оо~) и В (о оо), то АВ = (ог оо), но ВА = (оо о) Произведения матрицы и вектора иди двух векторов вычисляются путем представления вектора как матрицы размером и х 1 (нли 1 х гг в случае вектора-строки). Таким образом, если А — матрица размером т х и, а х — вектор размером и, то Ах является вектором размера т. Если х и у — векторы размера и, то произведение и х у=~~ ту; т.е. норма х — это длина вектора в гг-мерном евклидовом пространстве.
Обратные матрицы, ранги и детерминанты Матрицей, о0ратной (1пчегзе) к данной матрице А размером и х п, является матрица размером и х тг, обозначаемая как А ' (если таковая существует), такая что А А г = 1в — — А ' А. Например, представляет собой число (в действительности — матрицу размером 1 х 1), называющееся скалярным произведением (шпег ргодпсг) векторов х и у.
Матрица размером п х п Я = ху с элементами аО = ж;у называется тенэорным лроизведением (ошег ргодпсг) этих же векторов. (Евклидова) норма ((еис11деап) попп) ~~х8 вектора к размером и определяется соотношением Глава 28. Работа с матрицами 829 Многие ненулевые квадратные матрицы не имеют обратных матриц. Матрица, для которой не существует обратная матрица, называется необращаемой (поп1пчеи!Ые), или вырожденной (з1пйп!аг). Вот пример ненулевой вырожденной матрицы: (':) Если матрица имеет обратную матрицу, она называется обращаемой (!пчег!1Ые), или невырожденной (попз1пйп!аг). Если обратная матрица существует, то она единственная (см.
упражнение 28.1-3). Если А и  — невырожденные матрицы размером и х и, то (АВ) ' = А 'В '. (28.6) Операция обращения коммутативна с операцией транспонирования: (А-з) = (Ат) ' Векторы хы хз,... х„линейно зависимы (!шеаг!у берепбеп1), если существуют коэффициенты сы сз,..., с„, среди которых есть ненулевые, такие что сзхз + + сзхз+ ° ° + с х„= О. Например, векторы хд = (1 2 3), хз = (2 6 4) и хз = (4 11 9) линейно зависимы, поскольку 2хз + Зхз — 2хз = О. Если векторы не являются линейно зависимыми, они называются линейно независимььми (1!пеаг!у !поерепоеп1).
Например, столбцы единичной матрицы линейно независимы. Столбновым рангом (со1шпп гапк) ненулевой матрицы А размером т х и называется размер наибольшего множества линейно независимых столбцов А. Аналогично, строчным рангом (тою гап1с) ненулевой матрицы А размером т х и называется размер наибольшего множества линейно независимых строк А.
Фундаментальным свойством любой матрицы А является равенство ее строчного и столбцового рангов, так что мы можем говорить просто о ранге (гап!с) матрицы. Ранг матрицы размером т х и представляет собой целое число от О до ппп (т, и) включительно (ранг нулевой матрицы равен О, ранг единичной матрицы размером и х и равен и). Другое эквивалентное (и зачастую более полезное) определение ранга ненулевой матрицы А размером т х и — это наименьшее число г такое, что существуют матрицы В и С размером соответственно т х г и т х и такие, что А = ВС.
Квадратная матрица размером и х и имеет полный ранг (йП гапк), если ее ранг равен и. Матрица размером т х и имеет лолный столбцовый ранг (Гп11 со!шпп гав!с), если ее ранг равен и. Фундаментальное свойство рангов приведено в следующей теореме. Часть Ч11. Избранные темы 830 Теорема 28.1. Квадратная матрица имеет полный ранг тогда и только тогда, когда она является невырожденной. И Ненулевой вектор х, такой что Ах = О, называется аннулирующим еектором (пп11 чес1ог) матрицы А. Приведенная далее теорема (доказательство которой оставлено в качестве упражнения 28.1-9) и ее следствие связывают столбцовый ранг и вырожденность с аннулирующим вектором. Теорема 28.2. Матрица А имеет полный столбцовый ранг тогда и только тогда, когда для нее не существует аннулирующий вектор.
Следствие 28.3. Квадратная матрица А является вырожденной тогда и только тогда, когда она имеет аннулирующий вектор. И Минорам (пплог) элемента он (11-минор) матрицы А размером и х и (и > 1) называется матрица А1; 1 размером (и — 1) х (и — 1),получаемая нз А удалением 1-й строки и 7'-го столбца. Определитель, или детерминант (де1епшпап1) матрицы А размером п х и можно определить рекурсивно при помощи миноров следующим образом: оы при и = 1, де~ (А) = " 1+. ); ( — 1) да131)е~(А1111) прин > 1.
1=1 (28.7) Множитель ( — 1)ь+з деФ (АМ) называется алгебраическим дополнением (со(ас1ог) элемента а;1. В приведенных ниже теоремах, доказательство которых здесь опущено, описывают фундаментальные свойства определителей. ° Определитель матрицы А умножается на — 1, если обменять местами любые два ее столбца (или строки). Кроме того, для любых квадратных матриц А и В де1 (АВ) = де1 (А) с1еФ (В). И Теорема 28.4 (Свойства определителя).
Определитель квадратной матрицы А обладает следующими свойствами. ° Если любая строка или любой столбец А нулевой, то 11е1 (А) = О. ° Если все элементы одного произвольного столбца (или строки) матрицы умножаются на Л, то ее определитель также умножается на Л. ° Определитель матрицы А остается неизменным, если все элементы одной строки (или столбца) прибавить к элементам другой строки (столбца).
° Определитель матрицы А равен определителю транспонированной матрицы 4т Глава 28. Работа с матрицами 831 Теорема 28.5. Квадратная матрица А вырождена тогда и только тогда, когда беФ1А) = О. Ы Положительно определенные матрицы Во многих приложениях важную роль играют положительно определенные матрицы.
Матрица А размером и х и является положительно определенной (роз1сп~е-дейпйе), если хтАх > О для любого ненулевого вектора х размера и. Например, единичная матрица положительно определенная, поскольку для про,т извольного ненулевого вектора х = (х1 хг ... х„) хт1„х = хгх = ~~> хг > О. Как мы увидим, зачастую встречающиеся в приложениях матрицы положительно определены в силу следующей теоремы. Теорема 28.6. Для произвольной матрицы А с полным столбцовым рангом мат- рица АтА положительно определена. Доказательство. Мы должны показать, что хт 1АтА) х > О для любого ненуле- вого вектора х.
Для произвольного вектора х хт (АтА) х = 1Ах) 1Ах) = 8Ах!)г где первое равенство следует из упражнения 28.1-2. Заметим, что 8Ах8 предг ставляет собой просто сумму квадратов элементов вектора Ах. Таким образом, (~Ах8~ > О. Если 8Ах8~ = О, все элементы вектора Ах равны О, те. Ах = = О. Поскольку А — матрица с полным столбцовым рангом, из Ах = О согласно теореме 28.2 следует, что х = О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
