Вычислительная математика лекции. Конспект лекций. Санкт петербург 2011 2 Оглавление

• Название: Конспект лекций. Санкт петербург 2011 2 Оглавление
• Анкор: Вычислительная математика лекции.pdf
• Дата: 01.04.2017
• Размер: 3.86 Mb.
• Имя файла: Вычислительная математика лекции.pdf
• Тип: Конспект; #4404
• страница: 1 из 19

САНКТ- ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ
ПОЛИТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
А. Н. Кирсяев, В. Е. Куприянов.
ВЫЧИСЛИТЕЛЬНАЯ МАТЕМАТИКА.
КОНСПЕКТ ЛЕКЦИЙ.
САНКТ- ПЕТЕРБУРГ 2011

2
Оглавление
1.Введение. .................................................................................................... 9 1.1.Источники погрешностей. ............................................................. 9 1.2.Погрешность округления. .............................................................. 9 1.3.Особенности машинной арифметики ......................................... 10 1.4.Правила записи приближенных чисел........................................ 12 1.5.Корректность и обусловленность задач и алгоритмов. ............ 12 2.Конечные, разделенные разности и сеточные функции. ..................... 14 2.1. Конечные разности и их свойства. ................................................. 14 2.2.Разделенные разности и их свойства. ............................................. 16 3.Интерполирование функций. .................................................................. 21 3.1.Постановка задачи. Алгебраическое интерполирование. ............ 21 3.2.1 Интерполяционный полином в форме Лагранжа. ................... 22 3.2.2. Интерполяционный полином в форме Ньютона. ...................... 24 3.3.Остаточный член интерполяционного полинома. Оценка погрешности интерполирования. .................................................................... 25 3.4. Минимизация погрешности интерполирования. .......................... 25 3.5. Сходимость интерполяционного метода. ...................................... 27 3.6. Устойчивость интерполяционного полинома относительно погрешности вычисления y(x). ........................................................................ 29
3.7. Интерполяция сплайнами. .......................................................... 30 3.7.1.Обсуждение способа построения кубического интерполяционного сплайна с дефектом 1. ................................................... 31 3.7.2.B сплайны. ...................................................................................... 32

3 4.Среднеквадратичное приближение ........................................................ 33 4.1.Постановка задачи для f(x). .............................................................. 33 4.2.Постановка задачи для приближения векторов ............................. 34 4.3.Определения. .................................................................................. 35 4.4.Решение задачи. ............................................................................. 37 5.Ортогонализация ...................................................................................... 38 5.1.Постановка задачи ............................................................................. 38 5.2.Процедура построения системы ортогональных базисных элементов. ........................................................................................................... 38 6.Равномерное приближение функций. ..................................................... 40 7.ЧИСЛЕННОЕ ДИФФЕРЕНЦИРОВАНИЕ ........................................ 42 8.Численное интегрирование...................................................................... 45 8.1.Постановка задачи численного интегрирования ............................ 45 8.2. Квадратурные формулы с равноотстоящими узлами
(формулы Ньютона – Котеса). .......................................................................... 48 8.3.Составные квадратурные формулы. ................................................ 50 8.3.1.Простейшие составные квадратурные формулы. ....................... 51 8.3.1.1. Составная формула левых прямоугольников. ..................... 52 8.3.1.2. Составная формула правых прямоугольников. ................... 53 8.3.1.3. Составная формула трапеций. ............................................... 53 8.3.1.4. Составная формула Симпсона. ............................................. 55 8.4.Квадратурные формулы наивысшей степени точности
(формулы Гаусса). .............................................................................................. 55 8.5.Практическая оценка погрешности (правило Рунге). .................... 60

4 8.6.Адаптивные процедуры численного интегрирования. ................. 61 8.7.Обусловленность квадратурных формул интерполяционного типа. ................................................................................. 62 8.8.Примеры использования квадратурных формул. .......................... 63 8.9.Применение формул Ньютона- Котеса. ......................................... 66 8.10.Применение формул Гаусса. ......................................................... 68 8.11. Замечания о точности квадратурных формул. ........................... 69 9.Дополнительные элементы линейной алгебры и теории матриц ....... 70 9.1.Собственные числа и векторы. .................................................... 71 9.2.Решение системы линейных однородных уравнений с вырожденной матрицей. ............................................................................... 72 9.3.Подобное преобразование. .................................................................. 76 9.4.Приведение к канонической форме Жордана. ........................... 77 9.5.Вычисление матрицы преобразования. ...................................... 79 9.6. Функции от матриц. ............................................................................. 87 9.7.Многочлен Лагранжа – Сильвестра. .................................................. 89 9.8.Свойства матричной экспоненты. ....................................................... 92 9.9.Использование канонической формы Жордана при вычислениях матричных функций. ..................................................................... 92 9.10.Дифференциальные уравнения и матричная экспонента. .............. 94 9.11.Решение системы разностных уравнений. ....................................... 96 9.12.Матричные нормы. ............................................................................. 99 9.13.Устойчивость решений обыкновенных дифференциальных и разностных уравнений. ....................................................................................... 100 9.13.1. Основные понятия теории устойчивости. .......................... 100

5 9.13.2..Анализ устойчивости решения систем линейных обыкновенных дифференциальных уравнений с постоянными коэффициентами. ......................................................................................... 102 9.13.3.Анализ устойчивости решения систем линейных разностных уравнений с постоянными коэффициентами. ...................... 103 10.Численные методы решения обыкновенных дифференциальных уравнений ........................................................................... 105 10.1. Постановка задачи. ........................................................................... 105 10.2.Метод аналитического продолжения ( метод рядов). .................... 106 10.2.1.Методы Эйлера. .............................................................................. 109 10.2.3.Методы Рунге – Кутты. .................................................................. 112 10.2.4.Контроль точности методов Рунге – Кутты. ............................... 115 10.3. Методы эквивалентных интегральных уравнений ....................... 116 10.4. Свойство жесткости систем дифференциальных уравнений ....... 121 11.Решение систем линейных алгебраических уравнений. .................. 123 11.1.Постановка задачи. ........................................................................ 123 11.3.Обусловленность задачи решения системы линейных алгебраических уравнений. ............................................................................. 126 11.4.Прямые методы решения систем линейных алгебраических уравнений. ............................................................................. 128 11.4.1.Метод Гаусса и LU разложение. ............................................... 128 11.4.2.Метод Холецкого (метод квадратного корня). ........................ 135 11.4.3.QR разложение матрицы и решение систем линейных алгебраических уравнений. ............................................................................. 138

6 11.5.Сравнительный анализ вычислительной устойчивости прямых методов решения систем линейных алгебраических уравнений. ........................................................................................................ 141
11.6.Итерационные методы решения систем линейных
алгебраических уравнений. ................................................................................. 142 11.7.Решение линейных алгебраических систем с трехдиагональной матрицей методом прогонки. ........................................ 146 12.Методы отыскания решений нелинейных уравнений. .................... 148 12.1. Постановка задачи. ...................................................................... 148 12.2. Основные этапы решения. .......................................................... 148 12.3. Обусловленность задачи вычисления корня............................. 149 12.4. Методы отыскания решений нелинейных уравнений. ............ 151 12.4.1 Метод бисекции. ........................................................................ 151 12.4.2 Метод простых итераций. ......................................................... 152 12.4.3 Метод Ньютона. ........................................................................ 154
Доп. замечания. ..................................................................................... 158 13.Методы отыскания решений систем нелинейных уравнений. ....... 159 13.1. Постановка задачи. ...................................................................... 159 13.2. Разложение в ряд Тэйлора вектор - функции F=(f
1
, f
2
,…,f n
)
T
. ........................................................................................................ 160 13.3. Метод Ньютона. ....................................................................... 160 13.4. Метод простых итераций. ....................................................... 161 13.5. Упражнения. ............................................................................. 162 14. Методы решения проблемы собственных значений. ...................... 164 14.1. Постановка задачи. ...................................................................... 164

7 14.2.QR алгоритм .............................................................................. 166 14.3. Метод Якоби для действительных симметричных матриц. .......................................................................................................... 168 14.4. Степенной метод. ...................................................................... 169 14.5. Метод обратных итераций для вычисления собственных векторов. ....................................................................................................... 171 14.6. Упражнения. .............................................................................. 173 15.Введение в минимизацию функций. ................................................... 175 15.1.Минимизация функции одной переменной. ............................... 175 15.1.1. Постановка задачи. Определения. ........................................... 175 15.1.2. Метод деления отрезка пополам. ............................................. 176 15.1.3. Метод золотого сечения. ........................................................... 178 15.2.Введение в многомерную минимизацию. ............................... 180 15.2.1. Постановка задачи. .................................................................... 180 15.2.2. Поверхности уровня. Градиент и матрица Гессе.
Необходимые и достаточные условия локального минимума.................... 180 15.2.3. Задача минимизации квадратичной функции. ....................... 182 15.2.4. Обусловленность задачи минимизации. ................................. 184 15.2. 5. Понятие о методах спуска. ...................................................... 184 15.2.7. Градиентный метод. .................................................................. 186 15.2.7.1.Метод наискорейшего спуска. ........................................... 187 15.2.7.2. Метод сопряженных градиентов. ..................................... 189
Метод сопряженных градиентов в общем случае ........................ 191 15.2.8. Метод Ньютона. ......................................................................... 192

8 15.2.8.1. Простейший вариант метода Ньютона. ........................... 192 15.2.8.2. Метод Ньютона с дроблением шага. ............................... 193 15.2.8.3. Понятие о квазиньютоновских методах. ........................ 194 15.2.9. Метод Левенберга – Марквардта. ....................................... 196 16.Методы решения краевой задачи для линейных обыкновенных дифференциальных уравнений. ...................................... 197 16.1. Постановка задачи. ...................................................................... 197 16.2. Метод стрельбы (баллистический метод). ................................ 198 16.3. Разностный метод (метод конечных разностей). ................. 199 17.Сингулярное разложение и метод наименьших квадратов. ............ 200 17.1. Решение переопределенной системы уравнений. .................... 200 17.2. Сингулярное разложение матрицы. ........................................... 204 17.3. Метод наименьших квадратов с использованием сингулярного разложения. ............................................................................. 205 18. Псевдообратная матрица. ................................................................... 208
Псевдообратные матрицы ................................................................ 208
Пусть .................................................................................................. 208
Рекомендуемая литература ................................................................... 212

9
1.Введение
.
Вычислительная математика занимается разработкой численных методов решения математических задач. Численное решение содержит набор чисел с ограниченным количеством десятичных цифр и уже по этой причине всегда является приближенным. Это в свою очередь обусловливает необходимость анализа адекватности решения. (Как это сделать?).
1.1.Источники погрешностей.
Вычислительная математика имеет дело с математическими моделями исследуемых процессов и явлений. Наличие погрешностей обусловлено рядом причин:
1.Погрешность модели.
2.Погрешность исходных данных.
3.Методическая погрешность.
4.Вычислительная погрешность (погрешность округления).
1.2.Погрешность округления.
Имеем дело с вещественными числами, которые, как правило, представлены в форме с плавающей запятой:
, где β – основание системы исчисления; M- мантисса (0≤M<β), l- порядок числа.
Упрощенная структура машинного слова для хранения вещественных чисел имеет вид:
S
p
S
M
P
0
P
1
…. P
k-1
P
k
d
1
d
2
…… d
t
S
p
– код знака порядка;
S
M
– код знака мантиссы;

10 k+1 – количество разрядов порядка; t – количество разрядов мантиссы.
Множество хранимых чисел: fl(x) =
l
0 ≤ d i
≤ β-1; i= 1, …, t.
0 ≤ p j
≤ β-1; j = 0,…,k.
Обычно предполагают d
1
≠ 0 (нормированные системы).
Здесь x
R, а fl(x) F, F – множество чисел, хранимых в ЭВМ.
В отличие от R, F дискретно и содержит конечное число элементов, то есть существуют fl(x
1
), fl(x
2
)
F, между которыми нет элементов, принадлежащих F. Возникает относительная погрешность
Её максимальная величина носит название машинной точности
ε
M
≈ β
-t
. При компьютерных вычислениях получается
(1+ ε
M
)fl(x) = fl(x). Таким образом, уже в процессе ввода числа в
ЭВМ возникает относительная погрешность ε
M
Минимальное положительное число, представимое в ЭВМ, называется машинным нулем
0
M
;
. Если
, то fl(x) = 0
(исчезновение порядка).
Максимальное по модулю число, представимое в ЭВМ, называется машинной бесконечностью
. Если
, возникает переполнение разрядной сетки и вычисления аварийно останавливаются.
1.3.Особенности машинной арифметики
Пример 1. Пусть t = 8, тогда 10 8
+1 -10 8
= 0; 10 8
-10 8
+ 1 = 1.

11
Объяснение: машинное представление 10 8
=0.1 10 9
, 1 = 0.1 10 1
При сложении и вычитании порядки предварительно выравниваются.
То есть в 1-ом случае число 1 = 0.000000001 10 9
= 0
(единица младщего разряда оказывается за пределами разрядной сетки).
Аналогичные эффекты возникают при суммировании следующего ряда
. Пусть t = 3. Если вести сложение слева направо, получим 100. При сложении справа налево после сложения 1000 слагаемых получаем 100 и дальнейшее прибавление 0.1 не будет изменять результат. Конечное значение
200. Однако правильный результат 300 можно получить, если сложить 1000 чисел по 0.1, затем ещё 1000чисел по 0.1 и далее промежуточные суммы.
Вывод: при сложении следует располагать слагаемые в порядке возрастания абсолютных величин, стремясь, чтобы при каждом сложении порядки слагаемых мало отличались. При необходимости цикл суммирования разбивается на ряд более коротких циклов.
Аналогичное правило действует при перемножении большого числа сомножителей.
Пример 2. Пусть и вычисляем
; a=10
-30
, b=10
-
60
, c=10
-40
, d=10
-50
Если выполнить действия в порядке x=ab/c/d имеем исчезновение порядка.
Если вычислить x=1/c/dab, имеем переполнение.
Если вычислить x=(a/c)(b/d) получим x=1.
Вывод: при переполнении или исчезновении порядка следует попытаться изменить последовательность действий. При исчезновении порядка не всегда следует обнулять результат.

12