Рефотека.ру / Математика

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

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

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

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

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

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


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


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

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


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

(подпись)

Проверил _____________

(подпись)


Тула 2008г.

Содержание


Введение

1. Решение систем линейных алгебраических уравнений методом простой итерации

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

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

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

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

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

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

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

2. Полиномиальная интерполяция функции методом Ньютона с разделенными разностями

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4. Численное интегрирование функций методом Гаусса

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

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

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

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

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

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

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

Заключение

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

Введение


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

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

Разработка и исследование вычислительных алгоритмов и их применение к решению конкретных задач составляет содержание огромного раздела современной математики — вычислительной математики.

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

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

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

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

1. Решение систем линейных алгебраических уравнений методом простой итерации


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


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


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


Пусть А – невырожденная матрица Численные методы решения типовых математических задачи нужно решить систему


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


где диагональные элементы матрицы А ненулевые.


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


Метод Гаусса

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

Пусть дана СЛАУ

Запишем расширенную матрицу системы:

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


На первом шаге алгоритма Гаусса выберем диагональный элемент (если он равен 0, то первую строку переставляем с какой-либо нижележащей строкой) и объявляем его a11≠0 ведущим, а соответствующую строку и столбец, на пересечении которых он стоит - ведущими. Обнулим элементы ведущего столбца. Для этого сформируем числа (-a22/a11), (-a31/a11), .. , (an1/a11).

LU-разложения матриц

Компьютерная реализация метода Гаусса часто осуществляется с использованием LU-разложения матриц.

LU – разложение матрицы A представляет собой разложение матрицы A в произведение нижней и верхней треугольных матриц, т.е.


A=LU


где L - нижняя треугольная матрица (матрица, у которой все элементы, находящиеся выше главной диагонали равны нулю, lij=0 при i>j), U- верхняя треугольная матрица (матрица, у которой все элементы, находящиеся ниже главной диагонали равны нулю, uij=0 при i>j).

LU – разложение может быть построено с использованием описанного выше метода Гаусса. Рассмотрим k - ый шаг метода Гаусса, на котором осуществляется обнуление поддиагональных элементов k - го столбца матрицы. Как было описано выше, с этой целью используется следующая операция

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


В терминах матричных операций такая операция эквивалентна умножению A(k)=MkA(k-1), где элементы матрицы определяются следующим образом

В терминах матричных операций такая операция эквивалентна умножению A(k)=MkA(k-1), где элементы матрицы определяются следующим образом


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


В результате прямого хода метода Гаусса получим , A(n-1)=U


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

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


где A(n-1)=U - верхняя треугольная матрица, а - нижняя треугольная матрица, имеющая вид .

Таким образом, искомое разложение A=LU получено.

Метод прогонки

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


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


решение которой будем искать в виде


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


где Qi,Pi,i=1,n - прогоночные коэффициенты, подлежащие определению. Для их определения выразим из первого уравнения СЛАУ (1.1) x1 через x2, получим:


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


откуда


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

Из второго уравнения СЛАУ (1.1) с помощью (1.3) выразим x2 через x3, получим:


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


откуда


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


Продолжая этот процесс, получим из i-го уравнения СЛАУ (1.1):


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

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


следовательно


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


Из последнего уравнения СЛАУ имеем


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


то есть


Метод простых итераций

При большом числе уравнений прямые методы решения СЛАУ (за исключением метода прогонки) становятся труднореализуемыми на ЭВМ прежде всего из-за сложности хранения и обработки матриц большой размерности. В то же время характерной особенностью ряда часто встречающихся в прикладных задачах СЛАУ является разреженность матриц. Число ненулевых элементов таких матриц мало по сравнению с их размерностью. Для решения СЛАУ с разреженными матрицами предпочтительнее использовать итерационные методы.

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


Метод Зейделя решения СЛАУ

Метод простых итераций довольно медленно сходится. Для его ускорения существует метод Зейделя, заключающийся в том, что при вычислении компонента xik+1 вектора неизвестных на (k+1)-й итерации используются x1k+1, x2k+1, .., xik+1 уже вычисленные на (k+1)-й итерации. Значения остальных компонент берутся из предыдущей итерации. Так же как и в методе простых итераций строится эквивалентная СЛАУ и за начальное приближение принимается вектор правых частей . Тогда метод Зейделя для известного вектора на k-ой итерации имеет вид:

предыдущей итерации. Так же как и в методе простых итераций строится эквивалентная СЛАУ и за начальное приближение принимается вектор правых частей . Тогда метод Зейделя для известного вектора на k-ой итерации имеет вид:


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


Из этой системы видно, что Численные методы решения типовых математических задач, где В - нижняя треугольная матрица с диагональными элементами , равными нулю, а С - верхняя треугольная матрица с диагональными элементами, отличными от нуля, α=B+C. Следовательно

При таком способе приведения исходной СЛАУ к эквивалентному виду метод простых итераций носит название метода Якоби.


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


откуда


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


Таким образом, метод Зейделя является методом простых итераций с матрицей правых частей α=(E-B)-1C и вектором правых частей (E-B)-1β.

Разрешим систему относительно неизвестных при ненулевых диагональных элементах , aii≠0, i= 1,n (если какой-либо коэффициент на главной диагонали равен нулю, достаточно соответствующее уравнение поменять местами с любым другим уравнением). Получим следующие выражения для компонентов вектора β и матрицы α эквивалентной системы


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


В качестве нулевого приближения x(0) вектора неизвестных примем вектор правых частей x(0)=β. Тогда метод простых итераций примет вид:


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


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

Имеет место следующее достаточное условие сходимости метода простых итераций.

Метод простых итераций (1.19) сходится к единственному решению СЛАУ при любом начальном приближении x(0), если какая-либо норма матрицы α эквивалентной системы меньше единицы Численные методы решения типовых математических задач

Если используется метод Якоби (выражения (1.18) для эквивалентной СЛАУ), то

достаточным условием сходимости является диагональное преобладание матрицы A, т.е.

Численные методы решения типовых математических задач(для каждой строки матрицы A модули элементов, стоящих на главной диагонали, больше суммы модулей недиагональных элементов). Очевидно, что в этом случае ||α||c меньше единицы и, следовательно, итерационный процесс (1.19) сходится.

Приведем также необходимое и достаточное условие сходимости метода простых итераций. Для сходимости итерационного процесса (1.19) необходимо и достаточно, чтобы спектр матрицы α эквивалентной системы лежал внутри круга с радиусом, равным единице.

При выполнении достаточного условия сходимости оценка погрешности решения на k- ой итерации дается выражением:


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

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

Следует подчеркнуть, что это неравенство дает завышенное число итераций k, поэтому редко используется на практике


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


Разрешим систему относительно неизвестных при ненулевых диагональных элементах , aii≠0, i= 1,n (если какой-либо коэффициент на главной диагонали равен нулю, достаточно соответствующее уравнение поменять местами с любым другим уравнением). Получим следующие выражения для компонентов вектора β и матрицы α эквивалентной системы:

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


При таком способе приведения исходной СЛАУ к эквивалентному виду метод простых итераций носит название метода Якоби.

В качестве нулевого приближения x(0) вектора неизвестных примем вектор правых частей x(0)=β. Тогда метод простых итераций примет вид:


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


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

Имеет место следующее достаточное условие сходимости метода простых итераций.

Метод простых итераций (1.19) сходится к единственному решению СЛАУ при любом начальном приближении x(0), если какая-либо норма матрицы α эквивалентной системы меньше единицы Численные методы решения типовых математических задач

Если используется метод Якоби (выражения (1.18) для эквивалентной СЛАУ), то

достаточным условием сходимости является диагональное преобладание матрицы A, т.е.

Численные методы решения типовых математических задач(для каждой строки матрицы A модули элементов, стоящих на главной диагонали, больше суммы модулей недиагональных элементов). Очевидно, что в этом случае ||α||c меньше единицы и, следовательно, итерационный процесс (1.19) сходится.

Приведем также необходимое и достаточное условие сходимости метода простых итераций. Для сходимости итерационного процесса (1.19) необходимо и достаточно, чтобы спектр матрицы α эквивалентной системы лежал внутри круга с радиусом, равным единице.

При выполнении достаточного условия сходимости оценка погрешности решения на k- ой итерации дается выражением:


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


где x·- точное решение СЛАУ.

Процесс итераций останавливается при выполнении условия , где εε≤)(kε - задаваемая вычислителем точность.

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

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

откуда получаем априорную оценку числа итераций k при ||α||<1


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

Следует подчеркнуть, что это неравенство дает завышенное число итераций k, поэтому редко используется на практике.


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

program Yakobi;

uses crt;

const

maxn=100;

type

matrix=array[1..maxn,1..maxn] of real;

vector=array[1..maxn] of real;

vector1=array[1..maxn] of real;

var

i,j,n,k1: integer;

e,norma:real;

a: matrix;

b: vector;

x2,x3: vector1;

imya,dannble_i_rezultat,ekran:string;

procedure input(var kolvo:integer; var pogreshnostb:real; var matr1:matrix; var matr2:vector);

{Ввод исходных данных}

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;

end;

end;

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


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


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

2. Полиномиальная интерполяция функции методом Ньютона с разделенными разностями


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


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


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


Дана табличная функция:


i yi
0 x0 y
1 x1 0
2 x2 y
... ... 1
n xn y


2


...


y


n

или

Численные методы решения типовых математических задачТочки с координатами (xi, yi) называются узловыми точками или узлами.

Количество узлов в табличной функции равно N=n+1.

Необходимо найти значение этой функции в промежуточной точке, например, x=D, причем Численные методы решения типовых математических задач.

Для решения задачи строим интерполяционный многочлен.

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


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

Интерполяционный многочлен может быть построен при помощи специальных интерполяционных формул Лагранжа, Ньютона, Стерлинга, Бесселя и др.

Интерполяционный многочлен по формуле Лагранжа имеет вид:

Докажем, что многочлен Лагранжа является интерполяционным многочленом, проходящим через все узловые точки, т.е. в узлах интерполирования xi выполняется условие Ln(xi) = yi. Для этого будем последовательно подставлять значения координат узловых точек таблицы в многочлен (2.1). В результате получим:


если x=x0, то Ln(x0) = y0,

если x=x1, то Ln(x1) = y1,

……………

если x=xn, то Ln(xn) = yn.


Это достигнуто за счет того, что в числителе каждой дроби при соответствующем значении уj, j=0,1,2,…,n отсутствует сомножитель (x-xi), в котором i=j, а знаменатель каждой дроби получен заменой переменной х на соответствующее значение хj.

Таким образом, интерполяционный многочлен Лагранжа приближает заданную табличную функцию, т.е. Ln(xi) = yi и мы можем использовать его в качестве вспомогательной функции для решения задач интерполирования, т.е. Численные методы решения типовых математических задач.

Чем больше узлов интерполирования на отрезке [x0,xn] , тем точнее интерполяционный многочлен приближает заданную табличную функцию, т.е. тем точнее равенство:

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


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

При решении задачи экстраполирования функции с помощью интерполяционного многочлена вычисление значения функции за пределами отрезка [x0,xn] обычно производят не далее, чем на один шаг h, равный наименьшей величине


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


так как за пределами отрезка [x0,xn] погрешности, как правило, увеличиваются.


Интерполяция по Ньютону

Интерполяционный многочлен по формуле Ньютона имеет вид:


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


где n – степень многочлена,


Численные методы решения типовых математических задач- разделенные разности 0-го, 1-го, 2-го,…., n-го порядка, соответственно.

Сплайн-интерполяция

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

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

Например, для некоторых функций (рис.) необходимо задать все кубические функции q1(x), q2(x), …qn(x).

В наиболее общем случае эти многочлены имеют вид:


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


где kij - коэффициенты, определяемые описанными ранее условиями, количество которых равно 4n. Для определения коэффициентов kij необходимо построить и решить систему порядка 4n.

Первые 2n условий требуют, чтобы сплайны соприкасались в заданных точках:


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


Следующие (2n-2) условий требуют, чтобы в местах соприкосновения сплайнов были равны первые и вторые производные:


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

Система алгебраических уравнений имеет решение, если число уравнений соответствует числу неизвестных. Для этого необходимо ввести еще два уравнения. Обычно используются следующие условия:


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


При построении алгоритма метода первые и вторые производные удобно аппроксимировать разделенными разностями соответствующих порядков.

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


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


Значения f(x0), f(x1), … , f(xn) , т.е. значения табличной функции в узлах, называются разделенными разностями нулевого порядка (k=0).


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

Отношение Численные методы решения типовых математических задачназывается разделенной разностью первого порядка (k=1) на участке [x0, x1] и равно разности разделенных разностей нулевого порядка на концах участка [x0, x1], разделенной на длину этого участка.

Для произвольного участка [xi, xi+1] разделенная разность первого порядка (k=1) равна


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


Отношение Численные методы решения типовых математических задачназывается разделенной разностью второго порядка (k=2) на участке [x0, x2] и равно разности разделенных разностей первого порядка, разделенной на длину участка [x0, x2].

Для произвольного участка [xi, xi+2] разделенная разность второго порядка (k=2) равна


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


Таким образом, разделенная разность k-го порядка на участке [xi, xi+k] может быть определена через разделенные разности (k-1)-го порядка по рекуррентной формуле:


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


Где Численные методы решения типовых математических задач Численные методы решения типовых математических задач n – степень многочлена.

Максимальное значение k равно n. Тогда i =0 и разделенная разность n-го порядка на участке [x0,xn] равна

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


т.е. равна разности разделенных разностей (n-1)-го порядка, разделенной на длину участка [x0,xn].

Разделенные разности


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


являются вполне определенными числами, поэтому выражение (2.2) действительно является алгебраическим многочленом n-й степени. При этом в многочлене (2.2) все разделенные алгебраическим многочленом n-й степени. При этом в многочлене (2.2) все разделенные разности определены для участков [x0, x0+k], Численные методы решения типовых математических задач.

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


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


Докажем это. Пусть х=х0 , тогда многочлен (2.2) равен


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


Пусть х=х1, тогда многочлен (2.2) равен


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


Пусть х=х2, тогда многочлен (2.2) равен

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


Заметим, что решение задачи интерполяции по Ньютону имеет некоторые преимущества по сравнению с решением задачи интерполяции по Лагранжу. Каждое слагаемое интерполяционного многочлена Лагранжа зависит от всех значений табличной функции yi, i=0,1,…n. Поэтому при изменении количества узловых точек N и степени многочлена n (n=N-1) интерполяционный многочлен Лагранжа требуется строить заново. В многочлене Ньютона при изменении количества узловых точек N и степени многочлена n требуется только добавить или отбросить соответствующее число стандартных слагаемых в формуле Ньютона (2.2). Это удобно на практике и ускоряет процесс вычислений.


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


На рисунке 2.1 представлена схема алгоритма решения задачи №2.

На рисунке 2.2 представлена схема алгоритма ввода исходных данных (подпрограмма-процедура Vvod).

На рисунке 2.3 представлена схема алгоритма интерполяции функции по методу Ньютона с разделенными разностями (newt)

На рисунке 2.4 представлена схема алгоритма записи данных и результата в файл (подпрограмма-процедура zapisb_v_fail).

На рисунке 2.5 представлена схема алгоритма вывода содержимого записанного файла на экран (подпрограмма-процедура outputtoscreen).


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


program newton;

uses crt,graph;

const c=10;

type matr=array[0..c,0..c] of real;

mas=array[0..c] of real;

var x,y,koef_polinoma:mas;

a:matr;

b:mas;

d1:real;

n:integer;

fail,fail1,ekran:text;

procedure Vvod(var kolvo:integer; var uzel,fun:mas);

{Процедура осуществляет ввод данных:пользователь вводит с клавиатуры

узлы интерполяции и значения функции в них. Также определяется количество узлов.}

var code,i:integer; s:string;

begin

writeln('введите количество узлов');

readln(kolvo);

kolvo:=kolvo-1;

for i:=0 to kolvo do

begin

repeat

writeln('введите ',i,'-й узел интерполирования');

readln(s);

val(s,uzel[i],code);

until code=0;

repeat

writeln('введите значение функции, соответствующее данному узлу');

readln(s);

val(s,fun[i],code);

until code=0;

end;

end;


procedure newt(var kolvo:integer; D:real; var koef,uzel,fun:mas)

var L,P:real;

begin

L:=fun[0];

P:=1;

for i:=1 to kolvo do

begin

P:=P*(D-uzel[i-1]);

for j:=1 to kolvo-i do

begin

fun[j]:=(fun[j-1]-fun[j])/(uzel[j+i]-uzel[i])

end;

koef[i]:=fun[0];

L:=L+P*fun[0];

end;

end;

procedure newt(var kolvo:integer; D:real; var koef,uzel,fun:mas) {процедура интерполяции функции методом Ньютона}

var L,P:real;

begin

L:=fun[0];

P:=1;

for i:=1 to kolvo do

begin

P:=P*(D-uzel[i-1]);

for j:=1 to kolvo-i do

begin

fun[j]:=(fun[j-1]-fun[j])/(uzel[j+i]-uzel[i])

end;

koef[i]:=fun[0];

L:=L+P*fun[0];

end;

end;

procedure zapisb(koef:mas; uzel,fun:mas; kolvo:integer; var f:text);

{В данной процедуре осуществляется запись в файл данных и результата}

var i:integer;

begin

assign(f,'interpol.txt');

rewrite(f);

for i:=0 to kolvo do writeln(f,'x= ',uzel[i]:8:4,' f(x)=',fun[i]:8:4);

writeln(f,'Интерполяционный полином');

write(f,'p(x)=',koef[0]:8:4);

for i:=1 to kolvo do if i>1 then write (f,'+(',koef[i]:8:4,')*x^',i)

else write (f,'+(',koef[i]:8:4,')*x');

close(f);

end;

procedure vblvod(var f1,f2:text);

{Вывод содержимого записанного файла на экран}

var s1:string;

begin

clrscr;

assign(f1,'interpol.txt');

reset(f1);

assigncrt(f2);

rewrite(f2);

while not eof(f1) do


assigncrt(f2);

rewrite(f2);

while not eof(f1) do

begin

Readln(f1,s1);

writeln(f2,s1);

end;

close(f2);

close(f1);

end;

procedure grafik(kolvo:integer; uzlbl,funktsiya:mas; c:mas);

{Построение графика полученной функции}

var driver,mode,Err,a1,b1,z,i,j:integer; s:string; xt,yt:real;

begin

driver:=detect;

InitGraph(driver,mode,'d:\tp7\bp\bgi');

err:=graphresult;

if err<>grok then writeln('Ошибка при инициализации графического режима')

else

begin

Setcolor(9);

line(320,0,320,480);

line(0,240,640,240);

settextstyle(smallfont,horizdir,3);

setcolor(10);

outtextxy(320,245,'0');

a1:=0;

b1:=480;

z:=-10;

for i:=0 to 20 do

begin

if z<>0 then

begin

str(z,s);

setcolor(10);

outtextxy(a1,245,s);

outtextxy(325,b1,s);

setcolor(8);

line(0,b1,640,b1);

line(a1,0,a1,480);

end;

outtextxy(325,b1,s);

setcolor(8);

line(0,b1,640,b1);

line(a1,0,a1,480);

end;

a1:=a1+32;

b1:=b1-24;

z:=succ(z);

end;

setcolor(5);

for i:=0 to kolvo do

begin

xt:=uzlbl[i];

yt:=funktsiya[i];

putpixel(round(320+xt*32),round(240-yt*24),5);

end;

moveto(round(320+uzlbl[0]*32),round(240-funktsiya[0]*24));

setcolor(11);

for i:=0 to kolvo do

begin

xt:=uzlbl[i];

yt:=0;

for j:=0 to kolvo do yt:=yt+c[j]*vozvedenie_v_stepenb(uzlbl[i],j);

lineto(round(320+xt*32),round(240-yt*24));

moveto(round(320+xt*32),round(240-yt*24));

end;

readln;

closegraph;

end;

end;

{Основная часть программы}

BEGIN

CLRSCR;

Writeln('Программа осуществляет интерполирование функции, заданной в узлах');

Vvod(N,X,Y);

writeln(‘введите значение промежуточной точки’);

readln(d1);


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


writeln('Нажмите Enter');

readln;

newt(N,d1,X,Y,koef_polinoma);

zapisb(koef_polinoma,x,y,n,fail);

vblvod(fail,fail1);

writeln('Нажмите Enter для просмотра графика функции, затем еще раз для выхода из программы');

readln;

grafik(N,X,Y,koef_polinoma);

END.

readln(d1);

writeln('Нажмите Enter');

readln;

newt(N,d1,X,Y,koef_polinoma);

zapisb(koef_polinoma,x,y,n,fail);

vblvod(fail,fail1);

writeln('Нажмите Enter для просмотра графика функции, затем еще раз для выхода из программы');

readln;

grafik(N,X,Y,koef_polinoma);

END.


Дана табличная функция:

Вычислить разделенные разности 1-го, 2-го, 3-го порядков (n=3) и занести их в диагональную таблицу.

Разделенные разности первого порядка:


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


Разделенные разности второго порядка:


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

Разделенная разность третьего порядка:


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


Интерполяционный многочлен Ньютона для заданной табличной функции имеет вид:


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


График интерполяционного многочлена будет таким:

procedure zapisb(koef:mas; uzel,fun:mas; kolvo:integer; var f:text);

{В данной процедуре осуществляется запись в файл данных и результата}

var i:integer;

begin

assign(f,'interpol.txt');

rewrite(f);

for i:=0 to kolvo do writeln(f,'x= ',uzel[i]:8:4,' f(x)=',fun[i]:8:4);

writeln(f,'Интерполяционный полином');

write(f,'p(x)=',koef[0]:8:4);

for i:=1 to kolvo do if i>1 then write (f,'+(',koef[i]:8:4,')*x^',i)

else write (f,'+(',koef[i]:8:4,')*x');

close(f);

end;

procedure vblvod(var f1,f2:text);

{Вывод содержимого записанного файла на экран}

var s1:string;

begin

clrscr;

assign(f1,'interpol.txt');

reset(f1);

assigncrt(f2);

rewrite(f2);

while not eof(f1) do

begin

Readln(f1,s1);

writeln(f2,s1);

end;

close(f2);

close(f1);

end;

procedure grafik(kolvo:integer; uzlbl,funktsiya:mas; c:mas);

{Построение графика полученной функции}

var driver,mode,Err,a1,b1,z,i,j:integer; s:string; xt,yt:real;

begin

driver:=detect;

InitGraph(driver,mode,'d:\tp7\bp\bgi');

err:=graphresult;

if err<>grok then writeln('Ошибка при инициализации графического режима')

else

begin

Setcolor(9);

line(320,0,320,480);

line(0,240,640,240);

settextstyle(smallfont,horizdir,3);

setcolor(10);

outtextxy(320,245,'0');

a1:=0;

b1:=480;

z:=-10;

for i:=0 to 20 do

begin

if z<>0 then


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


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


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


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


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


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


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


где Численные методы решения типовых математических задач - весовая функция.

Такое приближение называют среднеквадратичным.


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


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

Когда уровень неопределенности в задании приближаемой функции f(xi), i=1..m, достаточно велик, что характерно для обработки экспериментальных данных, бессмысленно требовать выполнения условий интерполирования; кроме того, число точек задания функции f(xi) часто весьма велико. Все это делает применение интерполирования мало перспективным по причинам плохой обусловленности задачи высокой размерности и проблем сходимости процесса интерполяции

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


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


Метод среднеквадратичного приближения обеспечивает построение полинома Pn(x), исходя из минимизации величины

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


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


в пространстве параметров a0 , a1 ,...,an. Существуют различные подходы к решению задачи минимизации функции D(a). Простейший из них приводит к необходимости решения нормальной системы линейных алгебраических уравнений


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


Однако, уже при n > 5 матрица такой системы оказывается настолько плохо обусловленной, что полученные из (3.4) значения aj оказываются мало пригодными для вычисления Pn(x). Поэтому, при необходимости построения полиномов наилучшего среднеквадратичного приближения более высоких степеней применяют другие алгоритмы, например, метод сингулярного разложения.


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


Можно рассмотреть две задачи:

1 - подобрать функцию Численные методы решения типовых математических задач так, чтобы выполнялось неравенство


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


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


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


Далее займемся отысканием наилучшего приближения.

Разложим функцию Численные методы решения типовых математических задач по системе линейно независимых функций Численные методы решения типовых математических задач:


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


В дальнейшем для сокращения записи будем пользоваться определением скалярного произведения в пространстве функций Численные методы решения типовых математических задач:

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


Подставляя (3.7) в условие (3.6), получим


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


Дифференцируя это выражение по Численные методы решения типовых математических задач и приравнивая производные нулю, получим


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


Определитель этой системы есть определитель Грама функций Численные методы решения типовых математических задач. В силу их линейной независимости этот определитель не равен нулю. Следовательно, из системы (3.8) можно найти коэффициенты Численные методы решения типовых математических задач, определяющие функцию Численные методы решения типовых математических задач согласно (3.6) и минимизирующие интеграл от погрешности Численные методы решения типовых математических задач . Таким образом, наилучшее среднеквадратичное приближение существует и оно единственно.

При использовании ортонормированной системы функций Численные методы решения типовых математических задач система (3.8) упрощается:


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

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

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

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

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

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


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


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

Условие наилучшего среднеквадратичного приближения записывается следующим образом:


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

Полагая Численные методы решения типовых математических задач, где Численные методы решения типовых математических задач, и подставляя этот многочлен в (3.10), придем к системе (3.8), в которой скалярные произведения вычисляют согласно (3.9). Описанная процедура аппроксимации носит название метода наименьших квадратов.

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

Система уравнений (3.8) при этом принимает вид


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

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

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


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

Рис. 3.1 Основная программа

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

Рис. 3.2 Процедура ввода данных

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

Рис 3.3 Процедура среднеквадратичного приближения

program srpribl; {$R+}

uses graph;

label 1,2,3,4;

const m=2;

type mas= array [1..21] of real;

mas1= array [1..m] of real;

mas2= array [1..m,1..m+1] of real;

var i,j:byte;

y1,x1:mas;

xx1:mas1;

a1:mas2;

procedure vvod (x,y: mas);

begin

x[1]:=0;y[1]:=0.290234387293458; x[2]:=0.25;y[2]:=0.201247759722173;

x[3]:=0.5;y[3]:=0.0712686786428094;x[4]:=0.75; y[4]:=0.044294935464859;

x[5]:=1;y[5]:=-0.0745576142333448; x[6]:=1.25;y[6]:=-0.0807833694852889;

x[7]:=1.5;y[7]:=-0.233371530473232;x[8]:=1.75;y[8]:=-0.283957027737051;

x[9]:=2;y[9]:=-0.308697660081089;x[10]:=2.25;y[10]:=-0.42091366359964;

x[11]:=2.5;y[11]:=-0.516991161741316;x[12]:=2.75;y[12]:=-0.427710095947851;

x[13]:=3;y[13]:=-0.374748698528856;x[14]:=3.25;y[14]:=-0.229905794281513;

x[15]:=3.5;y[15]:=-0.205365492492496639;x[16]:=3.75;y[16]:=-0.129155068378896;

x[17]:=4;y[17]:=-0.0438349825330079;x[18]:=4.25;y[18]:=0.0294586319476366;

x[19]:=4.5;y[19]:=0.132592592108995;x[20]:=4.75;y[20]:=0.206369574274868;

x[21]:=5;y[21]:=0.26959548862651;

end;

procedure srpribl (xx:mas1;a:mas2);

var l:real;

s,z,k1:integer;

begin

for s:=1 to m-1 do

for z:=s+1 to m do

begin

a[z,s]:=-a[z,s]/a[s,s];

for k1:=s+1 to m+1 do a[z,k1]:=a[z,k1]+a[z,s]*a[s,k1]

end;

xx[m]:=a[m,m+1]/a[m,m]; writeln(' xx[',m,']=',xx[m]:2:3);

for i:=m-1 downto 1 do

begin

l:=a[i,m+1];

for j:=i+1 to m do l:=l-xx[j]*a[i,j];

xx[i]:=l/a[i,i]; writeln(' xx[',i,']=',xx[i]:2:3)

end

end;


procedure Grafik (var x,y:mas;xx:mas1)

var ec,gd,gm:integer;

begin

gd:=detect;

initgraph (gd,gm,' ');

ec:=graphresult;

if ec<>grok then begin

writeln ('Oshibka v inicializacii grafika');

halt (1);

end;


setcolor(white);

line (0,420,620,420);

line (0,0,0,420);

setcolor (white);

for i:=1 to 21 do begin

circle (round (x[i]*150),round (y[i]*100),1);

end;

setcolor (yellow);

for i:=1 to m do begin

circle (round (x[i]*150),round (xx[i]*100),1);

end;

setcolor (green);

for i:=2 to m do begin

line (round (x[i-1]*150),round(xx[i-1]*100),round (x[i]*150),

round (xx[i]*100));

end;

end;

begin

vvod(x1,y1);

for i:=1 to 2 do

for j:=1 to 3 do a[i,j]:=0;

a[1,1]:=21;

for i:=1 to 21 do

begin

a[1,2]:=a[1,2]+x[i];

a[2,1]:=a[2,1]+x[i];

a[2,2]:=a[2,2]+x[i]*x[i];

a[1,3]:=a[1,3]+y[i];

a[2,3]:=a[2,3]+y[i]*x[i]

end;

srpribl(xx1,a1);

for i:=1 to 21 do

writeln(y[i]:2:3,' ',xx[1]+xx[2]*x[i]:2:3);

Grafik(x1,y1,xx1);

end.


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


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


Найти тригонометрический многочлен наилучшего среднеквадратичного приближения наименьшей степени со среднеквадратичным отклонением меньшим Численные методы решения типовых математических задачдля функции Численные методы решения типовых математических задач

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


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

Вычислим коэффициенты Фурье


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


Вычислим частичные суммы ряда Фурье


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


Вычислим среднеквадратичное отклонение


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


Найдем минимальное Численные методы решения типовых математических задач, при котором Численные методы решения типовых математических задачбудет меньше Численные методы решения типовых математических задач


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

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


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


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

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


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


Построим график среднеквадратичного отклонения


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


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


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

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


Найдем минимальное Численные методы решения типовых математических задач, при котором Численные методы решения типовых математических задачбудет меньше Численные методы решения типовых математических задач

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

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


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


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


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


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


Построим график среднеквадратичного отклонения


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

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


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


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

4. Численное интегрирование функций методом Гаусса


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


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


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


Пусть функция задана на стандартном интервале Численные методы решения типовых математических задач. Задача состоит в том, чтобы подобрать точки Численные методы решения типовых математических задач и коэффициенты Численные методы решения типовых математических задач так, чтобы квадратурная формула


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


была точной для всех полиномов наивысшей возможной степени.


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


Одномерный случай

Основная идея большинства методов численного интегрирования состоит в замене подынтегральной функции на более простую, интеграл от которой легко вычисляется аналитически. При этом для оценки значения интеграла получаются формулы вида


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

где Численные методы решения типовых математических задач— число точек, в которых вычисляется значение подынтегральной функции. Точки Численные методы решения типовых математических задач называются узлами метода, числа Численные методы решения типовых математических задач— весами узлов. При замене подынтегральной функции на полином нулевой, первой и второй степени получаются соответственно методы прямоугольников, трапеций и парабол (Симпсона). Часто формулы для оценки значения интеграла называют квадратурными формулами.


Метод прямоугольников

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


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


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


Метод трапеций

Если функцию на каждом из частичных отрезков аппроксимировать прямой, проходящей через конечные значения, то получим метод трапеций.

Площадь трапеции на каждом отрезке:


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

Погрешность аппроксимации на каждом отрезке:


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


Полная формула трапеций в случае деления всего промежутка интегрирования на отрезки одинаковой длины h:


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


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

Погрешность формулы трапеций:


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


Метод парабол (метод Симпсона)

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


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

Если разбить интервал интегрирования на 2N равных частей, то имеем


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

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


Если разбить интервал интегрирования на 2N равных частей, то имеем


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

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


Увеличение точности

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

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

При стремлении количества разбиений к бесконечности, оценка интеграла стремится к его истинному значению для любого численного метода.

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


Метод Гаусса

Описанные выше методы используют фиксированные точки отрезка (концы и середину) и имеют низкий порядок точности (0 --- методы правых и левых прямоугольников, 1 --- методы средних прямоугольников и трапеций, 3 --- метод парабол (Симпсона)). Если мы можем выбирать точки, в которых мы вычисляем значения функции Численные методы решения типовых математических задач, то можно при том же количестве вычислений подынтегральной функции получить методы более высокого порядка точности. Так для двух (как в методе трапеций) вычислений значений подынтегральной функции, можно получить метод уже не 1-го, а 3-го порядка точности:


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


В общем случае, используя Численные методы решения типовых математических задачточек, можно получить метод с порядком точности Численные методы решения типовых математических задач. Значения узлов метода Гаусса по Численные методы решения типовых математических задачточкам являются корнями полинома Лежандра степени Численные методы решения типовых математических задач.

Значения узлов метода Гаусса и их весов приводятся в справочниках специальных функций. Наиболее известен метод Гаусса по пяти точкам.

В общем случае, используя Численные методы решения типовых математических задачточек, можно получить метод с порядком точности Численные методы решения типовых математических задач. Значения узлов метода Гаусса по Численные методы решения типовых математических задачточкам являются корнями полинома Лежандра степени Численные методы решения типовых математических задач.

Значения узлов метода Гаусса и их весов приводятся в справочниках специальных функций. Наиболее известен метод Гаусса по пяти точкам.

Метод Гаусса-Кронрода

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


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

где Численные методы решения типовых математических задач— узлы метода Гаусса по Численные методы решения типовых математических задачточкам, а Численные методы решения типовых математических задач параметров Численные методы решения типовых математических задач, Численные методы решения типовых математических задач, Численные методы решения типовых математических задачподобраны таким образом, чтобы порядок точности метода был равен Численные методы решения типовых математических задач.

Тогда для оценки погрешности можно использовать эмпирическую формулу:


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


где Численные методы решения типовых математических задач— приближённое значение интеграла, полученное методом Гаусса по Численные методы решения типовых математических задачточкам.


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


Пусть функция задана на стандартном интервале Численные методы решения типовых математических задач. Задача состоит в том, чтобы подобрать точки Численные методы решения типовых математических задач и коэффициенты Численные методы решения типовых математических задач так, чтобы квадратурная формула


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


была точной для всех полиномов наивысшей возможной степени.

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

Запишем полином в виде Численные методы решения типовых математических задач и подставим в (4.1). Получим

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

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


Приравнивая выражения при одинаковых коэффициентах Численные методы решения типовых математических задачполучим


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

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


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


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

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

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

. . . . . . .

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

Система (4.2) нелинейная, и ее решение найти довольно трудно. Рассмотрим еще один прием нахожденияЧисленные методы решения типовых математических задачи Численные методы решения типовых математических задач. Свойства полиномов Лежандра


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


таковы:


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

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


3) полином Лежандра Численные методы решения типовых математических задач имеет Численные методы решения типовых математических задач различных и действительных корней, расположенных на интервале Численные методы решения типовых математических задач.

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


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


Функция Численные методы решения типовых математических задач при Численные методы решения типовых математических задач есть многочлен степени не выше Численные методы решения типовых математических задач. Значит для этой функции формула Гаусса справедлива:


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

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

Разложим Численные методы решения типовых математических задач в ряд по ортогональным многочленам Лежандра:


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

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

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


т.е. все коэффициенты Численные методы решения типовых математических задач при Численные методы решения типовых математических задач . Значит Численные методы решения типовых математических задач с точностью до численного множителя совпадает с Численные методы решения типовых математических задач. Таким образом, узлами формулы Гаусса являются нули многочлена Лежандра степени Численные методы решения типовых математических задач.

Зная Численные методы решения типовых математических задач, из линейной теперь системы первых Численные методы решения типовых математических задач (4.2) легко найти коэффициенты являются нули многочлена Лежандра степени Численные методы решения типовых математических задач.

Зная Численные методы решения типовых математических задач, из линейной теперь системы первых Численные методы решения типовых математических задач (4.2) легко найти коэффициенты Численные методы решения типовых математических задачЧисленные методы решения типовых математических задач. Определитель этой системы есть определитель Вандермонда.

Формулу Численные методы решения типовых математических задач, в которой Численные методы решения типовых математических задач- нули полинома Лежандра Численные методы решения типовых математических задач, а Численные методы решения типовых математических задач определяют из (3.3), называют квадратурной формулой Гаусса.

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


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

Рис. 4.1 Основная программа метода

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

Рис .4.2 Интегрирование методом Гаусса

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

Рис 4.3 Процедура подсчета коэффициентов по методу Гаусса


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


uses crt,graph;

var aaa,bbb,kkk:real;

const

g10c1=0.9739065285/6.2012983932;

g10c2=0.8650633667/6.2012983932;

g10c3=0.6794095683/6.2012983932;

g10c4=0.4333953941/6.2012983932;

g10c5=0.1488743390/6.2012983932;

g10x1=0.0666713443/6.2012983932;

g10x2=0.1494513492/6.2012983932;

g10x3=0.2190863625/6.2012983932;

g10x4=0.2692667193/6.2012983932;

g10x5=0.2955242247/6.2012983932;


function F(x:real):real;{интегрируемая функция}

begin

F:= ln(1+x*x*x);

end;

function gauss_calc(a,b:real):real; {метод Гаусса}

var n,m,s,s1,s2,s3,s4,s5 :real;

begin

m:=(b+a)/2; n:=(b-a)/2;

s1:=g10c1*(f(m+n*g10x1)+f(m-n*g10x1));

s2:=g10c2*(f(m+n*g10x2)+f(m-n*g10x2));

s3:=g10c3*(f(m+n*g10x3)+f(m-n*g10x3));

s4:=g10c4*(f(m+n*g10x4)+f(m-n*g10x4));

s5:=g10c5*(f(m+n*g10x5)+f(m-n*g10x5));

s:=s1+s2+s3+s4+s5;

gauss_calc:=s*(b-a);

end;

{рекурсивная ф-ция подсчета с заданной точностью}

{ gc - ранее посчитаный интеграл на интервале (a,b)}

function gauss(a,b,eps,gc:real):real;

var t,ga,gb :real;

begin

t:=(a+b)/2; {разбиваем интервал на две половинки}

ga:=gauss_calc(a,t); {в каждой половинке считаем интеграл}

gb:=gauss_calc(t,b);

if abs(ga+gb-gc)>eps then {проверяем точность вычислений}

begin

ga:=gauss(a,t,eps/2,ga); {рекурсия для первой половинки}

gb:=gauss(t,b,eps/2,gb); {рекурсия для второй половинки}

end; {при этом точность повышаем, чтобы }

{при сложении ошибка не накапливалась}

gauss:=ga+gb; {интеграл = сумме интегралов половинок}

end;


procedure inputnum(prm:string;var num:real;lb,ub:real);

var q:boolean;

begin

repeat

write('Введите ',prm,' ');readln(num);

q:=(lb>=num) or (num>ub);

if q then writeln('Число должно быть от ', lb:0:0,' до ',ub:0:0);

until not q;

end;

function main_menu:integer;

var i:integer;

begin

Writeln('==========================================================');

Writeln('0 - выход');

Writeln('1 - решать тестовый пример a=0 b=1.2 k=10 eps = 0.0001');

Writeln('2 - решать пример с произвольными a, b, k, eps');

Writeln('----------------------------------------------------------');

Write('Выбор >>> ');readln(i);

Writeln('==========================================================');

main_menu:=i;

end;

{Вывод графика}

procedure outputgraph(a,b,a1,b1:real;n:integer);

var i,j,j1,k:integer;t,y1,y2,x1,x2,x,y:double;s:string;

begin

clearviewport;

x1:=a1-1;x2:=b1+1;

if x1<0.5 then x1:=-0.5;

y2:=f(ln(bbb/aaa)/(bbb-aaa))*1.2;

y1:=-y2;

{Линия y=0}

setcolor(15);

y:=0;

j:=trunc(480*(y-y2)/(y1-y2));

line(0,j,639,j);

{Линии x=a,x=b}

setcolor(5);

j:=trunc(480*(-y2)/(y1-y2));

i:=trunc(640*(a-x1)/(x2-x1));

j1:=trunc(480*(f(a)-y2)/(y1-y2));

line(i,j,i,j1);

i:=trunc(640*(b-x1)/(x2-x1));

j:=trunc(480*(-y2)/(y1-y2));

j1:=trunc(480*(f(b)-y2)/(y1-y2));

line(i,j,i,j1);

{Сам график}

setcolor(14);

setlinestyle(0,0,3);

t:=(b-a)/n;

k:=0;

j1:=trunc(480*(-y2)/(y1-y2));

for i:=0 to 640 do begin

x:=(x2-x1)*i/640+x1;

y:=f(x);

j:=trunc(480*(y-y2)/(y1-y2));

if j>479 then j:=479;

if j<0 then j:=0;

setcolor(14);

setlinestyle(0,0,3);

if i=0 then moveto(i,j) else lineto(i,j);

setcolor(8);

if (x>t*k+a) then begin

k:=k+1;

setcolor(15);

end;


k:=0;

j1:=trunc(480*(-y2)/(y1-y2));

for i:=0 to 640 do begin

x:=(x2-x1)*i/640+x1;

y:=f(x);

j:=trunc(480*(y-y2)/(y1-y2));

if j>479 then j:=479;

if j<0 then j:=0;

setcolor(14);

setlinestyle(0,0,3);

if i=0 then moveto(i,j) else lineto(i,j);

setcolor(8);

if (x>t*k+a) then begin

k:=k+1;

setcolor(15);

end;

setlinestyle(0,0,1);

if (x>=a) and (x<=b) then line(i,j,i,j1);

end;

setcolor(15);

y:=f(b);

i:=trunc(640*(b-x1)/(x2-x1));

j:=trunc(480*(y-y2)/(y1-y2));

line(i,j,i,j1);

setlinestyle(0,0,1);

setcolor(12);

{Подписи}

setcolor(13);

str(a:6:6,s);

s:='a='+s;

i:=trunc(640*(a-x1)/(x2-x1));

outtextxy(i,j1+2,s);

str(b:6:6,s);

s:='b='+s;

i:=trunc(640*(b-x1)/(x2-x1));

outtextxy(i-10,j1+2,s);

setcolor(15);

y:=0;

j:=trunc(480*(y-y2)/(y1-y2));

outtextxy(5,j+3,'y=0');

readkey;

end;

procedure equateit(eps:real);

var integral,a,b:real;i,j:integer;

begin

a:=0;b:=1;

Integral:=gauss(a,b,eps,gauss_calc(a,b));

writeln('Интеграл = ',integral:0:6);

readkey;

i:=vga;j:=vgahi;

initgraph(i,j,'..\bgi');

outputgraph(a,(b+a)/2,a,b,1);

outputgraph((b+a)/2,b,a,b,1);

outputgraph(a,b,a,b,1);

closegraph;

end;

var sel:integer;

eps:real;

begin

repeat

clrscr;

sel:=main_menu;

case sel of

1:begin

aaa:=0.1;bbb:=1.2;kkk:=10;

eps:=1e-4;

equateit(eps);

end;

2:begin

inputnum('a',aaa,0,1000);

inputnum('b',bbb,-1000,1000);

inputnum('k',kkk,-1000,1000);

inputnum('точность',eps,0.000000001,1);

equateit(eps);

end;

end;

until sel=0;

end.


i:=vga;j:=vgahi;

initgraph(i,j,'..\bgi');

outputgraph(a,(b+a)/2,a,b,1);

outputgraph((b+a)/2,b,a,b,1);

outputgraph(a,b,a,b,1);

closegraph;

end;

var sel:integer;

eps:real;

begin

repeat

clrscr;

sel:=main_menu;

case sel of

1:begin

aaa:=0.1;bbb:=1.2;kkk:=10;

eps:=1e-4;

equateit(eps);

end;

2:begin

inputnum('a',aaa,0,1000);

inputnum('b',bbb,-1000,1000);

inputnum('k',kkk,-1000,1000);

inputnum('точность',eps,0.000000001,1);

equateit(eps);

end;

end;

until sel=0;

end.


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


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

Используя семиточечную формулу вычислить интеграл Численные методы решения типовых математических задач

(Точное решение - 2,3201169227)


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

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

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

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

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

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

Заключение


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

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


Бахвалов Н., Жидков Н., Кобельков Г. Численные методы. М.: Лаборатория базовых знаний, 2001. 632 с.

Вержбицкий В.М., Численных методы. Линейная алгебра и нелинейные уравнения. М.: Высшая школа, 2000. 266 с.

Вержбицкий В.М., Основы численных методов. М.: Высшая школа, 2002. 840 с.

Пирумов У.Г. Численные методы . М.: Дрофа, 2003. 224 с.

Буслов В.А., Яковлев С.Л. Яисленные методы и решение уравнений. Санкт-Петербург, 2001. 44 с.

Фаронов В.В. Турбо Паскаль 7.0. Начальный курс. Учебное пособие. – М.: Нолидж, 1997. – 616 с.

Похожие работы:

  1. • Решение прикладных задач численными методами
  2. • Средства языка программирования Паскаль для решения ...
  3. •  ... высокого уровня для реализации численных методов
  4. •  ... высокого уровня для реализации численных методов
  5. • Язык программирования Норма
  6. • Язык программирования Норма
  7. • Методы математического моделирования экономики
  8. •  ... уровня для реализации численных методов и прикладных программ
  9. • Построение интерполяционного многочлена и вычисление по нему ...
  10. • Численные методы решения систем линейных уравнений
  11. • Методы численного моделирования МДП-структур
  12. • Интерполяция функции одной переменной методом Ньютона
  13. • Синтаксический анализ языка НОРМА. Разбор описания
  14. • Математическое мышление младших школьников
  15. • План-конспект урока Математическое моделирование при решении ...
  16. • Применение новейших экономико-математических методов для ...
  17. • Математические методы в экономическом анализе
  18. • Численное решение системы линейных уравнений с ...
  19. • Математическое моделирование при решении экологических задач
Смотреть все похожие работы
Рефетека ру refoteka@gmail.com