Научная литература
booksshare.net -> Добавить материал -> Математика -> Лоуcон Ч. -> "Численное решение задач метода наименьших квадратов" -> 22

Численное решение задач метода наименьших квадратов - Лоуcон Ч.

Лоуcон Ч., Хенсон P. Численное решение задач метода наименьших квадратов: учебное пособие. Под редакцией Тыртышникова Е.Е. — М.: Наука, 1986. — 232 c.
Скачать (прямая ссылка): louson_h_chisl_resh_zmnk.djvu
Предыдущая << 1 .. 16 17 18 19 20 21 < 22 > 23 24 25 26 27 28 .. 88 >> Следующая

4. Положить х: =
59
Алгоритм HFTI применим, в частности, к задачам неполного ранга указанным на рис. 1.1 как случаи \b, 2Ь и ЪЬ. Строго говоря, однако, имея] но псевдоранг, а не ранг А будет определен в ходе вычислений.
Исходя из теорем 2.3 и 3.19, сформулируем математические соотношу
ния, лежащие в основе алгоритма HFTI: Г Л,1 Л,г 1)*
QAP = R=\ У , (14.1)
Z~ ^2 *)т~к '
к п- К
[Л,,:Л12] А'= [W :01, (14.31
^Vi=Ci, (14.41
уг - произвольный вектор, (14.5)
*=^[^' j =РКу, (14.6)
lb-Ах 11= ic2 -R22y2l( = Нс2 11прн^2 =0). (14 7)
Алгоритм определит ортогональную матрицу Q и матрицу перестановки Р такие, что R будет верхней треугольной матрицей с невырожденной подматрицей Rlt.
Матрица перестановки Р строится неявно как результат стратегии перестановок столбцов, принятой в алгоритме. Эта стратегия тесно связана с задачей определения псевдоранга к. Существенна невырожденность подматрицы Лм. Если специальные требования конкретных приложений не заставляют выбрать иной критерий, то предпочтительным решением будет достаточно хорошо обусловленная матрица Rn и матрица R22 с достаточно малой нормой.
Пример такой нестандартной ситуации - случай, когда заранее известно,, что А„х„ имеет простое собственное значение нуль. В этом случае можно было бы положить к = п - 1 вместо того, чтобы определять значение А: посредством алгоритма.
Другая нестандартная ситуация — это задача НК с весами (гл. 22), где может допускаться очень плохо обусловленная матрица Л11.
В алгоритме HFTI используется следующая стратегия перестановок столбцов. Перед построением/-го преобразования Хаусхолдера среди столбцов с номерами/,..., п выбирается тот (назовем его X), у которого сумма квадратов компонент в строках с j-й по m-ю наибольшая. Содержимое столбцов / и X затем меняется местами, после чего строится /-е преобразование Хаусхолдера так, чтобы аннулировать элементы в позициях ац, i =/' + 1,... ,m.
Некоторой экономии счетного времени можно добиться, если перест раивать от шага к шагу нужные суммы квадратов *). Это возможно благо-
*) А не вычислять их заново на каждом шаге. (Примеч. пер.)
to
даря ортогональности преобразования Хаусхолдера. Подробности перестройки даны в описании алгоритма HFTI (шаги 3-10).
В результате принятой стратегии перестановок диагональные элементы R не будут возрастать по абсолютной величине. Более того, они будут удовлетворять неравенствам (6.16). См. в этой связи теоремы 6.13 и 6.31.
В алгоритме HFTI псевдоранг к определяется как наибольший индекс у; для которого I г j/ | >т, где т - задаваемый пользователем неотрицательный параметр. Стратегия перестановок столбцов и подходящий выбор т, разумеется, зависят от исходного масштабирования матрицы. Этот предмет обсуждается в гл. 25.
Выбор значения к меньшего, чем min (m, и), равносилен замене заданной матрицы
A=QT\ п „ \РТ [0 R22 J
матрицей
*¦*[""?']''¦ _...... (|48>
Заметим, что %А -А 1= 1-/?22 I, \А —A \F = 1/?22 1^-. Далее при указанных процедурах перестановки столбцов и определения псевдоранга имеем
П/?22 IKOi-Ar)1/2 1гЛ+,,*+1 \<(/i-k)4*T,
ц = min (/и, и).
Ортогональная матрица К в (14.3) выбирается так, чтобы И7 была невырожденной верхней треугольной А: X Аг-матрицей; А:-вектор ji вычисляется как единственное решение (14.4). Для и- Ar-вектора у2 можно задать произвольное значение; при этом нулевому у2 соответствует решение с минимальной длиной. Окончательно решение х выражается формулой (14.6). Норму невязки можно вычисдить как правую часть формулы (14.7).
На входе в алгоритм HFTI задаются матрица А и вектор Ь, хранимые в одноименных массивах, целые числа т, и и неотрицательный параметр т. Ортогональная матрица Q из формулы (14.1). является произведением Ц преобразований Хаусхолдера Qt. Информация, определяющая эти матрицы, занимает на выходе нижнюю треугольную часть массива А плюс ц дополнительных ячеек массива с именем Л.
Массив Л используется также для хранения квадратов длин столбцов некоторых подматриц, генерируемых в процессе вычислений. Эти числа нужны при определении перестановок столбцов. На их место можно записать (и действительно записываются) главные элементы матриц Qt.
Матрица перестановки Р строится как произведение матриц-транспози-ции Р = О.Pi) • • • (Р>Рц)- Здесь (/,/) обозначает матрицу перестановки, получаемую путем транспозиции столбцов i и / единичной матрицы /„. Целые числа Pj записываются в массив р. Ортогональная матрица К из (14.3) есть произведение к преобразований Хаусхолдера К,. Информация, определяющая зти матрицы» занимает прямоугольную часть массива А, образованную первыми к строками и последними п—к столбцами, и еще к дополнительных ячеек в массиве ?.
w11 ш13 *и *«
"« w22 »я *24 *25
"о "я *»и *34
"и "24 "34 + +
"is "2S "33 "45 +
",е "2» "эо "46

"« "22 "33 "44 «вв

*22 У

А As Рз А
Массив, в котором первоначально хранится матрица А. По окончании работы в нем хранятся матрица W и большая часть информации, необходимой для построения ортогональных преобраэа ваний Хаусхолдера
Предыдущая << 1 .. 16 17 18 19 20 21 < 22 > 23 24 25 26 27 28 .. 88 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed