Форсайт Дж., Малькольм М., Моулер К. - Машинные методы математических вычислений (1040536), страница 38
Текст из файла (страница 38)
198 х! 0', о, = О. 548 х 1 О', 6, = О,! 85 х 10! соответственно. Числа обусловленности равны 0.575 х!0' н 10.7; последнее значение более чем приемлемо даже при счете с обычной точностью. Вычисления можно теперь проводить и втой, и в другой разрядности; если заданная граница погрешности не будет слишком высока, то ни одно из сингулярных чисел не будет расценено как пренебрежимо малое. Все приближения, построенные этим способом, имеют достоверные коэффициенты, и все предсказывают, что численность населения в 1980 г. будет равна примерно 227.78 миллиона.
Мы все же не уверены, какова будет численность населения в !980 г. В попытке выяснить это можно увеличить степень полинома. Выбор базисных полиномов и границы для ошибки становится тогда более критическим. Возможно, и вероятно даже разумно, применить модели, основанные не на полиномах, а на каких-либо других функциях. Исследование этих возможностей предоставляется читателю в качестве упражнения. Главное, что мы хотели показать, это то, что использование сингулярного разложения предоставляет ценную информацию о надежности и чувствительности моделей, полученных методом наименьших квадратов, и помогает составителю таких моделей оценить их полезность.
Р.2. Ортогональность и сингулярное разложение Сингулярное разложение ягР является мощным вычислительным средством для анализа матриц и задач, связанных с матрицами, которое имеет приложения во многих областях. В последующих параграфах этой главы будет определено 51ЛЭ, описаны некоторые другие его применения и дан алгоритм для его вычисления. Этот алгоритм — типичный представитель используемых в настоящее время алгоритмов для решения различных матричных задач па собственные значения и может служить одновременно введением в численные методы для этих задач. Малоизвестно, что сингулярное разложение имеет довольно давнюю историю.
Основополагающими в большой мере были работы Голуба и его коллег Кахаиа, Бизингера и Райнша. Наше обсуждение будет построено главным образом на статье Голуб, я.я. Ортогондльиость 22! Райнпг (1971) '). Авторы используемых алгоритмов для матричных собственных значений — Фрэнсис, Рутисхаузер и Уилкинсои; эти алгоритмы описаны в книге Унлкинсон (19бб). Сравнительно недавно изданные книги Лоусон, Хэнсон (1974) и Стьюарт (1973) содержат ЯЧ1) и ряд примыкаюгцих сюда вопросов. В элементарной линейной алгебре множество векторов называется линейно независимым, если ни один из иих не может быть представлен в виде линейной комбинации других.
В вычислительной линейной алгебре очень полезно иметь количественную оценку «степени» независимости. Мы хотели бы определить величину, которая бы отражала тот факт, что, например, векторы О, 1 и 0 очень независимы, в то время как векторы 1.00, 1.01 и !.00 почти зависимы. Поскольку два вектора зависимы, если они параллельны, то разумно считать их очень независимыми, если они перпендикулярны нли ортогональны. Используем индекс Т, чтобы обозначать транспоиирование вектора или матрицы.
Два вектора и и о называются ортогональными, если их скалярное произведение равно нулю, т. е. если иго — 0 Далее, вектор и имеет длину 1, если ги Квадратная матрица называется ортогональной, если ее столбцы суть попарно ортогональные векторы длины 1. Таким образом, матрица 17 ортогональная, если и'17=7, где 7 — единичная матрица. Заметим, что ортогональная матрица автоматически не вырождена, поскольку 17 '=-17г. Вскоре мы придаднм точный смысл представлению о том, что ортогональная матрица очень не вырождена, а ее столбцы — очень независимьс.
') По существу, алгоритм сннгулярного раэложення содержится в работе В. В. Воеводина )968 г. (Ошнбкн онруглення в алгебранческнх процессах. сб, докладов под ред. В. В. Воеводина,— мл ВЦ мГУ, !968, с. 39 — 56).— Прим, перев. 9. НАИМЕНЬШИЕ КВАДРАТЫ Простейшими примерами ортогональных матриц являются плоские вращения вида соз О з|п О" сг =- — з|п О соз О) ' Если х — вектор в 2-пространстве, то !/х — тот же самый вектор, повернутый на угол О. Полезно ассоциировать ортогональные матрицы с такими вращениями, несмотря на то что для более высоких размерностей ортогональные матрицы могут быть устроены более сложно. Например, матрица 24 36 23 !У=49 41 12 — 24 12 — 3! 36 ортогональная, хотя ее нельзя интерпретировать как простое плоское вращение.
Умножение на ортогональные матрицы не изменяет такие важные геометрические величины, как длина вектора илн угол между двумя векторами. Ортогональные матрицы имеют также в высшей степени замечательные вычислительные свойства, поснольку они не увеличивают ошибок.
Для любой матрицы А н любых двух ортогональных матриц у и у рассмотрим матрицу Х, определяемую соотношением УТАУ Если и| и пг суть столбцы матриц У и У соответственно, то отдельные компоненты матрицы Х равны игА„ За сингулярным разложением скрывается та идея, что надлежащим выбором матриц !У и У можно обратить большинство элементов ан в нули; более того, можно даже сделать Х Диагональной с неотрицательными диагональными элементами, Поэтому дадим такое определение. Сингулярным разложением действительной тх и-матрицы А называется всякая ее факторизация вида А=и |тг, где С| — ортогональная тхт-матрица, 1' — ортогональная пх х п-матрица, а Х вЂ” диагональная т хи-матрица, у которой он=О при |чь!' и ои-— — о, .-О.
Величины о; называются сингулярными числами матрицы А, а столбцы матриц С| н У вЂ” левыми и правымн сингулярными векторачи. Читатели, знакомые с теорией матричных собственных значе-~ пий, отметят, что ненулевые собственные значения у матриц ААТ ~ 9 ь ОРтогонлльность 223 и А гА одни и те же и что сингулярные числа А суть положительные квадратные корни из этих собственных значений.
Кроме того, левые и правые сингулярные векторы суть частные выб:ры собственных векторов для ААг и А'А соответственно. На язьп<е збстрактной линейной алгебры матрица А является представлением некоторого линейного оператора в конкретных координатных системах. Вьполнян одно ортогональное преобразование координат в области определения оператсра, а другое ортогональное преобразование в области его значений, превращаем представление в диагональное. Чтобы упростить обозначения, предположим, что все прямоугольные матрицы имеют по крайней мере столько же строк, сколько столбцов, так что т и. В прпменепиях ВЧР к анализу экспериментальных данных матричный элемент аы представляет собой 1-е наблюдение 1-го переменного в эксперим нте, следовательно, ш — общее число наблюдений, а и — общее число переменных.
Нам приходилось встречать задачи, для которых т= =-!О 000, а а=5; однако наиболее распространены, по-видимому, задачи с тп=п. Предположение пг)п означает, что имеется и сингулярных чисел ои <'= — 1, ..., и. В сингулярном разложении имеется определенный произвол. Приведенное выше определение не фиксирует какой-либо конкретный порядок для сингулярных чисел. Даже если такой порядок указан, то столбцы матриц 11 и к", отвечающие кратным сингулярным числам, определены неоднозначно. Если проводить реальные вычисления по описываемой ниже подпрограмме ЗЧР, задавая одну и ту же матрицу на различных машинах с разной длиной слова пли даже только с различными программами извлечения квадратного корня, то могут быть получены совершенно разные матрицы 11 и У; однако результать<, вычисленные на любой машине, будут удовлетворять определению в пределах точности этой машины и давать удовлетворительные решения наших задач.
Приведем здесь пример с размерами 5хЗ; он будет использоваться иа протяжении всей главы. (Ради экономии места значения элементов приводятся лишь с тремя десятичными знакамн, хотя на практике работают обычно с большим числом знаков.) Заметим, что из-за нулевых столбцов в Х лишь самое большое первые п столбцов матрицы У могут действительно вносить вклад в произведение 1/ Х'к'г. Более того, если некоторые из сингулярных чисел равны нулю, то нужны менее чем п столбцов 11. Если к — количество ненулевых сингулярных чисел, то возможно сократить У до размеров пгхй, Х вЂ” до размеров экй н Кг — до размеров йхп.
Формально такие матрицы 1/ и г' не являются ортогональными, поскольку они не квадратные, однако их столбцы составляют ортонормированные системы векторов. Зтот а нАименьшие кВАдРАты 224 1 6 11 2 7 12 3 8 1Зэ 4 9 14 5 10 15 0.355 — 0.689 0.399 -0.376 0.443 -0.062 0.487 0.25! 0.53! 0.564 35.127 0 0 2.465 О 0 0 0 О,О 0.541 0.193 0.265 — 0.802 — О.!13 0.2!О О.!60 -0.587 -0.656 — 0.079 0.742 — 0.378 0.180 -0.235 0,559 0.202 0,890 0.408 !' = 0.517 0.257 — 0.816 ° 0.832 — 0.376 0.408 0.399 -0.376 У = 0.433 -0.062 0.487 0.251 0.531 0.564 35.127 О 0.202 0,890 0.517 0.257 ° 0.832 — 0.376 Понятие ранга матрицы имеет фундаментальное значение в большинстве разделов линейной алгебры. Согласно обычному вариант ЯЧ) можно назвать экономичным.
Экономия машинной памяти может быть весьма значительна, если е или п гораздо меньше, чем гл. Экономичный вариант нашего примера таков: 0,355 — 0.689 зх ОРтогонхльность 225 определению, это маисимальное число независимых столбцов, пли, что эквивалентно, максимальный порядок ненулевого минора матрицы. Основываясь на таком определении, трудно вычислять реально ранг матрицы общего вида. Однако если матрица диагональная, то ясно, что ее ранг равен числу ненулевых диагональных элементов.
Если независимая система векторов умножается на ортогональную матрицу, то полученная система по-прежнему независима. Другими словами, ранг произвольной матрицы А равен рангу диагональной матрицы Х в ее сингулярном разложении. Следовательно, практичным было бы определение ранга матрицы как количества ненулевых сингулярных чисел. Для обозначения ранга будем использовать букву и. (В примере н=-2,) Матрица размера тхн, т)п, называется матрицей полного ранга, если н=п, илн матрицей недостаточного рангси если н(п. Для квадратных матриц часто вместо полного и недостаточного ранга соответственно используют более привычные термины: нгвырожденная и вырожденная. Поскольку ранг матрицы всегда должен быть целым числом, он обязательно будет разрывной функцией элементов матрицы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
