Численное решение задач метода наименьших квадратов - Лоуcон Ч.
Скачать (прямая ссылка):
Главные элементы преобразований Хшщ холдера Qf
Главные элементы преобразований \ж§ холдера Kt
Информация о перестановках
Ри с. 14.1
На рис. 14.1 показано распределение памяти на выходе для т = 6, п~,
5 и к = rank Л = 3. Если требуется сохранить полную информацию об исходной матрице А, то нужно использовать дополнительный массив для; записи диагональных элементов матрицы Rtl из формулы (14.1). Они понадобятся для вычисления матрицы Q той же формулы. Так как в ал-! горитме HFTI матрица Q применяется непосредственно к вектору Ь, то здесь этого дополнительного массива не нужно.
По окончании работы алгоритма вектор решения х находится в одноименном массиве, а вектор с — в массиве с именем Ь. Алгоритм организован таким образом, что имена b их могут отвечать одному и тому же массиву памяти, т.е. нет необходимости в дополнительном массиве для хранения х. В этом случае длина массива Ъ должна быть равна max (/и, л).
Шаги 1-13 алгоритма HFTI описывают приведение к верхнему треугольному виду с использованием перестановок столбцов. В сущности, это — алгоритм, предложенный в [72]. Дополнительные шаги соответствуют обобщению алгоритма на случай неполного ранга [90].
В формулировке шагов 3—10 мы следовали деталям программы, содержащейся в [25] ._Проверка на шаге 6, по существу, эквивалентна условию: "Если Л\ > 10317л ". Форма этого условия, которую мы используем, позволяет избежать явного указания машинно зависимого параметра 77. Его смысл — относительная точность машинной арифметики.
Алгоритм 14.9. HFTI (А, т, п, Ь, т, х, к, л, g, р) :
1. Положить Ц: = min (/и, и).
2. Для /: = 1,... , /и выполнить шаги 3—12.
3. Если/ = 1, перейти к шагу 7.
4. Для /:=/,..., л положить ht: = ht — af_ t,/.
a
5. Определить X такое, чтоЛ\: = тах{ «,:/</<«}.
6. Если (Л + I0~3hx)> h, перейти к шагу 9.
т
7. Для /•=/...., и положить я,: = ? д?,.
¦•=/
8. Определить X такое, что й^: = max {я,: / </ <и}. Положить й: =h\.
9. Положить р,-: = X. Если ру =/', перейти к шагу 11.
10. Переставить столбцы / и X матрицы А и положить Я\: = йу.
11. Выполнить алгоритм Н1(/,/ + 1, m,aif,hj,aij+i,n - /)•
12. Выполнить алгоритм Н2(/,/+ 1, т, <*i/,fy> ft, 1).
13. Комментарий. Теперь следует определить псевдоранг Л. Заметим,
что диагональные элементы R (хранимые в позициях alt.....дмм) не
возрастают по абсолютной величине. HFTI выбирает в качестве к наибольший индекс / такой, что I Дуу | >т. Если I а,-,- | <т для всех/, то псевдорангу к присваивается значение 0, вектор решения х полагается равным нулю н алгоритм заканчивается.
14. Если к = п, перейти к шагу 17.
15. Комментарий. Здесь к< и. Сейчас будут определены ортогональные преобразования К{, чье произведение составляет матрицу К формулы
16.Для /:=*, Аг-1,...,1 выполнить алгоритм Н1 (i,Л + 1,1,0/1,?/, а1Ь/ — 1). (Параметры а{1 и ац указывают первые элементы соответствующих строчных векторов.)
17. Положить xk: = bkjakk. Если к< 1, перейти к шагу 19.
18. Для /: = к - 1, к - 2,..., 1 положить х(: = —(ft/ - 2 в/,-ху )(см.
19. Если к = и, перейти к шагу 22.
20. Задать и - Л-вектор у2 (см. (14.5)) и поместить его компоненты в позиции Xf, i: = А: + 1,..., п. В частности, если требуется решение минимальной длины, нужно положить у г '¦= 0.
21.Для i: = l,...,Jfc выполнить алгоритм Н2(/,к + 1,и,дп,gi,x, 1) (см. (14.6). Параметр а{1 указывает первый элемент строчного вектора).
22. Для /: = u, U - 1, ¦ • •, 1 выполнить шаг 23.
23. Еслиру Ф/, переставить содержимое ячеек ху ихр. (см. (14.6)).
ГЛАВА 15
АНАЛИЗ ПОГРЕШНОСТЕЙ ОКРУГЛЕНИЙ ДЛЯ ПРЕОБРАЗОВАНИЙ ХАУСХОЛДЕРА
В предыдущих главах мы рассматривали преимущественно математические аспекты различных задач метода наименьших квадратов. В гл. 9 было исследовано воздействие на решение неопределенности во входных Данных задачи. Практические машинные вычисления связаны с погрешностями округлений. Замечательный вывод теории погрешностей °кРУглений [7] состоит в том, что для многих классов задач линейной
(14.3).
(14.4)).
63
алгебры вычисленное машиной решение является точным для задачи, полу, чаемой из исходной сравнительно малым возмущением коэффициентов.
Большое значение имеет тот факт, что возмущения коэффициентов, эквивалентные произведенным округлениям, часто бывают меньше, чем неопределенность задания этих коэффициентов; в таких случаях погрещ.. ности округлений с практической точки зрения можно игнорировать^
Цель гл. 15—17 представить результаты этого типа для алгоритмом наименьших квадратов, описанных в гл. 11-14. 1
Действительные числа, точно представимые на данной машине в видя нормализованных чисел с плавающей запятой, будем называть машинными числами. |
Емкость арифметики с плавающей запятой данной машины удобно ха*| рактеризовать тремя положительными числами L, U, г). Число L — это наименьшее положительное число такое, что и L, и -L являются машинными числами. Число U — зто наибольшее положительное число с тем свойством, что и U, и -Uявляются машинными числами.
В последующем анализе предполагается, что все ненулевые числа х, участвующие в вычислениях, удовлетворяют условиям L <| х \ <U. Надежная универсальная программа, реализующая описываемые алгоритмы, может обеспечить неравенство | х | < U путем соответствующего масштабирования. При этом может оказаться невозможным одновременно гарантировать условие | х | > L для всех ненулевых чисел х. В то же время подходящим масштабированием можно добиться того, чтобы числа, для которых I х | < L, можно было заменить нулями, не влияя сколько-нибудь существенно на точность результатов в смысле векторных норм.
