Численное решение задач метода наименьших квадратов - Лоуcон Ч.
Скачать (прямая ссылка):
Замечание. Это доказательство примо вытекает из теоремы 5.10. Доказательство, предложенное Экартом и Янгом, по существу, содержите себе и доказательство теоремы 5.10.
5.16. Решить задачу 5.15, заменив II • IIF на II ¦ II.
5.17. Определим к(А) как отношение наибольшего сингулярного числа матрицы^ к ее наименьшему ненулевому сингулярному числу. (Это "число обусловленности" А будет использоваться в последующих главах.) Показать, что если ранг m X л-матрицы А равен л, a m X г-матрица В получена из А удалением п - г столбцов, то к(в) < к(А).
t ¦ 1 ¦ ¦ • .
ГЛАВА 6
ОЦЕНКИ ДЛЯ ЧИСЛА
ОБУСЛОВЛЕННОСТИ ТРЕУГОЛЬНОЙ МАТРИЦЫ
При практическом анализе задачи наименьших квадратов в гл.25 возникнет необходимость в оценке наибольшего и наименьшего ненулевого сингулярных чисел матрицы А: отношение этих двух величин (число обусловленности А) интерпретируется как коэффициент увеличения ошибки. Эта интерпретация числа обусловленности будет представлена в гл. 9.
Наиболее прямой подход состоит в том, чтобы вычислить сингулярные числа А (см. гл. 4, 18). Однако часто бывает желательно получить оценку для числа обусловленности, не вычисляя сингулярных чисел. В данной главе будут изложены некоторые теоремы и примеры, связанные с этой задачей.
Большинство алгоритмов, описываемых в этой книге, порождают в качестве промежуточного результата невырожденную треугольную матрицу (назовем ее R), имеющую те же ненулевые сингулярные числа, что и исходная матрица А. В общем случае невырожденная треугольная матрица является лучшим отправным пунктом при оценке обусловленности, чем заполненная матрица. Поэтому мы ограничимся оценками сингулярных чисел только для невырожденной треугольной матрицы R.
Обозначим упорядоченные сингулярные числа невырожденной треугольной л X л-матрицы R через s { > ... > sn > 0. Как отмечено в упражнении 4.22, Jj = IIR II. Отсюда получаем легко вычислимую нижнюю оценку
24
для Si:
st >max \ rtl\.
(6.1)
Далее, так как R треугольная, то числа, обратные к дааготяышм элементам R, суть элементы Л"1. Поэтому
|| Л'1 || >шах | г,? |. (6.2)
Согласно упражнению 4.23, s"1 = ||/?~' II, откуда
s„ < min I rit I
(6.3)
Итак, нижнюю границу р для числа обусловленности к " *фл дает неравенство
к>р =
max | Гц |
Л/
min |г«| t
(6.4)
Эта нижняя граница, хотя н не лишена практической пользы, не может, вообще говоря, рассматриваться как надежная оценка для к. В самом деле, к может быть значительно больше, чем р.
Это показывает пример (см. [108]) верхней треугольной л X и -матрицы R, определяемой формулами
| 0,/</,
П/ = \ l,i = i, . (6.5)
l-l,/>i
Например, для и = 4 - ¦ тн
R =
-1 -1 -1
0 1 - 1 - 1
0 0 1 -1
0 0 0 1
(6.6)
Используя (6.4), получим р = 1 в качестве нижней границы для к. Эта оценка не содержит никакой информации. Для данной матрицы более реалистическую верхнюю границу для s„ можно вывести, рассматривая действие R на вектор у с компонентами
у, = г*-\ 1 = 1,... .ii-i, у„=у„^ (6.7)
Легко проверить, что Ry = z, где
Z/ = 0, / = 1.....л-1, z„ = 22~".
Теперь, используя неравенства ^ ll^ll 1
(6.8)
= 11Я" II > находим
,2-л »
(6.9)
Село)
25
iаолкцаол
Последний диагональный элемент Я и последнее сиигуяярное число R
п
20 21 22 23 24 25 26
330 165 82,5 40,5 20,5 8,96 4,59
i„ X 10*
286 143 71,6 35,8 17,9 8,95 4,52
*nlr„„
0,867 0,867 0,868 0,884 0,873 0,999 0,985
Неравенство (6.9) можно интерпретировать и так: оно показывает, что R близка к вырожденной матрице. Близость понимается в том смысле,.что существует матрица Е такая, что ||2Г|| <22~" и матрица R-E вырождена. Легко проверить, что нужная матрица задается формулой Е = zyT/yTy.
Для и = 4 у = (1, 1/2, 1/4, 1/4) г, z = (0, 0, 0, 1/4) г, и < 1/4, к > 4. Кроме того, при вычитании матрицы
"о 0 0 0 "
0 0 0 0
0 0 0 0
_2_ 1 1 1
_11 11 22 22
из матрицы R (см. (6.6)) получим вырожденную матрицу.
Этот пример показывает, что иногда опасно считать матрицу хорошо обусловленной даже в том случае, когда р в (6.4) мало, а матрица выглядит вполне "невинно".
Напомним, что нас интересуют главным образом треугольные матрицы, возникающие в алгоритмах решения линейных систем. Матрица, определяемая формулами (6.5), обсуждалась в литературе в связи с тем, что она инвариантна относительно гауссова исключения как с частичным, так и с полным выбором главного элемента. Однако она не будет инвариантна относительно исключения посредством преобразований Хаусхолдера, сопровождаемого перестановками столбцов (так обстоит дело, например, в алгоритме HFTI, который будет описан в гл. 14).
В этой связи и в качестве численного эксперимента мы применим алгоритм HFTI к матрице R из (6.5). Пусть R обозначает треугольную матрицу, полученную в результате этой операции. Мы вычислили также сингулярные числа R. Вычисления проводились на машине UNIVAC 1108 в режиме смешанной точности (см. гл. 17), характеризуемом использованием как арифметики с обычной точностью (т? = 2~г 1 ~ 0,745 X 10~8), так и арифметики с удвоенной точностью (w = 2-58 * 0,347 X 10"'7). В табл. 6.1 представлены вычисленные значения последнего диагонального элемента г„„ и наименьшего сингулярного числа s„, а также отношения sn/rnn для значе-
