Обобщение алгоритма Ремеза на случай полиномиальных сплайнов

• Автор: Сухорукова, Надежда Владимировна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2005
• Место защиты: Санкт-Петербург
• Количество страниц: 126 с. : ил.

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

Дж. Алберг, Э. Нильсон, Дж. Уолш Теория сплайнов и ее приложения [1]

1 Введение

1.1 Мотивация

1.2 Основные определения

1.3 Структура диссертации

2 Негладкая оптимизация

2.1 Квазидифферснцируемые функции

2.2 Условия экстремума

2.3 Численные методы негладкой оптимизации

2.3.1 Метод дискретного градиента

2.3.2 Метод отсекающего угла
3 Аппроксимации полиномами наилучшего приближения
3.1 Полиномы: необходимые и достаточные условия оптимальности
3.2 Алгоритм Ремеза
4 Аппроксимация полиномиальными сплайнами
4.1 Спалйны: необходимые и достаточные условия оптимальности
4.2 Обобщение алгоритма Ремеза на случай полиномиальных сплайнов
4.2.1 Задача построения линейного сплайна (ломаной), удовлетворяющего условию альтернанса
4.2.2 Задача построения полиномиального произвольной векторной степени сплайна, удовлетворяющего условию альтернанса

4.2.3 Замена базиса
4.3 Численные примеры
5 Численные эксперименты
5.1 Обобщенный алгоритм Ремеза: непрерывные функции
5.2 Обобщенный алгоритм Ремеза: дискретные функции
5.2.1 Базы данных
5.2.2 Нагревание Титана
5.2.3 База данных Пезака
5.2.4 Некоторые важные замечания и рекомендации
6 Теория аппроксимации в задачах налогообложения
6.1 Постановка задачи
6.2 Необходимые и достаточные условия оптимальности
6.3 Численные эксперименты с модельными функциями
6.3.1 Негладкий случай
6.3.2 Гладкий случай
7 Сплайны со свободными узлами
7.1 Непрерывная и дискретная аппроксимация
7.1.1 Приближение непрерывных функций
7.1.2 Дискретная аппроксимация (равномерная аппроксимация
и критерий наименьших квадратов)
7.2 Полиномиальные сплайны со свободными узлами: вычислительные аспекты
7.3 Численные экспериметны с непрерывной функцией
7.4 Численные эксперименты с дискретными функциями: сравнение
алгоритмов
7.4.1 Метод Г. Белякова (Алгоритм 1)
7.4.2 Конкретизация Алгоритма
7.4.3 Новый алгоритм (Алгоритм 2) для приближения дискретной функции (базы данных)
Глава 4. Аппроксимация полиномиальными сплайнами

Сплайн представляет из себя непрерывную ломаную, поэтому имеем следующую систему равенств
Отсюда
а + Ьі — й2^і + Ь21 e 202 + 02 = + Ьз,
. яп_і0п_і -Р Ьп—і = (in0n—i -Р Ьп.
&2 = а1^1 + 6l — Й2^1)
Ьз = Яі0і -Р аг(^2 — 0і) — яз^2 + Ь,
Ьп — Яі^х + й2(^2 — 0і) + .. • + ап_і(0п_і — 0п-г) — an0n_i -(
(4.2.2)
fc—і
&A: — c101 -)- ^ ^Q*i(6i 6{—j ak9k-i -P bi, h — 2,... ,n.

Из (4.2.32) и (4.2.33) получаем следующую систему ait-o + bi — С = /(£о),
Яі£і + Ьі + С = /(И),
аі0і + Ьі -Р аг(£2 — 0і) ~ С = /(£2)1
fti0i + 61 + аг(02 — 0і) + ®з(£з — О2) + С = /(£з):
Яі0і + Ь + ... -Р an(xn — 0„_i) + (—l)n+1C = f(tn),
, a.ві + &! + ... + (—1 )n+2C — f(tn+i).
(4.2.3)
Это система относительно переменных (щ, аг, ..., а„, 6і, С)г, вектор свободных членов (/(£о), /(И), ■ ■ •, /(£п), /(£п+і))г, а матрица системы имеет вид
' to 0
£1 0
0i £2 — 01
0і 02 - 01 £3
0i 02 — 01
0i 02 — 01
u 02 — 01
-1

0П_1-0П_2 £П-0П_1 1 (-1Г+1
Вп- 1-&П-2 £„+1~0п-1 1 (-1Г+2
Найдем определитель матрицы , и покажем, что он отличен от нуля, поэтому решение системы (4.2.5) существует и единственно.