Численное решение задач метода наименьших квадратов - Лоуcон Ч.
Скачать (прямая ссылка):
(17.1) (17.2) (17.3) (П.4) (17.5)
W
вмести pj.zri мдфица
В-Я[С + й(йтС)Ь-1] (17.6)
будет вычислена в арифметике с со-точностью, а затем ее элементы будут переведены в форму с rj-точностью. Поэтому оценки погрешностей (15.29) и (15.30) заменятся соответственно на
ll?lF< lClFtj + 0(т>2) (17.7)
и (с учетом (17.5)) на
\\B-BlF< 29 IICH^tj +6>(172). (17.8)
Теперь оценка (15.40) для погрешности, соответствующей умножению на к преобразований Хаусхолдера, превращается в
ИНк1р< 29к \\АЪРп + 0(щ2). (17.9)
Наконец, при решении треугольной системы (15.44) тоже можно было бы использовать арифметику с со-точностью. В этом случае вместо оценки (15.46) мы имели бы
lSlF< II/?Hftj+0(tj2). (17.10)
Оценка (15.46) уже и так' мала по сравнению с оценками погрешностей для других этапов полного решения задачи НК. Следовательно, при использовании со-точности в решении (15.44) уменьшение оценки для обшей погрешности процесса будет очень незначительно. По этой причине мы предполагаем, что система (15.44) решается в 17-точности, а не в со-точ-ности.
Для версий наших алгоритмов, использующих смешанную арифметику, теоремы 16.1, 16.11, 16.18 и 16.36 заменятся соответственно теоремами 17.11, 17.15, 17.19 и 17.23. Доказательства опушены, поскольку они мало чем отличаются от соответствующих доказательств гл. 16.
Теорема 17.11 (переопределенная задача наименьших квадратов полного ранга). Пусть А — m X п-матрица псевдоранга п,а b — некоторый m-вектор. Пусть используется арифметика со смешанной точностью, характеризуемая параметрами 17 и со< г/2, и пусть х - решение задачи Ах s b, вычисленное посредством алгоритмов HFT (см. 11.4) и HS1 (см. 11.10) или HFTI (см. 14.9). Тогда х является точным решением задачи
(А + Е) х = b + f, - •¦ ¦¦ (17.12)
где ' ':' ' .
\Е\Р< ЗОи \АHF17+O(172), .. , (17.13)
1/1< 29и H&I17+0O72). ^ (17.14)
Теорема 17.15 (квадратная невырожденная задача). Пусть А -п X п-матрица псевдоранга п, a b - некоторый п-вектор. Пусть используется арифметика со смешанной точностью, характеризуемая параметрами г] и со< 172, и пусть х - решение задачи Ах = Ь, вычисленное посредством алгоритмов HFT (см. 11.4) и HS1 (см. 11.10) или HFTI (см. 14.9). Тогда х является точным решением задачи ^
(А +?) x = b+f, * ¦ ¦ • < ^ „-417.16)
77
B?BF< ЗОи lUl^rj + OCt}2), (17.17)
1/1< 29и HftBi7+0(r?2). (17.18)
Теорема 17.19 (нормальное решение недоопределенной задачи полного ранга). Пусть А - m X п-матрица псевдоранга m,a Ь - некоторый m-вектор. Пусть используется арифметика со смешанной точностью, характеризуемая параметрами щи cj< 172, и пусть х - решение задачи Ах = Ь, вычисленное посредством алгоритмов НВТ (см. 13.8) и HS2 (см. 13.9). Тогда х близко к точному решению возмущенной задачи в следующем смысле: существуют матрица Е и вектор х такие, что х является нормальным решением задачи
(А+Е)х = Ь, (17.20)
причем
B?llF< 30m ВЛВ^тг + ОО?2), (17.21)
I3t-JtH< 29m Иjc I17 + 0(г)2). (17.22)
Теорема 17.23 (задача НК неполного ранга). Пусть А - m X п-матрица, Ь - m-вектор. Пусть используется арифметика со смешанной точностью, характеризуемая параметрами т? и cj< 172, и пусть х - решение задачи Ах^Ь, вычисленное посредством алгоритма HFTI (см. 14.9). Пусть к - значение псевдоранга, определенное алгоритмом, a R22 - вычисленная матрица, соответствующая матрице R22 из (14.1). Тогда х близко к точному решению возмущенной задачи в следующем смысле: существуют матрица Е и векторы /их такие, что х является нормальным псевдорешением задачи
(A+E)x*b+f, (17.24) причем
\lEiF< VlR22<llF + 59k VlAiF + 0(т?2), (17.25)
B/IK 29*Ш17 +0(172), (17.26)
|jt-хВ< 29fc »х»г? + 0(т?2). (17.27)
Другого типа анализ погрешностей округлений для того же алгоритма — последовательности преобразований Хаусхолдера в применении к задаче AmX пх- b,m>n, rank Л =п - был выполнен в работах [146, 147]. Этот анализ был мотивирован рассмотрением задач наименьших квадратов с сильно различающимися весами. Такие задачи являются средством решения задачи НК с ограничениями-равенствами и в этом качестве исследуются в гл. 22.
В гл. 22 мы рассмотрим задачу наименьших квадратов с таким свойством: все элементы некоторых строк исходной матрицы [А : Ь) очень малы по величине сравнительно с элементами других строк; тем не менее относительная точность этих малых элементов существенна для задачи. Последнее означает, что возмущения этих элементов, значительные по отношению к их величинам, приводят к большим изменениям решения.
78
Ясно, что теорема 17.11 не гарантирует, что алгоритм Хаусхолдера даст удовлетворительное решение такой задачи; ведь неравенства (17.13) и (17.14) допускают возмущения всех элементов^ которые, хотя и "малы" сравнительно с наибольшими элементами в А и Ь соответственно, могут быть велики по отношению к малым элементам.
И действительно, Пауэлл и Рид обнаружили экспериментально, что результаты, получаемые алгоритмом Хаусхолдера (таким например, как алгоритм HFTI (см. 14.9)) для задач с сильно различающимися весами, критически зависят от упорядочения строк матрицы [А : Ь]. Они заметили, что если в качестве ведущей берется строка из малых элементов, а некоторые последующие строки имеют большие элементы в ведущем столбце, то в (10.7) величина vp будет мала сравнительно с s. В предельном случае, когда |vpl/|s| < г/, величина vp вовсе не дает вклада в ир. Кроме того, в подобных случаях р-я компонента вектора с/ в (10.21) может оказаться очень малой относительно р-й компоненты вектора f/u и не даст вклада в вектор Таким образом, если элементы ведущей строки очень малы в сравнении с элементами некоторых последующих строк, то эффект, по существу, будет тот же, как если бы мы заменили коэффициенты ведущей строки нулями. Если решение чувствительно к подобной потере информации, то описанной ситуации следует по возможности избегать.
