Блочно-линеаризационный подход к решению систем нелинейных уравнений

• Автор: Седельникова, Анна Владимировна
• Шифр специальности: 01.01.07
• Научная степень: Кандидатская
• Год защиты: 2002
• Место защиты: Москва
• Количество страниц: 158 с. : ил

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ

ГЛАВА 1. Описание подхода и исследование сходимости алгоритмов БЛП

§ 1.1. Основные конструкции метода

§ 1.2. Структурная классификация алгоритмов решения систем нелинейных уравнений и задач безусловной минимизации
§ 1.3. Исследование сходимости алгоритмов БЛП для решения систем нелинейных уравнений

ГЛАВА 2. Анализ сходимости и устойчивости алгоритмов БЛП

§ 2.1. О скорости сходимости алгоритмов БЛП

§ 2.2. Исследование устойчивости алгоритмов, построенных

на основе блочно-линеаризационного подхода
§ 2.3. Анализ устойчивости методов решения систем нелинейных уравнений и задач безусловной минимизации
ГЛАВА 3. Методика и примеры реализации алгоритмов на основе блочно-линеаризационного подхода
§ 3.1. Методика построения алгоритмов БЛП
§ 3.2. Методы решения систем нелинейных уравнений
3.2.1. Блочный вариант метода сопряженных невязок (МСН) (Алгоритм А1 (1 <1 <п))
3.2.2. Блочный симметричный вариант метода сопряженных невязок (Алгоритм А2 (/ < / < л))
3.2.3. Модифицированные варианты метода сопряженных градиентов (Алгоритм АЗ (2 < I < п; тц 1 = 1,
т»А =2’ I = 2,1))
§ 3.3. Методы решения задач безусловной минимизации
3.3.1. Блочный вариант метода сопряженных градиентов (Алгоритм В1 (/ <1<п))
3.3.2. Модифицированный метод сопряженных градиентов (Алгоритм В2 (2<1<п; т^1=1, т^1=2,
2.1))
3.3.3. Блочный вариант метода минимальных итераций (Алгоритм ВЗ (1<1 <«))
3.3.4. Блочный вариант квазиньютоновских методов (Алгоритм В4 (/< 1<п))
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА

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

ОБОЗНАЧЕНИЯ И СОКРАЩЕНИЯ
Я'1 - «-мерное вещественное евклидово пространство;
п ШУИ
Я - пространство вещественных матриц размера тхп
Е - единичная матрица;
Xі - вектор, транспонированный к вектор-столбцу х;
I • II - норма как вектора х е Я", так и подчиненная ей норма пря-
II и 2 г
моугольных матриц; х = х х = 2_,
*і > і=
x,,x2,...,xm - матрица, состоящая из m вектор-столбцов х, gä", i —
m> 1;
xj или Xj - j-я компонента вектора х, какой смысл имеет индекс будет
видно из контекста;
А - матрица, транспонированная к матрице А;
Aj,(a 1) -j-я столбец и i-я строка матрицы А;
А~' - матрица, обратная к матрице А;
cij - элемент i- й строки у-го столбца матрицы А;
arg Z - решение задачи Z;
= - равно по определению;
ф'(х) - производная векторной функции ф :Rn -> Rn, матрица Яко-

V/(x)s /'(х) градиент функции /(х) ;
/”(х) матрица вторых производных, матрица Гессе;
БЛП - блочно-линеаризационный подход;
РАП - разностно-аппроксимационный подход;
СНУ - система нелинейных уравнений;
СЛУ - система линейных уравнений;
БМ - безусловная минимизация;
МСГ - метод сопряженных градиентов.
Нумерация лемм, теорем и формул в каждой главе диссертации независимая.

§ 1.3. Исследование сходимости алгоритмов БЛП для решения систем нелинейных уравнений
Приступим к изучению свойств алгоритмов, построенных на основе блочно-линеаризационного подхода (описание дано в § 1.1.). Докажем следующую лемму.
Лемма 1.1. Пусть матрицы Ак, СеКпхп и матрица Як е Втщ таковы, что АТкАк, СтС 6 Ял/п и е ЯткХтк - положительно определенные матрицы с параметрами (а1,а2), (у7,у2) для УкеК, соответст-
венно (ПЗ.З). Пусть матрица Ок-АТкСТС, тогда все ранги матриц л* =^[АА^, Вк =5а.Л:/5[, Нк=ВкОк равны тк, матрицы ОкАк, Ак, В)[Ок положительно определены с соответственными параметрами (8;,82), (53,5^), (85,бб), а матрица Вк положительно полуопреде-лена при тк<п и положительно определена при тк-п с параметрами (57,5§), где
5/= а/Р/; 82=а2|32; 83=а/Р/у/; 82 = а2Р2у2; (1.3.1)
О, тк < п
У1 т - и ’ ^ “ п"
>тк~П СС/РуУ;
$.5 - а/Р/; 5,5—а2Р2; 57 — ■
Доказательство
Докажем сначала первое утверждение. Так как матрицы АТк Ак, СтСеЯпхп и 5^5^ £ Я” положительно определены, то они будут невырожденными матрицами [39], [51]. С другой стороны, эти матрицы являются матрицами Грама, а значит ранги матриц Ак, С, АгкАк, С1С равны п, а ранги матриц Бк равны тк [39], [51]. Известно [39], [51], что для произве-
дения матриц Т еЯкхр и М е Лрх<1 справедливо неравенство Сильвестра: гт+гм~Р^ гт-м ^ ^т{гт,гм), (1.3.2)
где гг, гм и гт.м - ранги матриц ДМ и Т-М соответственно. Применяя неравенство Сильвестра к матрицам Ок и Д. Ак, получим, что г0к = п и = п.
Представим матрицу Ак как Ак = (САк8к )Т {САк8к). Применим последовательно неравенство Сильвестра к матрице САк8к, получим, что ее ранг равен гСАЗ = тк. Следовательно, ранг матрицы Л^тоже равен тк, так как она является матрицей Грама для матрицы САк8к. Очевидно, что ранг матрицы А~к также равен тк, так как Ак - квадратная невырожденная матрица. Далее, применяя последовательно неравенство Сильвестра к матрице Вк, получим, что гв - тк. Таким же образом получается гн> = тк.