Диссертация (1150736), страница 12
Текст из файла (страница 12)
Тогда за размер таблицы можно считать количество ненулевых битов данных в таблице. Количество ненулевых битов для коэффициентов дефектов в промежуточных узлахквазисплайна не превосходит≤02∑︁−1 −1∑︁max(0, 2 + ⌈ + log2 |, |⌉),=0 =0где - минимальная допустимая длина дробной части коэффициента полиномиальной аппроксимации в одном сегменте. Дополнительная единица требуется для хранения знака , .63Поставим задачу минимизации таблиц для , . Нелинейный функционал неудобен для минимизации. Рассмотрим более простую линейную задачуarg min{, } ∑︁−1∑︁, |, |.=0 =1Параметры , выбираются таким образом, чтобы занулить наибольшее количество коэффициентов.2.3Оценка точности аппроксимации на одномсегментеДля оценки ошибки метода аппроксимации нам потребуются сведенияиз теории интерполяции, см., например, ( [72], c.
122-141). Они изложены вприложении B.Воспользуемся этими результатами для оценки точности аппроксимацииполиномом на одном сегменте при наличии дополнительных ограничений.2.3.1Погрешность аппроксимации интерполяционным полиномом с ограничениями типа неравенстваВведение дополнительных ограничений нарушает постановку задачи нахождения полиномов наилучшего равномерного приближения. Поставим аналогичную по смыслу задачу, сохраняющую корректность при наличии ограничений. Заменим требование равномерного приближения на отрезке на требование равномерного приближения на сетке точек. Задача равномерного приближения является предельным случаем новой задачи при устремлении шагасетки к 0.Найдем оценку погрешности полиномиальной аппроксимации при ограничении на отклонение полинома от аппроксимируемой функции на сетке сдостаточно мелким шагом.Введем несколько определений64Определение 3 Обозначим (, [, ]) класс всех функций на отрезке [, ],у которых производная порядка ограничена заданным числом:| () ()| ≤ .Определение 4 Пусть (1 , .
. . , ) — набор интерполяционных узлов на промежутке [, ]. Числами Лебега для этого набора назовём, = sup∑︁∈[−1,1] =1()| ()|,0 ≤ < , ≥ 1,где () — фундаментальные полиномы из определения 17 в Приложении B.Сформулируем теорему об оценке точности аппроксимации интерполяционным полиномом.Теорема 1 Пусть ∈ ( ; ), ≥ 2 и задана система узлов ={0 , . . . , }, ∈ [, ], содержащая узлы интерполяции ˆ = {ˆ1 , .
. . , ˆ },ˆ ⊂ и удовлетворяющая условию0 = , = , < +1 , +1 − < ,0 ≤ < .Рассмотрим интерполяционный полином , построенный по интерполяционным данным (ˆ, ), таким что sup | − ( )| = 0 .Тогда выполняется неравенство(︂)︂−2,2 (0 )2 ( − )0 ≤ ‖ − ‖ ≤ 0 + +0 .8( − 2)!2( − )2Доказательство. Обозначим = ‖ − ‖ = | (* ) − (* )|.
Точка * существует, поскольку непрерывная функция на компакте достигает своего экстремума.Точка * может совпадать с узлом для некоторого , тогда = 0 .В противном случае * будет экстремальной точкой гладкой функции, поскольку границы отрезка являются узлами и ′ (* ) − ′ (* ) = 0.65Выберем ближайший к * узел , = |* − | ≤ .2Рассмотрим первый член и остаток разложения в ряд Тейлора ( ) − ( ) = (* ) − (* ) + 2 ′′( () − ′′ ()).2Используя неравенство треугольника, напишем следующую оценку: 2 ′′| (* ) − (* )| ≤ | ( ) − ( )| + | () − ′′ ()|.8Заменяя точечные оценки номами, получим 2 ′′ ≤ 0 + ‖ − ′′ ‖.8Используя оценку точности аппроксимации для второй производной изтеоремы 20, перепишем неравенство как)︂(︂−2()(−),20+0 . ≤ 0 + 28( − 2)!2( − )2Теорема в этой форме позволяет применение без замены переменных иперехода к интервалу [−1, 1].
Для практического применения необходимо заранее вычислить ,2 (0 ) для известной системы узлов на интервале [−1, 1].2.3.2Погрешность квадратичной и кубической аппроксимации интерполяционным полиномомС практической точки зрения нам интересна квадратичная и кубическаяинтерполяция с симметричным расположение узлов на интервале [−1, 1].Для квадратичной интерполяции единственной такой системой является(−1, 0, 1). Система (−1, 0, 1) совпадает с системой расширенных чебышевскихузлов при = 3.Лемма 3 Для системы узлов (−1, 0, 1) 3,2 = 4.66Доказательство. В соответствии с определением 4,3,2 =sup3∑︁|′′ ()|∈[−1,1] =10 () = ( − 1)( + 1) = 3 − ,′ 0 () = 32 − 1(︂)︂( − 1)( + 1)() =, −( − 1)( + 1),223∑︁′′|′′ ()| = 4. () = (1, −2, 1),3,2 ==1Эти узлы содержатся в сетке узлов с шагом = 2− .Для кубической интерполяции симметричные на [−1, 1] системы описы√ваются как (−1, −, , 1) с параметром ∈ (0, 1).
При = 2 − 1 системасовпадает с системой расширенных чебышевских узлов при = 4.Лемма 4 Для = [−1, 1] и системы узлов (−1, −, , 1), min∈(0,1) 4,2 = 24, идостигается при = 0.5.Доказательство. По определению 44,2 =sup4∑︁|′′ ()|,∈[−1,1] =12 220 () = − + + 4 − 2 ,′ 0 () = −2 − 22 + 43 ,(︃( + )( − )( − 1) ( + 1)( − )( − 1)() =,,22 − 22 − 23)︃( + 1)( + )( − 1) ( + )( − )( + 1),,23 − 22 − 22(︃−2 + 2 + 3 − 2 2 − − 3 + =,,22 − 223 − 2)︃232232 − + − + − − ,23 − 222 − 2)︂(︂6 − 2 −6 + 2 6 + 2 −6 − 2′′ () =,,,,22 − 2 23 − 2 23 − 2 22 − 2(︂)︂1334,2 =sup|3 − 1| + | − 1| + | + 1| + |3 + 1| .1 − 2 ∈[−1,1]67Функция кусочно-линейна и, следовательно, достигает экстремумов наконцах интервала и в точках излома ∈ {1, −1, 1/3, −1/3, /3, −/3}.
Из симметрии относительно 0 мы можем рассмотреть только точки ∈ 1, 1/3, /34,2 =1626max{6+,2+,4}=.1 − 2 − 2Минимум достигается в экстремальной точке6(−1 + 2)4,2== 0.(−1 + )2 2min∈(0,1) 4,2 = 24, и достигается при = 0.5Дополнительным преимуществом является то, что эти узлы всегда содержатся в равномерной сетке с шагом = 2− . Такая система узлов не являетсярасширенной чебышевской.Используя точную оценку ошибки, мы можем найти допустимую полиномиальную аппроксимацию степени при помощи решения задачи линейного программирования. При этом на коэффициенты полиномов накладываетсяограничение представимости с помощью чисел с фиксированной точкой.2.4Расчёт таблиц при помощи целочисленноголинейного программированияПредположим, что фиксирован следующий способ расчёта аппроксимацийзаданной функции на заданном промежутке определения ∆.
Промежуток∆ разбивается на отрезки, и внутри каждого отрезка функция приближается полиномом. В памяти хранятся параметры, необходимые расчёта значенийполиномов по всем отрезкам. Требуется минимизировать размер этой памяти.В соответствии с утверждением теоремы 1, равномерная точность аппроксимации интерполяционным полиномом гарантируется на всём отрезке определения функции, если обеспечена точность аппроксимации на заданной сетке отсчётов ( ). Аппроксимация на сетке отсчётов определяется конечнымнабором линейных неравенств, и с ней могут быть связаны задачи линейного программирования. Для получения округленных значений коэффициентв68будем применять метод целочисленного линейного программирования. Необходимые сведения изложены в приложении C.2.4.1Целочисленная аппроксимация на одном сегментеВ данном разделе представлены обозначения для одной из задач целочисленного линейного программирования, которые далее потребуются для основных формулировок.Предположим, что требуется аппроксимировать функцию многочленом() степени на заданной сетке отсчётов:{︃ = max∈[0..
] | ( ) − ( )|, 0 = 0, > −1 , = 1,∑︀* = min , = =0 .Задача оптимальной аппроксимации на сетке отсчётов можно следующимобразом сформулировать в каноническом виде:⎧ (︃)︃(︃)︃⎪ −1⎪⎨ˆ ≤,− −1−⎪⎪⎩ * = min^ ˆ.′Здесь = { },=0,=0 - матрица Вандермонда, = ( (0 ), . . . , ( )) -вектор значений в узлах, ˆ = (0 , . . .
, )′ - вектор переменных, ˆ - целеваяфункция, где = (0, . . . , 0, 1).Для нахождения округленных коэффициентов полинома используется метод смешанного целочисленного линейного программирования. Вводятся дополнительные ограничения на переменные: ˆ ∈ ( ) +1 ×+ , где — множество двоичных дробей с цифрами после запятой. Использование целочисленного программирования обеспечивает существенно лучшую точностьпо сравнению с округлением коэффициентов к ближайшей представимой точке. Это позволяет сэкономить 1-2 бита на каждом коэффициенте.В отличие от алгоритма Ремеза, метод на основе линейного программирования позволяет не только приближать оптимальные по точности интерполяционные полиномы, но и решать задачу в условиях ограничений на достаточную точность аппроксимации и на значения полиномов в узлах.
Это дости69гается ценой дополнительных вычислительных затрат на решение задачи набольшом наборе узлов.2.4.2Случай квазисплайнаФункция, составленная из аппроксимирующих полиномов на соседних отрезках, образует квазисплайн. Метод уменьшения размера таблиц, изучаемыйв данном разделе, основан на группировке нескольких соседних отрезков интерполяции и далее на совместном кодировании коэффициентов многочленовна этих отрезках.Идея уменьшения размера таблиц полиномиальной интерполяции связанас тем, что аппроксимирующие полиномы на соседних сегментах могут иметьизбыточную информацию, которую можно учесть. Таким образом, каждая секция таблицы данных содержит параметры некоторого квазисплайна.В конце данного раздела будет показано, что при помощи решения вспомогательной задачи линейного программирования и аналитических оценок потеореме 1 длины таблиц можно существенно сократить таким способом дляряда элементарных функций.Для аппроксимации функций часто используются гладкие сплайны минимального дефекта.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
