11.2. РЕЛАКСАЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ СИСТЕМ УРАВНЕНИЙ И НЕРАВЕНСТВ

В данном разделе дано математическое обоснование алгебраических алгоритмов реконструкции, которое будет взято за основу при решении задачи нахождения вектора, удовлетворяющего заданной системе линейных неравенств. Другими словами, необходимо найти У-мерный вектор для которого справедливы неравенства

где — заданные -мерные векторы, заданные вещественные числа. Неравенства (11.5) взяты из соотношения (6.42).

Из сказанного можно сделать вывод, что векторы имеют по крайней мере одну ненулевую компоненту. Физический смысл этого предположения состоит в том, что во внимание не принимаются те измерения, в которых не дает вклада ни один из элизов. Причина введения данного предположения состоит в том, что мы стремимся избежать рассмотрения частных случаев, когда аналогично тому, что было сделано в формуле (11.2).

Введем некоторое множество векторов и величину Для любого интервале имеем

и

Другими словами, множество векторов, удовлетворяющих неравенствам из общего числа неравенств в выражении (11.5), а множество векторов, полностью удовлетворяющих всем неравенствам. Задача при этом заключается в нахождении одного элемента множества

Говоря более точно, нам необходимо найти алгоритм, позволяющий по заданным значениям и находить из множества Здесь предполагается одна из разновидностей алгебраического алгоритма, в которой определяются последовательность функций вида

где — вещественное число, которое в контексте данной книги названо релаксационным параметром.

Рассмотрим следующую процедуру, которую мы назовем релаксационным методом решения системы неравенств (или просто релаксационным методом для неравенств), а именно

где функции определяются соотношением (11.8), Если релаксационный параметр удовлетворяет довольно слабому условию вида

для всех к, то релаксационный метод для неравенств дает последовательность величин которые сходятся к значению вектора во множестве при единственном условии, что множество непустое. Доказательство этого положения приведено в разд. 16.8.

Теперь дадим геометрическую интерпретацию релаксационного метода для неравенств и, в частности, выясним геометрический смысл релаксационных параметров. Предположим, что

Рис. 11.1. Рисунок, демонстрирующий применение релаксационного метода для частного случая, когда для всех k). При этом значения выбираются в соответствии с выражением (11.12), а — в соответствии с выражением (11.13). (Рисунок заимствован из работы (71) с разрешения авторов. Copyright 1976, Pergamon Press, Ltd.)

есть множество векторов для которых неравенство переходит в точное равенство. Заметим, что является подмножеством множества Каждая из величин в математике называется гиперплоскостью. При гиперплоскость переходит в обыкновенную плоскость в обычном трехмерном пространстве, а при в прямую линию на плоскости. Указанный двумерный случай иллюстрируется рис. 11.1. Здесь мы имеем две гиперплоскости и для которых

и

Установим следующий очевидный геометрический факт: вектор (представленный в виде линии, соединяющей на плоскости начало координат с точкой перпендикулярен линии Этот вывод можно обобщить на случай пространств произвольной размерности. Читатель, знакомый с основами аналитической геометрии, легко может убедиться в этом из соотношения (11.11).

Поскольку в релаксационном методе для неравенств, описываемом выражением (11.9), роль параметра в формуле (11.8) выполняет то оказывается, что если итерации отличаются друг от друга, то разность (которая умножается на представляет собой вектор, перпендикулярный гиперплоскости

Дадим теперь геометрическую интерпретацию величинам . В двумерном случае, очевидно, представляет собой множество точек, лежащих по одну сторюну от линии а также на ней самой. Например, на рис. полуплоскости, включающие в себя и начало координат. Их перекрывающаяся часть заштрихована на рис. 11.1. Подобное геометрическое представление также достаточно общо, и поэтому можно говорить о том, что полуплоскость, которая состоит из множества точек, лежащих по одну сторону от гиперплоскости а также на ней самой. Величина как это определено соотношением (11.7), задается пересечением двух полуплоскостей.

В релаксационном методе для неравенств, как это следует из выражений (11.8) и (11.9), оценка не меняется на итерации (т.е. ), если принадлежит полуплоскости Если не принадлежит полуплоскости то оценка «перемещается» перпендикулярно граничной полуплоскости (т.е. отрезок перпендикулярен а степень ее «перемещения» зависит от величины параметра

Если то в этом случае, исходя из соображений, аналогичных учитываемым в соотношении (11.3), можно показать, что т.е. значение лежит на гиперплоскости Достаточно прюсто можно доказать и другие положения. На итерации в релаксационном методе для неравенств при не принадлежащем полуплоскости перемещение оценки от до происходит вдоль перпендикуляра, опущенного на гиперплоскость и обладает следующими геометрическими свойствами :

а) если то оценка удаляется от ;

б) если то перемещение отсутствует;

в) если то перемещение оценки происходит в направлении на гиперплоскость но не достигает ее;

г) если то перемещение происходит до точного совпадения оценки с ;

д) если то перемещение продолжается и после достижения оценкой гиперплоскости однако оценка оказывается ближе к чем предыдущая оценка ;

е) если то оценка является зеркальным отображением относительно гиперплоскости ;

ж) если то располагается по другую сторону от гиперплоскости и на большем расстоянии от нее, нежели оценка

Для дальнейшего анализа релаксационного метода для неравенств вновь обратимся к рис. 11.1, на котором представлены два неравенства (т.е. ), а также векторы и, и и скаляры определенные выражениями (11.12) и (11.13) соответственно. Предположим, что для всех к параметр Необходимо также выбрать вектор начальных значений, который примем равным

тогда легко проверить, что

Поскольку оценка принадлежит одновременно двум гиперплоскостям все остальные величины при будут одинаковыми и равными Следовательно, метод обеспечивает сходимость для лежащих на гиперплоскости

Сходимость, имевшая место в предыдущем примере, называется конечной сходимостью, поскольку оценка остается постоянной после первых нескольких итераций. Однако это не означает, что релаксационный метод для неравенств обеспечивает конечную сходимость при выборе величины X в соответствии с неравенством (11.10).

Теперь перейдем к изучению систем уравнений. Предположим, что заданы У-мерные векторы и вещественные числа Пусть также

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

то

и аналогично тому, как определяется формулой (11.7), так и величина определяется (11.17) при условии, что задано соотношениями (11.18) и (11.19). Следовательно, релаксационный метод можно применить к системе неравенств для нахождения элементов множества Здесь мы предполагаем, что при .

Заметим, однако, что

где граничная гиперплоскость полуплоскости как это определено равенством (11.11). Следовательно, суммарный эффект итераций состоит в перемещении (если оно вообще имеется) в направлении, перпендикулярном гиперплоскости Эти две итерации можно объединить в одну операцию и получить следующий алгоритм для релаксационного метода решения систем уравнений:

Из аналчза результатов, полученных при использовании релаксационного метода для неравенств, легко видеть, что если для всех значений к имеем

а удовлетворяет соотношению (11.10), то релаксационный метод для равенств дает последовательность оценок которая сходится к вектору множества при условии, что непустое.

Алгоритм, описываемый выражениями (11.1) и (11.2), является частным случаем релаксационного метода для равенств при и любом k. Этот случай иллюстрируется рис. 11.1. Полагая, что определяются значениями (11.12) и (11.13), можно показать, что если в качестве начального значения взято согласно (11.14), то мы получим оценки соответствующие значениям (11.15). С этой точки зрения последовательность, получаемая с помощью релаксационного метода для равенств, отличается от последовательности, полученной ранее обсуждавшимся релаксационным методом для неравенств. Это обусловлено тем, что оценка не принадлежит множеству и поэтому в дальнейшем необходимо брать значения ближе и ближе к элементу множества который в данном случае определяется единственной точкой пересечения двух линий С помощью данной геометрической модели можно прийти к выводу, что последовательность векторов получается путем опускания перпендикуляров либо на линию либо на (рис. 11.1).

В общем случае множество может содержать более чем один элемент. При несколько более тщательном выборе значения можно получить

гарантию того, что релаксационный метод для равенств будет давать сходимость именно к тому элементу множества который удовлетворяет критерию оптимальности, а именно критерию минимума нормы (разд. 6.4). Чтобы сделать это, введем множество векторов, представляющее собой множество всевозможных линейных комбинаций из

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

Согласно соотношению (6.37), .

При этом элемент с минимальной нормой на множестве . В разд. 6.4 уже обсуждался вопрос о том, почему выбор элемента с минимальной нормой считается полезным при реконструкции изображений.

Из условий (11.22) видно, что если выбрано элементом множества то и величина также будет элементом множества при всех k. Это приводит к тому, что, согласно основным положениям линейной алгебры, предел последовательности оценок также принадлежит Поскольку предельное значение также принадлежит множеству (благодаря сходимости релаксационного метода для равенств), то и само значение лежит в Следовательно, как следует из теоремы для минимума нормы, значение является элементом с минимальной нормой в

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

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