Макет для изготовления в системе L^{A}TEX2ε

ДИПЛОМНАЯ РАБОТА

Кафедра ПМ — ФМиИТ УлГУ — 2009 Государственное образовательное учреждение высшего

профессионального образования Ульяновский государственный университет

Российско-германский факультет

Факультет математики и информационных технологий Кафедра �Прикладная математика�

Работа допущена к защите

Зав.кафедрой д.ф.-м.н. Бутов А. А.

(Ф. И. О)

(подпись)

(дата)

ДИПЛОМНАЯ РАБОТА

Сравнительный анализ

последовательных алгоритмов оценивания

(название темы)

010501 – Прикладная математика и информатика

(код и наименование специальности)

Шледевитц

Выполнил студент \underline{РГ-5м}

(Пахалина) Т.С.

(группа)  (подпись)  (Ф.И.О.)
Научный руководитель \underline{профессор}  \underline{Семушин И. В.}

Рецензент \underline{доцент}

Цыганова Ю. В.

Ульяновск 2009

(должность)  (подпись)  (Ф.И.О.)

(должность)  (подпись)  (Ф.И.О.)

Оглавление

Введение 5

1 Безусловная оптимизация 8

1.1 Функции для минимизации . . . . . . . . . . . . . . . . . . . . 8 1.1.1 Название . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.1.2 Название . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.1.3 Таблица функций для минимизации . . . . . . . . . . . 8

1.2 Название . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.2.1 Название . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.2.2 Название . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.3 Название . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.3.1 Название . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.3.2 Название . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.4 Название . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.4.1 Название . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.4.2 Название . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2 Название 13

2.1 Название . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.1.1 Название . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.1.2 Название . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.2 Название . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.2.1 Название . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.2.2 Название . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2.3 Название . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.3.1 Название . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.3.2 Название . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.4 Название . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.4.1 Название . . . . . . . . . . . . . . . . . . . . . . . . . . 15

\underline{ОГЛАВЛЕНИЕ}

2.4.2 Название . . . . . . . . . . . . . . . . . . . . . . . . . . 16

3 Название 17

3.1 Название . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.1.1 Название . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.1.2 Название . . . . . . . . . . . . . . . . . . . . . . . . . . 17

3.2 Название . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.2.1 Название . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.2.2 Название . . . . . . . . . . . . . . . . . . . . . . . . . . 18

3.3 Название . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.3.1 Название . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.3.2 Название . . . . . . . . . . . . . . . . . . . . . . . . . . 19

3.4 Название . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.4.1 Название . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.4.2 Название . . . . . . . . . . . . . . . . . . . . . . . . . . 19

4 Название 20

4.1 Название . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 4.1.1 Название . . . . . . . . . . . . . . . . . . . . . . . . . . 20 4.1.2 Название . . . . . . . . . . . . . . . . . . . . . . . . . . 20

4.2 Название . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 4.2.1 Название . . . . . . . . . . . . . . . . . . . . . . . . . . 22 4.2.2 Название . . . . . . . . . . . . . . . . . . . . . . . . . . 22

4.3 Название . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 4.3.1 Название . . . . . . . . . . . . . . . . . . . . . . . . . . 22 4.3.2 Название . . . . . . . . . . . . . . . . . . . . . . . . . . 23

4.4 Название . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 4.4.1 Название . . . . . . . . . . . . . . . . . . . . . . . . . . 23 4.4.2 Название . . . . . . . . . . . . . . . . . . . . . . . . . . 23

Заключение 24

Список иллюстраций 26

Список таблиц 27

Список использованной литературы 28 A Ортогональные преобразования 32

A.1 Ортогональные матрицы и приложения . . . . . . . . . . . . . 32 A.2 Линейная задача наименьших квадратов . . . . . . . . . . . . 34 A.3 Ортогональные матрицы в задаче о наименьших квадратах . . 35 A.4 Преобразование Хаусхолдера . . . . . . . . . . . . . . . . . . . 36 A.5 Шаг триангуляризации матрицы преобразованием Хаусхолдера 41 A.6 Решение треугольной системы Rx = z и обращение матриц R

и A . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 A.7 Преобразование Гивенса . . . . . . . . . . . . . . . . . . . . . . 45 A.8 Варианты заполнения матрицы R . . . . . . . . . . . . . . . . 51 A.9 Правосторонние ортогональные преобразования и их применение 51 A.10Двусторонние ортогональные преобразования и их применение 52

B Название приложения B 56

B.1 Название подраздела B.1 в приложении B . . . . . . . . . . . . 56 B.1.1 Название пункта B.1.1 в приложении B, подразд. B.1 . 56 B.1.2 Название . . . . . . . . . . . . . . . . . . . . . . . . . . 56

B.2 Название подраздела в приложении 2 . . . . . . . . . . . . . . 56 B.2.1 Название . . . . . . . . . . . . . . . . . . . . . . . . . . 56 B.2.2 Название . . . . . . . . . . . . . . . . . . . . . . . . . . 56

Введение

Здесь пишите … Задача Введения — обосновать актуальность темы данной работы, т. е.

объяснить:

Зачем написана эта работа ? Для кого написана эта работа ? Как структурно организован текст работы ? Какой материал помещен в основные структурные единицы работы ? Чем подкреплена данная работа: эксперименты, расчеты… ? Еще вариант оформления списков: Зачем написана эта работа ? Для кого написана эта работа ? Как структурно организован текст работы ? Какой материал помещен в основные структурные единицы работы ? Чем подкреплена данная работа: эксперименты, расчеты… ? Еще вариант оформления списков: Зачем написана эта работа ? Для кого написана эта работа ? Как структурно организован текст работы ? Какой материал помещен в основные структурные единицы работы ? Чем подкреплена данная работа: эксперименты, расчеты… ?

\underline{Введение}

Еще вариант оформления списков: Зачем написана эта работа ? Для кого написана эта работа ? Как структурно организован текст работы ? Какой материал помещен в основные структурные единицы работы ? Чем подкреплена данная работа: эксперименты, расчеты… ? Еще вариант оформления списков: Зачем написана эта работа ? Для кого написана эта работа ? Как структурно организован текст работы ? Какой материал помещен в основные структурные единицы работы ? Чем подкреплена данная работа: эксперименты, расчеты… ? Вариантов оформления списков очень много … Еще примеры см. в За-

ключении.

Вложенные списки также возможны: Зачем написана эта работа ?

Для кого написана эта работа ?

Как структурно организован текст работы ?

Какой материал помещен в основные структурные единицы рабо-

ты ? Чем подкреплена данная работа: эксперименты, расчеты… ?

Для кого написана эта работа ?

Для кого написана эта работа ?

Как структурно организован текст работы ?

Какой материал помещен в основные структурные единицы работы ?

\underline{Введение}

Чем подкреплена данная работа: эксперименты, расчеты… ? Как структурно организован текст работы ?

Для кого написана эта работа ?

Как структурно организован текст работы ?

Какой материал помещен в основные структурные единицы рабо-

ты ? Чем подкреплена данная работа: эксперименты, расчеты… ?

Какой материал помещен в основные структурные единицы работы ? Для кого написана эта работа ? Как структурно организован текст работы ? Какой материал помещен в основные структурные единицы рабо-

ты ? Чем подкреплена данная работа: эксперименты, расчеты… ?

Чем подкреплена данная работа: эксперименты, расчеты… ? Для кого написана эта работа ? Как структурно организован текст работы ? Какой материал помещен в основные структурные единицы рабо-

ты ? Чем подкреплена данная работа: эксперименты, расчеты… ?

Однако слишком �разукрашивать� свою дипломную работу не стоит. Стиль оформления должен быть не рекламный, а достаточно строгий, академический. Желательно остановиться на одном-единственном варианте оформления ненумерованных списков, например, на таком:

▷ современный уровень банковских услуг; ▷ развитие технической и информационной базы банков и их клиентов; ▷ технология работы электронных банковских продуктов; ▷ безопасность проведения расчетов; ▷ возможности и экономическая целесообразность внедрения электронных розничных услуг в коммерческих банках.

Глава 1

Безусловная оптимизация

Здесь пишите … Как показано в гл. 1, подразд. 1.1, пункт 1.1.2 ...

1.1 Функции для минимизации

1.1.1 Название

Здесь пишите …, что в данном пункте 1.1.1

Название

Здесь пишите …, что в данном подпункте

Название

Здесь пишите …, что в данном подпункте

1.1.2 Название

Здесь пишите …, что в данном пункте 1.1.2

Название

Здесь пишите …, что в данном подпункте

Название

Здесь пишите …, что в данном подпункте

1.1.3 Таблица функций для минимизации

Глава 1. Безусловная оптимизация Таблица 1.1. Функции для безусловной минимизации

{� \atop п/п}

Функция f(x)

Начальный вектор x_{0} Точка минимума x^{⋆}

Значение f(x^{⋆})

1 {(1 − x_{1})^{2} + (x_{1} − x_{2})^{2} + \atop + (x_{2} − x_{3})^{2} + (x_{3} − x_{4})^{2}} [−2; 3; −4; 5]  [1; 1; 1; 1]  0
2 (x_{1} − 1)^{2} + 10(x_{2} − 1)^{2} + ; +100(x_{3}−1)^{2}+1000(x_{4}− ; − 1)^{2} [−1; −2; −3; −4] [1; 1; 1; 1]  0
3 100(x_{2} − x_{1}^{2})^{2} + (1 − x_{1})^{2} [3; 4]  [1; 1]  0
4 100(x_{2} − x_{1}^{3})^{2} + (1 − x_{1})^{2} [−1, 2; 1]  [1; 1]  0
5 {(x_{1}+10x_{2})^{2}+5(x_{3}−x_{4})^{2}+ \atop +(x_{2}−2x_{3})^{4}+10(x_{1}−x_{4})^{4}} [3; −1; 0; 1]  [0; 0; 0; 0]  0
6 {x_{1}^{2}+x_{2}^{2}+x_{3}^{2}+x_{4}^{2}+16x_{1}^{2}x_{2}^{2}+ \atop + 8x_{2}^{2}x_{3}^{2} + x_{3}^{2} + x_{4}^{2} + 2} [1; 2; 3; 4]  [0; 0; 0; 0]  0
7 10(x_{1} − sin x_{2})^{2} + 0, 1x_{2}^{2}  [1, 2; 3]  [0; 0]  0
8 (1, 5 − x_{1}(1 − x_{2}))^{2} + ; + (2, 25 − x_{1}(1 − x_{2}^{2}))^{2} + ; + (2, 625 − x_{1}(1 − x_{2}^{3}))^{2} [0; 0]  [3; 0, 5]  0
9 100(x_{2} −x_{1}^{2})^{2} +(1−x_{1})^{2} + ; +90(x_{4}−x_{3}^{2})^{2}+(1−x_{3})^{3}+ ; + 10, 1((x_{2} − 1)^{2} + (x_{4} − ; −1)^{2})+19, 8(x_{2} −1)(x_{4} − ; − 1) [−3; −1; −3; −1] [1; 1; 1; 1]  0
10 {−x_{1} − 2x_{3} − x_{2}x_{3} + x_{1}^{2} + \atop + x_{2}^{2} + x_{3}^{2}} [0; 0; 0]  [\frac{1}{2}; \frac{2}{3}; \frac{4}{3}]  \frac{9}{12}
11 x_{1}^{3} + x_{2}^{3} − 3x_{1}x_{2}  [−1; 3]  [1; 1]  −1
12 2x_{1}x_{2}x_{3} −4x_{1}x_{3} −2x_{2}x_{3} + ; +x_{1}^{2}+x_{2}^{2}+x_{3}^{2}−2x_{1}−4x_{2}+ ; + 4x_{3} [−3; −3; −3]  [1; 2; 0]  −5
13 x_{1}^{4} + x_{2}^{4} − (x_{1} + x_{2})^{2}  [0; 0]  [1; 1] , [−1; −1] −2
14 {x_{1}^{2} + x_{2}^{2} + x_{3}^{2} − x_{1}x_{2} + x_{1} − \atop − 2x_{3}} [2; 2; 2]  [−\frac{2}{3}; \frac{1}{3}; 1]  −\frac{4}{3}

продолжение таблицы на следующей странице

Глава 1. Безусловная оптимизация

продолжение таблицы с предыдущей страницы

{� \atop п/п}

Функция f(x)

Начальный вектор x_{0} Точка минимума x^{⋆}

Значение f(x^{⋆})
15 3x_{1} − x_{1} + x_{2}^{3} − 3x_{2}^{2} − 1 [−1; −1]  [\frac{1}{3}; 2]  −\frac{47}{9}
16 6x_{1} + 2x_{1}^{2} − 2x_{1}x_{2} + 2x_{2}^{2}  [−1; −1]  [−2; −1]  −6
17 x_{1}+x_{2}^{2}+((x_{1}+x_{2}−10)/3)^{2} [−1; −1]  [5; 0, 5]  7, 5
18 (x_{1} − 1)^{2} + 100(x_{1} − x_{2})^{2} [3; 4]  [1; 1]  0
19 5(x_{1} − 3)^{2} + (x_{2} − 5)^{2}  [0; 0]  [3; 5]  0
20 x_{1}^{2} − x_{1}x_{2} + x_{2}^{2}  [1; 2]  [0; 0]  0
21 9x_{1}^{2} + 16x_{2}^{2} − 90x_{1} − 128x_{2} [0; 3]  [5; 4]  −481
22 {2x_{1}^{2} + 2x_{2}^{2} + 2x_{1}x_{2} − 4x_{1} − \atop − 6x_{2}} [1; 1]  [\frac{1}{3}; \frac{4}{3}]  −\frac{14}{3}
23 x_{1}^{2} − x_{1}x_{2} + x_{2}^{2} − 2x_{1} + x_{2} [3; 5]  [1; 0]  −1
24 {5x_{1} + 4x_{1}x_{2} + x_{2}^{2} − 16x_{1} − \atop − 12x_{2}} [1; 1]  [−4; 14]  −152
25 {2x_{1}^{2} + 2x_{2}^{2} + x_{1}x_{2} − 11x_{1} − \atop − 8x_{2}} [−3; −5]  [2; 3]  −23
26 x_{1} − x_{2} + 2x_{1}^{2} + 2x_{1}x_{2} + x_{2}^{2} [1; 1]  [−1; 1, 5]  −1, 25
27 x_{1}^{2} + x_{2}^{2} + x_{1}x_{2}  [1; 1]  [0; 0]  0
28 x_{1}^{2} + 16x_{2}^{2}  [2; 2]  [0; 0]  0
29 (1 − x_{1})^{2} + (x_{1} − x_{2})^{2}  [−5; −8]  [1; 1]  0
30 x_{1}^{2} + 4x_{2}^{2} + 1  [3; 5]  [0; 0]  1

Глава 1. Безусловная оптимизация

1.2 Название

Здесь пишите …

1.2.1 Название Здесь пишите …

Название

Здесь пишите …

Название

Здесь пишите …

1.2.2 Название Здесь пишите …

Название

Здесь пишите …

Название

Здесь пишите …

1.3 Название

Здесь пишите …

1.3.1 Название Здесь пишите …

Название

Здесь пишите …

Глава 1. Безусловная оптимизация

Название

Здесь пишите …

1.3.2 Название

Здесь пишите …

Название

Здесь пишите …

Название

Здесь пишите …

1.4 Название

Здесь пишите …

1.4.1 Название

Здесь пишите …

Название

Здесь пишите …

Название

Здесь пишите …

1.4.2 Название

Здесь пишите …

Название

Здесь пишите …

Название

Здесь пишите …

Название

Здесь пишите … Как показано в гл. 2, подразд. 2.1, пункт 2.1.2 ...

2.1 Название

Здесь пишите …

2.1.1 Название

Здесь пишите …

Название

Здесь пишите …

Название

Здесь пишите …

2.1.2 Название

Здесь пишите …

Название

Здесь пишите …

Название

Здесь пишите …

Глава 2. Название

Рис. 2.1. Множество Жюлиа.

2.2 Название

Здесь пишите …

2.2.1 Название

Здесь пишите …

Название

Здесь пишите …

Название

Здесь пишите …

2.2.2 Название

Здесь пишите …

Название

Здесь пишите …

Глава 2. Название

Название

Здесь пишите …

2.3 Название

Здесь пишите …

2.3.1 Название Здесь пишите …

Название

Здесь пишите …

Название

Здесь пишите …

2.3.2 Название Здесь пишите …

Название

Здесь пишите …

Название

Здесь пишите …

2.4 Название

Здесь пишите …

2.4.1 Название Здесь пишите …

Глава 2. Название

Название

Здесь пишите …

Название

Здесь пишите …

2.4.2 Название

Здесь пишите …

Название

Здесь пишите …

Название

Здесь пишите …

Название

Здесь пишите …

3.1 Название

Здесь пишите …

3.1.1 Название Здесь пишите …

Название

Здесь пишите …

Название

Здесь пишите …

3.1.2 Название Здесь пишите …

Название

Здесь пишите …

Название

Здесь пишите …

Глава 3. Название

3.2 Название

Здесь пишите …

3.2.1 Название Здесь пишите …

Название

Здесь пишите …

Название

Здесь пишите …

3.2.2 Название Здесь пишите …

Название

Здесь пишите …

Название

Здесь пишите …

3.3 Название

Здесь пишите …

3.3.1 Название Здесь пишите …

Название

Здесь пишите …

Глава 3. Название

Название

Здесь пишите …

3.3.2 Название

Здесь пишите …

Название

Здесь пишите …

Название

Здесь пишите …

3.4 Название

Здесь пишите …

3.4.1 Название

Здесь пишите …

Название

Здесь пишите …

Название

Здесь пишите …

3.4.2 Название

Здесь пишите …

Название

Здесь пишите …

Название

Здесь пишите …

Название

Здесь пишите …

4.1 Название

Здесь пишите …

4.1.1 Название Здесь пишите …

Название

Здесь пишите …

Название

Здесь пишите …

4.1.2 Название Здесь пишите …

Название

Здесь пишите …

Название

Здесь пишите …

Глава 4. Название Рис. 4.1. Фрактальное дерево.

Глава 4. Название

4.2 Название

Здесь пишите …

4.2.1 Название Здесь пишите …

Название

Здесь пишите …

Название

Здесь пишите …

4.2.2 Название Здесь пишите …

Название

Здесь пишите …

Название

Здесь пишите …

4.3 Название

Здесь пишите …

4.3.1 Название Здесь пишите …

Название

Здесь пишите …

Глава 4. Название

Название

Здесь пишите …

4.3.2 Название

Здесь пишите …

Название

Здесь пишите …

Название

Здесь пишите …

4.4 Название

Здесь пишите …

4.4.1 Название

Здесь пишите …

Название

Здесь пишите …

Название

Здесь пишите …

4.4.2 Название

Здесь пишите …

Название

Здесь пишите …

Название

Здесь пишите …

Заключение

Здесь пишите … В данной работе освещены аспекты систем электронных расчетов в со-

временном коммерческом банке со следующих точек зрения:

▷ современный уровень банковских услуг;

▷ развитие технической и информационной базы банков и их клиентов;

▷ технология работы электронных банковских продуктов;

▷ безопасность проведения расчетов;

▷ возможности и экономическая целесообразность внедрения электронных розничных услуг в коммерческих банках.

Это, конечно, ПРИМЕР. — Заключение не должно пересказывать основной текст, — этого делать не надо.

В Заключении надо:

• перечислить, какие задачи из числа задач этой работы, сформулированных в разделе �Постановка задачи�, вами решены,

• сформулировать, какие выводы из этих результатов вами найдены и обоснованы в основном тексте работы.

Еще один пример оформления списков (нумерованный список):

1. Перечислить, какие задачи из числа задач этой работы, сформулированных в разделе �Постановка задачи�, вами решены.

2. Сформулировать, какие выводы из этих результатов вами найдены и обоснованы в основном тексте работы.

Здесь пишите … В данной работе освещены аспекты систем электронных расчетов в со-

временном коммерческом банке со следующих точек зрения:

\underline{Заключение}

▷ современный уровень банковских услуг;

▷ развитие технической и информационной базы банков и их клиентов;

▷ технология работы электронных банковских продуктов;

▷ безопасность проведения расчетов;

▷ возможности и экономическая целесообразность внедрения электронных розничных услуг в коммерческих банках.

Это, конечно, ПРИМЕР. — Заключение не должно пересказывать основной текст, — этого делать не надо.

В Заключении надо:

• перечислить, какие задачи из числа задач этой работы, сформулированных в разделе �Постановка задачи�, вами решены,

• сформулировать, какие выводы из этих результатов вами найдены и обоснованы в основном тексте работы.

Еще один пример оформления списков (нумерованный список):

1. Перечислить, какие задачи из числа задач этой работы, сформулированных в разделе �Постановка задачи�, вами решены.

2. Сформулировать, какие выводы из этих результатов вами найдены и обоснованы в основном тексте работы.

Список иллюстраций

2.1 Множество Жюлиа. . . . . . . . . . . . . . . . . . . . . . . . . 14

4.1 Фрактальное дерево. . . . . . . . . . . . . . . . . . . . . . . . . 21

A.1 Алгебраически эквивалентные задачи, решаемые методом наименьших квадратов значений невязки v или среднего квадрата погрешности e: (a) — оптимальное моделирование неизвестной системы по экспериментальным условиям A и данным z; (b) — оптимальное оценивание неизвестного вектора по наблюдениям Ax в присутствии случайных помех v с характеристиками E {v} = 0 и E {vv^{T} } = I . . . . . . . . . . . . . . . . . . . . . . 33

A.2 Геометрия преобразования Хаусхолдера. Задача 1 (прямая): даны векторы u и y, найти вектор y_{r}, отраженный от гиперплоскости U_{⊥} . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

A.3 Геометрия преобразования Хаусхолдера. Задача 2 (обратная): даны векторы y и y_{r}, найти вектор u, задающий отражающую гиперплоскость U_{⊥}; здесь y_{r} = se_{1} = [s | 0 ⋯ 0]^{T} . . . . . . . . 39

A.4 Схематическое представление возможных случаев применения теоремы A.1 к матрице A(m, n); (a) недоопределенная система: k = m − 1 ≤ n; (b) определенная система: k = n − 1, m = n;

(c) переопределенная система: k = n < m; (d) k < n < m … 40

A.5 Сохранение преобразования T и вычисление вектора y = T z, ∀y ∈ ℝ^{m} . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

A.6 Вычисление матрицы A^{−1} после сохранения преобразования T 46

СПИСОК ИЛЛЮСТРАЦИЙ

A.7 Геометрия вращений . . . . . . . . . . . . . . . . . . . . . . . . 46 A.8 Преобразование Гивенса: (a) столбцово ориентированная схема

вычисления матрицы P A, где P = P^{(j)} при j = min (m − 1, n) (нижняя матрица слева); (б) вычисление координаты r вектора (a, b)^{T}, повернутого до совмещения с первой осью, а также косинуса и синуса угла поворота и рабочего признака ζ; (в) строчно ориентированная схема вычисления матрицы P A (верхняя матрица слева); (г) восстановление косинуса и синуса угла поворота из признака ζ; (д) получение вектора y теми преобразованиями P_{j,i} произвольного вектора z ∈ ℝ^{m}, которые сохранены в рабочих признаках ζ_{j,i} и восстанавливаются из них; (е) вследствие (б), векторы 1, 2, 3 и 4 поворачиваются к положительному направлению первой координатной оси, а векторы 5, 6, 7 и 8 поворачиваются к отрицательному направлению этой оси. . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

Список таблиц

1.1 Таблица функций для минимизации . . . . . . . . . . . . . . . 9

Список использованной литературы

A.1 Эффективное обращение верхнетреугольной матрицы: U := R^{−1}. Реализуются формулы (A.31), (A.32) и (A.33). Верхнетреугольные матрицы R и U хранятся как векторы размерности N(N + 1)/2. Если нужно, U может замещать R. . . . . . . . . 45 1. Андриевский, Б. Р. Избранные главы теории автоматического управле-

ния с примерами на языке MATLAB / Б. Р. Андриевский, А. Л. Фрадков.

— СПб. : Наука, 2000.

2. Араманович, И. Г. Функции комплексного переменного. Операционное исчисление. Теория устойчивости / И. Г. Араманович, Г. Л. Лунц, Л. Э. Эльсгольц. — М. : Наука, 1965.

3. Евграфов, М. А. Аналитические функции / М. А. Евграфов. — М. : Наука, 1965.

4. Корн, Г. Справочник по математике (для научных работников и инженеров) / Г. Корн, Т. Корн. — М. : Наука, 1974.

5. Лаврентьев, М. А. Методы теории функций комплексного переменного / М. А. Лаврентьев, Б. В. Шабат. — М. : Наука, 1987.

6. Медич, Дж. Статистически оптимальные линейные оценки и управление / Дж. Медич. — М. : Энергия, 1973.

7. Острем, К. Ю. Введение в стохастическую теорию управления / К. Ю. Острем. — М. : Мир, 1973.

8. Пугачев, В. С. Основы стохастической теории автоматических систем / В. С. Пугачев, И. Е. Казаков, Л. Г. Евланов. — М. : Наука, 1980.

9. Свешников, А. Г. Теория функций комплексной переменной / А. Г. Свешников, А. Н. Тихонов. — М. : Наука, 1979.

10. Соломенцев, Е. Д. Функции комплексного переменного и их применения / Е. Д. Соломенцев. — М. : Высшая школа, 1988.

11. Андриевский, Б. Р. Избранные главы теории автоматического управления с примерами на языке MATLAB / Б. Р. Андриевский, А. Л. Фрадков.

— СПб. : Наука, 2000.

12. Араманович, И. Г. Функции комплексного переменного. Операционное исчисление. Теория устойчивости / И. Г. Араманович, Г. Л. Лунц, Л. Э. Эльсгольц. — М. : Наука, 1965.

13. Евграфов, М. А. Аналитические функции / М. А. Евграфов. — М. : Наука, 1965.

14. Корн, Г. Справочник по математике (для научных работников и инженеров) / Г. Корн, Т. Корн. — М. : Наука, 1974.

15. Лаврентьев, М. А. Методы теории функций комплексного переменного / М. А. Лаврентьев, Б. В. Шабат. — М. : Наука, 1987.

16. Медич, Дж. Статистически оптимальные линейные оценки и управление / Дж. Медич. — М. : Энергия, 1973.

17. Острем, К. Ю. Введение в стохастическую теорию управления / К. Ю. Острем. — М. : Мир, 1973.

18. Пугачев, В. С. Основы стохастической теории автоматических систем / В. С. Пугачев, И. Е. Казаков, Л. Г. Евланов. — М. : Наука, 1980.

19. Свешников, А. Г. Теория функций комплексной переменной / А. Г. Свешников, А. Н. Тихонов. — М. : Наука, 1979.

20. Соломенцев, Е. Д. Функции комплексного переменного и их применения / Е. Д. Соломенцев. — М. : Высшая школа, 1988.

21. Андриевский, Б. Р. Избранные главы теории автоматического управления с примерами на языке MATLAB / Б. Р. Андриевский, А. Л. Фрадков.

— СПб. : Наука, 2000.

22. Араманович, И. Г. Функции комплексного переменного. Операционное исчисление. Теория устойчивости / И. Г. Араманович, Г. Л. Лунц, Л. Э. Эльсгольц. — М. : Наука, 1965.

23. Евграфов, М. А. Аналитические функции / М. А. Евграфов. — М. : Наука, 1965.

24. Корн, Г. Справочник по математике (для научных работников и инженеров) / Г. Корн, Т. Корн. — М. : Наука, 1974.

25. Лаврентьев, М. А. Методы теории функций комплексного переменного / М. А. Лаврентьев, Б. В. Шабат. — М. : Наука, 1987.

26. Медич, Дж. Статистически оптимальные линейные оценки и управление / Дж. Медич. — М. : Энергия, 1973.

27. Острем, К. Ю. Введение в стохастическую теорию управления / К. Ю. Острем. — М. : Мир, 1973.

28. Пугачев, В. С. Основы стохастической теории автоматических систем / В. С. Пугачев, И. Е. Казаков, Л. Г. Евланов. — М. : Наука, 1980.

29. Свешников, А. Г. Теория функций комплексной переменной / А. Г. Свешников, А. Н. Тихонов. — М. : Наука, 1979.

30. Соломенцев, Е. Д. Функции комплексного переменного и их применения / Е. Д. Соломенцев. — М. : Высшая школа, 1988.

31. Андриевский, Б. Р. Избранные главы теории автоматического управления с примерами на языке MATLAB / Б. Р. Андриевский, А. Л. Фрадков.

— СПб. : Наука, 2000.

32. Араманович, И. Г. Функции комплексного переменного. Операционное исчисление. Теория устойчивости / И. Г. Араманович, Г. Л. Лунц, Л. Э. Эльсгольц. — М. : Наука, 1965.

33. Евграфов, М. А. Аналитические функции / М. А. Евграфов. — М. : Наука, 1965.

34. Корн, Г. Справочник по математике (для научных работников и инженеров) / Г. Корн, Т. Корн. — М. : Наука, 1974.

35. Лаврентьев, М. А. Методы теории функций комплексного переменного / М. А. Лаврентьев, Б. В. Шабат. — М. : Наука, 1987.

36. Медич, Дж. Статистически оптимальные линейные оценки и управление / Дж. Медич. — М. : Энергия, 1973.

37. Острем, К. Ю. Введение в стохастическую теорию управления / К. Ю. Острем. — М. : Мир, 1973.

38. Пугачев, В. С. Основы стохастической теории автоматических систем / В. С. Пугачев, И. Е. Казаков, Л. Г. Евланов. — М. : Наука, 1980.

39. Свешников, А. Г. Теория функций комплексной переменной / А. Г. Свешников, А. Н. Тихонов. — М. : Наука, 1979.

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

40. Соломенцев, Е. Д. Функции комплексного переменного и их применения / Е. Д. Соломенцев. — М. : Высшая школа, 1988.

Приложение A

Ортогональные преобразования

A.1 Ортогональные матрицы и приложения

В этом разделе напомним определение и некоторые свойства ортогональных матриц, полезные для дальнейшего.

Определение 1.1. Матрица T, имеюшая размер n×n, т.е.T (n, n), есть ортогональная матрица, если и только если T T^{T} = I.

Свойство A. Если T_{1} и T_{1} суть две ортогональные матрицы, то их произведение T_{1}T_{2} есть тоже ортогональная матрица.

Свойство B. T^{−1} = T^{T} и T^{T} T = I.

Свойство C. Ортогональное преобразование сохраняет скалярное произведение векторов, т. е.∀x, y ∈ ℝ^{n} : y^{T} x ≜ (x, y) = (T x, T y), в частности, оно сохраняет (евклидову) норму вектора: ∥T y∥ = ∥y∥.

Свойство D. Если v есть вектор случайных переменных с математическим ожиданием E {v} = 0 и ковариацией E {vv^{T} } = I, то теми же характеристиками обладает вектор v̄ = T v, т. е.

E \left\{{ \atop v̄}\right\} = 0, E \{v̄v̄^{T} \} = I.

Хотя это свойство легко проверяется, немного удивительно, что компоненты преобразованного вектора остаются взаимно некоррелированными.

Свойства C и D играют существенную роль в квадратно-корневых алгоритмах решения прикладных задач оптимального моделирования и оптимального оценивания методом наименьших квадратов (рис. A.1).

Приложение A. Ортогональные преобразования

x  − • •  Модель  ∥v∥^{2} → min_{x} A  Система  z Ax  v = z − Ax A  x̃ +  • •  Оценка E {∥e∥^{2}} → min_{x̃} x  Наблюдение  z Ax  v x̂  x̂ −  x̃ (a) (b) Неизвестный вектор  e = x̃ − x

Рис. A.1. Алгебраически эквивалентные задачи, решаемые методом наименьших квадратов значений невязки v или среднего квадрата погрешности e: (a) — оптимальное моделирование неизвестной системы по экспериментальным условиям A и данным z; (b) — оптимальное оценивание неизвестного вектора по наблюдениям Ax в присутствии случайных помех v с характеристиками E {v} = 0 и E {vv^{T} } = I

A.2 Линейная задача наименьших квадратов

Линейная задача наименьших квадратов (см. рис. A.1) ставится следующим образом.

Дано линейное уравнение

z = Ax + v,  (A.1)

в котором известны вектор z ∈ ℝ^{m} и (m × n)-матрица A ∈ ℝ^{m×n}, т. е.A = A(m, n). Разностный вектор v ≜ z − Ax, называемый невязкой, зависит от переменного вектора x ∈ ℝ^{n}. Требуется найти значение x̂ вектора x, минимизирующее квадратический критерий качества

J(x) = (z − Ax)^{T} (z − Ax) = ∥v∥^{2} → min .  (A.2)

Если ни при каком x невязка v не может быть обращена в 0 — нулевой вектор, то система Ax = z — несовместная, в противном случае совместная, т. е.критерий (A.2) охватывает оба случая. Однако сам метод наименьших квадратов (МНК), выраженный критерием (A.2), создан Лежандром в 1805 году как алгебраическая процедура именно для несовместных систем и подтвержден как статистическая процедура Гауссом в 1809 году [?]. МНК как алгебраическая процедура проиллюстрирован выше с помощью рис. A.1(a), а как статистическая процедура — с помощью рис. A.1(b). Замечательно, что обе процедуры имеют одинаковые решения, т. е.алгебраически эти решения эквивалентны и при E {v} = 0 и E {vv^{T} } = I (см. рис. A.1(b)) совпадают, поэтому можно говорить о едином МНК-решении x̂.

МНК-решение x̂ всегда существует как решение нормальных уравнений

A^{T} Ax̂ = A^{T} z,  (A.3)

выражается формулой

x̂ = A^{+}z + (I − A^{+}A)y  (A.4)

через произвольный вектор y ∈ ℝ^{n}, где A^{+} — псевдообратная матрица для матрицы A, и единственно тогда и только тогда, когда A^{+}A = I, что равносильно условию, что только нулевой вектор составляет ядро (нульпространство) матрицы A, т. е.при rank A = n.

Условие rank A = n, называемое условием полного столбцового ранга матрицы A, обусловливает случай m ≥ n, что при m > n означает переопределенную систему полного ранга в (A.1). Этот типичный для практики случай ниже и рассматривается, при этом из (A.3), (A.4) следует x̂ = A^{+}z и A^{+} = (A^{T} A)^{−1}A^{T}.

Замечание A.1. Слагаемое x̂_{0} ≜ A^{+}z в (A.4) есть единственное МНК-решение с минимальной нормой, называемое нормальным псевдорешением. Оно ортогонально второму слагаемому в (A.4), т.е.A^{+}z ⊥ (I − A^{+}A)y, и лежит в пространстве строк матрицы A, т. е.x̂_{0} ∈ R(A^{T}).

Таким образом, типичный для практики случай имеет формальное решение x̂ = x̂_{0} = (A^{T} A)^{−1}A^{T} z, и вычислительная задача наименьших квадратов заключается в его эффективном отыскании.

A.3 Ортогональные матрицы в задаче о наименьших квадратах

В рассматриваемой задаче о наименьших квадратах

J(x) = ∥z − Ax∥^{2}, A(m, n), m ≥ n, rank A = n.  (A.5)

Пусть T, T (m, m), есть матрица некоторого ортогонального преобразования. В силу свойства C (см. разд. A.1) запишем

J(x) = ∥T (z − Ax)∥^{2} = ∥(T z) − (T A)x∥^{2}.  (A.6)

При таком представлении видно, что минимум критерия J(x), равный J(x̂), не зависит от T. Этом фактом можно воспользоваться, т.е.матрицу T можно выбрать так, что (T A) приобретает привлекательную для вычислений форму. Действительно, в разд. A.4 и A.7 мы покажем, как можно выбрать T, чтобы преобразованная матрица имела вид

T A =\begin{aligned}[ \begin{matrix}R \\ 0 \end{matrix} ] & \} n \\ & \} m − n \end{aligned}  (A.7)

с верхнетреугольным блоком R, rank R = n.

Если соответственно этому вектор T z разбить на блоки, т. е.записать

T z =\begin{aligned}[ \begin{matrix}z_{1} \\ z_{2} \end{matrix} ] & \} n \\ & \} m − n \end{aligned} ,  (A.8)

то J(x) от (A.6) приводится к виду

J(x) = ∥z_{1} − Rx∥^{2} + ∥z_{2}∥^{2}.  (A.9)

Приведение критерия наименьших квадратов к виду (A.9) позволяет видеть, что искомый вектор x̂, минимизирующий этот критерий, должен удовлетворять уравнению

Rx̂ = z_{1},  (A.10)

которое легко решается обратной подстановкой (см. разд. A.6), и кроме того,

min J(x) = J(x̂) = ∥z_{2}∥^{2}.  (A.11)

В вычислительном отношении эти результаты гораздо более элегантны, чем неразумная трата сил на решение нормальных уравнений (A.3). Но важнее всего то, что решение, использующее ортогональные преобразования (соотношения (A.7), (A.8), (A.10) и (A.11)), менее чувствительны к погрешностям, вызванным ошибками округления в компьютере. Это видно хотя бы из того, что выражение (A.7) влечет равенство

R^{T} R = (T A)^{T} (T A) = A^{T} A,

которое означает, что R является квадратным корнем из матрицы (A^{T} A) системы нормальных уравнений (A.3). Следовательно, при решении системы (A.10) вдвое более эффективно используется разрядная сетка компьютера, чем при решении системы (A.3)^{1}.

A.4 Преобразование Хаусхолдера

Преобразования Хаусхолдера суть матричные представления, которые соответствуют геометрическому понятию отражения. Пусть задан некоторый ненулевой вектор u, который мы называем направляющим вектором. Подпространство, ортогональное ему, есть гиперплоскость U_{⊥}. Если взять произвольный вектор y, то можно отразить его от U_{⊥}, в точности соблюдая законы обычного оптического отражения от плоского зеркала (рис. A.2).

Обозначим отраженный вектор y_{r}. Поскольку положение гиперплоскости U_{⊥} не зависит от длины направляющего вектора, пронормируем его, т. е.образуем орт û = u/∥u∥. Проекция (y | u) вектора y на прямую, задаваемую направлением u, равна (y^{T} û)û. Следовательно,

y = (y | u) + v, v ⊥ u, v ∈ U_{⊥}.  (A.12)

1 Представление в компьютере квадрата a^{2} любого действительного числа a требует удвоенной разрядности мантиссы, т. е.счет по уравнению (A.10) равносилен счету с удвоенной разрядностью мантиссы чисел по уравнению (A.3).

Приложение A. Ортогональные преобразования

U_{⊥} y_{r} − y y_{r}  v  y (y | u)  u −(y | u)  0

Рис. A.2. Геометрия преобразования Хаусхолдера. Задача 1 (прямая): даны векторы u и y, найти вектор y_{r}, отраженный от гиперплоскости U_{⊥}

Отраженный вектор y_{r}, как видно из рис. A.2, имеет разложение

y_{r} = −(y | u) + v, v ⊥ u, v ∈ U_{⊥}  (A.13)

с той же составляющей v, которая ортогональна вектору u, но с проекцией −(y | u), которая (в силу знака −) направлена противоположно проекции (y | û) вектора y на направление u. Исключая v из (A.12) и (A.13), находим

y_{r} = y − 2(y | u) = (I − βuu^{T})y = T_{u}y,  (A.14)

где β ≜ 2/∥u∥^{2} = 2/u^{T} u. Матрица T_{u} ≜ (I − βuu^{T}), в вычислениях явно не участвующая, имеет фундаментальное значение для приложений в силу своих замечательных свойств.

Свойство 1. T_{u} = T_{u}^{T}, т. е.T_{u} — симметрическая матрица.

Свойство 2. T_{u}^{2} = I, т. е.T_{u} — идемпотентная матрица. Это легко продемострировать алгебраически разложением матрицы T_{u}^{2} или же геометрически по рис. A.2 как двукратное отражение вектора y относительно U_{⊥}.

Свойство 3. Если u(j) = 0, то (T_{u}y)(j) = y(j), т. е.если j-я компонента вектора u — нулевая, то T_{u} оставляет j-ю компоненту вектора y неизменной.

Свойство 4. Если u ⊥ y, то T_{u}y = y.

Свойство 5.

T_{u}y = y − γu,  γ ≜ 2y^{T} u/u^{T} u = βy^{T} u.  (A.15)

Свойство 5 важно с практической точки зрения. Формирование матрицы T_{u} в качестве множителя для y потребовало бы на порядок больше вычислений, чем того требует прямое вычисление T_{u}y по свойству 5. Это также означает, что не нужно тратить память для хранения T_{u}, что наиболее существенно проявляется при больших m.

Триангуляризация матрицы преобразованиями Хаусхолдера. Обратимся к основному применению ортогональных преобразований. Для этого решим задачу, обратную к той, что рассмотрена выше, а именно: дан вектор y и дано желаемое расположение отраженного вектора y_{r}, — найти направление u такое, что T_{u}y = (s, 0, …, 0)^{T} (рис. A.3). Из свойства C, разд. A.1, норма (евклидова длина) вектора y не изменяется при ортогональном преобразовании, следовательно, определим ее как

σ ≜ ∥T_{u}y∥ = |s| = (y^{T} y)^{1/2}.  (A.16)

Направление u может быть получено из свойства 5 (уравнение (A.15)), т. е.

u = const · (y − se_{1}).  (A.17)

Этот результат приводит к следующему свойству.

Свойство 6. Пусть s = − sgn [y(1)]σ, где sgn [·] — функция знака,

sgn [x] = \begin{cases}1, & x ≥ 0, \\ −1, & x < 0, \end{cases}

и элементы вектора u определены выражением (A.17), т. е.u(1) = y(1) − s, u(i) = y(i), i > 1. Тогда T_{u}y = se_{1} и β ≜ 2/u^{T} u = −1/(su(1)).

Замечание A.2. Геометрический смысл выражения (A.17) ясен из рис. A.3, где видно, что вектор y_{r} ортогонален гиперплоскости U_{⊥} и параллелен вектору u.

Непосредственное вычисление u^{T} u показывает, что u^{T} u = −2su(1), при этом знак для s выбран противоположно знаку первого элемента y(1), т. е.так, чтобы максимизировать |u(1)| и тем уменьшить относительную погрешность вычисления разности u(1) = y(1) − s. Если свойство 6 применить к матрице A, взяв в качестве y ее первый столбец, то это даст первый шаг, который послужит основой приведения матрицы к верхнетреугольному виду. Повторение таких действий шаг за шагом позволит осуществлять верхнюю триангуляризацию любой заданной матрицы A.

Приложение A. Ортогональные преобразования

y_{r} a_{r}  U_{⊥}  e_{2} 0  a  y u e_{1}

Рис. A.3. Геометрия преобразования Хаусхолдера. Задача 2 (обратная): даны векторы y и y_{r}, найти вектор u, задающий отражающую гиперплоскость U_{⊥}; здесь y_{r} = = se_{1} = [s | 0 ⋯ 0]^{T}

Лемма A.1. Пусть дана матрица A(m, n). Тогда существует ортогональное преобразование Хаусхолдера T_{u} такое, что

T_{u}A = \begin{matrix}^{1} & ^{n−1} \\ 1\{ & [ s | ; 0 | Ã ; | ] . \\ m−1 & \{ \end{matrix}  (A.18)

Замечание A.3. Скаляр s и матрица Ã в (A.18) вычисляются непосредственно по данным в матрице A; s — по выражению (A.16) и свойству 6, а Ã — по свойству 5, (A.15). Первый столбец, который уместно назвать ведущим столбцом, используют как вектор y в задаче 2 (см. рис. A.3) для определения вектора u. Второй и далее столбцы, обозначенные на рис. A.3 произвольно как вектор a, отражают от найденной таким образом гиперплоскости U_{⊥}, решая для этого задачу 1 (см. рис. A.2) с y := a и тем самым получая блок Ã.

Теорема A.1 (Триангуляризация матрицы по методу Хаусхолдера). Пусть A_{1} := A(m, n) и для каждого j выбрано элементарное преобразование Хаусхолдера T_{j} так, что

T_{j}A_{j} = \begin{matrix}^{1} & ^{n−j} \\ 1\{ & [ s_{j} | a_{j}^{T} ; 0 | A_{j+1} ; | ] , \\ m−j & \{ \end{matrix} j = 1, …, k; k ≤ min (m−1, n). (A.19)

Тогда в процессе после k повторных применений свойства 6 и леммы A.1 имеем следующий промежуточный результат триангуляризации матрицы A:

s_{1}  a_{1}^{T} s_{2}  a_{2}^{T}_{...}  ⋮ s_{k} a_{k}^{T} A_{k+1} 0 T^{(k)}A =  (A.20)

с отвечающей этому моменту процесса итоговой матрицей преобразований

T^{(k)} = [ \begin{matrix}I_{k−1} & 0 \\ 0 & T_{k} \end{matrix} ] ⋯ [ \begin{matrix}I_{1} & 0 \\ 0 & T_{2} \end{matrix} ] T_{1} .  (A.21)

Замечание A.4. Важно подчеркнуть, что алгоритм триангуляризации (A.19) не требует вычисления или запоминания ортогональной матрицы T^{(k)}, так как правая часть равенства (A.4) вычисляется непосредственно в соответствии с замечанием A.3. Стоит также заметить, как неявно определяется A_{j+1} рекурсией по j в алгоритме (A.19). Кроме A_{j+1}, на шаге j этой рекурсии определяются скаляр s_{j} и (n−j) компонент вектор-строки a_{j}^{T}. Эти неявные соотношения для s_{j}, a_{j}^{T} и A_{j+1} и весь процесс вычислений (рис. A.4) представлены в явном виде в разд. A.5.

\underbrace{n}_{m \{} \overbrace{m}  _{n \{} \underbrace{n} _{m \{} \underbrace{n}_{\} n} _{m \{} \underbrace{n} \overbrace{k} 0  0  0  0_{(a)}  _{(b)}  _{(c)}  _{(d)}

Рис. A.4. Схематическое представление возможных случаев применения теоремы A.1 к матрице A(m, n); (a) недоопределенная система: k = m − 1 ≤ n; (b) определенная система: k = n − 1, m = n; (c) переопределенная система: k = n < m; (d) k < n < m

A.5 Шаг триангуляризации матрицы преобразованием Хаусхолдера

Пусть матрица A = A(m, n) задана. Тогда, согласно лемме A.1, базовая операция процесса триангуляризации заключается в вычислении скаляра s и матрицы Ã = Ã(m, n − 1) таких, что

T_{u}A = \begin{matrix}^{1} & ^{n−1} \\ 1\{ & [ s | ; 0 | Ã ; | ] . \\ m−1 & \{ \end{matrix}  (A.22)

Алгоритм. Для вычисления s следует применять свойство 6, т.е.выполнять (A.23) для всех k = 1 до min (m−1, n). Затем для вычисления Ã следует применять свойство 5, т.е.последовательно в цикле по j = 2, …, n для всех i = k, …, m выполнять (A.24) с λ ≜ −γ (см. (A.15)). Здесь введена величина α ≜ −β (см. (A.14) и свойство 6).

Для k = 1 до min (m − 1, n)

\begin{matrix}s_{k} & = − sgn [A(k, k)] (∑_{i=k}^{m} [A(i, k)]^{2})^{1/2} , \\ u_{k}(1) & = A(k, k) − s_{k}, \\ u_{k}(i) & = A(k + i − 1, k), i = 2, …, m − k + 1, \\ α_{k} & = 1/(s_{k}u_{k}(1)) (α_{k} < 0). \end{matrix} \}  (A.23)

Для j = k + 1, …, n

\begin{matrix}λ & := α_{k} · ∑_{i=k}^{m} u_{k}(i − k + 1)A(i, j), \\ Для i = k, k + 1, …, m \\ A(i, j) := A(i, j) + λu_{k}(i − k + 1). \end{matrix} \}  (A.24)

Приведенный алгоритм (A.23), (A.24) называют столбцово ориентированным, так как операции (A.24) вычисляют целиком каждый j-й столбец матрицы, находящийся справа от ведущего, т. е.k-го столбца.

Альтернативная схема вычислений называется строчно ориентированным алгоритмом. Ее можно получить из выражения T_{u} = I − βuu^{T} для матрицы Хаусхолдера следующим образом.

Введем вспомогательные обозначения: μ ≜ \sqrt{β}, w ≜ μu, чтобы записать T_{u} = I − ww^{T}. Тогда (T_{u}A) = A − wz^{T}, где z^{T} ≜ w^{T} A = μv^{T}, v^{T} ≜ ∑_{i=1}^{m} u(i)A(i, ·) и A(i, ·) есть i-я строка матрицы A = A(m, n). Введем обозначение λ^{T} = αv^{T}, используя ранее введенное (см. (A.23)) α ≜ −β. Отсюда получаем формулу для любой i-й строки (T_{u}A)(i, ·) преобразованной матрицы (T_{u}A) в виде

(T_{u}A)(i, ·) = A(i, ·) − w(i)z^{T} = A(i, ·) − μ^{2}u(i)v^{T} = A(i, ·) + λ^{T} u(i).

Алгоритм (строчно ориентированный), эквивалентный (A.23) и (A.24). Для k = 1 до min (m − 1, n)

\begin{matrix}s_{k} & = − sgn [A(k, k)] (∑_{i=k}^{m} [A(i, k)]^{2})^{1/2} , \\ u_{k}(1) & = A(k, k) − s_{k}, \\ u_{k}(i) & = A(k + i − 1, k), i = 2, …, m − k + 1, \\ α_{k} & = 1/(s_{k}u_{k}(1)) (α_{k} < 0). \end{matrix} \}  (A.25)

Для j = k + 1, …, n

\begin{matrix}λ_{k}(j − k) := α_{k} · ∑_{i=k}^{m} & u_{k}(i − k + 1)A(i, j), \\ Для i = k, k + 1, …, m \\ Для j = k + 1, …, & n \\ A(i, j) := A(i, j) & + λ_{k}(j − k)u_{k}(i − k + 1). \end{matrix} \}  (A.26)

A.6 Решение треугольной системы Rx = z и обращение матриц R и A

Как отмечено в разд. A.3, мы часто заинтересованы в решении уравнения

Rx = z,  (A.27)

где R = R(n, n) — верхнетреугольная невырожденная матрица. Если нужно иметь только решение x, то R^{−1} (для x = R^{−1}z) вычислять не надо. Следующий алгоритм обратной подстановки позволяет вычислить решение x непосредственно.

Алгоритм. Для j = n, n − 1, …, 1 вычислять

x(j) = (z(j) − ∑_{k=j+1}^{n} R(j, k)x(k)) /R(j, j).  (A.28)

По сложности этот алгоритм почти такой же, как матричное умножение. Он допускает записывать x(j) поверх z(j), что очень удобно в приложениях.

Если все же требуется иметь матрицу U ≜ R^{−1}, то ее можно вычислить по алгоритму окаймления, основанному на следующем легко проверяемом тождестве для треугольных матриц:

[ \begin{matrix}R_{j} & y \\ 0 & σ_{j+1} \end{matrix} ]^{−1} = [ \begin{matrix}R_{j}^{−1} & −R_{j}^{−1}yσ_{j+1}^{−1} \\ 0 & σ_{j+1}^{−1} \end{matrix} ] = R_{j+1}^{−1} .  (A.29)

Это соотношение позволяет вычислять обратную матрицу U ≜ R^{−1} рекуррентно, т.е., если R_{j}^{−1} = U_{j}, где R_{j} обозначает верхнюю левую часть матрицы R, то

U_{j+1} = [ \begin{matrix}U_{j} & −U_{j} [R(1, j + 1), …, R(j, j + 1)]^{T} σ_{j+1} \\ 0 & σ_{j+1} \end{matrix} ] ,  (A.30)

где σ_{j+1} = 1/R(j + 1, j + 1). Полагая U = R_{−1}, этот результат представим в алгоритмической форме.

Алгоритм. Задать начальное значение

U(1, 1) = 1/R(1, 1).  (A.31)

Для j = 2, …, n вычислять по формулам (A.32) и (A.33):

U(j, j) = 1/R(j, j),  (A.32)
U(k, j) = − (∑_{i=k}^{j−1} U(k, i)R(i, j)) U(j, j), k = 1, …, j − 1.  (A.33)

Замечание A.5. R^{−1} вычисляется по столбцам, при этом элементы матрицы R^{−1} могут записываться поверх элементов исходной матрицы R.

В справочных целях приведем примеры реализации данного алгоритма на языке FORTRAN. Эти примеры могут помочь студентам написать свои собственные программы на других языках высокого уровня при выполнении лабораторного проекта � 6, описание которого дано ниже в подразд. ??.

Обращение верхнетреугольной матрицы: U := R^{−1}. Реализуются формулы (A.31), (A.32) и (A.33). Если нужно, U может замещать R.

R(N, N), U(N, N), R и U — верхнетреугольные матрицы.
U(1, 1) = 1./R(1, 1)
DO 20 J = 2, N
U(J, J) = 1./R(J, J)
JM1 = J − 1
DO 20 K = 1, JM1
SUM = 0.
DO 10 I = K, JM1
10 SUM = SUM − U(K, I) ∗ R(I, J)
20 U(K, J) = SUM ∗ U(J, J)

В случаях, когда важно или нужно экономить память компьютера, матрицы в программе объявляют как одномерные массивы (см. подразд. ??). Хотя в компьютере даже многомерно объявленные массивы всегда хранятся как одномерные, компилятор генерирует индексные выражения с операциями умножения и деления. Операции сложения и вычитания в компьютерах выполняются гораздо быстрее, поэтому индексы для доступа к элементам матриц следует программировать в рекуррентной инкрементной форме, экономя таким образом и время процессора (табл. A.1). В этой программе преобразование в треугольную форму выполняется отождествлением J(J − 1)/1 + I с (I, J). Рекуррентное инкрементное вычисление KK, JJ и KK экономит вычисления.

Как отмечалось на с. 43, иногда требуется вычислять R^{−1}. Такая ситуация появляется, если требуется найти A^{−1}, для которой уже выполнено преобразование T A = R, где T = T^{(n−1)} по формуле (A.21), так как в теореме A.1 для этого случая m = n и A^{−1} = R^{−1}T. Последнее означает, что то же самое ортогональное преобразование T теперь надо применить к строкам матрицы R^{−1}, но уже в обратном порядке следования элементарных преобразований, составляющих полное преобразование T = T^{(n−1)} по формуле (A.21). Таким образом, возникает проблема запоминания элементарных преобразований, составляющих полное преобразование T = T^{(n−1)}, чтобы позже можно было его применить в задаче отыскания A^{−1} или же для решения уравнения Ax = z с невырожденной матрицей A после пребразования T A = R.

Как видно из (A.24), для отражения любого вектора y = T^{(k)}z от гиперплоскости U_{⊥}, заданной вектором u, требуется иметь сохраненными две

Таблица A.1. Эффективное обращение верхнетреугольной матрицы: U := R^{−1}. Реализуются формулы (A.31), (A.32) и (A.33). Верхнетреугольные матрицы R и U хранятся как векторы размерности N(N + 1)/2. Если нужно, U может замещать R.

R(N, N), U(N, N), R и U — верхнетреугольные матрицы .
U(1) = 1./R(1)  \begin{matrix}c \\ ◯ \end{matrix} R(1) ≡ R(1, 1)
JJ = 1
DO 20 J = 2, N
\overline{JJ} = JJ  {\begin{matrix}c \\ ◯ \end{matrix} \overline{JJ} = J(J − 1)/2 = (J − \atop 1, J − 1)}
JJ = JJ + J  \begin{matrix}c \\ ◯ \end{matrix} JJ = J(J + 1)/2 = (J, J)
U(JJ) = 1./R(JJ)
JM1 = J − 1
KK = 0
DO 20 K = 1, JM1
KK = KK + K  \begin{matrix}c \\ ◯ \end{matrix} KK = K(K + 1)/2
KI = KK
SUM = 0.
DO 10 I = K, JM1
SUM = SUM − U(KI) ∗ R(\overline{JJ} + I) {\begin{matrix}c \\ ◯ \end{matrix} KI = (K, I), \overline{JJ} + 1 = \atop = (I, J)}
10 KI = KI + I  \begin{matrix}c \\ ◯ \end{matrix} KI = (K, I + 1)
20 U(\overline{JJ} + K) = SUM ∗ U(JJ)  \begin{matrix}c \\ ◯ \end{matrix} \overline{JJ} + K = (K, J)

величины: вектор u и скаляр α. Поскольку нули ниже диагонали, получающиеся в результате триангуляризации, хранить не нужно, это место можно отвести для сохранения вектора u (вместе с диагональю, поэтому диагональные элементы s_{k} приходится хранить отдельно). Данное предложение схематически показано на рис. A.5. Каким образом можно выполнить вычисление матрицы A^{−1}, показано на рис. A.6 на конкретном примере размерностей, а именно: m = 4, n = 4.

A.7 Преобразование Гивенса

Преобразование Гивенса осуществляет вращение вектора в плоскости двух координат. Поскольку поворот вектора y = (y_{1} | y_{2})^{T} на угол θ по часовой стрелке эквивалентен повороту системы координат против часовой стрелки на тот же угол, легко найти (рис. A.7), что координаты y′_{1}, y′_{2} повернутого вектора y_{r} = (y′_{1} | y′_{2})^{T} определяются в виде y′_{1} = y_{1} cos θ + y_{2} sin θ, y′_{2} = −y_{1} sin θ + y_{2} cos θ.

Приложение A. Ортогональные преобразования

z_{1}

u_{k}

a_{k}^{T}

α_{1} ⋯ α_{k} ⋯ α_{n}

T^{(k)}A = {

k ⇓ T^{(k)}z T z

y_{k}
y_{m}

⋮
z_{2}

s_{1} ⋯ ⋯ s_{k} s_{n}

R

Для k = 1 до min (m − 1, n)

λ = α_{k} ∑_{i=k}^{m} u_{k}(i − k + 1)y_{i}

Для i = k до m

y_{i} := y_{i} + λu_{k}(i − k + 1)

T A =\begin{aligned}[ \begin{matrix}R \\ 0 \end{matrix} ] & \} n \\ & \} m − n \end{aligned} , Rx = z_{1}

Рис. A.5. Сохранение преобразования T и вычисление вектора y = T z, ∀y ∈ ℝ^{m} u_{1}

u_{2} u_{3} a_{1}^{T}

a_{2}^{T} a_{3}^{T} s_{4} A

[ \begin{matrix}—–—y_{1}^{T} —–— \\ —–—y_{2}^{T} —–— \\ —–—y_{3}^{T} —–— \\ —–—y_{4}^{T} —–— \end{matrix}]

↪ Y := R^{−1}

R = [ \begin{matrix}s_{1} & & & a_{1}^{T} \\ & s_{2} & & a_{2}^{T} \\ & & s_{3} & a_{3}^{T} \\ 0 & & & s_{4} \end{matrix} ]

⟶

↘ ↑

↩

Для k = n − 1, …, 2, 1

Для r = 1 до n

λ = α_{k} ∑_{i=k}^{n} u_{k}(i − k + 1)y_{r}(i)

Для i = k до n

y_{r}(i) := y_{r}(i) + λu_{k}(i − k + 1)

↓

Y := A^{−1} s_{1} s_{2} s_{3}

α_{1} α_{2} α_{3}

Рис. A.6. Вычисление матрицы A^{−1} после сохранения преобразования T

e′_{2}  0 e_{2}  yθ e′_{1}e_{1}

Рис. A.7. Геометрия вращений

Записывая это в матричной форме и требуя, чтобы поворот P_{1,2} в плоскости (e_{1}, e_{2}) происходил до совмещения с первой координатной осью, получим

y_{r} = [ \begin{matrix}c & s \\ −s & c \end{matrix} ] y = P_{1,2}y = [ \begin{matrix}r \\ 0 \end{matrix} ] , \{ \begin{matrix}c ≜ cos θ = y_{1}/r \\ s ≜ sin θ = y_{2}/r \end{matrix} \} , r ≜ \sqrt{y_{1}^{2} + y_{2}^{2}},

где, очевидно, матрица P_{1,2} плоского вращения ортогональна при любом θ.

Триангуляризация матрицы преобразованиями Гивенса. Выбор θ такой, что вторая координата вектора y_{r} становится равной нулю, используем для триангуляризации матрицы A(m, n). На первом шаге нужны преобразования, делающие равными нулю все элементы ниже первого диагонального элемента. Для этого, очевидно, нужно выполнить последовательно элементарные вращения P_{1,2}, P_{1,3}, ⋯, P_{1,m}. Так определенные преобразования воздействуют на все столбцы матрицы, но только первый столбец, который уместно назвать ведущим столбцом, приобретает желаемый вид.

Лемма A.2. Пусть дана матрица A(m, n) и y — ее ведущий (левый) столбец. Тогда существует ортогональное преобразование Гивенса, задаваемое матрицей P_{1} = P_{1}(m, m), такое, что

P_{1}A = \begin{matrix}^{1} & ^{n−1} \\ 1\{ & [ r | ; 0 | Ã ; | ] , \\ m−1 & \{ \end{matrix}  (A.34)

P_{1} = P_{1,m} ⋯ P_{1,3}P_{1,2} , P_{1,i} (i = 2, 3, …, m)_{1}  _{i}  _{m}_{c_{1,i}}  _{s_{1,i}}_{−s_{1,i}}  _{c_{1,i}}_{...} _{...}_{1}  _{1} _{...} _{1}_{1}_{i}_{m}  0  0  _{←} _{r_{1,1} := y_{1} ; Для i = 2, 3, …, m ; r_{1,i} := \sqrt{r_{1,i−1}^{2} + y_{i}^{2}} ; c_{1,i} := \frac{r_{1,i−1}}{r_{1,i}} ; s_{1,i} := \frac{y_{i}}{r_{1,i}} ; r ≜ r_{1,m} = ∑_{i=1}^{m} y_{i}^{2} = ∥y∥^{2}} _{←} _{y}_{y_{1}}_{y_{i}}_{y_{m}}

Теорема A.2 (Триангуляризация матрицы по методу Гивенса). Пусть A_{1} := A(m, n) и для каждого j = 1.2…. , k, k ≤ min (m − 1, n) серия элементарных преобразований Гивенса, задаваемая матрицей P_{j} размера (m + 1 − j) × (m + 1 − j), выбрана для ведущего (левого) столбца y_{j} матрицы A_{j} так, что

P_{j}A_{j} = \begin{matrix}^{1} & ^{n−j} \\ 1\{ & [ r_{j} | a_{j}^{T} ; 0 | A_{j+1} ; | ] , \\ m−j & \{ \end{matrix} j = 1, …, k; k ≤ min (m−1, n). (A.35)

Тогда в процессе после k повторных применений леммы A.2 имеем следующий промежуточный результат триангуляризации матрицы A:

r_{1}  a_{1}^{T} r_{2}  a_{2}^{T}_{...}  ⋮ r_{k} a_{k}^{T} A_{k+1} 0 P^{(k)}A =  (A.36)

с отвечающей этому моменту процесса итоговой матрицей преобразований

P^{(k)} = [ \begin{matrix}I_{k−1} & 0 \\ 0 & P_{k} \end{matrix} ] ⋯ [ \begin{matrix}I_{1} & 0 \\ 0 & P_{2} \end{matrix} ] P_{1} , P_{j} = P_{j,m−j+1} ⋯ P_{j,3}P_{j,2} , (A.37)
P_{j,t} (t = 2, 3, …, l), l ≜ m − j + 1, j = 1, 2, …, k, i = j + t − 1._{1}  _{t}  _{l}_{c_{j,i}}  _{s_{j,i}}_{−s_{j,i}}  _{c_{j,i}}_{...} _{...}_{1}  _{1} _{...} _{1}_{1}_{t}_{l}  0  0  _{←} _{r_{j,1} := y_{1,j} ; Для t = 2, …, l ; r_{j,t} := \sqrt{r_{j,t−1}^{2} + y_{t,j}^{2}} ; c_{j,j+t−1} := \frac{r_{j,t−1}}{r_{j,t}} ; s_{j,j+t−1} := \frac{y_{t,j}}{r_{j,t}} ; r_{j} ≜ r_{j,l} = ∑_{t=1}^{l} y_{t,j}^{2} = ∥y_{j}∥^{2}} _{←} _{{y_{j} \atop ⇓}}_{y_{1,j}}_{y_{t,j}}_{y_{l,j}}

Формула (A.37) имеет рекуррентный вид произведения

\begin{matrix}P^{(j)} & = [ \begin{matrix}I_{j−1} & 0 \\ 0 & P_{j} \end{matrix} ] P^{(j−1)} , P^{(1)} = P_{1} \\ P_{j} & = P_{j,m−j+1} ⋯ P_{j,3}P_{j,2} , j = 2, …, N \end{matrix}\} , N = min (m − 1, n). (A.38)

Все участвующие здесь матрицы являются ортогональными, поэтому финальная матрица P ≜ P^{(N)} также ортогональна. Общее число используемых при этом элементарных матриц вращения равно (m − 1) + (m − 2) + … + + (m − N) = (2m − N − 1)N/2. В результате (в случае m > n) получим

P A = [ \begin{matrix}R \\ ⋯ \\ 0 \end{matrix} ] , R = 0  ≜ R_{ne},  (A.39)

где индекс _{ne} подчеркивает, что в треугольной матрице R заполненной частью может быть только �северо-восточная� (north-by-east) часть. Полагая Q = P^{T}, при m = n имеем QR-разложение матрицы A = A(n, n), т. е.A = QR. Матрицы в (A.37) и (A.38) непосредственно не вычисляются.

Для алгоритма Гивенса — так же, как и для других матричных алгоритмов, — имеются две схемы вычислений: (1) строчно ориентированная схема и (2) столбцово ориентированная схема (рис. A.8). Как и в алгоритме преобразований Хаусхолдера (см. рис. A.5), здесь обычно требуется сохранять информацию о произведенных по ходу алгоритма (A.38) элементарных преобразованиях, чтобы впоследствии иметь возможность решать системы уравнений Ax = z (совместные или несовместные, в последнем случае — по методу наименьших кdадратов, см. подразд. A.3) или же находить обратную матрицу A^{−1} (когда m = n).

Необходимая информация означает значения косинуса и синуса, однако их сохранение было бы неэффективным решением. Gentleman (1973) предложил эффективный способ, включенный в рис. A.8(б) и (г) с геометрической иллюстрацией его действия на рис. A.8(е). Введенный им рабочий признак ζ — это одно число, которое можно хранить в позиции (i, j) как ζ_{j,i} вместо нулевого элемента, появляющегося в позиции (i, j) матрицы (A.39) в момент преобразования P_{j,t} (t = i + 1 − j) в (A.37). Как и с преобразованиями Хаусхолдера, нахождение A^{−1} после преобразований Гивенса требует такой же последовательности процедур: сначала находят R^{−1} (см. A.6), затем к R^{−1} применяют с правой стороны финальное преобразование P ≜ P^{(N)} (A.38), так как A^{−1} = R^{−1}P. Для этого на рис. A.6 надо взять алгоритм из рис. A.8(д), который также отыскивает P z при решении уравнения Ax = z.

r_{j}

ζ_{j,i} a_{is}

a_{js}

r_{j}

ζ_{j,i} a_{is}

a_{js}

y_{jj}

y_{ij}

{j \atop ⇓} s ⇓

j ⇒

i ⇒

m

{j \atop ⇓} s ⇓

m i ⇒ j ⇒

y_{ij}

y_{jj}

(а)

Для j = 1 до min(m−1, n)

r_{j} := a_{jj}

Для i = j + 1 до m

a := r_{j}; b := a_{ij}

получить (r, c, s, ζ)

из (a, b)

(a_{jj} ≜ r_{j}) := r

(a_{ij} ≜ ζ_{j,i}) := ζ

c_{j,i} := c; s_{j,i} := s

Для s = j + 1 до n

Для i = j + 1 до m

α = c_{j,i}a_{js} + s_{j,i}a_{is}

a_{is} = −s_{j,i}a_{js} +c_{j,i}a_{is}

a_{js} := α

(б)

........Процедура........ получить (r, c, s, ζ) из (a, b)

σ = \{ \begin{matrix}sgn [a], & |a| > |b| \\ sgn [b], & |a| ≤ |b| \end{matrix}

r = σ(a^{2} + b^{2})^{1/2}

c = \{ \begin{matrix}a/r, & r ≠ 0 \\ 1, & r = 0 \end{matrix}

s = \{ \begin{matrix}b/r, & r ≠ 0 \\ 0, & r = 0 \end{matrix}

ζ = \{ \begin{matrix}s, & |a| > |b| \\ 1/c, & \begin{cases}|a| ≤ |b| & \\ & c ≠ 0 \end{cases} \\ 1, & c = 0 \end{matrix}

(в)

Для j = 1 до min(m−1, n)

Для i = j + 1 до m

a := a_{jj}; b := a_{ij}

получить (r, c, s, ζ)

из (a, b)

(a_{jj} ≜ r_{j}) := r

(a_{ij} ≜ ζ_{j,i}) := ζ

Для s = j + 1 до n

α = ca_{js} + sa_{is}

a_{is} = −sa_{js} + ca_{is}

a_{js} := α

(г)

........Процедура........ получить (c, s) из (ζ)

ζ = 1 ⇒ \{ \begin{matrix}c := 0 \\ s := 1 \end{matrix}

d := (1 − ζ^{2})^{1/2}

ζ < 1 ⇒ \{ \begin{matrix}c := d \\ s := ζ \end{matrix}

ζ > 1 ⇒ \{ \begin{matrix}c := ζ \\ s := d \end{matrix}

(д)

Для j = 1 до min(m−1, n)

Для i = j + 1 до m

получить (c, s) из ζ_{j,i}

α = cy_{jj} + sy_{ij}

y_{ij} = −sy_{jj} + cy_{ij}

y_{jj} := α

P^{(j)}A y_{j}

(е)

1 2

3

4

5

6 7 8

|r| −|r|

Рис. A.8. Преобразование Гивенса: (a) столбцово ориентированная схема вычисления матрицы P A, где P = P^{(j)} при j = min (m − 1, n) (нижняя матрица слева); (б) вычисление координаты r вектора (a, b)^{T}, повернутого до совмещения с первой осью, а также косинуса и синуса угла поворота и рабочего признака ζ; (в) строчно ориентированная схема вычисления матрицы P A (верхняя матрица слева); (г) восстановление косинуса и синуса угла поворота из признака ζ; (д) получение вектора y теми преобразованиями P_{j,i} произвольного вектора z ∈ ℝ^{m}, которые сохранены в рабочих признаках ζ_{j,i} и восстанавливаются из них; (е) вследствие (б), векторы 1, 2, 3 и 4 поворачиваются к положительному направлению первой координатной оси, а векторы 5, 6, 7 и 8 поворачиваются к отрицательному направлению этой оси.

A.8 Варианты заполнения матрицы R

Традиционно, любые ортогональные преобразования (выше рассмотрены T — преобразование Хаусхолдера и P — преобразование Гивенса, ниже будет рассмотрено Q — преобразование Грама-Шмидта) приводят матрицу к виду, показанному на рис. A.4 или в выражении (A.39). Однако выбор того угла матрицы, который должен остаться треугольно заполненым, естественно, произволен. Предпочтения диктуются целями использования, т.е.предназначением преобразования. Преследуя здесь учебнотренировочные цели, включим в проект (см. подразд. ??) все четыре возможных варианта заполнения матрицы R, а именно: первый вариант показан в (A.39), следующие три имеют вид

P A = [ \begin{matrix}R \\ ⋯ \\ 0 \end{matrix} ] , R =  0 ≜ R_{nw},  (A.40)

где индекс _{nw} подчеркивает, что в треугольной матрице R заполненной частью может быть только �северо-западная� (north-by-west) часть,

P A = [ \begin{matrix}0 \\ ⋯ \\ R \end{matrix} ] , R = 0  ≜ R_{se},  (A.41)

где индекс _{se} подчеркивает, что в треугольной матрице R заполненной частью может быть только �юго-восточная� (south-by-east) часть, и

P A = [ \begin{matrix}0 \\ ⋯ \\ R \end{matrix} ] , R =  0 ≜ R_{sw},  (A.42)

где индекс _{sw} подчеркивает, что в треугольной матрице R заполненной частью может быть только �юго-западная� (south-by-west) часть. Вполне очевидно, что эти вариенты получаются простым изменение порядка действий в алгоритмах преобразований.

A.9 Правосторонние ортогональные преобразования и их применение

С правосторонними ортогональными преобразованиями мы уже сталкивались (см. подразд. A.6); тогда для квадратной матрицы A после T A = R вычисляли A^{−1} = R^{−1}T. Однако, можно начинать с правостороннего преобразования матрицы A; тогда отыскание A^{−1} потребует, соответственно, левостороннего преобразования.

Пусть A = A(n, n) — квадратная невырожденная матрица. Будем рассматривать ее строки как векторы в ℝ^{n}. Преобразования вектора как матрицы-строки в n-мерном линейном пространстве задаются умножением ее на преобразующую матрицу справа. Поэтому правосторонним ортогональным преобразованием Q можно привести матрицу A к виду AQ = R, где применена ортогональная матрица Q одного из типов, а R — треугольная матрица, имеющая форму одного из возможных вариантов заполнения (см. подразд. A.9). При этом преобразованию Q подвергаются не столбцы, а строки матрицы A, и преобразование Q запоминается по принципу, показанному ранее на рис. A.5 и рис. A.8, на месте элементов, обращаемых в нуль.

После такого преобразования матрицы A решение системы Ax = z сводится к решению эквивалентной системы с треугольной матрицей Ry = z. Затем искомый вектор определяется через сохраненное преобразование Q как x = Qy. Обратная матрица A^{−1}, соответственно, находится как решение системы RY = I с последующим преобразованием Q матрицы Y, т. е.X = A^{−1} = QY. Матрица Q не формируется, из чего видна необходимость запоминания преобразований, обеспечивших AQ = R.

A.10 Двусторонние ортогональные преобразования и их применение

Ортогональные преобразования, будучи применены одновременно слева и справа к данной матрице A, позволяют приводить ее к формам с нулями как ниже, так и выше диагонали. Это, в свою очередь, облегчает решение других сложных задач. С помощью ортогональных преобразований для квадратной матрицы широко распространены: приведение симметрической матрицы к трехдиагональному виду и приведение квадратной матрицы к двухдиагональному виду. При этом в качестве ортогональных преобразований одинаково успешно могут быть использованы преобразования Хаусхолдера или преобразования Гивенса.

Приведение симметрической матрицы к трехдиагональному виду. Применим к симметрической матрице слева и справа преобразование Хаусхолдера (или Гивенса), выбирая его из задачи желаемого преобразования ведущего столбца и ведущей строки, а именно: сохранение первого диагонального элемента, получение ненулевых элементов в двух смежных с ним позициях и получение нулевых элементов в остальных позициях.

Лемма A.3. Пусть дана матрица A = A(n, n) = A^{T}. Тогда существует ортогональное преобразование Q_{2} (Хаусхолдера T_{2} или Гивенса P_{2}) такое, что

[ \begin{matrix}I_{1} & 0 \\ 0 & Q_{2} \end{matrix} ] A [ \begin{matrix}I_{1} & 0 \\ 0 & Q_{2}^{T} \end{matrix} ] = \begin{matrix}^{1} & ^{1} & ^{n−2} \\ 1\{ & [ \begin{matrix}a_{1} & s_{1} & 0 \\ s_{1} \\ 0 & & Ã \end{matrix} ] . \\ 1\{ \\ n−2 & \{ \end{matrix}  (A.43)

Замечание A.6. В (A.43) транспонирование Q_{2}^{T} не требуется, если в качестве Q_{2} взято преобразование Хаусхолдера (в силу его симметричности). При этом индекс �_{2}� указывает на позицию того элемента в ведущем столбце (для левостороннего преобразования) или в ведущей строке (для правостороннего преобразования), который остается ненулевым в этом столбце (в результате применения Q_{2}) или в этой строке (в результате применения Q_{2}^{T}). В данном случае, т.е.в (A.43), эти элементы суть s_{1} и s_{1}. Элемент a_{1} не изменяется, так как I_{1} — единичная матрица размера 1 × 1.

Теорема A.3 (Тридиагонализация симметрической матрицы). Пусть дана симметрическая матрица A = A(n, n) = A^{T}, A_{1} := A(n, n) и для каждого j = 1, …, k, где k ≤ N = n − 2, выбрано элементарное преобразование Q_{j+1} (Хаусхолдера T_{j+1} или Гивенса P_{j+1}) так, что

[ \begin{matrix}I_{1} & 0 \\ 0 & Q_{j+1} \end{matrix} ] A_{j} [ \begin{matrix}I_{1} & 0 \\ 0 & Q_{j+1}^{T} \end{matrix} ] = \begin{matrix}^{1} & ^{1} & ^{n−j−1} \\ 1\{ & [ a_{j} | s_{j} 0 ; s_{j} | ; 0 |  A_{j+1} ; | ] . \\ 1\{ \\ n−j−1 & \{ \end{matrix} (A.44)

Тогда в процессе после k повторных применений леммы A.3 имеем отвечающую этому моменту процесса итоговую матрицу преобразований

Q^{(k)} = [ \begin{matrix}I_{k} & 0 \\ 0 & Q_{k+1} \end{matrix} ] Q^{(k−1)}, 1 ≤ k ≤ N = n − 2, Q^{(0)} = I_{n} (A.45)

и промежуточный результат тридиагонализации данной матрицы A в виде

a_{1} _{s_{1}}_{s_{1}} _{a_{2}} _{s_{2}}_{s_{2}}  _{s_{k}} _{s_{k}}_{a_{k}}_{...}  _{A_{k+1}} 0  0_{Q^{(k)}A (Q^{(k)})^{T} =}  _{...} _{...}  ^{.}

Приведение квадратной матрицы к двухдиагональному виду. Применим к произвольной квадратной матрице слева преобразование Q_{1} и справа преобразование S_{2} (беря любое из них как преобразование Хаусхолдера или как преобразование Гивенса), при этом Q_{1} выберем из задачи желаемого преобразования ведущего столбца и S_{2} — из задачи желаемого преобразования ведущей строки, а именно: при действии Q_{1} — получение ненулевого диагонального элемента и нулевых элементов ниже него в первом (ведущем) столбце; при действии S_{2} — сохранение диагонального элемента, получение в смежной с ним позиции ненулевого элемента и нулевых элементов правее него в первой (ведущей) строке.

Лемма A.4. Пусть дана матрица A = A(n, n). Тогда существуют ортогональное преобразование Q_{1} (Хаусхолдера или Гивенса) и ортогональное преобразование S_{2} (Хаусхолдера или Гивенса) такие, что

Q^{(1)}AS^{(1)} = \begin{matrix}^{1} & ^{1} & ^{n−2} \\ 1\{ & [ \begin{matrix}s_{1} & a_{1} & & 0 \\ 0 & & Ã \end{matrix} ] , \\ n−2 & \{ \end{matrix}  \{ \begin{matrix}Q^{(1)} & = Q_{1}, \\ S^{(1)} & = [ \begin{matrix}I_{1} & 0 \\ 0 & S_{2} \end{matrix} ] . \end{matrix}  (A.46)

Теорема A.4 (Бидиагонализация квадратной матрицы). Пусть дана квадратная матрица A = A(n, n), A_{1} := A и для каждого j = 1, …, k, где k ≤ n − 2, выбраны элементарное преобразование Q_{j} (Хаусхолдера типа T_{j} или Гивенса типа P_{j}) и элементарное преобразование S_{j+1} (Хаусхолдера типа T_{j+1} или Гивенса типа P_{j+1}) таким образом, что в результате получаем

Q_{j}A_{j} [ \begin{matrix}I_{1} & 0 \\ 0 & S_{j+1} \end{matrix} ] = \begin{matrix}^{1} & ^{1} & ^{n−j−1} \\ 1\{ & [ \begin{matrix}s_{j} & a_{j} & 0 \\ 0 & & A_{j+1} \end{matrix}  ] . \\ n−j & \{ \end{matrix}  (A.47)

Тогда в процессе после k повторных применений леммы A.4 имеем отвечающие этому моменту процесса итоговые матрицы преобразований

\begin{matrix}Q^{(k)} & = [ \begin{matrix}I_{k−1} & 0 \\ 0 & Q_{k} \end{matrix} ] Q^{(k−1)}, k ≤ n − 2, Q^{(0)} = I_{n}, Q^{(1)} = Q_{1}, \\ S^{(k)} & = S^{(k−1)} [ \begin{matrix}I_{k} & 0 \\ 0 & S_{k+1} \end{matrix} ] , k ≤ n − 2, S^{(1)} = [ \begin{matrix}I_{1} & 0 \\ 0 & S_{2} \end{matrix} ] \end{matrix}\}

(A.48)

и промежуточный результат бидиагонализации данной матрицы A в виде

s_{1} _{a_{1}}_{s_{2}} _{a_{2}}_{...} _{...}_{s_{k}} _{a_{k}}_{A_{k+1}} 0  0_{Q^{(k)}AS^{(k)} =}  ^{.}

Выполнив после k = n−2 еще одно левостороннее преобразование Q_{n−1} (что отвечает применению верхней формулы (A.48) для k = n − 1), получаем окончательно

s_{1} a_{1} a_{2} s_{2}  s_{n−1} s_{n} a_{n−1}_{...} _{...}0 0 Q^{(n−1)}AS^{(n−2)} =  .

Приложение B

Название приложения B

B.1 Название подраздела B.1 в приложении B

Как показано в приложении B, подразд. B.2, пункт B.2.1 ...

B.1.1 Название пункта B.1.1 в приложении B, подразд. B.1

Название подпункта пункта B.1.1 в приложении B, подразд. B.1

B.1.2 Название

Название

B.2 Название подраздела в приложении 2

B.2.1 Название

Название

B.2.2 Название

Название

Дипломный проект

Фамилия Имя Отчество

Название дипломной работы

Дипломная работа выполнена мною самостоятельно. Использованные в работе материалы из опубликованной научной, учебной литературы и Интернет имеют ссылки на них.

Отпечатано в экземплярах. Библиография наименований. Один экземпляр сдан на кафедру.

Дата  подпись