Меню
Главная
Авторизация/Регистрация
 
Главная arrow Математика arrow Специальные методы оптимизации

ГЛАВА 5 ДЕКОМПОЗИЦИЯ И АГРЕГИРОВАНИЕ

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

§20. МЕТОД АГРЕГИРОВАНИЯ ДЛЯ РЕШЕНИЯ СИСТЕМЫ ЛИНЕЙНЫХ УРАВНЕНИЙ

Пункт 20.1. Рассмотрим следующую систему линейных уравнений:

где х,Ь — /г-мерные векторы; А — (яхл)-мерная матрица, обладающая свойствами:

Пусть х = (хх, хп) — решение системы (20.1). Сложив все уравнения системы (20.1), получим скалярное уравнение

И обратно, если известно X — решение уравнения (20.2), то

Видно, что задача (20.1) будет решена, если удастся определить числа рь так, что

Приведем итеративный метод решения системы уравнений (20.1), изложенный в [52], [53]. Пусть задано х° = = (*{*, ..., х°) —некоторое начальное приближение решения (20.1).

Положим

Построим X1 по следующему правилу: или,обозначив получим и далее

I

Из (20.5), (20.6) получим

Введем матрицу

и перепишем (20.8) в виде

Матрица в обладает свойствами:

Предположим, что матрица Б неразложима, т. е. не существует такой перестановочной матрицы Р% что

где в! — квадратичная подматрица.

Достаточным условием для этого является неразложимость матрицы А.

Известно [13], что

1) последовательность {8Л’} сходится к некоторой матрице Т;

2) векторы-столбцы матрицы Т одинаковы и равны вектору t> 0;

3) для любого вектора

Из (20.9) и вышеперечисленных свойств матрицы Э следует, что

и

Таким образом, сходимость этого итерационного процесса показана.

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

Определение 20.1. ХА. называется Jk — агрегированной переменной, если

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

Обозначим

Тогда система (20.1) преобразуется в систему

При построении итерационного процесса зададим, как и раньше, начальное значение

На первом шаге получаются значения Хх, X, из решения системы

Элементы матрицы А(0) получаются из (20.10), если положить

Однако знание точного решения (20.12) не является, по существу, необходимым.

Будем решать (20.1) следующим образом.

Определим

Пусть У'1* получается в результате решения скалярного уравнения

Вместо того, чтобы определить Хд.11 из (20.12), положим

и далее получим

Аналогично, значение хя на (А + 1)-м шаге итерации получим по формуле

Назовем процесс решения системы (20.1) в первом случае одношаговым итерационным процессом, а процесс, описанный только что, двухшаговым, так как в первом случае все переменные системы (20.1) были объединены в одну переменную X, а во втором случае аналогичный процесс объединения произошел за два шага.

В результате итерации с номером N двухшагового процесса были получены значения переменных х6 = х^К Пусть хв = х* * — значение х8 после IV-й итерации в одношаговом процессе.

Покажем сходимость двухшагового процесса.

Начальные значения для обоих процессов одинаковы, т. е.

Сравним (20.3) и (20.14), получим

Из (20.3), (20.14), (20.18), (20.19) получим

Используя (20.6), (20.13), (20.16), (20.18) и то, что с/у не пересекаются, получим

Аналогично, по индукции доказывается, что

Естественно, что процесс решения (20.1) можно представить и не только двухшаговым, но и многошаговым.

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

Пункт 20.2. Описанный метод итерационного агрегирования особенно эффективен, если матрица А в (20.1) имеет блочно-диагональную структуру.

Будем считать, что в одну величину Х*(/е = 1 ,т) агрегируются все переменные х,, г е J Таким образом, запишем (20.1) в виде:

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

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ ОРИГИНАЛ   След >
 

Популярные страницы