Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Поиск Решения

Читайте также:
  1. B. Принятия оптимального управленческого решения по наиболее важным вопросам деятельности на рынке.
  2. I.5.5. Просмотр и анализ результатов решения задачи.
  3. Marilyn Manson: Ну, это – ссылка на фильм, «Chitty Chitty Bang Bang» (прим. На русский перевели как «Пиф-паф ой-ой-ой», как мне говорит кинопоиск), ты его смотрел?
  4. Автоматический поиск несоответствия в словах собеседника
  5. Алгоритм поиска подстроки Кнута-Морриса-Пратта (на основе префикс-функции)
  6. Алгоритм поиска подстроки, основанный на конечных автоматах
  7. Алгоритм решения

Этот раздел будет немного непонятным и потребует некоторых знаний в линейной алгебре. Во-первых, давайте перепишем d k - p (tk) в другом виде:

Здесь d 0, d k и d n даны, а N 0, p (tk) и Nh,p (tk) можно найти вычислением N 0, p (u) и Nh,p (u) для tk. Для удобства, определим новый вектор q k:

Затем, функцию суммы квадратов f () можно переписать так:

Далее, определим, на что же похож квадрат расстояния погрешности Вспомним тождество x . x = | x |2. Это значит, что скалярное произведение вектора x на самого себя дает квадрат его длины. Таким образом, квадрат погрешности можно переписать как

Затем, функция f () становится

Как минимизировать эту функцию? Функция f () - это эллиптический параболоид для переменных p 1,..., p h -1. Таким образом, мы можем продифференцировать f () по каждому p g и найти нули этих производных. Там, где производная равна нулю, функция достигает экстремума, в данном случае f () достигает минимума.

В вычислении производной по p g, заметьте, что все q k и Ni,p (tk) - это константы (т.e. без участия p k) и их частные производные по любой p g должны быть равны нулю. Таким образом, имеем

Возьмем второй элемент из суммы, который является суммой значений Ni,p (tk) p i . q k. Производная каждой из его составляющих вычисляется так:

Частная производная p i по p g не равна нулю только если i = g. Таким образом, частная производная второго члена суммирования равна:

Производная третьего члена уже сложнее; но все-таки не очень. Здесь испльзуется правило умножения (f.g)' = f'.g + f.g'.

Так как частная производная p i по p g равна нулю, если i не равно g, то частная производная третьего члена суммирования по p g равна:

Объединяя эти результаты, получаем, что частная производная f () по p g равна

Приравнивая ее к нулю, получим:

Так как имеется h -1 переменных, то g изменяется от 1 до h -1 и всего h -1 таких уравнений. Заметьте, что эти уравнения являются линейными для неизвестных p i. Перед тем, как продолжить, определим три матрицы:

Здесь k -й ряд P - это вектор p k, k -й ряд Q - это правая сторона k -го уравнения, а k -й ряд N содержит значения вычислений N 1, p (u), N 2, p (u),..., Nh -1, p (u) для tk. Таким образом, если исходные точки - это s -мерные векторы, то P, N и Q - это матрицы размеров соответственно (h -1)× s, (n -1)×(h -1) и (h -1)× s.

Теперь перепишем g -е линейное уравнение

в другом виде, чтобы коэффициент при p i легче читался:

Таким образом, коэффициент при p i равен

Если взглянуть на матрицу N, то видно, что Ng,p (t 1), Ng,p (t 2),..., Ng,p (tn -1) - образуют g -й столбец N, а Ni,p (t 1), Ni,p (t 2),..., Ni,p (tn -1) - i -й столбец N. Заметьте, что g -й столбец N - это g -й ряд транспонированной матрицы N, N T, а коэффициент p i равен "скалярному" произведению g -го ряда N T и i -го столбца N. Имея это ввиду, систему линейных уравнений можно переписать в таком виде

Так как N и Q известны, то решая эту систему линейных уравнений относительно P, получим искомые контр. точки.

Алгоритм

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

Вход: n +1 исходных точек d 0, d 1,..., d n, степень p, и желаемое количество контр. точек h +1;
Выход: Кривая B-spline степени p, определяемая h +1 контр. точками, которая аппроксимируется к исходным точкам;
Алгоритм:

Получаем набор параметров t 0,..., tn и узловой вектор U;
Принимаем p 0 = d 0, а p h = d n;
for k:= 1 to n -1 do

Вычисляем q k по следующей формуле:

for i:= 1 to h -1 do

Вычисляем следующее и записываем в i -й столбец матрицы Q;

/* матрица Q получена */
for k:= 1 to n -1 do

for i:= 1 to h -1 do

Вычисляем Ni,p (tk) и записываем в ряд k и столбец i матрицы N;

/* матрица N получена */
Вычисляем M = N T. N;
Находим P из M . P = Q;
Ряд i матрицы P - это контр. точка p i;
Контр. точки p 0,..., p h, узловой вектор U и степень p определяют аппроксимирующую кривую B-spline;


Дата добавления: 2015-10-29; просмотров: 120 | Нарушение авторских прав


Читайте в этой же книге: Неявные Поверхности | Поверхности Безье: Алгоритм de Casteljau | Поверхности B-spline: Важные Свойства | Поверхности B-spline: Алгоритм de Boor | Метод Длины Хорды | Центростремительный Метод | Получение Узлового Вектора | Универсальный Метод | Параметры и Узловые Векторы для Поверхностей | Нахождение Решения |
<== предыдущая страница | следующая страница ==>
Глобальная Аппроксимация Кривых| Поиск Решения

mybiblioteka.su - 2015-2024 год. (0.008 сек.)