Skeleton decomposition of rectangular matrices and its application for structural regularization of ill-conditioned systems of linear algebraic equations.pdf Пусть нам дана система линейных алгебраических уравнений (1) (2) Ш = у. Здесь у - правая часть СЛАУ - заданный n-мерный вектор, где n - некоторое ограниченное натуральное число больше 2; а - неизвестный n-мерный вектор - ее решение, а U - заданная квадратная порядка n матрица коэффициентов данной СЛАУ, которая является невырожденной, но плохо обусловленной матрицей, т.е. такой, что ее ранг rU и число ее обусловленности cond U удовлетворяют следующим соотношениям: rU = n , cond U >> 1. Здесь символ « >> » означает, что cond U существенно, т.е. в 100 и более раз больше 1. Как известно [1, 2], характерной особенностью подобных СЛАУ является чрезмерно высокая чувствительность их решений a к различного рода изменениям их правых частей y и матриц коэффициентов U. Последнее означает, что даже самые незначительные изменения Ду вектора y и (или) AU матрицы U влекут за собой столь значительные изменения Да решения a исходной СЛАУ (1), что вычисленное решение а = а + Да может оказаться сколь угодно далеким от интересующего нас решения а и не иметь с ним ничего общего. Получить пригодное для практических приложений решение подобной СЛАУ оказывается возможным только в случае применения для его вычисления того или иного метода регуляризации, позволяющего исправить решаемую СЛАУ таким образом, чтобы решение регуляризированной (исправленной) СЛАУ оказалось менее чувствительным к изменениям ее исходных данных и, вместе с тем, достаточно близким к решению а и пригодным для дальнейшего его использования. В настоящее время известен целый ряд методов регуляризации плохо обусловленных СЛАУ, основанных на различных идеях и подходах [1, 3]. Характерная особенность данных методов состоит в том, что регуляризация решаемой СЛАУ осуществляется с помощью так называемых параметров регуляризации, варьируя которые удается добиться желаемой устойчивости вычисляемого решения к изменениям исходных данных СЛАУ и его приемлемой точности. Для их отличия от метода регуляризации, рассматриваемого ниже, назовем и будем называть их всюду далее, методами параметрической регуляризации плохо обусловленной СЛАУ. Учитывая отмеченную выше особенность данных методов, можно видеть, что предлагаемое их название представляется достаточно обоснованным и вполне оправданным. Целью данной работы является рассмотрение нового метода регуляризации плохо обусловленных СЛАУ, названного и называемого нами далее методом структурной регуляризации подобных СЛАУ. Сущность предлагаемого метода заключается в изменении структурных характеристик решаемой СЛАУ таким образом, чтобы решение измененной СЛАУ оказалось устойчивым к изменениям ее исходных данных и пригодным для его дальнейшего использования. При этом под структурными характеристиками СЛАУ далее будем понимать размерности строк и столбцов ее матрицы U и соответственно ее правой части у и решения а. 1. Определение и важнейшие свойства скелетных разложений прямоугольных (шхи)-матриц Предлагаемый метод структурной регуляризации плохо обусловленных СЛАУ основан на использовании известных в теории матриц так называемых скелетных разложений прямоугольных матриц и, таким образом, понятие «скелетное разложение прямоугольной матрицы» является для наших целей основополагающим. Поэтому и для упрощения последующего описания предлагаемого метода в данном разделе приведем необходимые нам сведения о скелетных разложениях прямоугольных матриц и, чтобы не вводить в рассмотрение еще какую-либо матрицу, сделаем это применительно к нашей матрице U, временно считая при этом, что она является прямоугольной (тх^-матрицей и ее ранг равен rU . Здесь m, n и rU - соответственно число строк, число столбцов и ранг матрицы U - некоторые натуральные числа, такие, что m может быть как больше, так и меньше или равно n , а rU - не больше меньшего из m и n. Как известно из теории матриц [4], скелетным разложением матрицы U принято называть равенство вида U = SR. (3) Здесь S и R - прямоугольные (m х rU) - и (rU х n) -матрицы соответственно, ранги rS и rR которых удовлетворяют соотношениям rS = rU , rR = rU . (4) Данные равенства означают, что S и R являются так называемыми матрицами полного или максимального ранга (их ранги равны их меньшим размерностям, больше которых ранги матриц не могут быть по определению) или, что то же самое, S является столбцово-невырожденной, а R - строчно-невырожденной матрицей. Отметим свойства скелетных разложений матрицы U, являющиеся для наших целей основополагающими. 1. Для любой матрицы U существует сколь угодно много скелетных разложений. В самом деле, пусть матрицы S и R удовлетворяют равенству (3). Тогда этому же равенству удовлетворяют и матрицы S' и R', определяемые равенствами вида S' = SP, R' = P lR, где P- некоторая невыфожденная порядка rU матрица, а P 1 - обратная к ней матрица. Составив произведение S 'R', можно видеть, что оно также удовлетворяет равенству (3) и, таким образом, также является скелетным разложением матрицы U. Отсюда, учитывая, что невырожденных порядка rU матриц P существует сколь угодно много и каждая из них позволяет получить некоторое скелетное разложение матрицы U, можно заключить, что множество возможных скелетных разложений данной матрицы является бесконечным несчетным множеством. 2. Представив матрицу U как совокупность векторов-столбцов, т.е. равенством вида U = (u1 u2... un), можно элементарными выгчислениями убедиться в том, что матричное равенство (3) вполне эквивалентно следующей совокупности вектор-но-матричных равенств: ru _ Sr] =X skrkj =u j, j=1 n. (5) k=1 Непосредственно видно, что j-е равенство в данном случае является не чем иныш, как разложением j-го столбца u ■ матрицы U по столбцам sk, k = 1, ru матрицы S. При этом коэффициентами данного разложения являются компоненты rkj вектора-столбца rj матрицы R. 3. При любой заданной столбцово-невыфожденной матрице S j-е равенство (5) является СЛАУ относительно j-го столбца rj матрицы R, правая часть которой равна j-му столбцу uj матрицы U, j = 1, n, и так как имеет место равенство (4а), то данная СЛАУ оказывается совместной и имеет бесконечное множество решений. 4. В случае, когда вместо точно заданной матрицы U приходится иметь дело с матрицей U , удовлетворяющей равенству U = U + AU, где AU - прямоугольная (m х n) -матрица, элементами которой являются погрешности (ошибки) задания элементов матрицы U, оказывается необходимым и возможным использовать обобщенное или, что то же самое, условное скелетное разложение матрицы U, определяемое равенством вида U « SR, (6) используя при этом в качестве количественной меры близости между его левой и правой частями следующее условие: II U - SR ||< regu , (7) где || • || - евклидова норма матриц, а regu - некоторое достаточно малое положительное число, выбираемое с учетом погрешностей задания матрицы U. Назовем и всюду далее будем называть данное число параметром структурной регуляризации скелетного разложения матрицы U . Если параметр регуляризации regU = 0, то, как вытекает из (7) и определения нормы матриц, условное равенство (6) превращается в строгое равенство и, таким образом, получаемое при этом обобщенное скелетное разложение матрицы U оказывается не чем иным, как простым или классическим скелетным разложением данной матрицы, определяемым строгим равенством (3). В случае, когда regU > 0, получаемое скелетное разложение матрицы U оказывается ее обобщенным скелетным разложением, ранги r^ и rR матриц S и R которого удовлетворяют соотношениям r- = rR < U, при этом ранг r- существенно зависит от выбранного значения regU и оказывается тем меньше, чем большее значение имеет параметр регуляризации regU , изменяясь при этом в пределах от r^ = r до r- = 1 S ■ Отмеченные выше свойства простого и обобщенного скелетных разложений матрицы U позволяют составить достаточно полное представление о их важнейших свойствах. Данные свойства, очевидно, в полной мере сохраняются и в случае любой квадратной порядка n матрицы. В частности, если данная матрица оказывается плохо обусловленной, то использование ее обобщенного скелетного разложения позволяет предложить целый ряд методов структурной регуляризации плохо обусловленных СЛАУ. 2. Анализ возможностей и некоторых проблем построения скелетных разложений (шхи)-матриц Приведенные выше сведения о скелетных разложениях матрицы U позволяют непосредственно видеть, что для получения какого-либо конкретного ее скелетного разложения необходимо и достаточно задать некоторую конкретную матрицу S и, решая n СЛАУ вида (5), вычислить матрицу R. Рассмотрим более детально возможности и некоторые проблемы скелетного разложения (3) матрицы U, имея в виду при этом ее представление (5). 1. Для получения скелетного разложения (3) матрицы U необходимо прежде всего задать (т х rS) -матрицу S ранга rS . Так как подобных матриц сколь угодно много, то задать конкретную S можно, только учитывая те или иные дополнительные соображения и требования (минимальный объем вычислений, устойчивость решения, удобство программирования и т.п.). 2. При любой заданной матрице S построение скелетного разложения (3) матрицы U сводится к решению n систем линейных алгебраических уравнений вида (5) относительно столбцов r}- матрицы R. Поскольку ранги матриц U и S равны rU и rU < n , а правыми частями данных СЛАУ являются столбцы матрицы U, то все эти СЛАУ оказываются совместными. 3. Трудоемкость решения данных СЛАУ и свойства их решений r^, j = 1, n , существенно зависят от выбранной и используемой матрицы S. В частности, если матрицу S выбрать в соответствии с равенством S = U1, где U1 - (m х ru) -матрица, составленная из rS линейно независимых столбцов матрицы U и этими столбцами являются ее первые rS столбцов, то матрица R будет определяться равенством вида R = (Ers |R1), где блок Ers - единичная порядка rS матрица, а блок R1 - прямоугольная (rS х (n - rS)) -матрица, являющаяся решением матричного уравнения U1R1 = U2, правая часть U2 которого является прямоугольной (m х (n - r)) -матрицей, составленной из остальных (n - rS) столбцов матрицы U, линейно зависимых с ее первыми rS столбцами; 4. В случае, когда матрица S является столбцово-ортогональной матрицей, удовлетворяющей равенству ST S = D, где St - транспонированная матрица S, а D - диагональная порядка rS матрица, диагональные элементы dii которой вычисляются по формулам dn =(si, si ) i = 1 rs , (8) сомножитель R скелетного разложения (3) имеет вид R = D-lSTU . (9) Здесь D 1 - обратная к D матрица. При этом, если столбцы матрицы S не только попарно ортогональны, но и являются нормированными векторами и соответственно удовлетворяют равенствам || Sj ||= 1,0, j = 1, rS, где || sj || - евклидова норма вектора sj, выгчисляемая согласно равенству s1/2 ||s j||=|S sj V i=1 то равенства (8) и (9) предельно упрощаются и принимают следующий вид: dti = 1,0, i = vS, R = s t u . Приведенные результаты позволяют видеть, что задача построения скелетных разложений (3) матрицы U является существенно недоопределенной задачей. Данная особенность задачи является, с одной стороны, благом, так как она открывает широкие возможности построения различных скелетных разложений (3). С другой - она создает проблемы, обусловленные отсутствием в настоящее время каких-либо критериев и правил, позволяющих строить данные разложения в тех или иных конкретных условиях. 3. Построение робастного множителя S обобщенного скелетного разложения плохо обусловленной матрицы U Теперь мы откажемся от принятого выше временного допущения о том, что U является прямоугольной (m х n) -матрицей и всюду далее будем считать, что она является квадратной порядка n матрицей, а ее ранг rU и число обусловленности condU удовлетворяют соотношениям (2). Рассматриваемое построение матрицы S основано на использовании хорошо известного в линейной алгебре метода ор-тогонализации конечномерных векторов, называемого процедурой Грама - Шмидта [3, 4]. Результатом его применения являются матрицы S и Q, где Q -вспомогательная (n х n) - матрица, а его реализация сводится к выполнению следующих этапов. 1. Первые столбцы s1, q1 и подматрицы S1, Q1 матриц S и Q вычисляем в соответствии с равенствами s = «711 и1 II; q = u1; S1 = S1; Q = q; \ = q =1. Здесь u1 - первый столбец матрицы U, который считаем неравным нулевому n-мерному вектору 0n, а || u1 ||=(«1,u1 )1/2- евклидова норма столбца u1. Полученный столбец s1 является нормированным вектором, т.е. таким, что его евклидова норма || s1 ||= 1,0 . 2. Остальные столбцы sk , qk и подматрицы Sk , Qk матриц S и Q, а также их ранги rS^ и q , k = 2, n, формируем, выполняя при каждом значении k следующие операции. 2.1. Строим ортогональную проекцию pk столбца uk на линейную оболочку L ( s1, s2,..., sk), натянутую на столбцы s1, s2,..., skматрицы Sk, вычисляя ее в соответствии с соотношением Pk = Sk-1ck = c1k S1 + c2k S2 + ... + ck-\,k Sk-1 , (10) где Sk- (mх(k-1)) -матрица, составленная из k-1 столбцов s1,s2,...,sk, сформированных на предшествующих k -1 этапах; c1k,c2k,...,ck-1k - коэффициенты, вычисляемые согласно равенствам cik =(uk, sj ) = Z uiksu , j = 1k - L (11) i=1 Замечание 1. Непосредственными вычислениями нетрудно убедиться в том, что совокупность данных равенств можно представить одним, эквивалентным им векторно-матричным равенством вида ck = Sl-1uk, где S^ - транспонированная матрица Sk-1 . Замечание 2. Пусть k = 2 . В этом случае (10) и (11) принимают следующий вид: m p2 = S1c2 = c12s1, c12 = (u2 , S1 ) = Z Ui2Si1 . i =1 Воспользовавшись данными равенствами, легко проверить, что в случае, когда столбцы u2 и s1 являются строго линейно зависимыми, то p2 = u2, а в случае, когда u2 и s1 являются ортогональными, p2 = 0п, где 0п - нулевой n-мерный вектор-столбец. 2.2. Вычисляем вспомогательный вектор vk и его евклидову норму || vk || в соответствии с формулами 1/2 = uk-pk = uk-Sk-А; || vk ||= (Кj . (i2) 2.3. Проверяем неравенство вида || vk ||> regu , (13) где regu - некоторое заданное положительное число - параметр структурной регуляризации СЛАУ (1). 2.4. Если данное неравенство вытолняется, то формируем k-е столбцы sk , qk и подматрицы Sk, Qk матриц S и Q согласно следующим равенствам: sk = vkl\\vk||; 4k = uk; Sk =(Sk-1 = sk); Qk = (Qk-14), (14) а их ранги rs и q выгчисляем в соответствии с соотношениями \ = \-1 +1, Q = Q-1 +1. (15) 2.5. Если неравенство (13) не выполняется, то формируем матрицы Sk и Qk и их ранги rSt и q в следующем виде: Sk =( Sk-1 к), Qk = (Qk-1 \0„); (16) rsk = rsk-1, Q = Q-1. (17) т.е. оставляем их равными матрицам Sk-1 и Qk-1, сформированным на предшествующих k -1 этапах. 2.6. Выполнив операции (10), (11), (12) - (17) при k = n , получаем матрицы Sn и Qn и формируем необходимые нам матрицы S и Q согласно равенствам S = Sn, Q = Qn . Замечание 1. Полученная матрица S является прямоугольной (n х rs) -матрицей, ранг которой равен числу ее столбцов rs. При этом ее столбцы являются ор-тонормированными векторами-столбцами и, таким образом, она удовлетворяет равенству ST S = Er , (18) s где ST - транспонированная матрица S, а Er - единичная матрица порядка rs. Замечание 2. Как и матрица S, полученная матрица Q является прямоугольной (n х rS) -матрицей и ее ранг rQ = rS и, таким образом, она оказывается столбцовоневыфожденной матрицей. При этом ее столбцы qj, j = 1, rQ , являются строго линейно независимыми столбцами. Замечание 3. Как будет видно ниже, выполняя операции (16), тем самым устраняем (выбрасываем) столбец uk матрицы U, а компоненту ak решения a СЛАУ (1) полагаем равной 0. Устранение uk и обнуление компоненты ak в данном случае является, очевидно, вполне обоснованным. Действительно, в этом случае выполняется противоположное неравенство || vk ||< regu , которое означает, что между столбцом uk и предшествующими ему столбцами имеет место достаточно тесная линейная зависимость и, следовательно, его можно изъять из матрицы U, а соответствующую ему компоненту ak решения a СЛАУ (1) положить равной 0 и, тем самым, увеличить его устойчивость к ошибкам задания матрицы U. Замечание 4. Как видно из (10), (13) и (16), число столбцов матрицы существенно зависит от параметра регуляризации regU и, таким образом, изменяя его значение, можно существенно изменять число rs . При этом, чем при большем значении regU построена матрица S, тем она имеет меньшее число столбцов rs, и наоборот. Более детально выбор значения regU при построении матрицы S рассмотрим ниже. Здесь же отметим только, что устраняя столбец uk матрицы U и обнуляя соответствующую ему компоненту ak решения a СЛАУ (1) в соответствии с изложенным выше способом, тем самым осуществляем ее структурную регуляризацию. При этом ее результатом является регуляризированная СЛАУ, число столбцов матрицы коэффициентов и размерность решения которой оказываются согласованными и определяются используемым значением regU . 4. Построение регуляризированных скелетных разложений матрицы U и регуляризированных решений СЛАУ (1) Здесь и всюду далее под регуляризированным скелетным разложением матрицы U будем понимать ее скелетное разложение, определяемое равенством вида Q = SR , где S - прямоугольная (n х rS) - матрица, построенная в предыдущем пункте и соответственно являющаяся не только столбцово невырожденной, но и столбцово-ортогональной матрицей, а R - неизвестная нам прямоугольная (rS х n) -матрица. Построение данных разложений сводится к выполнению следующих операций. 1. Множитель R вычисляем согласно равенству R = (ST S)-1 STQ . Так как столбцы Sj матрицы S являются ортонормированными векторами, то матрица S удовлетворяет равенству (18), а равенство для определения R принимает следующий предельно простой вид: R = Ers ST Q = ST Q . 2. Вычисляем матрицы U и AU, а также евклидову норму || AU || матрицы AU в соответствии с равенствами / \1/2 n Z Au2 V h 1=1 У U = SR; AU = U-U; || AU ||= 3. Проверяем неравенство вида || AU ||< A . (19) Здесь A - некоторое заданное положительное число, выбираемое с учетом погрешностей задания матрицы U в (3), и если оно выполняется, то на этом процесс построения скелетного разложения SR матрицы U заканчиваем. 4. Если данное неравенство не выполняется, то задаем новое значение параметра regU , определяя его равенством regU = 0,5regU , и строим новое скелетное разложение S1R1 матрицы U, выполняя при этом рассмотренные выше 2-й и все последующие этапы еще раз. Процесс построения данного разложения продолжаем до тех пор, пока не будет выполнено неравенство (19). Из вышеизложенного следует, что решение СЛАУ (1) сводится к решению СЛАУ вида Qa = У , которая оказывается переопределенной СЛАУ. Поэтому в качестве решения данной СЛАУ используем ее псевдорешение a+ , выгчисляемое согласно равенству a+= Q+У , где Q + - псевдообратная матрица к матрице Q. При этом выгчисление псевдообратной матрицы Q + реализуем в соответствии с формулой Q+ = (SR)+ = R+ S + = R (rrt )-1 (sTS)-1 ST = R (rrt )-1 ST . Как известно из линейной алгебры и теории матриц [3, 4], выгчисленное в соответствии с данными формулами псевдорешение a СЛАУ (1) минимизирует евклидову норму || y - S + Ra || вектора y - S + Ra и имеет минимальную по сравнению со всеми другими решениями данной СЛАУ евклидову норму || a || и, таким образом, из всех возможных ее решений оно оказывается наиболее устойчивым к изменениям исходных данных (ошибкам задания ее правой части y и матрицы коэффициентов U). Заключение Основные результаты данной работы сводятся к следующему: 1. Предложен метод структурной регуляризации плохо обусловленных СЛАУ, основанный на использовании скелетных разложений прямоугольных матриц. 2. Наличие в данном методе параметров regu и Д позволяет получить решение плохо обусловленной СЛАУ, устойчивое к ошибкам задания ее правой части y и матрицы коэффициентов U.

Скачать электронную версию публикации