Дж. Деммель - Вычислительная линейная алгебра, страница 33

Новые версии 1АРАСК'а будут содержать улучшенные варианты ь)В; алгоритмов с выявлением ранга и метода БЧП для задачи наименьших квадратов. З.Т. Литература и смежные вопросы к главе 3 Наилучшим в настоящее время справочником по задачам наименьших квадратов является книги [33], где излагаются варианты обсулсдавшейся здесь основной задачи (такие, как задачи с ограничениями и весами, или перестройка решения при малоранговой модификации задачи), различные способы регуляризации в случае неполного ранга и программы для разреженных задач. См. также гл.

5 книги [121] и [168]. Теория возмущений и границы ошибок для решения задачи наименьших квадратов подробно изложены в [149]. ЯВ; разложения с выявлением ранга обсуждаются в [28, 30, 48, 50, 126, 150, 196, 206, 236]. В этих статьях исследуется, в частности, зависимость между трудоемкостью метода и надежностью определения ранга. В [206] проведено, кроме того, обширное сравнение производительности существующих методов для задач неполного ранга. 3,8. Вопросы к главе 3 Вопрос 3.1 (легкий). Показать, что два варианта алгоритма 3.1 - методы ССБ и МСБ, — математически эквивалентны. Для этого показать, что две формулы для г; в алгоритме 3.1 дают в точной арифметике один и тот же результат.

Вопрос 3.2 (легкий). Этот вопрос иллюстрирует различие в численной устойчивости трех алгоритмов вычисления ЯН-разложения матрицы: метода отражений (алгоритм 3.2), метода ССБ (алгоритм 3.1) и метода МСБ (алгоритм 3.1). Импортируйте Ма11аЪ-программу ЯНБ1аЬ11Ыу.ш из НОМЕРАСЕ/МапаЬ/ ь111Б»аЬ1В1у.ш. Эта программа генерирует случайные матрицы с задаваемы- 3.8, Вопросы к главе 3 ми пользователем размерами ш и и и числом обусловленности спй; для них указанными выше тремя алгоритмами вычисляется Яй-разложение и оценивается точность полученного результата.

Это делается с помощью невязки [~А — Я Щ/~8А[[, которая для устойчивого алгоритма должна быть величиной порядка машинного эпсилон е, и меры ортогональнвсти '8Я~ (> — Ц, которая тоже должна быть величиной порядка е. Поработайте с этой программой, используя умеренное число (вашр1ев = 20) случайных матриц с малыми размерами (например, ш = 6 и и = 4) и числами обусловленности, изменяющимися от спй =1 до спй = 10'е.

Опишите ваши выводы. Какой из алгоритмов устойчивей других? Попробуйте охарактеризовать возможную величину меры ортогональности 6Чт Я вЂ” 1~[ как функцию от выбора алгоритма, а также чисел сва и е. Вопрос 3.3 (средней трудности; трудный). Пусть А — матрица полного ранга и размера т х и, где т ) п. А1 1. (средней трудности). Показать, что система линейных уравнений ~ т [,) = [в1 совместна и компонента х ее решения минимизирует функцию Гг) [[Ах — Ь|[г.

Одно кз достоинств этой формулировки состоит в том, что при необходимости получить более точное решение мы можем применить к данной системе алгоритм итерационного уточнения (см. равд, 2.5). 2, (средней трудности). Выразить число обусловленности матрицы А через ее сингулярные числа. Указание: использовать сингулярное разложение матрицы. 3.

(средней трудности). Для обратной матрицы А 1, представленной в блочном 2 х 2-виде, дать явные выражения блоков через блоки матрицы А. Указание: использовать блочное 2 х 2 гауссово исключение. Где нам уже встречался блочный элемент (2, 1)? 4. (трудный). Указать способ использования ЯГс-разложения матрицы А в рамках алгоритма итерационного уточнения приближенного решения х. Вопрос 3.4 (средпей трудности).

Взвешенные наименьшие квадраты. Предположим, что некоторые компоненты вектора Ах — Ь важнее других. Тогда можно снабдить их весами, т. е. числовыми множителями до и решать вместо обычной задачи наименьших квадратов взвешенную задачу ппп8гг(Ах — Ь)[~г, где диагональная матрица В составлена из чисел дь Более общо, вспомним, что для симметричной положительно определенной матрицы С формула ~[х~~с = (х Сх)'~~ задает норму, поэтому можно рассмотреть задачу минимизации функции 8Ах — 5[~с.

Вывести нормальные уравнения для этой задачи, а также постановку, согласованную с предыдущим вопросом. Вопрос 3.5 (средней трудности; в. Ва1). Пусть А — положительно определенная п х и-матрица. Говорят, что векторы и1 и иг А-ортогональны, если и1тАиг = О. Если ГГ й ш™" и Г?тАГГ = 1, то говорят, что столбцы матрицы ГГ А-ортогонвльны.

Показать, что всякое линейное подпространство имеет А-ортонормальный базис. 146 Глава 3. Линейные задачи наименыоих квадратов Вопрос 3.6 (легкий; Т Ва»). Пусть матрица А имеет форму где  — верхнетреугольная и х п-матрица, а Я вЂ” плотная матрица размера и хи. Описать алгоритм приведения А к верхней треугольной форме, основанный на использовании отражений. Ваш алгоритм не должен кзаполнять» нули в В. Он будет, следовательно, более экономичным, чем алгоритм 3.2 в применении к данной матрице А.

Вопрос З.Т (средней трудности; Т Ва»). Пусть А = В+нот, где  — верхняя треугольная матрица, а и и и суть векторы-столбцы. Указать эффективный алгоритм для вычисления ЯГс-разложения матрицы А. Указание: используя вращения, можно построить алгоритм со сложностью 0(пг) операций, в то время как алгоритм 3.2 требует 0(пг) операций. Вопрос 3.8 (среднсй трудности Я.

Ва~). Пусть х е ~", а Р— такое отражение, что Рх = ~~(х(~)гем Пусть Сцг,...,С„ц„— вращения Гивенса, а сг = С»г... С„» „. Предположим, что Яз = ~ыгем Должны ли совпадать матрицы Р и Я? (Вы должны либо доказать равенство, либо привести контр- пример.) Вопрос 3 9 (легкий; Е Ва»). Пусть А — матрица размера тхп, имеющая ЯЧВ А = СЕ«'т. Выразить через С, Е и Ъ' сингулярные разложения следующих матриц: (АтА -» (АтА) — 'Ат 3 А(АтА) 4.

А(АгА) 'Ат Вопрос 3.10 (средней трудности; А. Ясате»оег). Пусть Аг — наилуч|пее приближение ранга й матрицы А, определенное в утверждении 9 теоремы 3.3. Пусть о; обозначает»зе сингулярное число матрицы А. Показать, что матрица Аь определена единственным образом, если аь > оь+м Вопрос 3.11 (легкий; 2. Ва»). Пусть А — матрица размера т х и. Показать, что выбор Х = А+ (псевдообратная Мура-Пенроуза) минимизирует функцию ~)АХ вЂ” Х(~р на множестве всех п х т-матриц Х. Каково значение этого минимума? Вопрос 3.12 (средней трудности Е Ва»).

Пусть А, В и С вЂ” матрицы таких размеров, что произведение АгСВт определено корректно. Пусть г — множество матриц Х, минимизирующих величину ~ПАХ — С~(к, и пусть Хо— единственный элемент этого множества, минимизирующий ))Х~(р. Показать, что Хо —— А «СВ+.

Указание: использовать сингулярные разложения матриц А и В. 147 3.8. Вопросы к главе 3 Вопрос 3.13 (средней трудности; Е Ва1). Показать, что матрица А+ — псевдаобратная Мура — Пенроуза для матрицы А — удовлетворяет следующим соотношениям: АА+А = А, А+АА+ = А+, А+А (А-~А)т АА+ = (АА+)т Вопрос 3.14 (средней трудности). Доказать утверждение 4 теоремы 3.3. (О Ат Пусть Н = ~ А О, где А — квадратная матрица, имеющая ЯЧП А = (7Е'г'~. Положим Х = 61ак(пд,...,и„), 17 = [им...,и„) и Ъ' = (им...,и„]. Доказать, что 2п собственных значений матрицы Н вЂ” это числа ~а;, а соответствующие нормированные собственные векторы имеют вид ~Ь [ "' ~. Распространить эти результаты на случай прямоугольной матрицы А. Вопрос 3.15 (средней трудности).

Пусть А — матрица полного ранга и размеРа т х и, где т < п. Задача ппп8Ах — Ь|)т называетсЯ недоопРеделенной задачей наименьших квадратов. Показать, что ее решения образуют линейное многообразие размерности п — т. Указать способы вычисления единственного решения с минимальной нормой посредством подходящих модификаций методов нормальных уравнений, ь)К-разложения и ЯЧП.

Вопрос 3.16 (средней гаруднвсти). Доказать лемму 3.1. Вопрос 3.17 (трудный). В разделе 2.6.3 было показано, как реорганизовать гауссово исключение так, чтобы на каждом его шаге выполнялись ВЬАЯ- операции уровней 2 и 3 с их более высокой скоростью. В этой задаче мы покажем, как умножить матрицу на последовательность отражений, используя ВЬАЯ-операции уровней 2 и 3. 1. Пусть иы..., иь — последовательность п-мерных векторов, таких, что '8и;'8т = 1 и первые 1 — 1 компонент в и; равны нулю. Пусть Р Рь Рь 1...

Ры где Р; = 1 — 2и;ит есть отражение. Положим 17 = (и„..., иь). Показать, что найдется нижнетреугольная Ь х Ь-матрица Т, такая, что Р = 1 — БТ(7~. Предложить алгоритм вычисления элементов матрицы Т. Таким образом, умножение на Ь отражений Ры..., Рь можно заменить тремя умножениями на матрицы Нт, Т и ЬГ (с предварительным вычислением Т). 2. Пусть Новее(х) — процедура, которая по заданному вектору х вычисляет ноРмиРованный вектоР и, такой, что (1 — 2иит )х = ох8зем В Разделе 3.4 было показано, как реализовать такую процедуру. Алгоритм 3.2, вычисляющий 14В;разложение т х и-матрицы А, может быть записан следующим образом: Еог г' = 1: т и; = Нопзе(А(1: т,г)) Р, = 1 — 2и;ит 148 Глава 3.

Линейные задачи наименьших квадратов А(»: т, »: и) = Р,А(»': т,1: п) еп«1Еог Указать спссоб эффективной реализации этого алгоритма посредством ВЬАЯ-операций уровня 2 (в частности, матрично-векторных умножений и модификаций ранга 1). Каково число флопов для этой реализации? (Можно ограничиться указанием членов с наивысшими степенями и и т.) Достаточно написать короткую программу в тех же обозначениях, что и выше (хотя хорошим способом самопроверки является составление программы в Ма11аЬ'е и ее сравнение с функцией ЯВ;разложения самого Ма«1аЬ'а!). 3. Используя результаты пункта 1, указать способы реализации цйкразложения посредством ВЬАЯ-операций уровня 3. Каково будет число операций? Этот прием используется для того, чтобы ускорить ЯВ;разложение подобно тому, как в равд.

2.6 было ускорено гауссово исключение. Он применен в 1.АРАСК-программе вйе«1г1. Вопрос 3.18 (средней трудности). Нередко приходится решать задачи наименьших квадратов с ограничениями, где вектор х помимо минимизации функции ()Ах — Ь((з должен еще удовлетворять линейному или нелинейному ограничению. Рассмотрим одну из таких задач. Пусть нужно найти вектор х, минимизирующий ~~Ах — Ь|~з при наличии линейного ограничения Сх = д. Предположим, что А — матрица размера т х п, а С вЂ” матрица размера р х и, причем С имеет полный ранг. Предположим также, что р < и (тогда система Сх = д заведомо совместна) и п < т + р (так что задача в целом не является недоопределенной).