4-1. В рамках новой теории регуляризации систем линейных алгебраических уравнений с приближенными данными, основные положения которой описаны в предыдущем разделе статьи, было разработано значительное количество конкретных методов (алгоритмов) нахождения приближенных решений систем (1), заданных аппроксимациями (2). При этом разработка методов осуществлялась с учетом следующих основных требований:
1) экономичности, т.е. возможности решения систем большой размерности за приемлемое время на современной персональной вычислительной технике (типа Pentium-2 с оперативной памятью размером 256 мегабайт и тактовой частотой 400 мегагерц);
2) устойчивости, т.е. минимального влияния тех ошибок округления, которые с неизбежностью возникают при проведении вычислений.
Совершенно очевидно, в свете всего сказанного в предыдущем разделе, что понятие метод (соответственно - алгоритм) нахождения устойчивого приближенного решения системы (1) по заданной ее аппроксимации (2) включает три основные составные части:
А) метод (алгоритм) нахождения приближенных решений системы (2) по заданным значениям параметров счета;
В) метод (алгоритм) управления процессом нахождения последовательности приближенных решений x(k), формирование множества пробных и допустимых решений в "нормальных" ситуациях, нахождение итогового решения в таких ситуациях;
С) метод (алгоритм) формирования множеств пробных и допустимых решений в "аномальных" ситуациях, нахождение итогового решения в таких ситуациях.
Ясно, что в некотором смысле определяющим (формирующим) является метод (алгоритм) А.
На первый взгляд кажется, что необходимо дать классификацию отдельно: 1) методов А); 2) методов В); 3) методов С). Однако гораздо лучше классифицировать не методы, а методообразующие идеи, или конструктивные, на что неоднократно указывал В. Н. Страхов, [см. Страхов, 1996a, 1996b, 1996c, 1998a, 1998b]. Суть дела здесь в том, что конструктивных (методообразующих) идей существенно меньше, чем методов, ибо последние всегда представляют собой реализацию определенных комбинаций конструктивных идей. Выделение конструктивных идей поэтому можно назвать "анатомией методов". По указанным соображениям ниже приводится именно классификация конструктивных (методообразующих) идей из методов класса А (нахождения приближенных решений при заданных значениях параметров счета).
4-2. Конструктивные идеи, комбинации которых образуют методы (здесь рассматриваются только методы класса А)) можно вводить, исходя их различных соображений. Авторам представляется, что наиболее полезны и понятны три классификации:
I) основанная на степени близости новых конструктивных идей к тем, которые уже давно эксплуатируются в рамках классической теории регуляризации линейных некорректных задач;
II) основанная на оценке степени перспективности (по соображениям полноты учета априорной информации, быстродействия и устойчивости вычислений);
III) основанная на том, используются или не используются ортогональные преобразования, и если используются, то какого типа.
4-3. Начнем с краткого изложения классификации I). В ней содержится три раздела: I1 ), I2 ), I3 ).
Конструктивные идеи группы I 1 ) - наиболее близкие по смыслу к тем, которые используются уже много лет в классической теории линейных некорректных задач (см. раздел 1 настоящей статьи). Это суть следующие идеи:
I11 ) использования постановок условных экстремальных задач, основанных на оценках предельной относительной погрешности приближенных решений; здесь искомыми величинами являются элементы матрицы , фигурирующие в представлениях (134) приближенных решений, см. п. 3-2 предыдущего раздела статьи;
I 12 ) использования расширенных систем линейных алгебраических уравнений 1-го рода; это конструктивная идея кратко описывается ниже, см. следующий параграф;
I 13 ) использования новых итерационных методов классического типа; здесь речь идет о методах, основанных на допущении о существенной разделенности спектров полезного сигнала и помехи, см. п.1-8; эти методы кратко описываются во второй части работы;
I 14 ) использования мультипликативно-аддитивной регуляризации; здесь речь идет о тех конструктивных приемах, которые изложены в п. 3-6 третьего раздела статьи;
I 15 ) использования приема получения решений, удовлетворяющих характеристическому уравнению метода наименьших квадратов; здесь речь идет о приеме, описанном в п. 3-4 предыдущего раздела статьи;
I 16 ) использования приема введения в классические (и новые) конструкции дополнительного параметра с целью получения возможности использования различных "принципов сохранения", о которых коротко было сказано в п. 3-5 предыдущего раздела статьи; этот прием коротко описывается в следующем параграфе настоящего раздела.
Конструктивные идеи группы I 2 ) принципиально отличны от идей группы I 1 ), они предложены В. Н. Страховым или совместно В. Н. Страховым и А. В. Страховым в последние 5-6 лет, см. работы [Страхов, 1990a, 1990b, 1991a, 1991b, 1991c, 1992a, 1992b, 1997d, 1997e, 1997f, 1997g, 1997h; Страхов, Страхов, 1998, 1999a, 1999b, 1999c, 1999d; Страхов, Тетерин, 1991а, 1991b, 1991c, 1993; Strakhov et al., 1995]. Это суть следующие идеи:
I 21 ) использования приема построения последовательности систем малой размерности - на основе процедур ортогональных преобразований исходной системы; это исключительно важная и плодотворная идея подробно описывается во второй части работы;
I 22 ) использования приема авторегуляризации; это также очень важная и плодотворная идея, суть которой в том, чтобы в процессе ортогональных преобразований (по ходу процесса преобразований) осуществлять приближенные процедуры выметания матриц; подробно эта идея рассматривается во второй части работы;
I 23 ) использования фильтрации системы - удаления из нее, по ходу процесса ортогональных преобразований, неинформативных (либо наименее информативных) строк и столбцов; эта очень важная идея подробно рассматривается во второй части работы;
I 24 ) использования так называемой "непараметрической регуляризации" (этот не самый удачный термин введен В. Н. Страховым, впервые предложившим эту идею); в рамках этой конструктивной идеи, в основном относящейся к системам с симметричными положительно полуопределенными и треугольными матрицами, осуществляется процедура уменьшения внедиагональных элементов с одновременным увеличением диагональных элементов; данная идея кратко описывается в следующем параграфе данного раздела статьи;
I 25 ) использования приема регуляризации разложения матрицы на треугольные множители; это одна из важнейших конструктивных идей, она рассматривается во второй части работы;
I 26 ) использования специального приема регуляризации систем с треугольными матрицами, так называемой "треугольной регуляризации"; эта идея также рассматривается во второй части работы;
I 27 ) использования приема ускорения сходимости последовательности приближенных решений; данная конструктивная идея рассматривается во второй части работы;
I 28 ) использования приема нахождения устойчивого приближенного решения системы большой размерности на основе построения устойчивого приближенного решения подсистем существенно меньшей размерности; эта исключительно важная конструктивная идея подробно рассматривается во второй части работы;
I 29 ) использования приближенных линейных аналитических аппроксимаций вектора неизвестных, в которых число параметров существенно меньше размерности искомого вектора; эта конструктивная идея также рассматривается во второй части работы.
Наконец, конструктивные идеи группы I 3 ) являются в максимальной степени отличными от тех, которые используются в классической теории линейных некорректных задач; эти идеи были предложены В. Н. Страховым и А. В. Страховым в ряде работ, выполненных в 1997-1998 гг., [см. Страхов, Страхов, 1998, 1999a, 1999b, 1999c, 1999d]. Это суть следующие идеи, детальное описание которых дается во второй части работы:
I 31 ) использования редукции исходной системы к системе с вектором правой части, содержащим всего одну ненулевую компоненту (первую или последнюю), при этом редуцирование в обязательном порядке включает ортогональное преобразование либо исходной, либо вспомогательной матрицы, на которую потом умножаются обе части исходной системы;
I 32 ) использования редукции исходной системы к последовательности двух уравнений с одним неизвестным; данная редукция также в существенном основывается на использовании ортогональных преобразований;
I 33 ) использование приема редукции исходной системы к одному уравнению с одним неизвестным; эта идея в сжатой форме изложена в п. 3-4 предыдущего раздела данной статьи, и из этого изложения ясно, что здесь также основную роль играют ортогональные преобразования;
I 34 ) использования итерационных процессов нового типа, основанного на корреляционных преобразованиях столбцов матрицы А;
I 35 ) использования итерационных процессов нового типа, основанных на ортогональных преобразованиях, изменяющих некоторое отношение эвклидовых норм парциальных векторов первого столбца матрицы.
Итак, общее число новых конструктивных идей класса А), используемых в рамках новой общей теории регуляризации систем линейных алгебраических уравнений с приближенно заданной правой частью (случай чисто аддитивной помехи) равно 20, из них только 6 имеют достаточно очевидную связь с конструктивными идеями классической теории регуляризации линейных некорректных задач. В следующей части работы будет приведено достаточно детальное описание 14 из этих идей.
4-4. Итак, приведем краткие описания трех новых конструктивных идей: I 12 ), I 16 ) и I 24 ) по первой классификации.
Конструктивная идея I 12 ) - использование расширенных регуляризованных систем первого рода. Ее суть в том, что система (22), возникающая в классическом вариационном методе регуляризации А. Н. Тихонова, может рассматриваться как первая трансформация Гаусса следующей системы:
![]() | (207) |
где
![]() | (208) |
Иначе говоря, система (22) порождается следующей задачей наименьших квадратов:
![]() | (209) |
- при фиксированном значении параметра a.
Из сказанного следует два вывода:
во-первых, вариационный метод А. Н. Тихонова действительно представляет собой реализацию некоторого варианта метода наименьших квадратов - для расширенной системы (207), которую естественно назвать расширенной регуляризованной системой 1-го рода;
во-вторых, решение системы (207) при заданном a > 0 может быть найдено большим числом методов (алгоритмов), как прямых, так и итерационных.
При нахождении решений систем (207) возможно использование различного рода ортогональных преобразований, приводящих ее к максимально простому виду. Читателю рекомендуется рассмотреть возникающие возможности самостоятельно.
Конструктивная идея I 16 ) - введения дополнительных параметров в целях использования тех или иных "законов сохранения" для возмущенных матриц.
Простейший пример реализации этой идеи: переход от уравнения (10) к уравнению
![]() | (210) |
Здесь
b, 0<b<1, суть
новый (дополнительный) параметр,
DA - диагональная матрица, элементы которой
i = aii
- диагональным элементам матрицы А. Ясно, что:
1) система (210) эквивалентна более простой, в вычислительном плане, системе
![]() | (211) |
2) возможно использовать следующие соотношения между характеристиками матриц A a,b и A:
![]() | (212) |
и
![]() | (213) |
а также некоторых других. Соотношения (212) и (213) и выражают "законы сохранения".
Ясно, что "законы сохранения" позволяют фактически сократить число параметров счета с двух (a, b) до одного - a или b ; при этом могут возникнуть некоторые дополнительные условия на допустимые значения параметров a и b.
Ясно, что подобного рода конструкции могут быть использованы и в случае уравнения (22); имеется в виду переход к уравнению
![]() | (214) |
а также и в других методах. Более подробное рассмотрение этих возможностей предоставляется читателю.
Конструктивная идея I 24 ) - идея использования "непараметрической регуляризации". (Как уже сказано выше, предложенный В. Н. Страховым термин "непараметрическая регуляризация" [Страхов, 1997f], которым подчеркивается отличие данной конструкции от классических, в котором вводимый параметр возникает при решении некоторой условной экстремальной задачи методом множителей Лагранжа, не является очень удачным; но он достаточно краток, уже экплуатируется и неясно, каким кратким термином его заменить.)
Отправная позиция идеи "непараметрической регуляризации" в случае систем
(1)-(2) с
A = AT 0 та же,
что и в методе
М. М. Лаврентьева - необходимо усилить диагональные элементы системы. Поэтому
в методе непараметрической регуляризации используются два
взаимодополняющих приема:
во-первых, уменьшения внедиагональных элементов;
во-вторых, усиления диагональных элементов.
В случае систем (2) с
A = AT 0 "непараметрическая
регуляризация" состоит в переходе к регуляризованной
системе
![]() | (215) |
где a>0 параметр, DA = diag aii,
![]() | (216) |
и Ab есть матрица с нулевой диагональю, элементы которой определены через внедиагональные элементы aij матрицы A и параметр b, 0<b<1:
![]() | (217) |
Ясно, что и в рамках данной конструкции возможно использование "законов сохранения":
![]() | (218) |
или
![]() | (219) |
позволяющие перейти от двух параметров счета (a, b) к одному - a или b, с возможным введением дополнительных ограничений на значения параметров.
Практически весьма важно, что описанная конструкция "непараметрической регуляризации" элементарным образом переносится на случай систем линейных уравнений (1) и (2) с треугольными матрицами A - верхней или нижней, при aii>0.
Действительно, соотношения (217) и (218)-(219) и в этом случае (в (217) следует принимать i - j>0 ) могут быть оставлены в силе. При этом мотивация идеи непараметрической регуляризации в случае треугольной A основывается на хорошо известной оценке эвклидовой нормы обратной матрицы, см. [Лоусон, Хенсон, 1986], стр. 197. В случае верхней треугольной A эта оценка имеет вид:
![]() | (220) |
где mi выражаются соотношениями
![]() | (221) |
причем
![]() | (222) |
4-5. В 4-3 данного раздела была приведена первая из трех возможных классификаций 20 новых конструктивных идей. В настоящем, заключительном, параграфе раздела кратко описываются две другие классификации этих 20 конструктивных идей.
Вторая классификация (II). Напомним, что это классификация по степени перспективности (эффективности) конструктивных идей. Она включает подразделение идей также на три группы:
- II 1 ) наиболее перспективных идей;
- II 2 ) перспективных идей;
- II 3 ) наименее перспективных идей.
К группе II 1 ) относятся идеи (по первой классификации):
I 13 ), I 21 ), I 22 ), I 25 ), I 33 ), I 35 ).
К группе II 2 ) относятся идеи:
I 12 ), I 15 ), I 23 ), I 24 ), I 28 ), I 29 ), I 31 ), I 32 ), I 34 ).
Наконец, к группе II 3 ) относятся идеи:
I 11 ), I 14 ), I 16 ), I 26 ), I 27 ).
Третья классификация (III) (основанная на том, используются в реализации этой идеи ортогональные преобразования, или нет). Она, естественно, включает подразделение идей на две группы:
III 1 ) ортогональные преобразования используются;
III 2 ) ортогональные преобразования не используются.
К группе III 1 ) относятся идеи (по первой классификации):
I 14 ), I 21 ), I 22 ), I 23 ), I 31 ), I 32 ), I 33 ), I 34 ), I 35 ).
К группе III 2 ) относятся идеи:
I11 ), I12 ), I13 ), I15 ), I16 ), I24 ), I25 ), I26 ), I27 ), I28 ), I29 ).
Читатель безусловно обратит внимание на тот факт, что в группе III1 ) число наиболее перспективных и перспективных идей больше, чем в группе III2 ), хотя их общие численности одинаковы. Здесь четко просматривается тот уже упоминавшийся факт, что в новой теории регуляризации систем линейных алгебраических уравнений ортогональные преобразования играют существенно большую роль, чем в классической.
Главная цель настоящей статьи (первой части работы) состоит в том, чтобы изложить основы классической теории регуляризации систем линейных алгебраических уравнений с приближенными данными - с одной стороны, и основы новой теории регуляризации линейных систем (созданной трудами В. Н. Страхова, частично в соавторстве, см. [Страхов, 1990a, 1990b, 1991a, 1991b, 1991c, 1992a, 1992b, 1997c, 1997d, 1997e, 1997f, 1997g, 1997h, 1998d, 1998e; Страхов, Страхов, 1998, 1999a, 1999b, 1999c, 1999d; Страхов, Тетерин, 1991a, 1991b, 1991c, 1993; Strakhov et al., 1995]) - с другой, и продемонстрировать тот факт, что новая теория существенно более адекватна реальной геофизической практике, что она гибче и богаче классической теории. Вместе с тем материал данной статьи является сугубо вводным, только в следующих частях будет в полном объеме продемонстрирована суть основных новых методов (алгоритмов) построения пробных и допустимых решений, а также важнейшая, с точки зрения гравиметрии и магнитометрии, общая идея использования аппроксимационного подхода в целом, и конкретно - методов редуцирования аппроксимационных постановок к нахождению устойчивых приближенных решений систем линейных алгебраических уравнений с приближенными данными, и к демонстрации эффективности аппроксимационного подхода на модельных и практических примерах.