Федченко Г.М. Лекции. Численные методы
Подождите немного. Документ загружается.
ПОГРЕШНОСТИ МАШИННОЙ АРИФМЕТИКИ
относительную погрешность представления вещественных чисел в
компьютере. В качестве характеристики этой точности используют величину
– машинный эпсилон – наименьшее машинное число, которое при сложения
с числом 1 дает результат, больший чем 1.
В соответствии со стандартом IEEE для чисел одинарной точности
имеем следующие представления чисел:
1
0 01111111 00000000000000000000000
следующее за 1 число
0 01111111 00000000000000000000001
Таким образом, =1.2· и, следовательно, бессмысленно рассчитывать
более чем на 7-8 верных десятичных знаков в результате вычислений
одинарной точности и на то, что возможно разрешить относительные
различия, меньшие уровня .
Машинный эпсилон определяет относительную погрешность
арифметики компьютера (относительную плотность). Пусть x, y –
положительные вещественные числа с плавающей точкой, x > y. Тогда их
сумму можно записать в виде
.
Очевидно, что при y/x < сумма x + y совпадает с x, т.е. машинные числа y1<px
ничего не добавляют в сумму.
Чаще всего уже при записи десятичных чисел в память компьютера
возникает ошибка округления в силу использования двоичной системы
счисления. Ошибка представления в конечном количестве разрядов
локализована в последнем бите. Относительная погрешность этого
представления ограничена сверху величиной :
, .
Замечание: Числа с плавающей запятой имеют неравномерную,
возрастающую к нулю, абсолютную плотность распределения на всем
отрезке числовой оси, определяемом границами диапазона; и равномерную
относительную плотность распределения.
Вернемся еще раз к вопросу о катастрофической потере верных
цифр при вычитании близких чисел. Рассмотрим два положительных числа x
и y, расположенных на расстоянии, относительно сравнимом с машинным
эпсилон. Пусть y>x и . Тогда разность . Абсолютная погрешность разности ,
а относительная погрешность . Таким образом, все цифры разности могут
быть неверными.
Суммируем важнейшие свойства вычислений с плавающей точкой.
Конкретные параметры приведены для арифметики одинарной точности,
удовлетворяющей стандарту IEEE.
39
ПОГРЕШНОСТИ МАШИННОЙ АРИФМЕТИКИ
1. Множество чисел с плавающей точкой конечно.
Количество чисел .
2. Существует наибольшее число с плавающей точкой (OFL – OverFlow
Level).
.
3. Существует наименьшее число с плавающей точкой (UFL – UnderFlow
Level).
.
4. Числа с плавающей точкой между и распределены неравномерно.
Между каждыми двумя степенями двойки находится чисел с плавающей
точкой. Например, на отрезках и их одинаковое количество.
Таким образом, числа с плавающей точкой гуще расположены вблизи
нуля.
5. Арифметические операции над числами с плавающей точкой не всегда
приводят к точно представимым результатам, поэтому результат
усекается или округляется до ближайшего числа с плавающей точкой.
6. Машинный эпсилон характеризует относительную точность машинной
арифметики.
.
7. Константы и определяются количеством битов показателя, –
количеством битов мантиссы. Тем самым эти константы характеризуют
разные части представления чисел с плавающей точкой.
Числа с плавающей точкой можно использовать для моделирования
системы действительных чисел в математике, учитывая при этом ее
существенные отличия. Ось действительных чисел можно представить
разбитой на 7 областей:
1. Отрицательные числа меньшие –.
2. Отрицательные числа от – до –.
3. Отрицательные числа от – до 0.
4. Нуль.
5. Положительные числа от 0 до .
6. Положительные числа от до .
7. Положительные числа большие .
40
отрицательное
переполнение
1
2
3
4
5
6
7
выражаемые
отрицательные числа
положительное
переполнение
выражаемые
положительные числа
отрицательная
потеря
значимости
положительная
потеря
значимости
нуль
ПОГРЕШНОСТИ МАШИННОЙ АРИФМЕТИКИ
4.4. Выполнение арифметических операций над числами с
плавающей точкой
При сложении и вычитании чисел сначала производится
подготовительное действие, называемое выравниванием порядков. Порядок
меньшего по модулю числа при этом становится равным порядку большего.
Для этого мантисса числа с меньшим порядком сдвигается в ячейке вправо
на количество разрядов, равное разности порядков данных чисел. После этой
операции одинаковые разряды чисел оказываются в соответствующих
разрядах обеих ячеек, и теперь уже сложение или вычитание мантисс
выполняется достаточно просто, так же как и над числами с фиксированной
запятой.
При умножении двух чисел с плавающей точкой их порядки
складываются, а мантиссы – перемножаются.
При делении из порядка делимого надо вычесть порядок делителя, а
мантиссу делимого разделить на мантиссу делителя.
Пусть даны два числа a=m·p, b=m·p (n n).
a b = (m m·p) · p ;
a · b = (m · m) · p ;
a / b = (m / m) · p .
Мантисса результата нормализуется, т.е. сдвигается вправо или влево так,
чтобы ее первая значащая цифра попала в первый разряд после запятой.
Одновременно порядок результата увеличивается или уменьшается на число,
равное величине сдвига.
Пример 4.3. Вычислим , используя компьютерную арифметику одинарной
точности, и сравним результат с очевидным точным ответом 10 000.
Для этого воспользуемся алгоритмом:
// s – величина вещественного типа одинарной точности
1. n:=100000
2. s:=0
3. для i=1, …, n
4. s:=s+0.1
Выходные данные: s
Компьютер выдаст ответ s9998.557 с абсолютной погрешностью и
относительной погрешностью .
41
ПОГРЕШНОСТИ МАШИННОЙ АРИФМЕТИКИ
Источник погрешности кроется, прежде всего, в невозможности точно
представить число 0.1 в двоичной системе счисления, так как оно выражается
бесконечной периодической дробью
0.1=0.0(0011)=1.(1001)·2.
При записи в 23-разрядную мантиссу произойдет округление и в
памяти компьютера будет представлено несколько большее число,
отличающееся на величину от истинного значения и, следовательно,
относительная погрешность представления . Если бы вычисления
производились над с сохранением всех разрядов, то результат был бы
больше 10000 на величину =. Результат же отличается от ожидаемого. В ходе
вычисления частичная сумма помещается на хранение в величину одинарной
точности, при этом она может быть округлена как с недостатком, так и с
избытком. Так как сумма растет, последние добавления 0.1 мало сравнимы с
текущей величиной суммы и при выравнивании мантисс отсекаются
дополнительные разряды, что приводит к росту погрешности. Смешанный
эффект этих ошибок и дает фактическую погрешность.
Проведем еще несколько экспериментов при различных значениях n.
При n=1000000 компьютер выдаст результат s100958.3 с относительной
погрешностью . А при n=100000000: 2097152 с относительной
погрешностью . Объясните этот феноменальный результат.
4.5. Алгебраические особенности системы чисел конечной
точности
Множество чисел конечной разрядности является моделью числовой
прямой. При этом можно отметить основные отличия представления чисел в
поле памяти n-разрядного компьютера от их представления в поле памяти
человека.
1. Количество чисел конечно.
2. Не выполняется свойство замкнутости относительно арифметических
операций.
3. Не выполняется ассоциативный закон, т.е. необязательно выполняются
равенства
(a+b)+c = a+(b+c),
(a ·b) · c = a · (b · c).
4. Не выполняется дистрибутивный закон, т.е. необязательно
выполняется равенство
(a+b)·c = a·c + b·c.
1–4 справедливо как для целых так и для вещественных чисел конечной
точности.
42
ПОГРЕШНОСТИ МАШИННОЙ АРИФМЕТИКИ
5. Вещественные числа конечной точности не являются всюду плотными
в отличие от обычных вещественных чисел, для которых между
любыми двумя вещественными числами x, y существует другое
вещественное число z=(x+y)/2.
Бесконечное и счетное (нумеруемое) множество целых чисел
представимо в n-разрядной арифметике отрезком . Бесконечное, несчетное
множество вещественных чисел, располагающихся на числовой оси
равномерно и плотно, представляется конечным подмножеством множества
рациональных чисел, определяемое разрядностью арифметики.
Различия в представлении чисел в обычной и машинной (n-разрядной)
арифметике ограничивают как «арифметические возможности компьютера,
так и «компьютерные» возможности арифметики, математики,
использования математических методов, алгоритмов в компьютерах. Нужно
всегда иметь в виду, что точность в теоретической математике – понятие
абстрактное и в практическом применении математики может возникнуть
иллюзия точности там, где ее на самом деле нет, если не произведена
достаточно корректная интерпретация практической точности.
4.6. Контрольные вопросы и упражнения
1. Найдите основные числовые характеристики вещественных чисел с
плавающей точкой удвоенной и повышенной точности.
2. Рассмотрим воображаемую систему с плавающей точкой из
следующих чисел:
,
где каждое число , и y принимает одно из значений 0 или 1, а всегда
равно 1, за исключением случая = = = y = 0. Изобразите фрагмент
вещественной оси с нанесенными на нее элементами множества S.
Определите количество элементов этого множества. Каковы значения
констант , , ?
3. Как определить, какой вариант используется при записи вещественного
числа конечной разрядности: усечение или округление вашей
вычислительной системой?
4. Вычислите , используя компьютерную арифметику одинарной
точности. Объясните результат. Попробуйте увеличить верхний предел
суммы в 10, 100, 1000, 10000 раз.
43
ПОГРЕШНОСТИ МАШИННОЙ АРИФМЕТИКИ
5. Вычислите выражение четырьмя способами: 1) суммируя
последовательно слева направо; 2) слева направо все положительные и все
отрицательные, затем вычитание; 3) последовательно справа налево; 4)
справа налево все положительные и все отрицательные, затем вычитание.
Объясните разницу в полученных результатах для достаточно больших n и
определите какое из полученных значений наиболее точно приближает
истинное значение конечного ряда.
6. Продемонстрируйте нарастание погрешности и потерю верных цифр в
алгоритме вычисления из примера 4.4 при x = –10 или x = –15.
7. Модифицируйте алгоритм вычисления примера 4.4 в соответствии с
рекомендацией и проверьте его на устойчивость.
8. Компьютерная компания решила выпустить машину с 16-битными
числами с плавающей точкой. В модели 001 формат состоит из знакового
бита, 7-битной смещенной мантиссы (смещение 64) и 8-битной мантиссы.
В модели 002 формат состоит из знакового бита, 5-битной смещенной
мантиссы (смещение 16) и 10-битной мантиссы. В обеих моделях
основание возведения в степень равно 2. Каково самое маленькое и самое
большое положительное нормализованное число в этих моделях? Сколько
десятичных разрядов точности содержится в каждой модели? А вы купили
бы какую-нибудь из этих моделей?
9. Решите систему линейных алгебраических уравнений методом
Крамера и методом Гаусса. Определите количество операций типа
сложения и типа умножения, выполненных в процессе решения.
44
52
1223
12
321
321
321
xxx
xxx
xxx
РЕШЕНИЕ СЛАУ. ПРЯМЫЕ МЕТОДЫ
Лекция 5
РЕШЕНИЕ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ.
ПРЯМЫЕ МЕТОДЫ
5.1. Введение
Большой объем расчетных математических задач приходится на
решение систем линейных алгебраических уравнений (СЛАУ).
Математические модели многих явлений и процессов либо сразу строятся
как линейные алгебраические, либо сводятся к таковым в процессе решения
математической задачи. СЛАУ возникают, например, при решении методом
сеток дифференциальных уравнений, при изучении колебаний различных
систем, при решении задач управленческого и экономического характера и
т.п.
Современная вычислительная математика располагает большим
арсеналом методов, а программное обеспечение ЭВМ – многими пакетами
прикладных программ, позволяющими решать различные возникающие на
практике линейные системы. Чтобы ориентироваться среди методов и
программ и в нужный момент сделать оптимальный выбор, нужно
разбираться в основах построений методов и алгоритмов, учитывающих
специфику постановок задач, знать их сильные и слабые стороны и границы
применимости.
Все методы решения алгебраических задач (наряду с задачей решения
СЛАУ, это и вычисление определителей, и обращение матриц, и задачи на
собственные значения) можно разделить на два класса: прямые и
итерационные.
Прямые методы дают решение задачи за конечное (точно
определяемое для каждого метода) число арифметических операций. Если
операции реализуются точно, то и решение будет точным. Но из-за ошибок
округления, в частности при вычислениях в арифметике конечной
разрядности, решение гораздо чаще получается приближенным. Поэтому и в
прямых методах актуальны вопросы оценки погрешности решения,
разработки методов уменьшения накапливания ошибок округления. К
прямым методам относятся методы Крамера, Гаусса и различные его
модификации, прогонки, вращений.
Итерационные методы дают решение как предел бесконечной
последовательности приближенных решений, в которых каждое
последующее более точное приближение находится по уже найденному
предыдущему (или предыдущим). К таковым относятся метод простой
итерации, Зейделя, релаксации.
Мы будем рассматривать решение таких СЛАУ, у которых число
уравнений совпадает с числом неизвестных, причем имеющих единственное
45
РЕШЕНИЕ СЛАУ. ПРЯМЫЕ МЕТОДЫ
решение. Такое ограничение естественно, так как решение
недоопределенных, переопредленных систем, систем с комплексными
коэффициентами сводится к решению однозначно определенных
вещественных систем.
Итак, мы будем изучать вопрос о численном решении систем вида:
(5.1)
Или в матричной форме
Ax=b, (5.2)
где A – квадратная матрица коэффициентов при неизвестных, b – вектор-
столбец свободных членов, x – вектор-столбец неизвестных.
Решением системы называется такой набор , который обращает все
уравнения системы (5.1) в тождества. Если detA0, то система (5.1) и
эквивалентное ей матричное уравнение (5.2), имеет единственное решение. В
случае, когда detA0, система уравнений либо не имеет решений, либо имеет
бесконечное множество решений.
Геометрическая интерпретация. Решением системы (5.1) являются точки
пересечения гиперплоскостей n-мерного пространства, задаваемых
уравнениями системы.
Проиллюстрируем на примере системы двух линейных уравнений:
.
Каждому уравнению соответствует прямая на плоскости xO x, а точка
пересечения этих прямых есть решение системы уравнений. Если detA0, то
наклоны прямых равны и они либо параллельны, либо совпадают.
Но возможен случай, когда углы наклона прямых мало отличаются:
Тогда небольшие погрешности в коэффициентах и правых частях могут
привести к большим погрешностям в решении, т.е. к весьма неточному
определению положения точки пересечения. Геометрически это означает, что
небольшое изменение наклона или сдвиг одной прямой сильно меняют
46
x
x
O
detA0
x
x
O
detA0
x
x
O
РЕШЕНИЕ СЛАУ. ПРЯМЫЕ МЕТОДЫ
положение точки пересечения, Такие системы называются плохо
обусловленными. В многомерном случае картина может быть более сложной.
Так, для трех переменных возможен случай плохой обусловленности, когда
соответствующие трем уравнениям плоскости пересекаются под большими
углами (т.е. далеки от параллельности), но линии их попарного пересечения
почти параллельны.
5.2. Метод Крамера
Классическая теория систем линейных алгебраических уравнений
дает несколько прямых методов решения. По правилу Крамера для системы
n линейных уравнений с n неизвестными при detA0 значение каждого из
неизвестных вычисляется как отношение двух определителей порядка n:
, j=1, …, n, (5.3)
где detA – определитель матрицы, получаемой заменой j-го столбца матрицы
A столбцом свободных членов.
Таким образом, решение линейной системы с n неизвестными
сводится к вычислению (n+1)-го определителя порядка n, на вычисление
каждого из которых затрачивается n! операций умножения и столько же
операций сложения. Факториальный рост количества арифметических
операций нарастает катастрофически. Например, при n=100, n!10, и
рассматривая потенциальные возможности развития вычислительной
техники, можно прийти к выводу, что в обозримом будущем системы сотого
порядка системы сотого порядка в принципе не могут быть решены по
формулам Крамера. Кроме того, при таком количестве арифметических
действий погрешности округлений будут катастрофически нарастать.
Если осуществлять вычисление обратной матрицы с помощью
союзной матрицы, т.е. через алгебраические дополнения, то нахождение
решения векторно-матричного уравнения (5.2) по формуле
x=A·b
фактически равнозначно применению формул Крамера и также непригодно
для вычислительных целей.
5.3. Метод Гаусса
Наиболее известным и популярным способом решения СЛАУ
является метод Гаусса. Суть его в последовательном исключении
неизвестных. в отличие от курса алгебры здесь нас будут интересовать
вычислительные аспекты этого метода, а именно, создание алгоритма
получения вектора-решения x, причем, по возможности, минимизирующего
влияние неизбежных ошибок округления. Для этого получим общие
формулы метода Гаусса.
В ходе решения СЛАУ методом Гаусса можно выделить два этапа:
47
РЕШЕНИЕ СЛАУ. ПРЯМЫЕ МЕТОДЫ
1. преобразование исходной системы к треугольному виду –
прямой ход;
2. вычисление значений неизвестных в обратном порядке –
обратный ход.
Проведем поэтапное сведение системы (5.1) к треугольному виду,
исключая сначала x из второго, третьего, …, n-го уравнений, затем x из
третьего, четвертого, …, n-го уравнений преобразованной системы и т.д.
1 этап. Исключение неизвестного x из второго, третьего, …, n-го уравнений.
Заменяем второе, третье, …, n-е уравнения на уравнения,
получающиеся вычитанием из них первого уравнения, умноженного
соответственно на , , …, (a – ведущий элемент). Результатом этих
преобразований будет эквивалентная (5.1) система:
, (5.4)
коэффициенты которой рассчитываются по формулам
, , , где i, j = 2, 3, …, n.
При этом можно считать, что a0, так как по предположению система (5.1)
однозначно разрешима, значит коэффициенты при x не могут одновременно
равняться нулю, и на первое место всегда можно поставить уравнение с
отличным от нуля первым коэффициентом.
2 этап. Проделываем те же операции с подсистемой системы (5.4),
получающейся исключением первого уравнения. Результат этого этапа будет
иметь вид
, (5.5)
где
, , ; i, j = 3, …, n.
Продолжаем этот процесс до (n–1) этапа.
n–1 этап. В результате выполнения этого этапа получается треугольная
система, эквивалентная (5.1):
, (5.6)
Итак, на k-ом этапе происходит расчет по формулам:
, , ; i, j = k+1, …, n.
k изменяется от 1 до n–1. Полагаем также , .
Треугольная структура системы (5.6) позволяет последовательно
вычислить значения неизвестных, начиная с последнего:
, k=n–1, n–2, …, 1.
48