Содержание к диссертации
Введение
ГЛАВА 1. Описание подхода и исследование сходимости алгоритмов БЛП
1.1. Основные конструкции метода 19
1.2. Структурная классификация алгоритмов решения систем нелинейных уравнений и задач безусловной минимизации 29
1.3. Исследование сходимости алгоритмов БЛП для реше ния систем нелинейных уравнений 35
ГЛАВА 2. Анализ сходимости и устойчивости алгоритмов БЛП
2.1. О скорости сходимости алгоритмов БЛП 54
2.2. Исследование устойчивости алгоритмов, построенных на основе блочно-линеаризационного подхода 61
2.3. Анализ устойчивости методов решения систем нелинейных уравнений и задач безусловной минимизации ... 80
ГЛАВА 3. Методика и примеры реализации алгоритмов на основе блочно-линеаризационного подхода
3.1. Методика построения алгоритмов БЛП 84
3.2. Методы решения систем нелинейных уравнений 94
3.2.1. Блочный вариант метода сопряженных невязок (МСН) (Алгоритм А1 (/ / «)) 94
3.2.2. Блочный симметричный вариант метода сопряженных невязок (Алгоритме (1 / «)) 114
3.2.3. Модифицированные варианты метода сопряженных градиентов (Алгоритм A3 (2 l п; т j = 1, іим=2,і= )) 121
3.3. Методы решения задач безусловной минимизации 126
3.3.1. Блочный вариант метода сопряженных градиентов (Алгоритме/(/ / «)) 126
3.3.2. Модифицированный метод сопряженных градиентов (Алгоритм В2 (2 1 п; т г=1, туіі = 2,
i = 2J)) 129
3.3.3. Блочный вариант метода минимальных итераций (Алгоритм ВЗ (7 / //)) 135
3.3.4. Блочный вариант квазиньютоновских методов (Алгоритм В4{1 / «)) 138
Заключение 141
Литература
- Структурная классификация алгоритмов решения систем нелинейных уравнений и задач безусловной минимизации
- Исследование устойчивости алгоритмов, построенных на основе блочно-линеаризационного подхода
- Анализ устойчивости методов решения систем нелинейных уравнений и задач безусловной минимизации
- Модифицированные варианты метода сопряженных градиентов (Алгоритм A3 (2 l п; т j = 1, іим=2,і= ))
Структурная классификация алгоритмов решения систем нелинейных уравнений и задач безусловной минимизации
В 2.2 рассматриваются вопросы устойчивости к малым возмущениям итерационного процесса {хк} решения систем нелинейных уравнений и задач безусловной минимизации. Рассмотренная в диссертации проблема устойчивости - это проблема сохранения сходимости и оценок скорости сходимости при наличии погрешностей в вычислении величин рк и Хк. Строгое рассмотрение реального процесса сходимости последовательности {хк} к решению х с учетом влияния погрешностей различной природы (ошибки округления в ЭВМ, аппроксимации вычисляемых величин и т.д.) - интересная и малоисследованная тема. Существующий в настоящее время подход к сходимости хк —» х , при к - оо является идеализацией этого реального процесса, так как реальный процесс имеет всегда конечное число шагов. Однако, такая идеализация часто позволяет сделать правильные качественные выводы о характере сходимости {хк} к х в реальном вычислительном процессе при различном уровне его погрешностей. В схеме исследования устойчивости природа погрешности Арк и АХк не учитывается, требуется только малость величин ЦД/ Ц и AA,fc. Предложенная схема исследования устойчивости процесса сходимости последовательности [хк} к решению х является существенным уточнением рассмотренной в работах [18], [19] схемы устойчивости для задач (0.1) и (0.2). Особенностью указанных работ является то, что в них рассматривалась устойчивость (сходимость хк — х при наличии погрешностей Арк и АХк, в которой сохраняется порядок скорости сходимости невозмущенного метода) для задач (0.2) и констатировался перенос условий сходимости на задачи (0.1). В настоящей работе подробное изложение устойчивости итерационной последовательности {хк}, к = 1,2,... проведено для задачи (0.1) и при рассмотрении конкретных утверждений делались по аналогии регулярные уточнения о характере устойчивости для задачи (0.2). Целью построенной в 2.2 теории устойчивости для численных методов на основе БЛП является получение достаточных условий для уровней погрешностей \\Арк\\ и ДА,А, при которых сохраняется требуемый порядок скорости сходимости при различных условиях реализации алгоритмов БЛП, таких как, градиентная согласованность последовательности {рк}, локальная сильная выпуклость минимизируемой функции F(x) И др. Опираясь на по 14 лученные теоремы об устойчивости последовательности {хк}, в главе 3 будут доказаны утверждения о сходимости предложенных в настоящей работе методов решения задач (0.1) и (0.2). Приведенная в работе схема исследования устойчивости обладает определенной общностью. Она позволяет получить выводы об условиях устойчивости известных методов решения задач (0.1) и (0.2), таких как метод Ньютона, градиентные методы, квазиньютоновские методы и т.д. Однако отметим, что для каждого конкретного метода решения систем нелинейных уравнений и задач безусловной минимизации необходимо провести достаточно точную оценку для Л/?І, что не всегда является простым делом.
Схема исследования устойчивости сходимости хк — х , построенная в диссертации, является развитием работ [18], [19]. Нам неизвестны работы, кроме указанных, в которых исследуется влияние погрешностей Арк и АХк на сходимость для целого класса численных методов решения задач (0.1) и (0.2). Укажем на некоторые монографии, в которых изучалось влияние погрешностей на сходимость конкретных методов решения рассматриваемых задач. Исследование влияния погрешностей различной природы при вычислении градиента V/(x) на сходимость градиентных методов и методов Ньютона проведено в [10], в работе [20] сформулированы условия, накладываемые на погрешности вычисления f"{x) и V/(x), а также гарантирующие квадратичную скорость сходимость метода Ньютона в задаче поиска седло-вых точек функции f(x), х є Rn. Влияние погрешности при вычислении функции ф(х), ф: R" - R", на сходимость метода Ньютона изучалось в работах [21], [22]. Вопросы влияния ошибок округления при решении СНУ изучались также в работах [23], [24].
В 2.3 второй главы приведены примеры, иллюстрирующие применение доказанных в 2.2 теорем об устойчивости для широко известных методов решения задач (0.1) и (0.2). Примеры 1 и 2 иллюстрируют новые оценки скорости сходимости для метода наискорейшего спуска и метода сопряженных градиентов, а примеры 3 и 4 приведены для дальнейшего их использования при доказательстве теорем сходимости в главе 3 настоящей работы.
Глава 3 диссертации посвящена вопросам методики построения алгоритмов решения задач (0.1) и (0.2) на основе блочно-линеаризационного подхода и примерам реализации конкретных методов их решения.
В 3.1 третьей главы рассмотрены вопросы методики практической реализации алгоритмов на основе блочно-линеаризационного подхода, описание которого дано в 1.1, а структурная схема методов - в 1.2. В методике построения конкретных алгоритмов БЛП можно выделить две части: вначале рассматриваются вопросы построения элементов алгоритмов в соответствии со структурной схемой алгоритмов ( 1.2), а после этого рассмотрены вопросы экономичного вычисления элементов алгоритмов БЛП на основе разностных аппроксимаций производных первого и второго порядка точности. Указывается, что для построения вектора рк = р (, i = 1,1 применимы обширные классы методов решения систем линейных уравнений и расписана по элементам техника вычисления вектора р г. Разностные аппроксимации первых и вторых производных применяются в основном для вычисления элементов алгоритмов при вычислении вектора р ., но в некоторых случаях могут применяться и для вычисления шага А, . В 3.2 исследуются свойства численных методов решения систем нелинейных уравнений с симметричной и несимметричной матрицами ф (х), построенных на основе блочно-линеаризационного подхода.
Первым рассматривается численный метод (Алгоритм АЇ) решения задачи (0.1) при параметре блочности 1 / п, матрица ф (х) - несимметрична, названный - "Блочный вариант метода сопряженных невязок" [25]. Его основой является метод решения системы линейных уравнений Ах = Ь, в котором строится система сопряженных относительно матрицы АтА векторов, и свойства которого изучались в [26], [27]. В работе доказана лемма 3.1, в которой получены новые результаты о свойствах сходимости метода сопряженных невязок (МСН) для решения систем линейных уравнений. Для доказательства сходимости алгоритма А1 при 1 / п сначала была доказана вспомогательная теорема 3.1, в которой получены оценки для погрешностей Арк в вычислении вектора рк при 1 = 1. Теорема 3.1 объемна (10 страниц текста), фактически она дает методику получения оценок погрешности в вычислении вектора рк при наличии погрешностей алгоритма, обусловленных разностными аппроксимациями производных. В теореме 3.2 доказывается сходимость алгоритма А1 при 1 1 п к решению х , причем алгоритм сходится по крайней мере с линейной скоростью. Отметим, что при 1 = 1 реализуется первый вариант БЛП, а при 1 1 - его третий вариант, так как при / = 1 имеем реализацию первого варианта БЛП, а при i 1 - второго варианта БЛП.
Исследование устойчивости алгоритмов, построенных на основе блочно-линеаризационного подхода
В настоящем параграфе рассматривается достаточно общая схема исследования влияния вычислительных погрешностей Арк и А при вычислении соответственно вектора рк и числа Хк на сходимость последовательности {хк}, к = 1,2,3,... к точке х , когда {хк} определена рекуррентной формулой хк = хк_1+ркХк.
В настоящей работе на основе определения устойчивости методов, близкого к определению устойчивости методов из [18], будет рассматриваться вопрос устойчивости достаточно широкого класса методов, включая предлагаемые в диссертации.
Пусть s є Rn - точное значение вектора, s - его приближенное значение, As - погрешность, т.е. s=s + As (2.2.1) Погрешность As будем называть абсолютно-ограниченной, если она удовлетворяет условию: Н є (2.2.2) и относительно-ограниченной погрешностью, если для нее справедлива оценка: ІНІ ЧИІ (2.2.3) где в (2.2.2) и (2.2.3) є - достаточно малое число. Погрешности подобного рода рассматривались в [ 10] применительно к вектору s = V/(x). Рассмотрим для решения систем нелинейных уравнений и задач безусловной минимизации итерационный процесс вида: хк=хк_1+Хкрк, к = 1,2,3,... (2.2.4а) где рк =P{xk_,) Rn, Xk=A{xk_,,pk)eRJ и Р: Rn —» Rn, A:RnxRn- R1 - некоторые отображения, определяемые конкретным методом. Предполагается, что Ит Рассмотрим на к-м шаге возмущенный процесс решения рассматриваемых задач: хк=хк_,+Хкрк, к = 1,2,3,... (2.2.46) гДе Рк =Рк+АРк Рк =p(xk-i) Ьк=%к+М к k=A(xk-i Pk) АРк и АЧ - погрешности в вычислении вектора рк и числа Хк. В данном случае для точки хк имеем соотношение: Xk=xk-i+ kPk+Axk=xk+Axk (2-2.5) где хк =xk_j+Xkpk, Ахк = \кк -Хк)Рк +ХкАРк +АХк(Рк+Арк), кк= {хк-і Рк) 62 где коэффициенты q(, i = 1,к, определяют скорость сходимости последовательности {хк} и обычно ограничены числом q, таким, что qt q l, для V/, і = 1,к, к - оо. Из (2.2.5) и (2.2.7) получим оценку: - возмущенное значение коэффициента скорости сходимости qk. Заметим, что в случае сходимости возмущенной последовательности {х } выполняется очевидное соотношение дк qk 1. сохраняется. Следовательно, задачу исследования устой чивости процесса сходимости возмущенной последовательности {хк} к ре шению х можно свести к изучению характера изменения коэффициента qk. В соответствии с наиболее часто используемыми оценками скорости сходимости дадим следующее определение устойчивости процесса сходимости последовательности {хк}.
Определение 2.2. Итерационный процесс (2.2.5) будем называть: а). Линейно устойчивым (или просто устойчивым), если коэффициент qk (2.2.8) удовлетворяет условию qk qk q 1, для Ук К0, к —»со; б). Сверхлинейно устойчивым, если qk - 0 при А;—»оо; Точно так же можно ввести определения устойчивости и для других оценок скорости сходимости. Конечно, введение такого определения в неко 64 торых случаях огрубляет оценки характера сходимости возмущенной последовательности \хк}, однако, как это будет видно из дальнейшего, оно не из Ах,, что для реализации устойчивой сходимости при qk q 1 необходимо, чтобы \\Ахк —» 0 и менит качественного характера изучаемого процесса.
Этот случай (теоретически реализуемый) можно назвать случаем устойчивой относительно-ограниченной погрешности (2.2.3) для вектора , где z = l-qk. Следует заметить, что в реальных вычислительных процессах решения систем нелинейных уравнений и задач безусловной минимизации при помощи ЭВМ предел к - оо не реализуется, а именно, имеет место случай: к = 1,2,...,N, причем, вычисления проводятся с конечной точностью, что для подавляющего большинства задач дает погрешность
То есть, достаточно часто на практике реализуется случай с погрешностью решения Ахк, для которой не выполняется условие \\Ахк \ 0, при к - оо. В этих условиях говорить об устойчивости методов решения систем нелинейных уравнений и задач безусловной минимизации нельзя, и, если \\Ахк\\ удовлетворяют соотношению (2.2.11), то такие методы принципиально неустойчивы, так как, очевидно, для любого є 0 и qk 1 найдется такой вектор хк_], что qk l. Однако, в этом случае можно говорить об области неустойчивости рассматриваемых методов. Устойчивость методов ухудшается при хк_} -» х . Предположим, что процесс ухудшения сходимости, иначе, возрастания коэффициента qk при возрастании номера к монотонный, т.е. qk qk+] 1, для \/к N, это означает, что итерационный процесс был где є - мажоранта погрешности, 1 q qN - мажоранта коэффициента скорости сходимости для невозмущенной последовательности [хк}. Величина R в (2.2.12) имеет смысл радиуса области, вне которой конкретный метод заве домо устойчив, а V = jx є Rn больше радиуса области неустойчивости, т.е. 8 R. Если R 8, то получение решения с точностью 8 может быть затруднительно. Конечно, эти соображения носят качественный характер, например, в облас R метод будет устойчивым, но сходиться к решению может очень медленно, кроме того, определить мажоранты є и q для многих методов и конкретных вычислительных средств бывает чрезвычайно трудно.
Следует заметить, что хотя большинство методов решения систем нелинейных уравнений и задач безусловной минимизации на ЭВМ принципиально неустойчивы при к — GO , изучение устойчивости методов может быть полезным для анализа влияния погрешностей на сходимость методов, сравнения различных методов по их устойчивости и возможного качественного анализа достижимости решения задачи. Одним из методов изучения устойчивости алгоритмов решения СНУ и задач БМ является получение достаточных условий устойчивости для некоторого класса рассматриваемых задач. При этом исследование устойчивости при наличии погрешности Ахк подразумевает рассмотрение двух вопросов: А). Обеспечение начальной сходимости, т.е. qk l при 1 к К0, где К0 - некоторое целое число. Б). Обеспечение требуемой скорости сходимости при к К0, к -» со. Рассмотрим теперь достаточные условия, накладываемые на погрешности Ахк, Арк, АХк, при которых сохраняется порядок сходимости возмущенной последовательности {хк} к решению х систем нелинейных уравнений и задач безусловной минимизации. Пусть ф(х), q :XczRn - Rn - непрерывно дифференцируемая вектор-функция, ф (х) - невырожденная матрица, для которой выполняются следующие условия (лемма 1.1):
Анализ устойчивости методов решения систем нелинейных уравнений и задач безусловной минимизации
В доказательстве теоремы 3.1 рассматривается основной случай, когда тк т п.Из доказательства теоремы следует, что в этом случае для любых чисел є и М найдется такое достаточно малое число \h\, что будет выполнено условие окончания гт Б -Г0, где тк т п, гк = minye,Мф(л:Л_7). Однако, указать такие числа є, М и h , для которых выполнено на практике условие окончания не всегда возможно. Кроме того, не представляется возможным в реальных условиях знать соотношение между числами т и п (т=п или т п). В этом случае предусмотрено условие тк п, которое ограничивает число шагов алгоритма Л1 при вычислении вектора рк .
Случай, когда т тк п, означает, что h выбран не достаточно малым и не выполнено условие основного случая: тк т п. Неудачный выбор числа h может привести и к неустойчивому случаю, когда вектор рк может быть неэффективным направлением убывания величины ф( . В этом случае в алгоритме при его программной реализации предусмотрен выбор такого шага по направлению убывания Хк, при котором выполняется неравенство: ф(хА ф(лгА_у . Однако, малость величины \h\ практически всегда обеспечивает эффективное направление убывания ф(х.
При практической реализации алгоритма А1 при / = 1 в условие окончания вводится параметр п0 п, п0 - целое число, по следующему пра вилу: тк = min \j : j є [/, п0 п\. г; гк \\г0 \\), ек = тіп (є, М\ц(хк_, ), 0 є 1, М 0, где параметр п0 при п0 п ограничивает число шагов в вычислении вектора рк, и тем самым, как показала практика, достаточно часто повышается эффективность алгоритма А1 решения систем нелинейных уравнений. Выбор параметра п0: п0 п - эвристический прием. Наиболее оправдано его введение на начальных шагах решения СНУ, когда точки последовательности [хк} еще "далеки" от точки х0,
Сказанное в п.п. А, Б, В справедливо, когда вычислительный процесс устойчив в смысле понятия устойчивости, введенного в 2.2. Замечание 2 к теореме 3.1. Из доказательства теоремы 3.1. видно, что погрешности в вычислении вектора рк на каждом шаге удовлетворяют оценке: число шагов, 1 т0 п; с - некоторая константа, зависящая от параметров метода. Теперь можно сформулировать теорему о сходимости блочного варианта m-шагового метода сопряженных невязок.
Теорема 3.2. Пусть вектор-функция ф(х), хеХ, X = х:ф(х ф(х0} удовлетворяет условиям: СИ/УТУ -ф (х) -а2УТУ Ух е X, О а.] а2 со, ф (х)-ф (_у L0 -\\х-у\\, Ух,уеХ, L0 0, и выполнены условия леммы 3.1. Пусть также в алгоритме А1 числа є0, ДА,, h - достаточно малы и &к г0, 0 г0 1, АЛ ЛЛ.. Тогда алгоритм А1 сходится к решению системы нелинейных уравнений X (ф(х )= 0) по крайней мере с линейной скоростью.
Рассмотрим сначала доказательство теоремы для случая, когда параметр блочности / = 1. В этом случае алгоритм А1 представляет собой дискретный m-шаговый метод сопряженных невязок, для которого справедлива теорема 3.1. В указанной теореме доказана оценка для погрешности исследуемого метода: НА II н\\Л к+сЩІУ(хк-іІ) Ь(хк-іІ с I\&Рк \\ Рк Рк — /——— Ьудем также считать, что погрешность одномерного поиска достаточно мала и Дл. АХ,, где ДА, -достаточно малое число..
Как указывалось в теореме 3.1, для исследуемого метода невозмущенным методом является метод Ньютона, который сходится не только с линейной, но и с квадратичной скоростью. Для метода Ньютона известно, что ко 113
эффициентом скорости сходимости может быть любое число q є (0,l). Тогда на основании теоремы 2.5 получаем, что дискретный w-шаговый метод сопряженных невязок сходится к решению х по крайней мере с линейной скоростью сходимости.
Если же наложить на параметры метода условие дополнительного уменьшения погрешностей, то дискретный m-шаговый метод сопряженных невязок будет сходиться к решению с квадратичной скоростью.
Доказательство сходимости блочного варианта метода сопряженных невязок (1 1 п), состоящего из двух вариантов: а), метод при 1 1 п -теорема 3.2 и б). 1 = 1 (дискретный m-шаговый метод сопряженных невязок) - теорема 3.1, потребовало значительных усилий. В частности, в случае а). доказана лишь линейная скорость сходимости (теорема 3.2), тогда как в слу чае б). - квадратичная скорость сходимости. Конечно, сходимость алгоритма рассматривается в предположении, что вычисления ведутся при достаточно большой мантиссе в представлении действительных чисел, когда округления при вычислениях мало влияют на результат вычислений. Эта идеализация показывает порядок теоретической сходимости алгоритмов при устойчивом характере сходимости, которая нарушается при хк — х . Практическая эффективность предложенных методов рассматривается в Приложении 1.
Рассмотрим теперь метод решения систем нелинейных уравнений ц (х)=0, ф:і?" - Rn, для которых матрица ф (х) невырождена и симметрична. Отметим, что численные методы решения систем нелинейных уравнений ф(х) = 0 с симметричной матрицей ф (х) актуальны для решения практических задач, таких как нахождение стационарных точек в задаче поиска минимакса: min max f{x,y), [хт,ут)є Rm +ni2, в задаче поиска седловых х у точек функций Лагранжа некоторых экстремальных задач и другие.
Модифицированные варианты метода сопряженных градиентов (Алгоритм A3 (2 l п; т j = 1, іим=2,і= ))
Рассматривается алгоритм решения систем нелинейных уравнений с симметричной невырожденной матрицей Якоби ф (х). Этот алгоритм решения систем нелинейных уравнений можно рассматривать как метод решения задачи безусловной минимизации с функцией f{x) = — фг(х)ф(х). Он является некоторой модификацией алгоритма В2 решения задачи безусловной минимизации, для него справедливы соображения, приведшие нас к его построению (см. ниже). Принципиально такой алгоритм возможен и для несимметричных матриц ф (х), но в несимметричном случае вычисление V/(x) = ф (х) ф(х) трудоемко и численная реальная его эффективность по сравнению с другими алгоритмами (например, методом Ньютона) будет мала. Шаг Хці в итерационном процессе
Можно предположить, что алгоритм A3 будет эффективным, если вычисление элементов для построения вариантов формул коэффициентов 3Ц; не будет трудоемким. Рассмотрим теперь разностные аппроксимации элементов в формулах (3.2.12), (3.2.13), (3.2.14).
Вычисление чисел sff"(x)sj, i,j = l,2 возможно и в другом приближенном варианте, если вычислить значения векторов f"(x)sj, j = l,2. Это , ч Vf{x + hSj)-Vf{x-hs ) — можно сделать по формуле f\x)Sj = —, j = 1,2 или, 2h после подстановки значения разностных аппроксимаций V/( ) по формуле (3.2.15): , . Ц)[х + hsj + hsj- Ц)[х + hsj - hsj- ф(х - hs + hs)+ ф(х - hs - hs) fbh = . у =7,2, где 5 = ф(х). Рассмотренные варианты алгоритмов решения систем нелинейных уравнений ф(х) = 0, с симметричной матрицей ф (х) назовем модификациями метода сопряженных градиентов.
Рассмотрим теперь свойства сходимости указанных алгоритмов. Теорема 3.5. Пусть для системы нелинейных уравнений ф(х) = 0 с симметричной матрицей ф (х), ХЕХ: Х = {хє/Г :ф(л: ф(х0}, непрерыв II ная функция f"(x) = — ф(х)Гф(х) удовлетворяет условиям: a j уТ у уТ f"(x)y а 2 у1 у, УхеХ, Vy є R", 0 а, а2 со. Тогда метод решения задачи безусловной минимизации, в котором р t вы числяется по формуле (3.2.12), (3.2.13), (3.2.14),
Единственность точки х очевидно определяется условиями теоремы. Доказательство во многом повторяет доказательство теоремы 3.6 (алгоритм В 2). Во-первых, убедимся, что в рассматриваемом методе вектор Лм = - v/( n,,w)+ РмЛм-/ где V/( n,/-/)= P l n,«w М ц,м) градиентно-согласован. Так как векторы УД (._у )ир г-_7 ортогональны, то , отсюда, константа градиентной согласо ванности %і 1. Знак равенства для обоих неравенств имеет место при / = 1, T-e-IW НМ м1 K%I=] Так же имеем - р /УДл ._;)= УДл у] и поэтому константа градиентной согласованности %3: %3 1.
Рассмотрим оценку для коэффициента Р . во втором варианте алгоритма, так как первый вариант совпадает со вторым при условии точного вычисления шага Я,,,,:
Если теперь в методе (3.2.12) взять погрешность шага одномерной минимизации ДА, . Сjє, где 8 - малое число, h2 - малое число, то на основании теоремы 2.6 имеем, что исследуемый второй вариант алгоритма, в котором элементы матрицы Л вычисляются по формулам (3.2.16), будет сходиться с линейной скоростью.
Рассмотрим теперь первую модификацию метода сопряженных градиентов, в которой коэффициент Р ; вычисляется по формуле (3.2.13). Таким образом, метод решения задачи безусловной минимизации, в котором коэффициенты р . вычисляются по формуле (3.2.13), будет сходиться в условиях теоремы 3.5 с линейной скоростью.
Отметим также, что для первой модификации метода сопряженных градиентов при любой размерности задачи увеличение объема вычислений по сравнению с методом Флетчера-Ривса составляет вычисление значений функции в 8-ми точках, что при больших размерностях задачи несущественно.
Предлагаемые в настоящем параграфе алгоритмы строятся на основе методов сопряженных направлений, которые находят точку минимума квадратичной функции не более, чем за п шагов (при условии выполнения точных вычислений). В общем случае, когда f{x) - неквадратичная функция, то теоретическая сходимость предлагаемых методов бесконечношаговая. Решения задачи безусловной минимизации, которые находят предлагаемыми алгоритмами, являются приближениями к точному решению и для них выпол няется следующее условие:
Этот алгоритм в своей основе имеет метод сопряженных градиентов для минимизации квадратичных функций и, если функция f(x) - квадратичная, полностью с ним совпадает. Его применение целесообразно для нахождения глобального (или локального) минимума сильно выпуклой функции f(x) (D . = Е), хеХ. Он предложен в [14], для параметра блочности 1 = 1 - в [35] и в несколько другой форме - в [15], [28]. Предлагаемый алгоритм будем называть "Блочный вариант метода сопряженных градиентов".
