Богачев - Практикум на ЭВМ. Методы решения линейных систем и нахождения собственных значений (947493), страница 11
Текст из файла (страница 11)
перехода от матрицы (4) к матрице (8), в й-ом столбце матрицы А~"~ образовались и — й нулевых элементов а ь = О, у = Й + 1,..., п. Поэтому возможно вместо матрицы Я вида (12) хранить на месте нижнего треугольника матрицы А набор параметров, с помощью которых можно вычислять тригонометрические функции углов р;1, 1' ( г, г = 2..., и, у' = 1,...,и — 1, задающих матрицы Т; . Конечно, проще всего было ~12. МЕТОД ВРАЩЕНИИ 51 бы хранить сами эти углы щ, но это требует вычисления обратных тригонометрических функций, что довольно медленно и вносит болыпую вычислительную погрегпность. На практике на месте а;, 1 < г, г = 2..., и, 1 = 1,..., и — 1 хранят соя у; или ейп у; — тот который имеет наименьший модуль. При этом на месте двух младших битов мантиссы этой величины хранятся признак того, что было запомнено: з1п или соя, и знак не запомненной тригонометрической функции.
Измененение двух младших битов мантиссы у соя д, или з1п у;. вносит погрешность, намного меньшую чем погрешность, с которой они вычислены. Запоминание значения соя д, или я1пу;, с наименьшим модулем уменьЮр~ ОС* Р ФО~У ~ ! Юц = ~ф-аОИ'Ю~ р;; = ~/~-а',ц.в ° р «р р,щ„ра е~,! 80х86, Мо1ого1а 68ххх, БРАКС, РоиегРС) поддерживают стандарт АИ81/1ЕЕЕ 754-1985 при работе с данными с плавающей точкой. Для таких процессоров младшие биты мантиссы являются младшими битами числа с плавающей точкой. При втором способе хранения матрицы Я не только экономится пэ ячеек памяти, но и экономится 2пэ+ 0(п~) (и -+ сс) умножений и пз+ 0(п2) (и -+ сс) сложений на построение матрицы Я.
Второму способу хранения благоприятствует также то обстоятельство, что редко требуется знать матрипу Я "саму по себе". Обычно требуется уметь вычислять ее произведения на вектор и матрицу. Для того, чтобы вычислить произведение матрицы Я вида (12) на некоторую матрицу В требуется вычислить п(п — 1)/2 произведений матриц элементарных вращений Т;, на В: ЮВ=П й (Т1В) ~=11=Н1 По лемме 5 на это потребеутся 2п (и — 1) умножений и п2(п — 1) сложений. По сравнению с количеством операций, необходимых для вычисления произведения двух матриц Я и В произвольного вида, число умножений тут в 2 раза болыпе, а число сложений совпадает. Если таких произведений требуется вычислить не очень много, то второй способ предпочтительнее первого.
З 12.5. Оценка количества арифметических операций в алгоритме построения ЯВ-разложения методом вращений Трудоемкость алгоритма построения ЯВ-разложения складывается из количества арифметических операций, необходимых для проведения алгоритма метода вращений, и количества арифметических операций, необходимых для построения матрицы Я.
Если для Я используется второй способ хранения, то дополнительных действий для ее построения не требуется. Следовательно, в этом случае для построения ЯВ-разложения надо выполнить 4~па+0(п2) (и -+ сс) мультипликативных операций и 2~па + 0(п2) (п -+ сс) аддитивных операций. К.Ю.Богачев Точные методы решения линейных систем ~13. МЕТОД ОТРАЖЕНИЙ 52 Если для Я используется первый способ хранения, то как показано вытпе для ее построения дополнительно к 1~по + 0(п2) (п -+ со) мультипликативным и ~~по + О(по) (и -+ со) аддитивным операциям, необходимых для проведения алгоритма метода вращений, требуется 2по+ 0(п~) (и — > со) умножений и по+ 0(п ) (и -+ оо) сложений, всего 1оп + 0(п2) (и -+ оо) мультипликативных операций и ~~по+ 0(п~) (п -+ оо) аддитивных операций.
2 13. МЕТОД ОТРА."~КЕНИИ Всюду в данном параграфе под нормой вектора будет пониматься евклидова норма, а под нормой матрицы — спектральная норма. Лемма 1. Спектральная норма всякой унитарной (ортпогональной в вещественном случае) матрицы равна 1.
Доказательство. Поскольку унитарные матрицы сохраняют евклидову длину вектора, по определению спектральной нормы получаем для всякой унитарной матрицы 1,г: !)Г!) = зпр = зпр = 1. !)Гх(/ !)х)/ . ~о 'ох'о *~о 'ох)/ Лемма 2. Собственные значения всякой унитарной матрицы по модулю равны 1.
Доказательство. Пусть Л вЂ” произвольное собственное значение матрицы Г. По лемме 1.4 )Л! < !)Ц = 1 — по предыдущей лемме. С другой стороны, Л ' является собственным значением матрицы С ', которая тоже унитарна. Опять по лемме 1.4 и лемме 1 (Л '! ( !)С ''О = 1, те. )Л! > 1. Следовательно, )Л! = 1. Лемма 3. Собственные значения всякой самосопряженной (симметричной в вещественном случае) матрицы А (т.е. А* = А) вещественны. Доказательство. Пусть Л вЂ” произвольное собственное значение матрицы А, х ф 0 — отвечающий ему собственный вектор, т.е. Ах = Лх.
Умножим это равенство скалярно на х: (Ах,х) = Л(х, х), откуда Л = (Ах,х)/~~х~)о. В силу замечания 9.1 выражение (Ах, х) вещественно для самосопряженной матрицы А. Следовательно, Л вещественно. К.Ю.Богачев Точные методы ретения линейных систем ~з13. МЕТОД ОТРАЖЕНИЙ З 13.1. Матрица отражения н ее свойства Определение. Магприцей отраженил называется матрица вида Г = У(х) = 1 — 2хх*, где х — единичный вектор (т.е.
~)х~! = 1). (Напомним, что х* (хы...,х„) — "матрица" размера 1 х п, х = (хы...,х„)' "матрица" размера п х 1 и потому хх* — матрица размера п х п.) Установим основные свойства матрицы отражения. Лемма 4. Матрица отраженил явллется самосопряженной матрицей. Доказательство. Вычислим сопряженную матрицу для матрицы отражения 11(х) (Г(х))* = (1 — 2хх*) = 1 — 2(х")'х* = 1 — 2хх* = Г(х), что и означает самосопряженность матрицы Г(х). Лемма 5. Матрица отраженил является унитарной матрицей.
Доказательство. Вычислим для матрицы отражения Г(х) Г(х)Г*(х) = Г(х) =(1 — 2хх*')(1 — 2хх*) =1 — 4хх*+4хх*хх* =1 — 4хх*+4х1х* =1, поскольку х'х = (х, х) = ~)хО~ = 1. Это равенство и означает унитарность ма- трицы Г(х). Лемма 6. Собстпвенные значения матрицы отр женил равны либо 1, либо — 1. Доказательство. Из лемм 2 и 4 вытекает, что собственные значения матрицы отражения по модулю равны 1. Из лемм 3 и 5 следует, что они вещественны. Значит, собственные значения есть либо 1 либо — 1. Лемма Т. Матрица отраженил 11(х) имеет собственное значение — 1 кратности 1, которому отвечает собсгпвенный вектор х, и собсгпвенное значение 1 кратносгпи п — 1, которому отвечает собственное подпространство (х) = (у: (у, х) = 01.
Доказательство. Имеем с1(х)х = (1 — 2хх*)х = х — 2хх*х = х — 2х = — х, поскольку х*х = (х,х) = ~~хО~ = 1. Следовательно, х — собственный вектор, отвечающий собственному значению — 1. Далее, для всех у Е (х) С(х)у = (1 — 2хх*)у = у — 2хх*у = у, поскольку х*у = (у, х) = О. Следовательно, у -собственный вектор, отвечающий собственному значению 1. Такие вектора у Е (х) образуют (п — 1)-мерное подпространство.
К.Ю.Богачев Точные методы ретения линейных систем ~г1 3. МЕТОД ОТРАЖЕНИЙ Лемма 8. Геометрический смысл преобразования, задаваемого матрицей отпраженил 17(х): отражение относительно гиперилоскости (х)-". Доказательство. Всякий вектор г е С" может быть представлен в виде г = сгх+ у, где у Е (х) . Здесь компонента сгх параллельна х, а компонента у ортогональна х, т.е. лежит в гиперплоскости (х).". В силу леммы 7 У(х)г = Цх)(ох+ у) = — сгх+ у, т.е. вектор г отразился относительно гиперплоскости (х) Лемма 9. Пусть е — произвольный единичный векншр: ]]е]] = 1.
Тогда для всякого вектора у Е С" существует вектор х Е С", ]]х]] = 1 такой, чшо 17(х)у = ]]у]]е. Доказательство. Так как вектора у и ]]у]]е должны быть получены друг из друга отражением относительно гиперплоскости (х), то вектор у — ]]у]]е должен быть параллелен х, т.е. х = а(у — ]]у]]е). Коэффициент а найдем из условия ]]х]] = 1. Получаем у — ]]у]]е ]]у — ]]у]]е]] Лемма 10. Произведение матрицы отражения на вектпор может бъипь вычислено за 2и+ О(1) (п -+ ос) сложений и столько же умножений (гпочнее,за 2и+ 1 умножение и 2п — 1 сложение).
Доказательство. Для матрицы отражения У(х) и произвольного вектора у имеем У(х)у = (1 — 2хх*)у = у — 2х(х*у) = у — 2х(у, х). На вычисление скалярного произведения (у, х) требуется и умножений и и — 1 сложение. На вычисление коэффипиента а = 2(у, х) требуется егце одно умножение. На вычисление линейной комбинации у — ах требуется и умножений и столько же сложений. Складывая эти оценки, находим, что всего необходимо и+ 1+ п = 2п+ 1 умножение и и — 1+ п = 2п — 1 сложений.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
