Ремонт принтеров, сканнеров, факсов и остальной офисной техники


назад Оглавление вперед




[227]

Раскрыв скобки, мы приходим к уравнению

АТАс = Ату,

(31.33)

называемому в математической статистике нормальным уравнением (normal equation). Матрица АтА будет симметрической (упр. 31.1-3), и, если только А имеет полный столбцовый ранг, положительно определённой (теорема 31.6). В этом случае (лемма 31.13) существует обратная матрица (АТА)~1, и решение системы (31.33) единственно:

е=((АтА)-1Ат)у = А+у,

(31.34)

Здесь через А+ обозначена матрица [АТА)-1АТ, называемая псевдообратной (pseudoinverse) к матрице А. Это понятие является естественным обобщением понятия обратной матрицы на случай неквадратных матрицы. (Сравните формулу (31.34), дающую решение системы Ас = у по методу наименьших квадратов, с формулой х = A~lЬ, дающей точное решение системы Ах = Ъ.) Для примера рассмотрим 5 экспериментальных точек

(-1,2),(1,1),(2,1),(3,0),(5,3)

(чёрные кружки рис. 31.3.) Мы хотим провести рядом с ними график квадратного трёхчлена

F(

ci + с2х + с3а

Выпишем матрицу значений базисных функций:

А

/1

2

3

4

х \

х2 х3

Х4 Х5

и найдём псевдообратную к ней:

А+

0.500 -0.388 0.060

0.300 0.093 -0.036

/1

1 1 1

0.200 0.190 -0.048

1

1\

1

4 9 25/

0.100 -0.100 0.193 -0.088 -0.036 0.060

Искомый вектор коэффициентов (с = А+у) будет равен

1.200 -0.757 0.214


Рис. 31.1 31.3 Метод наименьших квадратов в применении к точкам {( -1, 2), (1, 1), (2, 1), (3, 0), (5, 3)} (чёрные). Показан наилучший квадратный трёхчлен и его значения (светлые кружки). Серые отрезки - невязки, их сумма квадратов должна быть как можно меньше.

Ответ: квадратный трёхчлен

F(x) = 1.200 - 0.757ж + 0.214ж2,

представляет собой наилучшее приближение в смысле наименьших квадратов.

На практике при решении нормального уравнения (31.33) строят LU-разложение матрицы АТА - это положительно определённая симметрическая матрица (если А имеет полный ранг, см. упр. 31.13 и теорему 31.6).

Упражнения

31.6-1

Докажите, что все элементы на диагонали положительно определённой симметрической матрицы положительны. 31.6-2

Докажите, что для положительно определённой симметрической

матрицы размера 2 X 2 дискриминант ас - Ь2 положителен,

выделив полный квадрат в соответствующей квадратичной форме (аналогично доказательству Леммы 31.15). Как вывести это из утверждения леммы 31.15? 31.6-3

Докажите, что наибольший элемент положительно определённой матрицы матрицы находится на её диагонали. 31.6-4

Докажите, что определитель всякого углового минора положительно определённой симметрической матрицы положителен. 31.6-5

Пусть Ak - к - й угловой минор положительно определённой симметрической матрицы А. Докажите, что в при построении LU-разложения матрицы А с помощью LU-Decomposition к-й главный элемент будет равен det(Ajt)/det(Ajt-i). (Мы полагаем условно det(Ao) = 1.)

31.6-6

Даны точки (1,1), (2,1), (3, 3), (4, 8). Постройте приближение вида

F[x) = с\ + с2х lg ж + с3ех

методом наименьших квадратов. 31.6-7


Докажите следующие свойства псевдообратных матриц:

АА+А А+АА+

(АА+)Т (А+А)т

А

А+,

АА+,

А+А.

Задачи

31-1 Вероятностный алгоритм Шамира для умножения булевых матриц.

В разделе 31.3 мы видели, что алгоритм Штрассена нельзя просто так применить для булевых матриц, поскольку булево квазикольцо Q = ({0,1}, V, Л, 0,1) не является кольцом. Теорема 31.10 модифицирует алгоритм Штрассена и позволяет умножить две бу-левые матрицы размера га X га за время 0(ralg7), но арифметические операции приходится выполнять над 0(lg га)-битовыми числами. Вероятностный алгоритм Шамира производит только битовые операции и работает почти столь же быстро, однако не всегда даёт правильный ответ. Сейчас мы его опишем.

a.Покажите, что числовая система R = ({0,1}, ©, Л, 0,1), где © означает XOR (исключаещее ИЛИ, сложение по модулю 2) представляет собой кольцо.

Пусть А и В - булевы (га X га)-матрицы, а С = АВ - их произведение над квазикольцом Q Построим по матрице А матрицу А так: нули остаются на своих местах, а каждая единица либо остаётся на месте, либо заменяется нулём (с вероятностью 50%, разные единицы ведут себя независимо).

b.Положим С = (с--) = АВ, причём умножение выполняется над кольцом R. Докажите, что если c8j = 0, то с- - = 0. Докажите, что если Cij = 1, то с- - = 1 с вероятностью 1/2.

c.Взяв произвольное е > 0, повторим процедуру построения А и вычисления С чем lg(ra2/e) раз или более, каждый раз делая независимые случайные выборы. Докажите, что если c8j = 1 для некоторых г и j, то вероятность того, что с-- ни разу не примет значения 1, не превосходит е/п2. Докажите, что вероятность того, что в любой позиции, где c8j = 1, хоть раз был правильный ответ (т.е. 1), не меньшее 1-е.

d.Для любой константы к укажите алгоритм, вычисляющий произведение двух булевых (га X га)-матриц за время 0(ralg7lgra) с вероятностью ошибки не выше 1/пк. Над элементами матриц разрешается производить только побитовые операции Л, V и ©.

31-2 Трёхдиагональные системы линейных уравнений.



[стр.Начало] [стр.1] [стр.2] [стр.3] [стр.4] [стр.5] [стр.6] [стр.7] [стр.8] [стр.9] [стр.10] [стр.11] [стр.12] [стр.13] [стр.14] [стр.15] [стр.16] [стр.17] [стр.18] [стр.19] [стр.20] [стр.21] [стр.22] [стр.23] [стр.24] [стр.25] [стр.26] [стр.27] [стр.28] [стр.29] [стр.30] [стр.31] [стр.32] [стр.33] [стр.34] [стр.35] [стр.36] [стр.37] [стр.38] [стр.39] [стр.40] [стр.41] [стр.42] [стр.43] [стр.44] [стр.45] [стр.46] [стр.47] [стр.48] [стр.49] [стр.50] [стр.51] [стр.52] [стр.53] [стр.54] [стр.55] [стр.56] [стр.57] [стр.58] [стр.59] [стр.60] [стр.61] [стр.62] [стр.63] [стр.64] [стр.65] [стр.66] [стр.67] [стр.68] [стр.69] [стр.70] [стр.71] [стр.72] [стр.73] [стр.74] [стр.75] [стр.76] [стр.77] [стр.78] [стр.79] [стр.80] [стр.81] [стр.82] [стр.83] [стр.84] [стр.85] [стр.86] [стр.87] [стр.88] [стр.89] [стр.90] [стр.91] [стр.92] [стр.93] [стр.94] [стр.95] [стр.96] [стр.97] [стр.98] [стр.99] [стр.100] [стр.101] [стр.102] [стр.103] [стр.104] [стр.105] [стр.106] [стр.107] [стр.108] [стр.109] [стр.110] [стр.111] [стр.112] [стр.113] [стр.114] [стр.115] [стр.116] [стр.117] [стр.118] [стр.119] [стр.120] [стр.121] [стр.122] [стр.123] [стр.124] [стр.125] [стр.126] [стр.127] [стр.128] [стр.129] [стр.130] [стр.131] [стр.132] [стр.133] [стр.134] [стр.135] [стр.136] [стр.137] [стр.138] [стр.139] [стр.140] [стр.141] [стр.142] [стр.143] [стр.144] [стр.145] [стр.146] [стр.147] [стр.148] [стр.149] [стр.150] [стр.151] [стр.152] [стр.153] [стр.154] [стр.155] [стр.156] [стр.157] [стр.158] [стр.159] [стр.160] [стр.161] [стр.162] [стр.163] [стр.164] [стр.165] [стр.166] [стр.167] [стр.168] [стр.169] [стр.170] [стр.171] [стр.172] [стр.173] [стр.174] [стр.175] [стр.176] [стр.177] [стр.178] [стр.179] [стр.180] [стр.181] [стр.182] [стр.183] [стр.184] [стр.185] [стр.186] [стр.187] [стр.188] [стр.189] [стр.190] [стр.191] [стр.192] [стр.193] [стр.194] [стр.195] [стр.196] [стр.197] [стр.198] [стр.199] [стр.200] [стр.201] [стр.202] [стр.203] [стр.204] [стр.205] [стр.206] [стр.207] [стр.208] [стр.209] [стр.210] [стр.211] [стр.212] [стр.213] [стр.214] [стр.215] [стр.216] [стр.217] [стр.218] [стр.219] [стр.220] [стр.221] [стр.222] [стр.223] [стр.224] [стр.225] [стр.226] [стр.227] [стр.228] [стр.229] [стр.230] [стр.231] [стр.232] [стр.233] [стр.234] [стр.235] [стр.236] [стр.237] [стр.238] [стр.239] [стр.240] [стр.241] [стр.242] [стр.243] [стр.244] [стр.245] [стр.246] [стр.247] [стр.248] [стр.249] [стр.250] [стр.251] [стр.252] [стр.253] [стр.254] [стр.255] [стр.256] [стр.257] [стр.258] [стр.259] [стр.260] [стр.261] [стр.262] [стр.263] [стр.264] [стр.265] [стр.266] [стр.267] [стр.268] [стр.269] [стр.270] [стр.271] [стр.272] [стр.273] [стр.274] [стр.275] [стр.276] [стр.277] [стр.278] [стр.279] [стр.280] [стр.281] [стр.282] [стр.283] [стр.284] [стр.285] [стр.286] [стр.287] [стр.288] [стр.289] [стр.290] [стр.291] [стр.292] [стр.293] [стр.294]