Численные методы (лекции)2013
.pdfЛекции по численным методам
Белоусов Григорий Николаевич
1. Лекция 1
Типы погрешностей:
1)Неустранимая погрешность. Математическое описание задачи является не точным, в частности не точно заданы исходные данные.
2)Погрешность метода. Применяемый для решения метод часто не является точным.
3)Вычислительная погрешность. При вводе данных в машину, при выполнении арифметических операций и при выводе данных производится округление.
1.1.Представление чисел в ЭВМ.. При ручном счете поль-
зуются десятичной записью числа, т.е. x = ±a1a2 . . . an, an+1an+2 . . ..
Это означает
x = ±(a1 · 10n−1 + a2 · 10n−2 + · · ·+ an + an+1 · 10−1 + an−2 · 10−2 + · · ·).
Заметим, что существует две записи десятичного числа, а именно с нулями на бесконечности и с девятками на бесконечности, т.е.
1 = 1, 000 . . . = 0, 9999 . . ..
ЭВМ работает, как правило, в двоичной системе, т.е. x представляется последовательностью нулей и единиц (например
x= 10011, 01011). Другими словами,
x = ±(a1 · 2n−1 + a2 · 2n−2 + · · · + an + an+1 · 2−1 + an−2 · 2−2 + · · · ),
где ai = 0, 1. В позиционной системе исчисления с основанием r
запись
x = ±a1a2 . . . an, an+1an+2 . . .
означает
x = ±(a1 · rn−1 + a2 · rn−2 + · · · + an + an+1 · r−1 + an−2 · r−2 + · · · ),
где ai = 0, 1, . . . , r −1. Такое представление числа называется представлением числа в форме числа с фиксированной запятой. В ЭВМ чаще всего используется представление числа с плавающей запятой, т.е. в виде
x = M · rn,
где r основание системы исчисления, n целое число, r−1 ≤ M < 1. Число M называется мантиссой числа a. Число n называется порядком числа a.
Минимальное положительное число, которое можно представить в ЭВМ называется машинным нулем.
1
Определение 1.1. Пусть a точное значение некоторой величины, а a известное приближение к нему, то абсолютной погрешностью приближенного значения a называют величину Δ(a ), про которую известно, что
|a − a| ≤ Δ(a ).
Относительной погрешностью приближенного значения a называют величину δ(a ), про которую известно, что
a − a
≤ δ(a ).
a
Если a известное число, то относительной погрешностью часто называют величину δ(a), про которую известно, что
a − a
≤ δ(a).
a
2.Лекция 2
2.1.Постановка задачи приближения функций. Простейшая задача, приводящая к приближению функций, заключает-
ся в следующем. В дискретном множестве точек x1, . . . , xn мы знаем значение f (x). Требуется восстановить значения функции f при
других x. Пусть f (x) ≈ g(x, a1, . . . , an). Если параметры a1, . . . , an определяются из условий совпадения f и g в точках x1, . . . , xn,
то такой способ приближения называется интерполяцией. Точки x1, . . . , xn называются узлами интерполяции.
2.2. Интерполяционный многочлен Лагранжа. Предположим, что g = Lm алгебраический многочлен степени m т.е.
Lm = a0 + a1x + a2x2 + · · · + amxm.
Запишем условия равенства Lm(xi) = f (xi). Получим,
a0 |
+ a1x1 |
+ · · · + amx1m |
= f (x1) . |
|
|
a0 |
+ a1x0 |
+ · · · + amx0m |
= f (x0) |
|
· · ·· · · · · · · · · · · · |
|
||
|
|
|
|
|
|
|
|
m |
= f (xn) |
a0 + a1xn + · · · + amxn |
||||
|
|
|
|
|
Таким образом, мы получили n + 1 уравнений с m + 1 неизвестным. Для того, что бы это уравнение имело единственное решение должно выполнятся m = n.
2
Интерполяционная формула Лагранжа позволяет представить многочлен Ln−1 в виде
n
X
Ln(x) = ck (x)f (xk ),
k=0
где ck (x) многочлены степени n такие, что
(
1, если k = i
ck (xi) = .
0, если k 6= i
Другими словами многочлен ck (x) имеет n − 1 корень x0, . . . xk−1, xk+1, . . . , xn. Таким образом,
ck(x) = A(x − x0)(x − x1) · · ·(x − xk−1)(x − xk+1) · · · (x − xn).
Число A найдем из условия ck(xk ) = 1 т.е.
1
A = (xk − x0)(xk − x1) · · ·(xk − xk−1)(xk − xk+1) · · · (xk − xn) .
2.3. Интерполяционная формула Ньютона. Разделенными разностями первого порядка называются выражения вида
f (xi; xj ) = f (xj ) − f (xi) . xj − xi
Разделенными разностями второго порядка называются выражения вида
f (xi; xj ; xk ) = f (xj ; xk) − f (xi; xj ) . xk − xi
Далее, мы можем дать индуктивное определение разделенных разностей n-го порядка. Разделенными разностями n-го порядка называются выражения вида
f (x1; x2; . . . ; xn+1) = |
f (x2; . . . ; xn+1) − f (x1; x2; . . . ; xn) |
. |
|
||
|
xn+1 − x1 |
Лемма 2.1. Имеет место равенство
|
n |
f (xj ) |
|
|
X |
||
f (x1; x2; . . . ; xn) = |
|
. |
|
|
i=6 j (xj − xi) |
||
|
j=1 |
Q |
|
|
|
|
Доказательство. Доказательство будем проводить по индукции. При n = 2 это следует из определения. Предположим, что мы
3
доказали это равенство для n − 1. Тогда
f (x1; x2; . . . ; xn) = f (x2; . . . ; xn) − f (x1; . . . ; xn−1) xn − x1
1 |
n |
f (xj ) |
n−1 |
||
X |
X |
||||
|
|
− |
|||
xn − x1 |
|
i=6 j,i≥2(xj − xi) |
|
||
|
j=2 |
Q |
j=1 |
||
|
|
|
=
!
f (xj )
Q
i=6 j (xj − xi)
При j 6= 1, n коэффициент при f (xj ) равен
|
xn − x1 j=2 |
i=6 j,i≥2(xj − xi) − j=1 |
i=6 j (xj − xi) ! = |
|
||||||||
1 |
n |
1 |
|
n−1 |
1 |
|
|
|
||||
|
|
X |
|
|
|
X |
|
|
|
|
|
|
|
|
Q |
|
(xj − x1) − (xj −Q n) |
|
|
1 |
|
||||
|
|
|
|
|
|
|
x |
|
= |
|
|
, |
|
|
|
|
n |
= 1 |
|
|
n |
||||
|
|
|
|
Q |
|
|
|
Q1 |
|
|||
|
|
|
|
(xn − x1) i=6 j,i=1(xj − xi) |
i=6 j,i=1(xj − xi) |
|
||||||
т.е. имеем требуемый вид. Если j |
|
значение f (x ) входит только |
во второе слагаемое, и коэффициент при нем также имеет требуемый вид. Аналогично с f (xn).
Теорема 2.2. Имеет место интерполяционная формула Ньютона
Ln(x) = f (x0)+f (x0; x1)(x−x0)+f (x0; x1; x2)(x−x0)(x−x1)+· · ·+ + f (x0; x2; . . . ; xn)(x − x0)(x − x1) · · · (x − xn−1).
Доказательство. Заметим, что
n
X
Ln(x) = L0(x) + (Li(x) − Li−1(x)),
i=1
где Li(x) интерполяционный многочлен Лагранжа, построен-
ный по точкам x0, x1, . . . , xi. Рассмотрим разность Li(x) − Li−1(x). Заметим, что Li(x) − Li−1(x) многочлен степени i с корнями
x0, x1, . . . , xi−1. Таким образом,
Li(x) − Li−1(x) = Ai(x − x0)(x − x1) · · · (x − xi−1).
Найдем коэффициент Ai. Подставим x = xi. Получим,
f (xi) − Li−1(xi) = Ai(xi − x0)(xi − x1) · · ·(xi − xi−1),
так как Li(xi) = f (xi). Отсюда,
f (xi) − Li−1(xi)
Ai = (xi − x0)(xi − x1) · · ·(xi − xi−1) .
4
подставим выражение для Li−1(xi):
Li−1(xi) = |
i−1 |
(xi − x0)(xi − x1) · · · (xi − xk−1)(xi − xk+1) · · ·(xi − xn) . |
|||||||||||
|
|
f (xk)· |
|||||||||||
|
|
|
|
X |
|
|
|
|
|
|
|
||
|
|
|
|
k=0 |
(xk − x0)(xk − x1) · · · (xk − xk−1)(xk − xk+1) · · ·(xk − xn) |
||||||||
|
|
|
|
|
|
|
|
|
|
|
|||
Тогда получим |
|
|
|
|
|
|
|
||||||
Ai = |
|
|
|
|
f (xi) |
− |
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|||||
(xi − x0)(xi − x1) · · · (xi − xi−1) |
|
|
|
|
|||||||||
i−1 f (xk ) |
· |
|
|
|
1 |
= |
|
||||||
X |
|
|
|
|
|
|
|
|
|
|
|
||
|
xi − xk (xk − x0)(xk − x1) · · ·(xk − xk−1)(xk − xk+1) · · · (xk − xi−1) |
||||||||||||
k=0 |
|
|
|
|
|
|
|
|
|
|
|||
|
|
i |
|
|
|
f (xk ) |
|
|
|
|
|||
|
X |
|
|
|
|
. |
|||||||
|
|
|
|
|
|
|
|
||||||
|
|
|
(xk − x0)(xk − x1) · · · (xk − xk−1)(xk − xk+1) · · ·(xk − xi) |
||||||||||
|
k=0 |
|
|
|
|
|
|
|
|
|
|
||
Согласно |
|
|
лемме |
2.1 Ai |
разделенная |
разность, |
Ai = f (x0; x1; . . . ; xi). Поскольку L0(x) = f (x0) мы получаем
Ln(x) = f (x0)+f (x0; x1)(x−x0)+f (x0; x1; x2)(x−x0)(x−x1)+· · ·+ + f (x0; x2; . . . ; xn)(x − x0)(x − x1) · · · (x − xn−1).
3. Лекция 3
Как оценить качество приближения функции?
Введем понятие нормы функции. Нормой называется такая функция на множестве функций (функционал) ||f ||, удовлетворяющая следующим условиям:
•||f || ≥ 0;
•||αf || = |α|||f ||, α R;
•||f + g|| ≤ ||f || + ||g||.
Здесь, в качестве нормы мы выберем
||f || = sup |f |,
D
где D некоторое множество (например D = [a; b], R, R+).
Мы хотим приблизить функцию f функцией g так, чтобы норма ||f − g|| была минимальной.
5
3.1. Погрешность |
интерполирования. Мы |
пред- |
полагаем, что f (x) |
n раз дифференцируема. |
Пусть |
ϕ(x) = f (x) −Ln(x) −Kω(x), где ω(x) = (x −x0 )(x −x1 ) · · · (x −xn). Выберем произвольное x =6 x0, x1, . . . xn. Выберем такое K, что
ϕ(x) = 0. Тогда
K= f (x) − Ln(x) . ω(x)
Заметим, что ϕ(x) имеет по крайней мере n + 2 корня (x, x0, x1, . . . , xn). Тогда, по теореме Ролля, ϕ′(x) имеет n + 1 корень, ϕ′′(x) n корней и т.д. Таким образом, ϕ(n+1) имеет по крайней мере один ноль на отрезке [a; b], где a = min{x, x0, x1, . . . , xn}, b = max{x, x0, x1, . . . , xn}. Следовательно, существует ξ [a; b] такое, что
0 = ϕ(n+1)(ξ) = f (n+1)(ξ) − L(nn+1) − Kω(n+1)(x).
Заметим, что L(nn+1) ≡ 0, ω(n+1)(x) = (n + 1)!. Отсюда, K = Тогда
f (n+1)(ξ)
f (x) − Ln(x) = (n + 1)! ω(x).
Пусть Mn+1 = supξ [a;b] |f (n+1)(ξ)|. Тогда
|f (x) − Ln(x)| ≤ Mn+1 ω(x).
(n + 1)!
Рассмотрим выражение f (x) − Ln(x):
f (n+1) (ξ) (n+1)! .
f (x) − Ln(x) = f (x) − f (x0) · |
(x − x1)(x − x2) · · ·(x − xn) |
|
− |
|
(x0 − x1)(x0 − x2) · · · (x0 − xn) |
||||
|
|
f (x1) · |
(x − x0)(x − x2) · · ·(x − xn) |
− · · · − f (xn)· |
|
(x1 − x0)(x1 − x2) · · ·(x1 − xn) |
|||
|
|
|
(x − x0)(x − x1) · · ·(x − xn−1) |
|
= (x − x0)(x − x1) · · · (x − xn)· |
|
|
(xn − x0)(xn − x1) · · ·(xn − xn−1) |
|||
(x − x0)(x − x1) · · · (x − xn) − (x − x0)(x0 |
− x1)(x0 0− x2) · · ·(x0 − xn) |
|||
|
f (x) |
|
f (x ) |
f(x1)
−(x − x1)(x1 − x0)(x1 − x2) · · ·(x1 − xn) − · · · −
f (xn)
(x − xn)(xn − x0)(xn − x0) · · ·(xn − xn−1)
6
Поменяем местами слагаемые в скобках (x − xi) и применим лемму 2.1. Получим
(x − x0)(x − x1) · · ·(x − xn) · (x − x0)(x − x1) · · ·(x − xn) + |
|||
|
|
|
f (x) |
f (x0) |
+ |
f (x1) |
|
(x0 − x)(x0 − x1)(x0 − x2) · · · (x0 − xn) |
(x1 − x)(x1 − x0)(x1 − x2) · · · (x1 − xn) |
+· · ·+ (xn − x)(xn − x0)(xn − x0) · · ·(xn − xn−1) |
= f (x; x0; x1; . . . ; xn)·ω(x). |
||||
|
f (xn) |
|
|
|
|
Отсюда, |
|
|
|
|
|
|
|
f (n+1)(ξ) |
|
||
|
f (x; x0; x1; . . . ; xn) = |
|
. |
|
|
|
(n + 1)! |
|
3.2. Многочлены Чебышева.
Определение 3.1. Многочлены Чебышева Tn(x), определяются следующими соотношениями:
T0(x) = 1, T1(x) = x,
Tn+1(x) = 2xTn(x) − Tn−1(x).
Теорема 3.2. Имеет место следующее представление многочленов Чебышева при −1 ≤ x ≤ 1:
Tn(x) = cos(n arccos x).
Доказательство. Из формулы
cos x cos y = 12 (cos(x + y) + cos(x − y))
следует
cos((n + 1)θ) = 2 cos θ cos nθ − cos((n − 1)θ).
Подставим θ = arccos x, получим
cos((n + 1) arccos x) = 2x cos n arccos x − cos((n − 1) arccos x).
Следовательно, cos(n arccos x) удовлетворяет рекуррентному соотношению в определении 3.4. Осталось проверить справедливость
равенства Tn(x) = cos(n arccos x) для n = 0, 1. При n = |
0 |
T0(x) = cos 0 = 1. При n = 1 T1(x) = cos(arccos x) = x. |
|
Следствие 3.3. При всех x [−1; 1] имеет место неравенство
|T (x)| ≤ 1.
7
Из уравнения
Tn(x) = cos(n arccos x) = 0
получаем xm = cos( (2m−1)π ), m = 1, . . . n нули Tn(x).
n
ки экстремума. В этих точках |Tn(x)| = 1, т.е. x˜m = m = 0, 1, 2, . . . n. Причем Tn(˜xm) = cos mπ = (−1)m.
¯ |
1 |
|
n |
|
Многочлены Tn(x) = |
2n−1 |
Tn(x) = x |
|
+ . . ., n ≥ 1 |
многочленами, наименее уклоняющимися от нуля.
Теорема 3.4. Пусть Pn(x) многочлен степени n коэффициентом 1, то
Найдем точcos( mπn ), где
называются
со старшим
|
¯ |
|
1 |
|
max |P(x)| ≥ max |Tn(x)| = |
2n−1 |
. |
||
[−1;1] |
[−1;1] |
|
|
|
Доказательство. Предположим |
противное. Многочлен |
¯ |
|
|
|
|
|
|
|
|
|
Tn(x) − Pn(x) имеет степень n − 1. С другой стороны, поскольку |
|||||||||
|Pn(x)| < |
1 |
, |
|
|
|
|
|
|
|
n−1 |
|
|
|
|
|
|
|
||
2 |
|
|
|
|
|
|
|
|
|
¯ |
|
|
|
|
m |
1 |
|
m |
|
sign(Tn(˜xm) − Pn(˜xm)) = sign((−1) |
|
2n−1 |
− Pn(˜xm)) = (−1) |
|
. |
||||
Следовательно, многочлен |
¯ |
|
|
|
имеет корень на каж- |
||||
Tn(x) − Pn(x) |
|||||||||
дом интервале (˜xm; x˜m+1). Тогда |
|
|
|
¯ |
име- |
||||
многочлен Tn(x) − Pn(x) |
ет n различных нулей. Это невозможно, т.к. степень многочлена
¯ |
|
|
|
|
|
Tn(x) − Pn(x) равна n − 1. |
|
|
|
|
|
′ |
a+b |
+ |
b−a |
x отрезок [−1; 1] |
можно пере- |
Линейной заменой x = |
2 |
2 |
вести в отрезок [a; b]. В соответствии с теоремой 3.4 можно утвер-
ждать, что многочлен |
|
|
|
T¯n[a;b] = (b − a)n 22n−1 Tn |
b − a |
||
1 |
|
2x − (b + a) |
|
со старшим коэффициентом 1 является многочленом, наименее уклоняющимся от нуля на отрезке [a; b].
3.3. Минимизация погрешности интерполирования. По-
скольку ω(x) = (x − x0)(x − x1) · · ·(x − xn) многочлен, степени n+1 со старшим коэффициентом 1, то выберем узлы интерполяции
xm = |
2 |
+ |
2 |
cos |
|
|
2n |
, m = 1, . . . n. |
||||
|
|
a + b b − a |
|
|
π(2m − 1) |
|
|
|||||
Тогда |
|
|
|
|
|
|
|
|
|
|
|
|
ω(x) = (b − a)n 22n−1 Tn |
|
|
b − a |
|
||||||||
|
|
|||||||||||
|
|
|
|
|
1 |
|
|
|
2x − (b + a) |
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
8
и |
|
|
|
|
1 |
|
|
|
|
|
||ω(x)|| = (b − a)n |
. |
|
||
|
|
|
|
|
|||
|
|
|
22n−1 |
|
|||
|
|
|
|
|
|
|
|
Отсюда, |
|
|
|
|
|
|
|
|
|
||f (x) − Ln(x)|| ≤ |
Mn+1(b − a)n |
, |
|||
|
|
22n−1 · n! |
|||||
где M |
= sup |
[a;b] |
|f (n+1)(x)|. |
|
|
|
|
n+1 |
|
|
|
|
|
|
4.Лекция 4
4.1.Интерполирование с кратными узлами. Пусть в узлах xk заданы значения функции f (xk ) и ее производных f (i)(xk ), где i = 1, . . . , Nk − 1. Число Nk называется кратностью узла xk . Требуется построить многочлен Hn(x) степени n = N0+N1+· · ·+Nm такой, что
H(i)(xk ) = f (i)(xk ).
Такой многочлен называется интерполяционным многочленом Эрмита. Имеет место формула
m Nk −1
X X
Hn(x) = |
ckif (i)(xk ), |
k=0 |
i=0 |
где cki(x) многочлены степени n, удовлетворяющие условию
cki (xl ) = |
(0, если k =6 l или i =6 j . |
(j) |
1, если k = l, i = j |
Оценим погрешность интерполирования многочленами Эрмита. Пусть
ϕ(x) = f (x) − Hn(x) − Kω(x),
где ω(x) = (x − x0)N0 (x − x1)N1 · · · (x − xm )Nm . Функция ϕ(x) имеет n + 2 корня (с учетом кратностей) на отрезке [a; b]. Аналогично,
по теореме Ролля, ϕ(n+1)(x) имеет корень на отрезке [a; b]. Следовательно,
f (n+1)
f (x) − Hn(x) = (n + 1)! (x − x0)N0 (x − x1)N1 · · · (x − xm)Nm .
Тогда
|f (x) − Hn(x)| ≤ Mn+1 |ω(x)|,
(n + 1)!
где Mn+1 = sup[a;b] |f (n+1)(x)|.
9