Численные методы решения типовых математических задач
1.8 Инструкция пользователю
Данная программа осуществляет решение СЛАУ методом Гаусса-Зейделя. Вам будет предложено ввести количество уравнений, погрешность вычисления, построчно матрицу системы (коэффициенты перед неизвестными) и вектор свободных членов. Если система не имеет решений, выводится следующее сообщение: «Процесс итерации расходится, найти решение невозможно. Нажмите Enter для выхода». В случае, если метод сходится, то данные и результат записываются в файл, имя которого вам предложено будет ввести, и его содержимое выводится на экран. После этого для выхода из программы нажмите enter.
1.9 Инструкция программисту
Данная программа осуществляет решение СЛАУ методом Гаусса-Зейделя.
Константы:
С - константа целого типа, обозначает верхнюю границу матрицы системы и свободных членов.
Типы:
mas1=array [1..c,1..c] of real - двумерный массив c одинаковым количеством строк и столбцов;
mas2=array [1..c] of real - одномерный массив (вектор-столбец);
mas3=array [1..c,0..20] of real - двумерный массив.
Переменные:
N:integer-количество уравнений(размерность матрицы системы);
E :real- погрешность вычисления;
A:mas1-матрица коэффициентов перед неизвестными;
B:mas2 - вектор свободных членов;
Alpha:mas1,beta:mas2- матрицы, полученные при выражении неизвестных;
Shodimostb:boolean -логическая переменная, определяющая сходимость метода;
X:mas2- матрица-вектор решения системы;
Prib:integer- номер последнего приближения (вычисленного с заданной погрешностью);
Imya:string- имя файла, в который производится запись данных и результата;
Dannble_i_rezultat:text-файловая переменная, соответствующая записываемому файлу;
Ekran:text-файл, в который копируется данный файл для вывода на экран.
Подпрограммы
1)procedure input(var kolvo:integer; var pogreshnostb:real; var matr1:mas1; var matr2:mas2) - ввод исходных данных.
Формальные параметры:
Kolvo:integer - количество уравнений в системе
(размерность матрицы системы);
pogreshnostb:real-погрешность вычисления;
matr1:mas1-матрица системы(коэффициенты перед неизвестными);
matr2:mas2-вектор свободных членов;
Локальные переменные:
i,j-счетчики в циклах;
summa1,summa2:array [1..c] of real,summa3:real-переменные, необходимые для вычисления норм матрицы коэффициентов перед неизвестными matr3;
norma1,norma2,norma3:real-нормы матрицы коэффициентов
a_s:string, b_s: string - строковые переменные, используемые для контроля ввода элементов матрицы системы и вектора свободных членов;
code:integer - индикатор ошибки ввода данных(параметр процедуры перевода строковой переменной в число Val).
2)procedure proverka_shodimosti(matr1:mas1;matr2:mas2; kolvo:integer; var matr3:mas1; var matr4:mas2; var bool:boolean) - проверка сходимости метода;
Формальные параметры:
-передаваемые значения:
Kolvo:integer -количество уравнений в системе (размерность матрицы системы);
matr1:mas1-матрица системы(коэффициенты перед неизвестными);
matr2:mas2-вектор свободных членов;
-возвращаемые значения:
matr3:mas1, matr4:mas2 -матрицы, полученные при выражении неизвестных;
bool:boolean-логическая переменная, определяющая сходимость метода
Локальные переменные:
i,j-счетчики в циклах;
перед неизвестными matr3;
3) procedure reshenie_sistembl (matr3:mas1;matr4:mas2;
kolvo:integer;pogreshnostb:real; var matr5:mas3; var k:integer) - решение СЛАУ.
Формальные параметры:
-передаваемые значения:
matr3:mas1, matr4:mas2 -матрицы, полученные при выражении неизвестных;
kolvo:integer -количество уравнений в системе;
pogreshnostb:real-погрешность вычисления;
-возвращаемые значения:
matr5:mas3-вектор неизвестных(приближение);
k:integer -номер приближения, вычисленного с заданной погрешностью;
Локальные переменные:
i,j:integer-счетчики в циклах;
p:integer-количество элементов приближения, вычисленных с заданной погрешностью;
s1,s2:real-переменные,необходимые для вычисления элемента приближения;
4) procedure zapisb_v_fail(kolvo:integer; matr1:mas1; matr2:mas2; matr5:mas3; k:integer; var imyafaila:string; var f:text) - запись в файла данных и ответа.
Формальные параметры:
-передаваемые значения:
Kolvo:integer -количество уравнений в системе (размерность матрицы системы);matr1:mas1-матрица системы(коэффициенты перед неизвестными);matr2:mas2-вектор свободных членов;
matr5:mas3-вектор неизвестных(приближение); k:integer -номер приближения, вычисленного с заданной погрешностью;
-возвращаемые значения:
imyafaila:string-имя записываемого файла; f:text-файловая переменная, соответствующая записываемому файлу
Локальные переменные:
i,j-счетчики в циклах;
5) procedure outputtoscreen(var imyafaila:string; var f1,f2:text) - вывод содержимого записанного файла на экран.
Формальные параметры:
-передаваемые значения:
imyafaila:string-имя файла, который выводится на экран;
-возвращаемые значения:
f1,f2:text - файловые переменные, соответствующие копируемому файлу и файлу, в который осущ2 Задача №2: интерполирование функции, заданной в узлах, методом Вандермонда
2.1 Постановка задачи
Разработать схему алгоритма и написать программу на языке Turbo Pascal 7.0 для интерполирования функции, заданной в узлах, методом Вандермонда (решение системы уравнений, составленных по условиям интерполяции).
2.2 Математическая формулировка задачи
В узком значении под интерполяцией понимают отыскание ве-личин таблично заданной функции, соответствующих промежу-точным (межузловым) значениям аргумента, отсутствующим в таблице.
Под интерполяцией в широком смысле понимают отыскание аналитического вида функции y = F(x), выбранной из определённого класса функций и точно проходящую через узлы интерполяции . При этом задача формулируется таким образом : на отрезке [a ,b] заданы (n+1) точки x0 , x1 , x2 ,…, xn и значения некоторой функции f(x) в этих точках :
f(x0)= y0 , f(x1)= y1 , … , f(xn)= yn .
Вид функции либо неизвестен вовсе, либо он неудобен для расчётов (сложная функция, которую необходимо при расчётах интегрировать, дифференцировать и т. п.). Требуется построить функцию F(x) (интерполирующую функцию), принимающую в узлах интерполяции те же значения, что и исходная функция
f(x), т. е. F(x0)= y0 , F(x1)= y1 , … , F(xn)= yn . (1)
В такой постановке задача имеет бесконечное множество решений, или совсем не имеет. Однако эта задача становится однозначной,
В такой постановке задача имеет бесконечное множество решений, или совсем не имеет. Однако эта задача становится однозначной,
если вместо произвольной функции искать полином степени не выше n, удовлетворяющий условиям (1):
F(x) = a0 + a1x + a2x2 +…+ anxn
Для построения интерполирующего многочлена применяются многочисленные способы. Один из них - метод Вандермонда (решение СЛАУ, составленной по условиям интерполяции).
2.3 Обзор существующих численных методов
На практике для построения интерполирующего многочлена могут использоваться следующие методы: решение СЛАУ, составленной по условиям интерполяции (метод Вандермонда), метод Лагранжа, метод Ньютона, построение сплайна.
Интерполяционная формула Лагранжа:
Эта формула легко программируется. Число арифметических операций при вычислении растет не быстрее n2. Интерполяционной формулой Лагранжа невозможно пользоваться при большом числе узлов интерполяции ().
Интерполирование по Ньютону:
Pn(x)=f(x0)+(x-x0)f(x0,x1)+ (x-x0)(x-x1)f(x0,x1,x2)+...+
+(x-x0)(x-x1)...(x-xn-1)f(x0,x1,...,xn);
Полиномы Лагранжа и Ньютона представляют собой различную запись одного и того же многочлена .
Интерполяционную формулу Ньютона удобнее применять в том случае, когда интерполируется одна и та же функция f(x), но число узлов интерполяции постепенно увеличивается. Если узлы интерполяции фиксированы и интерполируется не одна, а несколько функций, то удобнее пользоваться формулой Лагранжа.
Интерполирование многочленами Лагранжа на всем отрезке [а,b] с использованием большого числа узлов интерполяции часто приводит к плохому приближению из-за накопления погрешности в процессе вычислений. Кроме того, из-за расходимости процесса интерполяции увеличение числа узлов необязательно приводит к повышению точности. Для того, чтобы избежать больших погрешностей, весь отрезок [а,b] разбивают на частичные отрезки и на каждом из них проводят интерполяцию полиномом невысокой степени. Это так называемая кусочно-полиномиальная интерполяция.
Для интерполирования на всем отрезке часто используют интерполирование с помощью сплайн-функций. Слово “сплайн” (spline) означает гибкую линейку, используемую для проведения гладких кривых через заданные точки. Сплайн-функцией или просто сплайном называют кусочно-полиномиальную функцию, определенную на отрезке [a,b] и имеющую на этом отрезке некоторое число непрерывных производных. Преимуществом сплайнов перед обычной интерполяцией является их сходимость и устойчивость процесса вычислений.
2.4 Численный метод решения
Пусть задана табличная функция своими (n+1) узловыми значениями (x0,y0 ) ; (x1,y1 ) ; (x1,y1 ) ; …, (xn,yn ) . Необходимо вычислить коэффициенты ai , i=(0,1,2,…n) интерполирующего многочлена (1).
Так как по определению интерполирующий многочлен проходит через узлы интерполяции без погрешности, то значения каждого из них обращает в тождество уравнение (1), то есть
a0 + a1x0 + a2x02 +…+ anx0n = y0,
a0 + a1x1 + a2x12 +…+ anx1n = y1,
a0 + a1x2 + a2x22 +…+ anx2n = y2,
a0 + a1xn + a2xn2 +…+ anxnn = yn .
Если функция однозначна и xi различны, то в результате подстановки значений узловых точек интерполяции в уравнения (1) получаем систему (2) (n+1) уравнений с (n+1) неизвестным. Определитель этой системы называют определителем Вандермонда:
1 x0 x02 … x0n
1 x1 x12 … x1n
= 1 x2 x22 … x2n
… … … …
1 xn xn2 … xnn
Определитель Вандермонда отличен от нуля, если xj все различные. Следовательно, данная система всегда имеет решение, и притом единственное. Таким образом, доказано существование и единственность интерполяционного многочлена. Значения коэффициентов интерполирующего многочлена получают, решив систему (2).
2.5 Схема алгоритма
На рисунке 2.1 представлена схема алгоритма решения задачи №2.
На рисунке 2.2 представлена схема алгоритма ввода исходных данных (подпрограмма-процедура Vvod).
На рисунке 2.3 представлена схема алгоритма возведения действительного числа в степень (подпрограмма-функция vozvedenie_v_stepenb).
На рисунке 2.4 представлена схема алгоритма вычисления определителя квадратной матрицы (подпрограмма-функция Determinante ).
На рисунке 2.5 представлена схема алгоритма построения СЛАУ с неизвестными - коэффициентами интерполяционного полинома (подпрограмма-процедура sistema).
На рисунке 2.6 представлена схема алгоритма решения полученной CЛАУ (подпрограмма-процедура reshenie).
На рисунке 2.7 представлена схема алгоритма записи данных и результата в файл (подпрограмма-процедура zapisb_v_fail).
На рисунке 2.8 представлена схема алгоритма вывода содержимого записанного файла на экран (подпрограмма-процедура outputtoscreen).
Рисунок 2.1 - Блок-схема алгоритма решения задачи №2
Рисунок 2.2 - Блок-схема алгоритма ввода данных
Рисунок 2.3 - Блок-схема алгоритма возведения действительного числа в степень
Рисунок 2.4 - Блок-схема алгоритма вычисления определителя квадратной матрицы
Рисунок 2.5 - Блок-схема алгоритма построения СЛАУ с неизвестными - коэффициентами интерполяционного полинома
Рисунок 2.6 - Блок-схема алгоритма решения полученной CЛАУ
Рисунок 2.7 - Блок-схема алгоритма записи в файл данных и результата
Рисунок 2.8 - Блок-схема алгоритма вывода содержимого записанного файла на экран
2.6 Текст программы
program vandermond;
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;
vand:real;
n:integer;
fail,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;
function vozvedenie_v_stepenb(osnovanie:real;pokazatelb:integer):real;
{Функция возводит в степень заданное действительное число}
begin
if pokazatelb=0 then vozvedenie_v_stepenb:=1
else
vozvedenie_v_stepenb:=osnovanie*vozvedenie_v_stepenb(osnovanie,pokazatelb-1);end;
Function Determinante(Mas:Matr; kolvo:Integer):Real;
{Функция вычисляет определитель заданной матрицы}
var
Arr:Matr;
i,j,k:Integer;
sum:Real;
begin
For i:=0 to kolvo do
For j:=0 to kolvo do Arr[i,j]:=Mas[i,j];
sum:= 0;
if kolvo>1 then begin
for i:=0 to kolvo do
begin
for j:=0 to kolvo do
begin
if i<>j then
begin
for k:=0 to kolvo-1 do
begin
if j>i then Arr[k,j-1]:=mas[k+1,j] else
arr[k,j]:=mas[k+1,j];
end;
end
end;
if (i+1) mod 2 = 1 then sum:=sum+mas[0,i]*Determinante(Arr,kolvo-1)
else sum:=sum-mas[0,i]*Determinante(Arr,kolvo-1);
end;
determinante:=sum;
end
else begin
determinante:=mas[0,0]*mas[1,1]-mas[0,1]*mas[1,0];
end;
end;
procedure sistema(uzel,fun:mas; kolvo:integer; var a1:matr; var b1:mas; var opr:real);
{Процедура строит матрицы слау, необходимые для решения,
также в ней вычисляется определитель Вандермонда}
var i,j:integer;
begin
for i:=0 to kolvo do
for j:=0 to kolvo do
begin
a1[i,j]:=vozvedenie_v_stepenb(uzel[i],j);
end;
for i:=0 to kolvo do b1[i]:=fun[i];
opr:=determinante(a1,kolvo);
end;
procedure reshenie(a1:matr; b1:mas; opr:real; kolvo:integer; var koef:mas);
{В данной процедуре осуществляется поиск коэффициентов интерполяционного полинома }
var c1:matr;
i,j,k:integer;
begin
for k:=0 to kolvo do
begin
for i:=0 to kolvo do
for j:=0 to kolvo do
c1[i,j]:=0;
for i:=0 to kolvo do
for j:=0 to kolvo do
if j=k then c1[i,j]:=b1[i]
else c1[i,j]:=a1[i,j];
koef[k]:=determinante(c1,kolvo)/opr;
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
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: 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);
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;
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(Нажмите Enter);
readln;
sistema(X,Y,N,A,B,vand);
reshenie(a,b,vand,n,koef_polinoma);
zapisb(koef_polinoma,x,y,n,fail);
vblvod(fail,ekran);
writeln(Нажмите Enter для просмотра графика функции, затем еще раз для выхода из программы);
readln;
grafik(n,x,y,koef_polinoma);
END.
2.7 Тестовый пример
Построить интерполяционный полином по значениям функции в узлах
x0=-1 y0=-1; x1=0 y1=-1; x2=1 y2=-1; x3=2 y3=0
Решение. По данным узлам и значениям функции составим СЛАУ
c0-c1+c2-c3=-1;
c0=-1;
c0+c1+c2+c3=-1;
c0+2c1+4c2+8c3=0;
Решив данную систему, получим
c0=-1, с1=-0.1667, с2=0, с3=0.1667.
На рисунке 2.9 изображен тестовый пример работы программы для данной системы, на рисунке 2.10 - график полученной функции.
Рисунок 2.9 - Тестовый пример работы программы интерполирования функции, заданной в узлах, методом Вандермонда
Рисунок 2.10 - График функции, полученной в данном тестовом примере