Математика и САПР

MATHEMATIQUES ET CAO

Volume 1

METHODES DE BASE

par

Patrick Chenin

Michel Cosnard

Yvon Gardan

Francois Robert

Yves Robert

Patrick Witomski

Volume 2

FORMES A POLES

par

Paul de Faget de Casteljau

Collection dirigee par Yvon Gardan Professeur, Universite de Metz

Hermes Publishing

Математика и САПР

В двух книгах Книга

ОСНОВНЫЕ МЕТОДЫ ТЕОРИЯ ПОЛЮСОВ

Перевод с французского канд. физ.-мат. наук С. Д. Чигиря

под редакцией д-ра физ.-мат. наук Н. Г. Волкова

Москва «Мир» 1988

ББК 32.97

мзз

УДК 681.3.082.5

Авторы: Шенен П., Коснар М., Гардан И., Робер Ф., Ро- бер И., Витомски П., Кастельжо П.

Математика и САПР: В 2-х кн. Кн. 1. Пер. с франц./ МЗЗ Шенен П., Коснар М., Гардан И. и др.-М.: Мир, 1988-204

" ISBN 5-03-000417-3

Книга французских специалистов посвящена математическим основам методов графического построения кривых и поверхностей, используемых в САПР. Излагаются методы интерполяции, аппроксимации, сглаживания, метод конечных элементов и метод конечных разностей.

Для специалистов в области САПР и студентов высших учебных заведении.

2404000000-319

М—————————185-88,4. 1

041(01)-88

Редакция литературы по информатике и робототехнике

ББК 32.97

ISBN 5-03-000417-3 (русск.)

ISBN 5-03-000464-5 (русск.)

ISBN 2-88601-042-6 (франц.)

© Hermes Publishing, 1985

© перевод на русский язык, «Мир», 1988

ПРЕДИСЛОВИЕ РЕДАКТОРА ПЕРЕВОДА

Благодаря развитию ЭВМ все большее значение в технике и технологии приобретают системы автоматизированного проектирования (САПР). Эти систе- мы содержат программные и аппаратные средства, назначением которых являет- ся автоматизация рутинной части работы конструктора и проектировщика. На компьютер возлагаются многие операции, начиная от изготовления чертежей и кончая оптимизацией проекта в целом. САПР существенно увеличивает произво- дительность труда инженера, изменяет его характер и открывает ранее недоступ- ные возможности новых технических решений. Недалек тот день, когда результа- том работы конструкторского бюро будет не комплект технической документа- ции, а программа для ЭВМ, управляющая работой автоматической линии, системой роботов или станков с числовым программным управлением.

Для обеспечения функционирования систем автоматизированного проектиро- вания необходимо создание соответствующих пакетов прикладных программ, которые можно разделить на два типа. К первому типу относятся программы прикладного характера (расчет конкретных конструкций, компоновка сложных узлов и т. д.). Ко второму типу можно отнести пакеты программ универсального характера, используемые в любых приложениях. Это программы, реализующие методы вычислительной математики (численное решение алгебраических и диф- ференциальных уравнений, минимизация функций, интерполяция и т. д.), про- граммы построения изображений, выводимых на дисплеи и графопостроители, сервисные программы. Их создание может осуществляться независимо от конк- ретных приложений, и они представляют интерес для всех разработчиков и пользователей САПР.

Предлагаемая вниманию советского читателя книга посвящена описанию математических моделей, встречающихся в задачах САПР. Основное внимание уделяется методам представления плоских и пространственных кривых и поверх- ностей. В части 1 книги изложены теоретические основы построения проекций в двумерном и трехмерном пространствах, методы интерполяции и аппроксимации кривых и поверхностей с помощью различных функций, в том числе с помощью многочленов и сплайнов, и метод конечных элементов. Кратко описаны числен- ные методы решения линейных и нелинейных алгебраических и дифференциаль- ных уравнений, используемых при построении моделей кривых и поверхностей. Часть 2 полностью посвящена теории полюсов—оригинальному методу полино- миальной интерполяции и сглаживания.

Материал, представленный в книге, традиционно входит в учебные пособия по вычислительной математике, однако данная книга не является еще одним пособием на эту тему. В большинстве книг по численным методам значительное внимание уделяется теоретическому обоснованию (доказательству сходимости, единственности, устойчивости и т.п.). Эта же книга носит сугубо практический характер (насколько это можно говорить о математике). Авторы много внимания уделяют практическим аспектам предлагаемых методов (часто проводят сопо- ставление теоретических и практических свойств). Это очень важно, так как теоретические оценки методов имеют нередко весьма отдаленное отношение к их практическим свойствам. Так, например, оценка скорости сходимости, как пра-

6 Предисловие редактора перевода

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

Хотя, как уже говорилось выше, книга содержит традиционные вопросы вычислительной математики, ее нельзя считать учебным пособием. Более того, в ряде случаев, особенно в ч. 2, от читателя требуется свободное владение числен- ными методами. Ее можно использовать скорее как справочное пособие. Основ- ная ценность книги заключается в полноте изложения вопросов, связанных с графическим представлением данных, в анализе и сопоставлении практических аспектов различных методов графического изображения кривых и поверхностей. Книга содержит много рабочих формул, на основе которых можно построить алгоритмы и программы для ЭВМ. Для читателей, желающих более подробно ознакомиться с теоретическими основами численных методов, можно рекомендо- вать следующие книги: Самарский А. А. Введение в численные методы.-М.:

Наука, 1982; Калиткин Н.Н. Численные методы.-М.: Наука, 1978; Стечкин С. Б., Субботин Ю.Н. Сплайны в вычислительной математике.-М.: Наука, 1976.

Книга рассчитана на широкий круг математиков и инженеров-разработчи- ков САПР, а также студентов соответствующих специальностей вузов.

Н. Г. Волков

Часть 1

ОСНОВНЫЕ МЕТОДЫ

П. Шенен, М. Коснар, И. Гардан, Ф. Робер, И. Робер, П. Витомски

ПРЕДИСЛОВИЕ АВТОРОВ

В распоряжении разработчика систем автоматизированного проектирования (САПР) имеются вполне определенные математические средства для создания математических моделей объектов. Выбор средств и моделей оказывает сущест- венное влияние на свойства САПР, которое может быть более или менее заметным при практическом применении САПР. Так, при использовании функций Безье или в-сплайнов для представления кривых и поверхностей даже неспециа- лист по информатике увидит различия. Например, если изменится положение одной из обрабатываемых точек, в случае использования функций Безье будет прослеживаться тенденция к изменению кривой или поверхности на всем протя- жении, а в случае использования Д-сплайна - только в окрестности точки. Мате- матическая модель может оказывать на практические результаты непредвиденное влияние, если ее свойства заранее неизвестны. Во всяком случае необходимо выбирать модель, обладающую вполне определенными характеристиками и возможностями.

Математическим основам САПР посвящено большое число работ, приведен- ных в списке литературы в конце книги. Мы попытались здесь дать единое представление о фундаментальной математической базе, на которой построена САПР.

Целью данной части книги является введение в математические основы, охватывающие все главные направления разработок САПР без излишних подроб- ностей. В гл. 1 освещены основные проблемы графического представления информации, а в гл. 2-проблемы обработки кривых и поверхностей. В ней наряду с описанием некоторых наиболее полезных методов (5-сплайны, функции Безье и т. д.) показаны задачи, для решения которых требуется применение этих методов, а также приведены сами решения. В двух последних главах рассмотрены методы решения систем линейных и нелинейных уравнений и метод конечных элементов.

Глава 1

Основы графического представления информации

1.1. ВВЕДЕНИЕ

Одним из технических средств САПР являются интерактивные мето- ды графического представления информации [2]. При их разработке используются определенные математические знания, в частности умение вычислять некоторые величины (расстояния, площади и т. д.), осуществ- лять переход от одного пространства к другому (от реального прост- ранства к пространству экрана дисплея, от трехмерного пространства к двумерному), выполнять геометрические преобразования, создавать ма- тематические модели на основе геометрических свойств объектов.

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

• основные операции машинной графики (пространственные преобразо- вания, нормировка и т.д.);

• преобразования на плоскости, определение расстояний, периметров и т.д. в двумерном пространстве;

• геометрические и перспективные преобразования, определение пересе- чений объектов и т. д. в трехмерном пространстве.

Кроме того, кратко изложены методы, с помощью которых создают- ся математические модели геометрических объектов.

1.1.1. Основные сведения из матричной алгебры

Матрица представляет собой таблицу вида

-^ll •xl2 xl3 ••• xln ^ х^ х^ Хдз ••• х^п xpl xp2 xp3 • • • xpn

состоящую из р строк и п столбцов. Элементы матрицы обозначаются Хц, где г-номер строки, у-номер столбца.

Матрицу, состоящую из одной строки или одного столбца, будем называть вектором, например:

V= \v^ v^ 1)3... г„ |-вектор-строка, Wi W= 2 - вектор-столбец. w?

Матрицы, состоящие из р строк и п столбцов, образуют векторное

Основы графического представления информации 9

пространство размерностью рп. Базис пространства образуется матри- цами ?y, единственный отличный от нуля (и равный 1) элемент которых находится на пересечении ;-й строки и j-ro столбца. Любую матрицу можно разложить по базису:

x=i i х,Е,.

1=1 J=l

Матрицей Х\ транспонированной по отношению к X. называют матрицу, для каждого элемента которой х\, справедливо соотношение

х'ц = х,., для i = (1, ..., р), j = (1, .... п).

Матрица, для которой X' = X, называется симметричной. Матрица, для которой X' = — X, называется антисимметричной. Две матрицы Х размерностью (р, п) и У размерностью (s, t) равны тогда и только тогда, когда

(р =s V;e(l,/»), \n=t У/б(1,п), -Yy=^..

Сумма двух матриц W= Х + Y, имеющих одинаковое число строк р и столбцов п, определяется следующим образом:

V; е (1, р). У/ е (1, я), н',, = -Vy + у„.

(Вычитание определяется аналогично.)

Произведение W= Х • У матрицы X, имеющей р строк и п столбцов, на матрицу У, имеющую п строк и т столбцов, определяется по следующему правилу:

п Vfe(l,^), V/e(l,m), Wy = ^ х^. k^l

Произведение W=s-X скаляра .? на матрицу Х определяется выраже- нием

Уге(1,/?), У/е(1,и) ^ц=д-Хц.

Напомним еще несколько важных свойств матриц:

• произведение матриц обладает свойствами ассоциативности и дистри- бутивности справа и слева по отношению к сложению;

• для двух матриц Х размерностью (р,п) и У размерностью (s,t) произведение Х • У существует, если п = s.

1.1.2. Основные сведения об однородных координатах

Объект из и-мерного пространства может быть представлен в п + 1- мерном пространстве. При переходе от w-мерного к п + 1-мерному пространству каждому объекту О может быть поставлено в соответствие бесконечное число его представлений О'. Однородные координаты пред- ставляют собой один из способов такого перехода, когда добавляется

10 Глава 1

одна дополнительная координата (называемая масштабным фактором) так, что

• представление в трехмерном пространстве двумерного вектора (х,у), соответствующего, например, точке на плоскости, задается следующими координатами:

(sx, sy, s),

где s -ненулевой скаляр;

• представление 3-мерного вектора (x,y,z), соответствующего, напри- мер, точке в пространстве, в 4-мерном пространстве задается следую- щим образом:

(sx, sy, sz, s),

где д- ненулевой скаляр.

В однородных координатах компоненты вектора (а, Ь, с) при его проекции на плоскость и вектора (а, Ь, с, d) при проекции на трехмерное пространство определяются соответственно

(ale, Ь/с)

и

(aid. bid, cfd).

Строго математически скаляр s при переходе от и-мерного к п + 1- мерному пространству выбирается произвольно при единственном усло- вии-он должен быть отличен от нуля. Однако при использовании численных методов могут возникнуть некоторые другие ограничения:

• Результатом преобразования должны быть числа, которые могут быть использованы в качестве координат. Например, если устройство отобра- жения работает только с целыми числами (или по любой другой причине необходимо работать только с ними), для произвольного s, например д = 1, нельзя представить точку с координатами (0,5; 0,1; 2,5). Однако при разумном выборе s можно достичь того, что однородные координа- ты будут целыми числами. В частности, если для приведенного случая взять д = 10, однородные координаты точки становятся целыми (5, 1, 25, 10).

• Результаты преобразования не должны приводить к арифметическому переполнению. Оставаясь в представлении целых чисел и зная, что диапазон их значений в ЭВМ составляет-216 — 216, для преобразования точки с координатами (80000, 40000, 1000) можно выбрать, например, значение параметра s = 0,1.

1.2. ДВУМЕРНОЕ ПРОСТРАНСТВО (ПЛОСКОСТЬ)

Вычисления в плоскости не представляют труда и основаны на понятиях планиметрии и аналитической геометрии. Мы ограничимся напоминанием основных сведений, рассмотрим примеры вычислений в ортонормированном базисе и проанализируем свойства рассматривае- мых алгоритмов.

Основы графического представления информации 11

1.2.1. Основные операции

Преобразование координат пространства в координаты экрана дисплея

Одна из особенностей геометрического моделирования состоит в том, что оно позволяет пользователю работать в своем собственном пространстве, не заботясь о последующем представлении информации на экране. Для связи пространств пользователя и экрана в них выделя- ются окна прямоугольной формы, края которых параллельны коорди- натным осям. Переход от одного пространства к другому состоит в определении соотношения между точками с координатами (Хд, Уд) в окне пользователя и (Ху, Y,) в окне экрана (рис. 1.1).

Окно поийзоеателя Хлв Окно экрана Хзв

_________ f ав ________ ^эв + + Лд лэ xпн Уд KW У, Ум Уан

Пространстео пользователя пространство жрана

Рис. 1.1. Окно пользователя и окно экрана.

Окно пользователя определяется координатами нижнего левого (Х^, Уди) и верхнего правого (Х^д, Уда) углов, окно экрана-аналогично (Хдд, У,,) и (Х,„, У„).

Из очевидных соотношений -УЭ ~ -^ЭН __ -^П ~ ^ПН У) ~ ^ЭН __ ^П ~ ^ПН -"ЭВ ~ -"ЭН -"ЧВ ~ "ПН *ЭВ —— ^ЭН -ПВ — ^ПН

легко получаем выражения для связи координат

Х,=АХ^+В, У,=Л'У„+Я и Z„ = СХ., + D, У„ = С'У, + D'.

Поиск пересечений

Пересечения плоских объектов находятся с помощью правил анали- тической геометрии на плоскости. Рассмотрим в качестве примера пересечение двух прямых, заданных уравнениями:

AX+BY+C=0, (1)

A'X + ffY+ С = 0. (2)

Очевидно, надо решить простую систему из двух уравнений с двумя неизвестными. Сначала вычислим определитель

DET = АВ' - ВА'.

Если | DET | < EPS, прямые считаются параллельными (EPS - очень малая величина), в противном случае координаты точки пересечения

12 Глава 1

определяются выражениями

X^=(C'B-CB')/DET,

I,NT = (CA' - AC')/DET.

Замечание. Использование однородных координат позволяет решить задачу в общем виде, охватывающем случай параллельных прямых. Действительно, запишем уравнения (1) и (2) в виде

АХ + BY+CW=0,

A'X + B'Y+C'W=0.

Точку пересечения этих прямых можно представить в виде вектора1)

Р = ((С В - СВ'), (CA' - АС), (АР - ВА')).

Точке, находящейся на бесконечности, будет соответствовать третья координата, равная нулю.

Пересечение окружности С с известными координатами центра (Хр, Yc) и радиусом R и прямой D. Запишем уравнения окружности и прямой в виде

(X-Xc)2+(Y-Yc)2=R2, (3)

AX+BY+C=0. (4)

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

AXc+BYc+C^^

^/А2 + В2

Если это условие выполняется, для решения задачи достаточно решить систему уравнений (3) и (4). Введем обозначения: DELTA = ^/R2 (A2 + В2) - (АХс + BYc + Q2, Ti = ВХс - AYc + DELTA, Т, = ВХс -AYc- DELTA. Тогда для двух решений имеем {X^iBT^-AQ^+B2), [ Y, = (- AT, - BQ/(A2 + В2); ^X^tBT^-AQ^+B2), [ Y^i-AT^-BQ^+B2). Пересечение двух окружностей, заданных координатами центров (Х^, Y^) и (Х^, Y-i) и радиусами R^ и R^. Сначала необходимо проверить, что окружности не являются концентрическими (т. е. расстояние между 1) С точностью до постоянного множителя W/DET, несущественного в однородных координатах.- Прим. перев. Основы графического представления информации 13 их центрами больше EPS). После этого находим выражение для ради- кальной оси11 окружностей и задача сводится к предыдущему случаю: отыскиваются точки пересечения (если они существуют) радикальной оси и одной из окружностей. Замечание 1. Обычно предметом поиска являются точки пересечения отрезков и дуг, поэтому необходимо проверять, что найденные точки пересечения прямых и окружностей принадлежат рассматриваемым отрезкам и дугам. Замечание 2. Примеры, приведенные выше, иллюстрируют лишь используемые методы. При рассмотрении аналогичных геометрических свойств и понятий аналитической геометрии в трехмерном пространстве мы к подобным примерам возвращаться больше не будем. 1.2.2. Поиск решения при наличии ограничений В большинстве двумерных систем в задачах с ограничениями отыски- ваются точки, окружности или дуги окружностей, прямые или отрезки прямых и реже кривые. В качестве примера можно привести задачу отыскания отрезка, касательного к двум заданным окружностям. Задача может не иметь решения, или можно найти 2 или 4 отрезка, удовлетво- ряющих ее условию. Неоднозначность устраняется за счет дополнитель- ной информации, например задания точки, вблизи которой должен пройти отрезок [2]. Задача с ограничениями в общем виде может быть определена так: (тип искомого объекта) (список ((ограничений) (элементов, на которые распространяются ограничения))). Решение такого типа задач сводится, вообще говоря, к решению довольно сложных систем уравнений. Однако решение удается упрос- тить сведением его к определенным частным случаям. Таким образом, можно предложить два общих метода решения этой задачи. Решение системы уравнений Метод состоит в том, что, исходя из ограничений, элементов, на которые действуют ограничения и, возможно, параметров, составляют систему линейных или нелинейных алгебраических уравнений. Затем находят решения системы, из которых отбирают нужное (см. гл. 3). Преимуществом метода является его общность, существенным недо- статком-возможная неэффективность решения в общем виде. Сведение к частным случаям Попытаемся в отличие от предыдущего каждую возникающую систе- му уравнений решить для частного случая. Существенный недостаток 1) Радикальная ось двух окружностей представляет собой геометрическое место точек, из которых можно провести касательные одинаковой длины к этим окружностям. Если уравнения окружностей имеют вид X2 + Y2 + А,Х + B,Y+ + С, = 0, где 1= 1,2, то уравнение радикальной оси имеет вид (А,—А^)Х+ + CBi - Д,) у+ (С, + С,) = 0-Прим. перев. 14 Глава 1 такого подхода заключается в том, что добавление нового ограничения или нового элемента требует отдельного решения одной или нескольких систем (и соответственно составления одной или нескольких подпро- грамм). Преимущество состоит в том, что не требуется использовать сложных методов решения и, овладев соответствующими навыками, решение любой задачи можно находить, сводя ее к частным случаям. С точки зрения вычислительной техники такой подход ценен тем, что позволяет создать библиотеку алгоритмов. Мы не описываем здесь все возможности подхода, а читателя, интересующегося этими вопросами, отсылаем к работе [2]. Приведем только два примера, которые иллюст- рируют достоинства такого подхода. Проведем окружность СЗ, касательную к двум окружностям С1 и С2 с координатами центров (XI, У1), (XI, У2) и радиусами R\ и R2. В частных случаях возможные центры окружности СЗ определяются как точки пересечения окружностей, концентрических с окружностями С1 и С2 и с радиусами11: R\+R и R1+R, Rl + R и \R2-R\, \Rl - R\ и \R2- R\, i |^1-^| и R2+R, где Т?-радиус касательной окружности. Отметим, что центры касатель- ных окружностей расположены на расстояниях Rl + R или |7?1 — R\ от центра окружности С1 и R2 + R или | R2 — R \ от центра окружности С2. Из геометрических соображений, используя аналогичные рассужде- ния, можно сделать вывод, что, например, окружность, касательная к трем непараллельным прямым, имеет центр на пересечении трех внут- ренних биссектрис и что ее радиус равен расстоянию от этой точки до любой из этих прямых. Замечание. Можно упростить вычисления, если использовать преоб- разования, рассмотренные в следующем разделе. Можно, например, выбрать такой базис, в котором начало координат является одной из выделенных точек (центром одной из окружностей).

1.3. ВЫЧИСЛЕНИЕ ПЕРИМЕТРОВ И ПЛОЩАДЕЙ

Эти вычисления выполняются без труда для фигур, представляющих собой многоугольники. Из графических представлений легко получить правила вычислений. Пусть имеется замкнутый многоугольник с JM вершинами (последняя вершина совмещена с первой). Обозначим через х,,у, координаты г'-й вершины. Тогда можно показать, что периметр Р i 1) Ограничение заключается в том, что решение следует искать не на все» множестве точек плоскости, а на более узком множестве точек, лежащих и концентрических окружностях с приведенными радиусами.-ТТрмл*. ред. Основы графического представления информации 15 площадь А вычисляются по следующим формулам^: N-1 Р= S [(^.i-^+Cy.+i-^)2]1'2, 1=1 Г j N-1 -I A = h? Z (-W+i - xi+lУi) + Wi - x^y^ . L^ 1=1 J Замечание. Приведенные формулы применимы только к многоуголь- никам. Если необходимо вычислить периметр или площадь другой фигуры, ограниченной более сложной кривой (например, отрезками и дугами), то приведенными формулами легко воспользоваться для при- ближенных вычислений после замены произвольного контура много- угольником. Точность результата будет зависеть от степени приближе- ния многоугольника к заданной фигуре. При необходимости можно произвести точные вычисления (используя другие методы [2]).

1.4. ГЕОМЕТРИЧЕСКИЕ ПРЕОБРАЗОВАНИЯ НА ПЛОСКОСТИ

Геометрические преобразования используются для перемещения и модификации объектов. Преобразования представлены в матричном виде с использованием приведенных выше сведений об однородных координатах. Последние необходимы еще и потому, что без них трудно обойтись при описании преобразования переноса. Геометрическое преобразование, примененное к объекту или сово- купности объектов, может быть композицией (последовательностью) нескольких преобразований. Для его описания будем использовать матрицу, представляющую собой произведение матриц более простых преобразований (что является следствием ассоциативности матричного умножения). Основные преобразования следующие: • преобразование переноса на вектор Г; • преобразование поворота относительно начала координат на угол а; • преобразование масштаба на вектор Е (умножение координат объекта на координаты вектора Е). Рассмотрим математические выражения для основных преобразова- ний (исходный объект-вектор Р(х, ^-преобразуется в вектор F(x', У))2'. • Преобразование переноса на вектор T(t^, ty): F = Р + Т, при этом f х' = х + г,, \У'=У+1у 1) Знак числового значения площади зависит от направления обхода точек. В правой системе координат (ось абсцисс-вправо, ось ординат - вверх) положи- тельный знак возникает при обходе против часовой стрелки. Использование отрицательных площадей часто бывает полезным.- Прим. ред. 2) Далее Р и Р понимаются как векторы-строки -Прим. ред. 16 Глава 1 Легко показать, что в однородных координатах матрица, описывающая это преобразование, имеет вид 1 О О М(Т)= 010, t. ty 1 а преобразование вектора Р(х, у, 1) в вектор Р'{х', у', 1) можно записать в виде F =РМ(Т). . Преобразование поворота относительно начала координат на угол а. Координаты преобразуются по следующему правилу: f х' = xcos a — vsin a, F = \ , {. у = xsm a + ycos a. Отсюда легко получается матрица преобразования: cos a sin a 0 М (R (а)) = — sin a cos a 0 О 0 1 Матричная запись преобразования: F =PM{R(a)). • Преобразование масштаба на вектор Е(е^, е^). Правила преобразова- ния координат: х' = е^х, у' = е^у. Матрица преобразования: е^ О О М(Е)= 0 е;, 0 . О 0 1 Матричная запись преобразования: F =РМ{Е).

Цепочка преобразований

Более сложные преобразования можно определить как цепочку ос- новных преобразований, примененных последовательно. Матрицу слож- ного преобразования будем искать в виде произведения матриц преобра- зований, составляющих цепочку. Предположим, что к объекту применяется преобразование переноса на вектор Г(^, ty), а затем преобразование поворота относительно начала координат на угол а. Выполним сначала перенос, обозначив результат через F: Р = РМ(Т). Основы графического представления информации 17 Затем выполним поворот, обозначив результат через Р": F' =P'M(R(a)). Окончательно получаем Р" =PM(T)M(R(a)). Воспользуемся свойством ассоциативности матричного умножения и выполним сначала умножение матриц М(Г) и M(R(a)). Результат будет представлять собой матрицу полного преобразования: 100 cos a sin а О 010 — sin a cos a 0 = ^ t, 1 0 01 cos a sin a 0 = — sin a cos a 0 t^cos а — tySm a t^sm a + t^cos a 1 По аналогии с приведенными здесь рассуждениями можно опреде- лить матрицу любого сложного преобразования, состоящего из цепочки основных преобразований. Пример 1. Определить матрицу преобразования, соответствующего повороту на угол в относительно точки С(х^, у^). Для решения этой задачи сначала отметим, что такое преобразование можно осуществить в три этапа: 1) преобразование переноса на—С для того, чтобы совместить центр поворота с началом координат (так как нам известна матрица преобразования поворота только относительно начала координат); 2) преобразование поворота на угол а относительно начала; 3) преобразование переноса на С для возвращения центра поворота в прежнее положение. Полное преобразование будет иметь вид F = P-M(T(- C))-M(R(a))-M(T(C)) = 1 0 0 cos a sin а 0 100 =Р 0 1 0 -sin a cos a 0 010= -С, -С, 1 0 0 1 С, С, I 1 О О cos а sin в О = Р 0 1 0 - sin a cos a 0 = -С, -С, 1 С, С, 1 cos a sin a 0 = Р — sin a cos a 0 — C^cos a + CySin a + C^ — C^sin a — CyCos a + Cy 1 Пример 2. Определить матрицу, соответствующую преобразованию гомотетии с центром в точке С (Су Су) и масштабом R(R^, R,). 2-1051 18 Глава 1 Задача решается аналогично предыдущему случаю, так как нам уже известна матрица центральной гомотетии (изменение масштаба относи- тельно начала координат). Требуемое преобразование получается путем выполнения следующей цепочки основных преобразований: 1) преобразование переноса на—С для совмещения центра гомоте- тии с началом координат; 2) преобразование масштаба на вектор R; 3) преобразование переноса на С для возвращения центра гомотетии в прежнее положение.

1.5. ГЕОМЕТРИЧЕСКИЕ ПРЕОБРАЗОВАНИЯ В ТРЕХМЕРНОМ ПРОСТРАНСТВЕ

Геометрические преобразования в трехмерном пространстве осу- ществляются так же, как и на плоскости. Таким же образом определяют- ся основные преобразования, и матрицы сложных преобразований полу- чаются умножением соответствующих простых матриц. Описание преобразований в трехмерном пространстве немного слож- нее, чем для плоскости. Например, преобразование произвольного поворота представляется в виде комбинации преобразований поворотов относительно трех осей. Как и в плоскости, определим три основных преобразования, включающие преобразование поворота, которое в свою очередь состоит из трех последовательных преобразований. Основные преобразования: • преобразование переноса на вектор Г; . преобразования поворотов вокруг оси Х на угол я, вокруг оси У на угол Ь, вокруг оси Z на угол с, • преобразование масштаба. Матрицы основных преобразований легко получить из следующих определений: • Матрица преобразования переноса на вектор T{ty ty, ?,): 1000 л/frr^ 0100 м{т)= 0010- Цепочка преобразований Более сложные преобразования описываются так же, как и для плоскости. Предположим, например, что требуется выполнить преобра- зование поворота относительно оси Х на угол а с последующим преобразованием переноса на вектор Г(^, ty, t,). Матрица полного преобразования равна произведению матриц его составляющих: 10 0 0 1000 ,, ^ 0 cos a sin в 0 0100 О — sin a cos а О О О 1 0 - 00 0 1 ^ t, t, 1 10 00 _ 0 cos a sin а О О — sin а cos a 0 ^ ty t, 1 2» 20 Глава ! В следующем примере показано, что также просто получить матри- цу, описывающую «классическое» геометрическое преобразование из матриц основных преобразований. Пример. Осуществить преобразование поворота относительно произ- вольной прямой d на угол с. Для решения задачи прямую удобнее всего задать в параметрической форме через точку Р, лежащую на прямой, и единичный вектор направ- ления V (если прямая задана в другой форме, достаточно ее привести к параметрической). Этапы решения следующие: 1) преобразование переноса на — Р для того, чтобы прямая проходи- ла через начало координат: 2) преобразования поворотов на угол а относительно оси X, затем на угол b относительно оси Y. Углы а и Ъ выбираются так, чтобы прямая d после поворотов совпала с осью z (рис. 1.3); •х /^ V /"' / ^ / ^'2, ^ ^г 7. /*" / / / Рис. 1.3. Поворот вокруг произвольной прямой. 3) преобразование поворота относительно оси Z на угол с; 4) преобразования поворотов на угол — b относительно оси У и на — а относительно оси X; 5) преобразование переноса на Р. Замечание. Единственная трудность состоит в определении углов а и b. Для вычисления угла а можно воспользоваться соотношениями V. _ К ^"-(^У^/2" D' V V V V ^^^W^-D- Отсюда матрица преобразования поворота для данного случая (из общего вида матрицы преобразования поворота относительно оси X) имеет вид 10 00 M(R(xa}}= ° VJD ^ID ° м\ {' " О -У/D VJD 0 • 00 01 Основы графического представления информации 21 Для определения угла Ъ найдем сначала, как преобразуется единичный вектор V после поворота на угол а относительно оси X: 10 00 V-(v V V 1) ° VJD VVID ° ={V 0 D^D 1)= V -^x v, V. l) Q _y^D VJD о ^x v и fu i, 00 01 =(7, 0 D 1). Отсюда получаем выражение для угла Ь cos Ь = D, sin b = — Р^ и для матрицы преобразования поворота на угол Ъ относительно оси У D 0^0 ^•")- °-.. ; °о S • О 001

1.6. ПАРАЛЛЕЛЬНЫЕ И ПЕРСПЕКТИВНЫЕ ПРОЕКЦИИ

В технических чертежах применяются паралелльные проекции, а перспективные обычно используют художники и архитекторы для изо- бражения общих планов. Черчение с применением перспективных проек- ций более или менее сложных объектов довольно трудоемко, но исполь- зование вычислительной техники позволяет упростить эту процедуру. С помощью вычислительных устройств удалось коренным образом изме- нить саму постановку проблемы. Средства САПР позволяют «видеть» объект в перспективе, легко исключая или представляя невидимые элементы изображения.

Перед разработчиками САПР в этом плане стоит следующая задача:

необходимо представить реальный трехмерный объект на устройстве, имеющем двумерную поверхность отображения (экран, чертеж). Реше- ние ее состоит в получении проекции трехмерного объекта на плоскость.

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

На рис. 1.4 приведена классификация типов плоских проекций, ис- пользуемых в САПР.

Итак, различают перспективные и параллельные проекции. Для получения перспективной проекции необходимо определить точки пере- сечения плоскости проекции с прямыми, исходящими из центра проекти- рования и проходящими через все точки объекта. Параллельная проек-

22 Глава

Проекции

Параллельные Перспективные

^ \

Косоугольные Аксонометригеские с 1 тогкои с 2 тогками с 3 тогками

Изометрия Диметпия Триметрия

Свободные Кабинетные

Рис. 1.4. Типы плоских проекций.

ция определяется аналогично, за исключением того, что центр проекти- рования находится на бесконечности (все прямые параллельны).

Аксонометрической проекцией называется параллельная проекция, у которой порождающие прямые перпендикулярны плоскости проекции. В противном случае имеем косоугольную проекцию.

Среди аксонометрических проекций различают:

• изометрию: в плоскости проекции углы между каждой парой осей равны;

• диметрию: в плоскости проекции равны между собой два угла между осями;

• триметрию: в плоскости проекции все три угла между осями различны.

Для косоугольных проекций проектирующие прямые составляют с плоскостью проекции угол, отличный от 90°. Различные типы косоуголь- ных проекций характеризуются величиной этого угла. Выделяют два типа косоугольных проекций:

• свободную проекцию: угол между проектирующими прямыми и плос- костью проекции равен 45°;

• кабинетную проекцию: частный случай свободной проекции, в кото- ром масштаб по третьей оси уменьшен в два раза.

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

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

Основы графического представления информации 23

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

Рассмотрим матричные представления различных типов проекций.

1.6.1. Аксонометрические проекции

Аксонометрия является параллельной проекцией. Рассмотрим снача ла ортографические проекции в плоскостях х = 0, у = 0, z = 0. Матриць преобразований проектирования для этих случаев легко выводятся и определений 0000 0100 М^{х=0)= 0010 » 0001 1000 0000 М^(у=0)= 0010 » 0001 1000 0100 M^(z=0)= 0000 0001 Для ортографических проекций на плоскости x=p,y=p,z=p необхо димо применить еще преобразование переноса 0000 1000 0000 0100 0100 0100 М^(х=р)= 0010 0010 == 0010 0001 ^001 р 0 0 1 Изометрия, диметрия и триметрия получаются комбинацией поворо тов, за которыми следует проекция из бесконечности. Если нужн описать проекцию на плоскость z = 0, то сначала необходимо осущест вить преобразование поворота на угол b относительно оси У, затем н угол а относительно оси X. Матрица, описывающая эти два преобразо вания, имеет вид cos b 0 — sin b 0 10 00 010 0 0 cos a sin a 0 М= sin& 0 cosb 0 0 — sin а cos а 0 — 000 1 00 01 cos b sin b • sin a — sin b • cos a 0 0 cos a sin a 0 sin b — sin a • cos b cos a • cos b 0 00 0 1 24 Глава 1 Вместе с преобразованием проектирования на плоскость г = 0 оконча- тельная матрица имеет вид 1000 cos b sin b -sin a 00 M'=M 0100^0 cos a 00 0000 sin b -sinacosu 0 1 0001 00 01 Применим это преобразование к единичным векторам, направленным по осям Х и У: [/,=[1 О О l]-M'=[cos6 sinA-sina О О], <7у=[0 1 О 1]-М'=[0 cosa О О]. Диметрия характеризуется одинаковыми факторами искажения при преобразовании V ^ и Uy в U'^ и U'y, т. е. U',=U'y. Отсюда cos:гb + sin2^ • su^a = со^а, или 1 — sin2^ + sin2^ SH^B = 1 — sin2^, sm2b(sm2a — 1) = — sin2 a, и окончательно получаем для связи углов а и b . ->, sir^a sm2b=-———^-. 1 — sin a Таким образом, выбрав угол а, можно вычислить угол b и определить матрицу диметрической проекции. Для получения изометрии необходимо взять одинаковые факторы искажения по всем трем осям С7, =и',=Щ. Из выражения для [/; U',=[0 О 1 l]-M'=[sin& -sina-cosu 0 1] имеем еще одну связь между углами а и b cos2b + sin-^sir^a = cos^, sin2^ + sin^cos^ = cos^. Преобразуя, как для предыдущего случая, получаем . ,, sir^a . , 1 — Isir^a sm'b = ————,-, sin-h = ————-—. 1 — sin a 1 — sin-a Отсюда su^a = 1 — 2sin2в, sin^ = 1/3, sin a = ,/1/3, sin2^ = 1/2. Основы графического представления информации 25

1.6.2. Косоугольные проекции

В косоугольных проекциях проектирующие прямые образуют с плоскостью проекции угол, отличный от 90°. Рассмотрим проекцию на плоскость ХОУ(рис. 1.5) и предположим, что Р^ и Ру являются состав- ляющими косоугольной проекции единичного вектора Z на эту плос- кость, т.е. вектор [001 1] преобразуется в вектор [Рд Ру О I]. Матрица такого преобразования имеет вид 1000 0100 Р^ Ру 0 0 • 0001 Для свободной проекции Р^ = cos 45°, Ру = sin 45°, а для кабинетной проекции Р, = l^cos45°, Р, = '/^su^0.

1.6.3. Перспективные проекции

Перспективную проекцию будем представлять в виде цепочки пер- спективного преобразования и преобразования проектирования на плос- кость, предполагая, что проектирование осуществляется на плоскость Z = 0 (рис. 1.6). В качестве точки проектирования выберем лежащую на оси Z точку У(0, 0, t^) и определим точки пересечения F (х', у', z') лучей, исходящих из точки проектирования и проходящих через все точки объекта Р(х, у, z) с плоскостью проекции Z == 0. Легко показать, что .-=^х, у=^-у Z-V, Z-V, или 1 1 х' = -z/v^+l^ у ~ -z/v^+^y' 'Y ^ 1х /z / / р -—'—7—-;^ _-____^_______ р'^ / ^ —^—^ оУ^ } \_______^ / ^ ^ у ,^ ^-^"^ Рис. 1.5. Косоугольные проекции. /' ^ ^„---'" у Рис. 1.6. Перспективные проекции. 26 Глава 1 Матрица преобразования перспективного проектирования имеет вид: 1000 М(Р )= ° 1 ° ° \ перс/ OOO-1/i;, " 0001 Заметим, что точка (О, О, 1, 0), расположенная на бесконечности на оси Z, преобразуется в точку (О, О, 1, — 1/t^), если к ней применить перспектив- ное преобразование (без проектирования): 1000 [0 ° 1 0] о о ° °-IA, =^0 ° 1 -1^- 0001 или [00 — i^ 1]. Отсюда следует, что любая прямая, параллельная оси Z, в результате такого преобразования будет проходить через точку [О 0 — u, 1]. Эта точка называется точкой схода. По аналогии можно рассмотреть еще две матрицы перспективного преобразования 1 0 0 - 1/и, 1000 0100 0 1 0 - 1/Uy 0010 "0010 0001 0001 для которых точки схода расположены соответственно на осях Х с абсциссой — 1/t^ и Ус ординатой — l/Vy. Рассмотренные перспективные преобразования являются преобразо- ваниями с одной точкой схода. Можно рассматривать также перспектив- ное преобразование с двумя точками схода, матрица которого содержит два ненулевых члена (кроме 1) в четвертом столбце: 1 0 0 - 1/и, О 1 0 - l/Vy 0010 0001 и с тремя точками схода, матрица которого имеет вид 1 0 0 - l/i^ О 1 0 -1/у, О 0 1 - 1/u, • 0001

1.7. МОДЕЛИРОВАНИЕ ОБЪЕКТОВ

Геометрическое моделирование является важным средством САПР, так как для многих приложений необходимо представлять геометричес- кие свойства объектов. Читатель найдет в работе [2] обзор по геометри- Основы графического представления информации 27 ческому моделированию, используемому в САПР. Следует отметить, что геометрическое моделирование в общем случае базируется в основ- ном на структуре данных (блоки, ограничители, деревья) и очень редко на элементах математики. Исключение составляет представление кри- вых и поверхностей, математическое обоснование которого дано в гл. 2. В работах [3, 5] предпринимались попытки математически описать геометрическое моделирование твердых тел. К сожалению, эти описания трудно применять на практике. Отсутствие теории или слабое теоретическое обоснование ограничи- вает области применения моделирующих систем. Кроме того, одновре- менное использование объектов, смоделированных различным образом (например, твердых тел и поверхностей), для большинства систем часто приводит к неразрешимым противоречиям.

1.8. ЗАКЛЮЧЕНИЕ

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

Глава 2

Кривые и поверхности

2.1. ВВЕДЕНИЕ

Одной из распространенных задач САПР является графическое пред- ставление кривых и поверхностей. В этой главе рассмотрены некоторые математические методы, из которых конструктор может выбрать наибо- лее подходящие для решения конкретных задач с учетом имеющихся ресурсов вычислительной техники.

Мы рассмотрим три типа задач: интерполяцию, сглаживание и аппроксимацию. Введем следующие обозначения: Q-и-мерное множество, принадлежащее пространству R" {п ^ 1); {5,}, g, -множество функционалов, т.е. отображений, которые каждой функции /, определенной на Q, ставят в соответствие действительное число 8, (f). Наиболее типичный пример: для данной точки Р пространст- ва R" функционал 5„ будет равен 8„ (f) = f(P) - значению / в точке Р; {z,}i^,- заданное множество действительных чисел; ^-множество функций, определенных на О., которые могут быть функциями интерпо- 28 Глава 2 ляции, сглаживания или аппроксимации (полиномы, кусочно-полино- миальные и другие функции). Уточним постановку задач, рассматриваемых в этой главе. Задача интерполяции Найти элемент v из V, такой что для всех ( из / 5,(u)=z,.

Задача сглаживания

Найти элемент v из V, такой что множество величин {8i(u)}ieiHe очень удалено от множества {z,},g/. Критерий удаления может быть математи- чески выражен достаточно строго (при использовании Д-сплайнов или функций Безье), но всегда полезно его уточнить в общем виде. Он определяется через полунорму^ (р на R', и задачу можно сформулиро- вать так: найти элемент v из V, такой что полунорма ф({8,(10}.е1-К}.^) будет минимальной. Задача аппроксимации Исходные данные для задачи: W- множество функций, определенных на и со значениями в R; f- эле- мент W; Vc. W; (р-полунорма, определенная в W. Задача состоит в том, чтобы найти элемент v из V, такой что полунорма ф(/— v) будет минимальной. Для функций одной переменной мы приводим классическое описание решений перечисленных задач. Это поможет читателю оценить метод, который он предполагает использовать, и обратиться к другим разделам этой книги или к специальной литературе для применения в конкретном случае. Мы старались не употреблять специальные математические понятия, для усвоения которых у конструктора обычно не хватает времени. Мы представили широкий спектр существующих методов и подробно рассмотрели вопросы линейности, выбора базиса, геометри- ческих свойств данных (в частности, в случае поверхностей).

Линейность

Будем отдавать предпочтение методам, которые обладают одним из следующих свойств: . результат линейно зависит от данных; . • решение задачи сводится к решению системы линейных уравнений.

Выбор базисных функций

Речь идет о корректном выборе параметров множества функций V, на котором отыскивается решение. Эти параметры неявно определяют выбор базиса и могут изменяться в процессе решения задачи. 11 Полунорма <р отличается от нормы тем, что в ней из условия (р (о) = 0 не следует равенство а = 0 (ср. стр. 5\).-Прим. ред. Кривые и поверхности 29

Геометрические свойства данных

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

2.2. КРИВЫЕ

В методах, к описанию которых мы приступаем, обычно использует- ся ортонормированный базис (на плоскости или в пространстве). Будем предполагать, если не оговорено противоположное, что рассматривае- мые кривые являются однозначными функциями в этом базисе: одной абсциссе / соответствует одна и только одна ордината f(t).

2.2.1. Интерполяция

Интерполяционные полиномы Лагранжа

Исходные данные: 1) Й=[а,6] cR; 2) {§.},^; 1={0, 1, .... т], 5, if) =f(t,), где а < to < t... < l^ < b; 3) z,eR, iel; 4) V= F"- множество полиномов степени, меньшей или равной т, т.е. У-векторное пространство размерностью т + 1. Первым этапом решения задачи интерполяции является выбор бази- са для V. Очевидно, в качестве простейшей базы можно взять степенные функции вида 1, t, t2,..., I"1, т. е. задача сводится к нахождению полинома v(t)= E ^> J=0 такого, что &i(v) = v(?,) = z,, iel. Для вычисления коэффициентов t^. требуется решить систему т + 1 линейных уравнений с т + 1 неизвестными: m ^ Vjti=Zi, i=0, I, .... т. j=o Матрица этой системы А = (йц), где Дц = t{, называется матрицей Ван- дермонда. Поскольку все t, различны, она является обратимой; следова- тельно, задача допускает единственное решение, но вычисление коэффи- циентов довольно трудоемко: оно требует решения системы или обраще- ния матрицы А, не содержащей нулевых элементов. Можно показать, что выбор одночленного базиса не является луч- шим. На практике предпочтение отдается другим базисным полиномам, использование которых приводит к простым системам уравнений. 30 Глава 2 Базисные полиномы Лагранжа. Возьмем в качестве базиса Р" полино- мы Лагранжа "1 t — t- ^)=П——. '^- j=0 Ч - 1, J^i Легко убедиться, что в этом базисе решением является v(t)= ^ z,L,(0, 1=0 поскольку L,( т. j=0 Легко показать, что система уравнений в этом случае имеет нижнюю треугольную матрицу. Действительно, из вида интерполяционного по- линома v(t) = ^ c,N,(t) j=o следует система уравнений для вычисления коэффициентов Cj v(t,}= ^ c,N,(?,)= i c,N,(t,)=z„ iel, J=0 J=0 Nj(ti) = 0 для j> i. Решение системы записывается в виде i-i Со = z„, с, = [г, - ^ c^.(f,)]/N,(f,), i = 1, ..., т. j-o Величины с, называются разделенными разностями порядка i на значе- ниях ZQ, . . . , Z, . Кривые и поверхности 31 Важное преимущество этого базиса состоит в том, что очень просто добавляются новые точки интерполяции, при этом все вычисленные ранее полиномы NJ и их коэффициенты не меняются. Это следует из классического определения разделенных разностей. Для заданных точек 1ц, ...,<„ и функции / разделенная разность определяется с помощью рекуррентных соотношений: ^М=/(0 d[_t„t,\=f{-ti\~_f[-ti}, i^j, ••' •i /Л, t -I - dLt0' •••' ^-2> tm-^ ~ d{-^ •••' '--г' 'J и L'0> • • •' 'mJ — ————————————————.——————.————————————————— i •т-1~ 'т где d[.to, •••, ?„]-разделенная разность порядка т. Заметим, что значе- ния разделенных разностей не зависят от нумерации точек t,. Если ст обозначает множество точек и х и у-we дополнительные точки, то а^.х.ул^-^-^-^. х-у Следует отметить однако, что добавление новой точки приводит к появлению значительных осцилляции (рис. 2.1-2.3). Итак, мы двумя способами построили интерполяционный полином Лагранжа. Очевидно, выбор базисных полиномов оказывает существен- ное влияние на последующие вычисления. Из двух рассмотренных методов обычно отдают предпочтение базисным полиномам Ньютона с нахождением коэффициентов с помощью разделенных разностей. Для вычисления интерполяционного полинома на большом числе точек следует использовать интерполяционные сплайны. Погрешность и сходимость. При решении задачи интерполяции нельзя упускать из виду такие важные свойства применяемого метода, как погрешность и сходимость. Дадим их общее определение и проиллюст- рируем на примере интерполяционных полиномов Лагранжа. Восполь- зуемся прежними обозначениями SI, {8;},.^д V и др. Обозначим через Р- оператор интерполяции, который каждой функции/из вставит в соответствие функцию Pfvii V, удовлетворяющую следующим условиям: S.W)=S,(A, iel; P^W)^/. Оператор интерполяции Р называют точным на полиномах степени т, если для каждого полинома р из Р справедливо соотношение Рр = р. Интерполяционный метод Лагранжа для т + 1 точек исходных данных является точным на полиномах степени, меньшей или равной т. Погрешность интерполяции в общем виде определяется выражением Rf(t}=f(t)-PRt). Для нахождения погрешности интерполяционной формулы Ньютона воспользуемся легко проверяемым соотношением 32 Глава 2 <0т >' •^У-^ /'"° ff»-—————————————————————i 0,S \. ./ ff ^,ff OA\ '•»—o-" /<7^| Уо\ /r\ ^i ? -^^/—————————————^ Й V-^ /^| f.ff-[ /~\ S.04 f 5.0} / \ / v^—^ V/-\ /^J U 0.5 'о. У Л_________________ ^Ь ^-^ УО.О\ О t,0 S,#\r\ /\ 510 \ \ / Рис. 2.1. Интерполяция с помощью \ / полиномов Ньютона на 5-7 точках, -s^^ ^^ 0,5 \^ s/ 0,3 ^-—•" Щ0\ ^& f и Рис. 2.2. Интерполяция с по- и^ у мощью полиномов Ньютона на N. >' 6-10 точках. Положение точек °.5 "< >" задается функцией | х — 51. 'О М,0\ т= ? d^,...,t,']N,{t)+d^,...,^,tWt). i=o Отсюда получим выражение для ошибки Rf(t}=d^,t„ ...,?„ СП (t). В общем случае, если для полиномов степени т интерполяция осуществляется точно, для произвольной функции ошибку находят по формуле Тейлора, предполагая функцию/дифференцируемой т + 1 раз. При этом получают два выражения Rf(t) - -гп^- П (t), а < ^ b, Rf(t}= } К^ (х, <)/•'" +)'«) dt, (т + 1)! д где К -функция ядра ошибки. Кривые и поверхности 33 Х lE[„.t] Напомним, что функция / называется аналитической на [а, Ь~\, если существуют такие а, и с, что / допускает разложение в степенной ряд, сходящийся на \_а,Ь~]: f(t) = Од + а, {t - с) + ... + а, (t - с)1 + ... . Достаточное условие аналитичности функции/состоит в том, что все ее производные должны быть ограничены на [а, Ь~\. Например, е\ sin t, cos t аналитичны на любом интервале, tg t на интервале [а, Ь~} с (— тс/2, я/2). Следует отметить, что исследование сходимости различных методов интерполяции, аппроксимации или сглаживания позволяет довольно 3 1051 34 Глава 2 объективно оценить их эффективность. Однако для этого используются сложные математические приемы, описание которых выходит за рамки данной книги.

Интерполяционные полиномы Эрмита

Этот тип полиномов является обобщением интерполяционных поли- номов Лагранжа и используется тогда, когда заданы не только значения функции, но также и касательные в данных точках. Таким образом, число условий удваивается и интерполяционный полином минимальной степени будет принадлежать пространству, размерность которого в два раза больше, чем в предыдущем случае. Здесь будут рассмотрены только первые производные, хотя обобщение можно распространить и на случай производных более высокого порядка. Исходные данные: 1) П = [а, Ь~\ с R; 2) {8,}, si, I ={0,1,...,2т + 1}, причем 8,(Л =т, ;=0,1,...,т, 8,(/) =/'(/,), i=m+ 1,...,2m+ I, где а = ty < ?i < ... < f„ = b; 3) V= P2"+1- множество полиномов степени, меньшей или равной 2т + 1. Размерность этого векторного пространства равна 1т + 2. 4) Z,?-R, iel, где первые т + 1 значений соответствуют ординатам точек с абсциссами г;, остальные-коэффициентам наклона касательных в этих точках. • Рассмотрим сначала частный случай: т = 1, ty = 0, t^= 1. Введем базисные полиномы следующего вида: (ро(?) = (2г + 1)(1 - t2), (рг(0 = ?0 - t)\ cpi(?)=(3-2?)<2, (рз (t)=(t -I)?2. Это полиномы третьей степени, удовлетворяющие следующим соотно- шениям: <Р,(У) = 5,^ (Р;(7) = 8,_^, i = О, 1, 2, 3, j = 0, 1, где 5,J = 1, если i =j, и 0, если ; Ф]. Интерполяционный полином Эрмита для этого случая имеет вид V (t) = ZQ (ро (t) + Zi (pi (t) + Z^ (p2 (0 + ^ ФЭ (')' что эквивалентно выражению с использованием оператора интерполя- ции Pf(t) = §о(Л<Ро(?) + SiOTcpiW + 5,(/-)(р^) + 8з(Л<РзС). • Переходя к общему случаю, попытаемся записать интерполяционный полином Эрмита в виде 2m+l v(t)= ^ z,(p,(t), (р.еУ, i=0 Кривые и поверхности 35 где полиномы (р, должны удовлетворять следующим условиям: (р,(?,) = 8,,,, (p;.(f,) = 8,-„,у, г = О, 1,.... 2т + 1, j = О, 1,..., т, которые позволяют их искать в виде Ф,(г) = u,(t)Lf(t), =0 i=0 Интерполяционный полином Эрмита является единственным и ин- терполяция является точной на полиномах степени 2m+l. Ошибка интерполяции равна Г(2т+2)/е, т = -\,СП(0]2. где а ^ ^ b. (im + 2.)! В заключение отметим, что полиномиальную интерполяцию имеет смысл применять лишь для небольшого числа точек (не больше пятнад- цати) из-за того, что вместе с числом точек растет степень полинома и имеют место большие осцилляции в промежутках между точками (рис. 2.1 - 2.3). Базис Лагранжа должен применяться в тех случаях, когда вычисляется большое число интерполяционных полиномов на одних и тех же точках, поскольку система уравнений получается диагональной. В других случаях обычно используют базис Ньютона, приводящий к треугольной системе, а использование разделенных разностей позволяет легко добавлять новые точки интерполяции.

Кусочная полиномиальная интерполяция

С помощью кусочной полиномиальной интерполяции можно обойти упомянутые выше затруднения и строить интерполирующие функции на большом числе точек. Идея состоит в том, чтобы строить независимо друг от друга полиномы на каждом интервале [г,, <,+ J, сшивая их между собой. Для этой цели можно использовать также и сплайны, но они будут рассмотрены в других разделах. В качестве исходных данных возьмем следующие: 1) П = [а, и] с R; 2) 8,(Д =/(?,), a =ty<...Интерполяция сплайнами

Со времени введения сплайнов Шёнбергом [49] им посвящено боль- шое число работ, в которых даны их различные представления. Мы будем использовать представление, данное в работе [23] для кубических сплайнов, и приведем некоторые обобщения. В качестве исходных данных возьмем следующие: 1) П = [а, и]; 2) 5,(/) =/(<,), а < to < ;i < ... < ?„ < Ь; 3) (г,)о^,$п- Кубические сплайны. Вернемся к примеру 3, где предполагались t— г, известными производные ^,. функции/в точках г,. Обозначим т = ———— ^i+l ~ 1! для ?, s$ t s$ г.+i, тогда /,(?) = Pf(t) = (роМЛ?.) + Полиномиальные сплайны. Полиномиальным сплайном степени q на п точках f, называют функцию s, которая является полиномом степени 2q — 1 на каждом интервале (г,, t,+i), (г = 1, ..., п — 1) и полиномом степени q — 1 на интервалах [а, ^) и (г„, и] и имеет непрерывную производную ^2e-2). Обозначим через S множество функций s, которые могут быть представлены в виде 9-1 в /. _ . •l2i-l ^^Sa.^S^^^——, J=O 1=1 \^Ч ~ Ч- где (< — /,)+ = t — t; при t — t, > 0 и (f — ?,) = 0 при f — г, < О и i ^ точек задается функцией | х - 5 | '< >^ (ср. с рис. 2.2). N^ у" 0.5 N^ / "•л ^-^ ^ i а.а^ г, 0-5 ^s, у^ ^ \^ що 5.0& o,s N^ y^ ff'3' T^—I< Ю,0 I 5,0ч 0,5 N. ./^ ^ v-^ що i 5,0o. 0'5 ^< J^ 0'3], V^rf- ЩО | .W^y \/A -0,2 \/'7,,,. Рис. 2.6. Интерполяция сплайном на 16 точках. Интерполяционная кривая хоро- шо описывает произвольные данные. 40 Глава 2 Помимо интерполяции, сплайны можно использовать и в других задачах. Ниже будут рассмотрены Д-сплайны, метод наименьших квад- ратов и др. Во всех случаях придается большое значение выбору «хороших» базовых функций на множестве S [17]. Сплайны общего типа. Из изложенного выше ясно, что сплайн можно определить двумя способами: исходя из взаимного согласования прос- тых функций и из решения задачи минимизации. Третье определение, данное в работе [2], использует понятие «воспроизводящего ядра». Это определение мы используем ниже в примере, когда будем рассматривать задачи с двумя пространственными переменными. В теории сплайнов показывается, что второе определение допускает обобщение в двух направлениях: • обобщение критерия минимизации: если D- дифференциальный опера- тор, можно искать минимум J^[?>/(0]2 dt; . обобщение используемых функционалов: (р (/) = max \f(t) \, либо (р(/)= тах \f'{t)\, либо (р(/) = max \af(t) + W (t)\, либо (р(/)= а<КЬ a2.2.2. Сглаживание

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

• метод наименьших квадратов;

• сглаживающие сплайны;

• функции Безье и Д-сплайны.

Метод наименьших квадратов

Рассмотрим два векторных пространства V и W конечных размер- ностей. Пусть п и т соответственно размерности V и W, п а$ т. Обозначим через (v,)i$i^„ и (w,)i^,^„ базисные функции пространств V и W. Предположим, что в W определено скалярное произведение. обозначаемое <^, ), т.е. операция, которая каждой паре (х, у) элементов из W ставит в соответствие действительное число (х, у} из R, такое что 1) ^xeW <(.т, хУ > 0, (,у, .т) = 0 тогда и только тогда, когда х = 0; 2) V.v, yeW (х, у) = (у, х'); 3) V?.. це/?, VJC, у, ze W (\х + \^у, г> = ^<х, г> + \а{у, г>. Кривые и поверхности 41 (В качестве упражнения возьмите W = R2 и определите скалярное произведение в евклидовой геометрии.) С помощью скалярного произведения можно определить понятие расстояния (р (х - у) = ^/{х - у, х - у} и довольно просто производить вычисления. При использовании метода наименьших квадратов задача сглажива- ния формируется следующим образом: 1) пусть Г-линейный оператор преобразования V в W полного ранга п, т. е. обладает свойством: TV = 0 тогда и только тогда, когда v = 0; 2) пусть w-элемент W; 3) найти элемент v из V, такой что = i ".(^А)' Р- Е ^(t.)- К=1 - - К=1 Допустим также, что Л=(ац),^,^^, где Яу=и,(г,), тогда х=А'А и l<»=Sm (3 = A'z, где А* - транспонированная матрица Л, и система линейных уравнений запишется в виде A'A^ = A'z. Эта система может быть решена с помощью методов, описанных в разд. 3.1. Однако вычисление матрицы А'А (порядка п) в процессе решения системы может снизить точность решения. Поэтому в настоя- щее время предпочитают использовать другой метод, который мы кратко опишем здесь. В его основе лежит метод Гивенса, рассмотренный в гл. 5, в котором матрица А представляется в виде произведения двух матриц А == QS, где Q - ортогональная матрица порядка п, а матрица R имеет следующую структуру: -I. где S- верхняя треугольная матрица порядка и. Тогда уравнение A'AK = A'z можно записать в виде S'Q'QSK = S'Q'z, что эквивалентно S'S'k^S'Q'z. Обозначим через [Q'z]„ вектор, принадлежащий R" и состоящий из п первых компонентов Q'z. Тогда S'S?i=S'[Q'z]„, где S-обратимая матрица, a S'S является разложением Холецкого матрицы А 'Л11. Отсюда SX = [Q'z],, Матрица полученной системы является верхней треугольной, и систему легко решить. Примеры решения приведены на рис. 2.7 и 2.8. Описанный метод прост, эффективен, обладает высокой вычисли- тельной устойчивостью. Кроме того, можно показать, что i^-z,)^ ^ ((Q'z),)2, i=l t=n+l и тем самым получить информацию об ошибках сглаживания. Отметим 1) Разложение Холецкого приведено на стр. ^4.-Пpuлl. перев. Кривые и поверхности 43 ^,0т а о о 2.0 "«fi. ° ° ^^" 'о\——^~~~~тг 1 ~~~~^'———а ~~0^2\ 0 ° ° ° 15.0\ ^ 3^ 3,6 а /^\ а_^ / \ а^^~>^а а / а\ у °\ / \ Рис. 2.7. Сглаживание методом Т^'у -is ° -^ ^г о наименьших квадратов полино- _,„ ^-—— „.я | мами 3 и 5 степени. ' О ' также, что если т = п и удачно выбраны точки г, и базовые функции и,, то можно получить систему уравнений с диагональной матрицей [30, 33]. В рассмотренном выше примере вместо полиномов можно исполь- зовать другие функции, например Д-сплайны, которые описаны ниже (см. также работу [17]). Задачу можно обобщить, рассматривая про- странство функций с дополнительными ограничениями линейного типа. В таких случаях систему уравнений решают методом неопределенных множителей Лагранжа [33]. Сглаживающие сплайны Рассмотрим пример применения кубических сплайнов для сглажива- ния (рис. 2.9-2.11). Пусть р - действительное положительное число. Тогда на данных (г,, z,)i^,.^„ сглаживающий сплайн/^ будет функцией, которая минимизирует критерий J,(Л=](f"(t)}2л+p^(f(t.)-z,)2. Ь 1=1 5.5 ^\ 4,о- У V W \° а / \° / \ ^\ / ^• OJ,————\^-——^———J.———————о -Z.O- а \а/ | -Z.S \У 15,0 \ О 5,5\ /\ V- / \ Рис. 2.8. Сглаживание методом ^\. rf. \ наименьших квадратов тригоно- а/ \а о» / \i метрическими полиномами Зи / \ /\ 1 V 5 степени: д!>—————\~у——\———г——————а ]>,sin(2ni0c-a)/(6-a))+ -г,а а \ „/ • | +i>,cos(2m(x-a)/(&-a)). -г'^ \у fs-'" 194 откуда Глава 10 С? — а = 12 14 С! в 195 14' Ал т. е. имеет место коррекция на — —. Для Ag аналогично определяется величина « Ag/55,6. 10.3. СРАВНЕНИЕ МЕТОДОВ СГЛАЖИВАНИЯ Алгебраическое сглаживание всегда слабее, чем квадратичное. Если применить оба метода к единичному импульсу (О, О, О, 1, О, О, 0), то при алгебраическом сглаживании получим — (0, — 1, 4, 30, 4, — 1, 0), а при 36 квадратичном-— (0, — 1, 4, 8, 4, — 1, 0). Для квадратичного сглажива- ния амплитуда уменьшается примерно вдвое, в то время как для алгебраического - на -. 6 Если ошибка исходных данных является переменной (+ 1, — 1 и т. д.), 1 1 то Л4/14 даже меняет знак (- -, - и т. д.), Л4/16 подавляет все скачки, а алгебраическое сглаживание А^/Зб дает (-, — - и т.д.). Отсюда видны недостатки квадратичного сглаживания; его ошибка теряет случайный характер! 10.4. ИНТЕРПОЛЯЦИЯ ПОВЕРХНОСТЕЙ С ПОМОЩЬЮ ОБОБЩЕННЫХ ПОЛЮСОВ Все, что было сказано относительно применения полюсов для обра- ботки кривых, применимо и для обработки поверхностей. В этом случае обозначение полюса имеет вид Р и зависит от двух '(и более) семейств параметров, причем каждое семейство не зависит от осталь- ных. Таким образом определяется разбиение поверхности на клетки, и его можно изменять с помощью операции построения подполюсов. Ввод новых индексов в оба семейства не зависит от порядка операций. Непрерывно перемещая полюсы из заштрихованной области (рис. 10.1) к границам, можно получить отклик на двумерную ступенчатую функцию-поверхность, искривленную по определенному контуру. Высокие степени в двумерном случае приводят к сложным формулам сглаживания, например для 7-й степени с = 6, р = 1 сглаживание по Заключение 195 Г-—-—————1 г———] ! Рис. 10.1. методу сплайнов составляет 1 5040 (1302А4 + 123A„ + Ag) при г = 3, 1 76 204 800 15120 + 31Лю) при г = 5 и (1680Л;, + 126Л.. + Л„) при г = 1, •• = 3, ————(37320Л. + 3786Ag + 1814400- 6 8 (363468Ag + 37844Лю + ЗПД^) при г = 7. Рассмотренные выше примеры с р = 1, п = 7 vi р = 3, п = 8 являются наиболее простыми, но сложность вычислений быстро нарас- тает. Рассмотрению доступны еще случаи р = 4 для 15-й степени и р = 5 для 24-й, но следует иметь в виду, что при этом возрастает время вычислений и разрядность чисел в ЭВМ для достижения необходимой точности. Таким образом, высокие степени представляют лишь теорети- ческий интерес. ЗАКЛЮЧЕНИЕ Теория полюсов долгое время развивалась в представлении декарто- вых координат. Параметрическому представлению не уделялось доста- точного внимания. Предлагаемый в данной книге подход основан как раз на таком представлении и этим отличается от других способов решения задачи интерполяции. В пользу такого подхода можно привести два аргумента. Во-первых, все вычисления вручную или на ЭВМ используют четыре арифметические операции конечное число раз, и поэтому любой резуль- тат вычислений носит алгебраический характер. Понятие «трансцедент- ный», означающее «неалгебраический», связано с предельным пере о- дом, т. е. предполагает бесконечное число операций, и таким образом оно нереализуемо на практике. Во-вторых, описание в декартовых координатах и параметрическое представление нельзя считать полностью эквивалентными, так как не всегда возможно исключение параметров при переходе к описанию в 196 Заключение декартовых координатах. Особенности декартового и параметрического описания поверхностей различны. Отсутствие касательной плоскости для первого трактуется как наличие конической точки, а для второго- как наличие двух коллинеарных касательных. Оба представления можно согласовать следующим образом. Доста- точно заметить, что особые точки поверхностей х(и, v), у (и, v), z(u, v) являются проекциями особых точек в пространстве -?5 Ha ^з' если рассматривать функции пяти переменных f(x, у, z, и, v), g (...), h (...). В декартовом представлении это является наиболее общим выражением параметрической зависимости. Проекция пятимерного объекта на ?3 (x, у, z) дает зависимость в декартовых координатах (р (х, у, z). Однако можно получить и другие проекции -р(х, и, v), q{y, и, v), r{z, и, v), из которых получаются параметрические представления х(и, v), у (и, v), z (и, v). Начиная с Гаусса, теория поверхностей опирается на параметри- ческое представление. Можно ли утверждать, что оно справедливо для неуникурсального декартового разложения? Пока это не доказано. Алгебраический путь решения поставленной задачи позволяет устра- нить эти трудности. Он оказался весьма плодотворным, возможности его применения в различных областях еще не исчерпаны. Теория полю- сов может найти применение в описании кривых и поверхностей и при решении дифференциальных уравнений. В методе конечных элементов есть возможность так преобразовать исходные уравнения, чтобы полу- чить соотношения между полюсами. В этих направлениях уже есть обнадеживающие результаты. Реализация характеристик восстановлен- ных кривых позволит применять теорию полюсов для построения математических или физических таблиц вместо используемых сейчас сплайнов. При этом достигается не только непрерывность первой производной, но и обеспечивается возможность разложения в локальные ряды. Таким способом можно избежать использования полиномов Чебышева для аппроксимации. Областями применения теории полюсов могут быть также баллистика, небесная механика, для многомерных приложений - физика сплошных сред, аэродинамика. Разумный выбор характеристик восстановленных кривых всегда позволит при исследова- нии физических закономерностей найти правильный компромисс между восстановлением общей картины явления и его локальным поведением. Первые попытки описания с помощью полюсов кривых и поверхнос- тей вполне удовлетворительны. Возьмем, например, точки, описание которых традиционными методами весьма сложно; тройные стыки, которые для своего изображения могут потребовать до 300 элементар- ных поверхностей. С помощью обобщенных полюсов их удается умень- шить до небольшого числа, причем непрерывность в точках сшивки получается автоматически. Обобщенные полюсы незаменимы в тех случаях, когда требуется осуществить плавную деформацию кривых и поверхностей, при этом описание внутренних областей, складок, высту- пов не составляет принципиальных и технических трудностей. Заметим также, что обобщенные полюсы вполне естественно распространить на область применения сплайнов, что можно сделать быстро и легко. ЛИТЕРАТУРА Часть 1 Глава 1 1. Foley J., van Dam. Fundamentals of interactive computer graphics, Addison, Wesley, 1981. [Имеется перевод: Фоли Д., ван Дэм А. Основы интер- активной машинной графики.-М., Мир, 1985.] 2. Gardan Y., Lucas M. Techniques graphiques interactives et CAO, Hermes, 1983. 3. Gardan Y. Systemes de CFAO, Hermes, 1983. 4. Newman, Sproull. Principles of interactive computer graphics, MacGraw-Hill, 1979. 5. Requilha A. G. Representation of rigid solids theory, methods and systems, Computing survey, 12, No. 4, 1980. 6. Rogers D. F., Adams J. A. Mathematical elements for computer graphics, MacGraw- Hill, New York, 1976. [Имеется перевод: Роджерс Д.Ф., Адаме Дж.А. Матема- тические основы машинной графики.-М., Машиностроение, 1980.] Глава 2 1. Ahlberg J. H., Nilson E. N., Walsh J. L. The theory of splines and their applications, New York, 1967. [Имеется перевод: Алберг Дж., Нильсон Э., Уолш Дж. Теория сплайнов и ее приложения.-М., Мир, 1972.] 2. Atteia A. These, Grenoble, 1966. 3. Auslander A. Optimisation convexe, Paris, 1976. 4. Barnhill R. E. Representation and approximation of surfaces. In Mathematical Software III, New York, 1977. 5. Barnhill R. E., Gregory. Compatible smooth interpolation on triangles, J. Approx. Theory, 15, 214-225. 6. Barnhill R.E., Riesenfeld R.F. Computer aided geometric design, New York, 1974. 7. Bezier P. Mathematical and Practical Posibilities of UNISURF, In Computer aided geometric design. New York, 1974. 8. Carasso С. These, Grenoble, 1973. 9. Cea J. Optimisation: Theorie et Algorithmes, Methodes Mathematiques pour 1'Informatique, Paris, 1971. [Имеется перевод: Cea Ж. Оптимизация. Теория и алгоритмы.-М., Мир, 1973.] 10. Chenin P. These. Grenoble, 1976. 11. HuiC.K. Schumaker U., WangJ.D. On spaces of piecewise polynomials with boundary conditions, Lect. Notes Maths., Springer Verlag, 1982. 12. Ciarlet. The finite element methode for elliptic problems. North Holland, 1978. 13. Cinquin Ph. These, Sainte-Etienne, 1981. 14. Cline. Scalar and planar-valued curve fitting using splines under tension, Comm. ACM, 17, 4, 218-220, 1974. 15. Coons. Surfaces for computer aided design of space forms. M.I.T. Press, 1967. 16. Corres Y. Generation automatiques d'une triangulation sur des points donnes, R. R. 49, С С S A, 1980. 17. Сох, Practical spline approximation, Lect. Notes Maths., 965, 1982. 18. Dahmen W., Micchelli С. A. Recent progress in multivariate splines, Approxi- mations theory, New York, 1983. 19. De Boor C. A practical guide to splines, App. Math. Sc., 27, Springer Verlag, Berlin, 1978. 20. Ducateau. These, Grenoble, 1971. 21. Duchon. Interpolation des fonctions de deux variables suivant le principe de la flexion des plaques minces, RAIRO Anal., No. 10, 1976. 22. Due Jacquet M. These, Grenoble, 1973. 198 Литература 23. Due Jacquet M. Seminaire d'Analyse Numerique de Grenoble, 1974-75. 24. Eddy W. F. A new convex hull algorithm for planner sets, ACM Trans. Math Softw., 3, 4, 1977. 25. Franke. Locally determined smooth interpolation at irregularly space points in several variables, J. Inst. Math. Appl., 19, 471-482, 1977. 26. Gardan Y., Lucas M. Techniques graphiques interactives et CAO, Paris, 1983. 27. Gennain-Bonne, Sablonniere. Comparaison des formes de courbes parametriques et de leurs approximants splines, Pub. 76, Lille. 28. Gordon. Distributions lattices and multivariate approximations, In Approximation with special emphasis on splines, New York, 1969. 29. Green J. P., Sibson R. Computing Dirichlet tesselations in the plane, Сотр. J., 21, 2, 1978. 30. Hacques G. Methodes mathematiques pour 1'informatique, Algorithmique numeri- que. Collection U, Armand Collin, Paris, 1971. 31. Klucewicz. A piecewise C1 interpolant to arbitrarily space data. Univ. Utah, 1977. 32. Lafranche Y. These. Rennes, 1984. 33. LaurentP.J. Approximation et optimization, Paris, 1972. [Имеется перевод: Лоран П. Ж. Аппроксимация и оптимизация.-M., Мир, 1975.] 34. Laurent P. J. Inf-convolution spline pour ('approximation des donnees discontinues, Grenoble, 1981. 35. Laurent P.J. Fonctions splines cardinales tronquees, Grenoble, 1983. 36. Lawson С. L. Software for C1 surfaces interpolation, In Mathematical Software III New York, 1977. 37. Le Mehaute, These, Rennes, 1984. 38. Little F.F., Schwing. Automatic generation of triangulations. Univ. of Utah, 1977. 39. Lorentz. Theory of approximation. 40. Marshall J. A. These, Dundee, 1975. 41. Me. Lain. Two dimensional interpolation from random data, Comput J , 19, "> 178-181, 1976. 42. Nielson. Some piecewise polynomial alternatives to splines under tension. In Computer aided geometric design, New York, 1974. 43. Pailhua L. These, Grenoble, 1978. 44. Polya. Schoenberg, On De La vallee Poussin means and convex maps Pacific J Math., 295, 1958. 45. Poncet A. These, Grenoble, 1979. 46. Preparata F. P., Hong S. J. Convex hulls finite sets of points in two and three dimensions, Comm. ACM 20, 2, 1977. 47. Sablonniere. These, Lille, 1982. 48. Saw, Smith. Automatic modal triangulations for finite elements computer aided design, 1973. 49. Schoenberg. On spline functions inequalities, Acad. Press., 255-291, 1967. 50. Schultz. Spline analysis, Prentice Hall, 1973. 51. Schumaker. Spline Functions: Basic Theory, J. Willey, New York, 1981. 52. Thomman J. These, Lille, 1970. 53. Utreras F. These, Grenoble, 1978. 54. Utreras F. Cross validation techniques for smoothing spline functions in one or two dimensions, Lect. Nots. Math. 55. Wamba G., Weindelberger J. Some new mathematical methods for variational objective analysis using splines and cross-validation. Weather review, 108, 1980. 56. Zienckievicz О. С. The finite element method in engineering science. London. 1971. [Имеется перевод: Зенкевич О. К. Метод конечных элементов в технике - М Мир, 1975.] Литература 199 Глава 3 1. Сеа J. Optimisation: Theorie et Algorithmes, Dunod, 1971. [Имеется перевод: Сеа Ж. Оптимизация. Теория и алгоритмы.-М., Мир, 1973.] 2. Ciarlet Р. Introduction a 1'analyse numerique matricielle et a 1'optimisation, Masson, 1982. 3. Chatelin F. Valeur propres, Masson. 4. Golub G. H., Meurant G. Resolution numerique de grands systemes lineaires, Eyrolles, 1983. 5. Hacques G. Algorithmique numerique, Mathematiques pour Unformatique, Armand Colin. 6. Hageman I. A., Young D.M. Applied iterative methods, Academic Press, 1982. 7. Ortega J., Rheinboldt W. C. Iterative solution of non linear equations in several variables, Academic Press, 1971. [Имеется перевод: Ортега Дж., Рейнболдт В. Итерационные методы решения нелинейных систем уравнений со многими неизвестными.—М., Мир, 1975.] 8. Ostrowski A. Solution of equations and systems of equations, Academic Press, 1966. [Имеется перевод: Островский А. М. Решение уравнений и систем уравне- ний.-М., ИЛ, 1963.] 9. Rail L.B. Computational solution of non linear operator equations, Wiley, 1969. 10. Raviart P. Cours d'analise numerique, Polycopie de 1'Ecole Polytechnique. 11. Temam R. Algebre lineaire, C3 Analyse numerique, Polycopie de 1'Universite d'Orsay, Paris, 1969. 12. Varga R.S. Matrix iterative analysis. Prentice Hall, 1962. 13. Wilkinson J. H. The algebric eigenvalue problem, Oxford Press, 1965. [Имеется перевод: Уилкинсон Дж. X. Алгебраическая проблема собственных значе- ний.-М., Наука, 1970.] 14. Bunch J.R., Rose D.J. Sparse matrix computation, Hermann, 1966. 15. Gastinel N. Analise numerique lineare, Hermann, 1966. 16. Stewart G.W. Introduction to matrix computation, Academic Press, 1973. 17. ACM Transaction on mathematical software. 18. Eispack, Lecture notes in computer science, 6, Springer Verlag, C. Moler (editor), 1976. 19. NAG Library reference manual, Numerical Algorithms Group, Oxford. 20. Wilkinson J. H., Reinsch C. Handbook for Automatic Computation Linear algebric, 2, Springer-Verlag, 1971. 21. Golub G., Van Loan C. F. Matrix computation. The John Hopkins University Press, 1984. Глава 4 1. Brezis. Analyse fonctionnelle, Theorie et Application, Masson, 1983. 2. Ciarlet P. G. Introduction a 1'analyse numerique et matricielle et 1'optimisation, Masson, 1982. 3. Ciarlet P.G. The finite element method for elliptic problems, North-Holland, 1987. 4. Raviart P. A., Thomas J. M. Introduction a 1'analyse numerique des equations aux derivees partielles, Masson, 1983. 5. Strang G., Fix G. An analysis of the finite element method, Prentice-Hall, 1973. Часть 2 1. Ahlberg J.K. et al. The Theory of Splines and their Applications, N.Y., 1967. 2. Barnhill R E. et al. Computer Aided Geometric Design (Proceedings of the Conference held at the University of UTAH SALT LAKE CITY, 1974). 200 Литература 3. Bohm W. Inserting new Knots into й-spline Curves, Computer Aided Design, 12, p. 199-201, 1980. 4. Bohm W. Subdividing multivariate Splines, Computer Aided Design, 15, No. 6, 1983. 5. Bohm W., Farm G. Letter to the Editor, Computer Aided Design, 15, 1983. 6. Blomgren R., Fuhr R. Algorithms to convert between rational Д-Spline. Representa- tion of Curves and Surfaces, Boeing, November 16, 1982. 7. De Boor. A practical Guide to Splines, Applied Math Sciences, No. 27, Springer- Verlag. On calculating with Д-Splines, J. Approximation Theory, 6, p. 50-62, 1972. 8. Cohen E., Lyche Т., Riesenfeld R. Discrete 5-Splines and subdivision Techniques, Computer Aided Geometric Design and Computer Graphics (University of Oslo Norway), Computer Graphics and Image processing, 14, p. 87-111, 1980. 9. Coons S.A. Surfaces for Computer Aided design. Design Division Mech. Engin, Dept. MIT 1964, revised 1967. 10. Farin G. Subsplines uber Dreiecken, Fakultat zu Braunschweig genehmigte Disser- tation zur Eriangung des Grades eines Doktors der Naturwissenschaften, 1979 В. Polynomials over Triangles and the Construction of Piecewise С and Polyno- mials, University of Utah, 1980. 11. Ferguson J. С. Multivariable Curve Interpolation. The Boeing Company D2-22504, July 1963, and J. of A CM [I, 1964. 12. Forrest A.R. Computational Geometry, Proc. Royal Soc. London A, 1971. 13. Forrest A.R. The twisted Cubic Curve, A Computer Aided Geometric Design Approach, CAD, 12, p. 165-172, 1980. 14. Gordon W.J. Blending-Function Methods ofbivariate and multivariate Interpola- tion and Approximation, SIAM J. Numer Anal, 8, No. 1, 1971. 15. Gordon W.J., Hall С. A. Construction of curvilinear coordinate Systems and Applications to mesh Generation, Intern. J. Numer methods engag., 1, No. 4, 461-477, 1973. 16. Gordon W.J., WixonJ.A. Pseudo-Harmonic Interpolation on convex Domains, SIAM J. Number Anal, II, No. 5, p. 909-933 1974. 17. Gordon W.J., Hall C.A. Exact Matching of Boundary Conditions and Incorpora- tions of semi quantitative Solution Characteristics in initial Approximations to Boundary value Problems, J. Comput. Phys., 25, No. 2, p. 151-162, 1977. 18. Gordon W.J., Wixom J.A. Shepard's Method of "Metric Interpolation" to bivariate and multivariate Interpolation, 32, No. 141, p. 253-264, 1978. 19. Greville T.N.E. On the Normalization of the 5-Splines and the Location of the Nodes for the Case of unequally spaced Knots (167), p. 286-291. 20. Greville Т. N. E., Schoenberg I. J., Sharma A. The Spline Interpolation of Sequence satisfying a linear Recurrence Relation, 17, No. 3, p. 200-221, 1976. 21. Lane J.M., Riesenfeld R.F. A theoretical Development for the Computer Genera- tion and Display of Piecevise polynomial Surfaces, IEEE Trans. on pattern Analysis and Machine intell., 2, No. 1, 1980. 22. Марчук Г. И. Методы вычислительной математики,-М.: Наука, 1980. 23. Riesenfeld R. Applications of 5-Spline Approximation to geometric Problems of Computer Aided Design, UTEC CSC, 73-126, March, 1973. 24. Schoenberg I. J. On Spline Functions with supplement by T. N. E. Greville Inequali- ties, Academic Press, 1967. 25. Schoenberg I. J. Cardinal Interpolation and Spline Functions, Journal of Approxi- mation Theory 2, p. 167-206, 1969. 26. Schoenberg I.J. Cardinal Interpolation and Spline Functions II. Intemolation of data of power Growth, Journal of Approximation Theory, 6, p. 404-420, 1972. Предметный указатель Аксонометрическая проекция 22, 23 Аналитическая функция 33 Антисимметричная матрица 9 Аппроксимация 27, 28, 50, 55 Базис 9, 28, 29, 30, 31, 40, 52, 64, 113, 117 Барицентрические координаты 64, 117, 120, 138, 139, 156 Бета-функция 153 Булева сумма 60 Вариационная задача 107, 109, 111, 113, 116 Векторное пространство 8, 29, 34, 51, 112 Включение индекса 143 Гамма-функция 153 Геометрическое преобразование 15, 18 Главный элемент 72, 103 Годограф 137 Граничные условия 108, 115, 117, 124 Диметрия 22, 24 Изометрия 22, 23 Интерполяция 27, 28, 29, 55, 60, 160, 165 Итерационная матрица 79 Итерационный метод 55, 78, 84, 93, 98 -оператор 31, 59, 84 Кабинетная проекция 22, 25 Квазиньютоновские методы 87 Клеточная матрица 75, 81 Конечный треугольный элемент 64 -элемент Лагранжа 64, 121, 124 -—Эрмита 65, 121 Корни полинома 96, 100 Косоугольная проекция 22, 25 Ленточная матрица 75, 81, 116 Масштабный фактор 10 Матрица Гессе 91 -жесткости 114, 115, 118 -остатков 83 - Хессенберга 98 Метод Бэрстоу 97 - Галеркина 113 -Гаусса 72, 103 - Гаусса-Зейделя 79 -Гивенса 42, 76, 100 - Гордона и Кунса 59 -дихотомии 95 - Жордана 74 -конечных разностей 126 -Лагерра 97 -Ланцоша 101 -ложного положения 94 -наименьших квадратов 40, 52, 193 -неполного разложения 82 - Ньютона 85. 93, 106 --с линейной итерацией 87 - - с якобианом из конечных разностей 86 -подгонки 54 - предобусловленности 83 -релаксации 80, 105 - Ритца 113 -Рябенького 186 -секущих 94 -симметричной релаксации 81 -сопряженных градиентов 81 -спуска 82 -Стефенсена 95 - Уолла 95 -Франка 54, 67 - Хаусхолдера 76 202 Предметный указатель -Якобы 80, 101 -с разверткой 102 Многоугольник Безье 58 Нелинейный метод Гаусса -Зейделя 89 -релаксации 89 -Якоби 89 Неоднородная задача Неймана 110 Норма 51, 52, 79, 85, 102, 112 Обобщенный полюс 150, 165, 182, 194 Обратная подстановка 71 Обусловленность 77, 97 Однородная задача Дирихле 109 -Неймана 110 Однородные координаты 9, 133 Окно пользователя 11 -экрана 11 Определитель Вандермонда 29, 163 Оптимизация 90 Ортографическая проекция 23 Ортогональная матрица 78 Ошибка итерации 79 Параллельная проекция 22 Параметрическое представление 55 Периметр многоугольника 15 Перспективная проекция 21, 25 Перспективное преобразование 25 Площадь многоугольника 15 Поверхность Безье 62 Погрешность интерполяции 31, 59 -сглаживания 42 Полиномы Бернштейна 44 -Лагерра 53 -Лагранжа 30, 59, 160, 164, 181 - Лежандра 53 - Ньютона 30 - Чебышева 53 -Эрмита 34, 53, 59 Полунорма 26 Порядок непрерывности 144, 149, 151, 155, 168, 173 Преобразование гомотетии 17 -масштаба 16, 19 -переноса 15, 18 -поворота 16, 18 -проектирования 21 - Хаусхолдера 98 Примитивный полюс 143 Прогрессивный полюс 150, 162 Простой полюс 146, 151, 167, 170, 182 Пространство пользователя 11 —экрана 11 Радикальная ось 13 Разбиение Делоне 69 Разделенная разность 30, 35, 46, 161 Разложение матрицы Холецкого 42, 74, 82 —LU 73. 78, 103 — QR 42, 77, 97, 98, 103 ——со сдвигом 99 Разреженная матрица 75, 81, 116 Сглаживание 27, 28, 40, 55, 171, 194 Сжимающий оператор 92 Симметрические полиномы 134 Симметричная матрица 9, 81, 100 Слабое решение 109 Собственные векторы матрицы 98, 102 -значения матрицы 78, 79, 97, 102 Сокращение индекса 137 Спектральный радиус матрицы 79, 81, 92, 102 Сплайн 31, 37, 43, 61, 65, 139, 149, 175 Д-сплайн 27, 43, 46, 56, 62, 149, 163 Стационарная точка 91 Степени свободы 118 Степенной метод 102 Степень восстановления 162, 165, 175, 193 Субсплайн 149, 168 Схема Горнера 154 Сходимость 31, 35, 80, 84, 88, 91, 93, 100, 103 Теорема Лакса - Мильграма 110, 112 -о локальной сходимости 92 -о сжатом отображении 92 Теплицева матрица 75 Точка схода 26 Треугольник Фибоначчи 135 Триангуляция 117 Триметрия 22 Унитарная матрица 99 Упрощенный метод Ньютона 87, 94 Условие Хаара 51 Устойчивость 54, 59, 76, 77 Предметный указатель Формула Грина 116, 124 Функция Безье 27, 44, 56 -ядра ошибки 32 Характеристический полином 97 Число обусловленности 78 Явление Гиббса 176 Якобиан 85, 92

Оглавление

Предисловие редактора перевода ........................ 5

Часть 1. Основные методы

Шеиен П., Коснар М., Гардач И., Робер Ф., Робер И., Витомски П.

Предисловие авторов ............................... 7

Глава 1. Основы графического представления информации ......... 8

1.1. Введение .................................. 8

1.2. Двумерное пространство (плоскость) ................. 10

1.3. Вычисление периметров и площадей ................. 14

1.4. Геометрические преобразования на плоскости ........... 15

1.5. Геометрические преобразования в трехмерном пространстве . . 18

1.6. Параллельные и перспективные проекции .............. 21

1.7. Моделирование объектов ........................ 26

1.8. Заключение ................................ 27

Глава 2. Кривые и поверхности ......................... 27

2.1. Введение .................................. 27

2.2. Кривые .................................. 29

2.3. Поверхности ............................... 59

Глава 3. Численные методы ре'пения систем уравнений ........... 70

3.1. Системы линейных уравнений ..................... 70

3.2. Системы нелинейных уравнений .................... 84

3.3. Нелинейные уравнения [5] ....................... 93

3.4. Заключение ................................ 103

3.5. Приложения ................................ 103

Глава 4. Основы метода конечных элементов ................. 107

4.1. Введение .................................. 107

4.2. Примеры вариационной формулировки дифференциальных урав- нений с граничными условиями .................... 108

4.3. Внутренняя аппроксимация. Метод Ритца - Галеркина ...... 111

4.4. Метод конформных конечных элементов .............. 115

4.5. Другие типы конечных элементов .................. 119

4.6. Пример применения конечных элементов в двумерном прост- ранстве .................................. 123

4.7. Заключение ................................ 126

Приложение. Введение в метод конечных разностей ....... 126

Оглавление 205

Часть 2. Теория полюсов Кастельжо П.

Предисловие ..................................... 130

Предисловие автора ................................ 131

Глава 1. Основная задача теории полюсов ................... 131

1.1. Введение .................................. 131

1.2. Основные свойства полюсов ...................... 132

1.3. Особенности применения теории полюсов к обработке кривых и поверхностей .............................. 133

Глава 2. Симметричные полярные формы ................... 134

2.1. Полярная форма параметрического уравнения ........... 134

2.2. Алгоритм включения новых полюсов ................ 136

2.3. Производные полярной формы .................... 137

Глава 3. Символьный анализ ........................... 138

3.1. Разбиение поверхности на прямоугольники ............. 138

3.2. Разбиение поверхности на треугольники ............... 139

3.3. Связь со сплайнами ........................... 139

3.4. Предполагаемые обобщения ...................... 142

Глава 4. Индексное представление полюсов .................. 143

4.1. Последовательности индексов .................... 143

4.2. Подполюсы ................................ 143

4.3. Увеличение степени ........................... 144

4.4. Включение индекса. Значение кривой в текущей точке ...... 144

4.5. Переход к следующей дуге ....................... 145

4.6. Непрерывность .............................. 146

4.7. Простые полюсы ............................. 146

4.8. Треугольная таблица разностей простых полюсов ......... 147

4.9. Алгебраическое разложение дуги .................. 148

4.10. Еще раз о непрерывности ....................... 149

4.11. Полюсы и сплайны .......................... 149

4.12. Прогрессивные полюсы ....................... 150

4.13. Обобщенные полюсы ......................... 150

Глава 5. Использование полюсов в практических расчетах ......... 151

5.1. Операции с простыми полюсами ................... 151

5.2. Свойства простых полюсов ...................... 152

5.3. Пример вычисления пятых степеней целых чисел ......... 152

5.4. Бета- и гамма-функции ......................... 153

5.5. Пример вычислений значений полинома ............... 154

5.6. Графические построения ........................ 155

5.7. Представление поверхностей с помощью полюсов ........ 156

5.8. Пример применения теории полюсов ................ 158

Глава 6. Полярная форма интерполяционных полиномов Лагракжа .... 160

6.1. Увеличение степени интерполяционного полинома ........ 160

6.2. Другие формы представления интерполяционных полиномов

206 Оглавление

Лагранжа ................................. 161

6.3. Степень восстановления ........................ 162

6.4. Связь полюсов с нечетными -8-сплайнами .............. 163

Глава 7. Характеристики восстановленных кривых .............. 164

7.1. Полярная форма интерполяционной формулы Лагранжа ..... 164

7.2. Вычисление обобщенных полюсов дуги ............... 165

7.3. Определение простых полюсов дуги .................. 167

7.4. Вычисления простых полюсов дуги . .................. 170

Глава 8. Интерполяция со сглаживанием .................... 171

8.1. Проверка степени восстановления .................. 171

8.2. Проверка непрерывности и отклик на единичный импульс .... 172

8.3. Число удовлетворенных условий непрерывности .......... 173

8.4. Сравнение со сплайнами ........................ 175

8.5. Примеры различных функциональных зависимостей ....... 176

8.6. Пример других характеристик интерполяции ............ 181

Глава 9. Применения теории полюсов ...................... 185

9.1. Вычисление оптимальной характеристики .............. 185

9.2. Математическое напряжение ...................... 186

9.3. Кубическая интерполяция с равномерным разбиением ...... 187

9.4. Кубическая интерполяция с неравномерным разбиением ..... 187

9.5. Интерполяция полиномами четвертой степени ........... 189

9.6. Интерполяция полиномами пятой степени ............. 191

Глава 10. Перспективы применения теории полюсов ............. 192

10.1. Замечания о характеристиках восстановленных кривых ..... 192

10.2. Сглаживание, определенное с помощью метода наименьших квадратов ................................ 193

10.3. Сравнение методов сглаживания ................... 194

10.4. Интерполяция поверхностей с помощью обобщенных полюсов ................................. 194

Заключение ..................................... 195

Литература ..................................... 197

Предметный указатель .............................. 201

УВАЖАЕМЫЙ ЧИТАТЕЛЬ! Ваши замечания о содержании книги, ее оформлении, качестве перевода и другие просим присылать по адресу: 129820, Москва, И-110, ГСП, 1-й Рижский пер., 2, изд-во «Мир». Научное издание Патрик Шенен, Мишель Коснар, Ивон Гардан, Франсуа Робер, Ив Робер, Патрик Витомски, Поль де Фаже де Кастельжо МАТЕМАТИКА И САПР В 2-х книгах Книга 1 Зам. зав. редакцией Э. Н. Вадиков Ст. научный редактор И. М. Андреева Мл. научный редактор В. Н. Соколова Художник Л. М. Муратова Художественный редактор Н. М. Иванов Технический редактор Л. П. Емельянова Корректор Н.А. Гиря ИБ № 6407 Сдано в набор 21.09.87. Подписано к печати 10.05.88. Формат 60 х 90/16. Бумага офсетная № 1. Печать офсетная. Гарнитура тайме. Объем 6,5 бум. л. Усл. печ. л. 13,0. Усл. кр.-отт. 26,26, Уч.-изд. л. 13,35. Изд. № 6/5464. Тираж 28000 экз. Зак. 1051. Цена 1 р. 10 к. ИЗДАТЕЛЬСТВО «МИР» В/о «Совэкспорткнига» Государственного комитета СССР по делам издательств, полиграфии и книжной торговли 129820, ГСП, Москва, И-110, 1-й Рижский пер., 2 Можайский полиграфкомбинат Союзполиграфпрома при Государственном комитете СССР по делам издательств, полиграфии и книжной торговли г. Можайск, ул. Мира, 93