Методы регуляризации

НОРМАЛЬНАЯ СИСТЕМА

В практических задачах часто бывает необходимо удовлетворить некоторому числу противоречивых требований. Если задача сводится к системе линейных уравнений, то такая система, вообще говоря, несовместна. В этом случае задачу можно решить путем выбора некоторого компромисса – все требования могут быть удовлетворены не полностью, а лишь до некоторой степени.

Рассмотрим систему с матрицей 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 возникают большие проблемы в получении решения системы.

Дата добавления: 2014-01-04