1 Теория и практика программирования задач на ЭВМ. - презентация

1 1 Теория и практика программирования задач на ЭВМ

2 2 Содержание курса Введение в численные методы Методы решения СЛАУ Исчисление конечных разностей Задача интерполяции Интерполяционный многочлен Лагранжа Интерполяционный многочлен Ньютона Сплайн-интерполяция Метод наименьших квадратов Численное дифференцирование Численное интегрирование: Методы прямоугольника Метод трапеции Метод парабол (метод Симпсона) Введение в Matlab Примеры программной реализации

3 3 Список литературы 1. Формалев В.Ф., Ревизников Д.Л. Численные методы. – М.: ФИЗМАТЛИТ, Руководство MATLAB 3. А.А.Самарский, А.В.Гулин. Численные методы М.: Наука, А.А.Самарский. Введение в численные методы М.: Наука, Петров И.Б., Лобанов А.И. Введение в вычислительную математику.

4 4 Введение в численные методы Первое применение вычислительных методов принадлежит древним египтянам, которые умели вычислять диагональ квадрата за конечное количество действий. Они также могли находить квадратный корень из 2, скорее всего, с помощью алгоритма, в дальнейшем получившего название формулы Герона, а еще позднее метода Ньютона: u k+1 =1/2(u k +2/u k ), u 0 =a Пример. Решается задача Коши для обыкновенного дифференциального уравнения 2-го порядка: u''(t) = u(t), u(0) = 1, u'(0) = - 1. Общее решение имеет вид u(t) = 0,5[u(0) + u'(0)]e t + 0,5[u(0) - u'(0)]e - t. При заданных начальных данных точное решение задачи: u(x) = e -t, однако малая погрешность δ в их задании приведет к появлению члена δe -t, который при больших значениях аргумента может существенно исказить решение.

5 5 Определение: Погрешность измерения оценка отклонения измеренного значения величины от её истинного значения. Погрешность измерения является характеристикой (мерой) точности измерения.

6 6 Определение: Абсолютная погрешность измерения (англ. absolute error of a measurement) – погрешность измерения, выраженная в единицах измеряемой величины.

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

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

9 9 Численное решение систем линейных алгебраических уравнений Пусть дана система линейных алгебраических уравнений (СЛАУ): После (n-1)-го шага алгоритма Гаусса получаем следующую расширенную матрицу с контрольными суммами, содержащую верхнюю треугольную матрицу СЛАУ

10 10 Пример. Методом Гаусса решить СЛАУ:

11 11 Теория приближений (1)

12 12 Исчисление конечных разностей

13 13 Задача интерполяции

14 14 Интерполяционный многочлен Лагранжа

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

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

17 17 Кубический сплайн

18 18 Метод наименьших квадратов

19 19 Численное дифференцирование

20 20

21 21 Численное интегрирование Впервые разработал И. Ньютон. Численное интегрирование основано на том, что функция заменяется интерполяционным многочленом: F(x)=Р(х) Р(х)=a 0 +a 1 x 1 +a 2 x 2 +…+a n x n (строится по точкам, то есть P(x i )=F(x i )

22 22 Применение численных методов Т.к. не все функции интегрируются аналитическими способами, то приходится применять численные методы. Функция y=F(x) заменяется интерполяционным многочленом P(x), который в точках x i равен значению функции P(x i )=F(x i )

23 23 Геометрическая интерпретация Интеграл – площадь криволинейной (подынтегральной) трапеции, одной из боковых сторон которой является кривая У= F(x) a b x у

24 24 Методы интегрирования В зависимости от степени интерполяционного многочлена выбираются различные методы интегрирования, в частности Методы прямоугольника 1. Слева 2. Справа Метод трапеции Метод парабол (метод Симпсона)

25 25 Метод прямоугольника Для методов прямоугольника выбирается интерполяционный многочлен 0-порядка Р(х)=a 0

26 26 Метод прямоугольника слева Р(х 0 )=у 0 Для метода прямоугольника слева интерполяционный многочлен Р(х i )=у i x y x0x0 ab x1x1 x2x2 xnxn у 1 у 1 у 0 у 0 у 2 у 2

27 27 Метод прямоугольника слева x y x0x0 ab x1x1 x2x2 xnxn у 1 у 1 у 0 у 0 у 2 у 2

28 28 Метод прямоугольника слева На отрезке [a, b] интеграл будет равен площади n-прямоугольников Интеграл слева вычисляется по формуле:

29 29 R n - погрешность где R n - погрешность, которая вычисляется по формуле:

30 30 Метод прямоугольника справа Р(х 0 )=у 1 Для метода прямоугольника справа интерполяционный многочлен Р(х i )=у i+1 x y x0x0 ab x1x1 x2x2 xnxn y1y1 y2y2 ynyn

31 31 Метод прямоугольника слева x y x0x0 ab x1x1 x2x2 xnxn y1y1 y2y2 ynyn

32 32 Метод прямоугольника справа На отрезке [a, b] интеграл будет равен площади n-прямоугольников: Интеграл справа вычисляется по формуле:

33 33 R n - погрешность где R n - погрешность, которая вычисляется по формуле:

34 34 Метод трапеций x y x0x0 ab x1x1 x2x2 xnxn

35 35 Метод трапеций Для метода трапеций выбирается интерполяционный многочлен 1-порядка F(x)=P(x) =a 0 +а 1 х и нам известно, что F(x 0 )=y 0, F(x 1 )=y 1 Построим интерполяционный многочлен

36 36

37 37 Интеграл по методу трапеции Таким образом, интеграл, вычисляемый по методу трапеции на отрезке [a, b] равен: x y b

38 38 Rn – погрешность где Rn – погрешность для метода трапеций, вычисляемая по формуле:

39 39 Метод Симпсона (парабол). у 2 у 2 у 0 у 0 у 1 у 1 x y x0x0 ab x1x1 x2x2 xnxn

40 40 Метод Симпсона (парабол) Для этого метода промежуток разбиваем на чётное количество частей и считаем, что нам известны 3 точки: y 0 =F(x 0 ) y 1 =F(x 1 ) y 2 =F(x 2 ) у 2 у 2 у 0 у 0 у 1 у 1 x y x0x0 ab x1x1 x2x2 xnxn

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

42 42 Метод Симпсона (парабол) Убедимся в том, что P(x 2 )=F(x 2 ): Заметим, что x 2 =x 0 +2h P(x)=y 0 +2y 1 -2y 0 +y 2 -2y 1 +y 0 =y 2

43 43 Метод Симпсона (парабол) На отрезке [x0, x0+2h] интеграл вычисляется по формуле:

44 44 Интеграл для метода Симпсона на отрезке [a, b] вычисляется по формуле:

45 45 Rn – погрешность где Rn – погрешность, вычисляемая по формуле:

46 46

47 47 Работа с матрицами в среде MatLab

48 48

49 49 Оператор двоеточия

50 50 Автоматическое создание матриц zeros – нулевая матрица rand – двумерное равномерное распределение randn – двумерное нормальное распределение ones- матрица, состоящая из единиц

51 51 Удаление строк и столбцов

52 52 Команда format

53 53 Выражения Переменные Числа Операторы функции

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

55 55 Метод наименьших квадратов

56 56 Кубическая интерполяция

57 57 Метод Симпсона #include using namespace std; double FX(double x){ return x+exp(x); } void main(){ double a,b; couta>>b; cout

58 58 Метод прямоугольников double f(double x){ return sin(x); } double rectangle_integrate(double a, double b, int n, double (*f)(double) ){ double result, h; int i; h = (b-a)/n; result = 0.0; for(i=1; i

59 59 Метод трапеций double INTEGR(double x){ return x*exp(x)+log(x)+1;} double trapez(double left, double right, double h){ double sum = 0; double runner; for(runner = left + h; runner < right; runner += h) sum += INTEGR(runner); sum = (sum + 0.5*(INTEGR(left) + INTEGR(right))) * h; return sum;} int main(int argc, char ** argv){ char c; double a, b; double h; printf("vvedit nizniy mezu integr : "); scanf("%lf",&a); printf("vvedit verhniy mezu integr : "); scanf("%lf",&b); printf("Enter integration step : "); scanf("%lf",&h); double trap = trapez(a, b, h); printf("vidpovid za metodom trapezii %10.10f.\n", trap); scanf("%c",&c);scanf("%c",&c); return 0; } Ответ: MATLAB x=1:0.1:5; y=x.*exp(x)+log(x)+1; trapz(x,y) ans =