Контексты подхода Гилла и Мюррея

Ниже приводится детальное описание всех операций, выполняемых по ходу построения модифицированной факторизации Холесского с перестановками, дана наиболее эффективная схема организации расчетов [5]. Все фигурирующие в ней величины при реализации на ЭВМ могут размещаться в памяти, первоначально выделяемой для записи исходной матрицы . При этом коэффициенты рассчитываемых факторов занимают места ее использованных элементов. В процессе вычисления - го столбца матрицы участвуют вспомогательные величины . Их также естественно заносить в массив, выделенный для . Точнее говоря, позиции использованных элементов сначала отводятся под запись чисел , а затем, по мере того как необходимость в каких-то числах отпадает, вместо них записываются соответствующие коэффициенты фактора .

Шаг 0. (Расчет порога для элементов). Вычислить , где , а числа и суть максимальные значения модулей диагонального и недиагонального элементов .

Шаг 1. (Инициализация). Присвоить индексу столбца значение 1. Положить .

Шаг 2. (Перестановка строк и столбцов). Найти индекс , такой, что . Поменять местами все данные, отвечающие столбцам матрицы с номерами и , а затем

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

Шаг 3. (Поиск максимальный по модулю величины ). Вычислить для и найти (если , взять ).

Шаг 4. (Расчет - го диагонального элемента фактора ). Вычислить

и поправку . Если , вычисления прекратить.

Шаг 5. (Расчет - ой строки ). Вычислить для . Для пересчитать диагональные элементы по формуле . Присвоить значение и вернуться к шагу 2.

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

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

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

По смыслу отражает точность, с которой удаётся вычислять значения . Что же касается параметра , то о его величине в общем случае ничего конкретного сказать нельзя.