МЕТОДЫ РЕГУЛЯРИЗАЦИИ
НОРМАЛЬНАЯ СИСТЕМА
В практических задачах часто бывает необходимо удовлетворить некоторому числу противоречивых требований. Если задача сводится к системе линейных уравнений, то такая система, вообще говоря, несовместна. В этом случае задачу можно решить путем выбора некоторого компромисса – все требования могут быть удовлетворены не полностью, а лишь до некоторой степени.
Рассмотрим систему с матрицей A для произвольных размеров m i n, то есть никаких условий на m и n не накладывается.
Невязкой называется вектор, который дает значение вектора X при подстановке в систему
R = B - A X.
Решение системы - это вектор X, дающий нулевую невязку.
Если система несовместна, то обычно стараются найти такой X, который дает невязку с минимальной нормой. Под нормой вектора R понимается его евклидова норма
Если такой X существует, то его считают обобщенным решением системы. Очевидно, если система совместна, ее решение будет также и обобщенным решением.
Таким образом, рассматривается задача о минимуме нормы невязки
|| R ||2 = (B - A X)T(B - A X).
Решение указанной задачи приводит к уравнению
A TA X = A TB,
где значком Т отмечена транспонированная матрица.
Справедливо следующее утверждение.
Предложение [7]. Нормальная система имеет единственное решение тогда и только тогда, когда система A Y = 0 имеет только нулевое решение, то есть столбцы (строки) матрицы линейно независимы.
Если решение нормальной системы неединственное, то выбирается решение с минимальной нормой.
Определение. Нормальным псевдорешением системы (24) называется вектор X0 с минимальной нормой среди всех векторов X, дающих минимальную по норме невязку при подстановке в эту систему.
Имеет место
Теорема [7]. Каждая система линейных уравнений имеет одно и только одно нормальное псевдорешение.
Предыдущие рассмотрения указывают необходимость выделения класса задач, для которых малые возмущения данных задач приводят к малому изменению решения. Класс таких задач называется корректным.
Приведем понятие корректности задачи по Адамару (Жак Адамар (1865-1963) – французский математик).
Задача называется корректной, если выполнены следующие три требования:
1) ее решение существует при любых входных данных задачи;
2) это решение единственно;
3) решение устойчиво по отношению к малым возмущениям входных данных.
В том случае, когда хотя бы одно из этих требований не выполнено, задача называется некорректной. Идеи Адамара были развиты И.Г. Петровским (Иван Георгиевич Петровский (1901-1973) – российский математик).
Следует заметить, что класс корректных задач по Адамару оказался слишком узок. А.Н. Тихонов (Андрей Николаевич Тихонов (1906-1993) – российский математик) расширил понятие корректности задачи за счет сужения множества ее решений. Определение корректности по Тихонову полностью повторяет определение Адамара на заданном множестве M, которое считается множеством компактности решений. В конечномерном пространстве компактность означает ограниченность решения. Существуют и другие определения корректности задачи.
К настоящему времени разработана теория решения многих классов некорректных задач. Методы решения таких задач (методы регуляризации) довольно сложны. В рамках линейных систем метод регуляризации А.Н. Тихонова приводит к решению следующей линейной системы:
(A TA + dE )X = A TB, d > 0, где d - параметр регуляризации, E - единичная матрица.
Выбору параметра регуляризации посвящено большое число работ. Ясно, что, чем меньше d, тем ближе полученное решение к обобщенному решению системы, однако это ведет к большим трудностям в численном решении системы. Выбор больших d приводит к значительным отклонениям от реального решения. Выбор необходимого d зависит от заданной точности решения и требований устойчивости вычислительных алгоритмов.
Несмотря на расширение класса корректных систем по А.Н. Тихонову, можно указать примеры линейных систем, для которых метод не приводит к успеху. Таковыми являются, например, матрица Гильберта [3] и задача Годунова [9]. К матрице Гильберта приводит задача полиномиальной регрессии.
Для этой системы известно решение
Число обусловленности матрицы A для n = 25 равно 0,69 " 1011, то есть система является плохо обусловленной.
Наилучшие результаты по точности решения системы дает метод Гаусса для n = 33. Метод Гаусса для систем решает исходную систему для n = 10 с приемлемой точностью. Для n > 33 возникают большие проблемы в получении решения системы.