Методическое пособие для практических и лабораторных работ по курсу «Численные методы»

100
приближенное значение функции по формуле
)
,
,
(
1
n
x
x
f
y
L
=
и оценим его абсолютную и относительную погрешности.
Если воспользоваться формулой Лагранжа, то, предполагая, что
)
,...,
(
1
n
x
x
f
непрерывно дифференцируема и ее первые частные производные незначительно меняются в области
G
, получаем
∑
=
∆
∂
∂
≤
−
n
i
i
n
i
x
x
x
f
x
y
y
1 1
)
,
,
(
L
,
∑
∑
=
=
∂
∂
=
∆
∂
∂
≤
−
n
i
i
n
i
i
n
i
i
n
i
x
x
x
f
x
x
x
x
x
f
x
y
y
y
1 1
1 1
)
,
,
(
ln
)
,
,
(
ln
δ
L
L

Поэтому, можно положить, что
∑
=
∆
∂
∂
≈
∆
n
i
i
n
i
x
x
x
f
x
y
1 1
)
,
,
(
L
,
(2.1)
∑
∑
=
=
∂
∂
=
∆
∂
∂
≈
n
i
i
n
i
i
n
i
i
n
i
x
x
x
f
x
x
x
x
x
f
x
y
1 1
1 1
)
,
,
(
ln
)
,
,
(
ln
δ
δ
L
L
(2.2)
Формулы (2.1), (2.2) позволяют оценить абсолютную и относительную погрешности любого выражения, в том числе суммы, разности, отношения и т.д.
Нередко приходится сталкиваться с ситуацией, когда функция
)
,
,
(
1
n
x
x
f
y
L
=
задается не явной формулой, а как решение нелинейного уравнения
0
)
,
,
(
1
=
n
x
x
y
F
L
, т.е. неявно. Если для такой неявной функции воспользоваться известными формулами нахождения производных




∂
∂
∂
∂
−
=
∂
∂
y
F
x
F
x
f
j
j
, вычисленными при
)
(x
f
y
=
,
n
j
,...,
1
=
, то исследование погрешностей неявной функции сводится к рассмотренному выше случаю.
Определение 5. Задачу вычисления погрешностей функции в случае, когда заданы погрешности аргументов, называют прямой задачей теории погрешностей.
Часто приходится находить такие допустимые неизвестные погрешности аргументов, чтобы погрешность функции не превышала заданного
ε
Определение 6.
Задача определения допустимой погрешности аргументов по заданной допустимой погрешности функции называется обратной задачей теории погрешностей.

101
Для функции одной переменной
)
(x
f
y
=
допустимую абсолютную погрешность аргумента, если
0
)
(
≠
′
x
f
, можно приближенно вычислить по формуле
y
x
f
x
)
(
1
∆
′
≅
∆

Для функции нескольких переменных
)
,
,
(
1
n
x
x
f
y
L
=
обратная задача теории погрешностей не имеет общего алгоритма решения, а решается только при ряде ограничений. Например, если значения всех аргументов можно одинаково легко определить с любой точностью, то применяют
принцип равных влияний, т.е. считают, что все слагаемые в формуле (2.1) равны между собой. В этом случае допустимые абсолютные погрешности аргументов находят по формулам
i
n
i
x
x
x
f
n
y
x
∂
∂
⋅
∆
≅
∆
)
,
,
(
1
L
,
n
i
,...,
1
=
(2.3)

Если значение одного из аргументов значительно труднее измерить или вычислить с той же точностью, что и значения остальных аргументов, то погрешность именно этого аргумента надо согласовать с требуемой погрешностью функции.
При вычислениях на ЭВМ погрешность единичного округления, как правило, мала (
12 8
10 10
−
−
÷
=
∆
x
). Однако существуют такие опасные ситуации
(«вычислительные ловушки»), когда малые погрешности округлений вызывают большие ошибки в результате. Так, например, покажем, что при вычитании близких по величине чисел относительная погрешность может стать большой, даже если абсолютная погрешность мала. Предварительно напомним следующие определения.
Определение 7. Значащими цифрами в десятичной записи числа называются все цифры, начиная с первой ненулевой слева.
Определение 8. Значащая цифра называется верной, если абсолютная погрешность числа не превосходит половины единицы разряда, соответствующего этой цифре.
Пример. Требуется определить относительную погрешность разности
y
x
u
−
=
, проводя вычисления с четырьмя значащими цифрами.
Предполагается, что значения
4 10 57207
,
0
⋅
=
x
,
4 10 57234
,
0
⋅
=
y
заданы точно,
4 10 5721 0
⋅
=
x
,
4 10 5723 0
⋅
=
y
. Тогда

102 3
,
0
=
∆
x
;
%
005
,
0 10 5721
,
0 3
,
0 4
≅
⋅
=
−
x
δ
,
4
,
0
=
∆
y
;
%
007
,
0 10 5723
,
0 4
,
0 4
≅
⋅
=
−
y
δ
,
10 2
,
0 10 0002
,
0 4
⋅
−
=
⋅
−
=
−
=
y
x
u
; точное значение
7
,
2
−
=
u
,
7
,
0
≅
∆
u
,
%
35 35
,
0
=
≅
u
δ
, т.е. в ответе нет ни одного верного знака.
Поэтому, если возможно, следует избегать при расчетах вычитания двух почти равных чисел. Это иногда можно сделать за счет преобразования соответствующих выражений. Например, вместо вычисления
0 1
cos
1
−
=
u
нужно вычислять
0 3
sin
2 2
′
=
u
, вместо
)
/(
)
(
y
x
y
x
u
n
n
−
−
=
вычислять
1 2
1
−
−
−
+
+
⋅
+
=
n
n
n
y
y
x
x
u
L
, вместо
ε
+
−
=
2
p
p
z
, где
0
>
p
,
ε
– мало, вычислять
(
)
ε
ε
+
+
−
=
2
p
p
u
и т.д.
Другим примером потери точности из-за погрешности округлений является суммирование последовательности чисел разных порядков на вычислительной машине. Как правило, на ЭВМ при выполнении арифметических действий младшие разряды результата, не вмещающиеся в разрядную сетку, отбрасываются.
Пусть имеется возрастающая последовательность точных чисел:
0,2335; 0,3213; 0,2259·10; 0,2575·10 1
; 0,1405·10 2
; 0,2314·10 2
; 0,1711·10 3
;
0,3304·10 3
; 0,1561·10 4
; 0,6785·10 4
, сумма которых S=0,88900788·10 4
Найдем сумму этих же чисел, если в качестве типа данных возьмем single (7-8 разрядный тип). Сначала сложение произведем, начиная с наименьшего числа в порядке возрастания чисел, получим
3 1
15625·10 8,89007910
=
S
с ошибкой
4 1
10 3
−
⋅
≅
−
S
S
. Затем просуммируем, начиная с большего числа в порядке убывания чисел, получим
3 2
5·10 8,89007812
=
S
с ошибкой
4 2
10 75
,
6
−
⋅
≅
−
S
S
. Сумма
2
S найдена с ошибкой, в 2 раза большей, чем
1
S . Эту ситуацию можно объяснить, рассматривая распространение ошибки округления при каждом отдельном суммировании.
Отсюда следует, что если необходимо сложение длинной последовательности чисел, надо так организовать счет, чтобы сначала суммировались наименьшие числа. При решении больших задач, когда надо выполнить огромное число операций, небольшая ошибка округления может быть сильно увеличена последующими операциями. Поэтому уменьшение потери точности при каждой отдельной операции важно для практических расчетов.

103
Замечание. Если число x
приводится в качестве результата без указания величины погрешности, то принято считать, что все его значащие цифры являются верными. Начинающий пользователь часто слишком доверяет выводимым из ЭВМ цифрам, предполагая, что вычислительная машина придерживается того же соглашения. Однако это совсем не так: число может быть выведено с таким количеством значащих цифр, сколько потребует программист заданием соответствующего формата. Как правило, среди этих цифр только первые окажутся верными, а возможно верных цифр нет совсем. Анализировать результаты вычислений и определять степень их достоверности совсем непросто. Важно понимать, что следует, а чего нельзя ожидать от результатов, полученных на ЭВМ.

2.4. Особенности машинной арифметики
Знание основных особенностей машинной арифметики необходимо для грамотного использования ЭВМ при численном решении задач.
Будем считать, что все вычислительные машины работают в двоичной системе счисления. Для хранения числа в памяти ЭВМ отводится поле стандартной длины (машинное слово), в котором число записывается в виде последовательности двоичных цифр (0 или 1). Целое число n представляется в виде
)
2 2
2
(
0 0
1 1
a
a
a
n
L
L
+
+
+
±
=
,
(2.4) где L - некоторое стандартное для ЭВМ целое число,
i
a – двоичные числа.
Всего для хранения числа n отводят
2
+
L
разрядов (один из них для хранения знака).
Из представления (2.4) видно, что максимальное по модулю целое число, представимое в ЭВМ, есть
1 2
2 2
2 1
0 1
max
−
=
+
+
+
=
+
L
L
n
. Операции сложения, вычитания и умножения над целыми числами реализованы так, что если результат не превышает по модулю число max
n
, то он получается точным. Однако, если модуль результата превышает max
n
, то на ряде вычислительных машин эта ситуация не доводится до сведения пользователя, происходит присвоение результату некоторого значения, меньшего max
n
по модулю, и вычисления продолжаются далее.
Для вещественных чисел принята форма представления с плавающей точкой, когда каждое число представляется в виде
p
t
t
x
2
)
2 2
2
(
2 2
1 1
−
−
−
⋅
+
+
⋅
+
⋅
±
=
γ
γ
γ
,
(2.5)

104
где
t
γ
γ
γ
,...,
,
2 1
– двоичные цифры. Число
x нормализуется так, чтобы
1 1
=
γ
и поэтому в
ЭВМ хранятся только значащие цифры.
Число
)
2 2
2
(
2 2
1 1
t
t
−
−
−
⋅
+
+
⋅
+
⋅
±
=
γ
γ
γ
µ
называется мантиссой числа
x . Количество
t цифр, которое отводится для записи мантиссы, называется разрядностью
мантиссы,
p
- целое число, называемое двоичным порядком. Порядок также записывают, как двоичное целое число
)
(
0 1
σ
σ
σ
−
±
=
l
l
p
, для хранения которого в машинном слове отводится
2
+
l
двоичных разрядов.
Так как нуль – ненормированное число (его нельзя представить в виде
(2.5) при
0 1
≠
γ
), то для его хранения предусматривают особый способ записи.
Отметим следующие моменты.
1.
В ЭВМ представимы не все числа, а лишь конечный набор рациональных чисел специального вида. Эти числа образуют представимое множество вычислительной машины. Для всех остальных чисел x возможно лишь их приближенное представление с ошибкой, которую принято называть
ошибкой представления (или ошибкой округления). Обычно приближенное представление числа x в ЭВМ обозначают как
)
(
x
fl
x
=
. Если округление производят по дополнению, то граница относительной погрешности представления равна единице первого отброшенного разряда мантиссы, т.е.
t
M
x
−
=
=
2
)
(
ε
δ
. Если же округление производят усечением, то
t
M
x
−
=
=
1 2
)
(
ε
δ
Величина
M
ε
играет в вычислениях на
ЭВМ фундаментальную роль, ее называют относительной точностью ЭВМ, а также машинной точностью (или машинным эпсилон). Значение этой величины определяется разрядностью мантиссы и способом округления.
Можно считать, что точное число
x
и отвечающее ему округленное число x
связаны равенством
)
1
(
M
x
x
ε
+
=
(2.6)
Среди представимых на ЭВМ чисел нет не только ни одного иррационального (в том числе и таких важных постоянных, как
π
,
e ,
2 ), но и даже такого широко используемого в вычислениях числа, как 0.1. Дело в том, что двоичная запись числа 0.1 является бесконечной периодической дробью:
...)
011 0001100110 0
(
1 0
=
. Поэтому это число представляется на
ЭВМ приближенно, с погрешностью, вызванной необходимостью округления.
2.
Диапазон изменения чисел в ЭВМ ограничен. Для всех представимых на ЭВМ чисел
x
(за исключением нуля) имеем
∞
<
≤
<
X
x
X
0 0
, где
)
1
(
0
max
2
+
−
=
p
X
, max
2
p
X
=
∞
,
1 2
1
max
−
=
+
l
p
. Все числа по

105
модулю большие
∞
X рассматриваются, как машинная бесконечность.
Попытка получить такое число приводит к аварийному останову (авосту)
ЭВМ по переполнению. Все числа по модулю меньшие
0
X для ЭВМ не различимы и представляются, как нуль (машинный нуль). Получение числа
x , такого, что
0
X
x
<
, называют исчезновением порядка. Обычно, при исчезновении порядка, автоматически полагается
0
)
(
=
x
fl
и вычисления продолжаются.
3.
Правила выполнения арифметических операций в двоичной системе счисления просты и легко реализуются на ЭВМ. Однако в процессе проведения вычислений погрешности округлений (в силу ограниченной разрядности мантиссы арифметические операции над представимыми в ЭВМ вещественными числами не могут быть реализованы точно) могут накапливаться, так как выполнение каждой из четырех арифметических операций вносит некоторую погрешность. Считается, что выполнение каждой арифметической операции вносит относительную погрешность не большую, чем
t
−
2 . Это предположение можно записать в виде
)
1
)(
*
(
)
*
(
ε
+
=
b
a
b
a
fl
,
(2.7)
где звездочка означает любую из операций +, -,
×
, :, и
t
−
≤
2
ε
. Если результат выполнения арифметической операции является машинным нулем, то в формуле (2.7) надо положить
1
−
=
ε
Отметим еще, что в отличие от обычных математических операций, машинные арифметические операции из-за ограниченной разрядности мантиссы обладают иными свойствами. Например, не выполняется известное правило арифметики «от перемены мест слагаемых сумма не меняется». Соответствующие примеры приведены в [1,17].
Численные методы можно объединить в группы методов, предназначенных для решения задач математического анализа, алгебры, оптимизации, обыкновенных дифференциальных уравнений и уравнений в частных производных.
В осеннем семестре мы с Вами изучим численные методы решения задач линейной и нелинейной алгебры, аппроксимации функций, численное дифференцирование и интегрирование.

106
Лекция № 3 Задачи вычислительной алгебры. Прямые и итерационные методы. Метод исключения неизвестных (метод
Гаусса) решения систем линейных алгебраических уравнений
(СЛАУ). Схема единственного деления. Метод Гаусса с выбором главного элемента. LU – разложение матрицы. Методы вращений, квадратного корня.

Алгоритмы построения решения многих задач приводят нас к вычислительным задачам линейной алгебры. Так происходит при построении интерполяционного кубического сплайна, при численном решении дифференциальных и интегральных уравнений, при построении элемента наилучшего приближения в гильбертовом пространстве и в ряде других случаев. Поэтому очень важно уметь хорошо решать вычислительные задачи линейной алгебры.
К вычислительным задачам линейной алгебры относят задачи решения систем линейных алгебраических уравнений (СЛАУ)
b
x
А
r r
=
, вычисления обратных матриц
1
−
A , вычисления определителей A , задачи вычисления собственных чисел и собственных векторов матриц. Эти задачи имеют очень важное теоретическое и прикладное значение. Трудности решения указанных задач, как правило, связаны с большой размерностью матриц.
Чаще всего вычислительные задачи линейной алгебры решают точными и итерационными методами.
Определение 1. Метод называется точным, если в предположении отсутствия ошибок округлений, получается точное решение за конечное число шагов.
Определение 2. Метод называется итерационным, если решение получается в виде предела элементов некоторой последовательности.
В точных методах матрицу исходной системы уравнений эквивалентными преобразованиями приводят к более простой матрице или раскладывают на произведение более простых матриц.
Большинство точных методов относятся к так называемым методам исключения. В этих методах, последовательно исключая неизвестные, исходную систему приводят к системе с треугольной или диагональной матрицей. Очевидно, что последние легко разрешимы.
3.1. Метод исключения Гаусса (схема единственного деления) решения
систем линейных алгебраических уравнений

Пусть дана система линейных алгебраических уравнений (СЛАУ)

107
,
b
x
A
r r
=
(3.1)
где A – вещественная матрица порядка n , b
r
- заданный вектор,
xr – искомый вектор.
Предположим, что
0
|
|
≠
A
. Тогда система (3.1) имеет единственное решение. Перепишем систему (3.1) в скалярном виде






=
+
+
+
=
+
+
+
=
+
+
+
...
..........
..........
,
,
2 2
1 1
2 2
2 22 1
21 1
1 2
12 1
11
n
n
nn
n
n
n
n
n
n
b
x
a
x
a
x
a
b
x
a
x
a
x
a
b
x
a
x
a
x
a
(3.2)

Систему (3.2) будем решать методом исключения Гаусса, который называют также методом последовательного исключения неизвестных. Он известен в различных вариантах уже более 2000 лет. Метод состоит в последовательном исключении неизвестных
n
x
x
x
,...,
,
2 1
из уравнений системы.
Пусть
0 11
≠
a
. Разделив первое уравнение на
11
a , имеем
,
1 1
2 12 1
y
x
c
x
c
x
n
n
=
+
+
+
(3.3) где
,
11 1
1
a
a
c
j
j
=
,
,...,
3
,
2
n
j
=
.
11 1
1
a
b
y
=
Теперь умножаем уравнение (3.3) последовательно на
,
1
i
a
n
i
,...,
3
,
2
=
и вычитаем, соответственно, из 2-го, 3-го, …, n -го уравнений. В результате получаем








=
+
+
+
=
+
+
+
=
+
+
+
=
+
+
+
+
...
...
...
...
...
,
,
,
)
1
(
)
1
(
)
1
(
3 2
)
1
(
2
)
1
(
3
)
1
(
3
)
1
(
33 2
)
1
(
32
)
1
(
2
)
1
(
2
)
1
(
23 2
)
1
(
22 1
1 3
13 2
12 1
n
n
nn
n
n
n
n
n
n
n
n
b
x
a
a
x
a
b
x
a
a
x
a
b
x
a
a
x
a
y
x
c
x
c
x
c
x
(3.4)
Таким образом,
1
x исключили из всех уравнений начиная со второго.
Далее, первое уравнение системы (3.4) оставляем без изменения. Теперь, предполагая, что
,
0
)
1
(
22
≠
a
делим на него второе уравнение в (3.4) и

108
аналогично предыдущему исключаем
2
x из всех уравнений, начиная с третьего, и т. д. В результате приходим к системе








=
=
+
=
+
+
+
=
+
+
+
+
−
−
−
,
...
...
...
...
,
,
1
,
1 1
2 2
3 23 2
1 1
3 13 2
12 1
n
n
n
n
n
n
n
n
n
n
n
y
x
y
x
c
x
y
x
c
x
c
x
y
x
c
x
c
x
c
x
(3.5)

Матрица этой системы
















=
−
−
−
1 0
0 0
0 1
0 0
0
...
...
...
1 0
1
,
1 2
1
,
2 23 1
1
,
1 13 12
n
n
n
n
n
n
c
c
c
c
c
c
c
c
C
(3.6) содержит нули всюду ниже главной диагонали. Такие матрицы называются
верхними треугольными. Нетрудно проверить, что
1
−
C есть также верхняя треугольная матрица.
Преобразование системы (3.2) к эквивалентной системе (3.5) с верхней треугольной матрицей называется

Скачать 1.29 Mb.

Поделитесь с Вашими друзьями: