ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 02.08.2019
Просмотров: 4678
Скачиваний: 6
Лекция 1
11
малая отрицательная погрешность в задании
a приведет к конечной, а не
сколь угодно малой погрешности в решении уравнения.
Определение 1. Задача называется поставленной корректно, если для
любых значений исходных данных из некоторого класса её решение 1) су-
ществует, 2) единственно и 3) устойчиво по исходным данным.
Неустойчивость методов.
Иногда при решении корректно поставлен-
ной задачи может оказаться неустойчивым метод её решения. Такие слу-
чаи имели место при вычислении синуса большого аргумента, когда был
получен результат, не имеющий смысла. Рассмотрим ещё один пример
неустойчивого алгоритма. Построим численный метод вычисления инте-
грала
I
n
=
1
Z
0
x
n
e
x
−1
dx,
n = 1, 2, . . .
Интегрируя по частям, находим
I
1
=
1
R
0
xe
x
−1
dx = xe
x
−1
1
0
−
1
R
0
e
x
−1
dx =
1
e
,
I
2
=
1
R
0
x
2
e
x
−1
dx = x
2
e
x
−1
1
0
− 2
1
R
0
xe
x
−1
dx = 1
− 2I
1
,
· · ·
I
n
=
1
R
0
x
n
e
x
−1
dx = x
n
e
x
−1
1
0
− n
1
R
0
x
n
−1
e
x
−1
dx = 1
− nI
n
.
Заметим, что подынтегральная функция на всем отрезке интегрирова-
ния неотрицательна, следовательно, и значение интеграла — положитель-
ное число. Более того, подынтегральная функция на данном интервале
ограничена функцией
y = 1, т.е. значение интеграла не может превышать
единицы. Однако если вычислить по этой формуле значение интеграла то
результат будет неверным.
На рис. 1.2
n-ый столбик обозначает I
n
. Причём чёрный столбик — это
I
n
, вычисленный по только что изложенному рекурсивному методу, а се-
рый — это
I
n
, вычисленный по более устойчивому методу конечных сумм.
Лекция 1
12
0, 00
0, 05
0, 10
0, 15
0, 20
0, 25
0, 30
0, 35
0, 40
I
1
I
2
I
3
I
4
I
5
I
6
I
7
I
8
I
9
I
10
I
11
I
12
I
13
I
14
I
15
I
16
I
17
I
18
óñòîé÷èâûé ìåòîä
ðåêóðñèÿ
Ïîðÿäêè îøèáêè è
èíòåðãàëà ñîâïàëè
Рис. 1.2: Высичление интеграла устойчивым методом и рекурсией
Видно, что
I
17
немного отклоняется от точного решения, а
I
n
при
n
>
18
уже нельзя считать решением. Исследуем источник погрешности. Макси-
мальная абсолютная погрешность при вычислении
I
1
равна
0, 5
· 2
53
≈
5
· 10
−17
(компьютер «обрезал» иррациональное число
1/e до 16 десятич-
ных разрядов мантиссы). Однако на каждом этапе эта погрешность умно-
жается на число, модуль которого больше единицы
(
−2, −3, . . . , −18), что
в итоге даёт
18!
≈ 6, 4 · 10
15
. Это и приводит к результату, не имеющему
смысла. Здесь снова причиной накопления погрешностей является алго-
ритм решения задачи, который оказался неустойчивым.
Лекция 2
13
1.2
Лекция 2
ìåòî
äû
ðåøåíèÿ
íåëèíåéíûõ
óðàâíåíèé
äåëåíèå
îòðåçê
à
ïîïîëàì
ìåòî
ä
ïðîñòûõ
èòåðàöèé
ìåòî
ä
Íüþòîíà
ìåòî
ä
Íüþòîíà
ñ
èê
ñèðîâàííîé
ïðîèçâî
äíîé
ìåòî
ä
ñåêóùèõ
1.2.1
Метод деления отрезка пополам.
Другое название метода — дихотомия от греческих слов
διχα «надвое»
и
τ oµη «деление».
ââî
ä
(a, b, ε)
b − a 6 ε
c = (b + a)/2
f (a)f (b) < 0
b = c
a = c
x = a
x = c
âûâî
ä
x
ñòîï
>
<
=
6
Рис. 2.1: Блок–схема метода деления отрезка пополам
После каждой итерации длина отрезка сокращается вдвое. Следова-
тельно, на
n-ой итерации длина отрезка будет (b
− a)/2
n
. Если задана
точность
ε =
|x
b
− x
∗
|, с которой нужно определить корень, то справедли-
во, что
ε
6
(b
− a)/2
n
. Можно оценить число итераций
n для достижения
точности
ε:
n =
log
2
b
− a
ε
+ 1,
Лекция 2
14
где квадратные скобки
[
· ] обозначают целую часть числа (например, [π] =
3, [
−2,123] = −2).
1.2.2
Метод простых итераций (МПИ).
Заменим уравнение
f (x) = 0 эквивалентным ему уравнением x = ϕ(x).
Это можно сделать многими способами, например, положив
ϕ(x) = x +
ψ(x)f (x), где ψ(x) — произвольная непрерывная знакопостоянная функ-
ция. Выберем некоторое нулевое приближение
x
0
и вычислим дальнейшие
приближения по формулам
x
n+1
= ϕ(x
n
),
n = 0, 1, 2, . . .
Очевидно, если
x
n
стремится к некоторому пределу
x
∗
, то этот предел есть
корень исходного уравнения.
Условия сходимости.
Определение 2.1. Функция
s(x) называется липшиц-непрерывной с по-
стоянной
q на множестве X, если для всех x
0
, x
00
∈ X выполняется
неравенство
|s(x
0
)
− s(x
00
)
|
6
q
|x
0
− x
00
|.
(2.1)
В дальнейшем в качестве
X будем брать отрезок U
r
(a) =
{x : |x − a|
6
r
} длины 2r с серединой в точке a. Основные свойства МПИ перечислены в
следующей
теореме.
a
x
∗
a + r
a − r
öåíòð èíòåðâàëà
êîðåíü
U
r
(a)
Теорема 2.2. Если
ϕ(x) липшиц-непрерывна
с постоянной
q
∈ (0, 1) на отрезке
U
r
(a), причем
|ϕ(a) − a|
6
(1
− q)r, то
уравнение
x = ϕ(x) при любом началь-
ном приближении
x
0
∈ U
r
(a):
1) имеет на отрезке
U
r
(a) единственное решение;
2) метод простой итерации
x
n+1
= ϕ(x
n
) сходится к x
∗
;
Лекция 2
15
3) для погрешности справедлива оценка
|x
k
− x
∗
|
6
q
k
|x
0
− x
∗
|,
k = 0, 1, 2, . . .
(2.2)
Доказательство. Сначала докажем по индукции, что
x
k
∈ U
r
(a), k =
1, 2, . . ., т. е. что метод простой итерации не выводит за пределы того
множества, на котором
ϕ(x) липшиц-непрерывна с постоянной q
∈ (0, 1).
Предположим, что
x
j
∈ U
r
(a) при некотором j
>
0, и докажем, что тогда
x
j+1
∈ U
r
(a). Из равенства
x
j+1
− a = ϕ(x
j
)
− a = (ϕ(x
j
)
− ϕ(a)) + (ϕ(a) − a)
получим
|x
j+1
− a|
6
|ϕ(x
j
)
− ϕ(a)| + |ϕ(a) − a|.
Учитывая условие липшиц-непрерывности, предположение индукции и
условие
|ϕ(a) − a| < (1 − a)r, имеем
|ϕ(x
j
)
− ϕ(a)|
л.-непр.
6
q
|x
j
− a|
предп. инд.
6
qr,
|x
j+1
− a|
6
qr + (1
− q)r
6
r,
т.е.
x
j+1
∈ U
r
(a).
Оценим теперь разность двух соседних итераций
x
j+1
− x
j
. Имеем
x
j+1
− x
j
= ϕ(x
j
)
− ϕ(x
j
−1
),
и поскольку все точки
x
j
,
j = 1, 2, . . ., находятся на отрезке U
r
(a), полу-
чаем оценку
|x
j+1
− x
j
|
л.-непр.
6
q
|x
j
− x
j
−1
|
л.-непр.
6
q
2
|x
j
−1
− x
j
−2
|
6
. . .
и, следовательно,
|x
j+1
− x
j
|
6
q
j
|x
1
− x
0
|,
j = 1, 2, . . .
(2.3)
Оценка (2.3) позволяет доказать фундаментальность последовательности
{x
k
}. Действительно, пусть p — любое натуральное число. Тогда
x
k+p
− x
k
=
p
X
j=1
(x
k+j
− x
k+j
−1
),