Вычислительная математика лекции. Конспект лекций. Санкт петербург 2011 2 Оглавление
 Скачать 3.86 Mb.
|
|
17. 2. Сингулярное разложение матрицы. Рассматривается матрица A R m×n О п р е д е л е н и е.Сингулярным разложением матрицы А с вещественными элементами называется ее представление в виде A = UΣV T UU T = E m , VV T = E n , где U ортогональная матрица размера m ×m; V ортогональная матрица размера n ×n; Σ – диагональная матрица размера m×n с элементами ϭ kj = 0 при k ≠ j и ϭ kk = ϭ k ≥ 0. E m и E n единичные матрицы m ×m и n×n соответственно. Величины ϭ k называются сингулярными числами, а столбцы матриц U и V – левыми и правыми сингулярными векторами. Рассмотрим две симметрические матрицы AA T и A T A размера m ×m и n ×n соответственно: A T A = (UΣV T ) T UΣV T = VΣ T U T UΣV T = V(Σ T Σ)V T ; AA T = UΣV T ( UΣV T ) T = UΣV T VΣ T U T = U(ΣΣ T )U T Пусть для определенности m>n. Матрица A T A подобна матрице Σ T Σ и имеет собственные числа, равные квадратам сингулярных чисел матрицы А ( Σ T Σ это диагональная матрица n ×n с квадратами сингулярных чисел на диагонали). Аналогично первые n собственных чисел матрицы AA T также равны квадратам сингулярных чисел, а остальные m – n собственных значений равны нулю ( ΣΣ T это диагональная матрица m ×m с квадратами сингулярных чисел в первых n строках на диагонали и нулевыми 205 диагональными элементами в остальных m-n строках). Таким образом, сингулярные числа есть квадратные корни из положительных собственных чисел матриц A T A или AA T Сингулярное разложение удобно использовать для вычисления ранга произвольной матрицы А. Под рангом понимается число линейно независимых столбцов или строк матрицы. Если матрица диагональная, то ясно, что её ранг равен числу ненулевых диагональных элементов. Если независимая система векторов умножается на ортогональную матрицу, то полученная система попрежнему независима. Другими словами, ранг матрицы А совпадает с рангом матрицы Σ, т. е. с числом ненулевых сингулярных чисел. Можно показать, что rankA= rankAA T = rankA T A. Поскольку ранг матрицы всегда целое число, он обязательно будет разрывной функцией элементов матрицы. Произвольно малые изменения (например , ошибки округления) в матрице неполного ранга могут сделать все её сингулярные числа ненулевыми и, следовательно, породить матрицу, формально имеющую полный ранг. На практике используется понятие эффективного ранга – количество сингулярных чисел, удовлетворяющих условию ϭ k > ε, где ε погрешность исходных данных. Через сингулярные числа можно выразить число обусловленности матрицы полного ранга cond(A)= ϭ max /ϭ min . Это число не совпадает с ранее введенным, но обладает теми же свойствами и величиной того же порядка. В частности для квадратной матрицы определенное таким образом число обусловленности в точности равно cond 2 (A). 17. 3. Метод наименьших квадратов с использованием сингулярного разложения. Будем решать задачу наименьших квадратов для табличной функции, сформулированную в начале раздела. Замена табличной функции 206 линейной комбинацией базовых функций приводит, как правило, к несовместной системе линейных алгебраических уравнений Аα = f, где A R m×n , α R n , f R m . Часто m>n. Обозначим вектор невязки r = Аα – f. Решение задачи среднеквадратичного приближения заключается в минимизации длины вектора невязки (r,r) → min. После замены матрицы А ее сингулярным разложением система линейных алгебраических уравнений принимает вид ΣV T α = U T f. Обозначив = V T α, f = U T f, имеем Σ = f . Полученная система эквивалентна исходной. Новый вектор невязки имеет вид = Σ - f . Так как замена переменных выполнялась с ортогональными матрицами, длины прежнего и нового векторов невязки совпадают. Пусть m > n. Компоненты вектора невязки = Σ - f разбиваются на две группы k = k ϭ k -f k , k=0,1,…,n-1; k =0 - f k , k =n, …, m-1. Здесь ϭ k сингулярные числа. Для удобства предполагается ϭ 0 ≥ ϭ 1 ≥ … ≥ ϭ n-1 ≥ 0. При m = n вторая подсистема отсутствует. Задача среднеквадратичного приближения превращается в задачу интерполяции. Минимум длины вектора невязки достигается, если в первой группе положить (в предположении ϭ k ≠ k = f k /ϭ k , k = 0,1, …, n-1. Значение минимума длины вектора невязки определяются второй группой компонентов и для m = n (в предположении ϭ k ≠ равно нулю. 207 Пусть некоторая часть ϭ k , например, ϭ n-1 = 0. Это означает, что матрица А матрица неполного ранга. Тогда последний из компонентов первой группы переходит во вторую, увеличивая значение минимума длины вектора невязки. Этот минимум не зависит от выбора n-1 . Переходя к исходному вектору коэффициентов α имеем α = V = 2 1 1 0 n n k k n k v v Здесь v n-1 последний столбец матрицы V, k=0, 2 k n однозначно определенные элементы из первой подгруппы, а коэффициент n-1 может задаваться произвольно. Часто полагают n-1 = 0, тем самым выделяя вектор коэффициентов α с минимальной длиной. Если матрица А плохо обусловлена, то чувствительность решения к погрешностям исходных данных становится высокой. Для повышения надежности решения вводится параметр ε, характеризующий точность исходных данных. Сингулярные числа, меньшие ε, полагают равными нулю и соответствующие компоненты первой подгруппы переносятся во вторую. Рассмотрим случай m < n (число столбцов матрицы Σ больше числа строк и ее последние n – m столбцов всегда нулевые ). Если все ϭ k сингулярные числа ненулевые, то вторая подгруппа компонентов отсутствует, а первая принимает вид k = k ϭ k - f k , k=0,1,…,m-1. Первые m значений k выбираются из условия k = f k /ϭ k , k = 0,1, …, m-1, обеспечивая нулевое значение длины вектора невязки. Остальные k могут выбираться произвольно. Наиболее популярен нулевой выбор их значений. Если некоторые ϭ k = 0, то последние компоненты из первой подгруппы переходят во вторую, образуя ненулевую длину вектора 208 невязки, а количество свободно задаваемых k увеличивается на число нулевых ϭ k 18. Псевдообратная матрица. Псевдообратные матрицы – обобщение обратных матриц в линейной алгебре. Псевдообратная матрица к матрице А обозначается А + Псевдообращение можно понимать как наилучшую аппроксимацию (по методу наименьших квадратов) решения соответствующей систеиы линейных уравнений. Псевдообращение определено для любых матриц над действительными и комплексными числами. Псевдообратная матрица может быть вычислена с использованием сингулярного разложения. В дальнейшем ограничимся рассмотрением вещественных матриц. Пусть A R m×n , тогда решение системы Ax=b можно записать x=A + b. Определение. А + называется псевдообратной матрицей для матрицы А, если она удовлетворяет следующим критериям: 1. АА + А=А; 2. А + АА + =А + ; 3. (АА + ) Т =АА + (это означает, что АА + - симметрическая матрица); 4. (А + А) Т =А + А (А + А – тоже симметрическая матрица). Свойства: • Псевдообращение обратимо более того эта операция обратима самой себе: (А + ) + =А. • Псевдообращение коммутирует с транспонированием (А Т ) + =(А + ) Т • Псевдообратное произведение матрицы на скаляр α равно соответствующему произведению матрицы А + на обратное число α -1 : (αА) + =α -1 А + , для α ≠0. • Если псевдообратная матрица для А Т А уже известна, она может быть использована для вычисления А + : А + =(А Т А) + А Т 209 • Аналогично, если матрица (АА Т ) уже известна: А + =А Т (АА Т ) + Особые случаи. • Если столбцы матрицы А линейно независимы, тогда матрица А Т А обратима. В таком случае псевдообратная матрица задается формулой А + =(А Т А) -1 А Т Отсюда следует, что А + - левая обратная для А: А + А=Е. • Если строки матрицы А линейно независимы, тогда матрица АА Т обратима. В таком случае псевдообратная матрица задается формулой А + =А Т (АА Т ) -1 Отсюда следует, что А + - правая обратная для А: АА + =Е. • Если столбцы и строки матрицы А линейно независимы (что верно для квадратных невырожденных матриц), псевдобращение равно обращению: А + =А -1 • Псевдообращение можно применять к скалярам ивекторам. Псевдообращение к скаляру х – ноль, если х=0, и обратный к х=х -1 в противном случае. • Псевдообратный для нулевого вектора – транспонированный нулевой вектор. Псевдообратный для иного вектора транспонированный вектор, деленный на квадрат своей длины: х + =х Т /(х Т х). Для доказательства достаточно проверить, что эти величины удовлетворяют определению псевдообратных. Вычисление Можно показать, что А + существует и единственна и для её построения применяется сингулярное разложение. С этой целью для заданного числа σ рассчитывают 1 , если 0 0, если 0 Для матрицы Σ размера m ×n введём матрицу Σ + размера n ×m: 210 0 0 1 1 , n n m n m n Тогда для исходной матрицы А=UΣV T её псевдообратная матрица задается формулой A + =VΣ + U T . Легко проверить, что, рассчитанная указанным образом A + , удовлетворяет определению псевдообратных. Как и ранее для уменьшения числа обусловленности и повышения надежности результата можно ввести эффективную псевдообратную матрицу A . С этой целью следует положить 1 , если 0, если Непосредственной проверкой можно убедиться, что A удовлетворяет условиям (2), (3), (4). Первое условие удовлетворяется с точностью ε: ||AA + A-A|| ε. Пример. Решается линейная система Ax=b : 1 2 1 1 4 1 1 6 x x Матрица А вырождена, система несовместна. Попытаемся найти нормальное решение, т. е. его аппроксимацию методом наименьших квадратов. Воспользовавшись процедурой svd, вычислим сингулярное разложение матрицы А=UΣV T 1 1 1 1 2 0 2 2 2 2 ; = ; V= 1 1 0 0 1 1 2 2 2 2 U Имеем 211 1 1 10 4 4 2 2 2 ; = = 6 1 1 6 2 2 2 2 T x b b U 1 – ая группа уравнений: 1 1 1 10 5 2 ; ; 2 2 r x x 2 – ая группа уравнений 2 2 2 2 0 ; 0; 2 r x x Компонент 2 x вектора x можно задавать произвольно, но, чтобы обеспечить минимальную длину вектора x, следует положить 2 0. x Возвращаемся к исходному вектору x: 1 1 5 5 5 2 2 2 2 2 1 1 5 0 0 2 2 2 x V Решим ту же задачу, используя псевдообратную матрицу. A + =UΣ + V T ; 1 1 1 0 4 4 ; A 2 1 1 0 0 4 4 1 1 5 4 4 4 2 1 1 6 5 4 4 2 x A b 212 Рекомендуемая литература Основная литература: 1. Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы. – Изд. 3-е, доп. и перераб.– М., БИНОМ, 2003, - 632 с. 2. Устинов С.М., Зимницкий В.А. Вычислительная математика. – СПб.: БХВ, 2009.- 336 с. 3. Вержбицкий В.М. Основы численных методов: Учебник для вузов – М.: Высш. шк., 2009.- 840 с. Дополнительная литература: 1. Бахвалов Н.С., Лапин А.В., Чижонков Е.В. Численные методы в задачах и упражнениях: Уч. пособие. – М.: Высшая школа, 2000. – 190 с. 2. Вержбицкий В.М. Численные методы ( линейная алгебра и нелинейные уравнения). – М.: Высшая школа, 2000.- 266 с. 3. Козлов В.Н., Куприянов В.Е., Шашихин В.Н. Вычислительная математика и теория управления: Учеб. пособие. – СПб.; Изд. СПбГТУ, 1996, - 284 с. 4. Волков Е.А. Численные методы. – М.: Наука, 2008, - 256с. 213 |