Главная Методы условной оптимизации [0] [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] Обычно е подбирают так, чтобы в /-Й позиции получить нуль. Если сам вектор обозначен через х, для этого надо положить s-=±Xj/r, c=±Xj/r, где /-= (Xf-bx)/. Из двух возможных знаков обычно выбирают верхний. Компактное описание любого плоского поворота представляет собой четверку чисел: /, /, s и с. Поскольку преобразованием Хаусхолдсра можно осуществить любой [юворот, причем векторы, ортогональные w, прн этом останутся неизменными, с помощью п таких преобра,зований любую mxn-матрицу А ранга п можно переделать в верхнюю треугольную. Очередное, i-e преобразование Я; подбирается так, чтобы обнулить в 1-м столбце элементы с i+1-ro по т-й, сохранив первые i-I столбцов нетронутыми. (Когда т=п, на все потребуется п-1 преобразований.) В частности, преобразование Hi должно перевести столбец с, матрищ.! А в вектор, коллинейрный единичному. Поскольку норма при этом сохранится, последний будег иметь вид (Гц, о, . . .. О)", где Г1, = %1а. Соответственно в качестве w дли Hi можно взять (Си-Гц. а,1, . . ., a„i). Чтобы избежать ошибок компенсации при подсчете первой компоненты этого вектора, знак Гп берут противотюложным знаку Оц. После п преобразований Хаусхолдера получим H„...HHiA = QA (2.45) где R есть невырожденная верхняя треугольная пхп-матрица, а Q - ортонормальная матрица, равная произведению Н„ . Hi Представление (2.45) называют QR-разложением А. Предположение о полном столбцовом ранге А существенно прн выводе (2.45), поскольку оно гарантирует, что преобразуемая часть очередтюго столбца всегда будет ненулевой, т. е. определения всех п преобразований Н, будут корректны. Если же ранг А равен г<.п, надо переставить столбцы так, чтобы первые г стали линейно независимыми. Тогда результатом г соответствующих преобразований над ними будет представление вида QAP = где Р - перестановочная, а Г - верхняя трапециевидная гхп-матрица. После этого дополнительными г преобразованиями Хаусхолдера над строками можно обнулить последние п-г столбцов сохранив треугольную структуру (но не сами элементы!) левой верхней части матрицы. Окончательно получим QAPH,...Hi = QAV = где Л - этогхг-невырожденная верхняя треугольная, а V - пхп-ортонормальная матрица. Это представление называют полным ортогональным разложением матрицы А. Ортогональные факторы приведенного разложения несут информацию о пространствах, натянутых на строки и столбцы А. Расщепим матрицу на две составляюцие следующим образом: Q=(Q.ez). где Qi и Qs суть тхг- и тх (т-rj-MarpHnbi соответственно. Тогда столбцы Qi будут ортоиормальным базисом столбцового пространства А, а столбцы Qi сформируют ортонормальиый базис его ортогонального дополнения. Кро.ме того, если г<;/г, последние п-г строк матрицы V образуют ортотюрмальный базис для множества векторов, ортогональных строкам А. Число операций, требуемых для расчета Q, R ч V,B прямоугольном случае определяется значениями т, п и г. Если innr, то количества сложений и умножений будут приблизительно равными тя=-(n-r)r. Когда разложение, аналогичное рассмотренному, требуется для матрицы А с полным строковым рангом (с линейно независимыми строками), то, как правило, его удобнее строить в форме известной под названием «LQ-разложение». Чаще всего ортогональные разложения используются при решении линейных задан о наи.ченьших кеадратих: найти дг. такой, чтобы величина ЦЛл;- Ь\\\ была минимальной. Поскольку орто-нормальное преобразование сохраняет евклидову длину вектора, исходная невязка (вектор АхЬ) будет иметь ту же норму, что и преобразованная матрицей Q. Таким образом, справедливо равенство I Ax-bli Q (Ах-Ь) I = 1] Rx- Qbi, или, что то же самое, Лл:-Ьа = x-Qb Из выражения в правой части видно, что норма преобразованного вектора невязок минимальна, когда первые п компонент векторов д: и Qb совпадают. Соответственно при п=г искомый вектор х будет единственным решением невырожденной линейной системы вида R.K=Q{b. 2.2.5.4. Спектральное разложение симметричной матрицы. Известно, что все собственные числа симметричной матрицы А вещественны, а из ее собственных векторов можно составить ортонормальиый базис в 8i". Обозначим зги числа {К, , К), а векторы через {ui.....и„}. Тогда по определению Au,=KiU,, 1=1.....п. (2.46) Введя матрицу U, i-й столбец которой равен и,, эти векторные равенства можно заменить одним матричным AU=UA, где Л= =diag(J,i, . . ., ). Так как U по построению ортонормальна, отсюда следует, что A = UAU. или, в более понятной форме. (2.47) &ГО представление называется спектральным разложением матрицы А. Итеративный алгоритм построения собственной системы симметричной матрицы требует около in сложений и умножений. 2.2.5.5. Разложение по особым числам. Любая тхп-матрица может быть представлена в виде А = иХ V, где f - ортонормальная mxm-матрица, V -ортонормальная пхп- матрнца, а 2 = diag {о,.....а„} -диагональная mXn-матрица с Oi>0 при любом i. Величины {о,} называют особыми числами матрицы А, и обычно предполагают, что оии упорядочены по убыванию; ai>aa>. . .>0 Если ранг матрицы А равен г, то о,>0, о,.+,=0, т. е. у нее будет ровно г ненулевых особых чисел. При этом особые числа обладают следующими свойствами; (i) а!(Л)=Я,,1Л-Л1; (ii) ai(A)=\\A\\t (максимальное особое число равно квадратичной норме матрицы). Для квадратной невырожденной матрицы А минимальное особое число а„ равно «расстоянию» (измеренному с помощью квадратичной нормы) от А до ближайшей вырожденной матрицы: а„=га1пЛ-S, где S - вырожденная матрица. Разложение по особым числам для симметричной матрицы легко получается из ее спектрального разложения, причем с,=\К,\. 2.2.5.8. Псевдообратные матрицы. Для любой невырожденной квадратной матрицы А однозначно определена обратная матрица А такая, что при произвольной правой части Ь решением системы АхЬ будет вектор х=Л->й. Если же Л - выронаденная или прямоугольная матрица, обратной к ней ие сущесгвует; более того, в этих случаях система Ах=Ь может оказаться несовместной. Здесь естественно пользоваться обобщением понятия обратного преобразования, которое формулируется в терминах соответствующей задачи минимизации суммы квадратов иевязок. Псевдообратной к т,<п-матрице Л называют матрицу Л+, однозначно определенную следующим требованием: при любой правой части Ь формула х=А*Ь должна давать самый «короткий» (в смысле евклидовой нормы) вектор из множества решений задачи минимизации значения Ufc-Ах\],. Существует несколько математически эквивалентных выражений для матрицы, псевдообратной к А. Если А невырожденная, то A*=A~. Когда А имеет полный столбцовый ранг, ее псевдо-обратиую матрицу можно представить так: A*(AA)-A. В этом же случае, располагая QR-разложением (2.45), можно воспользоваться формулой A*=R-Ql, причем именно она рекомендуется для конкретных вычислений. При неполном ранге А наиболее удобная форма представления А* вытекает из разложения по особым числам. Если Л = 1/2 V с г ненулевыми особыми числами, то A+=VQU, где £2=diag((i)i) с (а,=11а,, . . ., г, и ю;=0, 1г+1. 2.2.5.7. Пересчет матричных разложений. При составлении многих алгоритмов приходится решать проблему организации перехода от известного разложения некоторой матриць1Л к неизвестному разложению тесно связанной с ней матрицы А. Естественно, что при этом хочется как-то использовать старое разложение, с тем чтобы сократить объем вычислений, необходимых для построения нового. Кардинальный способ экономного планирования вычислений в этой ситуации состоит в том, чтобы найти метод модификации или пересчета разложения исходной матрицы. В большинстве случаев модификация потребует существенно меньших усилий, чем выполнение полного цикла расчетов, необходимых, чтобы построить разложение, начиная «с нуля». Соответствующие эффективные методы модификации имеются для всех рассмотренных ранее матричных разложений. Однако их детальный разбор выходит за рамки данной книги, и поэтому здесь будут кратко описаны только два из них. Оба относится к наиболее часто встречающемуся в оптимизационных приложениях случаю, когда Л отличается от А на матрицу ранга один (см. разд. 2.2.1.5). Простейшая модификация ранга один состоит в присоединении к матрице столбца. Отпоситсльно иее любую процедуру факторизации, в которой столбцы обрабатываются поочередно, можно рассматривать как последовательность пересчетов. Таким образом, здесь нет нужды придумывать специальные методы модификации: они уже содержатся в основных процедурах. Рассмотрим, например, обновление QR-разложения для матрицы Л, получающейся присоединением справа к mxn-матрице А нового столбца а. При этом где и,, Ua - составляющие т-мерного вектора v=Qa, aQ, R - факторы разложения Д. Обозначим через „ + , матрицу Хаусхолдера, которая обнуляет компоненты вектора v с (п+2)-й по т-ю, оставляя первые п компонент v неизменными, так что где lYl=lt/al8. Тогда, применив Я„+1 к QA, получим \о о/ или, что то же самое. Это - формула Q/J-разложения для А. Оно получено преобразованиями, которые по сути есть не что иное, как один шаг общей процедуры 0/?-факторизацин, и включают построение ровно одной матрицы Хаусхолдера, Некоторые другие процедуры факторизации также удается проинтерпретировать в терминах обновления факторов при последовательной модификации матрицы. После этого методы пересчета становятся естественным продолжением исходных процедур, и их нетрудно получать в форме, допускающей не только более сложные прямые, но и обратные преобразования матриц. Еще один метод пересчета факторов, который мы рассмотрим в этом разделе, это метод вывода разложения по Холесскому для положительно определенной матрицы В, получающейся из положительно определенной матрицы В модификацией вида B=B+vv. В случае с верхним знаком имеем B=LDU+m=L (D+pp)L-, где р - решение треугольной системы Lp=v. При зтом структура матрицы D-pp" настолько проста, что для элементов ее факторов Холесского (которые обозначтгм через L и D) легко выписать нерекуррентные формулы. Таким образом. B = LLt)UL =LDL\ где через L обозначено произведение LL, а D=D. Поскольку результатом перемножения двух единичных нижних треугольных матриц является матрица того же вида, полученное равенство и есть искомое разложение. Вычисления здесь можно организовать так, что расчет компонент вектора р и умножение L на L будут вестись параллельно, причем потребуют всего лишь порядка п" операций. Соответствующий экономный алгоритм вычисления Е и D состоит в следующем: (i) положить <о=1, u"=f; (ii) для / = 1, 2, .... п найти Pj = l", / = /-i+pH- d,-=d,-(,-/(, i, Р,- = Р/даЛ) . l,, = l,, + P/,/*"J Если матрица В возникает в результате вычитания, при обновлении факторов должны быть приняты особые меры предосторожности, исключающие возможность потери положительной определенности (появления иа диагонали В неположительных элементов) из-за ошибок округления. Поэтому алгоритм в данном случае будет несколько сложнее предыдущего: (i) решить уравнение Lp=v и вычислить („+i=l-pD-p; если (,n-i<e,vf, положить („+i=e„, где - относительная машинная точность; (ii) для У=п, п-I, . . ., 1 вычислить t, = t,4.i+P]/d„ d, = djt,.Jt,. t/=vJ*"+Pjl,j.] ;Ч-1, Поскольку предполагается, что теоретически положительная определенность матрицы В гарантирована, точное значение величины („.1 должно быть положительным. Заменяя слишком малое значение („+, на е, мы рискуем сделать ошибку того же порядка, что и ошибка, возникающая при вычислении разности ВВ-vu. При этом нетрудно убедиться, что все значения dj, /=1, 2, . . ., п, вычисляемые по представленной выше схеме, будут положительны независимо от того, какие ошибки округления возникнут в расчетах. Аналогичные методы применимы и для пересчета факторов разложения (2.42). [0] [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] 0.0017 |