Конспект лекций (стр. 1 )

III семестр. ММФ НГУ

Численный анализ

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

– проф. кафедры вычислительной математики

2009 – 2010 учебный год

Предлагаем Вашему вниманию конспект лекций полусеместрового курса «Численный анализ», подготовленный профессором кафедры для студентов второго курса механико–математического факультета Новосибирского государственного университета и практически являющийся половиной семестрового курса лекций по численному анализу, подготовленному автором более 10 лет назад для студентов ВКИ НГУ, тексты которого NumAn. dvi и NumAn. pdf можно найти на сервере ММФ НГУ.

Мы надеемся, что этот конспект будет полезен студентам ММФ НГУ для более полного усвоения курса и применения методов вычислительной математики в их дальнейшей учебной, научно–преподавательской и практической деятельности.

Ограничений на использование и распространение конспекта – нет.

Любым замечаниям автор конспекта будет только рад и принимает их по адресу

E-mail: *****@

или

E-mail: *****@***ru

Содержание

Лекция 1............................................................................................................... 3

Алгебраические методы интерполирования.................................................. 3

Интерполяционный полином в форме Лагранжа....................................... 4

Интерполяционный полином в форме Ньютона......................................... 4

Расчетные формулы интерполяционного полинома в форме Ньютона.... 8

Оценка погрешности интерполирования.................................................... 9

Лекция 2............................................................................................................. 11

Интерполирование с кратными узлами........................................................ 11

Представление интерполяционного полинома Эрмита в форме Лагранжа 12

Представление интерполяционного полинома Эрмита в форме Ньютона 13

Оценка погрешности интерполирования.................................................. 17

Лекция 3............................................................................................................. 18

Интерполирование кубическим сплайном.................................................... 18

Определение и построение кубического сплайна..................................... 18

Оценка погрешности.................................................................................. 20

Численное дифференцирование.................................................................... 22

Оценка погрешности численного дифференцирования............................ 22

Аппроксимация значения функции в центре интервала полусуммой ее значений на краях интервала.......................................................................................... 24

Аппроксимация производной разностью вперед.................................... 24

Аппроксимация производной разностью назад...................................... 25

Аппроксимация производной центральной разностью........................... 25

Некорректность численного дифференцирования.................................... 25

Лекция 4............................................................................................................. 27

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

Квадратуры Гаусса наивысшей алгебраической степени точности......... 28

Сходимость квадратур Гаусса................................................................... 31

Устойчивость квадратурных формул........................................................ 31

Примеры квадратурных формул.................................................................. 32

Формулы прямоугольников (на одном узле)............................................ 33

Формула трапеций (на двух узлах)........................................................... 34

Формула Симпсона (на трех узлах).......................................................... 34

Квадратура Гаусса на двух узлах............................................................. 35

Составные квадратурные формулы.............................................................. 35

Составные формулы прямоугольников на равномерной сетке............... 36

Составная формула трапеций на равномерной сетке............................... 37

Составная формула Симпсона на равномерной сетке.............................. 38

Лекция 5............................................................................................................. 39

Итерационные методы решения нелинейных уравнений............................ 39

Принцип сжимающих отображений.......................................................... 40

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

Метод Эйткена ускорения сходимости метода простой итерации........... 45

Лекция 6............................................................................................................. 49

Метод Ньютона.............................................................................................. 49

Случай простого корня: ................................................................... 51

Метод Ньютона с параметром................................................................... 56

Литература........................................................................................................ 57

Лекция 1.

Алгебраические методы интерполирования

Задача интерполирования функции на интервале состоит в том, чтобы по известным ее значениям в некоторых точках , определить ее значения в остальных точках области задания функции.

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

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

Определение 1.

Алгебраический полином

(1)

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

. (2)

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

Теорема 1. Задача алгебраической интерполяции (2) при имеет единственное решение.

Доказательство.

Перепишем систему (2) относительно неизвестных коэффициентов полинома в векторно-матричной форме:

(3)

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

Интерполяционный полином в форме Лагранжа

Теорема 2. Решение задачи алгебраической интерполяции (2) при представимо в форме Лагранжа

, (4)

где

. (5)

Доказательство.

Для каждого рассмотрим частный случай задачи алгебраического интерполирования:

Так как полином степени по условию имеет корней:

,

то он может быть представлен в виде произведения мономов:

, (6)

где постоянная определяется из условия :

.

Легко проверить, что этот полином можно переписать в следующем виде:

(7)

Очевидно, что линейная комбинация полиномов с весами является полиномом степени и, так как

то она является интерполянтом функции .

Интерполяционный полином в форме Ньютона

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

Можно ли подправить уже вычисленную таблицу значений , т. е. добавить к ней поправку ?

Так как разность является полиномом степени и имеет столько же корней: , то она представима в виде

(8)

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

или, с учетом интерполяционного условия :

. (9)

Итак, мы можем подправить таблицу значений , добавив к ней поправку (8) при (предварительно вычислив по формуле (9)):

,

что значительно быстрее (оцените), чем вычисление по формуле

.

Из формулы (8) следует, что интерполяционный полином на узлах может быть представлен в виде

(10)

Определим через значения интерполируемой функции в узлах коэффициенты формулы (10).

Так как , то из формулы (9) при получаем явную формулу для :

.

Определение 2.

Разделенной разностью первого порядка функции на узлах называется число

.

Очевидно, что разделенная разность является симметрической функцией:

,

а интерполяционный полином можно представить в форме (Ньютона):

. (11)

Добавим новый узел и найдем постоянную в представлении (форма Ньютона) интерполяционного полинома :

Из условия :

,

имеем

Определение 3.

Разделенной разностью второго порядка функции на попарно различных узлах называется число

Очевидно, что эта разделенная разность является симметрической функцией:

.

Итак, интерполяционный полином функции на попарно различных узлах можно представляется в виде

. (12)

Полученные формулы (11) и (12) позволяют предположить, что интерполяционный полином функции на попарно различных узлах можно представить в форме Ньютона:

где − разделенные разности -го порядка функции на попарно различных узлах .

Определение 4.

Разделенной разностью -го порядка функции на попарно различных узлах называется число

.

Лемма 1. Для разделенной разности -го порядка функции на попарно различных узлах справедлива следующая формула:

.

Доказательство.

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

Предлоложим, что лемма справедлива при и докажем ее для .

Из определения разделенной разности -го порядка и сделанного предположения математической индукции следует, что

что и требовалось доказать.

Лемма 2. Коэффициент из (9) (при ) равен разделенной разности -го порядка функции на попарно различных узлах , т. е.:

.

Доказательство.

Так как

то утверждение леммы является следствием леммы 1.

Теорема 3. Решение задачи алгебраической интерполяции (2) при функции на попарно различных узлах представимо в форме Ньютона:

,

где − разделенные разности -го порядка функции на попарно различных узлах .

Утверждение теоремы является следствием формулы (10) и леммы 2.

Расчетные формулы интерполяционного полинома в форме Ньютона

Расчетные формулы интерполяционного полинома в форме Ньютона:

1.  Сначала заполняем таблицу значений разделенных разностей:

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

2.  Затем для любого значения вычисляем значение по схеме Горнера:

за арифметических действий.

Оценка погрешности интерполирования

Определение 5.

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

.

Очевидно, что .

Лемма 3. Если и не совпадает ни с одним интерполяционным узлом , то

,

где .

Доказательство.

Интерполяционный полином функции по ее значениям в попарно различных узлах представим в форме Ньютона:

.

Тогда, так как , получим , что и требовалось доказать.

Лемма 4. Если функция ( раз непрерывно дифференцируема на отрезке ), то

для некоторой точки .

Доказательство.

Прежде всего продифференцируем раз ошибку интерполяции:

.

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

Не уменьшая общности, будем считать, что узлы интерполяции упорядочены по возрастанию: .

Погрешность имеет различный корень, так как .

Тогда по теореме о среднем значении ее первая производная будет иметь хотя бы один корень внутри каждого интервала : .

Следовательно, имеет различных корней, так как .

Аналогично получим, что

имеет не менее различных корней ,

…

имеет не менее различных корней ,

…

имеет не менее одного корня , что и требовалось доказать.

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

,

где .

Доказательство.

Если совпадает с одним из узлов интерполирования, то, утверждение леммы очевидным образом верно для любого .

Если не совпадает ни с одним из узлов интерполирования, то утверждение леммы является следствием леммы 3 и леммы 4.

Задача. Оценить , если , .

Элементарное решение: Если , , то

Лекция 2.

Интерполирование с кратными узлами

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

Определение 1.

Алгебраический полином

(1)

называется интерполяционным полиномом Эрмита для функции , заданной на отрезке по ее значениям , по значениям первых производных , …, в попарно различных точках (узлах) , если

(2)

Точки называются узлами интерполяции кратности .

Теорема 1. Задача алгебраической интерполяции (2) при имеет единственное решение.

Доказательство.

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

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

Предположим, что теорема неверна: система уравнений (2) либо не имеет решения, либо имеет несколько решений. Значит однородная система (2) имеет ненулевое решение , определяющее ненулевой полином степени и удовлетворяющий условиям

.

Отсюда следует, что узел является его корнем кратности , а, так как интерполяционные узлы попарно различны, то

,

т. е. является полиномом степени , что противоречит условию теоремы .

Следовательно, наше предположение ложно и теорема верна.

Представление интерполяционного полинома Эрмита в форме Лагранжа

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

, (3)

где полином степени определяется условиями