Разработка и реализация численных алгоритмов. Полиномиальная интерполяция
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
одить значения функции f(x) для очень большого количества значений аргумента, то прямой способ потребовал бы громадной вычислительной работы. В этом случае для уменьшения объема вычислений прибегают к интерполированию, т.е. вычисляют несколько значений f(xi) (i=0, 1,..., n) и по ним строят простую интерполирующую функцию F(x), с помощью которой и вычисляют приближенные значения f(x) в остальных точках.
Интерполяцией функции f(x) называется замена ее функцией F(x) определенного класса, совпадающей с f(x) в точках xk. При этом точки xk называются узлами интерполяции.
Если интерполяционная функция F(x) строится на всем рассматриваемом интервале изменения аргумента х, то такая интерполяция называется глобальной (когда F(x) проходит через все узлы). В противном случае интерполяцию называют кусочной или локальной (когда находим F(x) по некоторым узлам).
Погрешностью интерполяции функции f(x) на некотором отрезке называется максимум величины |f(x)-F(x)| на этом отрезке.
Типы интерполяции
1.Полиномиальная;
2.Тригонометрическая;
.Экспоненциальная.
Наиболее важным и распространенным типом интерполяции является полиномиальная. Это обусловлено как большей простотой вычисления полиномов по сравнению с другими классами интерполирующих функций, так и более развитым математическим аппаратом.
.3 Интерполяция методом Лагранжа
Один из подходов к задаче интерполяции это метод Лагранжа. Основная идея этого метода состоит в том, чтобы прежде всего найти многочлен, который принимает значение 1 в одной узловой точке и 0 во всех других.
Пусть на отрезке заданы точки , (узлы интерполирования), в которых известны значения функции . Задача интерполирования алгебраическими многочленами состоит в том, чтобы построить многочлен
степени n, значения которого в заданных точках , , совпадают со значениями функции в этих точках.
Запишем систему многочленов n-й степени:
Составим линейную комбинацию этих многочленов (их количество равно n + 1) с коэффициентами линейной комбинации, равными значениям сеточной функции, получим многочлен n-й степени:
(3)
Многочлен (3) называют интерполяционным многочленом Лагранжа n-й степени, так как он, во-первых, удовлетворяет условию интерполяции
и, во-вторых, имеет n-ю степень.
Интерполяционный многочлен Лагранжа обладает тем недостатком, что в случае, когда добавляются новые узлы интерполяции, все слагаемые необходимо пересчитывать. Но, с другой стороны, он обладает тем достоинством, что интервалы между узлами могут быть неравномерными:
Если у нас есть свобода выбора точек x0,.., xn, через которые мы будем проводить полином, то можно повысить точность интерполяции на выбранном нами отрезке [a, b] за счет особого способа выбора точек. Обычно рекомендуется выбирать точки xi так, что они будут корнями полинома Чебышева n+1-ой степени, определенного на отрезке [a, b]. Это расположение определяется следующими формулами:
2. Анализ требований
Интерфейс: Т.к. основной структурой нашей программы является модуль, то для более легкого использования другими пользователями будет доступна только одна функция, которая сама будет управлять входными данными и предоставлять рассчитанный интерполирующий полином.
Входные данные: уравнение функции, строковое представление интервала, переменная x и число точек интерполяции.
Выходные данные: значение интерполирующего полинома.
Основные функции:
1)Основная функция вычисление интерполяционного полинома и перенаправлением входных данных.
Входные данные: строковое представление функций, строковое представление интервала, переменная x и число точек итерации.
Выходные данные: значение полинома.
2)Функция обработки входного интервала представленного в виде строки. Входные данные: строковое представление интервала.
Выходные данные - массив из 2-х элементов содержащий нижнюю и верхнюю границу интервала.
3)Функция вычисления оптимальных значений переменных х0, х1, …, хn.
Входные параметры: верхняя и нижняя граница интервала.
Выходные параметры - массив переменных xi.
4)Функция выбора коэффициентов, функций и аргументов функций из уравнения представленного в виде строки
Входные параметры: строка, представляющая уравнение
Выходные параметры: глобальные переменные (static) состояния функции
5)Функция вычисления значений функций, которую мы ввели, с помощью ранее найденных оптимальных значений переменной x.
Входные данные: массив переменных xi.
Выходные данные: массив значений функций.
6)Функция вычисления значения интерполирующего полинома.
Входные параметры: массив значений функций, массив переменных xi,аргумент x.
Выходные параметры: значение интерполирующего полинома.
3. Проектирование
Архитектура: Сервисно-ориентированная архитектура
Достоинства: отсутствие конкретной привязанности к какой-либо платформе и относительно лёгкое экспортирование в другие приложение настольные или Web.
Структура данных:
1) Массивы представляющие степени и аргуме?/p>