Диссертация (1149346), страница 6
Текст из файла (страница 6)
Из (4.5) получаем PT = g ωв виде ω T c=eT eωc + ω T b и умножая последнее соотношение слева на g, а за-тем используя определение матрицы Q, находим (5.3). Благодаря применению вформуле (5.3) только что установленного первого из соотношений (5.2), получаемвторое соотношение в (5.2). Теорема доказана.Определение: Матрица Q называется матрицей продолжения, а матрицаP — матрицей сужения.Рассмотрим сначала матрицу P, обозначая ее элементы (pji ): согласно опредеee T , так что pji = hgi , ωej i, i ∈ J, j ∈ J.лению PT = g ω3 Доказательствоаналогично доказательству теоремы 7 из [6], и приводится здесь для удобства читателя.47ej и принимая во внимание непреУчитывая расположение носителя функции ωрывность этой функции, ввиду определения (4.4) приходим к выводу, что в j-мстолбце матрицы PT ненулевыми окажутся разве лишь те элементы pji с номерамиi ∈ J из рассматриваемого столбца, которым соответствуют узлы ti , являющиесявнутренними точками упомянутого носителя, то есть внутренними точками телаe j : ti ∈ Se 0 .
Итак,звезды Sje0.при ti ∈/SjXej ici .hgi , ω[Pc]j =i∈J,ti ∈S0jpji = 0(6.1)(6.2)Обратимся теперь к матрице Q = (qj 0 k )j 0 ∈J,k∈J, где qj 0 k = hgej 0 , ωk i; очевидно,eчто в каждой строке этой матрицы имеется лишь одна единица, а остальные элементы — нули: в строке с номером j 0 ∈ Je единица находится на том месте, номерk которого является номером удаляемой вершины tk исходной триангуляции T .e поставим в соответствие номераНомерам вершин укрупненной триангуляции Tвершин исходной триангуляции T и это соответствие обозначим ϑ; итак,ϑ:Je → J,etj = t ϑ(j) .(6.3)e k ∈ J.j 0 ∈ J,(6.4)В этих обозначениях имеемqj 0 k = δϑ(j 0 ),k ,Непосредственным вычислением покажем, что произведение QPT представляетсобой единичную матрицу.
ИмеемXX[QPT ]j 0 j =qj 0 k pjk =δϑ(j 0 ),k pjk = pjϑ(j 0 ) .k∈Jk∈JВвиду соотношений (6.3) находимe0tϑ(j 0 ) ∈ Sj⇐⇒j 0 = j,так что из (6.5) благодаря соотношениям (4.1) и (4.5) получаем[QPT ]j 0 j = δj 0 ,j ;48(6.5)последнее соответствует тому, что матрица Q — левая обратная к матрице PT (см.теорему 20).Теорема 22:В условиях теоремы 16 формулы декомпозиции (5.2) могутбыть записаны в видеeecj = cϑ(j) ∀j ∈ J,Xej icϑ(j) ,bi = ci −hgi , ωe ti ∈Se0j∈J,j(6.6)∀i ∈ J,а формулам реконструкции (5.3) можно придать формуXej ieci =hgi , ωcj + bi ,∀i ∈ J.e ti ∈Se0j∈J,j(6.7)(6.8)Доказательство: Соотношения (6.6) получаются применением свойства (6.4)к первой из формул (5.2).Для второй формулы (5.2) с учетом соотношения (6.2) получаемXej iebi = ci − [PT Qc]i = ci − [PT ehgi , ωcj ∀i ∈ J,c]i = ci −e ti ∈Se0j∈J,jоткуда учитывая (6.6), выводим (6.7).
Формулы реконструкции (6.8) очевиднымобразом получаются из (6.7).2.5.Триангуляция, допускающая локальное укрупнениеВ дальнейших рассуждениях ограничиваемся прямолинейной триангуляцией икусочно-линейной аппроксимацией Куранта, т. е. в качестве генерирующей функции берем ϕ(t) = (1, [t]1 , [t]2 )T .Для определения подходящего варианта сплайн-всплескового разложения важно иметь возможность локально укрупнять триангуляцию (т. е. укрупнять ее лишьв некоторой подобласти Ω0 ⊂ Ω, оставляя нетронутыми треугольники вне этойподобласти); при этом результирующая триангуляция области Ω должна оставаться правильной (т. е. никакая вершина никакого треугольника не должна лежатьна стороне другого треугольника).
Оказывается, не каждую триангуляцию можнолокально укрупнять.49В этом пункте рассмотрена локально укрупняемая триангуляция, причем в области укрупнения укрупненная триангуляция снова может укрупняться; такимобразом, предлагаемый алгоритм укрупнения обладает рекуррентными свойствами: укрупнение можно проводить многократно. Предлагаемый далее алгоритмприменим не только к плоской области, но и к некоторым двумерным поверхностям: он годится для аппроксимаций курантова типа в случае цилиндрическойповерхности, тора и сферы.Сначала рассмотрим правильную триангуляцию плоскости {t | t = (x, y) ∈ R2 }(эта триангуляция может состоять из конечного или бесконечного числа треугольников).
Нас интересуют локальные укрупнения исходной правильной триангуляции (т. е. объединения конечного числа треугольников), приводящие снова к правильной триангуляции.Для описания триангуляции будем использовать таблицу инциденций, каждаястрока которой описывает треугольник перечнем инцидентных ему вершин. Иногда рассматривается таблица инциденций, получающаяся объединением нескольких таблиц инциденций. Заметим, что порядок объединения таблиц не имеет значения; также не существен порядок строк и порядок следования вершин в строкахрассматриваемых таблиц.Введем обозначенияdefZ2 = {(i, j) | i ∈ Z ∀j ∈ Z},defZ20 = {(2i, 2j) | i ∈ Z ∀j ∈ Z},defZ21 = {(2i + 1, 2j + 1) | i ∈ Z ∀j ∈ Z},22b 2 defZ= Z0 ∪ Z1 .Пусть фиксированы числа h0 > 0, h00 > 0.
Обозначим ri,j точки с координатами(ih 0 , jh 00 ), (i, j) ∈ Z2 , и рассмотрим прямоугольники вида Πi,j = {(x, y) | ih0 ≤ x ≤def(i + 2)h0 , jh00 ≤ x ≤ (j + 2)h00 }, где (i, j) ∈ Z20 .50Пусть триангуляция T ∗ , описывается трехстолбцовой таблицей (с бесконечнымчислом строк), получающейся объединением таблицrri+1,j ri,j+1 i,j ∀ (i, j) ∈ Z2 , ri+1,j+1 ri+1,j ri,j+1 где rk,l — радиус-векторы соответвтующих вершин треугольников триангуляции.Легко видеть, что триангуляция T ∗ не допускает локального укрупнения с сохранением правильности; дальше предлагается триангуляция, лишенная этого недостатка.Пусть X∗ — некоторое (конечное или бесконечное) множество пар четных целочисленных индексов: X∗ ⊂ Z20 ; рассмотрим замкнутую область[defΩ=Πi,j(i,j)∈X∗(в частности, если X∗ = Z20 , то Ω совпадает со всей плоскостью R2 ).Через X обозначим множество индексов (i, j) ∈ Z20 ∪ Z21 таких, что точки ri,j =(ih0 , jh00 ) лежат в Ω; только что упомянутые точки ri,j будем называть узламиисходной сетки, они являются вершинами определяемой ниже исходной триангуляции.Узел r2i0 ,2j0 называется внутренним узлом для Ω, если он является внутреннейточкой в Ω (таким образом, в Ω содержатся прямоугольники Πi,j при i ∈ {2i0 , 2i0 −2}, j ∈ {2j0 , 2j0 − 2}; здесь же заметим, что вводимое понятие относится толькок узлам с четными индексами).
Множество пар (i, j) ∈ X∗ , для которых ri,j —внутренний узел, обозначим X0 . Очевидно, чтоb 2.X0 ⊂ X∗ ⊂ X ⊂ Z51Рассмотрим триангуляцию, которая получается объединением таблицri,jr2+i,j r1+i,1+jr2+i,2+j r2+i,j r1+i,1+jr2+i,2+j ri,2+j r1+i,1+jri,jri,2+j r1+i,1+j∀(i, j) ∈ Z20 .(7.1)Укрупнение триангуляции будем производить объединением двух соседних (тоесть имеющих общую сторону) треугольников.
Полученные в результате треугольники будем называть укрупненными треугольниками.Не нарушая общности, в дальнейшем предполагаем, что r0,0 — внутренний узелв Ω, то есть (0, 0) ∈ X0 . Рассмотрим такое укрупнение, при котором вершину r0,0окружают лишь укрупненные треугольники. Для этого заменим перечисленныениже соседние треугольники на треугольник, получающийся их объединением.Эквивалентное преобразование таблицы инциденций состоит в том, что из нееисключаются строки, соответствующие объединяемым треугольникам, и добавляются строки, соответствующие результатам такого объединения — укрупненнымтреугольникам. Как было отмечено выше, расположение строк в таблице инциденций не существенно, и потому строки могут быть добавлены между любымистроками упомянутой таблицы.
Таким образом, достаточно перечислить выбрасываемые строки таблицы и указать вставляемые в нее строки. Однако, для наглядности преобразования таблицы инциденций будем задавать указанием двухстрок заменяемых треугольников (в левой от стрелки части формулы) и указанием строки укрупненного треугольника (в правой части формулы).52Укрупнение зададим следующим преобразованием таблицы инциденций.r 0,0 r−2,0 r−1,1 r−2,2 r−2,0 r−1,1r −2,2 r0,2 r−1,1 r0,0 r0,2 r−1,1r 0,0 r0,2 r1,1 r2,2 r0,2 r1,1r 2,2 r2,0 r1,1 r0,0 r2,0 r1,1r 0,0 r2,0 r1,−1 r2,−2 r2,0 r1,−1r 2,−2 r0,−2 r1,−1 r0,0 r0,−2 r1,−1r0,0r0,−2 r−1,−1r−2,−2 r0,−2 r−1,−1r−2,−2 r−2,0 r−1,−1r0,0r−2,0 r−1,−1−→ r0,0 r−2,0 r−2,2 ,(7.2)−→ r0,0 r0,2 r−2,2 ,(7.3)−→ r0,0 r0,2 r2,2 ,(7.4)−→ r0,0 r2,0 r2,2 ,(7.5)−→ r0,0 r2,0 r2,−2 ,(7.6)−→ r0,0 r0,−2 r2,−2 ,(7.7)−→ r0,0 r0,−2 r−2,−2 ,(7.8)−→ r0,0 r−2,0 r−2,−2 .(7.9)Легко видеть, что в результате получается правильная триангуляция.Исходную триангуляцию (7.1) обозначим T , описанную только что укрупненную (согласно формулам (7.2) — (7.9)) триангуляцию обозначим T0 , а переход отисходной триангуляции к укрупненной обозначим [T 7−→ T0 ].2.6.Структура барицентрических звезд на исходной иукрупненной триангуляцияхДля построения аппроксимации Куранта важна структура барицентрическихзвезд, соответствующих вершинам рассматриваемой триангуляции.Для исходной триангуляции имеется два типа барицентрических звезд: к пер53вому типу отнесем барицентрические звезды, содержащие четыре треугольника,а ко второму типу отнесем барицентрические звезды с восемью треугольниками.3.8.1.
Барицентрические звезды с четырьмя треугольниками соответствуют вершинам ri,j при (i, j) ∈ Z21 ; каждой такой вершине соответствует барицентрическаязвезда, описываемая следующей таблицей инциденцийri,jr2+i,j r1+i,1+jr2+i,2+j r2+i,j r1+i,1+jr2+i,2+j ri,2+j r1+i,1+jri,jri,2+j r1+i,1+j.3.8.2. Вершинам ri,j при (i, j) ∈ Z20 соответствуют барицентрические звезды стаблицей инциденций видаri,j r−2+i,jr−1+i,1+jri,j ri,2+jr−1+i,1+jri,j ri,2+jr1+i,1+jri,j r2+i,jr1+i,1+jri,j r2+i,jr1+i,−1+jri,j ri,−2+jr1+i,−1+jri,j ri,−2+jr−1+i,−1+jri,j r−2+i,2+j r−1+i,−1+jПри локальном укрупнении триангуляции на "границе укрупнения" появляются дополнительно новые типы барицентрических звезд, содержащих по шесть и повосемь треугольников, тогда как внутри зоны укрупнения типы барицентрическихзвезд сохраняются.543.9.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
