ФЕДЕРАЛЬНОЕ АГЕНСТВО ПО ОБРАЗОВАНИЮ

ГОСУДАРСТВЕННОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО

ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

Тульский государственный университет

Кафедра автоматики и телемеханики

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

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

по дисциплине «вычислительная математика»

Выполнил студент группы _____________

(подпись)

Проверил _____________

(подпись)

Тула 2008г.

Содержание

Введение

1 Задача №1 Решение СЛАУ методом Гаусса-Зейделя

1.1 Постановка задачи

1.2 Математическая формулировка задачи

1.3 Обзор существующих численных методов

1.4 Численный метод решения

1.5 Схема алгоритма

1.6 Текст программы

1.7 Тестовый пример

1.8 Инструкция пользователю

1.9 Инструкция программисту

2 Задача №2 Интерполирование функции, заданной в узлах, методом Вандермонда

2.1 Постановка задачи

2.2 Математическая формулировка задачи

2.3 Обзор существующих численных методов

2.4 Численный метод решения

2.5 Схема алгоритма

2.6 Текст программы

2.7 Тестовый пример

2.8 Инструкция пользователю

2.9 Инструкция программисту

3 Задача №3 Среднеквадратичное приближение функции

3.1 Постановка задачи

3.2 Математическая формулировка задачи

3.3 Обзор существующих численных методов

3.4 Численный метод решения

3.5 Схема алгоритма

3.6 Текст программы

3.7 Тестовый пример

3.8 Инструкция пользователю

3.9 Инструкция программисту

4 Задача №4 Вычисление интеграла функций по составной формуле трапеций

4.1 Постановка задачи

4.2 Математическая формулировка задачи

4.3 Обзор существующих численных методов

4.4 Численный метод решения

4.5 Схема алгоритма

4.6 Текст программы

4.7 Тестовый пример

Заключение

Список использованных источников

Введение

Численное решение прикладных задач всегда интересовало математиков. Крупнейшие представители прошлого сочетали в своих исследованиях изучение явлений природы, получение их математического описания и его исследования. Анализ усложненных моделей потребовал создания специальных, как правило, численных методов решения задач. Названия этих методов - методы Ньютона, Эйлера, Гаусса, Чебышева и т.п. - свидетельствуют о том, что их разработкой занимались крупнейшие ученые своего времени.

Настоящее время характерно резким расширением приложений математики, во многом связанным с созданием и развитием средств вычислительной техники. Распространенное мнение о всемогуществе современных ЭВМ часто порождает впечатление, что математики избавились почти от всех хлопот, связанных с численным решением задач. В действительности дело обстоит иначе. Расширение возможности приложения математики обусловило математизацию многих научных дисциплин. Суть математизации состоит в построении математических моделей процессов и явлений и разработке методов их исследования. Современные успехи в решении таких проблем, как атомные и космические, вряд ли были бы возможны без использования численных методов. Прежде, чем поручать ЭВМ большую задачу, надо сделать много оценочных расчетов, понять, какие методы окажутся эффективными для данной задачи.

В данной работе рассматриваются следующие численные методы: решение системы линейных алгебраических уравнений методом Гаусса-Зейделя, интерполирование функции, заданной в узлах, методом Вандермонда (решение системы уравнений, составленных по условиям интерполяции), среднеквадратичное приближение функции, заданной в узлах, вычисление интеграла функции с использованием составной формулы трапеций.

1 Задача №1: решение системы линейных алгебраических уравнений методом Гаусса-Зейделя

1.1 Постановка задачи

Разработать схему алгоритма и написать программу на языке Turbo Pascal7.0. для решения систем линейных алгебраических уравнений, используя метод Гаусса-Зейделя.

1.2 Математическая формулировка задачи

Пусть дана система линейных уравнений

(1.1)

Коэффициенты a₁₁,₁₂,..., a_1n, ... , a_n1 , b₂ , ... , b_n считаются заданными.

Вектор-столбец неизвестных - является решением системы (1.1), если при подстановке этих чисел в уравнения системы все они обращаются в верное равенство. Задача состоит в том, чтобы найти вектор-строку неизвестных с заданной точностью е>0. Для решения задачи можно использовать метод Гаусса-Зейделя.

1.3 Обзор существующих численных методов

Методы решения систем линейных алгебраических уравнений делятся на две группы. Прямые методы дают решение задачи за конечное (точно определяемое для каждого метода) число операций. К прямым относятся следующие методы: метод Гаусса, метод Крамера, метод LU-разложения, метод Холецкого (квадратного корня), метод прогонки.

Решения, получаемые с помощью прямых методов, обычно содержат погрешности, вызванные округлением при выполнении операций над числами с плавающей точкой на ЭВМ с ограниченным числом разрядов. В ряде случаев эти погрешности могут быть значительными. В этих случаях предпочтительно использование итерационных методов.

Итерационные методы дают решение как предел бесконечной последовательности приближенных решений, в которых каждое последующее более точное приближение находится по уже найденному предыдущему решению (или предыдущим решениям). Из итерационных методов решения систем линейных алгебраических уравнений чаще всего используют метод простой итерации и метод Гаусса-Зейделя.

1.4 Численный метод решения

Для решения системы линейных алгебраических уравнений мы будем использовать метод Гаусса-Зейделя. Этот метод относится к итерационным.

Суть метода в том, что в процессе вычисления очередного приближения х₁^(к), х₂^(к), х_п^(к) найденные новые значения х_i^(к) сразу подставляются в правые части уравнений еще ненайденных переменных:



В общем случае для п уравнений

Если привести линейных алгебраических уравнений Ax = b к эквивалентной системе вида , то итерационный процесс выполняется при этом по соотношению

i = 1, 2, …, n.

Достаточное условие сходимости метода Гаусса-Зейделя определятся той же теоремой, что и достаточное условие сходимости метода простой итерации:

если какая-либо норма матрицы , согласованная с рассматриваемой нормой вектора , меньше единицы (), то последовательность в методе простой итерации сходится к точному решению системы со скоростью, не меньшей скорости геометрической прогрессии со знаменателем при любом начальном приближении .

Критерий окончания итерационного процесса имеет вид:

, где - допустимая погрешность вычисления.

Существует устойчивое заблуждение, что метод Гаусса-Зейделя сходится быстрее метода Якоби (метода простых итераций). Это действительно так, если матрица А положительно определенная и симметричная. Однако возможны случаи, когда метод итераций Зейделя сходится медленнее метода простой итерации, и даже случаи, когда метод простой итерации сходится, а метод итераций Зейделя расходится. Возможны и противоположные ситуации. Дело в том, что методы ориентированы на решение разных классов систем: метод Якоби -на системы с матрицами, близкими к диагональным, метод Гаусса-Зейделя - на системы с матрицами, близкими к нижним треугольным.

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) точки x₀ , x₁ , x₂ ,…, x_n и значения некоторой функции f(x) в этих точках :

f(x₀)= y₀ , f(x₁)= y₁ , … , f(x_n)= y_n .

Вид функции либо неизвестен вовсе, либо он неудобен для расчётов (сложная функция, которую необходимо при расчётах интегрировать, дифференцировать и т. п.). Требуется построить функцию F(x) (интерполирующую функцию), принимающую в узлах интерполяции те же значения, что и исходная функция

f(x), т. е. F(x₀)= y₀ , F(x₁)= y₁ , … , F(x_n)= y_n . (1)

В такой постановке задача имеет бесконечное множество решений, или совсем не имеет. Однако эта задача становится однозначной,

В такой постановке задача имеет бесконечное множество решений, или совсем не имеет. Однако эта задача становится однозначной,

если вместо произвольной функции искать полином степени не выше n, удовлетворяющий условиям (1):

F(x) = a₀ + a₁x + a₂x² +…+ a_nxⁿ

Для построения интерполирующего многочлена применяются многочисленные способы. Один из них - метод Вандермонда (решение СЛАУ, составленной по условиям интерполяции).

2.3 Обзор существующих численных методов

На практике для построения интерполирующего многочлена могут использоваться следующие методы: решение СЛАУ, составленной по условиям интерполяции (метод Вандермонда), метод Лагранжа, метод Ньютона, построение сплайна.

Интерполяционная формула Лагранжа:

Эта формула легко программируется. Число арифметических операций при вычислении растет не быстрее n². Интерполяционной формулой Лагранжа невозможно пользоваться при большом числе узлов интерполяции ().

Интерполирование по Ньютону:

P_n(x)=f(x₀)+(x-x₀)f(x₀,x₁)+ (x-x₀)(x-x₁)f(x₀,x₁,x₂)+...+

+(x-x₀)(x-x₁)...(x-x_n-1)f(x₀,x₁,...,x_n);

Полиномы Лагранжа и Ньютона представляют собой различную запись одного и того же многочлена .

Интерполяционную формулу Ньютона удобнее применять в том случае, когда интерполируется одна и та же функция f(x), но число узлов интерполяции постепенно увеличивается. Если узлы интерполяции фиксированы и интерполируется не одна, а несколько функций, то удобнее пользоваться формулой Лагранжа.

Интерполирование многочленами Лагранжа на всем отрезке [а,b] с использованием большого числа узлов интерполяции часто приводит к плохому приближению из-за накопления погрешности в процессе вычислений. Кроме того, из-за расходимости процесса интерполяции увеличение числа узлов необязательно приводит к повышению точности. Для того, чтобы избежать больших погрешностей, весь отрезок [а,b] разбивают на частичные отрезки и на каждом из них проводят интерполяцию полиномом невысокой степени. Это так называемая кусочно-полиномиальная интерполяция.

Для интерполирования на всем отрезке часто используют интерполирование с помощью сплайн-функций. Слово “сплайн” (spline) означает гибкую линейку, используемую для проведения гладких кривых через заданные точки. Сплайн-функцией или просто сплайном называют кусочно-полиномиальную функцию, определенную на отрезке [a,b] и имеющую на этом отрезке некоторое число непрерывных производных. Преимуществом сплайнов перед обычной интерполяцией является их сходимость и устойчивость процесса вычислений.

2.4 Численный метод решения

Пусть задана табличная функция своими (n+1) узловыми значениями (x₀,y₀ ) ; (x₁,y₁ ) ; (x₁,y₁ ) ; …, (x_n,y_n ) . Необходимо вычислить коэффициенты a_i , i=(0,1,2,…n) интерполирующего многочлена (1).

Так как по определению интерполирующий многочлен проходит через узлы интерполяции без погрешности, то значения каждого из них обращает в тождество уравнение (1), то есть

 a₀ + a₁x₀ + a₂x₀² +…+ a_nx₀ⁿ = y_0,

a₀ + a₁x₁ + a₂x₁² +…+ a_nx₁ⁿ = y_1,

a₀ + a₁x₂ + a₂x₂² +…+ a_nx₂ⁿ = y_2,

a₀ + a₁x_n + a₂x_n² +…+ a_nx_nⁿ = y_n .

Если функция однозначна и x_i различны, то в результате подстановки значений узловых точек интерполяции в уравнения (1) получаем систему (2) (n+1) уравнений с (n+1) неизвестным. Определитель этой системы называют определителем Вандермонда:

1 x₀ x₀² … x₀ⁿ

1 x₁ x₁² … x₁ⁿ

= 1 x₂ x₂² … x₂ⁿ

… … … …

1 x_n x_n² … x_nⁿ

Определитель Вандермонда отличен от нуля, если x_j все различные. Следовательно, данная система всегда имеет решение, и притом единственное. Таким образом, доказано существование и единственность интерполяционного многочлена. Значения коэффициентов интерполирующего многочлена получают, решив систему (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:\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;

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 - График функции, полученной в данном тестовом примере

2.8 Инструкция пользователю

Данная программа осуществляет интерполирование функции, заданной в узлах, методом Вандермонда. Вам будет предложено ввести количество узлов, узлы интерполяции и значения функции в них. Данные и результат записываются в файл interpol.txt, и его содержимое выводится на экран. После этого вы просмотрите график функции, для выхода из программы нажмите enter.

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}, когда значение приближаемой функции заданы в числе узлов, превышающих число базисных функций.

Будем нумеровать узлы от аргумента индексами х₀,...,х_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:\20\20\20.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:\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');

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.

3.7 Тестовый пример

На рисунке 3.7 изображен тестовый пример работы программы, на рисунке 3.8 - график полученной функции.



Рисунок 3.7 - Тестовый пример работы программы выполнения среднеквадратичного приближение функции, заданной в узлах

y(x)=-0.2541x^2+2.3852x+0.9964

Рисунок 3.8 - График функции, полученной в данном тестовом примере

3.8 Инструкция пользователю

Данная программа осуществляет среднеквадратичного приближение функции, заданной в узлах. Данные считываются из файла 20.txt. Результат - полином 2-й степени - выводится на экран. После этого вы просмотрите график функции для выхода из программы нажмите enter.

3.9 Инструкция программисту

Данная программа осуществляет среднеквадратичного приближение функции, заданной в узлах.

Типы:

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 -одномерный массив действительных чисел.

Переменные:

fail:text- файловая переменная, соответствующая файлу, их которого считываются данные

x,y:mas1-узлы и значения функции в них

koef_polinoma:mas2- искомые коэффициенты полинома

b:mas2-вектор свободных членов полученной СЛАУ

n:integer-номер последнего узла(нумерация с нуля)

psi:mas4 - система базисных функций

a:mas3 -матрица СЛАУ.

Подпрограммы

1) procedure chtenie_dannblh(var f:text; var uzlbl,funktsiya:mas1; var kolvo:integer)

Формальные параметры:

-возвращаемые значения

f:text-файл, из которого производится чтение данных

uzlbl,funktsiya:mas1- массивы узлов приближения и значений функции в них

kolvo:Integer-номер последнего узла(нумерация с нуля)

Локальные переменные:

I,j:Integer-счетчики цикла;

x_s,y_s,s:string-переменные, в которые возвращаются значения узла и значения функции (в строковой форме);

dlina_stroki:integer-длина строки файла;

code:integer - индикатор ошибки ввода данных(параметр процедуры перевода строковой переменной в число Val);

tab-Позиция символа табуляции в строке;

2) procedure bazis(uzlbl:mas1; kolvo:integer; var f:mas4)

Формальные параметры:

-передаваемые значения

uzlbl:mas1-массив узлов приближения

kolvo:Integer-номер последнего узла(нумерация с нуля)

-возвращаемые значения

f:mas4-базис степенных функций;

Локальные переменные:

I,j:Integer-счетчики цикла;

3) sistema(f:mas4;funktsiya:mas1; kolvo:integer; var a1:mas3; var b1:mas2)

Формальные параметры:

-передаваемые значения

funktsiya:mas1-массив значений функции в узлах приближения

kolvo:Integer-номер

последнего узла(нумерация с нуля)

f:mas4-базис степенных функций;

-возвращаемые значения

a1:m последнего узла(нумерация с нуля)

f:mas4-базис степенных функций;

-возвращаемые значения

a1:mas3, b1:mas2 - матрица СЛАУ с неизвестными - коэффициентами полинома, вектор свободных членов

f:mas4-базис степенных функций;

-возвращаемые значения

a1:mas3, b1:mas2 - матрица СЛАУ с неизвестными - коэффициентами полинома, вектор свободных членов.

-возвращаемые значения

c:mas2-искомые коэффициенты полинома.

Локальные переменные:

I,j,k:Integer-счетчики цикла;

4) rewenie_systembl(a1:mas3; b1:mas2; var c:mas2)

Формальные параметры:

-передаваемые значения

a1:mas3, b1:mas2 - матрица СЛАУ с неизвестными - коэффициентами полинома, вектор свободных членов.

-возвращаемые значения

c:mas2-искомые коэффициенты полинома.

Локальные переменные:

I,j,k:Integer-счетчики цикла;

l:mas3-нижняя треугольная матрица матрицы A1,

y:mas2-матрица, полученная в результате умножения матрицы неизвестных на транспонированную матрицу L; sum:real-переменная, используемая при вычислении элементов матрицы Y.

Задача №4 Вычисление интегралов функций

4.1. Постановка задачи

Разработать схему алгоритма и написать программу на языке Turbo Pascal7.0 для вычисления интегралов функций, используя составную формулу трапеций.

4.2 Математическая формулировка задачи

Задача численного интегрирования состоит в нахождении приближенного значения определенного интеграла от заданной функции у(х) на заданном интервале [а,b]. Все методы численного интегрирования основаны на замене функции у(х) такой аппроксимирующей функцией f(x), интеграл от которой

легко выражается через элементарные функции от неизвестных точек.

Введем на [а,b] сетку: а=x₀<х₁<...<х_i<...<х_n=b. В качестве аппроксимирующей функции f(x) возьмем обобщенный интерполяционный многочлен по некоторой системе базисных функций:

Можно доказать, что если система базисных функций , i=0,1,...,n является системой Чебышева на интервале [а,b], то всегда можно перейти к новой базисной системе такой, что

.

В этом случае интерполяционный многочлен по новой базисной системе будет иметь в качестве коэффициентов значения интерполяционной функции в узлах. Следовательно, искомое приближенное значение интеграла есть линейная комбинация интегралов от базисных функций с коэффициентами

интегрируемой функции у(х) и могут быть вычислены заранее

тогда (3)

Тогда

(1)

Выражения такого вида, лежащие в основе численных методов, называются квадратурными формулами. Отдельные квадратурные формулы отличаются выбором узлов x₀,...,х_n и коэффициентов с₀,...,с_n. Очевидно, что при заданных узлах значения коэффициентов с₀,...,с_k определяются исходным выбором базисной системы функций {, k=0,1,...,n}, по которой cтроится обобщенный интерполяционный многочлен. Величину

называют остаточным членом квадратичной формулы (1).

Если пределы интегрирования а и b являются узлами интерполирования, то квадратурная формула называется замкнутого типа, в противном случае - открытого типа.

4.3. Обзор существующих методов численного интегрирования функции

Существует множество методов интегрирования. Ниже приведены наиболее распространенные методы.

Квадратурная формула Ньютона-Котеса

Квадратурными формулами Ньютона-Котеса называются квадратурные формулы, полученные, с помощью интерполяционных многочленов на равномерной сетке х₀,х₁,...,х_n,х_i+1-х_i=h=const.Выведем явное выражение для коэффициентов с_i k=0,1,…,n в выражение (1). В полиноме Лагранжа

обозначим

и , ,

получим с учетом х₀=а, х_i=х₀+1h, i=1,2,...,n-1, х_n=b, что х_i-х_j_=х₀+ih-х₀-jh=h(i-j).

Тогда

Тогда

или с учетом того, что , заменив переменную, получим

, i=0,1,...,n. Так как , то , где

,

i=0,1,…,n - постоянные, называемые коэффициентами Котеcа. Нетрудно убедиться, что

Квадратурная формула при этом принимает вид

,

где

,

i=0,1,...,n.

Некоторые другие формулы являются частным случаем форму-лы Ньютона -- Котеса. В частности, при n = 1 получаем метод тра-пеций (для одного участка), при n = 2 -- формулу Симпсона. Не следует брать n > 10, так как при больших значениях k алгоритм оказывается неустойчивым.

При разбиении всего интервала [a,b] на несколько участков формулу нужно применять для каждого участка, а результаты сложить.

4.4 Численный метод

Метод трапеций относится к простейшим методам. подынте-гральная функция заменяется наклонной прямой у=с₁х+с₀.

Формулы интегрирования при разбиении отрезка [a,b] на n частей с равномерным шагом h соответственно приоб-ретают вид:

-для одного участка интегрирования:

,

, (3)

-для n участков:

. (4)

Формула (2) - составная формула трапеций. Именно она используется в программе для вычисления интегралов функций.

4.5 Схема алгоритма