1611688890-f641c9ec8276824e4686da772eb56520 (826652), страница 44
Текст из файла (страница 44)
С2663. Численные методы линейной алгебрыпомощью ранга можно увидеть, к примеру, что все рассматриваемыеданные являются линейными комбинациями немногих порождающих.Ранг матрицы не зависит непрерывно от её элементов. Выражаясьязыком, который развивается в Главе 4 (§4.2), можно сказать, что задача вычисления ранга матрицы не является вычислительно-корректной.Как следствие, совершенно точное определение ранга в условиях «зашумлённых» данных, которые искажены случайными помехами и ошибками измерений, не имеет смысла. Нам нужно, как правило, знать«приближённый ранг», и при прочих равных условиях для его нахождения более предпочтителен тот метод, который менее чувствителенк ошибкам и возмущениям в данных.
Под «приближённым рангом»естественно понимать ранг матрицы, приближённо равной исходной всмысле некоторой разумной нормы. Здесь, правда, следует иметь в виду, что матрицы, «приближённо равные» данной в пределах указаннойточности, могут иметь разный ранг. Если требуется знать ранг, который гарантированно имеют все матрицы из рассматриваемого множества, то в качестве приближённго ранга имеет смысл взять минимальный из рангов всех матриц.Ясно, что ранг диагональной матрицы равен числу её ненулевыхдиагональных элементов.
Таким образом, ранг любой матрицы равенколичеству её ненулевых сингулярных чисел, что следует из сингулярного разложения (3.16), т. е. представленияA = U ΣV ∗и из того факта, что ортогональные преобразования сохраняют линейную зависимость или независимость.Другой способ нахождения ранга матрицы может состоять в приведении её к так называемому строчно-ступенчатому виду с помощьюпреобразований, которые использовались в прямом ходе метода Гаусса.Но в условиях неточных данных и неточных арифметических операций на ЭВМ строчно-ступенчатая форма является не очень надёжныминструментом из-за своей неустойчивости. Использование сингулярного разложения — более надёжный и достаточно эффективный подходк нахождению ранга матрицы.3.4бРешение систем линейных уравненийЕсли для матрицы A известно сингулярное разложение (3.16), тосистема линейных алгебраических уравнений Ax = b может быть пе-3.4. Приложения сингулярного разложения267реписана эквивалентным образом какU ΣV ∗ x = b.Отсюда решение легко находится в видеx = V Σ −1 U ∗ b.Получается, что для вычисления решения мы должны умножить вектор правой части на ортогональную матрицу, затем разделить компоненты результата на сингулярные числа и, наконец, ещё раз умножитьполучившийся вектор на другую ортогональную матрицу.
С учётомтого, что сингулярное разложение матрицы системы нужно ещё найти, вычислительной работы здесь существенно больше, чем при реализации, к примеру, метода исключения Гаусса (см. §3.6б) или другихпрямых методов решения СЛАУ. Но описанный путь безупречен с вычислительной точки зрения, так как позволяет без накопления ошибокнайти решение системы и, кроме того, проанализировать состояние еёразрешимости, указав ранг матрицы системы (см. предшествующийпункт).Напомним, что с геометрической точки зрения преобразования, осуществляемые ортогональными матрицами, являются обобщениями поворотов и отражений: они сохраняют длины и углы.
Поэтому в вычислительном отношении умножения на ортогональные матрицы обладают очень хорошими свойствами, так как не увеличивают ошибококруглений и других погрешностей. Ниже в §3.5б мы взглянём на этотфакт с другой стороны. Отличие в поведении и результатах методаГаусса и метода, основанного на сингулярном разложении, особеннозримо в случае, когда матрица системы «почти особенна».3.4вМалоранговые приближения матрицыПусть A — m × n-матрица, uk и vk — это её k-ые нормированныелевый и правый сингулярные векторы, а Υk обозначает их внешнеепроизведение, т. е.Υk = uk vk∗ .Отметим, что Υk — m × n-матрица ранга 1. Тогда сингулярное разложение (3.16) матрицы A равносильно её представлению в виде суммыA=nXk=1σk Υk ,(3.39)2683.
Численные методы линейной алгебрыгде σi , i = 1, 2, . . . , min{m, n}, — сингулярные числа матрицы A. Еслиσ1 ≥ σ2 ≥ . . . ≥ σn , и мы «обрубаем» выписанную сумму после p-гослагаемого (p ≤ n), то получающаяся матрицаAp =pXσk Υk ,(3.40)k=1называется p-ранговым приближением матрицы A.Это в самом деле матрица ранга p, что следует из её сингулярного разложения, а погрешность, с которой она приближает исходнуюматрицу, равнаnXσk Υk .k=p+1Величина этой погрешности решающим образом зависит от величинысингулярных чисел σp+1 , . .
. , σmin{m,n} , соответствующих отброшенным слагаемым в (3.39). Более точно, погрешность p-рангового приближения характеризуется следующим замечательным свойством:Теорема 3.4.1 Пусть σk , uk и vk — сингулярные числа, левые и правые сингулярные векторы m × n-матрицы A соответственно.
Еслиp<n иpXσk uk vk∗Ap =k=1— p-ранговое приближение матрицы A, тоkA − Ap k2 =minB∈Cm×nrank B≤pkA − Bk2 = σp+1 .Иными словами, относительно спектральной нормы p-ранговое приближение матрицы обеспечивает наименьшее отклонение от первоначальной матрицы среди всех матриц ранга не более p.Доказательство. Предположим, что найдётся такая матрица B, имеющая ранг rank B ≤ p, что kA − Bk2 < kA − Ap k2 = σp+1 .
Тогда существует (n − p)-мерное подпространство W ⊂ Cn , для которого справедливо w ∈ W ⇒ Bw = 0. При этом для любого w ∈ W мы имеемAw = (A − B)w, так чтоkAwk2 = k(A − B)wk2 ≤ kA − Bk2 kwk2 < σp+1 kwk2 .3.4. Приложения сингулярного разложения269Таким образом, W является (n − p)-мерным подпространством в Cn , вкотором kAwk2 < σp+1 kwk2 .Но в Cn имеется (p + 1)-мерное подпространство, образованное векторами v, для которых kAvk2 ≥ σp+1 kvk2 . Это подпространство, являющееся линейной оболочкой первых p + 1 правых сингулярных векторовматрицы A.
Поскольку сумма размерностей этого подпространства иподпространства W превосходит n, размерности всего пространства,то должен существовать ненулевой вектор, лежащий в них обоих. Этоприводит к противоречию.Совершенно аналогичный результат справедлив для фробениусовойнормы матриц, и исторически он был обнаружен даже раньше, чемТеорема 3.4.1:Теорема 3.4.2 (теорема Экарта-Янга [89]) Пусть σk , uk и vk — сингулярные числа и левые и правые сингулярные векторы m×n-матрицыA соответственно. Если p < n иAp =pXσk uk vk∗k=1— p-ранговое приближение матрицы A, тоkA − Ap kF =minB∈Cm×nrank B≤pkA − BkF = σp+1 ,где k · kF — фробениусова норма матриц. Иными словами, относительно фробениусовой нормы p-ранговое приближение матрицы обеспечивает наименьшее отклонение от первоначальной матрицы средивсех матриц ранга не более p.Доказательство опускается.Итак, если младшие сингулярные числа матрицы достаточно малы, то вместо неё можно взять p-ранговое приближение вида (3.40).Оно более «экономно», с меньшим числом параметров, приближённопредставляет исходную матрицу.3.4гМетод главных компонентВ качестве важного и интересного практического примера, которыйиллюстрирует понятия ранга матрицы, матричной нормы, сингуляр-2703.
Численные методы линейной алгебрыных чисел и сингулярных векторов матрицы и пр. рассмотрим так называемый метод главных компонент, широко применяемый в анализеданных и статистике.Во многих практических задачах приходится иметь дело с большими массивами числовых данных, характеризующих какой-либо объектили явление. Предположим для определённости, что набор параметров(свойств, признаков и т. п.) рассматриваемого объекта характеризуется вектор-строкой из n чисел, и мы имеем m штук таких векторов,относящихся, к примеру, к отдельным измерениям. Полученные данные образуют вещественную m × n-матрицу, которую мы обозначимчерез A.Нередко возникает необходимость сжатия данных, т. е. уменьшениячисла n параметров объекта с тем, чтобы оставшиеся p признаков,p ≤ n, всё-таки «достаточно наиболее полно» описывали всю совокупность накопленной об объекте информации, содержащейся в матрице A.
Метод главных компонент является одним из способов решенияпоставленного вопроса, который в формализованном виде принимает следующую форму: существует ли в Rn ортонормированный базис{ e1 , e2 , . . . , ep }, p < n, в котором рассматриваемые нами данные, содержащиеся в матрице A, будут представлены в наиболее экономичной(удобной, красивой и т. п.) форме?В качестве меры «близости» матриц мы можем брать различныерасстояния, получая различные постановки задач. Одним из практически наиболее важных является расстояние, порождённое фробениусовой нормой матриц, которое имеет ясный вероятностно-статистическийсмысл: с точностью до множителя оно совпадает с так называемойвыборочной дисперсией набора данных (см., к примеру, [77] или любой другой учебник по математической статистике).
Для фробениусовой нормы матриц математическая задача ставится следующим образом. Нужно найти такой ортонормированный базис { e1 , e2 , . . . , ep } вRn , p ≤ n, что квадратичное отклонение исходных Pвекторов данныхAi: = (ai1 , ai2 , . . . , ain )⊤ от их приближений X (i) = pj=1 xij ej в этомбазисе было бы наименьшим возможным для всех i = 1, 2, . . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
