Диссертация (1150736), страница 31

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 31)

. ., известны значения 1 , 2 , . . ., функции . Требуется оценить производную функции порядка .В качестве оценки производной функции выберем соответствующуюпроизводную интерполяционного полинома (). Тогда погрешность интерполяции будет равна() () = () () − () ().Лемма 33 Пусть ≥ 1 и - целые числа и ≥ ≥ 0, функция - разгладкая на отрезке [, ], и имеет ≥ различных нулей на на отрезке[, ]. Тогда () имеет не менее − различных нулей на на отрезке [, ].Доказательство. Утверждение выводится индукцией по из теоремы Ролля.Теорема 18 Пусть – некоторое число и функция имеет непрерывныхпроизводных на отрезке [, ], содержащем все узла интерполяции и точку .Тогда на отрезке [, ] существует такая точка , что* () =() * () () (),() =( − )!−∏︁( − * ), {* |() (* ) = 0}.=1Доказательство.По лемме 33 функция () () имеет не менее − различных нулейна на отрезке [, ].

Рассмотрим интерполяционный полином () степени − − 1, для функции в корнях * (). Алгебраические полиномы () и() степени − − 1 совпадают в − различных точках. Следовательноони равны. Воспользуемся теоремой 17 для полинома () для завершениядоказательства.Следствие 8 Из теоремы 18 следует, чтоmax |() ()| ≤ ( − )−max | * ()| ≤.( − )! ( − )!Приведенная оценка не зависит от интерполируемой функции и узлов интерполяции.194B.4Погрешность аппроксимации интерполяционным полиномомВ задаче аппроксимации полином не является интерполяционным, то естьв известных точках он принимает значения, отличные от значений аппроксимируемых функций.

Оценим отклонение аппроксимационного полинома отинтерполяционного полинома той же степени, если погрешности в узлах интерполяции известны.Рассмотрим числа Лебега для системы интерполяционных узлов(1 , . . . , ), ∈ 0 , где 0 = [−1, 1], через фундаментальные полиномы изопределения 17, = sup∑︁∈[−1,1] =1()| ()|,0 ≤ < ,≥1Лемма 34 Оценим норму производной интерполяционного полинома, построенного по парам (1 , 1 ), . . . , ( , ),‖(, )() ‖ ≤ , ‖‖.Доказательство.Рассмотрим интерполяционный полином в форме Лагранжа()‖(, ) ‖ = ‖∑︁() () ‖≤=1∑︁()‖ ()‖| | ≤ , ‖‖=1Лемма 35 Числа Лебега при линейных преобразованиях переменных связаныравенствомˆ , =(︂−2)︂−, ,ˆ , - числа Лебега для результата линейного отображения исходной сигде стемы узлов с 0 на промежуток [, ].Доказательство.

Пусть ∈ [−1, 1], рассмотрим замену переменнойˆ =−++22195Для системы (ˆ1 . . . ˆ ) узлов фундаментальные полиномы () = ˆ (ˆ),дифференцируя раз, получаем() ()(︂=−2)︂ˆ() (ˆ ).Тогда числа Лебега связаны по определению выражаются как(︂)︂−∑︁−()ˆ , = sup|ˆ (ˆ)| =,2^∈[−,]=1Можно поставить задачу выбора оптимальной системы узлов, минимизирующей число Лебега. Выражение для оптимальных узлов на сегодняшнийдень не известно. Хорошим приближением считаются расширенные чебышевские системы узлов [79], получающиеся отображением чебышевской системыузлов(2 − 1),2на интервал [3/(2), /(2)]: = 1, . .

. , , = (2 − 1) −1 ˆ = ,22 = 1, . . . , .При этом ˆ1 = 1, ˆ = −1. Из леммы следует, что (ˆ) < ( ).Теорема 19 Пусть ∈ ( ; [, ]]), = (1 , . . . , ) ∈ R - произвольный вектор, = (1 , . . . , ) - произвольная система узлов интерполяциина = [, ], (, ) - полином степени − 1, такой что ( , ) = , = ( (1 ), . . . , ( )) ∈ R . Тогда для любого 0 ≤ < справедливо неравенство()‖(, )(︂2− (, ) ‖ ≤ (0 )−())︂sup | ( ) − |.1≤≤Доказательство. Воспользуемся леммами 34 и 35‖(, )() − (, )() ‖ = ‖(, − )() ‖ ≤ , ‖ − ‖)︂(︂)︂(︂2−=, ‖ − ‖ = (0 )sup | ( ) − |2 − 1≤≤.196Теорема 20 Пусть ∈ ( ; ), = (1 , . .

. , ) ∈ R - произвольный вектор. Тогда для любых 0 ≤ < и ∈ справедливо неравенство(︂)︂−2(−)+ (0 ) sup | ( ) − |.‖ () () − (, )() ‖ ≤( − )!−1≤≤Доказательство. Воспользуемся неравенством треугольника:‖ () () − (, )() ‖ ≤ ‖ () − (, )() ‖ + ‖(, )() − (, )() ‖.Оценим первое слагаемое с помощью теоремы 18 и второе слагаемое с помощью теоремы 19.Это неравенство позволяет оценить точность приближения функции полиномом по значениям невязок в произвольных узлах интерполяции.

В отличиеот оценки погрешности полиномов наилучшего равномерного приближения,в случае выбора неоптимальных узлов интерполяции она является грубой изза погрешности округления, что приводит к избыточному измельчению сеткисегментов при кусочной аппроксимации и избыточной точности коэффициентов.197Приложение CЗадача смешанногоцелочисленного линейногопрограммированияКак известно, каноническая форма задачи линейного программированияопределяется следующим образом:min{ : ≤ }.Отличительной особенностью задачи оптимизации таблиц являетсянебольшой набор переменных и очень большое количество ограничений, пропорциональное количеству узлов сетки.

Только ограничения в окрестностяхточек максимума отклонения интерполяционного полинома имеют значение,все остальные ограничения выполняются автоматически.Другой важной особенностью задачи сокращения таблиц является фиксированная длина мантиссы коэффициентов интерполяционных полиномов. Длярешения задачи линейного программирования с ограничениями на целостьзначений некоторых переменных, называемой задачей смешанного целочисленного линейного программирования, используется алгоритм ветвей и границ.198C.1Выбор алгоритма решения задачи линейногопрограммированияВ работе задача линейного программирования решалась с помощью функции из оптимизационного пакета системы [80]. Однако ее использование заслуживает некоторой дискуссии, поскольку функция реализуеттри различных алгоритма решения, только один из которых подходит с некоторыми модификациями для решения рассматриваемого класса задач.Часто задача линейного программирования решается с помощьюсимплекс-метода [81].

Метод гарантированно сходится и находит точное решение задачи. Cкорость сходимости метода является экспоненциальной в худшем случае [82]. Для случайных матриц количество шагов симплекс-метода всреднем линейно от количества переменных [83] Наблюдается медленная сходимость для рассматриваемого класса задач, что делает метод неприменимымдля задач больших размерностей.Другим, более новым методом решения является метод внутренней точки,предложенный Карамаркаром [84].

Метод основан на определении барьернойфункции, быстро возрастающей при приближении к границе множества допустимых решений. Минимум суммы барьерной и целевой функции сходится крешению при уменьшении скорости роста барьерной функции. В отличие отсимплекс-метода, решения являются внутренними точками множества допустимых решений. Для рассматриваемого класса задач метод не сходится изза плохой обусловленности вспомогательной задачи оптимизации, вызваннойбольшим количеством избыточных ограничений.Последний метод является модификацией метода квадратичной оптимизации с активным множеством ограничений, предложенного Гилом [85] длясокращения эффективной размерности задачи. В этом методе на каждом шаге в множестве ограничений выбирается активное подмножество ограниченийˆ = ˆ. Остальные ограничения являются неактивными.типа равенство Общая схема метода описана листингом C.1.

При превышении количестваитераций метод может успешно завершиться в недопустимой точке, что частопроисходит в реализации функции .199Таблица C.1: Псевдокод метода с активным множеством ограничений.Найти начальную точкуiter = 0repeat until удовлетворяет ограничениям ∨ iter > MaxIteriter = iter + 1решить задачу с активными ограничениями типа равенстванайти множители Лагранжа для активных ограниченийудалить ограничения с отрицательными множителямидобавить нарушенные ограничение в множество активныхend repeatДля достижения цели оптимизации необходимо несколько раз перезапускать функцию , пока ограничения не будут удовлетворены.C.2Метод ветвей и границ для решения задачисмешанного целочисленного линейного программированияДля решения задачи минимизации таблиц требуется метод, обеспечивающий целость значений коэффициентов полиномов.

Простое округление решения непрерывной задачи приводит к существенным ошибкам. Для решениясмешанной целочисленной задачи используется метод ветвей и границ. Сутьметода в разделении пространства решений на два подпространства ≤ ⌊¯ ⌋и ≥ ⌈¯ ⌉, где ¯ - компонент текущего решения. Таким образом, искомыйоптимум может находиться либо в одном, либо в другом подпространствах.Общая схема метода целочисленного линейного программирования описаналистингом C.2. Здесь = , - текущая граница для метода ветвей играниц. LP - функция решения вспомогательной задачи линейного программирования.

Смешанный алгоритм отличается от листинга тем, что не все переменные округляются. Параметр определяет точность дискретизации целочисленных переменных и существенно влияет на скорость сходимости метода.200Таким образом, метод является приближенным, ‖* −‖ ≤ , где * - истинноерешение. Это должно учитываться при применении алгоритма.Обратим внимание, что любое нарушение ограничений, добавляемых алгоритмом при решении вспомогательной задачи линейного программирования,ведет к зацикливанию алгоритма.201Таблица C.2: Псевдокод метода ветвей и границ для целочисленноголинейного программирования=∞(ˆ, ˆ, )=ILP(ˆ, , , , , )(ˆ, ˆ)=LP( , , , )ˆ = if ˆ ≥ ˆreturnendif‖ˆ − ⌊ˆ + 0.5⌋ ‖ < ˆ = ˆreturnend∃, |ˆ − ⌊ˆ + 0.5⌋| ≥ (, ) = { ≤ ∧ ≤ ⌊ˆ ⌋}(¯, ¯, )=ILP(¯, , , , , )ˆif ¯ < ˆˆ = ¯, ˆ = ¯, ˆ = ¯end(, ) = { ≤ ∧ ≥ ⌈ˆ ⌉}(¯, ¯, )=ILP(¯, , , , , )ˆif ¯ < ˆˆ = ¯, ˆ = ¯, ˆ = ¯endend202Приложение DРеализация специальныхвидов БПФСпособы реализации БПФ хорошо разработаны.

Характеристики

Список файлов диссертации