Билет 13
2. Представление чисел с фиксированной и плавающей запятой, оценка абсолютной и относительной погрешностей представления.
Современные ЭВМ оперируют с числами, представленными в одной из форм: с фиксированной и плавающей запятой
Рассмотрим каждую из них:
Числа с фиксированной запятой:
a=a n , a n-1…a 0 , a –1a -2…a -m
целые дробые
где a i – разряды
используется позиционная система исчисления , где значение каждого разряда зависит от позиции
a=a n pn+ a n-1 pn-1+…+a 0 p+ a –1 p-1+ a –2 p-2…a –m p-m
где p-основание системы исчисления
ai- натуральное число, принадлежащее множеству {0,1…p-1}
в компьютере числа с фиксированной запятой выглядят:
Fr,t t
r- длина
t-число разрядов под дробную чать
если m- основание с/и
тогда максимальное число mr-1 и при нехватке разрядов возможна ситуация переполнения, а для операции деления возможна ситуация, когда останется тока целая часть или так часть остатка, которая вмещается
Числа с плавающей запятой
a=Mps
M-мантисса
p-основание системы
s-порядок числа
мантисса должна быть строго меньше 1 или больше или рана min числу 0.1 равному p-1 (0.1M<1)
максимальным здесь будет число 2n-1
n-число
разрядов
по умолчанию в компьютере за основание берется 2, тогда число будет выглядеть как:
мантисса*2порядок
здесь возможны 2 варианта ошибок: потеря значимости –выводится ноль (если пытаются отобразить слишком точное число) или аварийное завершение программы при задании оч. большого или оч. маленького числа
Погрешности:
M0=10-8 машинный ноль- самое маленькое число представляемое на машине
M =Mo-1 машинная бесконечность
Погрешность в числе с фиксированном кол-вом определяется:
1) количеством отбрасываемых разрядов
пример:
F2,1
a1=2,1
a2=2,2
a=2,18
a*=2,1 (отбрасывание восьмерки)
a=-0.08
2)округлением
|a1-a||a1-a| a=a2
|a1-a|<|a1-a| a=a1
а принадлежит (a1, a2)- диапазон числа a
a ½ (a1-a1)= ½ 10-t
Погрешность в числе с плавающей запятой определяется формулой:
(a)= ½ 10k-t = ½ 10 1-t
M* 10k
1. Ортогональные матрицы отражения (преобразования Хаусхольдера), их использование для реализации QR-разложения.
Большинство методов решения СЛАУ основанно на переходе от заданной системы Ax=b, к новой системе CAx=Cb, такой, что Bx=d,где B=CA и d=Cb, решается проще чем исходная. (C-треугольная матрица, а A- квадратная размера mxm)
При выборе матрицы С надо учитывать, что ее вычисление не должно быть слишком трудоемким. Т.к. A=C-1B, то матрица С-1 должна быть легко обратимой, как и С и в результате преобразования должен получаться определитель A: detA=det (C-1B)=det(C-1) det (B)
Рассмотрим матрицу U=E-wwT , где w- вектор-столбец единичной длины, которая будет являться матрицей отражения. Так как w- вектор-столбец, а wT- вектор- строка, то wwT будет являться симметричной матрицей, но т.к. UUT=E, то U- симметричная и ортогональная матрица.
Лемма: любая квадратная матрица может быть представлена в виде произведения ортогональной и верхней треугольной матриц.
A=UT A(m-1)
где UT-ортогональная, a A(m-1) правая треугольная.
A(m-1)x=Ub, где A(m-1) является правой (верхней) треугольной матрицей.
Существует ряд тщательно отработанных алгоритмов решения полной проблемы собственных значений и для ее решения рекомендуется использовать стандартные решения. Рассмотрим QR-разложение.
А (nxn) матрица, которую можно представить в виде A=UTA(n-1), где A(n-1) является правой треугольной, а U – ортогональной.
Запишем ее в виде A=QR, где Q- ортогональная, а R- правая треугольная матрица.
Применяя матрицу отражения, матрицу Q можно представить в виде Q= E-wwT , где w- вектор-столбец единичной длины.
Трудоемкость этого метода будет больше чем в LU-разложении и равна n2+1/2 n2, а рабочее поле (затраченная память) будет равна около ½n2
Этот подход обычно используется, когда вектор b является почти нулевым.
Данное разложение существует всегда, независимо от врожденности матрицы. В случае врожденности может получится трапеция.
Вторым методом представления QR-разложения помимо матриц отражения является представление с помощью матриц вращения.