Метод решения системы линейный уравнений звездчатого вида

[Schwungrad]

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

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

Звездчатый граф имеет форму дерева, а, следовательно, порождаемая им система линейных уравнений независима.

Можно заметить, что если число лучей равно 1-му или 2-м, то соответствующая система линейных уравнений имеет трехдиагональный вид. Для решения такой системы можно применить, например, метод прогонки.

Вопрос. Какой численный метод можно эффективно применить в случае, если число лучей звезды больше или равно 3-м?

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

[General]

А могли бы привести пример? Интересно.

[ewert]

Schwungrad в сообщении #284743 писал(а):

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

А я вот всё-таки предложу. Дело в том, что метод прогонки -- это и есть обычный метод Гаусса с обратным ходом, применённый к трёхдиагональной системе. У Вас же система почти трёхдиагональна, только одна из строк матрицы содержит дополнительные ненулевые элементы. Ну так сделайте эту строку последней и просто добавьте в каждый шаг прямого хода метода Гаусса обнуление заодно ещё и очередного элемента этой строки. Объём вычислений увеличится совсем не намного -- где-то на треть или типа того.

-- Вс янв 31, 2010 20:00:25 --

General в сообщении #284813 писал(а):

А могли бы привести пример? Интересно.

Я когда-то (лет десять или пятнадцать назад) сталкивался с такой задачей. Надо было рассчитать осесимметричные колебания мембраны такой формы: круг, от границы которого отходят в разные стороны два усечённых конуса. (Это ребята разрабатывали какой-то микрофон, и почему-то считали, что такая конструкция будет особо эффективной, а почему -- я не помню.) Так вот: если составить разностные уравнения колебаний в полярных координатах, то примерно такой трёхлучевой граф и получится.

[Schwungrad]

ewert в сообщении #284818 писал(а):

У Вас же система почти трёхдиагональна, только одна из строк матрицы содержит дополнительные ненулевые элементы.

На самом деле это не совсем верно. Поясню на примере случая, когда образующий систему линейных уранений граф имеет 3 луча:

$$ \xymatrix{ & & & & {\bullet} \ar@{-}[d] & & & & \cr & & & & {\bullet} \ar@{-}[d] & & & & \cr & & & & {\bullet} \ar@{-}[d] & & & & \cr & & & & {\bullet} \ar@{-}[d] & & & & \cr & & & & {\bullet} & & & & \cr & & & {\bullet} \ar@{-}[ur] & & {\bullet} \ar@{-}[ul] & & & \cr & & {\bullet} \ar@{-}[ur] & & & & {\bullet} \ar@{-}[ul] & & \cr & {\bullet} \ar@{-}[ur] & & & & & & {\bullet} \ar@{-}[ul] & \cr {\bullet} \ar@{-}[ur] & & & & & & & & {\bullet} \ar@{-}[ul] } $$

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

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

$$ \left( \begin{array}{cccccccccccc} * & * & & & & & & & & & & \cr * & * & * & & & & & & & & & \cr & * & * & * & & & & & & & & \cr & & * & * & & & & * & & & & *\cr % & & & & * & * & & & & & & \cr & & & & * & * & * & & & & & \cr & & & & & * & * & * & & & & \cr & & & * & & & * & * & & & & * \cr % & & & & & & & & * & * & & \cr & & & & & & & & * & * & * & \cr & & & & & & & & & * & * & * \cr & & & * & & & & * & & & * & * % \end{array} \right) {\bf x}= \left( \begin{array}{c} * \cr * \cr * \cr * \cr * \cr * \cr * \cr * \cr * \cr * \cr * \cr * \end{array} \right) $$

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

Теперь, как Вы предлагаете, делаем прямой ход прогонки, который, как и в классическом случае состоит из стандартной процедуры "изничтожения" нижней диагонали маленьких трехдиагональных матриц. В результате система примет вид:

$$ \left( \begin{array}{cccccccccccc} * & * & & & & & & & & & & \cr & * & * & & & & & & & & & \cr & & * & * & & & & & & & & \cr & & & * & & & & * & & & & *\cr % & & & & * & * & & & & & & \cr & & & & & * & * & & & & & \cr & & & & & & * & * & & & & \cr & & & * & & & & * & & & & * \cr % & & & & & & & & * & * & & \cr & & & & & & & & & * & * & \cr & & & & & & & & & & * & * \cr & & & * & & & & * & & & & * % \end{array} \right) {\bf x}= \left( \begin{array}{c} * \cr * \cr * \cr * \cr * \cr * \cr * \cr * \cr * \cr * \cr * \cr * \end{array} \right) $$

Теперь "изничтожим" элементы матрицы, которые ответственны за связь уравнений из разных блоков. Для этого, действуя стандартными элементарными преобразованиями из метода Гаусса, будем брать поочередно последнее уравнение из кадого блока и с его помощью обнулять элементы, находящиеся вне 2-х главных диагоналей. В результате матрица системы примет вот такой 2-х диагональный вид

$$ \left( \begin{array}{cccccccccccc} * & * & & & & & & & & & & \cr & * & * & & & & & & & & & \cr & & * & * & & & & & & & & \cr & & & * & & & & & & & & \cr % & & & & * & * & & & & & & \cr & & & & & * & * & & & & & \cr & & & & & & * & * & & & & \cr & & & & & & & * & & & & \cr % & & & & & & & & * & * & & \cr & & & & & & & & & * & * & \cr & & & & & & & & & & * & * \cr & & & & & & & & & & & * % \end{array} \right) {\bf x}= \left( \begin{array}{c} * \cr * \cr * \cr * \cr * \cr * \cr * \cr * \cr * \cr * \cr * \cr * \end{array} \right) $$

Итак, в каждом из выделенных скобками блоков, можно применить обратный ход прогонки:

$$ \begin{pmatrix} % \begin{pmatrix} * & * & & \cr & * & * & \cr & & * & * \cr & & & * \end{pmatrix} & & \cr & \begin{pmatrix}* & * & & \cr & * & * & \cr & & * & * \cr & & & * \end{pmatrix} & \cr & & \begin{pmatrix}* & * & & \cr & * & * & \cr & & * & * \cr & & & * \end{pmatrix} \cr \end{pmatrix} {\bf x}= \left( \begin{array}{c} * \cr * \cr * \cr * \cr * \cr * \cr * \cr * \cr * \cr * \cr * \cr * \end{array} \right) $$

ewert, большое спасибо за подсказку. Задачка хоть и простая, но я понял как ее решать, только прочитав Ваш ответ.

[Schwungrad]

General в сообщении #284813 писал(а):

А могли бы привести пример? Интересно.

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

1. Рассмотрим механическую систему, обладающую циклической симметрией. Для определения физической модели такой системы достаточно определить подсистему в одном единственном секторе с углом раствора $360^0/N$ , $N$ число симметрии системы. В предложенной мной задачке $N$ равно числу лучей звездчатого графа. Свойства полной системы определяются поворотом заданного сектора на угол кратный $360^0/N$ нужное число раз.

2. Элементом подсистемы является гармонический осциллятор: точечная масса + вязко-упругий элемент, пружина которого становится абсолютно жесткой при достижении деформации сжатия предельно допустимого значения. Механическим аналогом такого осциллятора является виток пружины сжатия, обладающий 2-я состояниями: упругим и жестким. При сжатии витка из разгруженного состояния до его блокировки считается выполненным закон Гука, а при достаточно сильном сжатии виток пружины заблокирован и представляет собой абсолютно жесткий элемент. Модель подсистемы в секторе состоит из цепочки таких гармонических осцилляторов. С одного конца цепочка жестко прикреплена к массивному носителю, который соответствует коневой вершине графа. На точечные массы и носитель действуют внешние силы.

3. Считается, что при движении состояние осцилляторов изменяется, т.е. осуществляются переходы упругость-жесткость. В жестком состоянии вязко-упругая сила заменяется силой реакции связей, которая определяется из уравнений кинематических связей (равенство ускорений) и уравнений движения. Это подход аналогичный лагранжиевым множителям, только неизвестными считаются не они, а контактные силы. Число неизвестных реакций связей считается равным числу независимых кинематических связей.

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

5. Считается, что на каждом шаге численного интегрирования такой системы ее топология (граф) не изменяется. Предложенная мной задача соответствует определению сил реакций связей, которые находятся из решения линейной системы алгебраических уравнений «звездчатого вида».