Кафедра информатики и вычислительной техники

Стр 1 из 4Следующая ⇒

Кафедра информатики и вычислительной техники

С. А. Лысенкова

Н. Б. Назина

ЧИСЛЕННЫЕ МЕТОДЫ

Учебно-методическое пособие

Сургут

Издательский центр СурГУ

УДК 519.6(072)

ББК 22.193я73

Л-886

Печатается по решению

редакционно-издательского совета СурГУ

Рецензент: Назин А.Г. – к.ф.-м.н., доцент кафедры

прикладная математика

Лысенкова С. А.

Численные методы: учебно-методическое пособие / С. А. Лысенкова, Н. Б. Назина; Сургут. Гос. Ун-т ХМАО – Югры. – Сургут: ИЦ СурГУ, 2014. – 53 с.

Приведена теория и формулы по темам «Элементы теории погрешностей», «Численные методы решения нелинейных уравнений», «Численные методы решения систем линейных алгебраических уравнений», «Аппроксимация экспериментальных данных», «Численное интегрирование», «Численное решение дифференциальных уравнений», «Линейное программирование».

Рассмотрены способы реализации средствами Excel.

Предназначено для студентов первого курса Политехнического института изучающих дисциплину «Информатика».

УДК 519.6(072)

ББК 22.193я73

Л-886

составление, 2014

ОГЛАВЛЕНИЕ

ЭЛЕМЕНТЫ ТЕОРИИ ПОГРЕШНОСТЕЙ.. 3

АБСОЛЮТНАЯ И ОТНОСИТЕЛЬНАЯ ПОГРЕШНОСТИ.. 4

Численные методы решения нелинейных уравнений.. 7

Способы отделения корней уравнений.. 7

Решение нелинейных уравнений методами бисекций и хорд 11

Решение нелинейных уравнений методом ньютона и комбинированным методом 14

Решение нелинейных уравнений методом простых итераций 17

Численные методы решения систем линейных уравнений 19

Решение систем линейных уравнений методом простых итераций методом зейделя 19

аппроксимация экспериментальных данных.. 23

аппроксимация методом наименьших квадратов.. 23

численное интегрирование.. 27

приближенное решение определенных интегралов.. 27

численное решение дифференциальных уравнений.. 33

приближенное решение обыкновенных дифференциальных уравнений 33

линейное программирование.. 38

Литература.. 41

Приложения.. 42

ЭЛЕМЕНТЫ ТЕОРИИ ПОГРЕШНОСТЕЙ

АБСОЛЮТНАЯ И ОТНОСИТЕЛЬНАЯ ПОГРЕШНОСТИ

Пусть – точное значение, – приближенное значение некоторого числа.

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

Довольно часто точное значение неизвестно, поэтому вместо абсолютной погрешности используют понятие границы абсолютной погрешности:

Число называется предельной абсолютной погрешностью, оно равно или превышает значение абсолютной погрешности.

Основной характеристикой точности числа является относительная погрешность.

Относительная погрешность – это отношение абсолютной погрешности к приближенному значению числа:

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

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

где – предельная абсолютная погрешность числа .

Пример: Известно, что где

Найти , , ,

Для оценки предельной абсолютной погрешности воспользуемся формулой:

Рис. 1. Вид экрана для вычисления абсолютной и относительной погрешностей

Исходные данные вводятся в блок А1: B6 (рис. 1). В ячейки С1: С6 вводятся формулы для вычисления частных производных искомой функции. В ячейку Е8 записывается формула . Модуль вводится с использованием функции =abs().

В ячейках D1: E6 рассчитываются верхние и нижние оценки значений переменных по формулам (аналогично для других переменных).

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

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

В ячейку Е10 записывается формула для вычисления относительной погрешности

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

Полученную формулу записывают в ячейку Е11. Найденная относительная погрешность не должна превышать значение предельной относительной погрешности, т.е.

Задания для самостоятельного выполнения.

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

Контрольные вопросы

1. Как записать основные математические функции в Excel.

2. Сформулируйте определение абсолютной и относительной погрешностей.

3. Запишите формулы для вычисления предельной абсолютной и предельной относительной погрешностей.

4. Основные правила вычисления абсолютной и относительной погрешностей.

Рис. 2. Таблица функции

Рис. 3. График функции

Теорема 1 (Теорема Больцано-Коши). Если непрерывная на отрезке функция на концах указанного отрезка принимает значения разных знаков, т.е. то на интервале она хотя бы один раз обращается в нуль.

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

Пример 2: Выполнить отделение корней уравнения аналитическим методом.

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

Шаг табулирования выбираем произвольно, т.о. заполняем ячейки А1: С2 (рис. 4). Далее в ячейку А5 записываем ссылку на ячейку А1, в ячейку А6 записываем формулу, см. рисунок 5. С помощью маркера автозаполнения в первом столбце производим дальнейшие вычисления.

Заполняем столбец B5: B17, для этого в ячейку B5 записываем формулу вычисления функции и протягиваем ее вниз.

Рис. 4. Вид экрана для аналитического метода отделения корней

Рис. 5. Формула для заполнения ячейки А6

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

В столбцах D и E записываются формулы для вычисления первой и второй производных данной функции.

Рис. 6. Формула для заполнения ячейки С6

В итоге видим, что найдены два отрезка, содержащие только один корень. Убедитесь в справедливости теоремы 2 для данных отрезков самостоятельно.

Задания для самостоятельного выполнения.

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

Контрольные вопросы

1. Как записать основные математические функции в Excel.

2. Сформулируйте алгоритм графического метода отделения корней.

3. Сформулируйте теорему 1 и теорему 2. В чем их отличия и сходства.

4. Сформулируйте алгоритм аналитического метода отделения корней.

Рис. 7. Вид экрана для метода бисекций

В ячейку G5 записывается формула оценки погрешности (рис. 8).

Рис. 8. Формула для заполнения ячейки G5

В ячейке А6 выбирается одно из значений или , для которого выполняется условие теоремы 2 (рис. 9). Аналогичная формула записывается в ячейке В6.

Все остальные ячейки заполняются с помощью маркера автозаполнения до тех пор, пока не появится надпись «корень=» в столбце G.

Рис. 9. Формула для заполнения ячейки А6

Метод хорд. Отрезок делится точкой и далее рассматриваются два отрезка: и . Затем выбирается один из них, для которого выполняется условие теоремы 2, выбранный отрезок переобозначается и снова делится. Получаем систему вложенных отрезков.

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

Пример 2: Найти корень уравнения методом хорд с точностью

Используем шаблон для вычисления корня методом бисекций (рис. 10). Вносим изменения в ячейку С5, записываем формулу (точка пересечения хорды с осью Ох) и протягиваем ее вниз. В ячейку G6 записываем формулу оценки погрешности и поиска корня, а ячейку G5 оставляем пустой. С помощью маркера автозаполнения находим ответ.

Рис. 10. Вид экрана для метода хорд

Задания для самостоятельного выполнения.

Из таблицы 2 приложения взять исходные данные своего варианта. Вариант определяется по порядковому номеру в списке группы. Найти корни уравнения методом бисекций и методом хорд для всех отрезков, содержащих единственный корень.

Контрольные вопросы

1. Метод бисекций решения нелинейных уравнений.

2. Графическая реализация метода бисекций.

3. Метод хорд решения нелинейных уравнений.

4. Графическая реализация метода хорд.

Рис. 11. Вид экрана для метода Ньютона (касательных)

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

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

Пусть, например, тогда итерационные формулы будут выглядеть следующим образом:

Если итерационные формулы примут вид:

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

Геометрическая интерпретация – построение касательных и хорд на каждом шаге итераций и нахождение их точек пересечения с осью Ох.

Пример 2: Найти корень уравнения комбинированным методом касательных и хорд с точностью

Выбираем один из найденных отрезков, содержащих только один корень.

Для каждого из концов отрезка проверяем условие . В нашем случае это точка .

Для вычисления корня комбинированным методом (рис. 12) в ячейки А5, В5 записываем относительные ссылки на исходные концевые точки отрезка, далее находим значение данной функции в этих точках С5, D5. В ячейку Е5, записываем формулу производной функции и аргументом будет В ячейку F6 записываем формулу оценки погрешности и поиска корня.

В ячейки А6, В6 записываем формулы, с аргументами из пятой строки:

(ячейка А6 ), (ячейка B6 ).

С помощью маркера автозаполнения находим ответ.

Рис. 12. Вид экрана для комбинированного метода

Задания для самостоятельного выполнения.

Из таблицы 2 приложения взять исходные данные своего варианта. Вариант определяется по порядковому номеру в списке группы. Найти корни уравнения методом касательных и комбинированным методом для всех отрезков, содержащих единственный корень.

Контрольные вопросы

1. Метод Ньютона решения нелинейных уравнений.

2. Графическая реализация метода Ньютона.

3. Комбинированный метод решения нелинейных уравнений.

4. Графическая реализация комбинированного метода.

Рис. 13. Вид экрана для метода простых итераций

В ячейку А2, В2 (рис. 13) записываем исходные данные. В ячейки С2, D2 ввести формулы вычисления производных данной функции. Формула для заполнения ячейки E2 (рис.14). Формула для заполнения ячейки C5 (рис.15). Формула для заполнения ячейки B8 (рис.16). В ячейку А9 устанавливаем ссылку на В8.

Рис. 14. Формула для заполнения ячейки E2

Рис. 15. Формула для заполнения ячейки C5

Рис. 16. Формула для заполнения ячейки B8

Задания для самостоятельного выполнения.

Из таблицы 2 приложения взять исходные данные своего варианта. Вариант определяется по порядковому номеру в списке группы. Найти корни уравнения методом простых итераций для всех отрезков, содержащих единственный корень.

Контрольные вопросы

1. Метод простых итераций решения нелинейных уравнений.

2. Сравните метод простых итераций с другими методами.

Рис. 17. Вид экрана для метода простых итераций

Рис. 18. Формула для заполнения ячейки А8

Заполнить блок вычисления (рис. 19), далее заполняем ячейки G8, H8 (рис. 20-21).

Рис. 19. Формула для заполнения ячейки D8

Рис. 20. Формула для заполнения ячейки G8

Рис. 21. Формула для заполнения ячейки H8

Протянуть восьмую строку до тех пор, пока в ячейке H8 не появится надпись “стоп”.

Метод Зейделя. В отличии от метода простых итераций в методе Зейделя есть изменения во второй и третьей итерационных формулах:

Данное изменение позволяет ускорить сходимость итерационного процесса.

Пример 2: Решить систему линейных уравнений

методом Зейделя с точностью

Скопировать метод простых итераций и в ячейки В17, С17 внести изменения в соответствии с формулами метода Зейделя (рис. 22).

Рис. 22. Вид экрана для метода Зейделя

Рис. 23. Проверка методом обратной матрицы

Выполнить проверку решения системы линейных уравнений методом обратной матрицы (рис. 23).

Задания для самостоятельного выполнения.

Из таблицы 3 приложения взять исходные данные своего варианта. Вариант определяется по порядковому номеру в списке группы. Предварительно проверить выполнение условия доминирования диагональных элементов. Если данное условие не выполняется, преобразовать систему линейных уравнений с помощью элементарных эквивалентных преобразований. Найти решение системы линейных уравнений методом простых итераций и методом Зейделя. Выполнить проверку решения методом обратной матрицы.

Контрольные вопросы

1. Метод простых итераций решения систем линейных уравнений.

2. Метод Зейделя решения систем линейных уравнений.

3. Достаточное условие для применений указанных методов.

Рис. 24. Графическое представление исходных данных

Полученная функция аппроксимации исходных данных имеет вид .

Рис. 25. Вид экрана при аппроксимации линейной функцией

Пример 2: Аппроксимировать методом наименьших квадратов функцию, заданную таблично:

	0, 23	0, 57	0, 94	1, 48	2, 03
	1, 45	0, 99	0, 65	0, 73	1, 3

Изобразим исходные данные графически (рис. 26), видно, что расположение точек напоминает параболу, поэтому для аппроксимации используем квадратичную функцию (рис. 27).

Рис. 26. Графическое представление исходных данных

Рис. 27. Вид экрана при аппроксимации квадратичной функцией

Полученная функция аппроксимации исходных данных имеет вид .

Задания для самостоятельного выполнения.

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

Контрольные вопросы

1. Аппроксимация функций методом наименьших квадратов.

2. Формулы линейной аппроксимации метода наименьших квадратов.

3. Формулы квадратичной аппроксимации метода наименьших квадратов.

Численное интегрирование

Рис. 28. Численное интегрирование по формулам прямоугольников

Заполнить блок А6: С16 самостоятельно.

Для заполнения ячейки D6 используется формула =$D$2*C6. Для заполнения ячейки D7 используется формула =$D$2*C7+D6, далее она протягивается вниз и заполняем весь столбец D.

Для заполнения ячейки Е6 используется формула (рис. 29).

Для заполнения ячейки F6 используется формула (рис. 30).

Рис. 29. Формула для заполнения ячейки Е6

Рис. 30. Формула для заполнения ячейки F6

Далее они протягиваются вниз и заполняют столбцы E и F.

Заполнить блок G6: I15 самостоятельно.

Для заполнения ячейки J6 используется формула (рис. 31). Далее она протягивается вниз и заполняет столбец J.

Рис. 31. Формула для заполнения ячейки J6

Выполняем вычисление определенного интеграла для

Оценку точности рассмотрим на примере формулы центральных прямоугольников.

Формула трапеций. Площадь каждой элементарной криволинейной трапеции можно приближенно вычислить как площадь трапеции, получим формулу трапеций:

где

Очевидно, что чем больше тем точнее будет найдено значение интеграла.

Пример 2: Вычислить определенный интеграл используя формулу трапеций. Обеспечить точность вычисления

Вводим отрезок интегрирования (рис. 32), ( С2 ), ( D2 ). Вычисляем значения подынтегральной функции на концах отрезка ( B4, C4 ).

Рис. 32. Численное интегрирование по формуле трапеций

Заполнить ячейку D4 и блок А6: C16 самостоятельно.

Для заполнения ячейки Е6 используется формула (рис. 33). Далее она протягивается вниз и заполняет весь столбец E.

Рис. 33. Формула для заполнения ячейки E6

Выполняем вычисление определенного интеграла для

Формула Симпсона. Разобьем отрезок интегрирования на четное число элементарных отрезков точками

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

где

Очевидно, что чем больше тем точнее будет найдено значение интеграла.

Пример 3: Вычислить определенный интеграл используя формулу Симпсона. Обеспечить точность вычисления

Вводим отрезок интегрирования , ( С2 ), заполняем ячейку D2 (рис. 33). Вычисляем значения подынтегральной функции на конце отрезка ( C4 ).

Рис. 33. Формула для заполнения ячейки E6

Заполнить блок А6: C16 самостоятельно.

Для заполнения ячейки D6 используется формула =C6. Для заполнения ячейки D7 используется формула =ЕСЛИ(ОСТАТ(A7; 2)=0; D6+2*C7; D6+4*C7), далее она протягивается вниз и заполняем весь столбец D (рис. 34).

Для заполнения ячейки Е6 используется формула (рис. 35). Далее она протягивается вниз и заполняет весь столбец E.

Рис. 34. Численное интегрирование по формуле Симпсона

Рис. 35. Формула для заполнения ячейки E6

Выполняем вычисление определенного интеграла для

Задания для самостоятельного выполнения.

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

Контрольные вопросы

1. Формулы прямоугольников.

2. Погрешность формул численного интегрирования

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

4. Формула Симпсона.

Рис. 36. Численное решение дифференциального уравнения методом Эйлера

Вводим отрезок , начальное условие ( С2 ), ( D2 ), ( E2 ) (рис. 36).

Вычисляем блок А5: А15 самостоятельно. Для заполнения ячейки В5 используется формула =C2. Для заполнения ячейки В6 используется формула =B5+$E$2*(2*A5^3-B5^2), далее она протягивается вниз и заполняем весь столбец В.

Выполняем решение дифференциального уравнения методом Эйлера при

Исправленный метод Эйлера. Решение обыкновенного дифференциального уравнения при заданном начальном условии можно определить по итерационной формуле исправленного метода Эйлера:

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

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

Вводим отрезок , начальное условие ( С2 ), ( D2 ), ( E2 ) (рис. 37).

Вычисляем блок А5: А15 самостоятельно.

Для заполнения ячейки В5 используется формула =C2. Для заполнения ячейки С5 используется формула =2*A5^3-B5^2. Далее заполняем ячейки D5: F5 по формулам (рис. 37).

Для заполнения ячейки В6 используется формула =B5+$E$2*(C5+F5)/2. Далее она протягивается вниз и заполняет весь столбец В, также протягиваем остальные столбцы.

Выполняем решение дифференциального уравнения исправленным методом Эйлера при

Установить, обеспечена ли требуемая точность.

Рис. 37. Численное решение дифференциального уравнения исправленным методом Эйлера

Метод Рунге-Кутта. Данный метод используется чаще остальных при решении практических задач.

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

где

Пример 3: Найти решение дифференциального уравнения на отрезке при начальном условии используя метод Рунге-Кутта. Обеспечить точность вычисления

Вводим отрезок , начальное условие ( С2 ), ( D2 ), ( E2 ) (рис. 38).

Вычисляем блок А5: А15 самостоятельно.

Для заполнения ячейки В5 используется формула =C2. Для заполнения ячейки С5 используется формула =2*A5^3-B5^2. Далее заполняем ячейки D5: K5 по формулам (см. рис. 38). Обращаем внимание, что ссылки на значение должны быть абсолютными.

Для заполнения ячейки В6 используется формула =B5+$E$2*(C5+2*F5+2*H5+K5)/6. Далее она протягивается вниз и заполняет весь столбец В, также протягиваем остальные столбцы справа.

Рис. 38. Численное решение дифференциального уравнения методом Рунге-Кутта

Выполняем решение дифференциального уравнения методом Рунге-Кутта при

Установить, обеспечена ли требуемая точность.

Задания для самостоятельного выполнения.

Из таблицы 6 приложения взять исходные данные своего варианта. Вариант определяется по порядковому номеру в списке группы. Выполнить численное решение дифференциального уравнения методом Эйлера, исправленным методом Эйлера и методом Рунге-Кутта. Обеспечить точность вычисления

Контрольные вопросы

1. Итерационная формула метода Эйлера и его геометрический смысл.

2. Погрешность формул численного решения дифференциальных уравнений.

3. Итерационная формула исправленного метода Эйлера и его геометрический смысл.

4. Итерационная формула метода Рунге-Кутта.

Линейное программирование

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

В линейном программировании решаются такие задачи как оптимальное управление производством; оптимальное составление смеси; оптимальное распределение ресурсов; транспортные задачи и др.

Требуется определить максимум или минимум функции при следующих ограничениях:

Пример: Рассмотрим задачу об оптимальном распределении ресурсов.

Для производства двух видов изделия А и В предприятие использует три вида сырья. Нормы расхода сырья каждого вида на изготовление единицы продукции представлены ниже. Требуется составить план выпуска изделий А и В, при котором прибыль от их реализации максимальна.

Виды сырья	Нормы расхода на одно изделие	Общее количество сырья
А	В
I
II
III
Прибыль

Составим математическую модель задачи.

Пусть – количество изделий вида А, – количество изделий вида В. Тогда

Система ограничений имеет вид:

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

12 3 4 Следующая ⇒