Беклемишев - Дополнительные главы линейной алгебры (947281), страница 48
Текст из файла (страница 48)
Обозначим через С матрицу размеров г х п, составленную из первых г строк преобразованной матрицы. $3. МЕТОДЫ ВЫЧИСЛЕНИЯ 2!3 Пусть  — матрица размеров лз х г, составленная из столбцов исходной матрицы А с номерами 1„..., 1„т. е. из базисных столбцов. Оказывается, что А=ВС, и это разложение скелетпое. Действительно, базисные столбцы (с номерами ~„..., 1,) матрицы С вЂ” зто столбцы единичной матрицы порядка г. Поэтому элементы /-го столбца С вЂ” те коэффициенты, с которыми этот столбец раскладывается по базисным столбцам. Но известно, что линейные зависимости между столбцами матриды сохраняются при элементарных операциях со строками.
Следовательно,!ьй столбец матрицы А раскладывается по ее базисным столбцам с теми же коэффициентами. Остается напомнить, что !ьй столбец произведения ВС есть линейная комбинация столбцов В с коэффициентами, равными элементам 1-го столбца С. Этот путь получения скелетного разложения имеет тот очевидный недостаток, что требует принятия решения относительно малости последних ~и — г строк преобразованной матрицы. Кроме того, вычисление псевдообратиой матрицы по формуле нз предложения 1О ч 1 требует выполнения значительного числа арифметических операций, и, по-видимому, ие существует возможности использовать полученную при разложении матрицы А преобразующую матпицу. Матрица В, помимо линейной независимости столбцов, никаким спепиальным строением не обладает. Как использовать специальное строение матрицы С, мы увидим ниже, в и.
7. 5. 9м-разложение для прямоугольных матриц. Напомним, что при построении методом отражений 1~!7-разложения для квадратной матрицы в 5 3 гл. 11! Мы преобразовьиали последовательно 1-й, 2-й, 3-й и т. д. столбцы матрицы к виду, соответствующему верхней треугольной форме. Каждое преобразование производилось путем уыногкения слева на матрицу отражения и не меняло достигнутого вида предыдущих столбцов.
Если 1-й'столбец матрицы был линейной комбинацией предыдущих столбцов, то после их преобразования элементы 1-го столбца, расположенные на диагонали и ниже, оказывались равными нулю. Такой столбец в преобразовании пе нуждался, и соответствующий множитель пропускался. То обстоятельство, что преобразуемая матрица — квадратная, по существу не играло роли в этом процессе. Преобразуя таким же образом произвольную матрицу А размерами и х п, мы получим разложение А=ЯМ, где Ц вЂ” ортогональная матрица порядка т, а !с — матрица размеров лз х и, элементы рц которой удовлетворяют условию рц = 0 при 1~ 1. Такое разложение мы назовем Яг-разложением, исполь- 214 гл !Р псевдоРешения и псевдооБРАтные мАЕРицы А и = а„, — Р ', свуп 1 ! где коэффициенты с; выбираются из условий дти =О...;, дти = О.
Эти условия можно записать в виде равенств Х т т с,т7, т);=а~ а (15) для всех 7 = 1, „., й. Обозначим через Г матрицу этой системы линейных уравнений, т. е. матрицу е элементами д~т<7Р Если вычисления выполняются точно, то столбцы дм ..., а» ортонормнрованы, à — единичная матрица, и с~ — — д~атдм откуда т х.з т т и = аьы — ~~ (~® аА,А) ~7ь т ! (16) Затем полагают а„, = и/!1 и 5 и переходят к вычислению ~74+э. зуя малую букву в напоминание о том, что матрица )7, вообщв говоря, не является квадратной.
Второе обобщение ())г-разложения мы получим, если вспомним получение 1,1)г-разложения методом ортогонализапии Грама— Шмидта (см. стр. 157). Пусть А — матрица размеров тп х п прн условии и > и, и пусть Кй А = и, т. е. столбцы А линейно независимы. Рассматривая эти столбцы как и векторов в т-мерном пространстве, мы можем применить к ним метод ортогонализации и построить такую правую треугольную матрицу У, что столбцы матрицы Я = А У ортогональны н нормированы относительно обычного скалярного произведения в пространстве столбцов.
Таким образом, матрица Я размеров тл х и может рассматриваться как совокупность п столбцов из некоторой ортогональной матрицы порядка т. Обозначая У ' через )г, мы получаем разложение А = Я)с, в котором )с — квадратная верхняя треугольная матрица порядка, п„ а Я вЂ” описанная выше матрица. Такое разложение мы будем называть Сй-разложением.
На стр. 157 мы отмечали, что процесс ортогоналнзации Грама— Шмидта в том виде, как он обычно излагается, не обладает устойчивостью по отношению к ошибкам округления. Ввиду важности иЛ-разложения для псевдообращения матриц, а процесса ортогонализации для ий-разложения, мы рассмотрим здесь модификацию метода ортогонализацни, повышающую его устойчивость. 6. Метод переортогонализации. Пусть мы должны ортогонали. зовать л столбцов высоты и: а„..., а„(т) п). Как известно, обычный метод состоит в том, что первый столбеп заменяется на д, = а,/!!а,~~, где !1э~! — евклидова норма.
Далее, если уже по. строены т)„„., т)„, то полагают я х мвтоды вычислиния 2!5 Однако если вычисления выполняются приближенно, Г только близка к Е и с! = гу! аг„уже не является решением системы (15). т При этом описанный выше процесс приводит к системе столбцов )у„..., гуы которая с высокой точностью порождает то же подпространство, что и столбцы а„..., а„. Отмечавшаяся выше неустойчивость метода ортогонализации состоит в том, что вычисленные столбцы гу! могут оказаться далеко не ортогональиыми, причем искажающее влияние ошибок округления тем больше, чем ближе столбцы а; к линейно зависимым. Чтобы избежать этого, мы должны решить систему (15), не используя ортонормнрованность вычисленных столбцов гу!. В этом случае ошибки, внесенные при вычислении )у„..., гуг, не влияютстольсущественио на вычисление гуг.!.
Можно воспользоваться методом простой итерации (ср. ~ 4 гл. П1), который здесь быстро сходится, поскольку матрица Г близка к единичной. Мы опишем здесь способ построения столбца )уггг, называемый методом переортогонализации. Пусть столбец и, полученный по формуле (16), не ортогонален гу„ ..., гуг.
Мы обозначим его через и!') н построим столбец и)м по формуле и)г) ц)!) ~~ ( утц)!)) )у )=! Вообще, может быть построена последовательность и)г) = = а„,, и"), и)г), ... согласно рекуррентному соотношению иы") = ион — ~ч ', (!утиц)) гу.. )=! Для произвольного члена этой последователю)ости рассмотрим произведения !утиц'!) при произвольном 1» и.
Мы имеем ! гутцц тц — тута)г) ~~ ( тцсо (гут)у ) )=1 Это означает, что строка р) г!) '))тутиыг!) „тц! ц)1 удовлетворяет соотношеншо ро "м = ры) (Š— Г). Последовательность рсн сходится к пулевой строке и притом очень быстро, так как Г близка к Е, Действительно, из свойств евклидовой нормы следует 1р'+!) 1» 1р!') ) 1Š— Г 1л» )! )а„! ~ 1 Š— Г Ць ', Докажем теперь, что последовательность и<') сходится.
Складывая почленно равенства вида (17) для всех а = а, ..., 13, мы гл. >ч псввдоэвшвния и псввдоовехтныв млтгицы получаем и<В> и<а) ~,' (<ути<В->> 1 1 сути< <=! (18) откуда 1и<В> и(а>ц~ ~х," ><ути<В->> 1 1 гугют(в>! ~<у,.$$» ! =- ! А  — ! '~ ~Отим> !.!<у 1 <=! 5=Я Считая, что <><у>1==2, и изменяя порядок суммирования, находим  †! ~ и<В> и<и> >>, 2 ~' 1 р<~> >т Так как 1-норма 1е1, не превосходит евклидовой нормы, имеем  †! я+! ~ и — и" >! ( 2 Ц а им ~ т ~ Š— Г !/'. ~ 1 . <Рв з=-а Поэтому предел п последовательности и'> удовлетворяет равенству е=а,,— ~," с><уь < --= ! где с,= 1пп с<Ю. Это показывает, что пФ- О, если только а,,г В со не является линейной комбинацией столбцов а„ ,.„ а,.
Как мы видели, у><'> †!- О (з — со). Поэтому столбец и ортогоналец всем <у„..., <у,. Разумеется, практически вместо е берется столбец и<'> с достаточно большим номером з. Так как !! Š— Г >!а мала, последовательность сходится быстро, и обычно можно ограничиться вычислением и<'>. После того как ненулевой столбец э, с должной точностью ортогональный столбцам <у„ ..., <уы построен, полагают гуда = = т>/<1 и !1 и переходят к вычислению <уд„.
Теперь нетрудно показать, что по заданному е ) О можно выбрать номер у так, чтобы!~ иоп — исо !! ( е, как только а, р у. Таким образом, мы видим, что последовательность и<'> удовлетворяет критерию Коши. Далее, полагая а =- О в формуле П8), находим, что при некоторых коэффициентах с<В> и =а„„вЂ” ~~ с! <у!. <В> — ч! <В> ! = ! $ х методы Вычисления 2!т ь1ы предполагали, что ортогонализуемые столбцы а,, ..., а„ линейно независимы. Освободимся от этого предположения.
Пусть столбец а»„линейно выражается через а„..., д». Тогда соответствующий столбец»з окажется нулевым. Он, естественно, не нормируется и не присоединяется к набору построенных ортонормированных столбцов. На следующем шагу столбец а»„ортогонализуется по отношению к имевшимся ранее столбцам дм ..., д». Заметим, что в случае, когда ранг матрицы неизвестен, может возникнуть затруднение: мы должны решить, считать ли столбец п нулевым, если его вычисленные элементы малы. Однако если эта трудность каким-то образом преодолена, мы можем для матрицы А размеров»п х п при и) и с помощью процесса ортогонализации построить дй-разложение А =- 1~Я, где Я вЂ” невырожденвая верхняя треугольная матрица, а матрица Я такова, что ее ненулевые столбцы ортонормированы.
Если т с и, то сохраняются те же рассуждения, только нулевые столбцы в матрице 1З появляются обязательно. 7. Использование дД-разложения. Покажем сначала, что дР-разложение произвольной матрицы Л позволяет по.чучить ее скелетнсе разложение. Для простоты записи будем считать, что в матрице А первые г столбцов базисные. Если это не так, всегда можно переставить столбцы, и, согласно предложению 8 2 1, это вызовет только перестановку строк в матрице А'.
Итак, матрица А считается разделенной на клетки А=1В, 5), причем клетка В размеров»п Х г имеет ранг г. Вычисляя дй-разложение А методом ортогонализаппи, мы приходим к невырожденной треугольной 'матрице Я порядка п такой, что АР = 1~, где Я имеет вид ()=1Р,, О), в котором клетка (), состоит из г ортонормированных столбцов. Столбец матрицы К с любым номером 1 состоит из коэфф»щиентов„с которыми столбец матрицы Я с тем же номером 1' раскладывается по столбцам матрицы А. При 1) г столбец Я нулевой.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
