Глава 12. АППРОКСИМАЦИЯ КРИВЫХ
12.1. ВВЕДЕНИЕ
В последних двух главах речь шла в основном об интерполировании, т. е. о задачах, в которых было необходимо построить кривую, обязательно проходящую через все экспериментальные точки. (Точки-ориентиры относятся к параметрам синтеза, и поэтому кривую, задаваемую ими, также можно использовать для интерполирования.) Существует множество прикладных задач, при решении которых интерполирование не только не требуется, но даже нежелательно — в этих задачах требуется построить кривую, проходящую вблизи экспериментальных точек. Таким образом, возникает задача аппроксимации. Если построение кривой по точкам осуществляется в интерактивном режиме, то различие между двумя задачами несущественно. Пользователь просто изменяет параметры (такие, как точки-ориентиры) до тех пор, пока воспроизводимая кривая не принимает «правильный» вид. Последнее может означать, что соответствующая кривая проходит через все экспериментальные точки или через их большую часть, или вблизи всех экспериментальных точек и т. д. При построении кривой по точкам, осуществляемом в автоматическом режиме, такого рода субъективные критерии требуется заменить мерами близости, точно определенными математически. Наиболее распространенными из таких мер являются максимальная ошибка и суммарная квадратичная ошибка (СКО). Отклонение может измеряться либо по координате, либо по нормали к аппроксимирующей кривой. Последнее кажется более естественным, однако сложнее в вычислительном отношении. Пусть 
обозначает ошибку в точке, измеренную в точке 
т. е. расстояние между построенной кривой и соответствующей точкой (измеренное любым из двух указанных методов). В таком случае
Поскольку математические средства CKO-аппроксимаций развиты в наибольшей степени, этот подход и является наиболее распространенным. Замкнутые формулы можно построить не только для случая аппроксимации с помощью многочленов, но и для
аппроксимации с помощью сплайнов и иных кривых. В разд. 12.2 и 12.3 дается обзор важнейших свойств способов аппроксимации, предусматривающих использование в качестве аппроксимирующих кривых многочленов или сплайнов с фиксированными узлами. При определении аппроксимирующей кривой по критерию максимальной ошибки приходится решать задачу линейного программирования либо использовать какой-либо еще итеративный алгоритм. Таким образом, достижение оптимальной аппроксимации может потребовать значительного объема вычислений, в связи с чем наблюдается рост популярности субоптимальных эвристических алгоритмов. Наибольшую важность имеет задача, которая практически не поддается решению строго математическими средствами — речь идет об аппроксимации с помощью сплайна с переменными узлами. В разд. 12.4 и 12.5 обсуждаются некоторые аспекты этой задачи, однако рассмотрение ее в полном объеме выходит за пределы задач нашей книги (см. раз. 12.7). В разд. 12.6 представлены некоторые возможности использования методов построения кривых по точкам в машинной графике.
