1611688890-f641c9ec8276824e4686da772eb56520 (826652), страница 45

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 45)

, m.Описанная выше процедура обработки матрицы данных называетсяметодом главных компонент в случае применения к матрице данных,которая центрирована путём вычитания из каждого столбца его среднего значения. При этом компонентами называются правые сингулярные векторы vk , а масштабированные левые сингулярные векторы σk ukносят название долей. Метод главных компонент обычно описывают в3.5. Обусловленность систем линейных уравнений271терминах собственных чисел и собственных векторов так называемойковариацонной матрицы A⊤A, но подход, основанный на сингулярномразложении, часто лучше с вычислительной точки зрения.Другая ситуация, в которой часто прибегают к методу главных компонент и которая не связана с необходимостью сжатия данных, — этожелание выделить из данных наиболее значимые факторы, т. е. комбинации переменных, наиболее существенные для рассматриваемого объекта или явления.

Здесь и пригождается понятие ранга матрицы илиже приближённого ранга для случая неточных данных.Приведённая выше теорема Экарта-Янга даёт математическую основу для решения поставленной задачи. Следует отметить, что соответствующие результаты неоднократно переоткрывались статистиками и,по-видимому, первым метод главных компонент предложил К. Пирсонв начале XX века, который отметил, что искомый минимум достигается в том случае, если базис { e1 , e2 , .

. . , ep } берётся в виде собственныхвекторов так называемой ковариационной матрицы C = A⊤A, отвечающих её p наибольшим собственным значениям. На современном языкеможно сказать, что искомый базис составлен из старших сингулярныхвекторов матрицы данных A, а «главными компонентами» обычно именуют компоненты разложения векторов данных по этому базису.3.5Обусловленностьсистем линейных уравнений3.5аЧисло обусловленности матрицВ этом параграфе мы вводим количественную меру чувствительности решения системы линейных алгебраических уравнений по отношению к вариациям матрицы и вектора правой части. Фактически, общиеидеи и понятия, развитые в §1.3, рассматриваются здесь в приложениик задаче решения систем линейных уравнений.Рассмотрим систему линейных алгебраических уравненийAx = bс неособенной квадратной матрицей A и вектором правой части b 6= 0,а также систему(A + ∆A) x̃ = b + ∆b,2723.

Численные методы линейной алгебрыгде ∆A ∈ Rn×n и ∆b ∈ Rn — возмущения матрицы и вектора правойчасти. Насколько сильно ненулевое решение x̃ возмущённой системыможет отличаться от решения x исходной системы уравнений?Пусть это отличие есть ∆x = x̃ − x, так что x̃ = x + ∆x, и потому(A + ∆A)(x + ∆x) = b + ∆b.Вычитая из этого равенства исходную невозмущённую систему уравнений, получим(∆A) x + (A + ∆A) ∆x = ∆b,(3.41)или(∆A)(x + ∆x) + A ∆x = ∆b.Вспоминая, что x + ∆x = x̃, можно заключить∆x = A−1 −(∆A) x̃ + ∆b .Для оценки величины изменения решения ∆x воспользуемся какойнибудь подходящей по условиям задачи векторной нормой.

Применяяеё к обеим частям полученного соотношения, будем иметьk∆xk ≤ kA−1 k · k∆Ak kx̃k + k∆bkпри согласовании используемых векторных и матричных норм. Предполагая, что возмущённое решение x̃ не равно нулю, можем поделитьобе части на kx̃k > 0, придя к неравенствуk∆xkk∆bk−1≤ kA k · k∆Ak +kx̃kkx̃kk∆Akk∆bk+= kA−1 k kAk ·.(3.42)kAkkAk · kx̃kЭто весьма практичная апостериорная оценка относительной погрешности решения, которую удобно применять после того, как приближённое решение системы уже найдено.8 Коль скоро kAk · kx̃k ≥kAx̃k ≈ kbk, то знаменатель второго слагаемого в скобках из правой8 От латинского словосочетания «a posteriori», означающего знание, полученноеиз опыта.

Под «опытом» здесь понимается процесс решения задачи.3.5. Обусловленность систем линейных уравнений273части неравенства «приблизительно не превосходит» kbk. Поэтому полученной оценке (3.42) путём некоторого огрубления можно придатьболее элегантный видk∆xkk∆Ak k∆bk,(3.43)/ kA−1 k kAk ·+kx̃kkAkkbkв котором справа задействованы относительные погрешности в матрице A и правой части b.Фигурирующая в оценках (3.42) и (3.43) величина kA−1 k kAk, на которую суммарно умножаются ошибки в матрице и правой части, имеетсвоё собственное название, так как играет важнейшую роль в вычислительной линейной алгебре.Определение 3.5.1 Для квадратной неособенной матрицы A величина kA−1 k kAk называется её числом обусловленности (относительно выбранной нормы матриц).Мы будем обозначать число обусловленности матрицы A посредством cond(A), иногда с индексом, указывающим выбор нормы.9 Еслиже матрица A особенна, то удобно положить cond(A) = +∞.

Это соглашение оправдывается тем, что обычно kA−1 k неограниченно возрастаетпри приближении матрицы A к множеству особенных матриц.Выведем теперь априорную оценку относительной погрешности ненулевого решения, которая не будет опираться на знание вычисленногорешения и годится для получения оценки до решения СЛАУ.10После вычитания точного уравнения из приближённого мы получили (3.41):(∆A) x + (A + ∆A) ∆x = ∆b.Отсюда∆x = (A + ∆A)−1 −(∆A) x + ∆b==−1A(I + A−1 ∆A)−(∆A) x + ∆b−1 −1I + A−1 ∆AA−(∆A) x + ∆b .9 В математической литературе для числа обусловленности матрицы A можновстретить также обозначения µ(A) или κ(A).10 От латинского словосочетания «a priori», означающего в философии знание,полученное до опыта и независимо от него.2743.

Численные методы линейной алгебрыБеря интересующую нас векторную норму от обеих частей этого равенства и пользуясь далее условием согласования с матричной нормой,субмультипликативностью и неравенством треугольника, получим−1 · kA−1 k · k∆Ak kxk + k∆bk ,k∆xk ≤ (I + A−1 ∆Aоткуда после деления обеих частей на kxk > 0:−1 k∆xk · kA−1 k · k∆Ak + k∆bk .≤ I + A−1 ∆AkxkkxkПредположим, что возмущение ∆A матрицы A не слишком велико,так что выполнено условие1k∆Ak ≤.kAkТогдаkA−1 ∆Ak ≤ kA−1 k k∆Ak < 1,и обратная матрица (I + A−1 ∆A)−1 разлагается в матричный ряд Неймана (3.37). Соответственно, мы можем воспользоваться вытекающейиз этого оценкой (3.38). ТогдаkA−1 kk∆bkk∆xk≤· k∆Ak +kxk1 − kA−1 k k∆Akkxk=kA−1 k · kAk·1 − kA−1 k k∆Akk∆bkk∆Ak+kAkkAk kxkcond(A)≤·k∆Ak1 − cond(A) ·kAkk∆Ak k∆bk,+kAkkbk(3.44)поскольку kAk kxk ≥ kAxk = kbk.Оценка (3.44) — важная априорная оценка относительной погрешности численного решения системы линейных алгебраических уравнений через оценки относительных погрешностей её матрицы и правойчасти.

Если величина k∆Ak достаточно мала, то множитель усиленияотносительной ошибки в данныхcond(A)k∆Ak1 − cond(A) ·kAk3.5. Обусловленность систем линейных уравнений275Рис. 3.9. Иллюстрация возмущения решения системы линейныхуравнений с плохой обусловленностью матрицы: малые «шевеления»любой прямой приводят к большим изменениям в решении.близок к числу обусловленности матрицы A.Понятие числа обусловленности матрицы и полученные с его помощью оценки имеют большое теоретическое значение, но их практическая полезность напрямую зависит от наличия эффективных способоввычисления или хотя бы приближённого оценивания числа обусловленности матриц.

Фактически, определение числа обусловленности требует знания некоторых характеристик обратной матрицы, и в случае общих матричных норм хорошего решения задачи оценивания cond(A)не существует до сих пор.Тем не менее, существует практически важный частный случай, когда число обусловленности матрицы имеет элегантное явное выражение, на основе которого можно достаточно эффективно организоватьего вычисление.

Это случай спектральной матричной нормы k · k2 , подчинённой евклидовой норме векторов.Напомним (Предложение 3.2.5), что для любой неособенной квад−1ратной матрицы A справедливо равенство σmax (A−1 ) = σmin(A), и поэтому относительно спектральной нормы число обусловленности матрицы естьσmax (A).cond2 (A) =σmin (A)Этот результат помогает понять большую роль сингулярных чисел в современной вычислительной линейной алгебре и важность алгоритмов2763. Численные методы линейной алгебрыдля их нахождения.

В совокупности с ясным геометрическим смысломевклидовой векторной нормы (2-нормы) это вызывает преимущественное использование этих норм для многих задач теории и практики.Рис. 3.10. Иллюстрация возмущения решения системы линейныхуравнений с хорошей обусловленностью матрицы: «шевеления»прямых приводят к соизмеримым изменениям в решении.Наконец, если квадратная n × n-матрица A симметрична (эрмитова), то её сингулярные числа σi (A) совпадают с модулями собственныхзначений λi (A), i = 1, 2 .

Характеристики

Список файлов книги