Применение методов переменной метрики для решения разреженных систем линейных алгебраических уравнений

Размещено на http://www.allbest.ru/

УДК 519.612+531.01

Применение методов переменной метрики для решения разреженных систем линейных алгебраических уравнений

В.Н. Иванов

Пермский государственный национальный исследовательский университет

Россия, 614990, Пермь, ул. Букирева, 15

precol@psu.ru; (342) 2-396-560



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

Ключевые слова: системы линейных алгебраических уравнений; итерационные методы; методы переменной метрики; SR1-формула; механические системы; уравнения движения; численное интегрирование.

разреженный линейный алгебраический сходимость



Application of the variable metric methods for solving the sparse linear algebraic systems

V. N. Ivanov

Perm State University, Russia, 614990, Perm, Bukirev st., 15

precol@psu.ru; (342) 239-65-60

The problem of solving sparse positive definite systems of linear algebraic equations with slowly varying coefficients is considered. The inverse iteration algorithm based on the Symmetric Rank-one formula of system matrix updating is used. Both conditions of local and global convergence of algorithm are reduced. Basic properties of algorithm are considered. Comparative efficiency of the method is shown by test examples.

Key words: systems of linear algebraic equation; iteration methods; variable metric methods; SR1-formula; mechanical systems; equations of motion; numerical integration.



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

Известно, что математическая модель или система уравнений движения любой связки твердых тел является системой линейных алгебраических уравнений (СЛАУ) относительно различных групп переменных: обобщенных или декартовых ускорений тел системы, множителей Лагранжа, реакций связей, импульсов. Матрица системы уравнений в общем случае зависит от обобщенных координат и является переменной во времени. На каждом шаге численного интегрирования необходимо приводить уравнения движения к явному виду, т.е. разрешать относительно указанных групп переменных. Это требует определенных вычислительных затрат, объем которых зависит от выбранного метода решения СЛАУ и плотности заполнения матрицы системы.

Обычно при малой величине шага интегрирования изменения элементов матрицы системы уравнений движения малы. Поэтому снижения трудозатрат можно добиться, если для решения использовать методы, основанные на итерационном уточнении малых возмущений в матрице системы. При этом методы ускорения расчетов должны быть различными для различных форм уравнений движения [1, 2]. Так, для уравнений движения в виде уравнений Лагранжа II рода с плотно заполненной матрицей системы можно добиться выигрыша во времени счета, если строить итерационные приближения для обратной матрицы системы. Для математических моделей в виде общих уравнений динамики или уравнений Лагранжа I рода, имеющих разреженную структуру, эффективнее оказываются алгоритмы, в которых происходит итерационное уточнение самой матрицы системы.

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

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

Постановка задачи

Задачу решения уравнений движения механических систем относительно ускорений, реакций связей, импульсов и множителей Лагранжа в текущий момент времени , где h - малый шаг численного интегрирования, с использованием накопленной информации о системе в предыдущий момент времени можно в терминах СЛАУ сформулировать следующим образом.

Пусть задана система n линейных алгебраических уравнений

(1)

где , , , - известные симметричные и положительно определенные матрицы n-го порядка, b=b0+ - известный вектор-столбец правых частей в n-мерном евклидовом пространстве, , - вектор-столбец неизвестных, - малый параметр, , . Кроме того, будем считать, что матрица A может быть разрежена, матрица возмущений непропорциональна матрице , т.е. не существует множителя такого, что .

Под нормой матрицы понимаем 2_норму в . Таким образом,

.

Требуется найти приближенное решение системы уравнений (1), если известна матрица или обратная матрица . Приближение к решению рассматриваем в среднеквадратическом смысле, т.е. считаем, что в точке выполняется неравенство

где - допустимое абсолютное отклонение.

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

Метод решения

Сначала представим обратный итерационный алгоритм, в котором уточняется матрица и напомним его свойства. Теоретическое обоснование предлагаемого численного метода дано в работах [3, 4].

Введем следующие обозначения:

- вектор невязки системы уравнений в точке ;

- вектор, указывающий направление, в котором происходит улучшение решения при перемещении из точки ;

k - номер итерации.

Обратный итерационный алгоритм:

1:

.

2:

,

, (2)

3:

Для обратного итерационного метода (2) в [1] доказаны следующие свойства:

1. Метод сходится за конечное число итераций. В общем случае спуск в точку происходит за итерацию, являющуюся решением системы уравнений (1): и .

2. Оказывается, что если матрица возмущений имеет ранг меньше n, то описываемый итерационный метод сойдется меньше, чем за n итераций. В случае, когда матрица возмущений имеет ранг r, метод сходится к точному решению за итерацию.

3. Если

, (3)

то алгоритм (2) обеспечивает выполнение следующих свойств (здесь = - число обусловленности матрицы ):

- - последовательность положительно определенных матриц;

- последовательности , и монотонно убывают.

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

4. Все направления поиска и векторы , линейно независимы.

5. Матрицы удовлетворяют квазиньютоновским условиям

. (4)

6. Векторы , не сопряжены с векторами , но удовлетворяют условию А-сопряженности с векторами , , т.е.

, , . (5)



7. Для сходимости метода достаточно, чтобы шаг интегрирования удовлетворял неравенству .

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

Приведенные в [3] результаты вычислительных экспериментов на реальных динамических задачах показывают, что метод (2) позволяет сохранить квадратичный закон роста трудоемкости моделирования в зависимости от роста размерности задачи. Обратный итерационный алгоритм (2) можно применять для тех механических систем, для которых более эффективными оказываются уравнения движения, спроектированные на подпространства обобщенных координат (типа Лагранжа второго рода), с достаточно плотно заполненной матрицей системы.

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

Покажем, каким образом можно модифицировать обратный итерационный алгоритм (2), чтобы он был эффективен для линейных систем с разряженной матрицей. Для этого сделаем несколько предварительных замечаний.

Формулы (2) пересчета матриц являются частным случаем симметричной формулы ранга 1 (Symmetric Rank-one formula, или SR1-formula) уточнения обратной матрицы Гессе в задаче минимизации функций, близких к квадратичным, или решения систем нелинейных уравнений с симметричной положительно определенной матрицей Якоби [5-8]:

. (6)

Формулы (2) получаются из (6), если взять и поменять последовательность операций вычисления и . Если , то метод минимизации квадратичных функций, основанный на SR1-формуле (6), в [9] назван методом Пауэлла. Классификацию различных методов переменной метрики и место среди них SR1_формулы (6) можно найти в [6, 8, 10].

Кроме того, в теории численных методов минимизации квадратичных функций установлено [5, 6, 8, 11], что любой метод переменной метрики может быть написан как для обратной матрицы , так и для прямой исходной матрицы системы (матрицы Гессе или Якоби). Алгоритм пересчета матрицы приближений к прямой матрице можно получить из формул (6) заменой: , , :

. (7)

Если положить , то формулу (7) можно привести к более простому виду:

.

Заметим, что численные методы, основанные на прямой SR1-формуле (7), относятся к более общему классу методов Бройдена [5, 7, 12, 13].

В численных методах минимизации функций или решения систем нелинейных уравнений обычно используют именно формулу пересчета . Это связано в первую очередь с тем, что итерационно можно пересчитывать не саму матрицу , а ее факторы в или разложениях Холецкого [6, 14]. Для плотно заполненных матриц это позволяет при решении систем уравнений в n раз сократить объем вычислений. Однако для решения линейных разряженных систем такой подход ничего не дает, так как поправки к матрице ранга 1 превращают матрицу в плотно заполненную матрицу. Выигрыш во времени расчетов в случае решения линейных систем можно получить, только если использовать разреженность матрицы системы.

Следует заметить, что существуют искусственные подходы к модификации методов переменной метрики для решения разряженных систем линейных уравнений, в которых используются приближения к матрице А, но они строятся той же структуры, что и матрица Гессе [5, 6]. При этом решаются дополнительные оптимизационные задачи, чтобы обеспечить приближениям заданные свойства, например по близости получаемых направлений спуска сопряженным направлениям. Основной недостаток подобных процедур - это потеря свойства конечной сходимости приближений к точному решению.

Свойства формул (6), (7) интенсивно изучались в 60-70-е годы прошлого столетия. Подробную библиографию можно найти в [6, 8]. Было установлено, что формулы (6), (7), в отличие от других методов переменной метрики, не требуют большой точности одномерных минимизаций при вычислении параметров и дают большую свободу выбора линейно-независимых направлений . Другое положительное свойство SR1-формулы - это ее простота. Но есть и недостатки. Основной из них заключается в том, что в процессе итераций знаменатель в добавках ранга 1 к матрице в формуле (7) может оказаться близким или равным нулю, что, естественно, приводит к потере точности и дополнительным итерациям. В настоящее время интерес к численным методам, основанным на SR1-формуле, возобновился. Это связано с тем, что были приведены примеры, в которых формула ранга один показывает лучшие результаты, чем более сложно устроенные методы ранга два, такие, как метод Дэвидона - Флетчера - Пауэлла (DFP-формула) или Бройдена - Флетчера - Гельд-фарба - Шанно (BFGS-формула) [15-20]. Так, в работах [17, 21-24] описываются свойства локальной и глобальной сходимости метода при решении различных задач. Ряд его модификаций предлагается в [18-20, 25-30]. В работах [16, 19, 20, 24] методы, основанные на SR1- формуле, сравниваются с другими квазиньютоновскими методами переменной метрики.

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

Введем обозначения, которые нам потребуются в дальнейшем:

, ,

. (8)

Используя (2), получим рекуррентные формулы вычисления векторов :

,

, . (9)

Для того чтобы найти текущее направление по формуле (9), достаточно помнить предыдущие направления спуска , , …, градиенты , , … и решить систему уравнений . Заметим, что в данном случае можно заранее построить (взять с предыдущего шага интегрирования) гауссово LU разложение или , разложения Холецкого матрицы и использовать их на всех итерациях при определении векторов .

Интересно, что формулу (9) можно еще упростить. Используя формулы (4), (5), (6) и (8) получим, что



Отсюда окончательно следует рекуррентная формула вычисления векторов :

,. (10)

Видно, что для определения по формуле (10) достаточно знать только предыдущее направление , градиент и найти .

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

Приведем в окончательном виде алгоритм решения разряженных систем линейных уравнений, основанный на методе (2).

Обратный итерационный алгоритм (вариант для разряженных систем):

1:

2:

,

(11)

, ,

3:

4: .

Подчеркнем основные свойства выписанного алгоритма.

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

2. Алгоритм (11) по виду можно отнести к методам сопряженных градиентов с предобусловливанием [14], в которых в качестве предобусловливателя выбирается матрица . Однако у него есть существенные отличия. С одной стороны, векторы , генерируемые процедурой (11), не сопряжены с векторами , но удовлетворяют условию А-сопряженности с векторами , . Поэтому теоретически этот метод требует на одну итерацию больше, чем любой метод сопряженных градиентов. С другой стороны, алгоритм (11) является методом переменной метрики. В нем неявно происходит перестроение предобусловливателя, т.е. каждое новое направление стоится с учетом уже уточненного обратного гессиана. Кроме того, алгоритм (11) основан на SR1-формуле. Следовательно, в отличие от методов сопряженных градиентов он не требует высокой точности построения направлений . Все это положительно сказывается на скорости сходимости и устойчивости итерационной процедуры (11) по сравнению с методами сопряженных направлений. Проведенные вычислительные эксперименты подтверждают данные выводы.

3. В алгоритм (11) на втором шаге параллельно с вычислениями векторов можно было бы поставить вычисление приближений к матрице системы А по формуле (7). Однако в этом нет никакого смысла, так как в рассматриваемой задаче решения систем уравнений механических систем в процессе их численного интегрирования элементы матрицы А известны и меняются медленно. Поэтому вместо пересчета матриц на втором шаге процедуры предусмотрен третий шаг перестроения разложения предобусловливателя в том случае, когда точность используемого предобусловливателя не позволяет найти решение за назначенное число итераций . В приводимых ниже вычислительных экспериментах выбиралось . Таким образом, алгоритм (11) можно назвать обратным итерационным алгоритмом с рестартами.

4. Эффективность применения алгоритма (11) для решения разряженных систем линейных уравнений с медленно меняющимися коэффициентами обуславливается тем, что на каждой итерации требуется выполнить только две матричные операции: вычислить градиент и найти решение линейной системы с использованием уже известного разложения матрицы . Решение линейных систем всегда распадается на два этапа: разложение матрицы системы и построение решения с использованием выполненного разложения. Поэтому итерационная процедура (11) эффективна только в тех задачах, в которых матрица возмущений имеет небольшой ранг и многократное построение решения линейной системы , оказывается менее затратным, чем процедура прямого решения возмущенной системы уравнений .

5. В задачах, в которых вычисления по формуле (9) приводят к потере сопряженности направлений , можно рекомендовать заменить ее формулой (10).

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

Вычислительный эксперимент

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

Пусть система линейных уравнений (1) имеет блочную трехдиагональную структуру:

(12)

где , , - матрицы m-го порядка, - m-мерные векторы. Все матрицы являются функциями от времени , , J - число шагов по времени.

Такой вид имеет математическая модель цепочки связанных твердых тел, если при формировании уравнений движения используется метод подсистем, n - число подсистем, m - число степеней свободы в подсистемах. Пусть - функция, значением которой является псевдослучайное число, равномерно распределенное на интервале , - ранг матриц приращений , . Процесс изменения коэффициентов уравнений (12) моделировался по следующему закону:

,

,

,

, ,

.

Элементы всех матриц - псевдослучайные числа, равномерно распределенные в указанных ниже диапазонах:

,

,

,

,

,

.

Тем самым имитировался процесс изменения коэффициентов дифференциальных уравнений во времени в процессе их интегрирования.

Заметим, что в расчетах не контролировалась положительная определенность матрицы системы. Оказывается, что для сходимости всех описанных в статье итерационных методов при использовании их для решения линейных систем уравнений достаточно, чтобы матрица системы не была плохообусловленной и выполнялись условия (3) для матрицы возмущений.

Вычисления проводились с двойной точностью. Итерационные процедуры завершались с абсолютной погрешностью .

При решении систем линейных уравнений использовалось -разложение [6, 14]. Сравнивались временные затраты на решение блочно-трехдиагональной системы уравнений (12) обратным итерационным алгоритмом с рестартами (11), -разложением и методом сопряженных градиентов с предобусловливанием [14, стр. 472]. Последний алгоритм будем называть PCG-методом. В обратном итерационном алгоритме и PCG-методе сопряженных градиентов использовался один и тот же критерий восстановления предобусловливателя .

В табл. 1 приведены результаты расчетов при различном числе блоков n и их порядков m. Число уравнений варьировалось от 30 до 750. Принималось: , , . Введенные параметры обеспечивали эффективный ранг матрицы возмущений не менее 20 при . Отбрасывались те варианты расчетов, в которых -разложение не находило решение.

Таблица 1 - Зависимость времени расчета от порядка системы линейных уравнений (в единицах )

Метод	Число блоков n	Порядок блоков m
		6	8	12	16	20	25	30
1	- разложение	5	1.00	1.49	3.57	6.35	11.74	17.80	27.59
	Алгоритм (11)		1.05	1.44	2.81	4.30	6.35	9.38	12.77
	PCG-метод		1.06	1.43	2.84	4.35	6.40	9.42	12.82
2	- разложение	11	2.11	3.29	7.75	13.92	23.27	38.68	60.42
	Алгоритм (11)		2.29	3.11	6.27	9.93	14.90	21.40	31.41
	PCG-метод		2.31	3.14	6.30	11.00	14.99	21.46	31.52
3	- разложение	15	3.26	5.06	11.88	21.22	35.75	59.80	93.30
	Алгоритм (11)		3.60	5.16	11.27	16.52	24.04	35.86	48.86
	PCG-метод		3.64	5.22	11.33	16.67	24.31	36.14	49.16
4	- разложение	20	4.43	6.89	16.36	28.71	48.31	80.58	127.61
	Алгоритм (11)		5.04	7.27	14.61	22.59	33.38	49.35	67.77
	PCG-метод		5.09	7.34	14.78	22.80	33.69	49.66	68.22
5	- разложение	25	5.63	8.62	20.34	36.31	61.01	112.21	167.23
	Алгоритм (11)		6.73	9.37	18.77	28.58	42.44	63.55	85.79
	PCG-метод		6.80	9.45	18.96	28.83	47.90	63.93	87.11

На рис. 1 приведены графики зависимостей времени расчета представленных в табл. 1, от порядка блоков m системы линейных уравнений (12) при и соответственно.

На рис. 2 приведены графики зависимостей времени расчета представленных в табл. 1, от числа блоков n системы линейных уравнений (12) при и соответственно.



а) б)

Рис. 1. Зависимости от m при: а) и б).

Кривая 1 - LDLT-разложение, кривая 2 - алгоритм (11)

На рис. 1 и 2 показано, что итерационный метод (11), как и точный метод -разложения, обеспечивает линейную зависимость времени счета от числа блоков блочной трехдиагональной системы линейных уравнений (12) и приблизительно квадратичную зависимость времени счета от порядка блоков.

Как видно из результатов, эффективность алгоритма (11) при решении системы линейных уравнений (12) проявляется, когда порядок блоков больше восьми. Обратный итерационный алгоритм (11) и метод сопряженных градиентов с предобусловливанием позволяют приблизительно в два раза ускорить решение блочной трехдиагональной системы линейных уравнений (12) по сравнению с -разложением, если порядок блоков m приближается к двадцати пяти.

На рис. 3 представлен график зависимости отношения времени расчета -разложением к времени расчета итерационным методом (11) от порядка блоков m системы уравнений (12) при .



а) б)

Рис. 2. Зависимости от n при: а) и б).

Кривая 1 - LDLT-разложение, кривая 2 - алгоритм (11)

Рис. 3. Зависимость от m

На рис. 3 показано, что для приведенной тестовой задачи обратный итерационный алгоритм (11) может ускорить расчеты не более чем в пять раз по сравнению с точным методом решения, использующим -разложение. Это связано с тем, что с ростом размерности или плотности системы линейных уравнений возрастает число рестартов в алгоритме (11), а число итераций, после которого включалось восстановление предобусловливателя, было ограничено параметром .

В заключение приведем результаты сравнения среднего числа итераций, требуемых для решения системы линейных уравнений (12) различными итерационными методами. В табл. 2 сравниваются характеристики 3-х методов: обратного итерационного метода (11), в котором применяется или полная формула (10) - алгоритм A1, или усеченная формула (9) - алгоритм А2 и PCG-метод -алгоритм А3. При этом число итераций k не ограничивалось.

Таблица 2 - Среднее число итераций в зависимости от размерности системы уравнений (12)

	Число блоков n
	11	20	30	50	70	90
А1	8.57	9.51	11.13	11.93	11.70	12.34
А2	8.57	9.50	11.02	11.75	11.36	11.92
А3	8.87	9.91	11.68	11.74	12.62	13.34

Расчеты показывают, что в рассматриваемой задаче наиболее устойчивым является алгоритм А2. Метод сопряженных градиентов сходится в целом за большее число итераций, чем обратный итерационный алгоритм (11).



Заключение

В настоящей статье предложена новая модификация обратного итерационного алгоритма, основанная на SR1-формуле и предназначенная для решения разреженных СЛАУ с медленно меняющимися коэффициентами. Метод можно использовать для решения уравнений движения механических систем относительно ускорений при их численном интегрировании.

Рассмотрены свойства алгоритма.

1. Показано, что метод сходится за конечное число итераций. Если матрица возмущений линейной системы уравнений имеет ранг r, то алгоритм сходится за r + 1 шаг.

2. На примере проиллюстрировано, что число итераций, требуемых для нахождения решения с заданной точностью, остается небольшим и практически постоянным для широкого диапазона изменения порядка СЛАУ.

3. Приведены результаты расчетов, которые выделяют область применения предлагаемого метода и подтверждают его высокую эффективность.



Список литературы

1. Иванов В.Н., Домбровский И.В., Набоков Ф.В., Шевелев Н.А., Шимановский В.А. Классификация моделей систем твердых тел, используемых в численных расчетах динамического поведения машиностроительных конструкций // Вестник Удмуртского университета. Математика. Механика. Компьютерные науки. 2012. № 2. С.139-155.

2. Бячков А.Б., Иванов В.Н., Шимановский В.А. Классификация форм уравнений динамики систем твердых тел со структурой дерева // Вестник Пермского университета. Математика. Механика. Информатика. 2009. Вып. 4. С. 119-116.

3. Иванов В.Н. Основные свойства обратного итерационного алгоритма решения систем линейных уравнений с положительно определенными матрицами // Вычислительные методы и программирование: Новые вычислительные технологии. 2012. Т. 13. С. 366-376 (http://num-meth.srcc.msu.ru/).

4. Иванов В.Н. Модификация алгоритма Пауэлла - Бройдена для решения систем линейных алгебраических уравнений // Вестник Пермского университета. Информационные системы и технологии. 2005. Вып. 4. С.115-119.

5. Гилл Ф., Мюррей У. Численные методы условной оптимизации. М.: Мир, 1977.

6. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. М.: Мир, 1985.

7. Дэннис Дж., Шнабель Р. Численные методы безусловной оптимизации и решения нелинейных уравнений. М.: Мир, 1988.

8. Nocedal J., Wright S.J. Numerical Optimization. Berlin: Springer, 2006.

9. Аоки М. Введение в методы оптимизации. М.: Наука, 1977.

10. Фиакко А., Мак-Кормик Г. Нелинейное программирование. Методы последовательной безусловной минимизации. М.: Мир, 1972.

11. Мину М. Математическое программирование. Теория и алгоритмы. М.: Наука, 1990.

12. Поляк Б.Т. Введение в оптимизацию. М.: Наука, 1983.

13. Химмельблау Д. Прикладное нелинейное программирование. М.: Мир, 1975.

14. Голуб Дж., Ван Лоун Ч. Матричные вычисления. М.: Мир, 1999.

15. Conn A.R., Gould N.I.M., Toint Ph.L. Convergence of quasi-Newton matrices generated by the symmetric rank-one update // Mathematical Programming. 1991. V. 50, № 1. P.177-195.

16. Khalfan H.F., Byrd R.H., Schnabel R.B. A Theoretical and Experimental Study of the Symmetric Rank-One Update // SIAM J. on Optimization. 1993. V. 3, № 1. P. 1-24.

17. Byrd R.H., Khalfan H.F., Schnabel R.B. Analysis of a symmetric rank-one trust region method // SIAM J. On Optimization. 1996. V.6. P. 1125-1139.

18. Yueting Y., Chengxian X. A switching algorithm based on modified quasi-Newton equation // Numer. Math. A J. of Chinese Universities. 2006. V. 15, № 3. P. 257-267.

19. Ferreira-Mendonca L., Lopes V.L.R., Martinez J.M. Quasi-Newton acceleration for equality-constrained minimization // Comput. Optim. Appl. 2008. V. 40. P.373-388.

20. Wah J., Malik A. H. A restarting approach for the symmetric rank one update for unconstrained optimization // Comput. Optim. Appl. 2009. V. 42. P. 327-334.

21. Kelley C.T. Local Convergence of the Symmetric Rank-One Iteration // Computational Optimization and Applications. 1998. V. 9. P. 43-63.

22. Spellucci P. A Modified Rank One Update Which Converges Q-Superlinearly // Computational Optimization and Applications. 2001. V. 19. P. 273-296.

23. Fletcher R. A New Low Rank Quasi-Newton Update Scheme for Nonlinear Programming // IFIP System Modeling and Optimization. 2006. V. 199. P. 275-293.

24. Schlenkrich S., Griewank A., Walther A. On the Local Convergence of Adjoint Broyden Methods // Math. Program. Ser. A. 2010. V. 121. P. 221-247.

25. Sun L. Updating the Self-Scaling Symmetric Rank One Algorithm with Limited Memory for Large-Scale Unconstrained Optimization // Computational Optimization and Applications. 2004. V. 27. P. 23-29.

26. Wang Zhou-Hong, Yuan Ya-Xiang. A subspace implementation of quasi-Newton trust region methods for unconstrained optimization // Numer. Math. 2006. V. 114. P. 241-269.

27. Wah J.L., Malik Abu H. Convergence of a positive definite symmetric rank-one method with restart // Advanced Modeling and Optimization. 2009. V. 11, № 4. P. 423-433.

28. Farzin M., Malik Abu H., Wah J.L. Multi-steps symmetric rank-one update for unconstrained optimization // World Applied Sci. J. 2009. V. 7, № 5. P. 611-615.

29. Farzin M., Malik Abu H., Wah J.L. Memoryless modified symmetric rank-one method for large-scale unconstrained optimization // American J. of Applied Sciences. 2009. V. 6, № 12. P. 2054-2059.

30. Farzin M., Malik Abu H., Wah J.L. Convergence of symmetric rank-one method based on modified quasi-Newton equation // J. of Math. Res. 2011. V. 2, № 3. P. 97-112.

Размещено на Allbest.ru

...