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