Численные методы решения типовых математических задач

курсовая работа

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).

Делись добром ;)