Cтраница 3
Все процедуры для решения систем уравнений с произвольными матрицами основаны на представлении исходной матрицы А в виде произведения LU, где L - нижняя треугольная и U - верхняя треугольная с единичной диагональю. Для разложения матрицы использован алгоритм с частичным выбором главного элемента. Он напоминает алгоритм исключения Гаусса, который, правда, приводит к нижней треугольной матрице с единицами по диагонали. [31]
Поскольку недозаполненный узел содержит f т / 2 - - 2 имен после исключения, этот узел, его минимально заполненный брат и их разделитель в узле-отце могут быть объединены в один узел с т - 1 или т - 2 именами. Теперь узел, содержащий V, стал недозаполненным, и этот же процесс повторяется в следующем более высоком уровне дерева. В худшем случае алгоритм исключения завершается в корне; тогда высота дерева может уменьшиться на один ярус, как в нашем примере. Когда мы объединяем V с его левым братом Е, К. [32]
Первый из этих методов редукции базируется на классическом принципе квазистационарности. В исходной схеме по части переменных ( как правило, промежуточные вещества) дифференциальные уравнения заменяются алгебраическими. В последние годы разработаны алгоритмы исключения промежуточных веществ и в случае нестационарного протекания реакции. [33]
Рассмотрим класс экстремальных задач, в которых имеются ограничения на суммарное количество некоторого ресурса. Фор-мальдо такое ограничение отражено в задаче условиями интегрального типа ( см. табл. II2 строка 1) или их конечномерными аналогами. Выделение этого класса задач оправдано тем, что задачи такого рода весьма часто встречаются в технике и, в частности, в химической промышленности. Кроме того, это рассмотрение позволяет дать примеры конкретизации вычислительных алгоритмов, приведенных ранее в канонической форме. Наконец, для этих задач очень полезна специфическая комбинация алгоритма исключения зависимых переменных и алгоритма проектирования градиента. [34]
Качественно, матрица А является почти вырожденной, а А нет. Если мы заменим последний элемент в А единицей или сделаем еще где-нибудь соответствующее маленькое изменение элементов этой матрицы, то она станет вырожденной. Но причины, почему хорошая обусловленность А была испорчена алгоритмом исключения, и средство против этого видны уже теперь. [35]
Простые случаи - удаление терминальных вершин или вершин только с одним потомком. Если же от исключаемой вершины отходят два поддерева, то, как и раньше, она заменяется на самую правую вершину ее левого поддерева. Как и в случае включения (4.63), вводится булевский параметр-переменная h, указывающий, уменьшилась ли высота поддерева. Балансировка идет, только если h - истина. Это значение присваивается переменной h при обнаружении и исключении какой-либо из вершин или уменьшении высоты какого-либо поддерева в процессе самой балансировки. В программе (4.64) в виде процедур мы вводим две ( симметричные) операции балансировки, поскольку обращение к ним встречается более чем в одной точке алгоритма исключения. Отметим, что balanceL используется при уменьшении высоты левого поддерева, a balanceR - правого. [36]