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

Размещено на http://www.allbest.ru/

МИНИСТЕРСТВО ТРАНСПОРТА И СВЯЗИ УКРАИНЫ

Днепропетровский Национальный Университет железнодорожного транспорта имени академика В. Лазаряна

Кафедра: «КИТ»

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

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

по теме:

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

Выполнил: студент 935 группы

Рябека А. А.

Проверила:

Шаповал И. В.

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

2010

Лабораторная работа №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. Алгоритм задачи (схема Насси-Шнайдермана)

Ввод значений функций x, y
L = 0
i є [1, N]
	Lg = 1
	j є [1, N]
		i != j
		Lg = (Lg*(x - x[j]))/(x[i] - x[j])
	j = j +1
	L = L + y[i]*Lg
	i = i + 1

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

Unit1.h

//---------------------------------------------------------------------------

#ifndef Unit1H

#define Unit1H

//---------------------------------------------------------------------------

#include <Classes.hpp>

#include <Controls.hpp>

#include <StdCtrls.hpp>

#include <Forms.hpp>

#include <Chart.hpp>

#include <ExtCtrls.hpp>

#include <Grids.hpp>

#include <Series.hpp>

#include <TeEngine.hpp>

#include <TeeProcs.hpp>

//---------------------------------------------------------------------------

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 <vcl.h>

#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. Вывод

интерполирование функция полином лагранж

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

Размещено на Allbest.ru