Содержание к диссертации
Введение
1. Обзор методов и средств приближения математических функций 10
1.1. Роль приближения функций в решении практических задач 10
1.2. Обзор современных систем компьютерной математики 12
1.3. Аналитический обзор численных методов полиномиальной аппроксимации 15
1.4. Численные методы приближения табличных данных 21
1.5. Метод наименьших квадратов 34
1.6. Тригонометрическая интерполяция рядами Фурье 37
1.7. Аппроксимация функциями Уолша 39
1.8. Выводы 41
2. Методы аппроксимации и интерполяции специ альных функций средствами систем компьютерной математики 43
2.1. Классификация методов интерполяции и аппроксимации специальных функций 43
2.2. Сравнительный анализ средств аппроксимации функций в современных системах компьютерной математики 46
2.3. Совмещение средств приближения функций с построением их графиков 48
2.4. Аппроксимация функций и сигналов на основе вейвлет-анализа и синтеза 49
2.5. Отражение систем компьютерной математики в Интернет 51
2.6. Перспективы онлайновых средств приближения функций в Интернете 57
2.7. Выводы 59
3. Веивлеты в технике выявления особенностей по ведения функций и сигналов 61
3.1. Необходимость учета особенностей поведения функций и сигналов 61
3.2. Основные предпосылки к вейвлет- анализу функций и сигналов 62
3.3. Основы непрерывного вейвлет- анализа функций и сигналов 64
3.4. Методика вейвлет-анализа особенностей функций и сигналов
с помощью системы компьютерной математики MATLAB 71
3.5. Специальные возможности непрерывного вейвлет- анализа 78
3.6. Выводы 84
4. Эффективная аппроксимация специальных функций с помощью систем компьютерной математики 85
4.1. Повышение эффективности аппроксимации специальных математических функций 85
4.2. Выбор метода приближения специальных функций 87
4.3. Методика рациональной (Паде) аппроксимации 89
4.4. Методика минимаксной аппроксимации 92
4.5. Оптимизация временных затрат при аппроксимации 97
4.6. Роль аппроксимации в машинной графике 99
4.7. Выводы 104
5. Реализация аппроксимации в системе компью терной математики матнематіса 4 105
5.1. Рациональная и минимаксная аппроксимации функций Бесселя 105
5.2. Аппроксимации с высокой степенью полинома 111
5.3. Минимаксная аппроксимация гамма- функции 112
5.4. Новые аппроксимации специальных математических функции 116
5.5. Моделирование сигналов 118
5.6. Комплекс программ приближения функций и ее визуализации 123
5.7. Выводы 127
Заключение 129
Список литературы
- Аналитический обзор численных методов полиномиальной аппроксимации
- Совмещение средств приближения функций с построением их графиков
- Основы непрерывного вейвлет- анализа функций и сигналов
- Методика рациональной (Паде) аппроксимации
Аналитический обзор численных методов полиномиальной аппроксимации
Обзор литературы по приближению функций показывает, что большая ее часть относится к математической литературе и почти не содержит описания методики применения современных инструментальных средств по технике приближения функций и сигналов, представленных современными системами компьютерной математики и их расширениями.
Задача приближения. Пусть имеется функция/(х) вещественной переменной х. Необходимо выполнить ее замену другой функцией ф(х) более простого вида. В большинстве случаев функция f(x) задана табличными значениями/ , fi,..., fn, которые она принимает при значениях х0, х],..., хп аргумента. Функция f(x) может быть задана также аналитически. Замена ее другой более простой функцией имеет целью получить вместо сложного аналитического выражения, которое плохо поддается анализу и расчету, гораздо более простое представление. Эта замена должна облегчить не только вычисление значения функции для значений аргумента, но также и вычисление значения производной для любой точки интервала и интеграла/ на отрезке [а,Ь] по заданным значениям/.
При нахождении функции ф(х) необходимо рассмотреть следующие вопросы: выбор класса приближенной функции; - выбор критерия близости исходной и приближающей функции; - определение погрешности - правила, которое позволяет с заданной степенью точности получить приближенное значение функции. Результаты построения приближающей функции существенно зависит от ответа на поставленные вопросы.
В вопросе о классе приближающих функций следует учитывать два фактора. Во-первых, приближающая функция должна отражать характерные особенности исходной функции. Во-вторых, она должна быть достаточно удобна для вычислений. В численном анализе применяются разнообразные классы приближающих функций. Это функции с выражениями вида 1, х, ..., хп, линейные комбинации которых формируют класс всех полиномов степени не выше п [35, 37, 41]. Другую группу образуют тригонометрические функции, формирующие, например, ряды Фурье для периодических функций. В случае, когда исходная функция имеет неравномерное распределение точек пересечения нулевого уровня и, следовательно, не обязательно является периодической, используют аналогичный класс приближающих функций в виде ряда Фурье по системе Уолша. Это объясняется сходством между тригонометрической системой функций и функциями Уолша [48].
Если исходная функция не имеет четкого периодического характера и содержит локальные особенности, то эффективность алгоритма преобразования Фурье заметно падает. Поэтому в последние годы используется новый алгоритм вейвлет- преобразование [51-55].
Выбор критерия близости определяется целью построения приближающей функции. Например, при интерполяции экспериментальных данных целесообразно использовать предварительную статистическую обработку данных, например, используя их среднеквадратичное приближение - регрессию. Это связано с тем, что исходные данные в этом случае получены в результате измерений и являются неточными в виду наличия погрешностей измерений [32].
Вопрос о точности получаемого решения во многих отношениях является основным. Качество метода приближения определяется, в первую очередь, быстротой получения решения с требуемой точностью и скоростью сходимости. Поэтому все перечисленные выше вопросы: выбор узловых точек, выбор класса приближающих функций и критерия согласия, должны быть подчинены одному критерию - вопросу о требуемой точности.
Решение вопроса точности. Рассмотрим типичную задачу полиномиальной интерполяции функции [88]. Пусть приближаемая функция р (х) должна совпадать с исходной функцией f(x) в (п+1)-точко,, то есть должно выполняться равенство: (р(х }=/(х =/ь і=0,...,п.
В качестве приближающей функции рассмотрим алгебраический полином, который часто используется, следующего вида:
Выбор конкретного значения п во многом определяется свойствами приближающей функции, требуемой точностью, а также выбором узлов интерполяции. В качестве критерия согласия принимается условия совпадения функций/и q в узловых точках: Лх,.) = Р(х/),0 = 0,1,...,л) Полином Р„(х), удовлетворяющий данному условию, будет интерполяционным полиномом.
Для задачи интерполирования в интервале [а,Ь] выбираются значения аргументов , которые соответствуют значениям /І=/(ХІ) (і=0,1,...,п) функции/ Для этой функции будет существовать и притом единственный полином степени не выше п, который принимает в узлах хг заданные значения .
Совмещение средств приближения функций с построением их графиков
В математике под специальными математическими функциями обычно подразумевают решения некоторых типов дифференциальных уравнений и вычисления интегралов, для которых характерно отсутствие представлений через элементарные функции. В данной диссертации используется несколько расширенная трактовка специальных функций. К ним будем относить еще и функции, задаваемые пользователем, а также сигналы, являющиеся функциями времени.
Как видно из рассмотренного выше, существуют разнообразные подходы к реализации задач приближения специальных функций. Эффективность применения различных методов определяется многими факторами. Трудно выделить какой-то один метод, который хорошо работал бы и давал требуемые результаты для разных практических и теоретических исследований. Поэтому предлагается выполнить некоторую классификацию рассмотренных методов. Ее удобно представить в виде структурной схемы (рис. 2.1), которая дает представление о логике построения данной классификации.
Как мы выяснили, одним из основных вопросов в решении задач приближения является вопрос выбора класса приближаемой функции. Это будет во многом определять успех приближения в целом, так как схожесть поведения исходной функции и искомой (приближаемой) определяет эффективность и качество результата приближения. Приближаемая функция должна как можно точнее отображать характерные особенности исходной функции.
Предлагаемая классификация выделяет отдельный класс задач приближения для функциональных зависимостей, полученных экспериментально. Это объясняется целесообразностью построения приближающей функции таким образом, чтобы уменьшить погрешности измерения на этапе снятия экспериментальных исходных данных.
Далее выделяются методы, которые являются уже классическими, использующие в качестве приближаемой функции алгебраический полином. Этот класс методов имеет довольно большую историю развития, и поэтому он наиболее представим по сравнению с другими направлениями в классификации. Здесь рассматриваются такие методы, как метод построения полинома Лагран-жа, полинома Ньютона, метод вычисления значения приближаемого полинома в конкретной точке методом Эйткена, метод наилучшего приближения Чебы-шева с наиболее удачным выбором узловых точек, определяющий минимальную погрешность. Одинаковым свойством для всех этих методов будет то, что результат приближения представляет собой полиномиальную функцию.
Но как, показано выше, эти методы имеют ряд недостатков, которые не способны повторить особенности поведения сложных сигналов. Поэтому далее в данном классе методов, в свою очередь, можно выделить те методы, которые направлены на улучшение качества полиномиального приближения. Это рациональные и кусочно- полиномиальные методы, которые представляют частный случай общего принципа полиномиального приближения.
Результатом рационального приближения будет рациональная функция, представляющая отношение двух полиномов. Кусочно-полиномиальный метод выполняет построение ряда полиномов, определяемых на каждом интервале отдельно и гладко соединяющихся в узловых точках (сплайн- функция, а также полином Эрмита).
Методы, использующие в качестве базисных sin- или cos- функции, то есть периодические, дают основание выделить их в отдельный класс. Подобное деление представляет метод приближения функций и сигналов рядом Фурье.
Применением непериодических функций Уолша, а также вейвлетов, в качестве базисных, определяются достаточно новые методы приближений, которые можно выделить в класс методов непериодическими функциями. Методы приближения специальных функци й
Предлагаемая классификация дает возможность оценить методы приближений. И затем, основываясь на требованиях точности приближения, простоты представления для дальнейшего использования приближаемой функции, а также возможности инструментальной реализации конкретного метода, можно сделать выбор в пользу того или иного метода.
Надо отметить, что одним из главных критериев выбора метода, будет являться характер исследуемой функциональной зависимости. Это требует предварительного анализа особенностей поведения исходной функции, что будет рассмотрено в главе 3.
Сравнительный анализ средств аппроксимации функций в современных системах компьютерной математики
Выполним сравнительный анализ средств аппроксимации в системах компьютерной математики (см. табл. 1). Здесь указаны наименования методов, имена пакетов систем компьютерной математики, функции и пакеты расширений, реализующих конкретные методы. Данные анализа позволяют оценить свойства пакетов систем относительно возможности проведения различных видов аппроксимации. Как видно (табл.1) все рассмотренные системы имеют встроенные функции, а также пакеты расширений для проведения различных методов приближения сигналов и функций. Кроме того, каждая, из рассмотренных систем компьютерной математики, дает возможность реализовать различные алгоритмы аппроксимации.
Системы Derive и MuPAD реализовывают методы, которые можно отнести к широко используемым. Это разложение функций в ряды Тейлора, Фурье. Таблично заданные функции приближаются с помощью функций, реализующих алгоритмы полиномиальной интерполяции. Эти методы хорошо приближают непрерывные функции, без разрывов и скачков. Надо отметить, что функции pade в Derive и spline в MuPAD, имеют неплохие результаты при аппроксимации более сложных по форме сигналов.
Основы непрерывного вейвлет- анализа функций и сигналов
Регулярно на сайте отражается оперативная информация о предстоящих семинарах и практических конференциях, на которых обсуждаются возможности пакета при решении различных задач. Для начинающих пользователей студенческий сайт http://www.maple4students.com/ main.html, где пользователь имеет возможность работать с обучающей программой по Maple, разработанной математическим отделом Центрального колледжа в Сиэтле (Seattle Central Community College). Разделы данной обучающей программы на практических примерах знакомят со многими возможностями, что удобно при изучении пакета. Полный обучающий курс в интерактивном режиме может быть установлен на компьютере пользователя или через Internet бесплатно. Использование подобных новых информационных технологий расширяет круг пользователей на этапе освоения пакета, дает хорошие перспективы в области образования и самообразования [87].
Mathematica. Разработчиком системы Mathematica является компания Wolfram Research (США) и ее основатель проф. Стивен Вольфрам (Stephen Wolfram). Для установки связи с Internet-страницей компании Wolfram Research необходимо указать адрес www.wolfram.com (рис. 2.9).
Надо отметить, что содержание сайта часто меняется, так как создаваемая система Matheamtica совершенствуется. Если в начале 2001 года инфор мация на ней была посвящена новой версии системы Mathematica 4.1, то с ноября 2001 года главной является информация о новой возможности работы с системой - это работа с ней в онлайновом режиме (в
Новый вариант работы с системами компьютерной математики дает возможность выполнять различные расчеты, а также расчеты для различных видов приближений, даже в том случае, если пользователь не имеет какой либо математической системы. Ему необходимо иметь доступ к Internet. Эту возможность предлагает компания Wolfram Research.
После выбора ссылки о представлении Web-Mathematica на главной странице компании Wolfram Research (www.wolfram.com/products /webmathematica/), имеем начальную страницу работы с Web-Mathematica (рис. 2.10). круг бесплатных примеров, где можно изменять исходные данные и тем самым, проводить исследование собственной математической модели. Так, например, для вычисления регрессии таблично заданных исходных данных можно выбрать соответствующее решение, где возможны три варианта: линейная, квадратичная или кубическая сплайн-интерполяция.
В результате пользователь получает расчет (рис. 2.11) коэффициентов полинома, график полиномиальной регрессии с исходными точками, а также максимальное значение отклонения в точках интерполяции. Результат вычисления полиномиальной регрессии в Web Mathematica.
Надо отметить, что применение данной технологии дает быстрые результаты, но далеко не лучшие в смысле поиска интерполяционного полинома с минимальной погрешностью. Это объясняется тем, что данная технология нова и пока, конечно, уступает возможностям пакета Mathematica.
1. Предложенная классификация известных методов приближений дает возможность целенаправленного эффективного выбора подходящего метода приближения специальных математических функций. 2. На основании детального аналитического рассмотрения задач приближения функций и сигналов можно сделать вывод о перспективности для их решения нового направления информационных технологий - систем компьютерной математики, уже представленных рядом таких серийно выпускаемых систем (Derive, MuPAD, Mathcad, Mathematica, Maple, MATLAB и др.).
3. Необходимость и важность быстрого и простого решения задач аппроксимации и регрессии подтверждается наличием в современных системах компьютерной математики (MATLAB) специальных инструментов, которые совмещают функции аппроксимаций и графиков результата приближения, а также графика погрешности.
4. В рамках сказанного особое значение имеет применение современных средств анализа функций и сигналов, в том числе заданных в виде временных рядов. Этот анализ должен в максимальной степени учитывать важнейшие особенности функций, такие как разрывы функций и их производных, периодичность, наличие асимптот и т.д.
В ближайшем будущем перспективными могут стать онлайновые средства работы с системами компьютерной математики в Интернете, в частности решение с их помощью задач по приближению функций и сигналов.
Необходимость учета особенностей поведения функций и сигналов
В данной диссертации определяются понятия функций и сигналов как равноценные. В математике функция/fx) обычно задается как функция независимой переменной х. Однако, достаточно часто рассматриваются функции времени вида f(t) или y(t). Сигнал s(t) также является временной функцией. Для сигналов нередко имеется дискретное представление значений функции в заданные моменты времени.
Поведение функции или сигнала будет определять метод приближения, так как любое приближение имеет свои необходимые условия выполнения и свои особенности проведения приближений. Поэтому предварительным этапом к проведению приближения является процедура исследования поведения исходной функции. Дискретизация функций и сигналов обычно требует применения методов интерполяции, а иногда и экстраполяции (прогноза), поскольку просмотр просто дискретных значений их мало нагляден и труден.
Поведение функции характеризуется рядом ее особенностей. К таким характеристикам относятся: область определения и точки разрыва функции, периодичность, нули функции, интервалы знакопостоянства, асимптоты, экстремумы и интервалы монотонности, точки перегиба и интервалы выпуклости и вогнутости. Проводимые исследования функции имеют цель определить интервал, где функция непрерывна. Непрерывность функции является главным критерием проведения операции приближения. Как рассматривалось выше, задача о приближении функции заключается в том, чтобы данную функцию f(x) заменить другой функцией. Если в качестве приближающей функции выбирают полином (1.1) так, чтобы отклонение функции f(x) от Q(x) на заданном множестве Х={х} было наименьшим.
Методика рациональной (Паде) аппроксимации
Если выбирать коэффициенты аппроксимирующей функции из условия минимума функции (4.9), то критерий оценивания параметров называется минимаксным, а соответствующая ему задача аппроксимации - минимаксной или задачей чебышевского приближения. Минимаксный критерий впервые был рассмотрен П.Л.Чебышевым во второй половине XIX века.
При решении минимаксных задач часто используется класс алгоритмов Ремеза и Вале-Пуссена. В этих алгоритмах используются множества точек, удовлетворяющих условиям чебышевского альтернанса. Пусть функция y=f(x) задана на отрезке [а,Ь], а функция Рп(х) - ее аппроксимирующий полином, при чем остаток Rn(x)=f(x)-Pn(x).
Совокупность точек x0 xi ,.. xn xn+i отрезка [а,Ь] удовлетворяет условиям чебышевского альтернанса, если значения остатка Rn(x) в этих точках удовлетворяют условиям Rn(x0) = -Rn(xx) = Rn(x2) = ... = (-\)n+lRn(xn+l) = ±max\Rn(x)\. (4.10) a x b
Для поиска решения задач полиномиальной аппроксимации используются численные процедуры, носящие итерационный характер. В этих методах осуществляется последовательный выбор точек, удовлетворяющих условиям (4.10).
В достаточно общем виде процедуру поиска точек чебышевского альтернанса при решении задачи полиномиальной можно сформулировать следующим образом: - на отрезке [а,Ь] выбирается начальное приближение XQ0) х/0) ... хп(0) хп+/0) для точек альтернанса, а параметр цикла к=0; - пусть на &-той итерации найдено приближение хп(к) х/к) ... хп(к) хп+/к). По значениям функции в этих точках определяются коэффициенты полинома Рп(к)(х) и параметр juk, удовлетворяющие условиям допустимая погрешность при определении точек альтернанса; - при выполнении условий (4.12) - (4.14) полученные на &-той итерации точки x0 xi ... xn xn+1 является точками приближения чебышев-ского альтернанса, а соответствующий им полином - оптимальным по минимаксному критерию. Данный алгоритм сходится со скоростью геометрической прогрессии. Для определения коэффициентов полинома Р„(х) и параметра // необходимо решить систему из (п+2)-х уравнений (4.11), содержащую п+2 неизвестных. Если функция у=/(х) задана на дискретном множестве из п+2 точек, то параметр /лк можно вычислить по формуле
Полином Лагранжа наиболее точно аппроксимирует функцию у=/(х), если его узлы является нулями полинома Чебышева п-ото порядка. Поэтому в качестве начального приближения для точек альтернанса наиболее целесообразно выбрать точки
Скорость сходимости алгоритма чебышевской аппроксимации существенно зависит от эффективности алгоритма поиска приближения на каждой итерации. Простейшим из класса алгоритмов Ремеза является алгоритм Вале-Пуссена, в котором на каждой итерации осуществляется замена только одной точки приближения для точек альтернанса. Такое приближение называется текущим базисным.
Преобразование базисного множества точек в алгоритме Валле-Пуссена осуществляется следующим образом: на отрезке [а,Ь] определяется точка х, в которой остаток Rn(x)=f(x)-Pn(x) имеет максимальное значение, то есть - возможны три случая расположения точки х на отрезке [а,Ь]:
Если х х0(к) и если Rn(x)Rn(xok)) 0, то есть остатки Rn(x) и Rn(x0(k)) имеют один и тот же знак, то на (к+1) -той итерации принимается хо(к+1)=х, а все остальные точки не изменяются; если же они имеют различные знаки, то осуществляется преобразование всех точек по формулам Есшх0(к) х хп+/к), то существует отрезок [хр Хр], которому принадлежит точка х. Тогда если Rn(x)Rn(xpJk) 0, то xp.j +1)=x. В противном случае хр(к+1):=х. Все остальные точки базиса остаются без изменений.
Если х хп+/к), то осуществляется замена последней точки хп+/+ -х при Rn(x)Rn(xn+1(k)) 0. При невыполнении этого условия осуществляется преобразование всех точек базиса по формулам x/k+1 =xi+f\ при і=0,1,...,п и
Последовательность приближений, получаемых с помощью этого алгоритма, сходится к точкам чебышевского альтернанса независимо от выбора начального базиса.
В отличие от алгоритма Валле-Пуссена, в алгоритме Ремеза на каждой итерации осуществляется замена всех точек текущего базиса, в результате чего возрастает скорость сходимости к точкам чебышевского альтернанса.
Пусть аппроксимируемая функция y=f(x) определена во всех точках [а,Ь], или заданы ее значения только в N дискретных точках, принадлежащих [а,Ь]. Алгоритм Ремеза замены базиса можно сформулировать следующим образом: - пусть х0 х/0/ ... хп(0) хп+/0) - начальный базис на [а,Ь], ро -максимальное значение остатка Rj0)(x); - пусть в результате выполнения итерационной процедуры найдено к-тое приближение базиса хо(0) х/0/ ... хп{0) хп+/0), а также соответствующее значение рк Преобразование базиса в алгоритме Ремеза на (к+1)-ой итерации состоит из (п+1) шагов.
Первый шаг: на отрезке [а,х/к)] определяются две точки v0 V], в одной из которых Rjk)(x) имеет наименьшее значение, а в другой - наибольшее. В этом случае нулевая и первая точка (к+1)-ото приближения принимаются равными
Второй шаг: на отрезке [х/к+1),Х2(к)] определяются две точки vj v2 в одной из которых Rn(k)(x) имеет наименьшее значение (на этом отрезке), а в другом - наибольшее. Если Rtjk)(x](k+1))Rn(k)(vi) 0, то вторая точка (к+1)-ото приближения x2(k+1)=v2, причем если \Rn(k)(xi(k+1)) I \R(vt) , то преобразуется также и первая точка (к+1)-ого приближения x/k+1)=V]. В этом случае запоминается значение параметра g=0 и осуществляется переход к следующему шагу алгоритма. Если же Rn(k)(x/k+1))Rn(k)(vj) 0, то принимается x2(k+1)=v1 и запоминаются r=v2, g=Rn(k)(r) и т.д. Предположим, что в результате преобразований такого типа найдены базисные точки х0 + х/ + ... хр( , а на предыдущем шаге при g O получено значение г.
