Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Лабораторная работа № 2
МЕТОДЫ ЧИСЛЕННОГО ИНТЕГРИРОВАНИЯ ФУНКЦИЙ
1 Цель работы
Ознакомление с методами численного интегрирования, с понятием порядка точности численного метода, а также со способами контроля численных результатов.
2 Описание метода
Пусть необходимо вычислить интеграл
. (2.1)
Разобьем отрезок интегрирования на n частей. Введем в рассмотрение последовательность узловых точек xi[a, b] : xi=ih+a, i=0,...,n. Величина называется шагом разбиения.
Все основные способы численного интегрирования сводятся к интерполяции функции по ее значениям в узловых точках f(xi) и интегрированию интерполяционного многочлена. При этом значение интеграла получается приближенно равным сумме
. (2.2)
При различном выборе Ai и xi получаются различные квадратурные формулы. Каждая из них обладает некоторой погрешностью m, которую можно оценить следующим образом:
mchk , (2.3)
где c>0 - некоторая постоянная, не зависящая от h (зависящая от a, b, вида f(x) и метода интегрирования),
k-некоторое целое число, называемое порядком точности метода. Чем больше k, тем быстрее убывает погрешность при уменьшении h.
Предлагается рассмотреть квадратурные формулы Ньютона-Котеса, к которым, в частности, относятся формулы прямоугольников (левых, правых и симметричных), трапеций, парабол. В таблице 2.1 представлены эти формулы и значения констант для оценки погрешности по формуле (2.3). В таблице обозначено
, f (j)(x) - j-ая производная f(x).
Таблица 2.1
|
№ |
Название метода |
Квадратурная формула |
c |
k |
|
1 |
Левых прямоуголь ников |
1 |
||
|
2 |
Правых прямоуголь ников |
1 |
||
|
3 |
Симметрич ных прямоуголь ников |
2 |
||
|
4 |
Трапеций |
2 |
||
|
5 |
Парабол |
4 |
Одним из способов практической оценки погрешности дискретизации, которая возникает при применении численных методов, (в том числе численного интегрирования, дифференцирования и т.п.) является правило Рунге, заключающееся в последовательном увеличении (например, удвоении) числа узловых точек n и соответствующем уменьшении шага дискретизации h. Оценка по правилу Рунге основана на предположении, что искомую величину J можно представить в виде
, (2.4)
где J – точное значение,
Jh – приближенный результат, полученный при шаге дискретизации равном h,
c – коэффициент, который предполагается независящим от h,
k – порядок точности метода,
(h) - составляющая погрешности, которая считается пренебрежимо малой по сравнению с chk. В этом случае, уменьшив шаг дискретизации в два раза и отбросив (h), нетрудно найти c и оценку погрешности
, (2.5)
где J - точное, а Jh, Jh/2 - приближенные значения интегралов, полученные, соответственно, с шагом h и h/2, k - порядок точности метода.
Тогда при заданной точности величина h должна выбираться так, чтобы выполнялось условие
. (2.6)
Критерием допустимости отбрасывания малых величин можно считать стабильность величины K
, (2.7)
полученной при уменьшении h в 4, 8 и т.д. раз:
3 Оценка погрешностей, связанных с машинным представлением чисел
Вычислительные ошибки этого типа порождаются ограниченной разрядностью представления чисел в ЭВМ. Эти ошибки резко возрастают в ситуациях, близких к математическим неопределенностям типа 0/0, –, 0·.
Рассмотрим некоторое число A=0.235486897110p в машинном представлении с плавающей точкой
|
Знак числа |
Мантисса (M разрядов) |
Знак порядка |
Порядок |
||||||||
|
|
2 |
3 |
5 |
4 |
8 |
6 |
8 |
|
p |
||
|
9 |
7 |
1 |
Последние цифры (9,7,1), помещенные в нижней строке не умещаются в m разрядов и теряются. В худшем случае все потерянные цифры равны 9. Следовательно, предельная погрешность равна единице последнего разряда
.
Относительная предельная погрешность
. (2.8)
Здесь использовано правило записи числа в нормализованном виде: среди множества способов записи числа с плавающей точкой выбирается тот, при котором старшая значащая цифра располагается непосредственно за точкой (этим минимизируется объем памяти, необходимый для записи числа, так как не нужно хранить незначащие нули и позицию точки).
Отметим, что в машинном представлении используется двоичная система счисления, поэтому на самом деле
,
где M2 - количество двоичных разрядов в мантиссе. Здесь мы используем десятичную систему только для удобства восприятия.
При сложении и вычитании двух чисел AB производится выравнивание порядков операндов по большему:
|
A |
+ |
2 |
3 |
5 |
4 |
8 |
6 |
8 |
+ |
02 |
|
B |
+ |
3 |
8 |
9 |
5 |
9 |
7 |
3 |
|
01 |
B |
+ |
0 |
0 |
0 |
3 |
8 |
9 |
5 |
+ |
02 |
||
|
9 |
7 |
3 |
При этом последние разряды меньшего по порядку числа теряются и возникает погрешность, которая оценивается аналогично (2.8). Только необходимо помнить, что при оценке абсолютной погрешности число (2.8) нужно умножить на старшее по порядку число, участвующее в операции
. (2.9)
После выравнивания порядков производится операция, результат которой при сложении чисел одинакового знака может иметь мантиссу, превышающую единицу. При приведении числа к нормализованной форме производится сдвиг разрядов вправо. В результате возникает погрешность, которая может превысить (2.9). Поэтому общая погрешность операции оценивается следующим образом:
. (2.10)
Рассмотрим пример вычитания двух близких чисел:
|
A |
+ |
2 |
3 |
5 |
4 |
8 |
6 |
8 |
+ |
02 |
|
B |
+ |
2 |
3 |
5 |
4 |
8 |
5 |
6 |
+ |
02 |
=
|
AB |
+ |
0 |
0 |
0 |
0 |
0 |
1 |
2 |
+ |
02 |
Результат операции, преобразованный в нормализованную форму:
|
AB |
+ |
1 |
2 |
0 |
0 |
0 |
0 |
0 |
|
03 |
Пять нулей, записанные после цифр результата операции введены произвольно. Поскольку каждое число A и B могло быть усечено, то вместо нулей на самом деле могли бы стоять любые цифры, в том числе и девятки. Поэтому формула (2.9) дает реальную оценку и в этом случае.
Учитывая (2.10) найдем оценку относительной погрешности результата операции сложения и вычитания:
. (2.11)
Теперь рассмотрим квадратурные формулы типа (2.2):
(2.12)
(последнее равенство следует из того, что интеграл от функции f(x)=const должен вычисляться точно). Пусть
.
Тогда ошибка исходных данных (усечения значений функции) . Ошибка суммы приближенных значений
. (2.13)
При вычислении суммы накоплением возникает ситуация, описанная выше, когда складываются слагаемые разного порядка.
Оценка одного слагаемого суммы
.
Поэтому в соответствии с (2.9) ошибка округления при очередной операции сложения
.
а таких операций необходимо совершить n. Кроме того, в соответствии с (2.12) для приближенного вычисления интеграла сумму надо умножить на h. В связи с этим оценка погрешности округления
. (2.14)
Тогда, с учетом ошибок округления равенство (2.4) может принять вид
, (2.15)
причем последнее слагаемое обусловлено ограниченной разрядностью. Можно приближенно указать значения h и n, при которых оценка суммарной погрешности имеет минимальное значение. Для этого запишем общую оценку погрешности квадратурной формулы
,
и найдем минимум (h):
,
,
,
.
Таким образом, можно считать, что
, (2.16)
где M - эквивалентное количество десятичных знаков мантиссы (при расчетах с обычной точностью M7-8, с двойной точностью M16).
Поскольку наличие значительной погрешности округления мешает использованию оценки (1.4.8), то при расчетах приходится ограничиваться меньшими n и большими h, чем это следует из (2.16). Кроме того, существуют различные способы, чтобы ограничить возрастание погрешности, связанное с математическими неопределенностями.
Возможность контроля погрешности округления несколько облегчает то обстоятельство, что эта погрешность, в отличие от остальных типов погреш ностей, как правило, ведет себя достаточно хаотично, и по уровню этой хаотической составляющей можно судить, хотя и очень приближенно, о ее величине.
4 Пример
В приведенных ниже таблицах показаны результаты численного интегрирования функции f(x)=6x5 на интервале [0,1] методом парабол (точное значение интеграла равно 1). Величины K и Рунге получены по формулам (2.7) и (2.6), теор – по (2.3) с учетом данных табл. 2.1, точное равно разности между точным и приближенным значением. Результаты, приведенные в таблице 2.2, получены путем вычисления с двойной точностью (мантисса 16 десятичных знаков), в таблице 2.3 – с одинарной точностью (мантисса 7-8 знаков). Из таблиц видно, что в данном случае коэффициент уменьшения погрешности K весьма стабилен до значений n примерно равных n0 (2.16). Кроме того, видно, что при этих n оценка по Рунге Рунге практически совпадает с точное, в то время как оценка через производную теор превышает их в два раза.
Таблица 2.2
|
n |
K |
точное |
Рунге |
теор |
|
1 |
– |
-1.2500×10-1 |
– |
2.5000×10-1 |
|
2 |
– |
-7.8125×10-3 |
-7.8125×10-3 |
1.5625×10-2 |
|
4 |
16.0 |
-4.8828×10-4 |
-4.8828×10-4 |
9.7656×10-4 |
|
8 |
16.0 |
-3.0518×10-5 |
-3.0518×10-5 |
6.1035×10-5 |
|
16 |
16.0 |
-1.9073×10-6 |
-1.9073×10-6 |
3.8147×10-6 |
|
32 |
16.0 |
-1.1921×10-7 |
-1.1921×10-7 |
2.3842×10-7 |
|
64 |
16.0 |
-7.4506×10-9 |
-7.4506×10-9 |
1.4901×10-8 |
|
128 |
16.0 |
-4.6566×10-10 |
-4.6566×10-10 |
9.3132×10-10 |
|
256 |
16.0 |
-2.9104×10-11 |
-2.9104×10-11 |
5.8208×10-11 |
|
512 |
16.0 |
-1.8190×10-12 |
-1.8190×10-12 |
3.6380×10-12 |
|
1024 |
16.0 |
-1.1366×10-13 |
-1.1369×10-13 |
2.2737×10-13 |
|
2048 |
16.1 |
-7.2997×10-15 |
-7.0906×10-15 |
1.4211×10-14 |
|
4096 |
13.9 |
3.6082×10-16 |
-5.0823×10-16 |
8.8818×10-16 |
|
8192 |
-68.7 |
2.4980×10-16 |
7.4015×10-18 |
5.5511×10-17 |
|
16384 |
0.2 |
-1.9429×10-16 |
3.2078×10-17 |
3.4694×10-18 |
|
32768 |
2.6 |
-4.1633×10-16 |
1.2338×10-17 |
2.1684×10-19 |
|
65536 |
0.1 |
-1.7486×10-15 |
8.6353×10-17 |
1.3553×10-20 |
Таблица 2.3
|
n |
K |
точное |
Рунге |
теор |
|
1 |
– |
-1.2500×10-1 |
– |
2.5000×10-1 |
|
2 |
– |
-7.8125×10-3 |
-7.8125×10-3 |
1.5625×10-2 |
|
4 |
16.0 |
-4.8828×10-4 |
-4.8828×10-4 |
9.7656×10-4 |
|
8 |
16.0 |
-3.0518×10-5 |
-3.0518×10-5 |
6.1035×10-5 |
|
16 |
16.0 |
-1.9073×10-6 |
-1.9073×10-6 |
3.8147×10-6 |
|
32 |
16.0 |
-1.1921×10-7 |
-1.1921×10-7 |
2.3842×10-7 |
|
64 |
45.0 |
-1.1921×10-7 |
-2.6491×10-9 |
1.4901×10-8 |
|
128 |
0.2 |
1.1921×10-7 |
-1.4570×10-8 |
9.3132×10-10 |
|
256 |
2.2 |
2.3842×10-7 |
-6.6227×10-9 |
5.8208×10-11 |
5 Порядок выполнения работы
1. По указанию преподавателя выбрать один из методов численного интегрирования функций.
2. Разработать алгоритм и программу вычисления интеграла выбранным методом с заданной точностью (=10-6). Предусмотреть оценку точности по правилу Рунге.
3. В качестве отладочного примера выбрать функцию f(x)=xm, где m=4,5,6,... и отрезок интегрирования [0,2]. Найти точное значение интеграла и распечатать его с необходимым числом знаков.
Распечатать результаты приближенного счета со всеми значениями, начиная с n=2 и их погрешность (разницу с точным значением) и оценки погрешности по правилу Рунге и по формуле (2.3). Результаты представить в виде таблиц 2.2 и 2.3.
4. Проинтегрировать численно функцию на отрезках [0, 1.5] и [0.001, 1.5], где m - номер по списку группы.
5. Объяснить результаты.
6 Требования к отчету
В отчете представить:
-пояснение сути метода;
-оценку и обоснование оценки погрешностей метода, округления и погрешности, вызванной неточностью исходных данных;
-объяснение результатов п.3 и 4.
Лабораторная работа №3
МЕТОД ГРАДИЕНТНОГО СПУСКА
1 Цель работы
Ознакомление с методами поиска экстремума нелинейной выпуклой функции нескольких переменных и решение таких задач с помощью ЭВМ.
2 Описание метода
Задача состоит в отыскании минимума функции двух переменных f(x,y) (следует отметить, что если необходимо найти максимум некоторой функции F(x,y), то эта задача сводится к поиску минимума функции f(x,y)=F(x,y) ).
Большинство численных методов состоит в отыскании некоторой последовательности (x0,y0), (x1,y1),..,(xk,yk), которая при k (или при kkM) сходится к точке минимума (x*,y*). Если при этом выполняется f(x0,y0)>f(x1,y1)>..>f(xk,yk), то есть значения функции монотонно убывают при увеличении k, то такой метод называется методом спуска.
Известно, что вектор градиента функции
направлен в сторону наибольшего возрастания функции f(x,y). Поэтому в качестве направления движения можно принять противоположное градиенту направление (антиградиент), т.е. координаты точек пересчитываются по формулам
(5.1)
Выбор величины k, с которой связана длина k-го шага, в общем случае является сложной задачей. Если k мало, то движение будет слишком медленным и потребует значительного объема вычислений. Если k велико, то существует возможность перескочить точку минимума и выйти на противоположный склон функции. При этом возможно нарушение требования монотонного убывания последовательности f(xk,yk) и появляется опасность зацикливания, то есть колебания последовательности (xk,yk) в некоторой окрестности точки минимума (x*,y*) без приближения к ней.
Существует несколько различных способов выбора k. В данной работе рассматривается разновидность метода с дроблением шага. Для этого задается начальное приближение (x0,y0) и начальное значение 0 (например, x0=y0=0, 0=1). Вычисление x1,y1 и всех последующих xk+1,yk+1 производится по формуле (5.1). При этом если окажется, что f(xk+1,yk+1)>f(xk,yk), то величина k уменьшается в два раза и вычисление xk+1,yk+1 повторяется от точки (xk,yk) с новым значением k. Если же значение функции убывает, то величина k=k1.
Критерием окончания счета принимается неравенство
(5.2)
либо одновременное выполнение двух неравенств
, (5.3)
3 Порядок выполнения работы на ПЭВМ
Задать входные данные согласно номеру варианта.
Провести вычисления на ЭВМ.
Написать отчет, который должен содержать результаты пунктов 1-3, а также комментарий хода вычислений с объяснениями результатов.
4 Варианты заданий
Минимизировать функцию методом градиентного спуска с точностью до =10-4. Коэффициенты выбрать из таблицы 5.1. Представить два варианта расчета: с коэффициентами из верхней и нижней частей таблицы. Объяснить разницу в работе алгоритма.
Таблица 5.1
|
Вари- ант |
a |
b |
c |
d |
|
1 |
1 |
-1.4 |
0.01 |
0.11 |
|
2 |
2 |
-1.3 |
0.04 |
0.12 |
|
3 |
3 |
-1.2 |
0.02 |
0.13 |
|
4 |
4 |
-1.1 |
0.16 |
0.14 |
|
5 |
5 |
-1.0 |
0.25 |
0.15 |
|
6 |
6 |
-0.9 |
0.36 |
0.16 |
|
7 |
7 |
-0.8 |
0.49 |
0.17 |
|
8 |
8 |
-0.7 |
0.64 |
0.18 |
|
9 |
9 |
-0.6 |
0.80 |
0.19 |
|
10 |
10 |
-0.5 |
0.94 |
0.20 |
|
11 |
11 |
-0.4 |
1.00 |
0.21 |
|
12 |
12 |
-0.3 |
1.21 |
0.22 |
|
13 |
13 |
-0.2 |
1.44 |
0.23 |
|
14 |
14 |
-0.1 |
1.69 |
0.24 |
|
15 |
15 |
0.0 |
1.96 |
0.25 |
|
16 |
16 |
0.1 |
1.99 |
0.26 |
|
17 |
17 |
0.2 |
2.56 |
0.27 |
|
18 |
18 |
0.3 |
2.89 |
0.28 |
|
19 |
19 |
0.4 |
3.24 |
0.29 |
|
20 |
20 |
0.5 |
3.81 |
0.30 |
|
21 |
21 |
0.6 |
4.00 |
0.31 |
|
22 |
22 |
0.7 |
5.02 |
0.32 |
|
23 |
23 |
0.8 |
4.84 |
0.33 |
|
24 |
24 |
0.9 |
5.29 |
0.34 |
|
25 |
25 |
1.0 |
5.76 |
0.35 |
|
26 |
26 |
1.1 |
7.25 |
0.36 |
|
27 |
27 |
1.2 |
6.76 |
0.37 |
|
28 |
28 |
1.3 |
5.98 |
0.38 |
|
29 |
29 |
1.4 |
7.29 |
0.39 |
|
30 |
30 |
1.5 |
8.41 |
0.40 |