Консалтология Общая теория консалтинга (стр. 3 )

Модификации метода Ньютона. Итерации Ньютона могут не сходиться, если начальное приближение вектора неизвестных х0п+х, контролируемое консультантом консультируемой проблемы, окажется далеким от решения и, следовательно, определенное матрицей Якоби направ­ление сходимости будет значительно отличаться от истинного.

На практике применяют различные модификации метода Нью­тона. Так, для демпфирования колебаний составляющих век­тора х в процессе итерационного решения систем (8.2) и (8.3) ис­кусственно ограничивают величину шага приращения колеблю­щихся переменных:

(8.8)

где xi (m+1) — полученное из выражения (8.4) значений i-й компо­ненты вектора х; λ — демпфирующий параметр, выбираемый при сопоставлении на m-й и (m+1)-й итерации знаков погреш­ности определения той составляющей вектора х, которая обусловила максимум относительной погрешности на т-й итерации. При этом

λ = λ λ 0, если знак погрешности изменился, в противном случае λ=λ/λ 0. Если при оценке окажется, что λ>1, то выби­рается значение λ=1. Начальное значение λ также равно 1, а λ0 выбирается эмпирически

(λ0 ≈0,75).

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

i = i0(eθх-1)

заменяется парой уравнений:

где

Кроме того, при оценке приращений переменных математиче­ской модели консультируемой проблемы применяется модификация формулы (8.8), заключающаяся в выборе очередного приближения согласно сле­дующему выражению:

(8.9)

где

— знак приращения; r и k—эмпирические константы.

Для повышения сходимости и точности применяются также ите­рационные методы Ньютона, в соответствии с которыми

(8.10)

где

Если при анализе статического режима метод Ньютона не сходится к решению за заданное максимальное число итераций, то целесообразно перейти к одной из разновидностей метода продол­жения решения по параметру. Например, можно осуществить постепенный перевод консультируемой проблемы из априорно известного на­чального состояния в искомый статический режим введением специального параметра τ≤ (0≤τ≤1). При τ=0 решение уравне­ний модели проблемы известно, а значение τ=1 соответствует рассчи­тываемому режиму. Для каждого из фиксированных значений па­раметра τ решается частная задача статики. Метод Ньютона обла­дает локальной сходимостью, поэтому можно для достаточно малых значений приращений ∆τ гарантировать сходимость задачи нахож­дения статического режима, если система уравнений исследуемого проблемы непрерывно дифференцируема на всем интервале изменения τ. Выбор приращений ∆τ целесообразно осуществлять по процеду­ре, принятой для оценки локальной погрешности метода числен­ного интегрирования.

Решение линейных систем. Для решения базовой линейной си­стемы уравнений вида (8.6)

Ах = b (8.11)

часто используется метод последовательного исключения Гаусса или одна из его модификаций. Если правая часть b в уравнении (8.11) меняется многократно, то рекомендуется при­менять метод

LU-преобразования, в соответствии с которым матрица А решаемой системы уравнений представляется произведением нижней треугольной матрицы с единичной диагональю L и верх­ней треугольной матрицы U:

А = LU. (8.12)

При этом элементы матриц L и U определяются с помощью сле­дующей рекурентной процедуры:

где п — размерность решаемой системы уравнений (8.11), а симво­лами а, l, и обозначены элементы матриц A, L и U соответственно. Например, для s= 1, 2, 3 получаем соответственно:

(8.14)

После LU-преобразования матрицы А решение системы (8.11) заменяется последовательным решением двух систем линейных уравнений с треугольными матрицами:

(8.15)

которые решаются простой обратной подстановкой

(8.16)

(8.17)

Пример 1. Рассмотрим процедуру LU - преобразования на примере системы уравнений

Используя выражения (8.12) — (8.14), определяем

На основании формулы (8.15) и (8.16) строим частную систему уравнений для прямого хода решения

и получаем из нее у= [9, —7/2, 188/10]t.

Далее, пользуясь выражениями (8.15) и (8.17), формируем частную си­стему уравнений для обратного хода решения

из которой находим искомый вектор переменных

х =[4, 1, 2]t.

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

Дополнительно к способам кодирования, рассмотренным в разделе 6, применительно к процедуре LU-преобразования исполь­зуется кодировка по способу «строк и столбцов». В этом случае массив IС содержит индексы строк НЭ матрицы L и индексы столб­цов НЭ матрицы U, а в массиве VA последовательно размещаются НЭ столбцов матрицы L и строк матрицы U. Границы участков массивов IС и VA, соответствующие НЭ отдельных столбцов мат­рицы L и НЭ отдельных строк матрицы U, фиксируются в мас­сиве IR, длина которого увеличивается вдвое по сравнению с ра­нее рассмотренными. Дополнительно формируется массив IVА, в котором указываются номера ячеек массива VA, содержимое которых изменяется в процессе LU-преобразования матрицы А. Благодаря измененной форме «упаковки» матрицы, согласован­ной с последовательностью процесса LU-преобразования, отсут­ствуют логические операции и процедуры поиска обрабатываемых НЭ на каждом шаге вычислений. При этом формируемые элементы матрицы L и U записываются на позиции «обработанных» элементов матрицы А, что существенно экономит массив используемой па­мяти.

Необходимость принятия специальных мер для сохранения раз­реженности уравнений модели консультируемой проблемы в процессе их решения объясняется тем, что при LU-преобразовании матрицы А воз­можно появление новых ненулевых элементов (ННЭ). Количество ННЭ существенно зависит от того, какие из элементов матрицы A и в какой последовательности будут выбраны в качестве глав­ных (диагональных).

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

Существует большое количество стратегий упорядочения, пред­ставляющих собой n-шаговую процедуру, каждый шаг которой включает:

- выбор среди элементов матрицы А текущего главного элемента, удовлетворяющего критерию упорядочения и условия вычисли­тельной устойчивости;

- перестановку строк и столбцов матрицы А так, чтобы уже вы­бранные главные элементы лежали на главной диагонали;

- анализ полученной ненулевой структуры с целью определения позиций ННЭ и проведение соответствующей коррекции информа­ционных массивов.

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

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

(8.18)

где rj, сi — число НЭ соответственно в j-й строке и i-м столбце, расположенных в непреобразованной части упорядоченной мат­рицы А. Вес ωij соответствует максимальному числу ННЭ, кото­рые могут появиться, если в качестве главного будет выбран эле­мент аji.