Введение в вычислительную физику - Федоренко Р.П.
ISBN 5-7417-0002-0
Скачать (прямая ссылка):
I — максимальное и минимальное собственные числа А.
Расстояние \\xj — х*|| убывает, как q>, где q = (L — 1)/{L + I). При малых значениях т] имеем q « 1 — 2 т]. Чем меньше т], тем медленнее осуществляется поиск минимума. Число г] имеет простую геометрическую интерпретацию: линии уровня квадратичной функции (при А > 0) суть «эллипсоиды», отношение экстремальных полуосей которых как раз и есть т]. Таким образом, «трудная» функция f°(x) — это функция, график которой похож на «овраг» с крутыми «склонами» и очень длинным пологим «дном», вдоль которого нужно очень долго идти до точки минимума.
Первые шаги процессов поиска приводят к быстрому спуску со «склона» на дно оврага, после чего начинается длительное «зигзагообразное» движение вдоль «дна» с очень медленным темпом убывания /° за шаг. При г) = 1 (линии уровня — сферы) метод спуска по
414
ПРИБЛИЖЕННЫЕ МЕТОДЫ ВЫЧИСЛИТЕЛЬНОЙ ФИЗИКИ
[Ч. II
градиенту приводит к минимуму за один шаг. Скорость сходимости (число q) покоординатного спуска в этом случае легко оценить. Предоставим это поучительное упражнение читателю (здесь интересна зависимость q от размерности пространства).
Несколько сложнее оценивается математическое ожидание убывания /° (при ті = 1) за один шаг спуска в случайном направлении. Здесь существенна размерность, причем сказывается следующее неприятное обстоятельство: почти вся площадь сферы в Rn сосредоточена в узком поясе около экватора (это свойство сфер проявляется тем резче, чем больше N). Поэтому «почти любое» случайное направление «почти ортогонально» направлению градиента, т.е. направлению в точку минимума такой простой функции, как ^ х\. (Предоставим читателю эти вычисления. Они не составят труда для того, кто знает формулу площади многомерной сферы.)
Эффективность процесса поиска минимума можно существенно повысить линейным преобразованием пространства, т.е. используя замену х = By. Легко понять, какой должна быть матрица В: квадратичная форма после замены переменных перейдет в (ABy, By) = (В*ABy, у). Чтобы в переменных у получить просто сумму квадратов, следует найти В из уравнения В*AB = Е, например. В качестве В можно взять А~112. Это, конечно, рецепт чисто теоретический. Он только указывает направление, в котором следует искать В: ведь можно брать матрицы В, близкие к идеальной, но более доступные на практике. Приведенные выше соображения можно трактовать несколько иначе. В линеаризованной задаче ограничение Ьх можно сформулировать в какой-то другой метрике, например (В дх, бх) =S є2 с положительной самосопряженной матрицей В. В этом случае методом Лагранжа найдем 6х zz B~lf°(xJ).
Квадратичная модель подсказывает идеальный выбор В: это должна быть матрица, близкая к гессиану А. Практическая реализация такой подсказки возможна двумя способами. Самый очевидный — использовать метод, основанный на квадратичной аппроксимации:
f°(x + дх) & /°(х) + /°дх + 0.5(/°* дх, дх).
В очередной точке Xj следует ВЫЧИСЛИТЬ Z0x(Xi) и гессиан Z0xx(Xi), решить задачу минимизации квадратичной функции. Например, если размерность пространства N не очень велика, можно решить систему линейных уравнений Z0(Xi) + Z0x(Xi) дх = 0. Такой алгоритм иногда называют методом Ньютона, так как его можно трактовать как решение системы нелинейных уравнений /°(х) = 0.
Применение вышеприведенной схемы вычислений сталкивается с двумя препятствиями. В начальной точке х0 гессиан Z0xx может не
§26]
ПОИСК МИНИМУМА
415
быть положительно-определенным. Тогда решение задачи минимизации квадратичной формы (если мы ее действительно минимизируем) уводит нас в бесконечность. Если же решается система линейных уравнений (необходимое условие экстремума квадратичной формы), то мы уже не отличаем минимума от максимума и от другого типа стационарных точек. Поэтому такая техника применяется после некоторого числа шагов спуска по градиенту, которые проходят достаточно эффективно и выводят точку Xі в область положительности гессиана.
Более серьезным препятствием является необходимость вычисления вторых производных. В пространствах не очень малой размерности это очень дорогая операция. В семидесятых годах был найден удачный компромисс, приведший к созданию так называемых ква-зиньютоновских процедур. Они основаны на следующем соображении. В методе спуска по градиенту, располагая значениями градиента в разных точках fx(Xj), мы получаем некоторую ограниченную на каждом шаге информацию и о f хх. В самом деле, если смещение \\xi + i — XiW не очень велико,
Л+ ~ /*00 ^ fXX(xJ + 1 — xJ)’
т.е. если пренебречь величинами 0(||х/+1 — ху||2), мы знаем величины N линейных комбинаций из элементов N^-N матрицы /хх. Накапливая такую информацию на нескольких подряд идущих шагах, можно с какой-то точностью восстановить и гессиан.
Практическая реализация вышеизложенных соображений приводит к процессу следующего типа. Кроме точки х1, имеем еще и положительно-определенную самосопряженную матрицу HL Функцию f (Xі + 6jc) аппроксимируем разложением
f(xj + 6х) sc f(xj) + fx(xJ) 6х + 0.5(Wbx, 6х).
