V Канатников и др. Дифференциальное исчисление функций многих переменных (1081393), страница 37
Текст из файла (страница 37)
Сравните скорость сходи мости двух методов. 10. ИНТЕРПОЛИРОВАНИЕ ЭУН~ЦИЙ МНОГИ~ ПЕРЕМЕНН~,|~~ 10.1. Интерполяционные сплайны первой степени Рассмотрим задачу восстановления функции двух перемен ных по известным значениям в заданных точках. Иначе говоря задача состоит в том, чтобы построить функцию Дх,у), дл„ которой ~(х;,у;) = Д, г = О, И. Отметим, что в общем случае определить однозначно функцию по ее значениям в конечнои наборе точек нельзя, и речь может идти лишь о некотором приближенном восстановлении функции. На плоскости хОу построим многоугольник М, вершинами которого является часть точек Р;. При этом предполагаем. что те точки Р;, которые не являются вершинами, расположены внутри многоугольника М.
Такой многоугольник можно выбрать не единственным способом (рис. 10.1). Соединяя подходящим образом точки Р; отрезками, мио гоугольник М можно разделить на некоторое количество тре угольников. Это можно сделать так, что вершинами треуголь ников будут точки Р;, и только они. Описанное разделение 10.1. Интерполяционные сплайны первой степени 275 «16 . гоугольника М на треугольники называют триангуля- ~Ф е4 многоугольника.
На рис. 10.2 показаны возможные триангуляции многоугольника изображенного на рис 10 1 б Рис. 10.2 Пусть для заданного множества точек Р;(х;;у;) выбраны многоугольник М и триангуляция этого многоугольника, состоящая из треугольников Ь,, 1= 1, К. Тогда на многоугольнике М можно задать такую функцию 8(х,у), которая на каждом треугольнике Ь является линейной функцией, т.е. 8(х,у) = а,.х+6~у+с,, (х; у) Е Ь', З =1, К, (10.1) где Ь' — замкнутое множество, ограниченное треугольником Ь; (т,е. внутренность треугольника плюс сам треугольник), и удовлетворяет условиям в(х;, у;) = Д, ~ = О, Ф. Графиком этой функции является поверхность в пространстве, составленная из треугольников с вершинами в точках р,'(х;; у;; Д) (рис. 10.3). Отметим, что функция в(х,у) непрерывна на многоугольнике М, Ее называют интерпол,яционным стиювйном пер- вЖ атпепени двух переменных.
Очевидно, что вид интерполяционного сплайна зависит От того, как выбран многоуголь- ф'* Ь»»»»» "ик М и как выполнена его три- »»:» аигуляция. При заданном много- А Угольнике М и его триангуляции "итерполяционный сплайн первой степени опрелелен единственным образом. Рис. 10.3 10. ИНТЕРПОЛИРОВАНИЕ ФУНКЦИЙ Чтобы вычислить значение 8(х, у) интерполяционного спл й на в произвольной точке (х; у) Е М, нужно определить верщинь, Рь Р~, Р,„треугольника Ь~, в который попала точка (х;„) а затем вычислить значение 8(х,у) согласно формуле (10 11 /1 используя заданные значения Д, ~~, ~ для определения к0 эффициентов а,, б~, с в (10.1).
Остановимся на описанн0„" процедуре подробнее. Отметим, что площадь 5 треугольника Р1 РгРз в плоскости хОу с вершинами Рсхд у;) может быть вычислена по формул 5= 0,5~Ь(Р1,Рг, Рз)~, где х1 у1 1 хг уг 1 уз Ь (Р1, Рг, Рз) = При этом знак определителя указывает на направление обхода точек Р1, Рг, Рз в плоскости хОу: если Ь(Р1,Рг,Рз) > О, то обход трех точек в последовательности Р1, Рг, Рз совершается против часовой стрелки. Действительно, рассмотрим в пространстве тетраэдр с вершинами РЯх;; у;;О), ~ = 1,2,3 и ч(0; 0; — 1) (рис.
10.4). Основанием этого тетраэдра является треуголь- О ник Р1РгРз, а его высота, опушен- У Р нам на это основание, равна еди- 1 нице. Поэтому его объем ~ равен трети произведения площади осноРис. 10.4 вания 5 на высоту, т.е. численно равен трети площади основания. В то же время объем тет раэдра можно записать с помощьв смешанного произведении трех векторов, направленных по трем смежным ребрам те' — — — + траэдра: ~= -!Ф~ ОРг ЯРз~ Так как Я~;=(х;;у;;1), ~= 1,2,3, то, используя представление смешанного произведени~ в прямоугольных координатах, получаем 1~ = -~Ь(Р1, Рг, Рз)~ Следовательно, Я = 3~ = 0,5~Ь(Р1, Рг, Рз) ~.
Отметим, что ес'и обход точек Р~, Рг, Рз совершается против часовой стрелки. т~ 1Р.1, Интерполвцнонные сплайны первой степени 277 тро ойка векторов ЯМ1, Я~г, ЯРз является правой, а смешанное оизведение положительно. А если точки Р1, Рг, Рз обходятся ? ? часовой стрелке, то тройка векторов ЯУ1, ЯРг, ЯРз является вой и смешанное произведение этих векторов отрицательно.
Упорядоченную тройку точек (Р1, Рг, Рз) в плоскости хОу, лежащих на одной прямой, назовем яровой тройкой то- ~е~р, если обход этой тройки совершается против часовой горелки. В противном случае эту тройку назовем левой двойкой точек. Если тройка точек (Р1, Рг, Рз) являет- ся правой, то проверить, попадает Рз ли точка Р(х; у) внутрь треугольника Р|РгРз, можно следующим образом. Точка Р попадает в треуголь- Р ник Р1 РгРз тогда и только тогда, ко- Рг гда все три тройки точек (Р, Рг, Рз), (Р1, Р, Рз), (Р1, Рг, Р) являются пра; выми (рис. 10.5).
Рис. 10.5 Для данного набора точек Р;(х;; у;), 2 = О, Х, фиксируем многоугольник М и его триангуляцию, задавая тройки номе- ров вершин каждого треугольника Р»Р1Р,„. При этом порядок вершин треугольников установим так, что они будут обходить- ся против часовой стрелки (т.е. обход вершин треугольника Р»Р1Р,„в порядке Р», Р1, Р совершается против часовой стрел- Ки). Произвольная точка Р(х; у) б М попадает лишь в один из треугольников заданной триангуляции (если не оказывается на границе между треугольниками).
Этот треугольник можно выявить, проверяя для каждого треугольника Р»Р~Р триангу- ляции неравенства ' светим, что если эти неравенства выполнены для некоторых индексов Й, 1, т, причем одно из неравенств на самом деле является равенством, то точка Р попадает на сторону 10. ИНТЕРПОЛИРОВАНИЕ ФУНКЦИЙ 278 треугольника. Например, если Ь(Р~, Р~, Р) = О, то точка Р и ходится на стороне Р~Р]. Точки ©(х;;у;;х;), г = 1,2,3, и Я(х;у; г) лежат в одной — ч плоскости тогда и только тогда, когда векторы Я~ц, Ч]Ч ц]Яз компланарны, т.е. Х вЂ” х] хя х] ХЗ-Х] У вЂ” У] х — 2] Уз -У] Уз — У] хз — х] Нетрудно увидеть, что значение определителя в левой части равенства совпадает со значением определителя у — у] х — х] О у~-у] гр-г] О Уз — У1 хз — ~1 у] х] 1 Х вЂ” х] Х~ — Х] ХЗ вЂ” Х1 х у г 1 х] у] х] 1 хз у~ х~ 1 хз уз хз (10З) Если точка Р(х; у) попадает в треугольник Р~Р~Р выбранной триангуляции многоугольника М, то значение 8 = 8(х,У) интерполяционного сплайна в зтой точке можно определять ис ходя из условия, что тОчки Ч1(х~', у~, 'Д), 3 = Й, 1, ш, и Ч(х; У лежат в одной плоскости.
Используя условие (10.3), после со ответствующей перестановки столбцов определителя получае]] Этот определитель четвертого порядка можно преобразовать, выполняя операции над его строками. Прибавляя последнюю строку последовательно к первой, второй и третьей строкам, а затем переставляя строки, приходим к следующему критерию принадлежности четырех точек Ч], Яз, Яз и Я одной плоскости: 279 10.1. Интерполяцнонные сплайны первой степени уР равнение 8 х у 1 Ь Л ~1 В 1 Утв ~тл уш С помощью разложения определителя в левой части уравнения „,> первому столбцу, приходим к следующему уравнению: зЯРь Р1, Р ) — Ь~ (Р, Рь Р ) + +Ьь(Р1 Р~Р,.) — 1~И,Р,Р~Р1) = 0. Из этого уравнения следует, что так как Ь(Р1„Р~, Р ) = 0 и Ь(Р~, Р1,,Р~) = 0 (зти определители "~4еют две одинаковые строки).
Отметим, что значение ЯР~,Р1, Р ), равное удвоенной площади треугольника Р1,Р1Р, отлично от нуля. Нетрудно убедиться прямой проверкой, что равенство (10.4) дает искомое представление интерполяционного сплайна первбй степени. Действительно, правая часть в (10.4) определяет линейную функцию координат т и у точки Р, так как линейными относительно переменных х и р являются выражения 4(Р,Р1,Р„,), Ь(Рь, Р,Р„„) и Ь(РьР~, Р). Эта функция в точках Р й, Р~, Р имеет заданные значения. Например, 280 30. ИНТЕРПОЛИРОВАНИЕ ФУНКЦИИ Обратим внимание на то, что выявление треугольник в который попадает заданная точка Р, и вычисление значе„„ ч н ния интерполяционного сплаина в этои точке основаны на одних хи тех же величинах.
Поэтому два этапа вычисления интерпол„ ционного сплайна можно объединить в одну процедуру. Если интерполяционный сплайн первой степени строит „ для приближения некоторой функции Дх,у) по ее известным значениям, то естественным является вопрос о погрешности т кого приближения. Пусть точка Р(х; у) попала в треугольни„ Р~Р~Р .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
