Алгоритмирование вычислительных процессов

МИНИСТЕРСТВО ТРАНСПОРТА И СВЯЗИ УКРАИНЫ Днепропетровский Национальный Университет железнодорожного транспорта имени академика В. Лазаряна Кафедра: «КИТ»

Лабораторная работа № 1

по дисциплине: «Алгоритмирование вычислительных процессов»

по теме:

«Интерполирование функций»

Выполнил: студент 935 группы Рябека А. А.

Проверила:

Шаповал И. В.

Днепропетровск

Лабораторная работа № 1.

Тема:

«Интерполирование функций»

Цель:

Научиться интерполировать функции методом Ла-Гранжа. Написать программу, которая будет интерполировать заданную функцию этим методом.

План

1. Теория

2. Постановка задачи.

3. Алгоритм задачи (схема Насси-Шнайдермана).

4. Текст программы.

5. Визуальная оболочка.

6. Пример работы.

7. Вывод.

1. Теория Интерполирование В расчетах часто требуется установить функцию f (x) для всех значений х отрезка [a, b], если известны ее значения в некотором конечном числе точек этого отрезка. Одним из способов приближения функции является интерполяция .

Задача интерполяции может возникнуть в практике при:

интерполировании табличных данных;

получении функциональной зависимости по экспериментальным данным, представленным в табличной форме;

замене сложной с вычислительной точки зрения функции, более простой зависимостью;

при дифференцировании и интегрировании.

Постановка задачи Пусть на отрезке [x0,xn] заданы n+1 точки x0, x1, x2,…, xn, называемые узлами интерполяции, и значения некоторой интерполируемой функции y=f (x) в этих точках, т. е. имеется таблица экспериментальных значений функции y=f (x): y0, y1, y2… yn.

y0= f (x0); y1=f (x1);.. .; yn=f (xn). (1.1)

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

Pm (x0)=f (x0)=y0,

… (1.2)

…

Pm (xi)=f (xi)=yi, где i = 0,1,2, …, n.

Такую задачу называют задачей интерполирования. Точки xi называются узлами интерполяции, функция f (x) — интерполируемой функцией, многочлен Pm (x) — интерполяционным многочленом. Задачей интерполяции, в узком смысле слова, считают нахождение приближенных значений табличной функции при аргументах x, не совпадающих с узловыми. Если значение аргумента x расположено между узлами x0<=x<=xn, то нахождение приближенного значения функции f (x) называется интерполяцией, если аппроксимирующую функцию вычисляют вне интервала [x0,xn], то процесс называют экстраполяцией. Происхождение этих терминов связано с латинскими словами inter — между, внутри, pole — узел, extra — вне.

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

Близость интерполяционного многочлена к заданной функции состоит в том, что их значения совпадают на заданной системе точек.

При решении задачи интерполирования обычно принимается, что:

интерполируемая функция непрерывна на отрезке [a, b] и в каждой точке имеет конечные производные любого порядка;

узлы интерполирования отличны друг от друга.

Интерполяционный полином в форме Лагранжа Вывод формулы Итак, мы ищем полином Ln (x) степени не выше n, значения которого совпадают со значениями yk заданной функции ѓ(x) в узлах xk, где k=1,2,…, n+1 и все узлы различны.

Одним из способов записи интерполяционного полинома является форма Лагранжа. Предположим, что для k=1,2,…, n+1 функции Фn (x) являются полиномами степени n, которые обладают следующим свойством Тогда полином будет как раз тем, который нам и нужен, поскольку это полином степени не выше n и Ln (xk) = yk для всех k=1,2,…, n+1.

Функции Фn (x) строятся легко. Действительно, функция является полиномом степени n, который обращается в ноль для всех xj не равных xk. В точке xk она принимает значение Тогда или, что-то же самое:

2. Постановка задачи Исходные данные:

— таблица значений произвольных функций.

Необходимо построить аналитическое выражение, которое сопоставит значения с табличнозаданными в некотором конечном количестве точек.

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

1) Параболическое интерполирование.

2) Интерполирование на основе специально оговоренных полином.

При интерполяции методом Ла-Гранжа функция строится на основе базиса xn, где n = 0, 1, 2,… .

где Фk (x) — базисная функция.

3. Алгоритм задачи (схема Насси-Шнайдермана)

4. Текст программы

Unit1.h

//—————————————————————————————————————;

#ifndef Unit1H

#define Unit1H

//—————————————————————————————————————;

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

//—————————————————————————————————————;

class TForm1: public TForm

{

__published: // IDE-managed Components

TStringGrid *StringGrid1;

TChart *Chart1;

TEdit *Edit1;

TLabel *Label1;

TLineSeries *Series1;

TLineSeries *Series2;

TButton *Button1;

TButton *Button2;

TButton *Button3;

void __fastcall Button3Click (TObject *Sender);

void __fastcall Button1Click (TObject *Sender);

void __fastcall Button2Click (TObject *Sender);

private: // User declarations

public: // User declarations

__fastcall TForm1 (TComponent* Owner);

double Langrang (double*x, double*y, double xt, int N)

{

double L, Lg;

int i, j;

L = 0;

for (i = 0; i < N; i++)

{

Lg = 1;

for (j = 0; j < N; j++)

{

if (i ≠ j)

Lg*= (xt-x[j])/(x[i]-x[j]);

}

L = L + y[i]*Lg;

}

return L;

}

};

//—————————————————————————————————————;

extern PACKAGE TForm1 *Form1;

//—————————————————————————————————————;

#endif

Unit1.cpp

//—————————————————————————————————————;

#include

#pragma hdrstop

#include «Unit1.h»

//—————————————————————————————————————;

#pragma package (smart_init)

#pragma resource «*.dfm»

TForm1 *Form1;

//—————————————————————————————————————;

__fastcall TForm1: TForm1 (TComponent* Owner)

: TForm (Owner)

{

}

//—————————————————————————————————————;

void __fastcall TForm1: Button3Click (TObject *Sender)

{

StringGrid1 -> Cells[0][0] = «x» ;

StringGrid1 -> Cells[1][0] = «y» ;

StringGrid1 -> RowCount = StrToInt (Edit1 -> Text) + 1;

StringGrid1 -> Visible = true;

}

//—————————————————————————————————————;

void __fastcall TForm1: Button1Click (TObject *Sender)

{

int i;

for (i = 1; i <= StrToInt (Edit1 -> Text); i++)

{

float x = StrToFloat (StringGrid1 -> Cells[0][i]);

float y = StrToFloat (StringGrid1 -> Cells[1][i]);

Series1 -> AddXY (x, y, ' ', clRed);

}

}

//—————————————————————————————————————;

void __fastcall TForm1: Button2Click (TObject *Sender)

{

int N = StrToInt (Edit1 -> Text);

double*ax;

ax = new double [N];

double*ay;

ay = new double [N];

for (int i = 0; i < N; i++)

{

ax[i] = StrToFloat (StringGrid1 -> Cells[0][i+1]);

ay[i] = StrToFloat (StringGrid1 -> Cells[1][i+1]);

}

double h = (ax[N-1]-ax[0])/(2*N);

for (double x = ax[0]; x <= ax[N-1]; x = x + h)

{

float y = Langrang (ax, ay, x, N);

Series1 -> AddXY (x, y, ' ', clGreen);

}

}

//—————————————————————————————————————;

5. Визуальная оболочка

6. Пример работы Начальный вид при запуске:

Вводим изначальное количество точек:

Вводим 5.

Нажимаем кнопку создать таблицу и вводим в нее произвольные данные:

X Y

1 3

2 5

3 7

4 6

5 5

Нажимаем кнопку построить график, в результате чего получаем:

Нажимаем кнопку интерполяция и в результате получаем:

Полученный график является верным.

7. Вывод интерполирование функция полином лагранж При выполнении работы я изучил основы интерполирования функций, научился использовать метод Ла-Гранжа для интерполирования функций, освоил построение интерполяционных графиков, а также узнал о значительном недостатке данного метода — значения крайних точек графика чаще всего очень разные с реальными значениями.