Разработка и реализация численных алгоритмов. 
Полиномиальная интерполяция

1. Анализ предметной области

1.1 Основы численного метода

1.2 Интерполирование и приближение функции

1.3 Интерполяция методом Лагранжа

2. Анализ требований

3. Проектирование

4. Руководство программиста

5. Руководство пользователя

6. Тестирование

Заключение

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

Целью моей курсовой является разработка и реализация численных алгоритмов, нахождение интерполяционного полинома методом Лагранжа.

1. Анализ предметной области

1.1 Основы численного метода

Эффективное решение крупных естественнонаучных и народнохозяйственных задач сейчас невозможно без применения быстродействующих электронно-вычислительных машин (ЭВМ). В настоящее время выработалась технология исследования сложных проблем, основанная на построении и анализе с помощью ЭВМ математических моделей изучаемого объекта. Такой метод исследования называют вычислительным экспериментом. Пусть, например, требуется исследовать какой-то физический объект, явление, процесс. Тогда схема вычислительного эксперимента выглядит так, как показано на рис. 1. Формулируются основные законы, управляющие данным объектом исследования (I) и строится соответствующая математическая модель (II), представляющая обычно запись этих законов в форме системы уравнений (алгебраических, дифференциальных, интегральных и т. д.).

Рис. 1. Схема вычислительного эксперимента После того как задача сформулирована в математической форме, необходимо найти ее решение. Но помимо самого решения, необходимо еще изучить качественное поведение решения и найти те или иные количественные характеристики. Именно на этом этапе требуется привлечение ЭВМ и, как следствие, развитие численных методов (см. III на рис. 1). Под численным методом здесь понимается такая интерпретация математической модели («дискретная модель»), которая доступна для реализации на ЭВМ. Результатом реализации численного метода на ЭВМ является число или таблица чисел. Чтобы реализовать численный метод, необходимо составить программу для ЭВМ (см. IV на рис. 1) или воспользоваться готовой программой. После отладки программы наступает этап проведения вычислений и анализа результатов (V). Полученные результаты изучаются с точки зрения их соответствия исследуемому явлению и при необходимости вносятся исправления в численный метод и уточняется математическая модель.

Необходимо подчеркнуть, что процесс исследования исходного объекта методом математического моделирования и вычислительного эксперимента неизбежно носит приближенный характер, потому что на каждом этапе вносятся те или иные погрешности. Так, построение математической модели связано с упрощением исходного явления, недостаточно точным заданием коэффициентов уравнения и других входных данных. По отношению к численному методу, реализующему данную математическую модель, указанные погрешности являются неустранимыми, поскольку они неизбежны в рамках данной модели.

При переходе от математической модели к численному методу возникают погрешности, называемые погрешностями метода. Они связаны с тем, что всякий численный метод воспроизводит исходную математическую модель приближенно. Наиболее типичными погрешностями метода являются погрешность дискретизации и погрешность округления. Поясним причины возникновения таких погрешностей. Обычно построение численного метода для заданной математической модели разбивается на два этапа: а) формулировка дискретной задачи, б) разработка вычислительного алгоритма, позволяющего отыскать решение дискретной задачи. Как уже отмечалось, дискретная модель представляет собой систему большого числа алгебраических уравнений. Невозможно найти решение такой системы точно и в явном виде. Поэтому приходится использовать тот или иной численный алгоритм решения системы алгебраических уравнений. Входные данные этой системы, а именно коэффициенты и правые части, задаются в ЭВМ не точно, а с округлением. В процессе работы алгоритма погрешности округления обычно накапливаются, и в результате решение, полученное на ЭВМ, будет отличаться от точного решения дискретизированной задачи. Результирующая погрешность называется погрешностью округления (иногда ее называют вычислительной погрешностью). Величина этой погрешности определяется двумя факторами: точностью представления вещественных чисел в ЭВМ. и чувствительностью данного алгоритма к погрешностям округления.

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

Требования к вычислительным методам.

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

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

Реальные вычислительные алгоритмы должны учитывать эти обстоятельства, т. е. они должны быть экономичными как по числу арифметических действий, так и по требуемому объему памяти.

Рассмотрим численный метод решения систем линейных алгебраических уравнений

(1)

где, А — матрица , — искомый вектор, — заданный вектор. Предполагается, что определитель матрицы, А отличен от нуля, так что решение x существует и единственно. Для большинства вычислительных задач характерным является большой порядок матрицы А.

Методы численного решения системы (1) делятся на две группы: прямые методы и итерационные методы. В прямых (или точных) методах решение х системы (1) находится за конечное число арифметических действий. Примером прямого метода является метод Гаусса. Отметим, что вследствие погрешностей округления при решении задач на ЭВМ прямые методы на самом деле не приводят к точному решению системы (1) и называть их точными можно лишь отвлекаясь от погрешностей округления. Сопоставление различных прямых методов проводится обычно по числу арифметических действий (а еще чаще—по асимптотике при больших m числа арифметических действий), необходимых для получения решения. При прочих равных условиях предпочтение отдается методу с меньшим числом действий.

Итерационные методы (их называют также методами последовательных приближений) состоят в том, что решение х системы (1) находится как предел при последовательных приближений, где n — номер итерации. Как правило, за конечное число итераций этот предел не достигается. Обычно задается некоторое малое число (точность) и вычисления проводятся до тех пор, пока не будет выполнена оценка

(2)

Число итераций, которое необходимо провести для получения заданной точности (т. е. для выполнения оценки (2)), для многих методов можно найти из теоретических рассмотрений. Качество различных итерационных процессов можно сравнивать по необходимому числу итераций .

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

Прямые методы не предполагают, что матрица, А имеет какой — либо специальный вид. На практике они применяются для матриц умеренного порядка (порядка ста). Итерационные методы можно применять и для матриц высокого порядка, однако их сходимость не очень быстрая.

1.2 Интерполирование и приближение функции

Основная задача классической теории интерполяции заключается в следующем. Пусть известны значения некоторой функции y = f (x) в точках х₀, х₁, …, х_n требуется заменить f (x) другой функцией F (x), которая бы просто вычислялась и была близка к f (x) в некотором смысле. К такой задаче можно прийти, если:

1) функция f (x) задана таблично;

2) вычисление значений f (x) трудоемко и требуется найти значения f (x) при x=x_k. Чтобы эта задача была корректной, на функцию f (x) необходимо наложить дополнительные условия: например, потребовать непрерывность ее производных.

Способ приближения функции f (x) некоторой функцией F (x), основанный на требовании: F (x_k)=f (x_k) называется интерполированием или интерполяцией.

Чаще всего интерполирующую функцию F (x) находят в виде алгебраического многочлена. Такой способ приближения имеет в своей основе гипотезу, что на небольших отрезках изменения х функция f (x) может быть достаточно хорошо приближена с помощью параболы некоторого порядка, аналитическим выражением которой и будет алгебраический многочлен.

К интерполированию приходится иногда прибегать и в том случае, когда для функции f (x) известно и аналитическое представление, с помощью которого можно вычислять ее значения для любого значения х из отрезка [a, b], в котором она определена, но вычисление каждого значения сопряжено с большим объемом вычислений. Если в процессе решения задачи необходимо находить значения функции f (x) для очень большого количества значений аргумента, то прямой способ потребовал бы громадной вычислительной работы. В этом случае для уменьшения объема вычислений прибегают к интерполированию, т. е. вычисляют несколько значений f (x_i) (i=0, 1,.., n) и по ним строят простую интерполирующую функцию F (x), с помощью которой и вычисляют приближенные значения f (x) в остальных точках.

Интерполяцией функции f (x) называется замена ее функцией F (x) определенного класса, совпадающей с f (x) в точках x_k. При этом точки x_k называются узлами интерполяции.

Если интерполяционная функция F (x) строится на всем рассматриваемом интервале изменения аргумента х, то такая интерполяция называется глобальной (когда F (x) проходит через все узлы). В противном случае интерполяцию называют кусочной или локальной (когда находим F (x) по некоторым узлам).

Погрешностью интерполяции функции f (x) на некотором отрезке называется максимум величины |f (x)-F (x)| на этом отрезке.

Типы интерполяции

1. Полиномиальная;

2. Тригонометрическая;

3. Экспоненциальная.

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

1.3 Интерполяция методом Лагранжа

Один из подходов к задаче интерполяции это метод Лагранжа. Основная идея этого метода состоит в том, чтобы прежде всего найти многочлен, который принимает значение 1 в одной узловой точке и 0 во всех других.

Пусть на отрезке заданы точки, (узлы интерполирования), в которых известны значения функции. Задача интерполирования алгебраическими многочленами состоит в том, чтобы построить многочлен степени n, значения которого в заданных точках, , совпадают со значениями функции в этих точках.

Запишем систему многочленов n-й степени:

Составим линейную комбинацию этих многочленов (их количество равно n + 1) с коэффициентами линейной комбинации, равными значениям сеточной функции, получим многочлен n-й степени:

(3)

Многочлен (3) называют интерполяционным многочленом Лагранжа n-й степени, так как он, во-первых, удовлетворяет условию интерполяции

и, во-вторых, имеет n-ю степень.

Интерполяционный многочлен Лагранжа обладает тем недостатком, что в случае, когда добавляются новые узлы интерполяции, все слагаемые необходимо пересчитывать. Но, с другой стороны, он обладает тем достоинством, что интервалы между узлами могут быть неравномерными:

Если у нас есть свобода выбора точек x_0,., x_n, через которые мы будем проводить полином, то можно повысить точность интерполяции на выбранном нами отрезке [a, b] за счет особого способа выбора точек. Обычно рекомендуется выбирать точки x_i так, что они будут корнями полинома Чебышева n+1-ой степени, определенного на отрезке [a, b]. Это расположение определяется следующими формулами:

2. Анализ требований

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

Входные данные: уравнение функции, строковое представление интервала, переменная x и число точек интерполяции.

Выходные данные: значение интерполирующего полинома.

Основные функции:

1) Основная функция вычисление интерполяционного полинома и перенаправлением входных данных.

Входные данные: строковое представление функций, строковое представление интервала, переменная x и число точек итерации.

Выходные данные: значение полинома.

2) Функция обработки входного интервала представленного в виде строки. Входные данные: строковое представление интервала.

Выходные данные — массив из 2-х элементов содержащий нижнюю и верхнюю границу интервала.

3) Функция вычисления оптимальных значений переменных х₀, х₁, …, х_n.

Входные параметры: верхняя и нижняя граница интервала.

Выходные параметры — массив переменных x_i.

4) Функция выбора коэффициентов, функций и аргументов функций из уравнения представленного в виде строки Входные параметры: строка, представляющая уравнение Выходные параметры: глобальные переменные (static) состояния функции

5) Функция вычисления значений «функций», которую мы ввели, с помощью ранее найденных оптимальных значений переменной x.

Входные данные: массив переменных x_i.

Выходные данные: массив значений функций.

6) Функция вычисления значения интерполирующего полинома.

Входные параметры: массив значений функций, массив переменных x_i,аргумент x.

Выходные параметры: значение интерполирующего полинома.

3. Проектирование

Архитектура: Сервисно-ориентированная архитектура Достоинства: отсутствие конкретной привязанности к какой-либо платформе и относительно лёгкое экспортирование в другие приложение настольные или Web.

Структура данных:

1) Массивы представляющие степени и аргументы функций private static double dStep = 0, dKoef = 0;

1) Массивы представляющие сами функции и их аргументы private static string sFunc = «» ;

Интерфейсы функций:

1) Обработка входного интервала представленного private static double[] GetInterval (string str)

2) Вычисление оптимальных значений переменных х₀, х₁, …, х_n private static double[] GetValuesX (double a, double b, int n)

3) Выбор коэффициентов, функций и аргументов функций из уравнения представленного в виде строки private static void GetParameters (string str)

4) Получение значения определённой функции из массива функций private static double GetValueFunction (double x)

5) Получение всех функций в зависимости от переменной х private static double[] GetAllValuesFuction (double[] x)

6) Вычисление значения интерполирующего полинома private static double GetInterpolation (double[] dX, double[] dF, double x)

4. Руководство программиста

1) Обработка входных параметров(GetParameters)

Метод считывания параметров основан на разборе строки с помощью символов^, *. До символа * располагается область коэффициента, если * нет, то коэффициент равен 1 (сохраняется в массив dKoef). После символа ^ расположена область степени функции, если ^ нет то степень равна 1 (сохраняется в массив dStep). Между * и ^ располагается сама функция. Она состоит из идентификатора функции (exp, x, ctg, tg, sin…, сохраняется в массив sFunc).

Общий вид: 2*х²

2) Обработка оптимальных значений переменных х (GetValuesX)

В этом методе находятся наиболее подходящие значения x_i по формуле Чебышева благодаря чему повышается точность интерполяции.

3) Обработка входного интервала (GetInterval)

Преобразование строкового значения в вещественное число, пригодного для использования. В данном методе происходит разбиение строки на нвчало и конец интервала.

4) Обработка значений интерполирующего полинома (GetInterpolation)

Данный метод основан на интерполяции по формуле Лагранжа. Сначала идет расчет для каждой функции отдельно, а затем их суммирование.

5. Руководство пользователя

· После запуска программы на вашем экране появилось окно, на котором есть область для ввода функции, поля для выбора отрезка [a;b] в переделах которого находятся точки x₀ ,…, x_n, поле для ввода переменной x и поле для ввода числа точек интерполяции.

· Введите функцию, с помощью которой будет вычисляться значение функции для каждой точки x_i. Введите границы отрезка [a;b] в переделах которого находятся точки x₀ ,…, x_n,что позволяет повысить точность итерации. Далее введите значение переменной x и число точек интерполяции.

· Нажмите кнопку «Вычислить интерполяционный полином».

· В области результат появится значение интерполяционного полинома.

· Для выхода из программы нажмите в меню «Файл» затем «выход».

· Для получения справки по использованию программы или сведений о программе зайдите в меню «Помощь».

· Для просмотра основного кода программы зайдите в меню «Текст программы»

6. Тестирование

1. Запускаем программу и заполняем пустые поля.

2. Жмем кнопку «Вычислить интерполяционный полином» и в области «Результат» получаем значение интерполяционного полинома.

(P.S. Более подробная информация по использованию программы находится в программе в разделе «Помощь — справка»)

Математическое решение

1) По методу Чебышева найдем 3 наиболее подходящих значения x_i на интервале [1;2].

Следовательно В данном случае, ,

2) Получим все функции в зависимости от переменной x_i.

,

2) Найдем значение интерполяционного полином Лагранжа.

В ходе решения интерполирующего полинома было получено значение 18, что соответствует результату выполнения программы.

Заключение

математический численный интерполяционный полином программист В курсовой работе я рассмотрел разработку и реализацию численных алгоритмов. Реализовал алгоритм помогающий найти полиномиальную интерполяцию методом Лагранжа. Данный алгоритм написан на языке Microsoft Visual C# 2005 Express Edition. Я использовал язык C# так как он очень удобный в обращение. Он превосходит по некоторым параметрам функциональности другой язык программирования, как Delphi, потому что:

1. есть ряд функций облегчающих работу программиста такие как split и foreach;

2. есть возможность ограничения доступа к полям в структурах, что не мало важно;

3. есть составные операторы такие как +=,-=,*=, /=,++,—.

И, конечно, что не мало важно есть недостатки — в C# существуют некоторые функции, которые записываются в достаточно длинной форме, что имеет существенное значение при написание очень длинных программ.