Главная > Разное > Метод конечных элементов для радиоинженеров и инженеров-электриков
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

7.7. Способы нумерации

Известно множество методов перенумерации. Однако нет ни одного метода, гарантирующего действительно оптимальную нумерацию, хотя ряд методов в большинстве случаев обеспечивает достаточное приближение к оптимуму. Эта область еще развивается и поэтому проводить здесь детальный обзор нецелесообразно. Тем не менее, поскольку все существующие методы основаны на исследовании графического представления структуры матрицы, можно изложить несколько общих принципов.

Для левого графа на рис. 7.2 нумерация лучше, чем для правого, потому что разности номеров переменных меньше. Соответственно ненулевые элементы матрицы группируются наиболее плотно около главной диагонали. При хорошей нумерации узлы с существенно разными номерами сильно разнесены. Такое разделение получается, если все узлы уровня пронумерованы раньше, чем узлы уровня Другими словами, если начальный узел обозначен номером 1, то следующими должны быть пронумерованы члены уровня затем — члены уровня и так далее до последнего уровня. Хотя основной принцип достаточно прост, остается неясным, как выбрать начальный узел и как нумеровать члены в пределах данного уровня. Один из эффективных методов состоит в выборе начального узла с минимальным числом соединений. Структура уровней формируется далее, начиная с этого узла. Затем в пределах каждого уровня первыми нумеруют те члены, которые непосредственно соединены с наименьшими номерами следующего уровня. Разумным объяснением такого подхода является то, что чем больше задерживается нумерация отдельного узла или переменной, тем меньше разница индексов между ним и членами следующего уровня. Подобная нумерация означает, что подавляющее число соединяющих линий будет иметь малые разности Несмотря на то что это рассуждение

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

Возвращаясь к рис. 7.2 и структуре уровней (7.28), видим, что узлы имеют следующие числа соединений с узлами более высокого уровня:

Нетрудно убедиться, что нумерация левого графа на рис. 7.2 выполнена вышеизложенным методом.

Из формул (7.28) и (7.29) можно увидеть, что наилучшая нумерация получается при таком выборе начальной точки, который дает много уровней, каждый из которых содержит всего несколько узлов. Это наблюдение приводит к другой группе методов, в которых по структуре матрицы определяется ее топологический диаметр и у одного из концов истинного диаметра выбирается начальный узел. Несмотря на то что объем работы в этом случае существенно увеличивается за счет дополнительных операций по определению диаметра, дополнительные усилия такого рода обычно компенсируются уменьшением затрат на решение уравнений.

<< Предыдущий параграф Следующий параграф >>
Оглавление