Введение 3
1. Сингулярное разложение 6
2. Основные понятия 7
3. Теоремы о сингулярном разложение матриц 10
4. Алгоритмы, используемые для практического вычисления сингулярного
разложения 13
5. Применения сингулярного разложения 14
6. Сжатие изображения 19
7. Использование сингулярного разложения для решения плохо обусловленных
систем 23
Заключение 29
Список литературы 30
Приложение 31
Сингулярное разложение (Singular Values Decomposition, SVD) является удобным методом при работе с матрицами. Сингулярное разложение показывает геометрическую структуру матрицы и позволяет наглядно представить име-ющиеся данные. Сингулярное разложение используется при решении самых разных задач — от приближения методом наименьших квадратов и решения систем уравнений до сжатия и распознавания изображений.
Сингулярное разложение было первоначально разработано в дифференциальной геометрии при изучении свойств билинейных форм учеными Эудженио Бельтрами и Жорданом Камилем в 1873 и 1874 годах [1].
Джеймс Джозеф Сильвестр пришел к понятию сингулярного разложения для квадратных матриц в 1889 году и, вероятно, также независимо от Эудженио Бельтрами и Жордана Камиля. Сильвестр называл сингулярные значения кано-ническими множителями матрицы. Первое доказательство сингулярного разложения для прямоугольных и комплексных матриц было осуществлено мате-матиками Карлом Эскартом и Гейлом Янгом в 1936 году.
В 1907 году Эрхард Шмидт определил аналог сингулярного разложения для интегральных операторов, не зная о том, что параллельно ведется работа над сингулярным разложением для конечномерных матриц. Его теория была дальше развита математиком Эмилем Пикаром в 1910 году. Именно Пикар пер¬вым назвал сгп сингулярными значениями.
Практические методы вычисления SVD-разложения восходят к работам Ерванда Когбетлянца в 1954, 1955 и Дэвида Хестенса в 1958 г., алгоритм кото¬рых сильно напоминает метод вращения Якоби для вычисления собственных значений с использованием поворотов Гивенса. Однако этот алгоритм был заменен методом, разработанным математиками Джином Голубом и Уильямом Кэхэном в 1965 г., который использует преобразования Хаусхолдера [2,190]. В 1970 году Джин Голуб и Кристиан Рейнш опубликовали вариант алгоритма Го- 3
луба-Кэхэна, который до сих пор является одним из самых используемых.
В данной работе речь пойдет о вычислении сингулярного разложения мат¬риц [2-4], а именно как и для чего вычисляется сингулярное разложение, а так¬же области его применения - это нахождение ранга матрицы, определителя матрицы, чисел обусловленности, общих решений однородных систем, для решения произвольной СЛАУ, нахождения псевдообратных матриц.
Рассматривается перспективный метод для точного решения почти сингу-лярных систем линейных уравнений. В методе используется усеченная сингу-лярная декомпозиция [2, 8]. Этот метод не требует дополнительных сведений о свойствах матрицы. Также рассматриваются алгоритмы сингулярного разложения матриц, которые используются для практического вычисления, свойства сингулярного разложения.
На примерах систем линейных уравнений с матрицами, близких к сингу-лярным, показано, как применяется SVD. В качестве примеров используются системы с Гильбертовой матрицей [6,10], проведены исследования с помощью процедур SVD и исключения Гаусса, данный численный опыт показал хоро¬шую точность предлагаемой схемы решения. Также на примере сжатия изображения показано, что SVD - удобный способ для сжатия изображения с мини¬мальной потерей информации, поскольку показана возможность существенного сокращения требуемого объема памяти для хранения изображений без существенной потери качества их представления.
Цели:
1) Изучить основные понятия сингулярного разложения (SVD).
2) Применить SVD для сжатия изображений и показать, что это SVD- разложение является эффективным способом для сжатия изображений с минимальной потерей информации.
3) На примерах систем линейных уравнений с матрицами, близких к сингулярным, показать, как применяется усеченное сингулярное разложение для решения таких линейных систем.
В данной работе были рассмотрены SVD - разложение, сингулярные числа, сингулярные векторы. Изучены теоремы и свойства сингулярного разложения, а также области применения S VD на практике.
На примере изображений, полученных в результате магнитно-резонансной томографии и фотографии Главного корпуса ТГУ, показана возможность существенного сжатия этих изображений с помощью сингулярного разложения (уменьшение размера изображения в байтах) без потери качества при исключе¬нии малозначимых компонент. Проведен анализ полученных данных для изоб¬ражений и сделан вывод, что эффективность алгоритма значительно выше в том случае, если на картинке не преобладают мелкие элементы.
Приведены результаты решения плохо обусловленной системы линейных уравнений с Гильбертовой матрицей порядка 8 и 10 (число обусловленности 1О10 и 1013, соответственно), с помощью аналитического решения, полученного в пакете Wolfram Mathematica, исключения Гаусса, SVD, TSVD [6]. Сделан вывод, что для данного примера наиболее лучшим является TSVD, поскольку ближе к аналитическому решению является результат, полученный с помощью TSVD [6], чем выше порядок матрицы, тем она хуже обусловлена и каждый метод стал больше отклоняться от точного решения, как раз это продемонстрировано в таблицах 3-4.
