Численные методы (лекции)2013

Лекции по численным методам

Белоусов Григорий Николаевич

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