Метод отражений. Матрицей Хаусхолдера (отражений) называются квадратные матрицы вида:
= − |
2 T |
(10.2) |
T , |
где R 0. Матрица является ортогональной и симметричной. Пусть = ( 1, 2, . . . , )T — вектор, подлежащий преобразованию. Для построения тогда используется уравнение
= + ( 1)‖ ‖2 1, |
(10.3) |
где 1 = (1, 0, . . . , 0)T. Тогда при умножении вектора на матрицу Хаусхолдера аннулируются все компоненты , кроме первой и для приведения матрицы к треугольному виду в качетве берутся матрицы
= ( |
0− |
|
|
), |
(10.4) |
|
|
|
|
1 |
0 |
|
|
где = 2, 3, ..., − 1, 1 = 1, −1 R( −1)×( −1) — единичная матрица, — матрица Хаусхолдера, для вычисления которой на каждом -ом этапе берется вектор , состоящий из − + 1 элементов-го столбца матрицы A.
Метод вращений. Матрицами Гивенса (вращений) называются квадратные матрицы вида:
|
|
1. . . . . . . . . 0
= |
. . . |
|
... ... ... |
. . . |
|
(10.5) |
.. .. .. |
. . . |
. . . .. .. .. |
||||
|
|
− |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0. . . . . . . . . 1
Матрица является ортогональной и симметричной. |
|
|
|
|
||
Пусть |
= ( 1, 2, . . . )T — вектор, подлежащий преобразованию. Для построения матрицы |
|||||
|
|
|
|
|
||
Гивенса |
коэффициенты = / , = / , где |
= |
2 + 2. При умножении вектора на |
|||
матрицу Гивенса аннулируется одна -я компонента и |
изменяется его |
|
-я компонента. Тогда для |
|||
√ |
|
|
|
|||
приведения матрицы к треугольному виду в качестве берутся матрицы
11. Псевдорешение и нормальное псевдорешение произвольных СЛАУ
Рассмотрим произвольную СЛАУ общего вида:
= , |
C × , |
C . |
(11.1) |
Всистеме (11.1) число обозначает число уравнений, а – число неизвестных.
Вслучае, когда rank ( ... ) > rank ( ), система (11.1) не имеет решений (несовместность). Тогда вводится понятие псевдорешения системы (11.1), под которым понимается решение системы
= пр, |
(11.2) |
где пр есть проекция вектора на Im .
Теорема 11.1. Для любой матрицы C × и вектора C ортогональная проекция пр вектора на множество значений матрицы , т.е. Im , определяется единственным образом.
В случае, если rank ( ... пр) = rank ( ) ̸= – система (11.2) имеет бесчисленное множество решений (неединственность) ′ = { : = пр}. В этом случае вводится понятие нормального псевдорешения *, т.е. псевдорешения с минимальной евклидовой нормой ‖ ‖2:
* = ‖ ‖2.
′
6
12. Вычисление псевдорешений на основе нормальной системы уравнений
В начале рассмотрим совместные системы с 6 .
Введем некоторые обозначения. Пусть = 1, 2, . . . , – номера строк матрицы , – строки
матрицы , = |
|
...1 |
|
|
C × , |
= ( 1, . . . , )T |
|
|
C . |
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
Рассмотрим |
для каждого |
|
совместные СЛАУ |
|
|
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
= . |
|
|
|
|
|
||||||
Положим также |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
= * , |
|
|
|
= − + . |
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
. |
Теорема 12.1. Пусть система = удовлетворяет условиям 6 и rank ( . ) = rank = |
||||||||||||||||||||||||
. Тогда векторы и матрицы ( = |
1, 2, . . . , ) удовлетворяют системе рекуррентных |
|||||||||||||||||||||||
соотношений |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
+1 |
= + T+1( +1 T+1)+( +1 − T+1 ), 0 = 0, |
|
|
||||||||||||||||||
|
|
|
+1 |
|
|
|
|
|
|
|
T |
|
+ |
|
|
T |
|
0 |
= |
, |
|
|
||
|
|
|
= − ( +1 +1) |
|
+1 +1 , |
|
|
|||||||||||||||||
где |
|
|
|
|
|
|
|
|
|
|
( +1 T |
|
)−1, если +1 T |
> 0; |
|
|
||||||||
|
|
|
|
|
|
|
+1 |
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
+ |
{ 0, |
|
|
|
+1 |
|
если +1 +1 = 0. |
|
|
|||||||
|
|
|
( +1 |
T |
|
) |
|
|
|
|
|
|
|
+1 |
|
|
|
|||||||
|
|
|
|
|
= |
|
|
|
|
|
|
|
|
|
|
T |
|
|
|
|||||
= 1, 2, . . . , − 1 и вектор = * = + . |
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
Если rank = , то ( |
|
T |
)+ |
= ( |
+1 |
|
T |
)−1 при всех = 1, 2, . . . , |
− |
1. |
||||||||||||||
|
|
|
|
|
+1 |
|
+1 |
|
|
|
+1 |
|
|
|
|
|
|
|
||||||
Пусть исходная система = является произвольной (возможно несовместной и неполного
ранга). Тогда: |
* |
0 |
)( |
) |
= ( |
0 ) |
|
|
= . |
(12.1) |
|||
|
|
( |
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Из (12.1) непосредственно следует, что |
|
|
− * |
|
) |
|
|
||||||
|
|
|
|
* = + = ( |
* |
, |
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
где |
* |
= + . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
13. Псевдообратная матрица Мура–Пенроуза
Матрицу + C × называют псевдообратной (или обобщенной обратной матрицей Мура– Пенроуза) к матрице C × , если
+ = , |
+ = * = * , |
(13.1) |
где и – некоторые матрицы.
Теорема 13.1 (Единственность). Матрица +, удовлетворяющая условиям (13.1), существует и единственна.
Теорема 13.2 (Условия Пенроуза). Для любой матрицы C × = +, если и только если
1)= ;
2)= ;
3) ( )* = |
и ( )* = . |
7
Теорема 13.3 (Определение через предел). Имеют место соотношения |
|
|
lim( * + 2 )−1 * = + |
(13.2) |
|
→0 |
|
|
lim *( * + 2 )−1 = +. |
(13.3) |
|
→0 |
|
|
Для матриц полного ранга (rank = min( , )) имеют место соотношения |
|
|
( * )−1 *, |
если rank = ; |
|
+ = { *( *)−1, |
если rank = . |
|
Свойства псевдообратной матрицы. Отметим следующие основные свойства псевдообратной матрицы:
1) |
( *)+ = ( +)*; |
|
2) |
( +)+ = ; |
|
3) |
( +)2 = +, |
( + )2 = + . |
14. Вычисление нормальных псевдорешений на основе псевдообратных матриц
Если матрица — квадратная и невырожденная, то
+ = −1. |
(14.1) |
Рассмотрим задачу
= ,
где | | ̸= 0, C . Псевдорешение может быть найдено как:
* = −1 .
Для произвольной C × , с учётом 14.1 псевдорешение может быть найдено с помощью формулы
|
* |
= + . |
(14.2) |
|
|
|
15.Числа с плавающей точкой
Всистеме чисел с плавающей точкой позиция десятичной или бинарной точки хранится отдельно от самих цифр, и промежутки между соседними представленными числами соответственно пропорциональны абсолютным величинам цифр.
Рассмотрим определение идеализированной системы с плавающей точкой. Эта система состоит из дискретного подмножества F множества действительных чисел R. Множество F чисел с плавающей точкой характеризуется четырьмя параметрами: основанием системы счисления > 2, разрядностьюи интервалом показателей [ −, +]. Каждое число F представимо в виде
= ± ( 1 |
+ 2 + · · · + |
) |
, |
(15.1) |
||
|
|
|
2 |
|
|
|
где целые числа , , 1, . . . , удовлетворяют неравенствам |
|
|
||||
0 ≤ ≤ − 1, |
= 1, . . . , ; |
− ≤ ≤ +. |
|
|||
Часто называют разрядами, – длиной мантиссы, – порядком числа (или экспонентой).
Мантиссой (дробной частью) называется число в скобках. Рассмотренное представление чисел, называемое представлением с плавающей точкой, используется в большинстве современных компьютеров. Основанием обычно является число = 2 (с такими исключениями, как = 16 для компьютеров IBM 370 и = 10 для некоторых решающих таблиц и большинства калькуляторов). Например, 0.101012 × 23 = 5.2510.
Число с плавающей точкой называется нормализованным, если старший разряд его мантиссы отличен от нуля ( 1 ̸= 0).
8
16. Машинное эпсилон
Удобно считать, что округление – это отображение множества действительных чисел R в множество F чисел с плавающей точкой. Точность представления действительных чисел с использованием множества F традиционно определяется числом, которое называется машинным эпсилон ( machine) и зависит от разрядности . При традиционном способе округления чисел имеем machine = 12 1− , при округлении отбрасыванием разрядов machine = 1− . В общем случае, для арифметики с плавающей точкой, имеющей -разрядную мантиссу и основание , максимальная относительная ошибка представления равна 0.5 × 1− . Это число – половина расстояния самого большого промежутка между полученными числами с плавающей точкой, т.е. machine имеет следующее свойство:
R, ′ F такое, что | − ′| 6 machine| |. (16.1)
Для значений и , стандартных для различных компьютеров, значение machine обычно лежит между 10−6 и 10−35. В IEEE-арифметике с одинарной и двойной точностью machine принимает значения 2−24 ≈ ≈ 5.96 × 10−8 и 2−53 ≈ 1.11 × 10−16 соответственно.
Область положительных нормализованных чисел IEEE-арифметики обычной точности простирается от 2−126 (порог машинного нуля) до 2127 · (2 − 2−23) ≈ 2128 (порог переполнения) или приблизительно от 10−38 до 1038. Границами области положительных нормализованных IEEE-чисел двойной точности являются 2−1022 (порог машинного нуля) и 21023 · (2 − 2−52) ≈ 21024 (порог переполнения), т.е., приблизительно, 10−308 и 10308.
Удобно считать, что округление – это некоторое отображение множества действительных чисел R в множество F чисел с плавающей точкой, т.е. : R → F. Если R, а ( ) F, то в этих терминах
неравенство (16.1) можно сформулировать в виде следующей аксиомы. |
|
Аксиома 16.1. Для всех R существует , | | 6 machine, такое, что |
|
( ) = (1 + ). |
(16.2) |
Таким образом, относительная ошибка между действительным числом и его ближайшим приближением в системе с плавающей точкой всегда не превышает машинное эпсилон.
17.Арифметика чисел с плавающей точкой, фундаментальная аксиома арифметика с плавающей точкой
Вкомпьютере все математические вычисления сводятся к набору +, −, × и ÷. Математически эти символы определяют операции над полем R. На компьютере они имеют точные аналоги операций над F. Соответствующие операции на множестве F чисел с плавающей точкой обозначаются как ,
, и .
Для компьютерных вычислений справедливы следующие основные принципы. Пусть и произвольные числа с плавающей точкой, т.е. , F. Пусть * одна из операций +, −, × или ÷, и пусть её аналог в арифметике с плавающей точкой. Тогда должно в точности давать
( * ) = . |
(17.1) |
Если это свойство выполняется, тогда из ( ) = (1 + ) и (17.1) можно заключить, что компьютерные вычисления обладают простым и мощным свойством. Оно известно как
Аксиома 17.1 (Фундаментальная аксиома арифметики с плавающей точкой). Для всех , R
существует , | | 6 machine, такое, что
= ( * )(1 + ). |
(17.2) |
Другими словами, каждая операция в арифметике с плавающей точкой имеет относительную погрешность, не превышающую machine.
9