Элективный курс по информатике для учащихся 10-11 классов

Численные методы и компьютерное моделирование

Авторы:Николаева Ирина Васильевна,

ВГПУ, доцент,

Олейникова Екатерина Владимировна,

методист кабинета информатики ВОИУУ,

Кислицына Ольга Николаевна,

МОУ СОШ № 2, учитель информатики

Пояснительная записка.

Компьютерные модели – это модели, составленные в расчете на исполнителя, имитированного на компьютере. Компьютерная модель – это информационная модель + алгоритм для реализации этой модели. Исходные данные, результат и связи между ними в компьютерной модели представляются в виде «понятном» компьютерному исполнителю. Примерами исполнителей, имитированных на компьютере являются: Qbasic-система, Pascal-система, Visual Basic-система, Delphi-система, электронные таблицы, математическая система автоматизированного проектирования Mathcad и др.

Информационная модель - это модель, представляющая объект, процесс или явление набором параметров и связей между ними.

Математическая модель – это информационная модель, в которой параметры и зависимости между ними выражены в математической форме.

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

Для решения таких задач стремятся найти какой-нибудь бесконечный процесс, сходящийся к искомому решению. Если такой процесс указан, то, выполняя некоторое число шагов, и затем, обрывая вычисления (их нельзя продолжать бесконечно), мы получим приближенное решение задачи. Эта процедура связана с проведением вычислений по строго определенное системе правил, которая задается характером процесса и называется алгоритмом. Сходимость процесса гарантирует, что для любой заданной точности ε, найдется такой номер N, что для всех n ≥ N полученное приближенное решение отличается от точного не более чем на ε, | х_n – x^* | ≤ ε, где x^*  - точное решение поставленной задачи. Алгоритмы, использующие бесконечный сходящийся процесс, требуют большой объем необходимых вычислений. Такие алгоритмы называют вычислительными алгоритмами, а основанные на них методы решения – численные методы. В прикладных задачах значения искомых величин желательно получить количественно, то есть ответ довести «до числа».

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

Цель курса – сформировать у учащихся в систематизированной форме понятия о приближенных (численных) методах решения практических задач, методах компьютерного моделирования, источниках ошибок и методах оценки точности результатов. Изучив курс, ученик должен уметь обосновать выбор численного метода и видеть пути оценки точности вычислений, владеть алгоритмом используемого метода и уметь реализовывать этот метод в виде программы на одном из языков программирования, иметь навыки практического использования программного обеспечения компьютера, например, MS Excel, Mathcad.

Задачи курса:

1. Общее развитие и становление мировоззрения учащихся. Содержание курса, методы реализации этого содержания выполняют развивающую функцию, учащиеся продолжают работать с методом познания окружающей действительности – методом компьютерного моделирования, используют полученные знания о компьютерной арифметике.

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

3. Развитие и профессионализация навыков работы с компьютером. Перед учащимися ставится задача реализовать алгоритм численного решения задачи на компьютере, в наглядной, доступной форме отобразить полученные результаты, провести вычислительный эксперимент численного решения задачи с использованием электронных таблиц MS Excel и математической системы Mathcad, что способствует более полному изучению возможности программного обеспечения компьютера, а при оценке точности – возможности компьютера, как вычислителя.

Предлагаемый курс включает следующие содержательные линии:

1. Представление информации. Представление числовой информации в компьютере, арифметические операции над числами, источники погрешностей при работе с числами на компьютере.

2. Формализация и моделирование. На примерах решения практических задач обучаемый участвует в реализации всех этапов компьютерного моделирования, начиная с исследования моделируемой предметной области и постановки задач до интерпретации результатов, полученных в ходе компьютерного эксперимента. Курс предполагает формирование навыков компьютерного моделирования. Он включает компьютерные лабораторные работы по реализации составленных обучаемыми или предложенных учителем программ численных методов решения задач, проведение вычислительного эксперимента.

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

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

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

На практических и лабораторных работах ученики преобразуют теоретические идеи в практическую вычислительную процедуру, разрабатывают алгоритмы решения задач и кодируют их в программы, предназначенные для реализации на компьютере, а так же используют готовые программы, встроенные в MS Excel и Mathcad для проведения вычислительного эксперимента при решении некоторых задач. Ученики получают практический опыт в описаниях вычислительных алгоритмов решения практических задач на одном из языков программирования, что ведет к более глубокому пониманию сущности численных методов и их практической ценности, ориентирует на грамотное использование прикладного программного обеспечения компьютера, обогащает учащихся новыми способами решения задач.

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

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

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

 Требования к знаниям и умениям учащихся.

1. Характеристики приближённых значений чисел.

Учащиеся должны знать:

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

–                    что, при оценке точности полученного решения задачи необходимо учитывать точность исходных данных;

–                    основные понятия: погрешность приближения, границы абсолютной и относительной погрешностей приближения, верная цифра в записи числа;

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

Учащиеся должны уметь:

–                    находить погрешность приближения, абсолютную и относительную погрешность приближения, границы абсолютной и относительной погрешности приближений;

–                    округлить приближенные значения чисел, записывать числа со всеми верными цифрами;

–                    вычислить границы абсолютной и относительной погрешностей результатов действий над приближенными числами.

2. Компьютерная арифметика.

Учащиеся должны знать:

–                    алгоритмы компьютерного представления целых чисел (знаковое и беззнаковое);

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

–                    алгоритмы машинного сложения и умножения целых чисел;

–                    источники возникновения ошибок при операциях с целыми числами;

–                    что такое битовые операции;

–                    компьютерное представление вещественных чисел;

–                    алгоритмы выполнения арифметических операций над вещественными числами;

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

Учащиеся должны уметь:

–                    имитировать представление целых чисел в компьютере в знаковой и беззнаковой форме на примере представления числа в 8 двоичных разрядах или 16 двоичных разрядах;

–                    определить для каждого представления чисел границы диапазона их представления;

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

–                    оценить точность полученного результата с учетом особенностей компьютерной арифметики над целыми числами;

–                    имитировать представление вещественных чисел в компьютере;

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

–                    имитировать проведение арифметических операций над вещественными числами в компьютере с фиксированным распределением разрядов ячейки памяти;

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

3. Численные методы.

Учащиеся должны знать:

–                    понятия компьютерная модель, численный метод, когда применяется численный метод решения практической задачи;

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

Учащиеся должны уметь:

–                    выбрать необходимый численный метод и инструмент для решения практической задачи;

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

3.1. Решение уравнений с одной переменной.

Учащиеся должны знать:

–                    этапы решения уравнений с одной переменной приближенными методами (этап отделения корня уравнения и этап уточнения корня уравнения);

–                    теоремы о существовании корня уравнения y = f(x) на отрезке [a, b];

–                    методы отделения корня уравнения с одной переменной: аналитический метод и графический метод отделения корня;

–                    алгоритм и программу отделения корня уравнения с одной переменной ;

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

–                    сущность метода хорд, алгоритм и программу уточнения корня уравнения с одной переменной методом хорд с заданным числом шагов;

–                    сущность метода касательных, алгоритм и программу уточнения корня уравнения с одной переменной методом касательных с заданным числом шагов;

–                    сущность комбинированного метода, алгоритм и программу уточнения корня уравнения с одной переменной с заданной точностью комбинированным методом;

–                    сущность метода простой итерации уточнения корня уравнений f(x) = 0, алгоритм и программу вычисления корня уравнений с одной переменной методом простой итерации с заданной точностью;

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

Учащиеся должны уметь:

–                    отделить корень уравнения одним из рассмотренных методов (аналитическим , графическим или « компьютерным»);

–                    вычислить корень уравнения с одной переменной с заданной точностью методом деления отрезка пополам и комбинированным методом, используя систему программирования (Qbasic, Turbo Pascal, Visual Basic, Delphi и др.);

–                    преобразовать уравнение к виду удобному для применения метода простой итерации;

–                    вычислить корень уравнения f(x) = 0 методом простой итерации с заданной точностью, используя систему программирования (Qbasic, Turbo Pascal, Visual Basic, Delphi и др.);

–                    вычислить корень уравнения с одной переменной с заданной точностью, используя электронные таблицы MS Excel и математическую систему Mathcad.

3.2. Решение систем линейных алгебраических уравнений.

Учащиеся должны знать:

–                    что является решением системы линейных алгебраических уравнений;

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

–                    элементарные преобразования систем линейных алгебраических уравнений;

–                    алгоритм и программу решения систем линейных алгебраических уравнений методом Жордана-Гаусса с уточнением;

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

Учащиеся должны уметь:

–                    определить какая система линейных алгебраических уравнений является совместной, несовместной, определенной, неопределенной;

–                    определить являются ли системы линейных алгебраических уравнений эквивалентными;

–                    решить систему линейных алгебраических уравнений методом Жордана-Гаусса с уточнением, используя систему программирования (Qbasic, Turbo Pascal, Visual Basic, Delphi и др.);

–                    найти решение систем линейных алгебраических уравнений, используя электронные таблицы MS Excel и математическую систему Mathcad, геометрически интерпретировать решение систем линейных алгебраических уравнений, если это возможно.

3.3. Решение задач линейного программирования.

Учащиеся должны знать:

–                    постановку задачи линейного программирования, общую математическую формулировку основной задачи линейного программирования;

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

–                    геометрическую интерпретацию решения задачи линейного программирования;

–                    симплекс-метод решения задач линейного программирования при заданном начальном допустимом базисном решении;

–                    алгоритм и программу реализации симплекс-метода на компьютере;

–                    один из методов отыскания исходного базиса;

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

Учащиеся должны уметь:

–                    составить информационные (математические) модели для решения практических задач на отыскание наибольших и наименьших значений некоторых величин, если методы математического анализа для решения поставленных задач являются непригодными;

–                    графически находить решения некоторых задач линейного программирования;

–                    решить задачу линейного программирования симплекс-методом, используя систему программирования (Qbasic, Turbo Pascal, Visual Basic, Delphi и др.), провести анализ решение задачи линейного программирования;

–                    отыскать исходный базис одним из методов;

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

3.4. Интерполирование функций.

Учащиеся должны знать:

–                    что такое интерполировании функции, когда используют приближение функции интерполяционным многочленом;

–                    геометрическую, математическую формулировку задачи интерполирования функции многочленом n-ой степени;

–                    формулы прямой и обратной линейных интерполяций, схему Эйткина интерполирования функции;

–                    конечные разности, свойства конечных разностей;

–                    интерполяционную формулу Лагранжа; алгоритм и программу вычисления значения функции с использованием интерполяционной формулы Лагранжа;

–                    что такое интерполяция сплайнами;

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

Учащиеся должны уметь:

–                    приблизить функцию, используя формулы прямой и обратной линейных интерполяции;

–                    находить конечные разности k-го порядка;

–                    приблизить функцию интерполяционным полиномом Лагранжа, используя систему программирования (Qbasic, Turbo Pascal, Visual Basic, Delphi и др.);

–                    находить приближающую функцию с помощью электронных таблиц MS Excel и математической системы Mathcad.

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

Учащиеся должны знать:

–                    постановку задачи численного интегрирования;

–                    формулы правых, левых и серединных прямоугольников численного интегрирования, остаточный член формулы серединных прямоугольников численного интегрирования, алгоритм и программу вычисления площади криволинейной трапеции по формулам прямоугольников;

–                    формулу трапеций численного интегрирования, остаточный член формулы трапеций численного интегрирования, алгоритм и программу вычисления площади криволинейной трапеции по формуле трапеций;

–                    формулу Симпсона численного интегрирования, остаточный член формулы Симпсона численного интегрирования, алгоритм и программу вычисления площади криволинейной трапеции по формуле Симпсона;

–                    знать возможности электронных таблиц MS Excel и математической системы Mathcad для решения задач численного интегрирования;

Учащиеся должны уметь:

–                    вычислить площади криволинейной трапеции с заданной точностью по формуле серединных прямоугольников, используя систему программирования (Qbasic, Turbo Pascal, Visual Basic, Delphi и др.);

–                    вычислить площади криволинейной трапеции с заданной точностью по формуле трапеций, используя систему программирования (Qbasic, Turbo Pascal, Visual Basic, Delphi и др.);

–                    вычислить площади криволинейной трапеции с заданной точностью по формуле Симпсона, используя систему программирования (Qbasic, Turbo Pascal, Visual Basic, Delphi и др.);

–                    сравнить используемые методы численного интегрирования;

–                    применить электронные таблицы MS Excel и математическую систему Mathcad для численного интегрирования.

Программа.

1. Характеристики приближённых значений чисел.

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

2. Компьютерная арифметика.

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

3. Численные методы.

Необходимость введения численных методов для решения многих практических задач (примеры задач, для решения которых необходимы приближенные методы). Структура полной погрешности решения задачи с использованием компьютера.

3.1. Решение уравнений с одной переменной.

Постановка задачи решения уравнения f(x) = 0 приближенным методом. Этапы решения уравнения f(x) = 0 приближенным методом. Отделение корня уравнения  f(x) = 0. Алгоритм и программа отделения корня уравнения  f(x) = 0.Уточнение корня уравнения f(x) = 0 методом деления отрезка пополам с заданной точностью. Алгоритм и программа уточнения корня уравнения  f(x) = 0 методом деления отрезка пополам с заданной точностью.  Уточнение корня уравнения f(x) = 0 методом хорд, методом касательных.  Уточнение корня уравнения f(x) = 0 комбинированным методом с заданной точностью. Алгоритм и программа уточнения корня уравнения f(x) = 0 комбинированным методом с заданной точностью. Метод простой итерации решения уравнения f(x) = 0. Геометрическая иллюстрация итерационной последовательности. Оценка погрешности последовательных приближений. Преобразование  уравнения f(x) = 0  к виду удобному для применения метода итераций. Практическая схема решения уравнения методом итераций. Алгоритм и программа уточнения корня уравнения f(x) = 0 методом простой итерации с заданной точностью. Решение задач с использованием электронных таблиц MS Excel и математической системы Mathcad.

3.2. Решение систем линейных алгебраических уравнений.

Некоторые понятия: точные и итерационные численные методы решения систем линейных алгебраических уравнений; решение системы линейных алгебраических уравнений; совместная и несовместная, определенная и неопределенная системы линейных алгебраических уравнений; элементарное преобразование систем линейных алгебраических уравнений. Решение системы  линейных алгебраических уравнений методом Жордана-Гаусса, уточнение решения. Алгоритм и программа решения системы линейных алгебраических уравнений методом Жордана-Гаусса с уточнением. Решение задач с использованием электронных таблиц MS Excel и математической системы Mathcad.

3.3. Решение задач линейного программирования.

Постановка задачи линейного программирования. Общая математическая формулировка основной задачи линейного программирования. Основные понятия: базисные переменные, свободные переменные, базисное решение, допустимое решение, целевая функция. Геометрический смысл решения задачи линейного программирования. Графическое решение задачи линейного программирования.  Симплекс-метод решения задач линейного программирования при заданном начальном допустимом базисном решении. Алгоритм и программа решения задачи линейного программирования с использованием симплекс-метода. Некоторые методы отыскания исходного базисного решения. Решение задач линейного программирования с использованием электронных таблиц MS Excel и математической системы Mathcad.

3.4. Интерполирование функций.

Задача приближения функций. Понятие об интерполировании функций. Геометрическая, математическая формулировка задачи интерполирования функции многочленом n-ой степени.  Прямая и обратная линейные интерполяции, схема Эйткина интерполирования функции. Конечные разности, свойства конечных разностей. Интерполяционная формула Лагранжа. Алгоритм и программа вычисления значения функции с использованием интерполяционной формулы Лагранжа. Интерполяция сплайнами. Решение задач на интерполирование функций с использованием электронных таблиц MS Excel и математической системы Mathcad.

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

Постановка задачи численного интегрирования. Формулы левых, правых и серединных прямоугольников численного интегрирования. Остаточный член формулы прямоугольников численного интегрирования. Алгоритм и программа численного интегрирования по формулам прямоугольников. Формула трапеций численного интегрирования. Остаточный член формулы трапеций численного интегрирования. Алгоритм и программа численного интегрирования по формуле трапеций.  Формула Симпсона численного интегрирования. Остаточный член формулы Симпсона численного интегрирования. Алгоритм и программа численного интегрирования по формуле Симпсона. Решение задачи численного интегрирования с использованием электронных таблиц MS Excel и математической системы Mathcad.

Тематический план.

Литература:

1. Заварыкин В.М., Житомирский В.Г., Лапчик М.П. Техника вычислений и алгоритмизация. – М.: Просвещение, 1987 г.

2. Андреева Е., Фалина И. Системы счисления и компьютерная арифметика. – М.: Лаборатория Базовых Знаний, 2000 г.

3. Заварыкин В.М., Житомирский В.Г., Лапчик М.П. Численные методы. – М.: Просвещение, 1991 г.

4. Мудров А.Е. Численные методы для ПЭВМ на языках Бейсик, Фортран и Паскаль. – Томск: МП «Раско», 1992 г.

ПРИЛОЖЕНИЯ

к списку авторов