5.7. Метод выбора направления

Предположим, что мы располагаем матрицей А, которая является матрицей Гессе или некоторым ее приближением. Нам необходимо получить положительно-определенную (или по крайней мере полуопределенную) матрицу в некотором смысле близкую к с тем, чтобы было бы допустимым направлением. Кроме того, нам хотелось бы разумно выбрать направление даже в случае, когда вырождена или близка к этому.

В основу метода выбора направления положена идея использования различных формул для расчета разных компоненту (в соответствующим образом выбранной системе координат). В работе Дженриха и Сэмпсона [115] используется исходная система координат и приравниваются к нулю те компоненты которые, как предполагается, в данный момент не оказывают влияния на Этот способ особенно целесообразно применять в сочетании с методом Гаусса. Более подробно Он будет рассмотрен в разделе Обычно это приводит к такому преобразованию координат, которое позволяет устранить «взаимодействие» между параметрами, т. е. в такой системе координат матрица Гессе становится диагональной, а эффект влияния на одной из компонент оказывается приближенно независимым от значений всех остальных компонент. Для обозначения этого метода Фарисс и Лоу [67] предложили термин вращательная дискриминация (rotational discrimination).

Для получения подходящего преобразования координат можно пользоваться спектральным разложением матрицы (см. приложение А.5). Высокая точность расчетов достигается с помощью шкалированных разложений. Этот способ и будет применяться далее. Пусть обратное шкалированное разложение задается уравнением т. е.

Тогда уравнение может быть записано — в виде

Пусть При этом мы имеем

Но и потому или в матричной записи

Следовательно, уравнение может быть переписано в системе координат 0 как

или, поскольку матрица диагональна с элементами

Решением являются значения

где

Теперь мы можем попробовать применить метод выбора направления при нарушении равенства для некоторых компонент. Прежде всего допустимость шага гарантируется лишь в случае, когда все положительны. Далее в соответствии со способом, предложенным Гринштадтом [93], мы заменим отрицательные собственные значения их абсолютными величинами. Заменим равенство на

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

Остановимся на том, как надо действовать, когда собственные значения оказываются нулевыми или очень малыми. Вычисленные собственные значения почти никогда не бывают точно нулевыми, поэтому нет необходимости специально рассматривать этот случай. Если очень мало, например то мы оказываемся перед дилеммой: с одной стороны, в соответствии с методом Ньютона именно направление, соответствующее этому собственному значению, наиболее эффективно приводит к минимуму при условии, что целевая функция является квадратической; с другой стороны, нам известно, что целевая

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

(а) Метод Ньютона-Гринштадта

где малая константа.

Рис. 5.1. Гребни целевой функции

(б) Модифицированный метод Фарисса — Лоу

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

(в) «Нейтральный» метод

где и константы.

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

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

Возвращаясь к выбору допустим, что это диагональная матрица с элементами Тогда из равенства следует

Заменяя в этом выражении в соответствии с их определениями, после умножения на получим

поэтому это искомая «почти обратная» матрица по отношению к