Численное решение задач метода наименьших квадратов - Лоуcон Ч.
Скачать (прямая ссылка):
у = (со2 - || ?(1* II2)1'2, где d и со2 определены равенством (19.8). При замене переменных х = Vp исходная задача НК переходит в задачу
Эта задача наименьших квадратов эквивалентна задаче (18.37), получение! посредством сингулярного разложения: диагональная матрица S ип-векто*
(19.19)
96
gv> в (19.19) те же, что ив (18.37); 7из (19.19) vig^J из (1837) удовлетворяют соотношению у = II II.
Однако при фиксированной разрядности машинного слова величины S, g (1) и у = || g (2) || будут определены путем спектрального анализа матрицы [А : b] т [А : Ь] менее точно, чем если бы применялся сингулярный анализ к самой матрице А = [А : Ь] или треугольной матрице R, полученной из А алгоритмом Хаусхолдера.
Как отмечено во введении к данной главе, при фиксированной относительной точности 17 машинной арифметики преобразования Хаусхолдера позволяют решать более широкий класс задач, чем если бы формировались нормальные уравнения, а затем применялось разложение Холесского. Это утверждение можно проиллюстрировать следующим примером. Рассмотрим 3 X 2-матрицу
.[: :
Ll 1
-е.
Предположим, что значение е существенно для данной задачи, например е > IOO17, но еа < г?, так что при вычислениях с относительной точностью rj будет 1 — еФ 1, но 3 + es вычисляется как 3. Поэтому вместо
L3-e 3-2e + eaJ
будет вычислена (с точностью до случайных 1 щих по абсолютной величине Зт») матрица
3 3-е
3-е 3
Последующее вычисление верхней треугольной матрицы
\Гц Г, 2 1
I 0 ггг \
для которойRTR=ATA, проводится в соответствии с методом Холесского (19.12)-(19.14) по формулам
Гц = у/3, г,2=-—, rU=p77~ri7.
у/Т
При вычислении г22 (опять же с точностью до случайных гюгрешноетей произвольного знака, не превышающих по модулю Зг?) получим
. 9-бе
г\г =3 -2е-—-— = 0.
Соответствующий точный результат был бы, конечно, равен
2 , 9-бе + е2 2е2 ^=3_2е + е2-—----- : щ ,
7-Ч. Лоусои W
Таким образом, при использовании арифметики с относительной точностью т? в вычисленном элементе т22 нет значащих цифр. Следовательно, матрица R неотличима от вырожденной. Причиной не являются недостатки алгоритма Холесского. Скорее здесь нашел отражение тот факт, что столбцы матрицы А ТА так близки к параллельности (линейной зависимости), что отсутствие точной параллельности нельзя установить в арифметике с точностью 17.
Сопоставим зту ситуацию с той, что имеет место при прямой (без предварительного формирования АТА) триангуляризации преобразованиями Хаусхолдера. По формулам (10.5)-(10.11) вычисляем
1 +N/37-]
1 , ь = -уД(1 +уД) = -(з+хД).
и =
i т ш
Теперь, умножая на / + Ь
t = b'l(uTa2) = -
второй столбец аг матрицы А, получаем
е(3-уД)-6
з +V?
а2 = а2 + Ш =
1 1
1 -е
е(3 - ч/з") - 6
1+v31
]
е(З-УЗ) 6
-е(3+ч/з)
Важно отметить, что вторая и третья компоненты а2, имеющие порядок -?, вычислены как разности величин порядка единицы. Поэтому в арифметике с ^-точностью эти компоненты не будут утрачены вследствие округлений.
Последний шаг триангуляризации Хаусхолдера состоит в замене второй компоненты а2 значением (со знаком минус) евклидовой нормы второй и третьей компонент. Этот шаг не вызывает вычислительных затруднений:
6(3-4/3») V f-e(3+V?) -еу/6
Ггг
6 J l 6 J J 3
Объединяя результаты, мы получаем (с точностью до абсолютных погрешностей, не превосходящих по модулю З17) матрицу
¦¦["Г
(е-3)1 у/1 -ечЛГ/З
Окончательный вывод из этого примера таков. Используя арифметику с т)-точностью и применяя преобразования Хаусхолдера непосредственно к А, мы вычислили треугольную матрицу, которая очевидным образом не вырождена. В то же время формирование нормальных уравнений и последующее разложение Холесского привели к вырожденной матрице. 98
§ 2. Модифицированная ортогоиалиэация Г рама—Шмидта
Ортогоналиэация Грама—Шмидта - это классический математический метод решения следующей задачи. Дана линейно независимая система векторов (fli.....а„); нужно построить ортогональную систему {qu .... q„)
с тем свойством, что для А: = 1, и подсистема {qt.....qk) порождает то
же Ar-мерное подпространство, что и {д,, ...,.ак}. Классические формулы, •выражающие qf через а/ и ранее вычисленные векторы qlt <7/-i> таковы:
Ч\ =ai, (19.20)
/ - 1
Я,=а,- * rqqg, / = 2.....и, ; (19.21)
где
rti'-ir1- 09.22)
Чтобы записать зти формулы в матричных обозначениях, определим А как матрицу со столбцами а,-, Q как матрицу со столбцами <fy и R как верхнюю треугольную матрицу с единичными диагональными элементами и наддиагональными элементами, задаваемыми формулами (19.22). Тогда (19.20) и (19.21) можно переписать в виде
А = QR. (19.23)
Отсюда ясно, что ортогонализацию Грама—Шмидта можно рассматривать как еще один метод разложения матрицы в произведение матрицы с ортогональными столбцами и треугольной матрицы.
Эксперименты свидетельствуют [157], что процесс (19.20) —(19.22) обладает значительно меньшей численной устойчивостью, чем некоторый его вариант, математически ему эквивалентный. Устойчивость этого варианта, называемого модифицированным методом Грэма-Шмидта, была установлена Бьорком [23]; ему принадлежат приводимые ниже оценки (19.35) и (19.36).
