Численные методы решения типовых математических задач
2.9 Инструкция программисту
Данная программа осуществляет интерполирование функции, заданной в узлах, методом Вандермонда.
Константы:
С - константа целого типа, обозначает верхнюю границу матрицы системы и свободных членов.
Типы:
matr=array[0..c,0..c] of real - двумерный массив с равным количеством строк и столбцов.
mas=array[0..c] of real - одномерный массив.
Переменные:
x,y:mas - узлы интерполяции и значения функции в них.
a:matr - матрица СЛАУ для нахождения коэффициентов полинома.
b:mas - вектор свободных членов СЛАУ.
vand:real - определитель Вандермонда.
n:integer - номер последнего узла (нумерация с нуля).
Fail:text-файловая переменная, соответствующая записываемому файлу;
Ekran:text-файл, в который копируется данный файл для вывода на экран.
Подпрограммы
1) procedure Vvod(var kolvo:integer; var uzel,fun:mas) - ввод исходных данных.
Формальные параметры:
-возвращаемые значения:
uzel,fun:mas-массивы узлов интерполяции и значений функции в них
kolvo:Integer-номер последнего узла(нумерация с нуля);
Локальные переменные:
code:integer - индикатор ошибки ввода данных(параметр процедуры перевода строковой переменной в число Val)
i:Integer-счетчик цикла;
s:string-переменная для контроля ввода данных .
2) Function Determinante(Mas:Matr; kolvo:Integer):Real - вычисление определителя квадратной матрицы.
Формальные параметры:
-передаваемые значения:
Mas:Matr-матрица, определитель которой надо вычислить;
kolvo:Integer-размерность матрицы;
Локальные переменные:
Arr:Matr-матрица, в которую копируются элементы данной (вспомогательная для вычисления определителя);
i,j,k:Integer-счетчики циклов;
sum:Real-результат(значение, возвращаемое функцией);
3) function vozvedenie_v_stepenb(osnovanie:real;pokazatelb:integer):real - возведение действительного числа в степень.
Формальные параметры:
-передаваемые значения:
Osnovanie - переменная типа Real, возвращающая значение основания степени.
Pokazatelb - переменная типа Integer, возвращающая значение показателя степени.
4) procedure sistema(uzel,fun:mas; kolvo:integer; var a1:matr; var b1:mas; var opr:real) - построение СЛАУ с неизвестными - коэффициентами интерполяционного полинома.
Формальные параметры:
-передаваемые значения:
uzel,fun:mas-массивы узлов интерполяции и значений функции в них
kolvo:Integer-номер последнего узла(нумерация с нуля);
-возвращаемые значения
a1:matr; b1:mas-матрица системы и вектор свободных членов;
opr:real-определитель Вандермонда.
Локальные переменные:
I,j:Integer-счетчики цикла;
5) procedure reshenie(a1:matr; b1:mas; opr:real; kolvo:integer; var koef:mas) - решение полученной СЛАУ.
Формальные параметры:
-передаваемые значения:
a1:matr; b1:mas-матрица системы и вектор свободных членов;
opr:real-определитель Вандермонда.
kolvo:Integer-номер последнего узла(нумерация с нуля);
-возвращаемые значения
koef:mas-искомые коэффициенты интерполяционного полинома
Локальные переменные:
c1:matr-матрица системы, в которой один из столбцов заменен на вектор свободных членов
I,j,k:Integer-счетчики цикла.
6) procedure zapisb(koef:mas; uzel,fun:mas; kolvo:integer; var f:text) - запись в файл данных и результата.
Формальные параметры:
-передаваемые значения:
uzel,fun:mas-массивы узлов интерполяции и значений функции в них
kolvo:Integer-номер последнего узла(нумерация с нуля);
koef:mas-коэффициенты интерполяционного полинома
-возвращаемые значения:
f:text-файловая переменная, соответствующая записываемому файлу
Локальные переменные:
i-счетчик в циклах.
7) procedure outputtoscreen(var imyafaila:string; var f1,f2:text) - вывод содержимого записанного файла на экран.
Формальные параметры:
-передаваемые значения:
imyafaila:string-имя файла, который выводится на экран;
-возвращаемые значения:
f1,f2:text - файловые переменные, соответствующие копируемому файлу и файлу, в который осуществляется копирование;
Локальные переменные:
s1:string-копируемая строка.
3 Задача №3: среднеквадратичное приближение функции
3.1 Постановка задачи
Разработать схему алгоритма и написать программу на языке Turbo Pascal 7.0. для выполнения среднеквадратичного приближение функции, заданной в узлах.
3.2 Математическая формулировка задачи
При интерполировании используется условие равенства значений интерполяционного многочлена и аппроксимируемой функции в узлах интерполяции. Для инженерной практики типична задача приближения функции с помощью многочлена по некоторому заданному базису {f k(x), k=0,1,...,n}, когда значение приближаемой функции заданы в числе узлов, превышающих число базисных функций.
Будем нумеровать узлы от аргумента индексами х0,...,хN. При N>n практически всегда не найдется многочлена, значения которого совпадали бы со значениями аппроксимируемой функции во всех узлах. В этом случае задача аппроксимации функции полиномом ставится как задача поиска такого вектора коэффициентов многочлена
,
при котором значения многочлена как можно меньше отклонялись от значений аппроксимируемой функции в совокупности всех узлов. Эту задачу можно решить с помощью среднеквадратичного приближения функции по степенному базису.
3.3 Обзор существующих методов решения
Среднеквадратичное приближение по тригонометрическому базису
Тригонометрическим многочленом порядка m называется функция
(t)= (1)
где бр, вр - произвольные числовые коэффициенты. Тригонометрическими многочленами естественно приближать периодические функции с периодом 2? . В теории рядов Фурье устанавливается, что коэффициенты тригонометрического многочлена наилучшего среднеквадратичного приближения непрерывной 2? -периодичной функции f(t), для которого величина
принимает минимальное значение, задаются формулами
, , .
Рассмотрим задачу нахождения тригонометрического многочлена наилучшего среднеквадратичного приближения на дискретном множестве точек. Пусть N,m - натуральные числа, m? N/2. Даны точки
i=0,1,...,N.
и значения функции в этих точках f(t). Требуется аппроксимировать функцию f(t) на интервале тригонометрическим полиномом (1).
Коэффициенты тригонометрического многочлена наилучшего среднеквадратичного приближения функции f(t) на дискретном множестве точек хi, i=0,1,...,N, в данном случае находятся по формулам
.
Для приближения функции на произвольном отрезке необходимо произвести замену переменных.
Мы будем решать поставленную задачу среднеквадратичного приближения функции по степенному базису.
3.4 Численный метод решения
Критерий среднеквадратического приближения (метод наименьших квадратов):
Коэффициенты многочлена выбирают исходя из условия
Подкоренное выражение представляет собой квадратичную функцию относительно коэффициентов аппроксимирующего многочлена. Она непрерывна и дифференцируема по . Очевидно, что ее минимум находится в точке, где все частные производные равны нулю .
Приравнивая к нулю частные производные, получим систему линейных алгебраических уравнений относительно неизвестных (искомых) коэффициентов многочлена наилучшего приближения.
,
,
Чтобы эта система имела единственное решение необходимо и достаточно, чтобы определитель матрицы А (определитель Грамма) был отличен от нуля.
Таким образом, необходимо и достаточно чтобы система базисных функций была линейно независимой на множестве узлов аппроксимации, что выполняется для системы степенных функций.
3.5 Схема алгоритма
На рисунке 3.1 представлена схема алгоритма решения задачи №3.
На рисунке 3.2 представлена схема алгоритма чтения из файла исходных данных (подпрограмма-процедура chtenie_dannblh).
На рисунке 3.3 представлено продолжение схемы алгоритма чтения из файла исходных данных (подпрограмма-процедура chtenie_dannblh).
На рисунке 3.4 представлена схема алгоритма построения базиса степенных функций (подпрограмма-процедура bazis).
На рисунке 3.5 представлена схема алгоритма построения СЛАУ с неизвестными - коэффициентами искомого полинома (подпрограмма-процедура sistema).
На рисунке 3.6 представлена схема алгоритма решения полученной CЛАУ (подпрограмма-процедура reshenie_systembl).
Рисунок 3.1 - Блок-схема алгоритма решения задачи №3
Рисунок 3.2 - Блок-схема алгоритма чтения из файла исходных данных
Рисунок 3.3 - Блок-схема алгоритма чтения из файла исходных данных (продолжение)
Рисунок 3.4 - Блок-схема алгоритма построения базиса степенных функций
Рисунок 3.5 - Блок-схема алгоритма получения СЛАУ, вектор неизвестных которой - искомые коэффициенты полинома
Рисунок 3.6 - Блок-схема алгоритма решения полученной СЛАУ
3.6 Текст программы
program priblizhenie;
uses crt,graph;
type mas1=array [0..20] of real;
mas2=array [0..2] of real;
mas3=array [0..2,0..2] of real;
mas4=array [0..2,0..20] of real;
var fail:text;
x,y:mas1;
koef_polinoma,b:mas2;
n:integer; psi:mas4;
a:mas3;
procedure chtenie_dannblh(var f:text; var uzlbl,funktsiya:mas1; var kolvo:integer);
{Процедура осуществляет чтение данных из файла, получаем узлы и значения функции в них}
var code,j,tab,i,dlina_stroki:integer;
x_s,y_s,s:string;
begin
kolvo:=-1;
assign(f,e:202020.txt);
reset(f);
while not eof(f) do
begin
readln(f,s);
dlina_stroki:=length(s);
kolvo:=kolvo+1;
x_s:= ;
y_s:= ;
for i:=1 to dlina_stroki do if s[i]=chr(9) then
tab:=i;
i:=1;
while i<tab do
begin
x_s:=x_s+s[i];
i:=i+1;
end;
for i:=tab+1 to dlina_stroki do y_s:=y_s+s[i];
delete(x_s,1,1);
delete(y_s,1,1);
val(x_s,uzlbl[kolvo],code);
val(y_s,funktsiya[kolvo],code);
end;
close(f);
for j:=0 to kolvo do writeln(uzel=,uzlbl[j]:4:2, function=,funktsiya[j]:16:15);
end;
procedure bazis(uzlbl:mas1; kolvo:integer; var f:mas4){Построение базиса степенных функций};
var i,j:integer;
begin
for i:=0 to 2 do
for j:=0 to kolvo do
if i=0 then f[i,j]:=1
else if i=1 then f[i,j]:=uzlbl[j]
else f[i,j]:=sqr(uzlbl[j]);
end;
procedure sistema(f:mas4;funktsiya:mas1; kolvo:integer; var a1:mas3; var b1:mas2){Получение СЛАУ, вектор неизвестных которой - искомые коэффициенты полинома};
var i,j,k:integer;
begin
for k:=0 to 2 do
for j:=0 to 2 do
for i:=0 to kolvo do
a1[k,j]:=a1[k,j]+f[k,i]*f[j,i];
for j:=0 to 2 do
for i:=0 to kolvo do
b1[j]:=b1[j]+funktsiya[i]*f[j,i];
end;
procedure rewenie_systembl(a1:mas3; b1:mas2; var c:mas2){Решение полученной СЛАУ};
var i,j,k:integer; l:mas3; y:mas2; sum:real;
begin
l[0,0]:=sqrt(a1[0,0]);
for i:=1 to 2 do l[i,0]:=a1[i,0]/l[0,0];
l[1,1]:=sqrt(a1[1,1]-sqr(l[1,0]));
l[2,1]:=(a1[2,1]-l[2,0]*l[1,0])/l[1,1];
l[2,2]:=sqrt(a1[2,2]-sqr(l[2,0])-sqr(l[2,1]));
for i:=0 to 2 do
begin
sum:=0;
for k:=0 to i-1 do sum:=sum+l[i,k]*y[k];
y[i]:=(b1[i]-sum)/l[i,i];
end;
c[2]:=y[2]/l[2,2];
c[1]:=(y[1]-l[2,1]*c[2])/l[1,1];
c[0]:=(y[0]-l[2,0]*c[2]-l[1,0]*c[1])/l[0,0];
end;
procedure grafik_priblizhenie(kolvo:integer; uzlbl,funktsiya:mas1; c:mas2);
var driver,mode,Err,a,b,z,i,j:integer; s:string;xt,yt:real;
begin
driver:=detect;
InitGraph(driver,mode,d: p7pgi);
err:=graphresult;
if err<>grok then writeln(Ошибка при инициализации графического режима)
else
begin
Setcolor(9);
line(320,0,320,480);
line(0,240,640,240);
settextstyle(smallfont,horizdir,3);
setcolor(10);
outtextxy(320,245,0);
a:=0;
b:=480;
z:=-10;
for i:=0 to 20 do
begin
if z<>0 then
begin
str(z,s);
setcolor(10);
outtextxy(a,245,s);
outtextxy(325,b,s);
setcolor(8);
line(0,b,640,b);
line(a,0,a,480);
end;
a:=a+32;
b:=b-24;
z:=succ(z);
end;
setcolor(5);
for i:=0 to kolvo do
begin
xt:=uzlbl[i];
yt:=funktsiya[i];
if xt<>0 then line(round(320+xt*32),240,round(320+xt*32),round(240-yt*24));
if yt<>0 then line(320,round(240-yt*24),round(320+xt*32),round(240-yt*24));
end;
setcolor(11);
xt:=uzlbl[0];
yt:=c[0]+c[1]*uzlbl[0]+c[2]*uzlbl[0];
moveto(round(320+xt*32),round(240-yt*24));
for i:=1 to kolvo do
begin
xt:=uzlbl[i];
yt:=c[0]+c[1]*uzlbl[i]+c[2]*sqr(uzlbl[i]);
lineto(round(320+xt*32),round(240-yt*24));
moveto(round(320+xt*32),round(240-yt*24));
end;
readln;
closegraph;
end;end;
BEGIN
CLRSCR;
WRITELN(ПРОГРАММА ВЫПОЛНЯЕТ СРЕДНЕКВАДРАТИЧНОЕ ПРИБЛИЖЕНИЕ ФУНКЦИИ,ЗАДАННОЙ В УЗЛАХ:);
chtenie_dannblh(fail,x,y,n);
bazis(x,n,psi);
sistema(psi,y,n,a,b);
rewenie_systembl(a,b,koef_polinoma);
writeln(Полученный полином);
write(P(X)=,koef_polinoma[0]:8:4,+(,koef_polinoma[1]:8:4
for i:=0 to 2 do
readln;
grafik_priblizhenie(n,x,y,koef_polinoma);
end.
,)*x^2);
writeln;
writeln(Нажмите Enter для построения графика и затем еще раз для выхода из программы);
readln;
grafik_priblizhenie(n,x,y,koef_polinoma);
end.