– 135–

Министерство образования Республики Беларусь

Учреждение образования

«Белорусский государственный университет

информатики и радиоэлектроники»

Кафедра «Вычислительные методы и программирование»

Соловьев В.П., Кривоносова Т.М.

ОСНОВЫ АЛГОРИТМИЗАЦИИ И ПРОГРАММИРОВАНИЯ

Конспект лекций

ЧАСТЬ 2

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

(материал не редактирован)

для студентов всех специальностей и форм обучения БГУИР

Минск 2008

СОДЕРЖАНИЕ

1. Этапы решения технических задач на ЭВМ 5

2. Методы реализации математических моделей 6

Раздел 1. Элементы теории погрешностей 7

1.1. Постановка задачи 7

1.2. Источники погрешностей 7

1.3. Приближенные числа и оценка их погрешностей 9

1.4. Правила записи приближенных чисел 10

1.5. Задачи теории погрешностей 12

1.6. Понятия устойчивости, корректности постановки задач и сходимости численного решения 13

1.7. Некоторые обобщенные требования к выбору численных методов 14

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

2.1. Основные понятия и определения 15

2.2. Методы решения СЛАУ 17

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

1. Правило Крамера 17

2. Метод обратных матриц 17

3. Метод Гаусса 18

4. Модифицированный метод Гаусса 19

5. Метод прогонки 26

6. Метод квадратного корня 28

2.2.2. Итерационные методы решения СЛАУ 38

1. Метод простой итерации 40

2. Метод Зейделя 45

2.3. Вычисление определителей высоких порядков 48

2.4. Вычисление обратных матриц 49

2.5. Применение метода итераций для уточнения элементов обратной матрицы 51

Раздел 3. Численное решение нелинейных уравнений 52

3.1. Постановка задачи 52

3.2. Отделение корней 53

3.2.1. Метод половинного деления 53

3.2.2. Графическое отделение корней 55

3.3. Итерационные методы уточнения корней 55

3.3.1. Метод простой итерации 55

3.3.2. Метод Ньютона (касательных) 57

3.3.3. Метод секущих 58

3.3.4. Метод деления отрезка пополам 59

3.3.5. Метод хорд 61

3.4. Общий алгоритм численных методов решения нелинейных уравнений 62

Раздел 4. Решение систем нелинейных уравнений 64

4.1. Постановка задачи 64

4.2. Метод простой итерации 64

4.2.1. Условия сходимости метода простой итерации для нелинейных систем уравнений второго порядка 65

4.2.2. Общий случай построения итерирующих функций 67

4.3. Метод Ньютона для систем двух уравнений 68

4.4. Метод Ньютона для систем n-го порядка с n неизвестными 70

Раздел 5. Аппроксимация функций 72

5.1. Постановка задачи 72

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

5.3. Типовые виды локальной интерполяции 74

5.3.1. Линейная интерполяция 74

5.3.2. Квадратичная (параболическая) интерполяция 75

5.4. Типовые виды глобальной интерполяции 76

5.4.1. Интерполяция общего вида 76

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

1. Формула Лагранжа для произвольной системы интерполяционных узлов 77

2. Полином Лагранжа на системе равноотстоящих интерполяционных узлов 78

5.4.3. Интерполяционный многочлен Ньютона 79

1. Интерполяционный многочлен Ньютона для системы равноотстоящих узлов 80

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

3. Локальная интерполяция 84

4. Глобальная интерполяция 85

5.5. Сплайны 88

5.6. Сглаживание результатов экспериментов 91

5.7. Вычисление многочленов 92