1611688890-f641c9ec8276824e4686da772eb56520 (826652), страница 51
Текст из файла (страница 51)
Рассмотрим, к примеру,3123. Численные методы линейной алгебрырешение системы линейных алгебраических уравнений Ax = b методом Гаусса в его матричной интерпретации. Обнуление поддиагональных элементов первого столбца матрицы A — это умножение исходнойСЛАУ слева на матрицу E1 , имеющую вид (3.62), так что мы получаемсистему(E1 A) x = E1 b(3.80)с матрицей E1 A, число обусловленности которой оценивается какcond(E1 A) ≤ cond(E1 ) cond(A).Перестановка строк или столбцов матрицы, выполняемая для поискаведущего элемента, может незначительно изменить эту оценку в сторону увеличения, так как матрицы перестановок ортогональны и имеют небольшие числа обусловленности.
Далее мы обнуляем поддиагональные элементы второго, третьего и т. д. столбцов матрицы системы(3.80), умножая её слева на матрицы E2 , E3 , . . . , En−1 вида (3.63). Врезультате получаем верхнюю треугольную систему линейных уравненийU x = y,в которой U = En−1 . . . E2 E1 A, y = En−1 . . . E2 E1 b, и число обусловленности матрицы U оценивается сверху какcond(U ) ≤ cond(A) · cond(E1 ) · cond(E2 ) · . .
. · cond(En−1 ).(3.81)Если Ej отлична от единичной матрицы, то cond(Ej ) > 1, причёмнесмотря на специальный вид матриц Ej правая и левая части неравенства (3.81) могут отличаться не очень сильно (см. примеры ниже).Как следствие, обусловленность матриц, в которые матрица A исходной СЛАУ преобразуется на промежуточных шагах прямого хода метода Гаусса, а также обусловленность итоговой верхней треугольнойматрицы U могут быть существенно хуже, чем у матрицы A.Пример 3.7.1 Для 2 × 2-матрицы (3.14)1 2A=3 4число обусловленности равно cond2 (A) = 14.93. Выполнение для неёпреобразований прямого хода метода Гаусса приводит к матрице1 2,Ã =0 −23.7.
Методы на основе ортогональных преобразований313число обусловленности которой cond2 (Ã) = 4.27, т. е. уменьшается.С другой стороны, для матрицы (3.15)B=1−324,число обусловленности cond2 (B) = 2.62. Преобразования метода Гауссапревращают её в матрицуB̃ =1 20 10,для которой число обусловленности уже равно cond2 (B̃) = 10.4, т. е.существенно возрастает.Аналогичные изменения претерпевают числа обусловленности матриц A и B относительно других норм. Числовые данные этого примерачитатель может воспроизвести с помощью систем компьютерной математики, таких как Scilab, Matlab и им аналогичных, где есть встроенная функция cond для расчёта числа обусловленности матрицы. Фактически, ухудшение обусловленности и, как следствие, всё бо́льшая чувствительность решения к погрешностям в данных — это дополнительная плата за приведение матрицы (и всей СЛАУ) к удобному длярешения виду.
Можно ли уменьшить эту плату? И если да, то как?Хорошей идеей является привлечение для матричных преобразований ортогональных матриц, которые имеют наименьшую возможнуюобусловленность в спектральной норме (и небольшие числа обусловленности в других нормах). Умножение на такие матрицы, по крайнеймере, не будет ухудшать обусловленность получающихся систем линейных уравнений и устойчивость их решений к ошибкам вычислений.По-видимому, с точки зрения устойчивости наилучшим инструментом численного решения систем линейных алгебраических уравненийна цифровых ЭВМ с конечной точностью представления данных является сингулярное разложение матрицы системы. При этом двумя ортогональными преобразованиями эта матрица приводится к диагональному виду.
Соответствующую технологию мы обсуждали в §3.4б. Нонахождение сингулярного разложения матрицы — задача более сложная и трудоёмкая, чем рассматриваемые нами прямые методы решенияСЛАУ.3143.7б3. Численные методы линейной алгебрыQR-разложение матрицОпределение 3.7.1 Для матрицы A представление A = QR в видепроизведения ортогональной матрицы Q и правой треугольной матрицы R называется QR-разложением.По поводу этого определения следует пояснить, что правая треугольная матрица — это то же самое, что верхняя треугольная матрица, которую мы условились обозначать U .
Другая терминология обусловлена здесь историческими причинами, и частичное её оправданиесостоит в том, что QR-разложение матрицы действительно «совсемдругое», нежели LU-разложение. Впрочем, в математической литературе можно встретить тексты, где LU-разложение матрицы называется«LR-разложением» (от английских слов left-right), т. е. разложением на«левую и правую треугольные матрицы».QR-разложение матриц часто определяют также для общих прямоугольных матриц, не обязательно квадратных. Если A — это m × nматрица, то представление A = QR может трактоваться как произведение ортогональной m × m-матрицы Q на трапецеидальную m × nматрицу R или же как произведение m × n-матрицы Q с ортогональными строками (столбцами) на правую треугольную n × n-матрицу R.На практике встречаются оба вида разложений.Теорема 3.7.1 QR-разложение существует для любой квадратнойматрицы.Доказательство.
Если A — неособенная матрица, то, как было показано при доказательстве Теоремы 3.6.4, A⊤A — симметричная положительно определённая матрица. Следовательно, существует её разложение ХолесскогоA⊤A = R⊤R,где R — правая (верхняя) треугольная матрица. При этом R, очевидно,неособенна. Тогда матрица Q := AR−1 ортогональна, посколькуQ⊤ Q = AR−1⊤= (R−1 )⊤AR−1 = (R−1 )⊤ A⊤A R−1R⊤ R R−1 = (R−1 )⊤ R⊤ RR−1 = I.Следовательно, в целом A = QR, где определённые выше сомножителиQ и R удовлетворяют условиям теоремы.3.7.
Методы на основе ортогональных преобразований315Рассмотрим теперь случай особенной матрицы A. Известно, чтолюбую особенную матрицу можно приблизить последовательностьюнеособенных. Например, это можно сделать с помощью матриц Ak =A + k1 I, начиная с достаточно больших натуральных номеров k. Приэтом собственные значения Ak суть λ(Ak ) = λ(A) + k1 , и если величина1k меньше расстояния от нуля до ближайшего ненулевого собственногозначения матрицы A, то Ak неособенна.В силу уже доказанного для всех матриц из последовательности{Ak } существуют QR-разложения:Ak = Qk Rk ,где все Qk ортогональны, а Rk — правые треугольные матрицы. В качестве ортогонального разложения для A можно было бы взять пределы матриц Qk и Rk , если таковые существуют.
Но сходятся ли куданибудь последовательности этих матриц при k → ∞, когда Ak → A?Ответ на это вопрос может быть отрицательным, а потому приходитсядействовать более тонко, выделяя из {Ak } подходящую подпоследовательность.Множество ортогональных матриц компактно, поскольку являетсязамкнутым (прообраз единичной матрицы I при непрерывном отображении X 7→ X ⊤ X) и ограничено (kXk2 ≤ 1). Поэтому из последовательности ортогональных матриц {Qk } можно выбрать сходящуюсяподпоследовательность {Qkl }∞l=1 . Ей соответствуют подпоследовательности {Akl } и {Rkl }, причём первая из них также сходится, как подпоследовательность сходящейся последовательности {Ak }.Обозначим Q := liml→∞ Qkl , и это также ортогональная матрица.Тогда⊤⊤lim Q⊤kl Akl = lim Qkl · lim Akl = Q A = Rl→∞l→∞l→∞— правой треугольной матрице, поскольку все Q⊤kl Akl были правымитреугольными матрицами Rkl .
Таким образом, в целом снова A = QRс ортогональной Q и правой треугольной R, как и требовалось.Если известно QR-разложение матрицы A, то решение исходнойСЛАУ, равносильной(QR)x = bсводится к решению треугольной системы линейных алгебраическихуравненийRx = Q⊤ b.(3.82)3163. Численные методы линейной алгебрыНиже в §3.15 и §3.18г мы встретимся и с другими важными применениями QR-разложения матриц — при численном решении линейнойзадачи наименьших квадратов и проблемы собственных значений.Для неособенных матриц доказательство Теоремы 3.7.1 носит конструктивный характер, но оно опирается на разложение Холесскогоматрицы A⊤A. По этой причине нахождение с его помощью QR-разложения — это окольный путь, чреватый многими опасностями. В частности, приближённый характер вычислений на цифровых ЭВМ будетприводить к тому, что ортогональная матрица в получающемся QRразложении не вполне ортогональна. На практике основным инструментом получения QR-разложения является техника, использующаятак называемые матрицы отражения и матрицы вращения, описаниюкоторых посвящены следующие разделы книги.3.7вОртогональные матрицы отраженияОпределение 3.7.2 Для вектора u ∈ Rn с единичной евклидовой нормой, kuk2 = 1, матрица H = H(u) = I − 2uu⊤ называется матрицейотражения или матрицей Хаусхолдера.
Вектор u называется порождающим или вектором Хаусхолдера для матрицы отражения H(u).Предложение 3.7.1 Матрицы отражения являются симметричными ортогональными матрицами. Кроме того, для матрицы H(u)порождающий вектор u является собственным вектором,отвечающим собственному значению (−1), т. е. H(u) · u = −u;любой вектор v, ортогональный порождающему вектору u,является собственным вектором, отвечающим собственномузначению 1, т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
