Численные методы решения типовых математических задач
1.5 Схема алгоритма
На рисунке 1.1 представлена схема алгоритма решения задачи №1.
На рисунке 1.2 представлена схема алгоритма ввода исходных данных (подпрограмма-процедура Input).
На рисунке 1.3 представлено продолжение схемы алгоритма ввода исходных данных (подпрограмма-процедура Input).
На рисунке 1.4 представлена схема алгоритма проверки сходимости метода (подпрограмма-процедура proverka_shodimosti).
На рисунке 1.5 представлено продолжение схемы алгоритма проверки сходимости метода (подпрограмма-процедура proverka_shodimosti).
На рисунке 1.6 представлена схема алгоритма решения системы линейных алгебраических уравнений методом Гаусса-Зейделя (подпрограмма-процедура reshenie_sistembl).
На рисунке 1.7 представлена схема алгоритма записи исходных данных и результата в файл (подпрограмма-процедура zapisb_v_fail).
На рисунке 1.8 представлена схема алгоритма вывода содержимого записанного файла на экран (подпрограмма-процедура outputtoscreen).
Рисунок 1.1 - Блок-схема алгоритма решения задачи №1
Рисунок 1.2 - Блок-схема алгоритма ввода данных
Рисунок 1.3 - Блок-схема алгоритма ввода данных (продолжение)
Рисунок 1.4 - Блок-схема алгоритма проверки сходимости метода
Рисунок 1.5 - Блок-схема алгоритма проверки сходимости метода (продолжение)
Рисунок 1.6 - Блок-схема алгоритма решения системы линейных алгебраических уравнений методом Гаусса-Зейделя
Рисунок 1.7 - Блок-схема алгоритма записи исходных данных и результата в файл
Рисунок 1.8 - Блок-схема алгоритма вывода содержимого записанного файла на экран
1.6 Текст программы
Далее приведен текст программы решения СЛАУ методом Гаусса-Зейделя.
program metod_Gaussa_Zeidelya;
uses crt;
const c=10;
type mas1=array [1..c,1..c] of real;
mas2=array [1..c] of real;
mas3=array [1..c,0..20] of real;
var dannble_i_rezultat,ekran:text;
shodimostb:boolean;
a,alpha:mas1;
b,beta:mas2;
x:mas3;
imya:string;
chetchik,n,prib:integer;
e:real;
procedure input(var kolvo:integer; var pogreshnostb:real; var matr1:mas1; var matr2:mas2);
{Ввод исходных данных}
var i,j,code:integer;
a_s: string;
b_s: string;
begin
writeln(введите количество уравнений);
readln(kolvo);
writeln(введите погрешность вычисления);
readln(pogreshnostb);
writeln(введите матрицу коэффициентов при неизвестных);
for i:=1 to kolvo do
for j:=1 to kolvo do
begin
repeat
begin
writeln(введите элемент [,i,,,j,] и нажмите Enter);
readln(a_s);
if (i=j) and (a_s=0) then
repeat
begin
writeln(Элементы на главной диагонали должны быть отличны от нуля. Повторите ввод);
readln(a_s);
end;
until a_s<>0;
val(a_s,matr1[i,j],code);
end;
until code=0;
end;
writeln(введите вектор свободных коэффициентов);
for j:=1 to kolvo do
begin
repeat
writeln(введите элемент ,j, и нажмите Enter);
readln(b_s);
val(b_s,matr2[j],code);
until code=0
d;
end;
procedure proverka_shodimosti(matr1:mas1;matr2:mas2; kolvo:integer; var matr3:mas1; var matr4:mas2; var bool:boolean);
{Проверяется возможность решения}
var i,j:integer; summa1,summa2:array [1..c] of real; norma1,norma2,norma3,summa3:real;
procedure proverka_shodimosti(matr1:mas1;matr2:mas2; kolvo:integer; var matr3:mas1; var matr4:mas2; var bool:boolean);
{Проверяется возможность решения}
var i,j:integer; summa1,summa2:array [1..c] of real; norma1,norma2,norma3,summa3:real;
begin
for i:=1 to kolvo do
begin
summa1[i]:=0;
summa2[i]:=0;
end;
summa3:=0;
for i:=1 to kolvo do
for j:=1 to kolvo do
begin
if i=j then matr3[i,j]:=0 else matr3[i,j]:=-matr1[i,j]/matr1[i,i];
summa1[i]:=summa1[i]+abs(matr3[i,j]);
summa3:=summa3+sqr(matr3[i,j]);
end;
for j:=1 to kolvo do matr4[j]:=matr2[j]/matr1[j,j];
for j:=1 to kolvo do
for i:=1 to kolvo do
summa2[j]:=summa2[j]+abs(matr3[i,j]);
norma1:=summa1[1];
norma2:=summa1[2];
norma3:=Sqrt(summa3);
for i:=1 to kolvo do
begin
if summa1[i]>norma1 then norma1:=summa1[i];
if summa2[i]>norma2 then norma2:=summa2[i];
end;
if (norma1<1) or (norma2<1) or (norma3<1) then bool:=true else bool:=false;
end;
procedure reshenie_sistembl(matr3:mas1;matr4:mas2;kolvo:integer;pogreshnostb:real; var matr5:mas3; var k:integer);
{В процедуре осуществляется решение системы методом Гаусса-Зейделя}
var s1,s2:real; i,j,p:integer;
begin
for i:=1 to kolvo do matr5[i,0]:=0;
k:=0;
repeat
begin
k:=k+1;
p:=0;
for i:=1 to kolvo do
begin
s1:=0;
s2:=0;
for j:=1 to i-1 do s1:=s1+matr3[i,j]*matr5[j,k];
for j:=i+1 to kolvo do s2:=s2+matr3[i,j]*matr5[j,k-1];
matr5[i,k]:=s1+s2+matr4[i];
if (abs(matr5[i,k]-matr5[i,k-1])<=pogreshnostb) then p:=p+1;
end;
END.
1.7 Тестовый пример
Задание: Найти решение СЛАУ методом Гаусса-Зейделя:
Матрица системы
Вектор свободных членов
Решение: Воспользуемся математическим программным пакетом Mathcad13.
На рисунке 1.9 изображен тестовый пример работы программы для данной системы.
Рисунок 1.9 - Тестовый пример работы программы решения СЛАУ методом Гаусса-Зейделя
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).