num-meth

2

Благодарности. Данный текст подготовлен при участии многих людей. Выражается благодарность студентам потока К7 различных лет за отзывы, предложения и непосредственное участие в наборе текста. Особая благодарность выражается Александру Эйдлину (2008 г.) и, в особенности, Евгению Григоренко (2011 г.), который проделал большую работу по улучшению качества текста. Также выражается благодарность преподавателям и аспирантам кафедры 22 за отзывы, предложения, советы, критику и просто поддержку: М.И. Аршавскому, Виктору Назарову, Андрею Лаптеву, Алексею Мозгачеву, Леониду Бесчасному, Леониду Шумскому, проф. В.Э. Вольфенгагену.

3.1.3Интегрирование с помощью составных квадратурных формул НьютонаКотеса. Составные квадратурные формулы трапеций и Симпсона . . 73

3.1.4Соотношения между формулами прямоугольников, трапеций и Симп-

3.1.6Квадратурные формулы Чебышева и Гаусса . . . . . . . . . . . . . . . 77

3.2Аппроксимация производных . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

3.2.1Вывод формул численного дифференцирования . . . . . . . . . . . . . 79

3.2.2Остаточные члены простейших формул численного дифференциро-

вания . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

3.2.3Простейшие аппроксимации второй производной. . . . . . . . . . . . . 83

3.2.4Оптимизация шага численного дифференцирования при ограниченной точности значений функции . . . . . . . . . . . . . . . . . . . . . . 86

4 Численные методы решения обыкновенных дифференциальных уравне-

4.1Методы Эйлера и Рунге-Кутты решения начальных задач для ОДУ . . . . . 91

4.1.1Постановка задачи. Классификация приближенных методов . . . . . 91

4.1.2Метод Эйлера – разные подходы к построению . . . . . . . . . . . . . 93

4.2О семействе методов Рунге-Кутты. Методы второго порядка . . . . . . . . . 97

4.2.1Методы Рунге-Кутты произвольного и четвертого порядков . . . . . . 99

4.3.1Многошаговые методы Адамса . . . . . . . . . . . . . . . . . . . . . . . 101

4.3.2Методы прогноза и коррекции. Предиктор-корректорные методы Адам-

са . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104

4.3.3Метод Милна четвертого порядка . . . . . . . . . . . . . . . . . . . . . 106

4.3.4Общий вид линейных многошаговых методов. Условия согласованности108

4.3.5О численном решении систем дифференциальных уравнений первого порядка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

4.3.6Численное решение дифференциальных уравнений высших порядков. Методы Адамса-Штермера . . . . . . . . . . . . . . . . . . . . . . 113

4.4О проблемах численной устойчивости . . . . . . . . . . . . . . . . . . . . . . . 117

4.4.1Общая схема решения задач численного анализа. . . . . . . . . . . . . 117

4.4.2Простейшие разностные аппроксимации задачи Коши . . . . . . . . . 119

4.4.3Жесткие уравнения и системы . . . . . . . . . . . . . . . . . . . . . . . 129

4.5Методы приближенного решения краевых задач для обыкновенных дифференциальных уравнений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134

4.5.1Постановка задачи. Классификация приближенных методов . . . . . 134

4.5.2Методы сведения краевых задач к начальным . . . . . . . . . . . . . . 135

4.5.3Метод конечных разностей . . . . . . . . . . . . . . . . . . . . . . . . . 139

4.5.4Метод коллокации . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142

4.5.5 Метод Галеркина . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145

4.5.6Метод конечных элементов . . . . . . . . . . . . . . . . . . . . . . . . . 148

Введение

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

Пример одной из первых и широко известных, а также до сих пор актуальных задач, в которых используются численные методы, – нахождением приближенных значений корней полиномиальных уравнений. Как известно, для полиномиальных уравнений порядка выше пятого решения в общем не существует. А решение в общем виде уже для уравнений третьей степени довольно громоздко. Один простейших способов приближенного вычисления корней полиномиальных уравнений – это метод Ньютона, заключающийся в том, что сначала выделяется интервал, на котором находится ровно один из искомых корней решаемого уравнения. Далее, выбирается произвольная точка на этом интервале и вычисляется уравнение касательной к кривой исследуемой функции. Точка пересечения касательной и один из концов исходного интервала образуют новый интервал, на котором содержится ровно один корень решаемого уравнения. Процесс повторяется итеративно, до тех пор, пока длина отрезка не станет меньше некоторой заранее заданной, достаточно малой, величины ε > 0, которая характеризует необходимую точность вычислений.

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

1.1.2Линейные пространства векторов и матриц

Непустое множество L элементов x, y, z, . . . называется линейным пространством, если оно удовлетворяет таким условиям:

1.Для любых двух элементов x, y L однозначано определен третий элемент z L, называемый их суммой и обозначаемый x + y, причем

(a)x + y = y + x (коммутативность),

(b)x + (y + z) = (x + y) + z (ассоциативность),

(c)в L существует такой элемент 0, что x + 0 = x для всех x L (существование нуля),

(d)для каждого x L существует такой элемент −x, что x + (−x) = 0 (существование противоположного элемента).

2.Для любого числа α и любого элемента x L определен элемент αx L (произведение элемента x на число α), причем

(a)α(βx) = (αβ)x,

(b)1 · x = x,

(c)(α + β)x = αx + βx,

(d)α(x + y) = αx + αy,

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

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

1.1.3Метрика. Норма векторов и матриц

Пусть дано действительное линейное пространство L. Каждому вектору x L поставим в соответствие действительное число x и назовем его нормой вектора x, если для любых векторов x, y L и любого действительного числа α выполняются следующие аксиомы нормы:

1.x > 0, причем x = 0, только, если x = 0.

2.αx = |α|x .

3.x + y ≤ x + y . (правило треугольника)

Линейное пространство L при этом называется нормированным пространством.

Ввекторном пространстве Rn наиболее употребительными являются:

1.октаэдрическая норма

∑n

x 1 = |xk| ;

k=1

В линейном пространстве (m × n)-матриц также рассматриваются различные нормы. Наиболее употребительными матричными нормами являются:

В линейном пространстве квадратных матриц порядка n кроме линейных операций важную роль играет операция умножения матриц. В связи с этим в этом линейном пространстве предпочтение отдают нормам, согласованным с операцией умножения, а именно:

AB ≤ A · B .

При этом норму матриц, не подчиняющемуся этому неравенству, иногда называют обобщенной нормой матриц.

Каждую (m × n)-матрицу A можно интерпретировать как оператор, действующий из n-мерного векторного пространства Rn в m-мерное пространство Rm по формуле y = Ax, x Rn, y Rm. Если в Rn и Rm введены нормы, то желательно рассматривать норму матриц размера m × n, согласованную с векторными нормами в Rn и Rm:

Ax ≤ A · x .

Примером такой нормы является матричная норма, индуцированная векторной нормой (или подчиненная векторной норме):

1.1.4Последовательности матриц и степенные матричные ряды

Последовательности (1.1) матриц Ak, имеющую предел, называют сходящейся. Сходимость последовательности матриц, по определению, равносильна их поэлементной сходимости. Докажем это.

Теорема 1. Для сходимости последовательности (1.1) матриц Ak необходимо и достаточно, чтобы при какой-либо матричной форме · выполнялось соотношение

Отсюда следует, что матрица |A−Ak|,составленная из модулей |aij −a(ijk)|, удовлетворяет неравенству

где J − (m × n) - матрица, каждый элемент которой равен единице. Потому

Обратно, пусть выполняется условие (1.3). Тогда при k > N(ε) будет выполняться соотношения

Следствие. Последовательность (1.1) матриц Ak сходится к нулевой матрице тогда и только тогда, когда