Билет № 13.
1). Ортогональные матрицы отражения, их использование для реализации QR- разложения (преобразования Хаусхольдера).
2). Представление чисел с фиксированной и плавающей запятой, оценка абсолютной и относительной погрешностей представления.
Ортогональные матрицы отражения, их использование для реализации 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=UTA(m-1) где UT-ортогональная, aA(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-разложения помимо матриц отражения является представление с помощью матриц вращения. |
Представление чисел с фиксированной и плавающей запятой, оценка абсолютной и относительной погрешностей представления. Современные ЭВМ оперируют с числами, представленными в одной из форм: с фиксированной и плавающей запятой Рассмотрим каждую из них: Числа с фиксированной запятой: a=a n , a n-1…a 0 , a –1a -2…a -m целые дробые где ai – разряды используется позиционная система исчисления , где значение каждого разряда зависит от позиции 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} в компьютере числа с фиксированной запятой выглядят:
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 |