Конспект лекций междисциплинарного курса МДК.01.04 Математические методы разработки алгоритмов профессионального модуля ПМ.01 Разработка программных модулей программного обеспечения для компьютерных систем (стр. 1 )

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ПЕНЗЕНСКИЙ ГОСУДАРСТВЕННЫЙ  УНИВЕРСИТЕТ

МНОГОПРОФИЛЬНЫЙ КОЛЛЕДЖ

               

КОНСПЕКТ ЛЕКЦИЙ

междисциплинарного курса

МДК.01.04  МАТЕМАТИЧЕСКИЕ МЕТОДЫ РАЗРАБОТКИ АЛГОРИТМОВ

профессионального модуля

ПМ.01 Разработка программных модулей программного обеспечения для компьютерных систем

Специальность  09.02.03 Программирование в компьютерных системах

Квалификация выпускника – Техник-программист

Форма обучения – Очная

2015 г.

Содержание

Введение        3

1. Приближенные числа и действия над ними …………………………………... 5

1.1. Виды погрешностей при приближенных вычислениях ……………………………….  5

1.2. Приближенные числа …………………………………………………………………….. 6

1.3. Значащие цифры, верные и сомнительные цифры ……………………………………...8

1.4. Округление ………………………………………………………………………………... 9

1.5. Погрешности арифметических операций ………………………………………………10 

2. Приближенное решение алгебраических уравнений …………………………11

2.1. Методы решения нелинейных алгебраических уравнений с одной переменной …... 12

2.2. Метод половинного деления ............................................................................................. 15

2.3. Метод хорд…..………………………………………………………………………….... 16

2.4. Метод простой итерации        18

2.5. Метод Ньютона (метод касательных) ………………………………………………….  21

3. Приближение функций        23

3.1. Постановка задачи приближения функции        24

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

3.3. Алгоритм вычисления значения интерполяционного многочлена Лагранжа        26

4. Решение систем линейных алгебраических уравнений (СЛАУ)         28

4.1. Матрицы и их свойства        28

4.2. Выполнение операции над матрицами        28

4.3. Системы линейных алгебраических уравнений        29

4.4. Обусловленность систем линейных алгебраических уравнений        31

4.5. Прямые методы решения СЛАУ        37

4.5.1. Метод Гаусса …………………………………………………………………… 32

4.5.2. Метод LU-разложения …………………………………………………………  33

4.6. Итерационные методы решения СЛАУ ………………………………………………..  34

4.6.1. Метод Якоби (метод простой итерации) ………………………………………34

4.6.2. Метод Зейделя ………………………………………………………………….  34

5.  Численное интегрирование и дифференцирование …………………………  35

5.1. Постановка задачи численного интегрирования ……………………………………… 35

5.2. Метод прямоугольников        36

5.3. Метод трапеций        38

5.4. Метод Симпсона        39

5.5. Правило Рунге …………………………………………………………………………… 41 

5.6. Численное дифференцирование ………………………………………………………… 41

Заключение        43

Литература        44

Введение

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

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

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

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

Стало возможным более эффективное познание законов реального мира, значительное увеличение производительности труда, развитие производства, совершенствование управления.

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

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

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

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

Источниками погрешности приближенного решения являются:

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

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

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

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

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

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

Классическим примером некорректной задачи является задача Коши для уравнения Лапласа. Эта некорректность исходной задачи проявляется и при её численном решении.

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

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

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

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

Сам алгоритм и компьютерная программа должны быть тщательно проверены. Даже проверка программы нелегка. Проверка алгоритма ещё более трудна, ибо для сложных алгоритмов не часто удается доказать сходимость классическими методами. Приходится использовать более или менее надежные «экспериментальные» проверки, проводя пробные расчеты на компьютере и анализируя их.

1. Приближенные числа и действия над ними

1.1. Виды погрешностей при приближенных вычислениях

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