- •Информодинамический подход к разработке алгоритмов, реализация и сравнение эффективности Зеленков г.А., Хакимова а.Б.
- •1. Роль контекста в построении алгоритмов
- •1.1. Контексты ньютоновских методов с регулировкой шага
- •1.2. Контексты подхода Гилла и Мюррея
- •1.3. Взаимосвязь контекстов подхода Гилла и Мюррея
- •2. Инженерия построения алгоритмов
- •2.1. Формирование строки сообщения о состоянии процесса построения алгоритма
- •2.2. Выход из завершенного контекста подхода Гилла и Мюррея
- •2.3. Стратегии задания направления спуска
- •3. Тестовые задачи и сравнительная оценка алгоритмов
2.1. Формирование строки сообщения о состоянии процесса построения алгоритма
Строка сообщения должна отражать основные моменты построения и способ задания направления спуска. Это можно сделать, например, так:
, , , , ,
Можно
рассуждать и по-другому. Просканируем
строку сообщения слева направо, кратко
озвучивая основные контексты фреймов,
входящих в состав этой строки. Фрейм
определяет как уравнение
для поиска направления спуска
,
так и связь положительно определённой
матрицы
с исходной матрицей
.
Фрейм
«озвучивает лицо алгоритма», поскольку
изменение фрейма приведёт к изменению
способа задания направления спуска
.
Фрейм
,
определяет алгоритм решения системы
уравнений
.
Фрейм
озвучивает алгоритм выбора длины шага
.
Фрейм
акцентирует внимание на стратегии
масштабировании шагов при спуске.
Сокращение строки приведёт к перегрузке фреймов оставшихся частей строки, а увеличение – к сканированию и анализу несущественных частей алгоритма, например, фрейма . Для улучшения зрительного восприятия строки сообщения можно использовать разделители, аббревиатуры и рисунки.
2.2. Выход из завершенного контекста подхода Гилла и Мюррея
Инструментами для изменения контекста строки сообщения являются контекстный анализ, накопление и сопоставление различных вариантов интеграции сообщений и совокупностей сообщений. Начнём с контекстного анализа подхода Гилла и Мюррея следующим образом. Направление спуска , в конечном счете, вычисляется как решение системы
(2.2.1)
,
где
,
а
есть решение системы
.
Величина элементов
зависит от способа задания направления
спуска. Поэтому, можно предположить,
что для численной устойчивости расчёта
элементов
,
достаточно потребовать изменения
способа задания
так, чтобы для всех
и некоторых заданных положительных
,
и
выполнялись неравенства
(2.2.2)
.
Это может стать ключом к решению проблемы масштабирования шагов при спуске, но такое предположение ошибочно - подход линейной алгебры к вычислению направления спуска исключает расчёт элементов вектора по ходу построения модифицированного разложения Холесского. Нужен альтернативный подход, который озвучим так. Равенства
(2.2.3)
достаточно, чтобы определить их элементы. В скалярной форме это равенство выглядит следующим образом
(2.2.4)
,
отсюда,
полагая
,
построим соотношения
(2.2.5)
,
для
расчёта элементов
,
.
Построение
факторов Холесского математически
эквивалентно применению метода исключения
Гаусса к системе уравнений
в прямом порядке, при этом техника
исключения Гаусса позволяет получить
соотношение
(2.2.6)
для расчёта элементов вектора и систему уравнений
(2.2.7)
для
вычисления направления спуска
.
Интеграция техники исключения Гаусса
и факторизации Холесского приводит к
соотношениям (2.2.5), (2.2.6), которые с помощью
элементарных арифметических операций
позволяют вычислить элементы
по ходу построения факторов Холесского.
Порядок расчёта удобно пояснить следующей
диаграммой
,
а процесс построения алгоритма озвучить
следующим образом:
, , , , ,
, , , ,
Сканируя сообщения слева направо и сверху вниз, определим изменение как результат замены фрейма , фреймом , основной контекст которого определяет соотношение для расчёта элементов вектора по ходу построения факторов Холесского. Это означает, что направление процесса разработки указывает на изменение стратегии задания направления спуска, а, следовательно, и на выход из завершённого контекста подхода Гилла и Мюррея.
