скачать ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ Томский государственный педагогический университет (ТГПУ) Физико-математический факультет «УТВЕРЖДАЮ» Декан физико-математического факультета ________________А.Н. Макаренко «___»____________200__г. ПРОГРАММА ДИСЦИПЛИНЫ ДПП.Ф.07 «Численные методы» Специальность 030100 (050202.65) Информатика Квалификация - учитель информатики ^ Курс «Численные методы» является одним из фундаментальных разделов вычислительной математики, который посвящен разработке методов и алгоритмов решения типовых математических задач, возникающих при исследованиях математических моделей. Программа предназначена для построения курса лекционных и лабораторных занятий для студентов специальности Информатика (квалификация – учитель информатики). В программу входят следующие темы дисциплины: теория погрешностей, методы решения нелинейного уравнения, методы решения систем уравнений, численная интерполяция, методы наилучшего приближения, численное дифференцирование, численное интегрирование, численные методы решения обыкновенных дифференциальных уравнений, численное интегрирование дифференциальных уравнений в частных производных, метод Монте-Карло. ^ Изучение курса «Численные методы» ставит своей целью сформировать у студентов в систематизированной форме понятия о численных методах решения прикладных задач, источниках ошибок и методах оценки точности результата. Задача курса – познакомить студентов с основными численными методами, продемонстрировать обоснование существования решений прикладных задач на базе математических знаний студентов. Студенты должны усвоить методы не сами по себе, а в связи с использованием компьютера.
В результате изучения дисциплины «Численные методы» студент должен: уметь применять теоретический материал к решению вычислительных задач; обосновывать выбор численного метода; уметь оценивать точность результата; владеть алгоритмом используемого метода; составлять соответствующую программу на одном из конкретных языков программирования.
4.2. Содержание разделов дисциплины ^ Структура полной погрешности решения задачи. Приближенные числа, погрешности результатов основных арифметических действий. Связь между числом верных знаков и погрешностью числа. Общая формула для погрешности. Вычисление значений простейших функций. ^ Способы отделения корней (аналитический, графический, машинный). Итерационные методы. Обоснование сходимости итерационного процесса, оценка точности. Метод хорд, метод Ньютона, комбинированный метод. Метод деления пополам. ^ Численная интерполяция. Алгебраический интерполяционный многочлен: форма Лагранжа и Ньютона. Обратное интерполирование. Многочлены Чебышева. ^ Общий случай вычисления производной произвольного порядка. Неустранимая погрешность формул численного дифференцирования. ^ Квадратурная формула прямоугольников. Квадратурные формулы Ньютона-Котеса. Формула трапеций. Формула Симпсона. Квадратурные формулы Гаусса. ^ Решение систем уравнений. Прямые и итерационные процессы (метод Гаусса, метод главных элементов, метод простой итерации). Обращение матрицы. Понятие о методе Ньютона решения систем нелинейных уравнений. ^ Метод наименьших квадратов. Линейная регрессия. Нахождение приближающей функции в виде степенной, показательной дробно - рациональной. ^ Метод статистической обработки опытных данных. 9. Методы решения обыкновенных дифференциальных уравнений. Метод Пикара. Понятие устойчивости. Пример плохой обусловленности. Задача Коши для обыкновенных дифференциальных уравнений. Метод Эйлера. Метод Рунге-Кутта. Многошаговые методы. ^ Вычислительные методы решения краевых задач математической физики. Разностные схемы. Аппроксимация. Устойчивость. Сходимость. Вариационно-разностные методы, метод конечных элементов. ^ Идея метода Монте-Карло. Вычисление площади произвольной фигуры. Вычисление кратных интегралов методом Монте-Карло. Решение систем уравнений методом Монте-Карло.
^ а) основная литература: 1. Бахвалов, Н.С. Численные методы: учебное пособие для вузов / Н.С. Бахвалов, Н.П. Жидков, Г.М. Кобельков; МГУ.-5-е изд. – М.: Бином. Лаборатория знаний, 2007. – 636 с. б) дополнительная литература:
^ Рекомендуемая литература и учебно-методические пособия по предмету. Вся основная литература, указанная в пункте 6.1 имеется в достаточном количестве в библиотеке ТГПУ. ^ Компьютерные классы.
^ Преподаватель должен ориентировать студентов на то, чтобы они учились оценивать полученные результаты. Ему необходимо обращать особое внимание на то, как студенты записывают результаты в тетрадь с монитора компьютера. Они должны записывать только верные цифры. Для этого следует преподавателю объяснять студентам о необходимости осмыслить результат, убедиться, что задача решена правильно. Он должен обратить внимание студентов на то, что при компиляции программы на языке Паскаль, выдаются сообщения о синтаксических ошибках в тексте программы, запуск программы на вычисление невозможен без исправления этих ошибок. Поэтому после прохождения компиляции у студентов может возникнуть иллюзия, что всё вычисляется верно, но это не всегда так. Преподаватель должен предложить студентам самостоятельно дополнить программу или выполнить какие-то действия с тем, чтобы они убедились, что программа выдаёт правильный результат. В каждом конкретном методе будут даны указания, что нужно делать для контроля результата. ^ Теория погрешностей вынесена полностью на самостоятельное изучение студентами. Преподаватель должен проверить, как студенты усвоили основные понятия теории погрешностей. Особое внимание обратить на понятия предельной абсолютной погрешности и предельной относительной погрешности. Эти понятия является весьма широкими, а именно всякое число, большее предельной погрешности, также может быть принято за предельную погрешность числа. Объяснить студентам, что точность измерения или вычисления определяется относительной погрешностью. ^ Преподаватель должен обратить внимание студентов на то, что методы отделения корней не являются универсальными, они зависят от вида уравнения и студенты должны их выбирать самостоятельно и уметь обосновать свой выбор. Итерационные методы решения уравнения преподаватель должен излагать в общем виде, а затем рассматривать частные случаи. Такой подход в изложении даёт возможность студентам создать свой итерационный метод. Преподаватель должен предложить студентам решить уравнение разными методами и сравнить результаты по скорости сходимости. Для контроля вычислений им необходимо выдавать не только значение корня, но и значение функции в нём, и сравнивать визуально это значение с заданной точностью. Так, если точность ![]() ^ Для определения погрешности формулы Лагранжа преподаватель должен предложить студентам выбор – решить её аналитически или с помощью вычислений на компьютере. Он должен объяснить студентам, что результат можно записать только тогда, когда будет определена погрешность. Для контроля вычислений преподавателю необходимо проверить значения интерполяционного многочлена в узловых точках, они должны точно совпадать со значениями исходной функции в узлах, и только после этого студент может использовать интерполяционный многочлен для произвольных точек. В теме интерполирование так же рассматривается задача обратного интерполирования. Обратить внимание студентов на то, что обратное интерполирование для функций приближенных многочленом Лагранжа выполняется достаточно просто, x и y меняют местами. В случае, когда исходная функция заменена 1 или 2 формулами Ньютона, для решения задачи обратного интерполирования, необходимо использовать итерационный метод решения уравнения. ^ При изучении численного дифференцирования обратить внимание студентов на то, что данная задача является некорректной. Решение этой задачи опирается на интерполирование, в котором мера близости приближающей функции – это совпадение в узлах с исходной функцией. Действительно, близость друг к другу ординат двух кривых ![]() ![]() ![]() ![]() ^ При изучении численного интегрирования обратить внимание студентов, что вывод квадратурных формул изложен в общем виде, для произвольного n (формулы Ньютона-Котеса, Чебышева, Гаусса), а затем приведены их частные случаи. Узлы в формулах Гаусса и Чебышева неравноотстоящие. Преподаватель должен продемонстрировать студентам, что квадратурная формула Чебышева, в которой вес всех значений ![]() ![]() ^ При решении систем линейных алгебраических уравнений, число неизвестных ![]() Дополнительно при вычислении обратной матрицы, студенты должны уметь расписать компактную формулу ![]() ![]() ![]() ![]() В методах решения систем нелинейных уравнений студенты должны уметь записывать матрицу Якоби системы n функций относительно n переменных. Они должны понимать, что для нахождения очередного приближения необходимо на каждом шаге вычислять обратную матрицу. ^ Преподаватель должен обратить внимание студентов на отличие приближения функции по методу наименьших квадратов от приближения функции методом интерполирования. Преподаватель предлагает студентам таблично заданную функцию приближать различными аналитическими функциями. При сравнении результатов аппроксимирования определяющим является величина суммарной ошибки ![]() ![]() ![]() ![]() Дополнительно студенты могут выполнить самостоятельно аппроксимирование по методу наименьших квадратов логарифмической ![]() ![]() ^ В методе статистической обработки опытных данных преподаватель должен объяснить студентам цель статистической обработки. Обратить их внимание на то, что величины D, S, C эта одна и та же характеристика случайной величины, отличаются только единицами измерения. Он должен обратить внимание на критерий Стьюдента, объяснить студентам, какова его роль в обработки опытных данных. ^ Преподаватель должен обратить внимание студентов на отличие приближенных методов от численных методов, на область применения этих методов и на то, в каком виде они дают решение. Сформулировать им необходимые условия применения численного метода, чтобы задача была хорошо обусловлена или устойчива, т.е. малые изменения начальных условий приводили бы к достаточно малому изменению интегральных кривых. Если это условие не выполнено, то небольшие изменения начальных условий или эквивалентные этим изменениям небольшие погрешности численного метода могут сильно исказить решение. Студенты должны знать условие, когда дифференциальное уравнение можно решить методом Пикара. Преподаватель должен объяснить, в чём основное преимущество многошаговых экстраполяционных методов Адамса. ^ Метод конечных разностей является универсальным методом решения дифференциальных уравнений. Преподаватель должен объяснить, что в основе метода лежит сведение дифференциальной задачи к системе линейных алгебраических уравнений. Студенты должны знать, что такое погрешность аппроксимации, какая разностная схема называется явной. В случае явной разностной схемы на самом деле получается рекуррентное соотношение, которое выражает значения искомого решения на последующем слое через значения на предыдущем слое. В случае неявной схемы студентам необходимо будет решать систему уравнений. ^ Способы решения задач, использующие случайные величины, получили общее название метода Монте-Карло. Преподаватель должен обратить внимание студентов на математическое обоснование метода Монте-Карло, определить сходимость последовательности по вероятности и объяснить отличие детерминированного метода от недетерминированного метода. Важно понимать то, что для решения одной и той же конкретной задачи схема применения метода может быть существенно различной. Он должны обратить внимание студентов на то, как меняется классический алгоритм вычисления кратных интегралов с увеличением кратности и, что происходит в этой ситуации с методом Монте-Карло. ^ По курсу «Численные методы» студенты должны прослушать лекции, самостоятельно проработать теоретические вопросы и выполнить лабораторные работы, которые проходят в компьютерных классах. По данному курсу опубликовано шесть методических разработок, в которых кроме изложения теории, рассмотрены примеры и приведены программы на языке Паскаль. Каждая тема заканчивается контрольными вопросами, с помощью их студент самостоятельно может проверить глубину усвоения соответствующей темы. Так как отдельные темы полностью вынесены на самостоятельное изучение, то наличие таких методических разработок, даёт студентам возможность, изучить, соответствующую тему не обращаясь к другим источникам. Для получения зачета студентам необходимо выполнить индивидуальные задания и пройти устный опрос теории по темам лабораторных занятий. Выполнение заданий, вынесенных на самостоятельное изучение, проверяются преподавателем в течение семестра, по ним так же проводится зачет. Студенты должны обращать особое внимание на точность того или иного метода, а так же на область его применения. При записи результата они должны записывать только верные цифры. Для этого им необходимо осмыслить результат, убедиться, что задача решена правильно. При компиляции программы на языке Паскаль, выдаются сообщения о синтаксических ошибках в тексте программы, запуск программы на вычисление невозможен без исправления этих ошибок. Поэтому после прохождения компиляции у студентов возникает иллюзия, что всё вычисляется верно, но это не всегда так. Они должны сами дополнить программу или выполнить какие-то действия с тем, чтобы убедиться, что программа выдаёт правильный результат. В каждом конкретном методе будут даны указания, что нужно делать для контроля результата. ^ Теория погрешностей вынесена полностью на самостоятельное изучение студентами. В этой теме они должны обратить внимание на источники и классификации погрешностей, а так же на понятие – верная цифра и связь количества верных цифр с относительной погрешностью числа. Дополнительно к основным вопросам студенты могут рассмотреть, что происходит с погрешностью при умножении приближенного числа на точный множитель, а так же какая проблема возникает при вычитании близких чисел и каким образом можно решить эту проблему. ^ При изучении методов решения уравнений с одним неизвестным студенты должны обратить внимание на то, что не только большинство трансцендентных уравнений не имеют формулы решений, но и алгебраические уравнения степень, которых выше четырёх. Они должны обратить особое внимание на то, что методы отделения корней не являются универсальными, зависят от вида уравнения. Студенты должны их выбирать самостоятельно и уметь обосновать свой выбор. Изложение итерационных методов решения уравнения выполнено в общем случае, затем рассмотрены частные случаи. Такой подход в изложении даёт возможность студентам создать свой итерационный метод. Студенты должны уметь выбирать начальное приближение в каждом методе, обосновывать этот выбор и определять условие, которое является критерием для достижения заданной точности. Студенты самостоятельно должны дополнить приведенную в методической разработке программу так, чтобы она выдавала количество итераций для достижения заданной точности. Студенты решают уравнение разными методами, сравнивают количество итераций. Это позволит им сделать вывод о скорости сходимости того или иного метода. Дополнительно по этой теме студенты могут рассмотреть геометрическую интерпретацию итерационных методов. ^ Формула погрешности интерполирования содержит производную (n+1) порядка от исходной функции. Студенты должны найти эту производную и определить её максимальное значение на заданном интервале. При решении этой задачи у них есть выбор – решить её аналитически или с помощью вычислений на компьютере. Он должны понимать, что результат можно записать только тогда, когда будет определена погрешность. Студенты должны усвоить понятие обобщенной степени числа и уметь записывать I и I I формулы Ньютона через обобщенную степень. Для контроля вычислений студенту необходимо проверить значения интерполяционного многочлена в узловых точках, они должны точно совпадать со значениями исходной функции в узлах, и только после этого он может использовать интерполяционный многочлен для произвольных точек. Дополнительно для более полного усвоения этой темы студенты должны уметь расписывать формулу Лагранжа в развёрнутом виде. Дополнительно они должны уметь пользоваться рекуррентными формулами для нахождения многочленов Чебышева. В теме интерполирование так же рассматривается задача обратного интерполирования. Обратить внимание студентов на то, что обратное интерполирование для функций приближенных многочленом Лагранжа выполняется достаточно просто, x и y меняют местами. В случае, когда исходная функция заменена 1 или 2 формулами Ньютона, для решения задачи обратного интерполирования, необходимо использовать итерационный метод решения уравнения. ^ При изучении численного дифференцирования студент должен обратить внимание на то, что данная задача является некорректной. Решение этой задачи опирается на интерполирование, в котором мера близости приближающей функции – это совпадение в узлах с исходной функцией. Действительно, близость друг к другу ординат двух кривых ![]() ![]() ![]() ![]() ^ При изучении численного интегрирования студенты должны научиться выводить квадратурные формулы в общем виде, для произвольного n (формулы Ньютона-Котеса, Чебышева, Гаусса), а затем рассмотреть их частные случаи. Студенты вычисляют интеграл по разным квадратурным формулам, выполняют, так называемый вычислительный эксперимент, и определяют какая из формул более точная при равных условиях. Когда речь идёт о точности той или другой квадратурной формулы, то это понятие довольно условное, так как всегда можно выбрать надлежащим образом значение h, получить результат, с какой угодно степенью точности. Дополнительно в этой теме студенты должны научиться вычислять коэффициенты Котеса при различных значениях n. ^ При решении систем линейных алгебраических уравнений. Число неизвестных ![]() Методы решения алгебраических задач разделяются на точные, итерационные и вероятностные. Студенты должны изучить три метода: метод главных элементов, метод итерации и метод Монте-Карло. Студенты должны решить систему разными методами и сравнить полученные результаты. Дополнительно при вычислении обратной матрицы, студенты должны уметь расписать компактную формулу ![]() ![]() ![]() ![]() В методах решения систем нелинейных уравнений студенты должны уметь записывать матрицу Якоби системы n функций относительно n переменных. Они должны понимать, что для нахождения очередного приближения необходимо на каждом шаге вычислять обратную матрицу. ^ Студенты должны знать, каким образом получается эмпирическая формула. Они должны обратить внимание на отличие приближения функции по методу наименьших квадратов от приближения функции методом интерполирования. Студенты должны знать, каким образом строится приближающая функция в виде различных элементарных функций. При выполнении лабораторной работы студенты таблично заданную функцию приближают различными аналитическими функциями. При сравнении результатов аппроксимирования определяющим является величина суммарной ошибки ![]() ![]() ![]() ![]() Дополнительно студенты могут выполнить самостоятельно аппроксимирование по методу наименьших квадратов логарифмической ![]() ![]() ^ В методе статистической обработки опытных данных студенты должны ясно представлять цель статистической обработки. Они должны уметь объяснить значение величин D, S, C. С какой целью эти величины введены, что характеризуют и в каких единицах измеряются по отношению к единицам измерения исходного массива. ^ Студенты должны знать основные виды дифференциальных уравнений и методы их решения. Они должны представлять отличие приближенных методов от численных методов и то, в каком виде эти методы дают решение. Так для успешного применения численного метода необходимо, чтобы задача была хорошо обусловлена или устойчива, т.е. малые изменения начальных условий приводили бы к достаточно малому изменению интегральных кривых. Если это условие не выполнено, т.е. задача плохо обусловлена, то небольшие изменения начальных условий или эквивалентные этим изменениям небольшие погрешности численного метода могут сильно исказить решение. Они должны знать условие, когда дифференциальное уравнение можно решить методом Пикара. Студенты должны уметь объяснить, в чём основное преимущество многошаговых экстраполяционных методов Адамса. Дополнительно студенты могут рассмотреть геометрический смысл численных методов и сравнить их по точности результатов. ^ Метод конечных разностей является универсальным методом решения дифференциальных уравнений. Студенты должны понимать что, в основе методов лежит сведение дифференциальной задачи к системе линейных алгебраических уравнений. Они должны знать, что такое погрешность аппроксимации, какая разностная схема называется явной. В случае явной разностной схемы на самом деле получается рекуррентное соотношение, которое выражает значения искомого решения на последующем слое через значения на предыдущем слое. В случае неявной схемы студентам необходимо будет решать систему уравнений. ^ Под методом Монте-Карло понимается совокупность приёмов, позволяющих получать решения математических или физических задач при помощи случайных многократных испытаний. Оценки искомой величины выводятся статистическим путем и носят вероятностный характер. Студенты должны обратить внимание на математическое обоснование метода Монте-Карло. Они должны уметь объяснить сходимость последовательности по вероятности, чем отличается детерминированный алгоритм от недетерминированного метода. Студенты должны понимать, что для решения одной и той же конкретной задачи схема применения метода может быть существенно различной. Они должны обратить внимание на то, как меняется классический алгоритм вычисления кратных интегралов с увеличением кратности и, что происходит в этой ситуации с методом Монте-Карло. Дополнительно студенты могут рассмотреть, в чем особенность решения системы линейных алгебраических уравнений методом Монте-Карло. ^
а) ![]() ![]() ![]() ![]() в) ![]() ![]() ![]() ![]()
![]() Написать в развернутом виде два первых слагаемых суммы.
Примерный перечень вопросов к зачету:
Программа составлена в соответствии с Государственным образовательным стандартом высшего профессионального образования по специальности 030100 (050202.65) Информатика, квалификация - учитель информатики. Программу составил: кандидат физ.- мат. наук., доцент кафедры теоретической физики ТГПУ ______________ Г.К. Разина. Программа учебной дисциплины утверждена на заседании кафедры теоретической физики протокол № ________ от “____” _______________ 200___ г. Зав. кафедрой, профессор _______________ И.Л. Бухбиндер Программа учебной дисциплины одобрена методической комиссией физико-математического факультета ТГПУ (УМС университета) Председатель методической комиссии физико-математического факультета, профессор_____________________ В.И. Шишковский Согласовано: Декан физико- математического факультета _________________________ А.Н. Макаренко.
|