Численные методы решения типовых математических задач (стр. 4 из 8)
2.5 Схема алгоритма
На рисунке 2.1 представлена схема алгоритма решения задачи №2.
На рисунке 2.2 представлена схема алгоритма ввода исходных данных (подпрограмма-процедура Vvod).
На рисунке 2.3 представлена схема алгоритма интерполяции функции по методу Ньютона с разделенными разностями (newt)
На рисунке 2.4 представлена схема алгоритма записи данных и результата в файл (подпрограмма-процедура zapisb_v_fail).
На рисунке 2.5 представлена схема алгоритма вывода содержимого записанного файла на экран (подпрограмма-процедура outputtoscreen).
2.6 Текст программы
program newton;
uses crt,graph;
const c=10;
type matr=array[0..c,0..c] of real;
mas=array[0..c] of real;
var x,y,koef_polinoma:mas;
a:matr;
b:mas;
d1:real;
n:integer;
fail,fail1,ekran:text;
procedure Vvod(var kolvo:integer; var uzel,fun:mas);
{Процедура осуществляет ввод данных:пользователь вводит с клавиатуры
узлы интерполяции и значения функции в них. Также определяется количество узлов.}
var code,i:integer; s:string;
begin
writeln('введите количество узлов');
readln(kolvo);
kolvo:=kolvo-1;
for i:=0 to kolvo do
begin
repeat
writeln('введите ',i,'-й узел интерполирования');
readln(s);
val(s,uzel[i],code);
until code=0;
repeat
writeln('введите значение функции, соответствующее данному узлу');
readln(s);
val(s,fun[i],code);
until code=0;
end;
end;
procedure newt(var kolvo:integer; D:real; var koef,uzel,fun:mas)
var L,P:real;
begin
L:=fun[0];
P:=1;
for i:=1 to kolvo do
begin
P:=P*(D-uzel[i-1]);
for j:=1 to kolvo-i do
begin
fun[j]:=(fun[j-1]-fun[j])/(uzel[j+i]-uzel[i])
end;
koef[i]:=fun[0];
L:=L+P*fun[0];
end;
end;
procedure newt(var kolvo:integer; D:real; var koef,uzel,fun:mas) {процедура интерполяции функции методом Ньютона}
var L,P:real;
begin
L:=fun[0];
P:=1;
for i:=1 to kolvo do
begin
P:=P*(D-uzel[i-1]);
for j:=1 to kolvo-i do
begin
fun[j]:=(fun[j-1]-fun[j])/(uzel[j+i]-uzel[i])
end;
koef[i]:=fun[0];
L:=L+P*fun[0];
end;
end;
procedure zapisb(koef:mas; uzel,fun:mas; kolvo:integer; var f:text);
{В данной процедуре осуществляется запись в файл данных и результата}
var i:integer;
begin
assign(f,'interpol.txt');
rewrite(f);
for i:=0 to kolvo do writeln(f,'x= ',uzel[i]:8:4,' f(x)=',fun[i]:8:4);
writeln(f,'Интерполяционный полином');
write(f,'p(x)=',koef[0]:8:4);
for i:=1 to kolvo do if i>1 then write (f,'+(',koef[i]:8:4,')*x^',i)
else write (f,'+(',koef[i]:8:4,')*x');
close(f);
end;
procedure vblvod(var f1,f2:text);
{Вывод содержимого записанного файла на экран}
var s1:string;
begin
clrscr;
assign(f1,'interpol.txt');
reset(f1);
assigncrt(f2);
rewrite(f2);
while not eof(f1) do
assigncrt(f2);
rewrite(f2);
while not eof(f1) do
begin
Readln(f1,s1);
writeln(f2,s1);
end;
close(f2);
close(f1);
end;
procedure grafik(kolvo:integer; uzlbl,funktsiya:mas; c:mas);
{Построение графика полученной функции}
var driver,mode,Err,a1,b1,z,i,j:integer; s:string; xt,yt:real;
begin
driver:=detect;
InitGraph(driver,mode,'d:\tp7\bp\bgi');
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');
a1:=0;
b1:=480;
z:=-10;
for i:=0 to 20 do
begin
if z<>0 then
begin
str(z,s);
setcolor(10);
outtextxy(a1,245,s);
outtextxy(325,b1,s);
setcolor(8);
line(0,b1,640,b1);
line(a1,0,a1,480);
end;
outtextxy(325,b1,s);
setcolor(8);
line(0,b1,640,b1);
line(a1,0,a1,480);
end;
a1:=a1+32;
b1:=b1-24;
z:=succ(z);
end;
setcolor(5);
for i:=0 to kolvo do
begin
xt:=uzlbl[i];
yt:=funktsiya[i];
putpixel(round(320+xt*32),round(240-yt*24),5);
end;
moveto(round(320+uzlbl[0]*32),round(240-funktsiya[0]*24));
setcolor(11);
for i:=0 to kolvo do
begin
xt:=uzlbl[i];
yt:=0;
for j:=0 to kolvo do yt:=yt+c[j]*vozvedenie_v_stepenb(uzlbl[i],j);
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('Программа осуществляет интерполирование функции, заданной в узлах');
Vvod(N,X,Y);
writeln(‘введите значение промежуточной точки’);
readln(d1);
2.7 Тестовый пример
writeln('Нажмите Enter');
readln;
newt(N,d1,X,Y,koef_polinoma);
zapisb(koef_polinoma,x,y,n,fail);
vblvod(fail,fail1);
writeln('Нажмите Enter для просмотра графика функции, затем еще раз для выхода из программы');
readln;
grafik(N,X,Y,koef_polinoma);
END.
readln(d1);
writeln('Нажмите Enter');
readln;
newt(N,d1,X,Y,koef_polinoma);
zapisb(koef_polinoma,x,y,n,fail);
vblvod(fail,fail1);
writeln('Нажмите Enter для просмотра графика функции, затем еще раз для выхода из программы');
readln;
grafik(N,X,Y,koef_polinoma);
END.
Дана табличная функция:
Вычислить разделенные разности 1-го, 2-го, 3-го порядков (n=3) и занести их в диагональную таблицу.
Разделенные разности первого порядка:
Разделенные разности второго порядка:
Разделенная разность третьего порядка:
Интерполяционный многочлен Ньютона для заданной табличной функции имеет вид:
График интерполяционного многочлена будет таким:
procedure zapisb(koef:mas; uzel,fun:mas; kolvo:integer; var f:text);
{В данной процедуре осуществляется запись в файл данных и результата}
var i:integer;
begin
assign(f,'interpol.txt');
rewrite(f);
for i:=0 to kolvo do writeln(f,'x= ',uzel[i]:8:4,' f(x)=',fun[i]:8:4);
writeln(f,'Интерполяционный полином');
write(f,'p(x)=',koef[0]:8:4);
for i:=1 to kolvo do if i>1 then write (f,'+(',koef[i]:8:4,')*x^',i)
else write (f,'+(',koef[i]:8:4,')*x');
close(f);
end;
procedure vblvod(var f1,f2:text);
{Вывод содержимого записанного файла на экран}
var s1:string;
begin
clrscr;
assign(f1,'interpol.txt');
reset(f1);
assigncrt(f2);
rewrite(f2);
while not eof(f1) do
begin
Readln(f1,s1);
writeln(f2,s1);
end;
close(f2);
close(f1);
end;
procedure grafik(kolvo:integer; uzlbl,funktsiya:mas; c:mas);
{Построение графика полученной функции}
var driver,mode,Err,a1,b1,z,i,j:integer; s:string; xt,yt:real;
begin
driver:=detect;
InitGraph(driver,mode,'d:\tp7\bp\bgi');
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');
a1:=0;
b1:=480;
z:=-10;
for i:=0 to 20 do
begin
if z<>0 then
3. Среднеквадратическое приближение функции
3.1 Постановка задачи
Разработать схему алгоритма и написать программу на языке Turbo Pascal 7.0 для выполнения среднеквадратического приближения функции, заданной в узлах.
3.2 Математическая формулировка задачи
Пусть имеется множество функций
, принадлежащих линейному пространству функций. Под близостью в среднем интерполируемой и интерполирующей функций будем понимать результат оценки интеграла 
, (3.1)где
- весовая функция.Такое приближение называют среднеквадратичным.
3.3 Обзор существующих численных методов решения задачи
Задача среднеквадратичного приближения возникает во многих областях прикладных исследований, например, при статистической обработке данных эксперимента с использованием регрессивного анализа, при оценивании параметров моделей, в задачах фильтрации и т.п.
Когда уровень неопределенности в задании приближаемой функции f(xi), i=1..m, достаточно велик, что характерно для обработки экспериментальных данных, бессмысленно требовать выполнения условий интерполирования; кроме того, число точек задания функции f(xi) часто весьма велико. Все это делает применение интерполирования мало перспективным по причинам плохой обусловленности задачи высокой размерности и проблем сходимости процесса интерполяции
Одной из наиболее простых и, поэтому, широко используемых приближающих функций является алгебраический полином
Метод среднеквадратичного приближения обеспечивает построение полинома Pn(x), исходя из минимизации величины
Рассмотренный метод приближения минимизирует среднеквадратичное уклонение аппроксимирующего полинома от аппроксимируемой функции, но не гарантирует от значительных локальных ошибок. Для предотвращения подобной возможности используют полиномы наилучшего равномерного приближения.
в пространстве параметров a0 , a1 ,...,an. Существуют различные подходы к решению задачи минимизации функции D(a). Простейший из них приводит к необходимости решения нормальной системы линейных алгебраических уравнений
Однако, уже при n > 5 матрица такой системы оказывается настолько плохо обусловленной, что полученные из (3.4) значения aj оказываются мало пригодными для вычисления Pn(x). Поэтому, при необходимости построения полиномов наилучшего среднеквадратичного приближения более высоких степеней применяют другие алгоритмы, например, метод сингулярного разложения.
3.4 Численный метод решения задачи
Можно рассмотреть две задачи:
1 - подобрать функцию
так, чтобы выполнялось неравенство 
; (3.5)2 - найти наилучшее приближение, т.е. такую функцию
, чтобы было справедливым соотношение