Вычислительная математика (Лабораторный практикум) (стр. 4 )

. (1)

Формула (1) называется формулой механических квадратур, – квадратурной суммой, Аj – квадратурными коэффициентами, хj – узлами или абсциссами квадратурного правила.

Остаточным членом квадратурного правила называется величина

. (2)

Возможны различные подходы к построению квадратурных формул.

5.1.  Интерполяционные квадратурные формулы

Пусть заданы значения подынтегральной функции f(x) в точках x0, x1, ¼, xn принадлежащих [a,b], тогда для f(x) строят интерполяционный многочлен Лагранжа n-ой степени, т. е.

, где . (3)

Формула (3) называется интерполяционной квадратурной формулой. Ее остаточный член

, (4)

где h – некоторая точка [a,b].

Если узлы квадратурного правила равноотстоящие, то квадратурные коэффициенты принимают вид

(5)

где , , .

5.2.  Квадратурные формулы Ньютона – Котеса

Запишем квадратурное правило для равноотстоящих узлов:

, (6)

где .

При заданных значениях n коэффициенты принимаю следующие значения:

n=0, ;

n=1, ;

n=2, , ;

n=3, , и т. д.

Замечание: предпочтительно использовать формулы Ньютона – Котеса с малыми значениями n, а для уменьшения погрешности результата отрезок разбивается на достаточно большое число интервалов, и к каждому из них применяют квадратурную формулу с малым числом узлов, затем результаты складывают.

5.2.1.  Формула прямоугольников

Пусть функция f(x) на [a,b] заменяется интерполяционным многочленом Лагранжа нулевого порядка, построенным по значению в средней точке отрезка[a, b], т. е. и . Тогда

и , где xÎ[a,b]. (7)

Разделим [a,b] на m равных частей длины . К каждому частичному отрезку [a+ih,a+(i+1)h] применим формулу прямоугольников, сложив результаты, получим обобщенную формулу прямоугольников:

. (8)

5.2.2.  Формула трапеций

Пусть функция f(x) на [a,b] заменяется интерполяционным многочленом первого порядка, построенным по значениям в точках а и b. Тогда

и , где xÎ[a,b]. (9)

Разделим [a,b] на m равных частей длины . К каждому частичному отрезку [a+ih,a+(i+1)h] применим формулу трапеций, сложив результаты и обозначив , получим обобщенную формулу трапеций:

. (10)

5.2.3.  Формула Симпсона (формула парабол)

Пусть функция f(x) на [a,b] заменяется интерполяционным многочленом второго порядка, построенным по значениям в точках а, и b. Тогда

и , (11)

где xÎ[a,b].

Разделим [a,b] на четное число m равных частей длины . К каждому частичному отрезку [a+(i-1)h,a+(i+1)h] применим формулу Симпсона, сложив результаты и обозначив , получим обобщенную формулу Симпсона

.(12)

5.3.  Квадратурная формула Гаусса

Пусть функция y=f(x) задана на промежутке [-1,1]. Нужно подобрать узлы квадратурного правила и коэффициенты так, чтобы квадратурная формула

(13)

была точной для всех полиномов f(x) наивысшей степени m=2n-1, т. к. имеем 2m неизвестных , а полином степени 2n-1 определяется 2n коэффициентами. Остаточный член обращается в нуль, когда , где Сi=const, i=0,¼,m. Тогда

Учитывая соотношение: , получаем систему 2n уравнений относительно :

(14)

Система (14) нелинейная, и ее исследование громоздко. Поэтому воспользуемся теоремой:

для того чтобы квадратурная формула (13) интерполяционного типа была точна для всех многочленов степени не выше 2n-1, необходимо и достаточно, чтобы ее узлы xj были корнями многочлена wn(x), ортогонального на [-1;1] к любому многочлену степени не выше n.

Ортогональную систему многочленов, имеющих n различных действительных корней на [-1;1], образуют многочлены Лежандра

(15)

Итак, в квадратурной формуле с n узлами, имеющей наивысшую степень точности 2n-1, узлы xj, j=1,...,n являются корнями многочлена Лежандра n-й степени, а из системы (14), зная xj, легко найдем Аj.

Для произвольного интервала [a,b] сделаем замену . В этом случае формула Гаусса примет вид

. (16)

Таблица узлов и коэффициентов формулы Гаусса

n	xj	Aj
n=1	x1=0	A1=2
n=2	x1=-0, x2=0,	A1=1 A2=1
n=3	x1=-0, x2=0 x3=0,	A1=0, A2=0, A3=0,
n=4	x1=-0, x2=-0, x3=0, x4=0,	A1=0, A2=0, A3=0, A4=0,
n=5	x1=-0, x2=-0, x3=0 x4=0, x5=0,	A1=0, A2=0, A3=0, A4=0, A5=0,
n=6	x1=-0, x2=-0, x3=-0, x4=0, x5=0, x6=0,	A1=0, A2=0, A3=0, A4=0, A5=0, A6=0,
n=7	x1=-0, x2=-0, x3=-0, x4=0 x5=0, x6=0, x7=0,	A1=0, A2=0, A3=0, A4=0, A5=0, A6=0, A7=0,

5.4.  Метод Монте-Карло

Методы решения задач, использующие случайные величины, называются методами Монте-Карло.

Пусть методом Монте-Карло требуется вычислить m-кратный интеграл

, (17)

где функция f(x1,...,xm) задана в ограниченной замкнутой области S, а эта область заключена в m-мерном параллелепипеде . Для преобразования m-мерного параллелепипеда в m-мерный единичный куб сделаем замену переменных следующего вида: , при этом 0£xj£1. Якобиан этого преобразования

.

Тогда интеграл (17) перепишется в виде

, (18)

где , s – новая область интегрирования, лежащая внутри m-мерного единичного куба.

Выберем m равномерно распределенных на [0,1] последовательностей случайных чисел ; ¼, . Точки можно рассматривать как случайные точки из m-мерного единичного куба. Будем считать, что n случайных точек принадлежат области s, а (N – n) точек не принадлежат ей.

Если взять достаточно большое число n точек из области s, то приближенно можно считать

, (19)

тогда выражение (18) можно переписать в виде

, (20)

здесь s – объем области интегрирования. Если вычисление объема затруднительно, то можно считать, что , тогда

.

5.5.  Задачи

I.   Вычислить определенный интеграл при n=24 по соответствующей квадратурной формуле:

№ п/п	Прямоугольников	Трапеций	Симпсона
1
2
3
4
5
6
7

№ п/п	Прямоугольников	Трапеций	Симпсона
8
9
10

II. Вычислить интегралы из задания I по формуле Гаусса при n=7.

III. Вычислить интегралы методом Монте-Карло с точностью до . Причем первоначально взять 20 случайных чисел, равномерно распределенных на [0,1], а затем добавлять по 10 чисел сразу и вычислять значения интеграла до тех пор, пока не будет достигнута требуемая точность (данные взять из задания I).

6.  Вычисление собственных значений и собственных векторов матриц

Определение. Вековым определителем матрицы называется определитель вида

.

Определение. Собственным значением квадратной матрицы А называется такое число l, для которого выполняется соотношение

, (21)

если – некоторый ненулевой вектор, называемый собственным вектором матрицы А, соответствующим собственному значению l.

Соотношение (21) можно переписать в виде

. (22)

Условием существования ненулевого решения однородной системы (22) является требование

. (23)

Это уравнение называется характеристическим уравнением матрицы А.

Все методы нахождения собственных значений и соответствующим им собственных векторов можно разделить на два класса: точные и итерационные.

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

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

При решении данных задач необходимо знать, что все собственные значения лежат в интервале, определяемом нормой исходной матрицы:

,

где – норма матрицы А, которая может быть посчитана двумя способами:

a)  евклидова норма ;

b)  сумма максимума модулей по строкам .

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

, .

6.1.  Метод Данилевского

Суть метода в приведении векового определителя к нормальному виду Фробениуса:

. (24)

Разложив определипо первой строке будем иметь:

. (25)

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

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

(26)

с помощью преобразований подобия матрица (26) приводится к матрице, имеющей нормальную форму Форбениуса:

(27)

Процесс приведения к нормальной форме Форбениуса:

I. Матрица А умножается справа на матрицу С1, а слева на :

,

В результате получаем матрицу , у которой (n-1)-й столбец имеет нужный нам вид.

II. На втором шаге матрица умножается справа на матрицу С2, а слева на :

,

В результате получаем матрицу , у которой (n-1)-й и (n-2)-й столбцы имеют тот же вид, что и соответствующие столбцы матрицы Форбениуса.

Продолжая этот процесс, после (n-1)-го шага получим матрицу , имеющую нормальную форму Форбениуса. Здесь предполагается, что , отличны от нуля.