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

Мы будем искать	следующее	приближение в
f (x0) + f ′(x0)(x1 − x0)	= 0. Тогда x1	= x0 −	f (x0)	. Пусть
			′

f (x0)

известно xn. Тогда

f (xn) xn+1 = xn − f ′(xn) .

виде

нам

Этот метод называется методом Ньютона или методом касательных. Заметим, что метод Ньютона состоит в том, что мы находим касательную в точке xn. Затем ищем пересечение этой касательной

сосью Ox. Это и будет следующее приближение. Метод Ньютона можно записать, как

xn+1 = s(xn),

где

				f (x)
		s(x) = x −			.
				f ′(x)
	Найдем s′(x):
	s′(x) = 1 −	(f ′(x))2	− f (x)f ′′(x)				=	f (x)f ′′(x)	.
		(f ′(x))2						(f ′(x))2

Рассмотрим вопрос о сходимости метода Ньютона. Для этого нам потребуется теорема о среднем.

Теорема 8.4. Пусть f (x) и g(x) непрерывные функции на отрезке [a; b] и g(x) неотрицательна. Тогда существует ξ [a; b] такое, что

Z b Z b

f (x)g(x)dx = f (ξ) g(x)dx.

a a

Теорема 8.5. Пусть x корень уравнения f (x) = 0. Предположим, что f (x) дважды дифференцируемая функция на отрезке Ur (x ), f ′′(x) непрерывна на этом отрезке и f ′(x) =6 0 на Ur (x ). Пусть

0 < m1 = inf |f ′(x)|, M2 = sup |f ′′(x)|,

Ur (x )	Ur (x )

причем

q = M2|x0 − x | < 1.

2m1

Тогда метод Ньютона сходится для любого x0 Ur (x ).

Доказательство. Перепишем метод Ньютона в виде

f (xn) xn+1 − x = xn − x − f ′(xn) ,

30

или

F (xn)

xn+1 − x =

,

f ′(xn)

где F (x) = (x − x )f ′(x) − f (x). Заметим, что F (x ) = 0 и

F ′(x) = f ′(x) + (x − x )f ′′(x) − f ′(x) = (x − x )f ′′(x).

Запишем тождество

x

x

F (xn) = F (x ) + Zx n F ′(t)dt = Zx n (t − x )f ′′(t)dt.

По теореме 8.4 имеем

xn

xn

− x

2

F (xn) = Zx

(t − x )f ′′(t)dt = f ′′(ξ) Zx

(t − x )dt =

(xn )

f ′′(ξ).

2

Отсюда,

|xn+1

− x | = |

F (xn)

| = |

(xn − x )2

f ′′(ξ)

| ≤

M2

(xn − x )2 ≤

f ′(xn)

2

f ′(xn) 2m1

2m1 ·

2m1

2

1+2+22+···+2n

(xn−1 − x )4 ≤ · · · ≤

2m1

(x0 − x )2

M2

M2

M2

n+1

2n+1

−1

− x |2

−1

|x0 − x | = q2

−1|x0 − x |.

= 2m1

|x0

M2

n+1

n+1

Таким образом, |xn+1 − x | → 0 при n → ∞.

8.3. Метод секущих. Метод секущих состоит в том, что мы проводим через две точки (xn−1, f (xn−1) и (xn, f (xn)) прямую, и ищем пересечение ее со осью Ox. В аналитической записи метод секущих записывается так

xn − xn−1

xn+1 = xn − f (xn) − f (xn−1) f (xn).

9.Лекция 9

9.1.Численное дифференцирование. Простейшие слу-

чаи. Пусть дано разбиение a = x0 < x1 < x2 < · · · < xn = b отрезка [a; b] на n равных частей, т.е. xi = a + ih. Мы хотим приблизить производные функции u(x). Обозначим ui = u(xi), u′i = u′(xi) и u(ik) = u(xi). В качестве приближенного значения u′(xi) мы можем взять одно из следующих выражений

ux−,i =	ui − ui−1	, ux+,i =	ui+1 − ui	, ux,i =	ui+1 − ui−1	.
	h		h
					2h

31

Найдем погрешность. Для этого воспользуемся формулой Тейлора. Получаем

ui − ui−1

ui − (ui − hui′ + h2 u′′

(ζ1))

= ui′ −

h

u′′

ux−,i =

=

2

(ζ1),

h

h

2

где ζ1 [xi−1; xi]. Аналогично,

ui+1 − ui

ui + hui′

+ h2 u′′(ζ2) − ui

h

ux+,i =

=

2

= ui′ +

u′′(ζ2),

h

h

2

где ζ2 [xi; xi+1]. Немного более точна последняя формула

ux,i =

ui+1 − ui−1

=

2h

(ui + hui′ +

h2

ui′′

+

h3

u′′′(ζ3)) − (ui + hui′ +

h2

ui′′ +

h3

u′′′(ζ4))

2

6

2

6

2h

= u′i + h2 (u′′′(ζ3) + u′′′(ζ4)), 12

где ζ3, ζ4 [xi−1; xi+1]. Мы можем считать u′′′(x) непрерывной. Тогда существует ζ5 [xi−1; xi+1] такой, что u′′′(ζ3) + u′′′(ζ4) = 2u′′′(ζ5). Отсюда

ux,i = ui′

+

h2

u′′′(ζ5).

6

Вторую производную можно заменить соотношением

uxx,i =

ui+1 − 2ui + ui−1

=

h2

1

(ui + hui′

h2

h3

h4

+

ui′′ +

ui′′′ +

u(IV )(ξ1)) − 2ui+

h2

2

6

24

h2

h3

h4

(ui − hui′

+

ui′′ −

ui′′′ +

u(IV )(ξ2)) =

2

6

24

ui′′ +

h2

(u(IV )(ξ1) + u(IV )(ξ2)) = ui′′ +

h2

u(IV )(ξ3),

24

12

где ξ1, ξ2, ξ3 [xi−1; xi+1].

9.2. Численные методы решения обыкновенных дифференциальных уравнений. Рассмотрим задачу Коши

x′ = f (t, x), x(t0 ) = x0.

Пусть ti = t0 + τ i равномерная сетка с шагом τ . Тогда рассмотрим разностное уравнение

xn+1 − xn = f (tn, xn).

τ

32

Таким образом, мы получим приближенные значения функции x(t) в точках tn. Данный метод называется методом Эйлера. Мы будем говорить, что разностный метод сходится в точке t, если при τ → 0 и tn = nτ = t последовательность |xn − x(tn)| → 0. Метод сходится на отрезке [t0; T ], если он сходится в каждой точке. Погрешностью метода в точке tn называется rn = xn −x(tn). Рассмотрим равенство

Z τ

x(tn+1) = x(tn + τ ) = x(tn) + x′(tn + z)dz.

0

Заменим R0τ x′(tn + z)dz на τ x′(tn) + O(τ 2). Тогда

x(tn+1) = x(tn) + τ x′(tn) + O(τ 2) = x(tn) + τ f (tn, xn) + O(τ 2).

Таким образом, мы получили метод Эйлера. Заметим, что погрешность метода Эйлера в точке tn равна O(τ ).

Теперь, вместо τ x′(tn) + O(τ 2) воспользуемся формулой трапеции

τ

′

x′(tn )+x′(tn+1 )

3

и заменим 0 x (tn +z)dz на

τ +O(h ). Получим неявную

2

формулу

Адамаса

R

f (tn, xn) + f (tn+1, xn+1)

x(tn+1) = x(tn) +

τ + O(h3).

2

Погрешность формулы Адамаса равна O(h2).

Рассмотрим

формулу

прямоугольника,

т.е.

заменим

R0

x (tn +

)

dz

на

τ x (tn +

2 ) + O(h ).

τ

1

3

τ

′

z

′

τ

3

Получим

x(tn+1) = x(tn) + τ f (tn +

, xn+ ) + O(h ),

2

2

где x

1

= xn + τ f (tn, xn). Этот метод называется методом Рунге–

n+

2

2

Кутта второго порядка.

Запишем явный вид методов Рунге–Кутта. В процессе вычисления фиксируются некоторые числа

α2, . . . , αq p1, . . . pq , βij , 0 < j < i ≤ q

последовательно получаем

k1(τ ) = τ f (tn, xn),

k2(τ ) = τ f (tn + α2τ, xn + β21k1(τ )),

. . . . . . . . . . . . . . . . . . . . . . . . . . .

kq (τ ) = τ f (tn + αq τ, xn + βq1k1(τ ) + · · · + βq, q − 1kq−1(τ ))

и полагаем

q

X

xn+1 = xn + piki(τ ).

i=1

33

(0) =

(0) =

=

P

q

i=1 piki(τ )). Выберем αi, βij , pi

Обозначим φ(τ ) = x(t + τ ) −x(t) −(

так, что φ′

φ′′

· · ·

φ(s)(0) = 0

При q = s = 4, чаще всего, используется формула

τ

k1

τ

k2

k1 = τ f (t, x), k2 = τ f (t +

, x +

), k3

= τ f (t +

, x +

),

2

2

2

2

1

k4 = τ f (t + τ, x + k3), xn+1 = xn +

(k1 + 2k2 + 2k3 + k4).

6

34