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

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

Лоуcон Ч., Хенсон P. Численное решение задач метода наименьших квадратов: учебное пособие. Под редакцией Тыртышникова Е.Е. — М.: Наука, 1986. — 232 c.
Скачать (прямая ссылка): louson_h_chisl_resh_zmnk.djvu
Предыдущая << 1 .. 4 5 6 7 8 9 < 10 > 11 12 13 14 15 16 .. 88 >> Следующая

26
ний и от 20 до 26. Заметим, что во всех случаях гпп дает хорошую оценку величины s„.
Тем не менее существуют и X л-матрицы с нормированными столбцами, которые могут быть порождены алгоритмом HFTI и у которых наименьшее сингулярное число приблизительно в 2"-1 раз меньше, чем наименьший диагональный элемент.
Пример такой матрицы, который мы сейчас приведем, принадлежит Кахану [108]. Определим nXn-матрицу R формулами
0, «>/,
»•=/.
-cs-', /</.
Здесь s и с - положительные числа, причем sa + с2 ¦ 1. Например, для и = 4
R =
1 - с - с - с
0 s - CS - CS
0 0 S2 - CS
0 ' 0 0 S3
(6.11)
Для любого п матрица/! верхняя треугольная, ее столбцы имеют единичную евклидову длину, и выполняются неравенства
кк
> Z г
i=k
* = 1,
1.
, п.
(6.12)
Как устанавливается в гл. 14, зти неравенства означают, что матрица/? может быть получена в результате применения алгоритма HFTI к некоторой матрице А.
Пусть T = R~1. Элементы Т выражаются формулами О,
1
С(1 тс)'"'-1
Например, в случае и = 4 с
1 —
Л"1 »Г =
/ =
;-|+ 1,
/ - I > 2.
с(1 +с)
О О L0
с(1 +с)2
с(1 +с)
S
О
Пусть т„ обозначает последний столбец R . Тогда
Когда s -*•+ 0, а с = (1 - s2)1'2 ->1 - 0, произведение II г„ Н2г„„, возрастая, стремится к (4"~1 + 2)/3. Поэтому найдется значение s, зависящее от и, для которого
Так как, согласно упражнению 4.24, IIR т„ || 1 II т„ II II т„ II '
то
*п<3,/22»-''|г,1Л|*1.73-2,-п|гп,,|.
Следующая теорема показывает, что в рассмотренном примере реализуется почти минимальное значение, которого может достигать отношение
«и/кип I-
Теорема 6.13 [9]. Пусть А - m X п-матрица ранга п. Предположим, что все столбцы А имеют единичную евклидову длину. Пусть R - верхняя треугольная матрица, полученная процессом хаусхолдеровой триангуляри-зации А с перестановками столбцов {так обстоит дело, например, в алгоритме HFTI из (14.9)). Тогда s„ - наименьшее сингулярное число А и rm -последний диагональный элемент R связаны неравенствами >
*„<|г,,„1, (6-14)
s„>3(4" +Ьп-1ГЧ2\г„„\>21-п\г„„\. (6.15)
Доказательство. Из способа, которым строится R, видно, что ее столбцы имеют единичную евклидову длину, а сингулярные числа те же, что и у А. Кроме того, перестановки столбцов обеспечивают выполнение неравенств
/
r\k> Z г2., Л = 1,----л - 1, / = * + 1.....п. , (6.16)
Из (6.16) следует, что
\rkk\>\rl)\, i>k, />*. k'l.....я-1. (6.17)
Так как
*я = II Л" ЧГ1, (6.18) то неравенства (6.14) и (6.15) эквивалентны неравенствам
• ИЛ"1 II > |г-„|, . (6.19)
\\R-1 ||<3-1(4п+6и-1)1/2|г;„|. (6.20)
Неравенство (6.19) - следствие того факт*, что г^,1 является элементом матрицы/!'1.
28
Чтобы доказать (6.20), мы выведем верхние границы для величин всех элементов^/?-', а затем вычислим норму Фробениуса мажорирующей матрицы М.
Положим Т = Л"1 .Будет удобно сгруппировать элементы Т по диагоналям, параллельным главной. Введем мажорирующие параметры для диагоналей следующим образом:
4t = max{| / = 1,...,и - *}, *=0,1.....п-1.
(6.21)
Тогда
go = max I tu I =max I r~J I = | r'l„ \.
(6.22)
Элементы к-й наддиагонали T можно выразить через элементы главной диагонали Т, элементы предшествующих наддиаго налей Т и элементы R:
U, i + k--
2 ri,i*lti + l, t + k 1 = 1
(&3)
1 <1<л - 1, Kk<n-i. Так как |/7/+/| < \ гц\, то из (6.21) и (6.23) получаем
* к к-1
gk - max \t{ l+k\< max 2 |Г/+|,/+*1< I gk_,= I gj. (6.24) / / /=i ;=i /=o
Легко проверить по индукции, что
в»<2*-|Лв2*-||г^|, * = 1.....п. (6.25)
Определим верхнюю треугольную л X л-матрицу М формулами
| 0, /</,
I 2'-'-1. />/, я и положим
Й = |г„-„|М 037)
Например, для и = 4
1 1 2 4" 0 112 0 0 11 .0 0 0 1_
Иэ (6.21) и (6.25)-(6.27) следует, что элементы Л'1 (- 7) мажорируются соответствующими элементами М. Поэтому
*п1 = IIЛ'1 || < \\R-1 \\F< \\M\\F = \r-„l„\\\M\\F. (6.28)
Чтобы вычислить норму Фробениуса матрицы Af„ заметим, что для / > 2
Af =
29
сумма квадратов элементов столбца / равна
/-2 А'-х + 2
и>? = 1 + Z 4' =---. (6.29)
' i = o 3
Это выражение верно и при / = 1, если считать, что сумма в средней части равна нулю. Теперь
\\R-4\F = \\T\\F<r-n*\\M\\F=r-„l Дн-/-г^ 4 +6?~1 . (6.30)
Неравенства (6.28) и (6.30) вместе устанавливают неравенство (6.20). Теорема 6.13 доказана.
Теорема 6.31 [9]. Пусть А и Яте же, что и в теореме 6.13. Сингулярные числа $i > ... > s„ матрицы А связаны с диагональными элементами Гц матрицы R неравенствами
2'-'|г„1 <3(4'т6/-1)-,/2|г„|<5,<(п-/ + 1),/21г|7|. /-1.....П.
(6.32)
Доказательство. Пусть R, - ведущая главная подматрица порядка / матрицы R. Обозначим через sf'^ /-е сингулярное число R/. Из теоремы 5.12 вытекают неравенства
*,=*/(л)>*,(л-,)> ...>4° (6.33)
Применяя к Rt теорему 6.13, получим
sf > 3(4'' + 6." - I)"1 '2| г„|. (6.34)
Это неравенство вместе с (6.33) доказывает нижнюю оценку для s{ в (6.32).
Определим Wj как главную подматрицу порядка л + 1 -/, стоящую в R на пересечении строк и столбцов с номерами /,..., л. Заметим, что первым диагональным элементом Wt является ги. Используя (6.16) и упражнение 6.37, получаем
Предыдущая << 1 .. 4 5 6 7 8 9 < 10 > 11 12 13 14 15 16 .. 88 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

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

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed