Численное решение задач метода наименьших квадратов - Лоуcон Ч.
Скачать (прямая ссылка):
Заметим, что значение скалярного произведения ajqt не изменится, если О/ заменить вектором вида
/ - 1
а, - ? akqk, (19.24)
* = i
так как qfq, = 0 для к Ф I. Исходя из этого, росомвндупся заменить
(19.22) на
«},)Г«|
г„=--, №25)
т Я\Я,
где
e(/) = а, - 'ilrk,qk. (19.26)
Если поставить задачу - минимизировать за счет выбора чисел ак норму вектора (19.24), то. как легко проверить, вектор с минимальной длиной задается формулой (19.26). Таким образом, вектор Д/ в (19.22) и вектор в (19.25) связаны неравенством \\а^ || <||д;- ||. Большая численная устойчивость модифицированного алгоритма проистекает как раз из этого факта.
Количество вычислений и необходимая память не увеличиваются модификацией, так как вместо непосредственного использования формулы
(19.26) векторы можно вычислять рекурсивно. Кроме того,
вектор + можно записывать на место, которое прежде занимал
вектор aj .
Этот алгоритм, за которым закрепилось название модифицированный метод Грама-Шмидта [157], описывается следующими уравнениями:
в}0 "в/. /=1.....<19-27)
Я,=а(/\ (19.28)
d) =Я?Яг (19-29)
П, = —Г" , (19-30)
dt
Д<'+,)=Д/(,)-rtlqr / = / + 1.....и, / = 1,(19.31)
Чтобы использовать MGS *) для решения задачи НК, можно составить расширенную матрицу
А = [А :Ь). (19.32)
После этого MGS применяется к жХ (л+ 1)-матрице А; в результате будет получено разложение
А = QR, (19.33)
где R — верхняя треугольная матрица с единичными диагональными элементами. Наддиагональные элементы R выражаются формулами (19.30). Векторы qt из (19.28). являются столбцами m X (л + 1)-матрицы Q
*) См. примечание на стр. 92. (Примеч. пер.) 100
Можно еще составить диагональную матрицу D порядка л + 1 с диагональными элементами dt, i = 1.....n+1, задаваемыми формулами (19.29).
Для последующего обсуждения, которое приведет к решению задачи НК, возьмем какую-либо ортогональную т X m-матрицу Q, удовлетворяющую соотношению
D |}л + 1 О J}m-n- 1
2т Xm J 0 ||^, „ , " QmX(n+l)-л + I
Тогда
А = Q \ п \R = Q \ 0 </„+ , I . (19.34)
Б\ \DR Л
В последнем переходе были использованы клеточные представления матриц D и R
"'[о ,J|,-
D О
D =
О d„ri
} л }1
л 1 л 1
Теперь для произвольного вектора х имеем IIАх— b ||2 = \\ QT(Ax- b) II2 = = \\D(Rx- с) ||2 + d2+I. Следовательно, минимальным значением величины || А х — Ь\\ будет \d„+l |, и это значение достигается на векторе х, разрешающем треугольную систему Rх = с.
При фиксированной точности арифметики MGS обладает примерно той же численной устойчивостью, что и алгоритм Хаусхолдера. Анализ ошибок, проведенный в работе [23], дает следующий результат: решение задачи Ах as Ь, вычисленное посредством MGS в арифметике со смешанной точностью (г/, г}2), является точным решением возмущенной задачи (А Ъ +/, где . ¦> , t •<¦>*.
\\E\\F < 2п3'2 \\А \\pTi, ч-.'.- - -г ,м (19.35)
||/||< 2л3/2 || ft || г?. (19.36)
Проведенное тестирование машинных программ (см, [185]) показало, что программы методов Хаусхолдера и MGS дают, по существу, одинаковую точность.
Число арифметических операций в MGS несколько больше, чем в методе Хаусхолдера (см. табл. 19.1), по той причине, что в MGS все операции производятся над векторами длины т, в то время как в методе Хаусхолдера столбцы последовательно укорачиваются. По той же причине программы MGS требуют обычно больше памяти, чем программы Хаусхолдера: в MGS нет удобного способа получать матрицу R на том месте, где хранилась исходная матрица А. Если, однако, не сохранять векторы q., то возможна такая организация MGS, что R замещает А в памяти; зто достигает-
101
ся за счет некоторой дополнительной работы по перемещению хранимой информации.
Метод MGS можно приспособить и к тому, чтобы последовательно накапливать строки или группы строк матрицы [А : b ]; зто бывает нужно в случае, когда произведение тп очень велико и т > п. Возможность такой
организации основывается на том, что (и + 1) X (и + 1)-матрица DR (см. (19.34)) определяет ту же задачу наименьших квадратов, что и т X (и+ 1)-матрица [А : b }. Исходя из этого, можно построить последовательный алгоритм MGS точно таким же образом, каким соответствующее свойство триангуляризации Хаусхолдера используется в гл. 27 для построения последовательного метода Хаусхолдера.
Специальными адаптация ми процесса Грама—Шмидта являются: 1) метод сопряженных градиентов, предназначенный для решения положительно определенных систем линейных уравнений (см. [94, ПО, 151, с. 62-67) и имеющий некоторые качества, привлекательные в случае больших разреженных систем [154—156]; 2) метод Форсайта [55] для полиномиального сглаживания с использованием ортогонализованных многочленов.
Упражнения
19.37. Пусть R - верхняя треугольная л X л-матрица, у которой некоторые диагональные элементы Гц равны нулю. Показать, что существует верхняя треуголь-
Т т
ная л X л-матрица Uтакая, что U U=R R и иц =0, / =/.....л, если гц =0,
Указание. Построить U в виде U = QR, где Q - произведение конечного числа специальным образом подобранных вращений Гивенса.
