авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:     | 1 |   ...   | 2 | 3 || 5 | 6 |   ...   | 8 |

«министерство образования и науки российской федерации федеральное государственное бюджетное образовательное учреждение высшего профессионального образования ульяновский ...»

-- [ Страница 4 ] --

Теорема 8.5 ( [12]). Пусть A и B симметрические положительно определенные матрицы и min (B 1A), max(B 1A) наименьшее и наиболь шее собственные значения в задаче Ax = Bx. Для погрешности метода минимальных поправок справедлива оценка A(xn x) n A(x0 x), n = 0, 1,..., B 1 B где min (B 1A) 0 =, =.

max (B 1A) 1+ Метод скорейшего спуска Возьмем явный метод (8.13) и выберем итерационный параметр k+1 из условия минимума zk+1 A при заданном векторе zk, где zk+1 = xk+1 x.

Поскольку погрешность zk удовлетворяет уравнению zk+1 = zk k+1Azk, имеем 2 2k+1(Azk, Azk ) + k+1(A2zk, Azk ).

zk+1 = zk A A 8.10 Итерационные методы вариационного типа (Azk, Azk ) Минимум нормы zk+1 достигается при k+1 =.

A (A2zk, Azk ) Величина zk = xk x неизвестна, но Azk = rk = Axk f. Поэтому вычисление k+1 проводят по формуле (rk, rk ) k+1 =.

(Ark, rk ) Теорема 8.6 ( [12]). Для погрешности явного метода скорейшего спуска справедлива оценка xn x n x0 x, n = 0, 1,..., A A где 1 min (A) 0 =, =.

1+ max (A) Если вместо (8.13) взять неявный метод (8.26) и параметр k+1 выбирать из условия минимума zk+1 A, то получим неявный метод наискорейшего спуска. Для него 2k+1(Azk, B 1Azk ) + k+1(AB 1Azk, B 1Azk ), 2 2 zk+1 = zk A A или 2 2 2k+1(rk, k ) + k+1(Ak, k ).

zk+1 = zk A A Следовательно, норма zk+1 будет минимальной при A (rk, k ) k+1 =.

(Ak, k ) Теорема 8.7 ( [12]). Для неявного метода скорейшего спуска спра ведлива оценка xn x n x0 x, n = 0, 1,..., A A где min (B 1A) 0 =, =.

max (B 1A) 1+ 8 Итерационные методы Метод сопряженных градиентов Этот метод исходит из задачи минимизации функции J(x) = (Ax, x) (b, x), (8.34) решение которой совпадает с решением системы A = AT 0.

Ax = f, (8.35) Полный вывод метода сопряженных градиентов можно найти в [12]. Опус кая детали, приведем окончательный результат.

Метод сопряженных градиентов для решения системы Ax = f состоит в вычислениях по следующим формулам:

rk = b Axk, k = 0, 1,..., k+1 k k 1 0 p = r + k+1 p, k = 1, 2,..., p = r, k+1 k k+1 (8.36) x = x + k+1 p, k = 0, 1,..., x = 0, k+1 = (rk, pk+1)/(pk+1, Apk+1), k = 0, 1,..., kk kk k+1 = (Ap, r )/(Ap, p ), k = 1, 2,....

Теорема 8.8 ( [12]). Для метода сопряженных градиентов (8.36) спра ведливо k xk x 2 (1 min /max )/(1 + min /max) x, A A где min и max минимальное и максимальное собственные значения мат рицы A.

Следуя [12], преобразуем соотношения (8.36). В этих соотношениях наибо лее трудоемкими являются две операции: вычисление векторов Axk и Apk.

Однако операцию вычисления вектора Axk можно исключить. Поскольку этот вектор нужен только для вычислении невязки rk, то можно заменить первую из формул (8.36) на rk = rk1 k Apk, r0 = b.

k = 1, 2,..., (8.37) Преобразуем формулы для вычисления параметров k+1 и k+1. Подставляя второе из соотношений (8.36) в четвертое, найдем k+1 = (rk, rk )/(pk+1, pk+1), k = 0, 1,.... (8.38) 8.11 Другие методы Заменяя здесь k + 1 на k и подставляя полученное выражение для (pk, Apk ) в последнее из соотношений (8.36), получим (Apk, rk ) = k k1 k1.

k+ (r, r ) Теперь подставим сюда вместо Apk его выражение из (8.37).

Теорема 8.9 ( [12]). После k шагов метода сопряженных градиентов невязки r0, r1,..., rk взаимно ортогональны.

Принимая это во внимание, найдем (rk, rk ) k+1 =, k = 1, 2,.... (8.39) (rk1, rk1) С учетом (8.37)–(8.39) формулы метода сопряженных градиентов (8.36) преобразуются к виду rk = rk1 k Apk, k = 1, 2,..., r0 = b, k+1 k k 1 0 p = r + k+1p k = 1, 2,..., p = r, k+1 k k+1 (8.40) x = x + k+1 p, k = 0, 1,..., x = 0, k+1 = rk 2 /(pk+1, Apk+1), k = 0, 1,..., k2 k1 k+1 = r / r, k = 1, 2,....

Легко проверить, что эти вычисления проводят в следующем порядке:

r0 = b, p1 = r0, Ap1, 1, x1, r1, 2, p2, Ap2, 2, x2,...

8.11 Другие методы Область итерационных методов решения систем линейных алгебраиче ских уравнений обширна. Она включает гораздо большее количество мето дов, чем то, что приведено выше.

В итерационных методах нашли применение полиномы Чебышёва, бла годаря которым можно решать задачу оптимального выбора итерационных параметров как для явных ИМ, так и для неявных ИМ [12].

Стационарные методы, широко применявшиеся в 1950–1980 годах, сейчас чаще применяются [126] как средство сглаживания в многосеточных алго ритмах [102, 118, 144] или для предобусловливания в алгоритмах Крылова [139].

8 Итерационные методы Идея сопряженных градиентов [136] оказалась очень плодотворной, и наи более широкое воплощение она нашла при опоре на метод подпространств Крылова, который является одним из методов решения проблемы собствен ных значений и собственных векторов для очень больших разреженных матриц [143]. Переход к методу подпространств Крылова в этой проблеме вызван тем, что преобразования подобия, лежащие в основе ее решения для небольших матриц, выполнять для очень больших матриц практиче ски невозможно. В то же время достаточно легко выполнять однотипные операции умножения матрицы на вектор: взять вектор x и затем, умножая слева на A, построить последовательность Крылова x, Ax, A2x, A3x,... и, соответственно, получить пространства Крылова Kj (A, x) = span x, Ax, A2x, A3x,..., Aj1x.

В настоящее время алгоритмы Крылова с предобусловливанием применя ются в большинстве итерационных методов решения больших разреженных линейных систем [126]. Успешной альтернативой методам Крылова явля ются многосеточные методы, по которым за последние 30–40 лет появилось огромное число публикаций [102, 118, 126, 144].

Вместе с этими мощными ветвями роста, в практике решения линей ных систем итерационными методами встречаются решения, которые могут быть классифицированы как Inventive Math. Это решения, по которым пока не найдено строгих доказательств, но которые подтверждают свою рабо тоспособность методом широкого вычислительного эксперимента. Приме ром такого подхода является метод делинеаризации для линейных систем [140, 141, 142].

8.12 Задание на лабораторный проект № Написать и отладить программу, реализующую ваш вариант задания в со ответствии с табл. 8.1 (см. ниже стр. 159), включающий два итерационных метода для численного решения систем линейных алгебраических уравне ний Ax = f с квадратной матрицей A и отыскания обратной матрицы A1.

Предусмотреть сообщение о невозможности решения указанных задач из-за превышения допустимого числа итераций. Отделить основные части про граммы:

а) подпрограмму решения систем линейных алгебраических уравнений;

б) подпрограмму обращения матриц;

8.12 Задание на лабораторный проект № в) сервисные подпрограммы.

Уделить особое внимание эффективности программы (в смысле экономии оперативной памяти и скорости решения указанных выше задач). Преду смотреть пошаговое выполнение алгоритма с выводом xk на каждой итера ции (для тестовой задачи небольшой размерности, см. ниже п. 4).

В качестве (см. критерий остановки в подразд. 8.2) для обоих итераци онных методов использовать погрешность решения данной системы линей ных алгебраических уравнений (СЛАУ) методом исключения переменных из лабораторной работы № 1.

Выполнить следующие пункты задания:

1. Провести подсчет фактического количества операций умножения и деления, выполняемых при решении системы линейных алгебраических уравнений c выводом результата на экран. Сравнить с методом исключе ния переменных из лабораторной работы № 1. Вывести таблицу и график.

2. Оценить скорость решения задач, т. е. определить время, затрачен ное на решение СЛАУ, и время, затраченное на обращение матриц. Для этого спроектировать и провести эксперимент, который охватывает матрицы порядка от 10 до 200 (через 10 порядков). Представить результаты в виде таблицы и графика зависимости времени выполнения от порядка матриц для трех алгоритмов (двух итерационных методов, соответствующих варианту, и методу исключения переменных из лабораторной работы № 1). Таблицу и графики вывести на экран.

3. Оценить точность решения систем линейных алгебраических урав нений, указанных в п. 2. Для этого сгенерировать случайные матрицы A, задать точное решение x и образовать правые части f = Ax. Провести анализ точности вычисленного решения x от порядка матрицы для трех алгоритмов (аналогично п. 2). В качестве точного решения взять вектор x = (1, 2,..., m)T, где m порядок матрицы. Для оценки точности ре шения использовать норму вектора x = max | xi |.

i Результаты по п. 3 представить в виде таблицы и графиков.

Замечание 8.2. Для проведения вычислительного эксперимента по пп. 2 и 3 применять симметрические положительно определенные матрицы A с диагональным преобладанием. Для заполнения матрицы A использовать случайные числа из диапазона от 100 до 100. Сначала заполнить ниж нюю треугольную часть матрицы A, т. е. элементы aij, где i j. Верхнюю 8 Итерационные методы трегольную часть, где i j, заполнить симметрично нижней части. Затем заполнить диагональ. В качестве диагонального элемента aii, i = 1, 2,..., m, выбрать случайное число из интервала |aij | + 101, |aij | + 1, j=i j=i чтобы обеспечить выполнение условия aii |aij | + 1, j=i гарантирующего положительную определенность матрицы A.

4. До проведения вычислительного эксперимента по пп. 2 и 3 выполнить отладку программы. Для отладки программы, а также для сравнительного тестирования двух заданных итерационных методов использовать следую щую тестовую задачу [99]:

41/209 = 0. 4 0 1 1 0 1 2 53/209 = 0. 4 A=, f =, x = 167/209 = 0.799043.

1 0 0 1 1 0 4 4 206/209 = 0. 5. Для тех вариантов задания, в которых присутствует метод Юнга (верх ней релаксации), провести специальный вычислительный эксперимент реше ния тестовой задачи по п. 4. Цель этого эксперимента исследование ско рости сходимости метода в зависимости от коэффициента релаксации в формуле (8.14).

Изменение параметра организовать с шагом = 0.05 равномерно в интервале теоретической сходимости метода: 0 2, т. е. по алгоритму:

0 := start Для i = 0, 1,..., 20 выполнять i+1 := i + Стартовое значение задавать с клавиатуры, например, start = 0.50.

6. Повторить п. 3 задания для плохо обусловленных матриц (см. под разд. 2.6 лабораторной работы № 1), имеющих порядок от 4 до 40.

8.13 Варианты задания на лабораторный проект № Таблица 8.1. Варианты задания на лабораторный проект № Варианты итерационных a b c d e f g методов - 13 14 1 2 3 a - - 15 5 6 7 b - - - 9 10 11 c метод Якоби;

a метод Зейделя;

b метод Юнга;

c метод минимальных невязок;

d метод минимальных поправок;

e метод скорейшего спуска;

f метод сопряженных градиентов.

g 7. Вычислить матрицу A1 двумя способами:

1) через решение системы AX = I на основе метода исключения Гаусса из лабораторной работы № 1 (в соответствии со своим вариантом);

2) через решение системы AX = I на основе любого из двух заданных итерационных методов.

Сравнить затраты машинного времени и точность обращения способами 1) и 2). Эксперименты провести для матриц порядков от 10 до 100 через 10, сгенерированных согласно замечанию 8.2. Для оценки точности в обоих способах воспользоваться формулой из лабораторной работы (проекта) № 1.

8.13 Варианты задания на лабораторный проект № По теме Итерационные методы студентам предлагается 15 вариантов лабораторной работы № 7, сведенных в табл. 8.1.

Если нет других указаний преподавателя, выбирайте ваш вариант из табл. 8.1 по вашему номеру в журнале студенческой группы.

Фонд задач Целью настоящего раздела является формирование и проверка у сту дентов, изучающих курс Численные методы, базовых навыков в области решения задач вычислительной линейной алгебры. Предлагаемые в этом разделе задачи охватывают широкий спектр методов: гауссово исключение переменных, итерационные методы решения систем линейных алгебраиче ских уравнений, включая методы вариационного типа, факторизацию поло жительно определенных матриц и ортогональные преобразования. Приво димые ниже задачи могут быть использованы как для практических заня тий и контрольных работ в аудитории, так и для самостоятельной работы студента, а также для проверки практических навыков студентов во время экзамена. Данный материал позволяет не только проверить знание базовых алгоритмов в области вычислительной линейной алгебры, но и определить уровень владения вычислительной техникой для решения тех или иных при кладных задач. Большое разнообразие и количество задач создает возмож ность формирования индивидуального задания для каждого студента.

9.1 Типовые задачи Начнем прежде всего, с разбора типовых задач. В соответствии с вы шесказанным настоящее учебное пособие содержит задачи по следующим пяти темам: метод исключения Гаусса, итерационные методы, итерацион ные методы вариационного типа, разложение Холесского для симметричных положительно определенных матриц и методы ортогонального приведения.

Задача 1 (см. ниже) является типичным представителем задач на метод Гаусса исключения переменных. Целью задачи является проверка знания базовых алгоритмов для разложения невырожденной матрицы в произведе ние нижней и верхней треугольных матриц, а также для решения системы 9.1 Типовые задачи линейных уравнений с разложенной матрицей коэффициентов и обраще ния матрицы. Разнообразие задач достигается за счет вовлечения различ ных вариантов разложения (см. лабораторную работу № 1, подразд. 2.8) и использования разных исходных матриц.

Задача Для матрицы A= 6 2 2 2 выполнить следующее:

а. Построить LU -разложение матрицы A (L с единицами на главной диа гонали).

б. С помощью LU -разложения матрицы A решить систему линейных уравнений Ax = b, где вектор b = (0, 3, 1)T.

в. С помощью LU -разложения найти матрицу A1 и вычислить число MA обусловленности матрицы A в норме · = max {|xi|}, x R3.

i=1,2, Задача 2 является типичным представителем задач на итерационные ме тоды решения систем линейных алгебраических уравнений. Целью задачи является проверка знания базовых итерационных алгоритмов, а также необ ходимых и достаточных условий их сходимости и критериев для оценки точности решения. Разнообразие задач достигается за счет вовлечения раз личных итерационных методов, изучаемых в курсе Численные методы, и использования разных исходных матриц.

Задача Для системы линейных алгебраических уравнений вида Ax = b, где матрица 5 1 A = 1 4 01 и вектор b = (4, 2, 1)T, выполнить следующее:

9 Фонд задач а. Сформулировать метод Зейделя в координатном и каноническом виде.

б. Определить является ли он сходящимся с нулевым начальным прибли жением, т. е. x0 = (0, 0, 0)T ? Ответ обосновать.

в. Вычислить две итерации по методу Зейделя и найти апостериорную оценку ошибки на каждой из них в норме · = max {|xi|}, x R3.

i=1,2, Следующая задача посвящена итерационным методам вариационного типа. Ее целью является проверка знания алгоритмов построения итера ционных методов вариационного типа, формул для вычисления оптималь ного итерационного параметра и критериев для оценки точности решения.

Разнообразие задач достигается за счет вовлечения различных способов по строения итерационных методов вариационного типа, изучаемых в курсе Численные методы, и использования разных исходных матриц.

Задача Для системы линейных алгебраических уравнений вида Ax = b, где матрица 5 1 A = 1 4 01 и вектор b = (4, 2, 1)T, выполнить следующее:

а. На основе метода Зейделя сформулировать неявный метод скорейшего спуска в каноническом виде.

б. Определить оптимальный параметр 1 для нулевого начального при ближения, т. е. x0 = (0, 0, 0)T ?

в. Вычислить одну итерацию и найти апостериорную оценку ошибки в норме · = max {|xi |}, x R3.

i=1,2, Задача 4 является типичным представителем задач на разложение Хо лесского для симметричных положительно определенных матриц. Целью 9.1 Типовые задачи задачи является проверка знания базовых алгоритмов Холесского для раз ложения симметричной положительно определенной матрицы, а также спо собов решения системы линейных уравнений с разложенной матрицей коэф фициентов и обращения матрицы. Разнообразие задач достигается за счет вовлечения различных вариантов разложения Холесского (см. лаборатор ную работу № 5, подразд. 6.8) и использования разных исходных матриц.

Задача Для матрицы 18 10 3 10 105 8 P = 3 8 1 10 25 0 выполнить следующее:

а. Построить U DU T -разложение матрицы P (U верхняя треугольная матрица с единицами на главной диагонали, D диагональная мат рица с положительными элементами на диагонали).

б. С помощью U DU T -разложения матрицы P решить систему P x = b, c вектором b = (21, 112, 4, 60)T.

в. С помощью разложения и решения системы найти величину квадра тичной формы J(x) = xT P x, где x решение из п.б.

Последняя задача этого раздела посвящена соответственно последней теме, а именно, методам ортогонального разложения матриц. Целью на стоящей задачи является проверка базовых знаний по алгоритмам ортого нального разложения матрицы, а также по способам решения системы ли нейных уравнений с разложенной матрицей коэффициентов и обращения матрицы. Разнообразие задач достигается за счет вовлечения различных вариантов ортогонального разложения (см. лабораторную работу № 6, под разд. 7.16) и использования разных исходных матриц.

9 Фонд задач Задача Для матрицы 2 2 6 A= 2 выполнить следующее:

а. Построить QR-разложение матрицы A с помощью преобразований отражения (Хаусхолдера).

б. С помощью QR-разложения матрицы A решить систему линейных уравнений Ax = b, где вектор b = (3, 1, 8)T.

в. С помощью QR-разложения найти матрицу A1 и вычислить число MA обусловленности матрицы A в норме · = max {|xi|}, x R3.

i=1,2, 9.2 Решения и рекомендации к типовым задачам Задача Решение.

а. Используя метод исключения переменных Гаусса, нетрудно получить 1 00 LU = 3 1 0 0 1 2.

1 11 б. Решая две линейные системы с треугольными матрицами, получаем x = (1, 1, 1)T.

в. Три раза решая линейные системы с правой частью в виде столбцов еди ничной матрицы, получаем 0.00 0.25 0. A1 = 1.00 0.00 1.00, MA = 9 · 3 = 27.

2.00 0.50 0. 9.2 Решения и рекомендации к типовым задачам Задача Решение.

а. Метод Зейделя в координатном и каноническом виде:

xn+1 = 0.2xn + 0.8, xn+1 = 0.25xn+1 0.25xn + 0.5, 2 xn+1 = 0.5xn+1 0.5;

3 (D + A1 )(xn+1 xn ) + Axn = b, n = 0, 1,..., где 5 0 D + A1 = 1 0.

0 1 б. Метод сходится. Для доказательства нужно воспользоваться теоремой о необходимом и достаточном условии сходимости одношагового стацио нарного итерационного метода.

в. Используя метод Зейделя в координатном виде, вычисляем необходимые итерации, а воспользовавшись формулой для апостериорной оценки точности, находим норму ошибки на этих итерациях.

x1 = (0.80, 0.70, 0.85)T, x1 0.36, x2 = (0.94, 0.95, 0.98)T, x2 0.1.

Задача Решение.

а. Неявный метод скорейшего спуска в каноническом виде:

(xn+1 xn ) + Axn = b, B n = 0, 1,..., n+ (rn,wn ) а wn = B 1rn и rn = Axn b, где n+1 =, (Awn,wn ) B = D + A1 = 1 4 0.

9 Фонд задач б. Используя формулу для вычисления оптимального итерационного пара метра метода скорейшего спуска, получаем 1 = 1.27.

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

x1 = (1.02, 0.89, 1.08)T, x1 1.17.

Задача Решение.

а. 1 1/4 3 2/5 4 00 0 1 0 16 0 1 U =, D= 0 0 1 0.

0 0 00 1 0 0 0 б. x = (1, 1, 1, 1)T.

в. J(x) = 189.

Задача Решение.

а. 1 2.8 0.4 38 2 0.4 2.2 0 5 5.

QR = 2 1 2 00 б.

x = (1, 1, 1)T.

в. 39 48 A1 12 9 15, MA = 12 · 117/75 = 18.72.

= 2 11 9.3 Варианты контрольных заданий 9.3 Варианты контрольных заданий В этом подразделе приведены примеры того, как составляются варианты контрольных заданий для всеобъемлющей проверки базовых теоретических знаний и практических навыков по четырем основным темам курса Чис ленные методы (алгебры) : решение систем уравнений методом исключения неизвестных, решение систем уравнений итерационными методами, факто ризация положительно определенных матриц и ортогональные преобразова ния. Каждый из четырех представленных вариантов содержит четыре зада ния по этим темам. Реальное разнообразие вариантов достигается примене нием различных алгоритмов и исходных данных.

Вариант I Задание 1. Для матрицы 1 4 A = 1 2 2 8 выполнить следующее:

а. Построить LU -разложение матрицы A (L с единицами на главной диаго нали).

б. С помощью LU -разложения матрицы A решить систему линейных урав нений Ax = b, где вектор b = (2, 1, 5)T.

в. С помощью LU -разложения найти матрицу A1 и вычислить число обу словленности матрицы A (MA ) в норме · = max {|xi |}, x R3.

i=1,2, Задание 2. Для системы линейных алгебраических уравнений вида Ax = b, где матрица 10 5 A = 6 20 2 3 и вектор b = (4, 22, 5)T, выполнить следующее:

9 Фонд задач а. Выписать метод Якоби в координатном и каноническом виде.

б. Определить является ли он сходящимся с нулевым начальным прибли жением, т.е. x0 = (0, 0, 0)T ? Ответ обосновать.

в. Вычислить две итерации по методу Якоби и найти апостериорную оценку ошибки на каждой из них в норме · = max {|xi |}, x R3.

i=1,2, Задание 3. Для матрицы 2 1 2 8 P = 2 0 17 8 10 выполнить следующее:

а. Построить LLT -разложение матрицы P (L нижняя треугольная мат рица с положительными элементами главной диагонали).

б. С помощью LLT -разложения матрицы P решить систему P x = b, c вектором b = (4, 18, 5, 16)T.

в. С помощью разложения и решения системы по пп. а,б найти величину квадратной формы J(x) = xT P x, где x решение из п.б.

Задание 4. Для матрицы 1 2 6 A= 2 выполнить следующее:

а. Построить QR-разложение матрицы A с помощью ортогональных преоб разований (отражения Хаусхолдера).

б. С помощью QR-разложения матрицы A решить систему линейных урав нений Ax = b, где вектор b = (5, 15, 8)T.

9.3 Варианты контрольных заданий в. С помощью QR-разложения найти матрицу A1 и вычислить число обу словленности матрицы A (MA ) в норме · = max {|xi |}, x R3.

i=1,2, Вариант II Задание 1. Для матрицы 8 3 A = 5 1 выполнить следующее:

а. Построить U L-разложение матрицы A (U с единицами на главной диа гонали).

б. С помощью U L-разложения матрицы A решить систему линейных урав нений Ax = b, где вектор b = (8, 0, 1)T.

в. С помощью U L-разложения найти матрицу A1 и вычислить число обу словленности матрицы A (MA ) в норме · = max {|xi |}, x R3.

i=1,2, Задание 2. Для системы линейных алгебраических уравнений вида Ax = b, где матрица A = 1 10 0 3 и вектор b = (1, 3, 7)T, выполнить следующее:

а. Выписать метод Зейделя в координатном и каноническом виде.

б. Определить является ли он сходящимся с нулевым начальным прибли жением, т.е. x0 = (0, 0, 0)T ? Ответ обосновать.

в. Вычислить две итерации по методу Зейделя и найти апостериорную оценку ошибки на каждой из них в норме · = max {|xi|}, x R3.

i=1,2, 9 Фонд задач Задание 3. Для матрицы 3 12 4 3 P = 12 4 13 1 2 выполнить следующее:

а. Построить U U T -разложение матрицы P (U верхняя треугольная мат рица с положительными элементами главной диагонали).

б. С помощью U U T -разложения матрицы P решить систему P x = b, c вектором b = (12, 17, 3, 3)T.

в. С помощью разложения и решения системы по пп. а,б найти величину квадратной формы J(x) = xT P x, где x решение из п.б.

Задание 4. Для матрицы 2 A = 2 6 2 7 выполнить следующее:

а. Построить QR-разложение матрицы A с помощью ортогональных преоб разований (вращения Гивенса).

б. С помощью QR-разложения матрицы A решить систему линейных урав нений Ax = b, где вектор b = (6, 3, 12)T.

в. С помощью QR-разложения найти матрицу A1 и вычислить число обу словленности матрицы A (MA ) в норме · = max {|xi |}, x R3.

i=1,2, 9.3 Варианты контрольных заданий Вариант III Задание 1. Для матрицы 1 3 A= 1 3 9 выполнить следующее:

а. Построить LU -разложение матрицы A (U с единицами на главной диа гонали).

б. С помощью LU-разложения матрицы A решить систему линейных урав нений Ax = b, где вектор b = (3, 7, 13)T.

в. С помощью LU -разложения найти матрицу A1 и вычислить число обу словленности матрицы A (MA ) в норме · = max {|xi |}, x R3.

i=1,2, Задание 2. Для системы линейных алгебраических уравнений вида Ax = b, где матрица 10 2 A = 2 20 3 1 и вектор b = (16, 50, 15)T, выполнить следующее:

а. Выписать метод Якоби в координатном и каноническом виде.

б. Определить является ли он сходящимся с нулевым начальным прибли жением, т.е. x0 = (0, 0, 0)T ? Ответ обосновать.

в. Вычислить две итерации по методу Якоби и найти апостериорную оценку ошибки на каждой из них в норме · = max {|xi |}, x R3.

i=1,2, Задание 3. Для матрицы 2 2 2 6 0 P = 2 0 15 8 8 выполнить следующее:

9 Фонд задач а. Построить LDLT -разложение матрицы P (L нижняя треугольная мат рица с единицами на главной диагонали, D диагональная матрица с положительными элементами на диагонали).

б. С помощью LDLT -разложения матрицы P решить систему P x = b, c вектором b = (4, 16, 5, 27)T.

в. С помощью разложения и решения системы найти величину квадратной формы J(x) = xT P x, где x решение из п.б.

Задание 4. Для матрицы 1 2 4 A= 2 выполнить следующее:

а. Построить QR-разложение матрицы A с помощью преобразований (Грама–Шмидта ортогонализация).

б. С помощью QR-разложения матрицы A решить систему линейных урав нений Ax = b, где вектор b = (8, 1, 8)T.

в. С помощью QR-разложения найти матрицу A1 и вычислить число обу словленности матрицы A (MA ) в норме · = max {|xi |}, x R3.

i=1,2, Вариант IV Задание 1. Для матрицы 14 A= 4 24 выполнить следующее:

а. Построить U L-разложение матрицы A (L с единицами на главной диаго нали).

9.3 Варианты контрольных заданий б. С помощью U L-разложения матрицы A решить систему линейных урав нений Ax = b, где вектор b = (6, 22, 8)T.

в. С помощью U L-разложения найти матрицу A1 и вычислить число обу словленности матрицы A (MA ) в норме · = max {|xi |}, x R3.

i=1,2, Задание 2. Для системы линейных алгебраических уравнений вида Ax = b, где матрица 4 2 A = 2 5 0 и вектор b = (0, 7, 0)T, выполнить следующее:

а. Выписать метод Зейделя в координатном и каноническом виде.

б. Определить является ли он сходящимся с нулевым начальным прибли жением, т.е. x0 = (0, 0, 0)T ? Ответ обосновать.

в. Вычислить две итерации по методу Зейделя и найти апостериорную оценку ошибки на каждой из них в норме · = max {|xi|}, x R3.

i=1,2, Задание 3. Для матрицы 30 5 12 5 15 4 P = 12 4 7 3 1 2 выполнить следующее:

а. Построить U DU T -разложение матрицы P (U верхняя треугольная матрица с единицами на главной диагонали, D диагональная мат рица с положительными элементами на диагонали).

б. С помощью U DU T -разложения матрицы P решить систему P x = b, c вектором b = (16, 15, 3, 3)T.

9 Фонд задач в. С помощью разложения и решения системы найти величину квадратной формы J(x) = xT P x, где x решение из п.б.

Задание 4. Для матрицы 3 A = 2 4 2 5 выполнить следующее:

а. Построить QR-разложение матрицы A с помощью преобразований (модифицированная Грама–Шмидта ортогонализация).

б. С помощью QR-разложения матрицы A решить систему линейных урав нений Ax = b, где вектор b = (1, 3, 4)T.

в. С помощью QR-разложения найти матрицу A1 и вычислить число обу словленности матрицы A (MA ) в норме · = max {|xi |}, x R3.

i=1,2, 9.4 Задачи для контрольных заданий и экзамена Задача Для матрицы A = 4 1 2 3 выполнить следующее:

а. Построить LU -разложение матрицы A (L с единицами на главной диа гонали).

б. С помощью LU -разложения матрицы A решить систему линейных уравнений Ax = b, где вектор b = (0, 0, 3)T.

9.4 Задачи для контрольных заданий и экзамена в. С помощью LU -разложения найти матрицу A1 и вычислить число MA обусловленности матрицы A в норме · = max {|xi|}, x R3.

i=1,2, Задача Для матрицы 3 A = 5 10 1 выполнить следующее:

а. Построить U L-разложение матрицы A (U с единицами на главной диа гонали).

б. С помощью U L-разложения матрицы A решить систему линейных уравнений Ax = b, где вектор b = (10, 16, 5)T.

в. С помощью U L-разложения найти матрицу A1 и вычислить число MA обусловленности матрицы A в норме · = max {|xi|}, x R3.

i=1,2, Задача Для матрицы 3 1 1 A= 1 выполнить следующее:

а. Построить LU -разложение матрицы A (U с единицами на главной диа гонали).

б. С помощью LU-разложения матрицы A решить систему линейных уравнений Ax = b, где вектор b = (0, 2, 2)T.

9 Фонд задач в. С помощью LU-разложения найти матрицу A1 и вычислить число MA обусловленности матрицы A в норме · = max {|xi|}, x R3.

i=1,2, Задача Для матрицы 3 1 2 A= 4 0 выполнить следующее:

а. Построить U L-разложение матрицы A (L с единицами на главной диа гонали).

б. С помощью U L-разложения матрицы A решить систему линейных уравнений Ax = b, где вектор b = (5, 2, 0)T.

в. С помощью U L-разложения найти матрицу A1 и вычислить число MA обусловленности матрицы A в норме · = max {|xi|}, x R3.

i=1,2, Задача Для матрицы 2 A= 2 1 выполнить следующее:

а. Построить LU 1-разложение матрицы A (U 1 с единицами на главной диагонали).

б. С помощью LU 1-разложения матрицы A решить систему линейных уравнений Ax = b, где вектор b = (0, 1, 2)T.

9.4 Задачи для контрольных заданий и экзамена в. С помощью LU 1-разложения найти матрицу A1 и вычислить число MA обусловленности матрицы A в норме · = max {|xi|}, x R3.

i=1,2, Задача Для матрицы 1 A= 5 1 8 выполнить следующее:

а. Построить L1U -разложение матрицы A (L1 с единицами на главной диагонали).

б. С помощью L1U -разложения матрицы A решить систему линейных уравнений Ax = b, где вектор b = (3, 0, 0)T.

в. С помощью L1U -разложения найти матрицу A1 и вычислить число MA обусловленности матрицы A в норме · = max {|xi|}, x R3.

i=1,2, Задача Для системы линейных алгебраических уравнений вида Ax = b, где матрица 1 1 5 0. A= 1 и вектор b = (18, 1, 18)T, выполнить следующее:

а. Сформулировать метод Якоби в координатном и каноническом виде.

б. Определить является ли он сходящимся с нулевым начальным прибли жением, т.е. x0 = (0, 0, 0)T ? Ответ обосновать.

9 Фонд задач в. Вычислить две итерации по методу Якоби и найти апостериорную оценку ошибки на каждой из них в норме · = max {|xi|}, x R3.

i=1,2, Задача Для системы линейных алгебраических уравнений вида Ax = b, где матрица 10 3 A= 1 5 1 1 и вектор b = (5, 7, 19)T, выполнить следующее:

а. Сформулировать метод Якоби в координатном и каноническом виде.

б. Определить является ли он сходящимся с нулевым начальным прибли жением, т.е. x0 = (0, 0, 0)T ? Ответ обосновать.

в. Вычислить две итерации по методу Якоби и найти апостериорную оценку ошибки на каждой из них в норме · = max {|xi|}, x R3.

i=1,2, Задача Для системы линейных алгебраических уравнений вида Ax = b, где матрица 0 0 5 A= 1 2 и вектор b = (3, 2, 9)T, выполнить следующее:

а. Сформулировать метод Зейделя в координатном и каноническом виде.

б. Определить является ли он сходящимся с нулевым начальным прибли жением, т.е. x0 = (0, 0, 0)T ? Ответ обосновать.

9.4 Задачи для контрольных заданий и экзамена в. Вычислить две итерации по методу Зейделя и найти апостериорную оценку ошибки на каждой из них в норме · = max {|xi|}, x R3.

i=1,2, Задача Для системы линейных алгебраических уравнений вида Ax = b, где матрица 10 2 A = 2 5 0 1 и вектор b = (8, 4, 3)T, выполнить следующее:

а. Сформулировать метод Зейделя в координатном и каноническом виде.

б. Определить является ли он сходящимся с нулевым начальным прибли жением, т.е. x0 = (0, 0, 0)T ? Ответ обосновать.

в. Вычислить две итерации по методу Зейделя и найти апостериорную оценку ошибки на каждой из них в норме · = max {|xi|}, x R3.

i=1,2, Задача Для системы линейных алгебраических уравнений вида Ax = b, где матрица 1 1 5 0. A= 1 1 и вектор b = (9, 6, 0)T, выполнить следующее:

а. Сформулировать метод минимальных невязок в каноническом виде.

б. Определить оптимальный параметр 1 для нулевого начального при ближения, т.е. x0 = (0, 0, 0)T ?

9 Фонд задач в. Вычислить одну итерацию и найти апостериорную оценку ошибки в норме · = max {|xi |}, x R3.

i=1,2, Задача Для системы линейных алгебраических уравнений вида Ax = b, где матрица 1 1 5 0. A= 1 1 и вектор b = (9, 6, 0)T, выполнить следующее:

а. Сформулировать явный метод скорейшего спуска в каноническом виде.

б. Определить оптимальный параметр 1 для нулевого начального при ближения, т.е. x0 = (0, 0, 0)T ?

в. Вычислить одну итерацию и найти апостериорную оценку ошибки в норме · = max {|xi |}, x R3.

i=1,2, Задача Для системы линейных алгебраических уравнений вида Ax = b, где матрица 3 1 5 A= 2 1 и вектор b = (11, 0, 8)T, выполнить следующее:

а. Сформулировать метод минимальных невязок в каноническом виде.

б. Определить оптимальный параметр 1 для нулевого начального при ближения, т.е. x0 = (0, 0, 0)T ?

9.4 Задачи для контрольных заданий и экзамена в. Вычислить одну итерацию и найти апостериорную оценку ошибки в норме · = max {|xi |}, x R3.

i=1,2, Задача Для системы линейных алгебраических уравнений вида Ax = b, где матрица 3 A= 1 5 2 1 и вектор b = (11, 0, 8)T, выполнить следующее:

а. Сформулировать явный метод скорейшего спуска в каноническом виде.

б. Определить оптимальный параметр 1 для нулевого начального при ближения, т.е. x0 = (0, 0, 0)T ?

в. Вычислить одну итерацию и найти апостериорную оценку ошибки в норме · = max {|xi |}, x R3.

i=1,2, Задача Для системы линейных алгебраических уравнений вида Ax = b, где матрица 0 A= 0 5 1 2 и вектор b = (3, 2, 9)T, выполнить следующее:

а. На основе метода Зейделя сформулировать метод минимальных попра вок в каноническом виде.

б. Определить оптимальный параметр 1 для нулевого начального при ближения, т.е. x0 = (0, 0, 0)T ?

9 Фонд задач в. Вычислить одну итерацию и найти апостериорную оценку ошибки в норме · = max {|xi |}, x R3.

i=1,2, Задача Для системы линейных алгебраических уравнений вида Ax = b, где матрица 0 0 5 A= 1 2 и вектор b = (3, 2, 9)T, выполнить следующее:

а. На основе метода Зейделя сформулировать неявный метод скорейшего спуска в каноническом виде.

б. Определить оптимальный параметр 1 для нулевого начального при ближения, т.е. x0 = (0, 0, 0)T ?

в. Вычислить одну итерацию и найти апостериорную оценку ошибки в норме · = max {|xi |}, x R3.

i=1,2, Задача Для системы линейных алгебраических уравнений вида Ax = b, где матрица 10 2 A = 2 5 0 1 и вектор b = (8, 4, 3)T, выполнить следующее:

а. На основе метода Зейделя сформулировать метод минимальных попра вок в каноническом виде.

б. Определить оптимальный параметр 1 для нулевого начального при ближения, т.е. x0 = (0, 0, 0)T ?

9.4 Задачи для контрольных заданий и экзамена в. Вычислить одну итерацию и найти апостериорную оценку ошибки в норме · = max {|xi |}, x R3.

i=1,2, Задача Для системы линейных алгебраических уравнений вида Ax = b, где матрица 10 2 A = 2 5 0 1 и вектор b = (8, 4, 3)T, выполнить следующее:

а. На основе метода Зейделя сформулировать неявный метод скорейшего спуска в каноническом виде.

б. Определить оптимальный параметр 1 для нулевого начального при ближения, т.е. x0 = (0, 0, 0)T ?

в. Вычислить одну итерацию и найти апостериорную оценку ошибки в норме · = max {|xi |}, x R3.

i=1,2, Задача Для матрицы 4 2 2 2 2 3 P = 2 3 14 4 3 8 выполнить следующее:

а. Построить LLT -разложение матрицы P (L нижняя треугольная матрица с положительными элементами главной диагонали).

б. С помощью LLT -разложения матрицы P решить систему P x = b, c вектором b = (4, 10, 27, 40)T.

9 Фонд задач в. С помощью разложения и решения системы по пп. а,б найти величину квадратичной формы J(x) = xT P x, где x решение из п.б.

Задача Для матрицы 10 7 3 7 30 6 P = 3 6 9 4 10 0 выполнить следующее:

а. Построить U U T -разложение матрицы P (U верхняя треугольная матрица с положительными элементами главной диагонали).

б. С помощью U U T -разложения матрицы P решить систему P x = b, c вектором b = (4, 7, 0, 2)T.

в. С помощью разложения и решения системы по пп. а,б найти величину квадратичной формы J(x) = xT P x, где x – решение из п.б.

Задача Для матрицы 4 2 2 2 2 3 P = 2 3 14 4 3 8 выполнить следующее:

а. Построить LDLT -разложение матрицы P (L нижняя треугольная матрица с единицами на главной диагонали, D диагональная мат рица с положительными элементами на диагонали).

б. С помощью LDLT -разложения матрицы P решить систему P x = b, c вектором b = (8, 0, 5, 32)T.

9.4 Задачи для контрольных заданий и экзамена в. С помощью разложения и решения системы найти величину квадра тичной формы J(x) = xT P x, где x решение из п.б.

Задача Для матрицы 14 1 1 1 10 2 P = 1 2 5 3 0 1 выполнить следующее:

а. Построить U DU T -разложение матрицы P (U верхняя треугольная матрица с единицами на главной диагонали, D диагональная мат рица с положительными элементами на диагонали).

б. С помощью U DU T -разложения матрицы P решить систему P x = b, c вектором b = (19, 9, 5, 5)T.

в. С помощью разложения и решения системы найти величину квадра тичной формы J(x) = xT P x, где x решение из п.б.

Задача Для матрицы 1 A = 2 6 2 выполнить следующее:

а. Построить QR-разложение матрицы A с помощью ортогональных пре образований (Хаусхолдера / Гивенса / ГШО / МГШО).

б. С помощью QR-разложения матрицы A решить систему линейных уравнений Ax = b, где вектор b = (5, 15, 8)T.

9 Фонд задач в. С помощью QR-разложения найти матрицу A1 и вычислить число MA обусловленности матрицы A в норме · = max {|xi|}, x R3.

i=1,2, Задача Для матрицы 1 2 6 A= 2 выполнить следующее:

а. Построить QR-разложение матрицы A с помощью ортогональных пре образований (Хаусхолдера / Гивенса / ГШО / МГШО).

б. С помощью QR-разложения матрицы A решить систему линейных уравнений Ax = b, где вектор b = (6, 3, 12)T.

в. С помощью QR-разложения найти матрицу A1 и вычислить число MA обусловленности матрицы A в норме · = max {|xi|}, x R3.

i=1,2, Задача Для матрицы 2 2 6 A= 2 7 выполнить следующее:

а. Построить QR-разложение матрицы A с помощью ортогональных пре образований (Хаусхолдера / Гивенса / ГШО / МГШО).

б. С помощью QR-разложения матрицы A решить систему линейных уравнений Ax = b, где вектор b = (8, 1, 8)T.

9.4 Задачи для контрольных заданий и экзамена в. С помощью QR-разложения найти матрицу A1 и вычислить число MA обусловленности матрицы A в норме · = max {|xi|}, x R3.

i=1,2, Задача Для матрицы 1 2 6 A= 2 7 выполнить следующее:

а. Построить QR-разложение матрицы A с помощью ортогональных пре образований (Хаусхолдера / Гивенса / ГШО / МГШО).

б. С помощью QR-разложения матрицы A решить систему линейных уравнений Ax = b, где вектор b = (5, 5, 12)T.

в. С помощью QR-разложения найти матрицу A1 и вычислить число MA обусловленности матрицы A в норме · = max {|xi|}, x R3.

i=1,2, Задача Для матрицы 1 2 6 A= 2 выполнить следующее:

а. Построить QR-разложение матрицы A с помощью ортогональных пре образований (Хаусхолдера / Гивенса / ГШО / МГШО).

б. С помощью QR-разложения матрицы A решить систему линейных уравнений Ax = b, где вектор b = (6, 3, 12)T.

9 Фонд задач в. С помощью QR-разложения найти матрицу A1 и вычислить число MA обусловленности матрицы A в норме · = max {|xi|}, x R3.

i=1,2, Задача Для матрицы 1 2 2 A= 2 7 выполнить следующее:

а. Построить QR-разложение матрицы A с помощью ортогональных пре образований (Хаусхолдера / Гивенса / ГШО / МГШО).

б. С помощью QR-разложения матрицы A решить систему линейных уравнений Ax = b, где вектор b = (1, 3, 4)T.

в. С помощью QR-разложения найти матрицу A1 и вычислить число MA обусловленности матрицы A в норме · = max {|xi|}, x R3.

i=1,2, Задача Для матрицы 1 2 6 A= 2 7 выполнить следующее:

а. Построить QR-разложение матрицы A с помощью ортогональных пре образований (Хаусхолдера / Гивенса / ГШО / МГШО).

б. С помощью QR-разложения матрицы A решить систему линейных уравнений Ax = b, где вектор b = (8, 1, 8)T.

9.4 Задачи для контрольных заданий и экзамена в. С помощью QR-разложения найти матрицу A1 и вычислить число MA обусловленности матрицы A в норме · = max {|xi|}, x R3.

i=1,2, Задача Для матрицы 2 2 6 A= 2 7 выполнить следующее:

а. Построить QR-разложение матрицы A с помощью ортогональных пре образований (Хаусхолдера / Гивенса / ГШО / МГШО).

б. С помощью QR-разложения матрицы A решить систему линейных уравнений Ax = b, где вектор b = (6, 3, 12)T.

в. С помощью QR-разложения найти матрицу A1 и вычислить число MA обусловленности матрицы A в норме · = max {|xi|}, x R3.

i=1,2, Задача Для матрицы 2 2 6 A= 2 7 выполнить следующее:

а. Построить QR-разложение матрицы A с помощью ортогональных пре образований (Хаусхолдера / Гивенса / ГШО / МГШО).

б. С помощью QR-разложения матрицы A решить систему линейных уравнений Ax = b, где вектор b = (7, 1, 10)T.

9 Фонд задач в. С помощью QR-разложения найти матрицу A1 и вычислить число MA обусловленности матрицы A в норме · = max {|xi|}, x R3.

i=1,2, Задача Для матрицы 2 2 6 A= 2 7 выполнить следующее:

а. Построить QR-разложение матрицы A с помощью ортогональных пре образований (Хаусхолдера / Гивенса / ГШО / МГШО).

б. С помощью QR-разложения матрицы A решить систему линейных уравнений Ax = b, где вектор b = (1, 3, 4)T.

в. С помощью QR-разложения найти матрицу A1 и вычислить число MA обусловленности матрицы A в норме · = max {|xi|}, x R3.

i=1,2, Задача Для матрицы 2 2 6 A= 2 выполнить следующее:

а. Построить QR-разложение матрицы A с помощью ортогональных пре образований (Хаусхолдера / Гивенса / ГШО / МГШО).

б. С помощью QR-разложения матрицы A решить систему линейных уравнений Ax = b, где вектор b = (10, 5, 4)T.

9.4 Задачи для контрольных заданий и экзамена в. С помощью QR-разложения найти матрицу A1 и вычислить число MA обусловленности матрицы A в норме · = max {|xi|}, x R3.

i=1,2, Задача Для матрицы 3 2 4 A= 2 выполнить следующее:

а. Построить QR-разложение матрицы A с помощью ортогональных пре образований (Хаусхолдера / Гивенса / ГШО / МГШО).

б. С помощью QR-разложения матрицы A решить систему линейных уравнений Ax = b, где вектор b = (8, 9, 4)T.

в. С помощью QR-разложения найти матрицу A1 и вычислить число MA обусловленности матрицы A в норме · = max {|xi|}, x R3.

i=1,2, Задача Для матрицы 1 2 4 A= 2 выполнить следующее:

а. Построить QR-разложение матрицы A с помощью ортогональных пре образований (Хаусхолдера / Гивенса / ГШО / МГШО).

б. С помощью QR-разложения матрицы A решить систему линейных уравнений Ax = b, где вектор b = (5, 5, 14)T.

9 Фонд задач в. С помощью QR-разложения найти матрицу A1 и вычислить число MA обусловленности матрицы A в норме · = max {|xi|}, x R3.

i=1,2, Задача Для матрицы 3 2 4 A= 2 5 выполнить следующее:

а. Построить QR-разложение матрицы A с помощью ортогональных пре образований (Хаусхолдера / Гивенса / ГШО / МГШО).

б. С помощью QR-разложения матрицы A решить систему линейных уравнений Ax = b, где вектор b = (7, 1, 10)T.

в. С помощью QR-разложения найти матрицу A1 и вычислить число MA обусловленности матрицы A в норме · = max {|xi|}, x R3.

i=1,2, Задача Для матрицы 1 2 4 A= 2 5 выполнить следующее:

а. Построить QR-разложение матрицы A с помощью ортогональных пре образований (Хаусхолдера / Гивенса / ГШО / МГШО).

б. С помощью QR-разложения матрицы A решить систему линейных уравнений Ax = b, где вектор b = (2, 1, 6)T.

9.4 Задачи для контрольных заданий и экзамена в. С помощью QR-разложения найти матрицу A1 и вычислить число MA обусловленности матрицы A в норме · = max {|xi|}, x R3.

i=1,2, Задача Для матрицы 1 2 4 A= 2 выполнить следующее:

а. Построить QR-разложение матрицы A с помощью ортогональных пре образований (Хаусхолдера / Гивенса / ГШО / МГШО).

б. С помощью QR-разложения матрицы A решить систему линейных уравнений Ax = b, где вектор b = (1, 7, 0)T.

в. С помощью QR-разложения найти матрицу A1 и вычислить число MA обусловленности матрицы A в норме · = max {|xi|}, x R3.

i=1,2, Задача Для матрицы 1 3 2 A= 2 5 выполнить следующее:

а. Построить QR-разложение матрицы A с помощью ортогональных пре образований (Хаусхолдера / Гивенса / ГШО / МГШО).

б. С помощью QR-разложения матрицы A решить систему линейных уравнений Ax = b, где вектор b = (4, 7, 16)T.

9 Фонд задач в. С помощью QR-разложения найти матрицу A1 и вычислить число MA обусловленности матрицы A в норме · = max {|xi|}, x R3.

i=1,2, Задача Для матрицы 1 2 4 A= 2 выполнить следующее:

а. Построить QR-разложение матрицы A с помощью ортогональных пре образований (Хаусхолдера / Гивенса / ГШО / МГШО).

б. С помощью QR-разложения матрицы A решить систему линейных уравнений Ax = b, где вектор b = (8, 1, 8)T.

в. С помощью QR-разложения найти матрицу A1 и вычислить число MA обусловленности матрицы A в норме · = max {|xi|}, x R3.

i=1,2, Задача Для матрицы 1 2 4 A= 2 5 выполнить следующее:

а. Построить QR-разложение матрицы A с помощью ортогональных пре образований (Хаусхолдера / Гивенса / ГШО / МГШО).

б. С помощью QR-разложения матрицы A решить систему линейных уравнений Ax = b, где вектор b = (8, 11, 3)T.

9.4 Задачи для контрольных заданий и экзамена в. С помощью QR-разложения найти матрицу A1 и вычислить число MA обусловленности матрицы A в норме · = max {|xi|}, x R3.

i=1,2, Задача Для матрицы 3 2 4 A= 2 5 выполнить следующее:

а. Построить QR-разложение матрицы A с помощью ортогональных пре образований (Хаусхолдера / Гивенса / ГШО / МГШО).

б. С помощью QR-разложения матрицы A решить систему линейных уравнений Ax = b, где вектор b = (1, 3, 4)T.

в. С помощью QR-разложения найти матрицу A1 и вычислить число MA обусловленности матрицы A в норме · = max {|xi|}, x R3.

i=1,2, Задача Для матрицы 3 2 4 A= 2 5 выполнить следующее:

а. Построить QR-разложение матрицы A с помощью ортогональных пре образований (Хаусхолдера / Гивенса / ГШО / МГШО).

б. С помощью QR-разложения матрицы A решить систему линейных уравнений Ax = b, где вектор b = (9, 3, 6)T.

9 Фонд задач в. С помощью QR-разложения найти матрицу A1 и вычислить число MA обусловленности матрицы A в норме · = max {|xi|}, x R3.

i=1,2, Задача Для матрицы 3 A = 2 4 2 5 выполнить следующее:

а. Построить QR-разложение матрицы A с помощью ортогональных пре образований (Хаусхолдера / Гивенса / ГШО / МГШО).

б. С помощью QR-разложения матрицы A решить систему линейных уравнений Ax = b, где вектор b = (2, 6, 7)T.

в. С помощью QR-разложения найти матрицу A1 и вычислить число MA обусловленности матрицы A в норме · = max {|xi|}, x R3.

i=1,2, Задача Для матрицы 3 A = 2 4 2 выполнить следующее:

а. Построить QR-разложение матрицы A с помощью ортогональных пре образований (Хаусхолдера / Гивенса / ГШО / МГШО).

б. С помощью QR-разложения матрицы A решить систему линейных уравнений Ax = b, где вектор b = (2, 6, 7)T.

в. С помощью QR-разложения найти матрицу A1 и вычислить число MA обусловленности матрицы A в норме · = max {|xi|}, x R3.

i=1,2, II Линейное оценивание Теоретические основы Пусть два вектора x Rn и z Rm связаны (в общем случае) прибли женным равенством z Ax. Требуется выбрать такое значение x вектора x, которое минимизирует квадрат отклонения v z Ax, т. е. найти x = arg min(z Ax)T (z Ax).

x Метод отыскания такого x был предложен Лежандром в 1805 году в виде алгебраической процедуры и обоснован как статистическая процедура Гаус сом в 1809 году (хотя утверждается, что рукопись Гаусса была известна на немецком языке уже с 1806 года [97]). Гаусс в 1809 году заявлял, что поль зовался этим методом как алгебраической процедурой уже в 1795 году, чем вызвал немалое раздражение Лежандра [137].

Таким образом, с момента возникновения метод наименьших квадратов (МНК) рассматривается как процедура алгебраическая или процедура ста тистическая, но какого-либо противопоставления этих процедур нет. Есть лишь разные точки зрения: ставить задачу с позиций Линейной алгебры (ЛА) или же с позиций Теории вероятностей (ТВ) и Математической стати стики (МС). ЛА придает задаче наименьших квадратов лаконичную форму, позволяет анализировать все решения этой задачи и формулировать метод.

ТВ и МС дают возможность подходить к этой задаче не формально алгебра ически, а с точки зрения неопределенности, присущей реальным эксперимен тальным данным z. Замечательно, что МС, формулируя задачу независимо и совершенно в других терминах, приводит к тем же аналитическим реше ниям, что и ЛА. Можно говорить, что МС дает статистическую интерпре тацию для чисто алгебраической задачи и алгебраического метода решения несовместных систем линейных алгебраических уравнений z Ax. Вычис лительная линейная алгебра (ВЛА) предлагает множество идей и подходов для эффективной численной реализации МНК.


10 Теоретические основы В настоящее временя МНК имеет множество приложений и эффективных численных реализаций и часто излагается как раздел Эконометрики [19], Математических методов обработки данных [49, 50], как Прикладной регрес сионный анализ [34] или Регрессионное моделирование [26].

Приводимый ниже материал имеет базовый теоретический характер.

В последующих разделах методы ВЛА применяются для изложения эффек тивных численных алгоритмов решения этих задач.

10.1 Конечномерные линейные пространства Множество L в Rn (L Rn ) называется линейным подпространством пространства Rn всех вещественных n-мерных 1 векторов, или, короче, под пространством в Rn, если при любых скалярных величинах и принад лежность x L и y L влечет принадлежность x + y L. Это выража ется следующей формулой:, R1 ((x L & y L) (x + y L)).

Линейная независимость системы {a1,..., am } Rn означает, что спра ведлива импликация m m i ai = 0 i = 0, i= i= в противном случае система называется линейно зависимой.

Подпространство L Rn называется m-мерным, т. е. имеющим размер ность dim L = m, если в нем имеется такая линейно независимая система векторов {a1,..., am }, что добавление к этой системе любого вектора a Rn дает уже линейно зависимую систему, содержащую m + 1 векторов. 3 Это выражается следующей формулой:

m m 1 m i ai = {a,..., a } L i = 0 & i= i= m i ai + i+1a = a L & & (i+1 = 0).

i= n-мерный вектор содержит n-компонент.

Импликация A B означает: из A следует B, или A влечет B, или если A, то B.

Такая система {a1,..., am } называется максимальной линейно независимой системой.

10.1 Конечномерные линейные пространства Так как m+1 = 0, то m µi ai, µi = i /m+1.

a= i= Следовательно, любой вектор a L, где dim L = m, может быть представ лен в виде линейной комбинации векторов {a1,..., am }. Система векторов {a1,..., am }, обладающая этим свойством, образует базис в L. В этом случае записывают L = L(a1,..., am ) и говорят, что L натянуто на {a1,..., am }.

Если каждый вектор из L может быть выражен линейной комбинацией системы векторов a1,..., am, то L называют линейной оболочкой векторов {a1,..., am }.

Множество L0, состоящее из одного нулевого вектора 0, является подпро странством в Rn размерности 0 и называется нулевым подпространством.

n-мерное евклидово пространство En это пространство Rn, в котором определено скалярное произведение двух векторов x и y по формуле (x, y) = = x1y1 + · · · + xnyn = xT y. 4 Норма x вектора x En равна (x, x)1/2, то есть x 2 = xT x. Расстояние между x, y En есть x y. Векторы x и y ортогональны, x y, если их скалярное произведение равно нулю:

(x, y) = xT y = 0. Вектор v Rn ортогонален к L, v L, если он ортогонален к любому вектору u L. Ортогональное дополнение к L, обозначаемое L, есть множество всех векторов в Rn, каждый из которых ортогонален к L.

Пусть L0 L Rn. Тогда:

Теорема 10.1 ( [25]).

(1) существуют целое число m, 1 m n, и ортонормированный базис {a1,..., am } в L. Если этот базис продолжить любым способом до орто нормированного базиса a1,..., am, am+1,..., an (10.1) в Rn, то линейное подпространство M с базисом am+1,..., an обладает свойствами:

(2) M = L, (3) L = M, (4) для любого вектора x Rn существует единственное разложение x L, x M.

x= x+x, (10.2) Везде, где не оговорено противное, в этой книге рассматривается пространство вещественных чисел и, кроме того, любой вектор ассоциируется с матрицей-столбцом.

10 Теоретические основы Доказательство.

(1) Так как L отлично от нулевого подпространства, L L0, то в нем суще ствует вектор a, отличный от 0. Образуем нормальный (т. е. с единичной нормой) вектор a1 = a/ a. Если в L найдется вектор, ортогональный к a1, нормируем его аналогично и обозначим a2. Если найдется вектор, ортогональный к a1 и к a2, нормируем его и обозначим a3. Продолжая этот процесс, завершим его построением ортонормированной системы векторов {a1,..., am }, где m 1 и m n. Действительно, a1 L, но m не может быть равно n. В противном случае векторы {a1,..., an } образовали бы базис в L (так как ортонормированные векторы линейно независимы), что означало бы L = Rn. Однако по условию L не совпа дает с Rn (L Rn ), поэтому m n.

Построенная система {a1,..., am } есть базис в L. Действительно, вместе с векторами {a1,..., am } к L принадлежат и все их линейные комбина ции, то есть векторы вида m i ai, i = (u, ai).

u= (10.3) i= Однако кроме них, других векторов в L нет. Допустив противное, сле довало бы считать, что и векторы вида m (x, ai) ai + y, x= (10.4) i= где y = 0, входят в L, x L. А так как все ai L, то и вектор m (x, ai) ai y =x i= следовало бы включить в L. Но для всех k = 1,..., m имеем m k k (x, ai)(ai, ak ) = 0, (y, a ) = (x, a ) (10.5) i= то есть k = 1,..., m (y ak ). Пронормированный вектор y/ y мог бы стать тем am+1, который расширил бы систему {a1,..., am } до системы {a1,..., am, am+1}. Однако это невозможно из-за доказанного ограничения для числа m. Тем самым утверждение (1) теоремы дока зано.

10.1 Конечномерные линейные пространства (2) Поскольку m n, в Rn существует вектор x, не зависящий линейно от {a1,..., am }, то есть выражаемый равенством (10.4), в котором y = 0, y Rn. Так как для y справедливо (10.5), построение базиса в Rn можно продолжить, как только что указано, до (10.1). Но любой вектор v M определяется, подобно (10.3), в виде n i ai, i = (v, ai).

v= (10.6) i=m+ Очевидно, что v u, и если известно, что какой-нибудь вектор a Rn ортогонален ко всем векторам из L, a L, то a M. Тем самым доказано утверждение (2) теоремы.

(3) Имеем u v. Если для какого-нибудь вектора a Rn известно, что a M, то a L. Доказано утверждение (3) теоремы.

(4) Наконец, если x – произвольный вектор в Rn, то единственно его пред ставление n µi ai, x= i= так как единственным образом определяются числа µi = (x, ai) = xT ai, называемые числовыми проекциями вектора x на направление единич ного вектора ai. Отсюда единственно разложение (10.2), причем m n i µi ai M.

µi a L, x= x= k=1 k=m+ Теорема 10.1 содержится в стандартных курсах линейной алгебры [25] и для метода наименьших квадратов может считаться отправной точкой.

Ее называют теоремой об ортогональном разложении пространства Rn и формулируют также следующим образом [13].

Теорема 10.2. Если оба L и M Rn и выполнено хотя бы одно из следующих условий:

(1) L = M (L состоит из векторов, ортогональных к M), (2) M = L (M состоит из векторов, ортогональных к L), (3) L и M взаимно ортогональны и dim L + dim M = n, 10 Теоретические основы то L и M являются ортогональными дополнениями друг к другу. Если выполнено хотя бы одно из этих трех эквивалентных условий, то любой век тор x Rn может быть разложен единственным образом в сумму x = x + x, где x L, x M. Составляющие этого разложения x и x являются проек циями вектора x на подпространства L и M, соответственно, и они взаимно ортогональны, т. е. xT x = 0.

Доказательство. Все, что есть в этой формулировке, уже доказано в Теореме 10.1, кроме последнего утверждения о проекциях вектора x. Чтобы доказать и это, напомним, что проекцией вектора x на подпространство L называется вектор из L, ближайший к вектору x.

Для любого y L имеем 2 2 2 + x 2, xy = x+xy = ( y) + x = xy x так как x y L и ( y) x. Поэтому x y 2 x 2, и строгое x неравенство выполняется, если и только если y = x. Следовательно, x проекция x на L. Замечание 10.1. Проекцию x вектора x на подпространство L будем обозначать следующим образом: x = (x L).

10.2 Обобщение на гильбертовы пространства Замечательно, что возможности линейной алгебры не ограничиваются конечномерными пространствами, состоящими лишь из детерминистских векторов. Реальные прикладные задачи имеют дело с функциями, причем не обязательно детерминистскими, а случайными. Необходимость оперировать со значениями функции на интервалах независимой переменной приводит к понятию бесконечномерного вектора. Действительно: любую функцию на интервале значений аргумента можно рассматривать как вектор с контину альным количеством компонент, равных значениям этой функции при изме нении аргумента в своем интервале. Дальнейшее усложнение картины мы получаем, когда рассматриваем случайные функции, то есть функции, при нимающие значения из некоторого выборочного, вероятностного простран ства. Эти обобщения содержатся в теории гильбертовых пространств слу чайных переменных, строгое построение которой можно найти, например, в фундаментальной монографии [92].

10.2 Обобщение на гильбертовы пространства В гильбертовых пространствах, обозначаемых H, сохраняются все основ ные определения.

Определение 10.1. Подпространством L векторного пространства X называют любое подмножество L данного множества X, L X, на котором x, y L влечет x + y L для всех, R. При этом L называют собственным подпространством, если L = X, т. е. L X. Для любого мно жества L X обозначение Sp {L} используют для множества всех конечных линейных комбинаций элементов множества L. Множество Sp {L} называют линейной оболочкой 5.

В гильбертовых пространствах, как и в конечномерных, понятие внутрен него (скалярного) произведения дает абстрактную формулировку концепции угла, и как результат, обобщенное понятие перпендикулярности.

Определение 10.2. Векторы x, y H называются ортогональными, если (x, y) = 0, и это обозначают записью x y. Если S H есть любое подмножество (и, в особенности, если S есть подпространство) в H, тогда пишут x S, если s S, x s. Подобно этому, обозначение S T для двух подмножеств S и T в H, указывает, что все элементы подмножества S ортогональны всем элементам подмножества T.


Приведем главный результат геометрии гильбертовых пространств. Он называется Теоремой о проекции. Как и в случае конечномерных про странств (см. подразд. 10.1) он просто устанавливает тот факт, что кратчай ший путь от точки до плоскости лежит на перпендикуляре от этой точки до данной плоскости (рис. 10.1). Нижеследующая Теорема о проекции обобщает этот результат на гильбертовы пространства.

Теорема 10.3 (Теорема об ортогональной проекции [92]). Пусть L есть собственное подпространство некоторого гильбертова пространства H и пусть x есть точка в H. Тогда x может быть единственным образом пред ставлено в форме x= y+z с y L и z L. Кроме того, для всех w L имеем xw xy, где равенство возможно, если и только если w = y (см. рис. 10.1).

Доказательство. См. [92]. Span = оболочка.

10 Теоретические основы x H xw L y w Рис. 10.1. Теорема об ортогональной проекции Метод наименьших квадратов заключается в практическом применении этой теоремы, т.е. в отыскании вектора y L H, ближайшего к заданному вектору x H и x L. Обобщение на гильбертовы пространства позволяет / пользоваться этим методом для обоснования многих теоретических резуль татов в широком классе линейных стохастических систем, включая: теорию оценивания, теорию оптимальной фильтрации и предсказания, теорию пара метрической идентификации стохастических динамических систем и теорию адаптивного управления [92].

10.3 Проектирование в конечномерных пространствах Вернемся к конечномерным пространствам. На основании Теоремы 10. может быть построено доказательство следующего утверждения, в котором используется понятие ранга матрицы A, а именно: rank A равен максималь ному числу строк (или столбцов) матрицы A, образующих линейно незави симую систему.

Теорема 10.4 ( Основная теорема линейной алгебры). С любой (n m)-матрицей A, имеющей rank A = r, ассоциированы четыре фунда ментальных подпространства:

(1) R(AT ) пространство строк матрицы A, dim R(AT ) = r, (2) N (A) нуль-пространство, т. е. ядро матрицы A, dim N (A) = m r, (3) R(A) пространство столбцов (образ) матрицы A, dim R(A) = r, 10.3 Проектирование в конечномерных пространствах (4) N (AT ) левое нуль-пространство матрицы A, dim N (AT ) = n r, при этом N (A) = (R(AT )), R(AT ) = (N (A)), N (AT ) = (R(A)), R(A) = (N (AT )).

Последнее означает, что система Ax = z имеет решение тогда и только тогда, когда вектор z N (AT ), то есть z R(A) тогда и только тогда, когда z ортогонален к каждому решению системы AT y = 0.

Базовые понятия, содержащиеся в этой теореме, широко используются в дальнейшем.

Определение 10.3. Квадратная матрица P называется матрицей проектирования или проектором на L, если (x P x) L, т. е. для всех x Rn проекция x = P x.

Теорема 10.5.

(1) Проекционная матрица P обладает свойствами:

(i) P 2 = P (идемпотентность), (ii) P = P T (симметричность).

(2) Любая матрица P, обладающая этими свойствами, является проекцион ной матрицей, причем она проектирует любой вектор на свое простран ство столбцов, R(P ).

(3) Если L = L(a1,..., am ), ai Rn и {a1,..., am } базис в L, то 1 T T 1 m P = PA = A(A A) A, где A = [a | · · · | a ] – матрица, столбцами которой служат векторы ai (i = 1, 2,..., m).

Доказательство.

(1) Свойство (i). Определение проектора на L означает, что x {P x = x, x = x + x, x L, x L, P x = 0}.

Отсюда x {P 2 x = P x = P (x x) = P x P x = P x, (P 2 P )x = 0}.

Следовательно, P 2 = P.

Свойство (ii). Имеем x, y {P x L, (I P )y L}. Отсюда (P x)T (I P )y = 0, xT (P T P T P )y = 0, P T = P T P, P = = (P T P )T = P T P. Следовательно, P = P T.

10 Теоретические основы (2) Пусть P есть (n n)-матрица со свойствами (i) и (ii) из предыдущего пункта теоремы. Имеем P x R(P ). В то же время R(P ) есть множе ство векторов вида P y, где y – любой вектор из Rn.

Найдем скалярное произведение (x P x)T P y = xT (I P T )P y = xT (P P T P )y = = xT (P P 2 )y = xT (P P )y = 0.

Следовательно, для любого x Rn произведение P x есть проекция вектора x на R(P ).

(3) Пусть P = A(AT A)1AT. Имеем P x L = R(A). В то же время R(A) есть множество векторов вида Ay, где y любой вектор из Rn. Найдем скалярное произведение (Ay)T (x P x) = y T AT [I A(AT A)1AT ]x = = y T [AT AT A(AT A)1AT ]x = 0.

Следовательно, x P x L для всех x Rn. В качестве простого следствия отсюда легко видеть, что проекция век тора x на L(y) задается формулой (xT y)y/ y 2, если y = 0. Также в ка честве следствия можно получить так называемую теорему разложения Фурье [1].

Теорема 10.6 (Теоремa разложения Фурье [1]). Пусть дано собствен ное подпространство L = L(a1,..., am ) Rn и {a1,..., am } ортонормиро ванный базис в L. Тогда для произвольного x Rn проекция x на L задается формулой m ai (ai )T x = AAT x, x= i= где A = [a1 |... | am ], т. е. P = PA = AAT, или же равносильной формулой m m Ti i (x, ai) ai.

x= (x a ) a = i=1 i= Кроме того, легко видеть в качестве следствия Теоремы 10.5, что если P есть проектор на L, то (I P ) есть проектор на L, где L = R(P ) и L = N (P T ).

Замечание 10.2. Теорема 10.5 в пункте (3) определяет матрицу проектирования на пространство R(A) столбцов данной (n m)-матрицы 10.4 Наименьшие квадраты и псевдоинверсия A, когда rank A = m. Эту матрицу удобно обозначить PA. Теорема 10. устанавливает, что в этом случае PA = A(AT A)1AT, в то время как Тео рема 10.6 рассматривает частный, но для вычислений очень удобный под случай, когда AT A = I, при этом PA = AAT. Наиболее общий случай проек тирования на R(A), когда (n m)-матрица A произвольна и не ограничена условием rank A = m, рассмотрен ниже (подразд. 10.4).

10.4 Наименьшие квадраты и псевдоинверсия Линейная задача наименьших квадратов возникает из необходимости решать систему линейных алгебраических уравнений Ax = z с произвольно заданными (n m)-матрицей A и правой частью z Rn. При этом в силу произвольности A и z система может оказаться несовместной (в этом слу чае правильнее писать Ax z) или же иметь одно или бесконечно много решений x Rm. Решение линейной системы Ax z в смысле наименьших квадратов 6 определяют как вектор x, доставляющий наименьшее значение квадратическому критерию качества = (z Ax)T (z Ax).

J(x) = z Ax (10.7) Таким образом, arg min (z Ax)T (z Ax).

x m xR Очевидно, данное определение эквивалентно соглашению принять в каче стве МНК-решения любой вектор x, если и только если A = z, где z x проекция z на R(A).

Теорема 10.7. МНК-решение x системы Ax = z, где A = A(n, m), удовлетворяет системе нормальных уравнений:

AT A = aT z.

x (10.8) Это решение всегда существует, хотя может быть не единственным. Оно единственно тогда и только тогда, когда A имеет полный столбцовый ранг, rank A = m.

Доказательство. По определению x имеем A = z, (z z ) Ac. Здесь x m c любой вектор из R. Это означает, что c Rm, (Ac)T (z z ) = cT (AT z AT A) = 0.

x Иначе, МНК-решение.

10 Теоретические основы Следовательно, AT z aT A = 0, т. е. x удовлетворяет (10.8). Эта система x всегда совместна, так как оба вектора AT z и AT (A) принадлежат одному x и тому пространству R(AT ) при Rm. Для установления условия един x ственности решения x докажем промежуточный результат.

Лемма 10.1. Справедливы равенства:

(1) R(AT ) = R(AT A), (2) R(A) = R(AAT ), (3) N (AT ) = N (AAT ), (4) N (A) = N (AT A).

Доказательство. На основании соотношений подпространств из Тео ремы (10.4), утверждение (1) Леммы 10.1 эквивалентно утверждению (4);

аналогично этому, утверждение (2) Леммы 10.1 эквивалентно утверждению (3). Поэтому достаточно доказать утверждение (3) и утверждение (4). Чтобы доказать совпадение N (A) с N (AT A), заметим, что AT Ax = 0, если Ax = 0.

В обратную сторону: если AT Ax = 0, то xT AT Ax = 0, т. е. Ax 2 = 0, что влечет Ax = 0. Таким образом, Ax = 0 эквивалентно AT Ax = 0, т. е.

N (A) = N (AT A). Аналогично устанавливается утверждение (3). Завершая доказательство Теоремы 10.7, используем из только что дока занной Леммы 10.1 утверждение (1). Согласно этому утверждению, rank A = = rank AT A. По условию теоремы, rank A = m. Отсюда, (m m)-матрица AT A системы (10.8) имеет полный ранг, т. е. (AT A)1 существует. В этом случае имеем единственное МНК-решение x = (AT A)1AT z. Очевидно, это возможно только при n m (переопределенные системы Ax = z) и rank A = m (полный столбцовый ранг). В других случаях: (i ) при n m, но rank A = r m, или (ii ) при n m, решение x не может быть един ственным. Каким образом в случае неединственности x выбрать среди x единствен ный вектор x0, в некотором смысле оптимальный?

нор Определение 10.4. Оптимальным МНК-решением, или иначе мальным псевдорешением системы Ax = z, называется вектор x0, кото рый имеет минимальную (евклидову) норму среди всех x, удовлетворяющих системе A = z, z R(A), (z z ) R(A).

x Замечание 10.3. Пусть rank A = m, когда в согласии с Теоре мой (10.7) имеем единственное x = (AT A)1AT z, оно же x0. Если теперь 10.4 Наименьшие квадраты и псевдоинверсия записать x0 = A+z, где A+ некоторая матрица, то для этого случая она 1 T + T определяется как A = (A A) A. Эта формула (при условии rank A = m) включает в себя наиболее простой случай, когда n = m. Тогда A1 суще ствует, A+ = A1 и x0 = A1z, что совпадает с обычным решением системы Ax = z, которая при этих условиях есть стандартная совместная система с квадратной матрицей A. Таким образом, матрица A+ обобщает понятие обратной матрицы A1 на случай, когда матрица A в системе Ax = z про извольна по своим размерам и рангу. В связи с этим она названа псевдооб ратной матрицей A+ к (n m)-матрице A;

при rank A = m она, как выше отмечено, равна (AT A)1AT. Перейдем к общему случаю для A+.

Определение 10.5. Псевдообратная матрица (в общем случае про извольной матрицы A) есть такая матрица A+, которая из всех решений x системы A = z, где z R(A) и (z z ) R(A) при произвольном векторе x z, выбирает x0 с минимальной нормой, определяя его как x0 = A+ z.

Следствие 10.1. Проектор на R(A) = L(a1,..., am ), где все столбцы a1,..., am Rn матрицы A не обязательно образуют линейно независимую систему векторов, определяется выражением PA = AA+. Соответственно, проектор на N (AT ) = R(A).

(I AA+) Действительно, проекция любого вектора z на R(A) равна z = A0 = x + = (AA )z = PA z, а z = z z = (I PA )z.

То, что x0 (а значит, и A+) существует, ясно из Теоремы 10.7. Однако, единствен ли вектор x0 ? В каком подпространстве он лежит и как его найти?

Ответить на эти вопросы означает, по существу, выяснить все свойства псев дообратной матрицы A+, поскольку приведенное для нее Определение 10. ее конструктивно не характеризует.

Теорема 10.8 ( [1]). Пусть x Rn и A матрица размера (n m).

Среди всех векторов x, минимизирующих z Ax 2, то есть удовлетворяю щих уравнению z R(A), (z z ) R(A), A = z, x (10.9) или, что эквивалентно, системе нормальных уравнений AT A = AT z, век x тор x0, имеющий минимальную норму, является единственным вектором из R(AT ), то есть вектором вида x 0 = AT y, y Rn.

10 Теоретические основы Доказательство. Каждый вектор x, согласно Теореме 10.1 (или Теоре мам 10.2, 10.4), может быть разложен в сумму xr R(AT ), xn N (A), xr xn.

x = xr + xn, Поэтому (теорема Пифагора) 2 2 2 xr x = xr + xn.

Компонента xr сама является решением уравнения Ar = z, так как An = x x по определению нуль-пространства N (A). Все x отличаются от xr добавле нием всевозможных ортогональных компонент xn, причем x xr при единственном условии: xn = 0. Наименьшее значение x = xr требует равенства xn = 0, т. е. достигается при единственном значении xn = 0.

Тем самым доказано, что x0 = xr. Чтобы установить единственность век тора x0 = xr с минимальной нормой, предположим, что существуют два различных x1 и x2, оба из R(AT ), такие что для них выполняется (10.9):

r r A1 = z, A2 = z.

xr xr Тогда, очевидно, имеем A(1 x2 ) = 0, так что (1 x2) N (A) = xr r xr r = (R(AT )). Оказалось, что вектор (1 x2) ортогонален сам себе, т. е.

xr r (r xr ) (r xr ) = xr xr = 0, и тем самым x1 = x2.

1 2T 1 2 x x r r Замечание 10.4. Теорема 10.8 устанавливает, что при любом z Rn x0 может быть получен из любого вектора y Rn, найденного как решение совместной системы AT A(AT y) = AT z, по формуле x0 = AT y.

10.5 Отыскание псевдообратной матрицы Переформулируем Определение 10.3 псевдообратной матрицы.

Определение 10.6. Псевдообратная матрица A+ к матрице A есть такая матрица, что z (0, x0 = A+ z), для которого выполнены условия:

x проекция вектора z на R(A): z z R(A);

(1) A0 = z, где z x (2) x0 R(AT ).

Пример 10.1. [13] A = 0 1 0.

10.5 Отыскание псевдообратной матрицы Rn Rm R(AT ) R(A) A0 = z x x 0 = A+ z x z x 0 = A+ z A = z x 0 z x An = x N (A) A+ z = xn z Действие A N (AT ) + Действие A Рис. 10.2. Матрица A и ее псевдообратная A+ [13] x1 1 x2 = x1 0 + x2 1 = x1e1 + x2e2.

T R(A) = R(A ) = 0 0 R(A) = L(e1, e2 ).

R(AT ) = L(e1, e2 ).

0 N (A) = 0 = x3 0 ;

N (A) = L(e3);

N (A) R(AT ).

x3 z1 z 1 Проектируем z = z2 на R(A). Находим z = z2.

z3 100 x z 2 Решаем систему A = z. Имеем 0 1 0 x2 = z2 x = x 000 x z фиксированные, = z произвольный.

x 10 Теоретические основы z 3 Выбираем из x тот x0 = z2, который имеет минимальную норму.

1 0 +z2 1 = z1 e1 +z2 e2.

T Видно, что x0 R(A ), так как x0 = z 0 4 Находим A+ такую, что A+ z = x0:

z1 z1 A+ z2 = z2 A+ = 0 1 0.

= z3 0 Пример 10.2. [13] µ1 0 0 A = 0 µ2 0 0 ;

µ1 0, µ2 0.

0 0 R(A) = L(e1, e2) R3 = E(e1, e2, e3).

z 1 Проектируем z = z2 на R(A) = z3 = 0. Имеем z z1 1 z = z2 = z1 0 + z2 1 = z1 e1 + z2 e2 R(A).

0 0 x1 µ1 0 0 0 z x 2 Решаем систему A = z : 0 µ2 0 0 2 = z2 x = x x 0 0 00 x z1 /µ фиксированные, z2 /µ = x произвольные.

x z1 /µ z /µ 3 Выбираем из x тот x0 = 2 2, у которого x0 = min x.

0 x 10.5 Отыскание псевдообратной матрицы 4 Находим A+ такую, что A+ z = x0:

µ1 z1 /µ1 z1 0 µ1 z2 = z2 /µ2 A+ =.

A + 0 0 z 0 0 0 Пример 10.3. (Обобщающий вышеприведенные примеры 10.1 и 10.2.) D Рассмотрим класс матриц вида = = (m, n), где D = = diag (µ1, µ2,..., µr ). Имеем, на основании примеров 10.1 и 10.2, что всегда D1 + = = +(n, m).

Теорема 10.9 (О сингулярном разложении матрицы A = A(m, n)).

Для произвольной матрицы A = A(m, n) ранга r существуют две ортого нальные матрицы Q1 = Q1(m, m) и Q2 = Q2 (n, n) и положительные дей ствительные числа µ1 µ2... µr 0, такие что:

1. Справедливы равенства D A = Q1QT, = = (m, n), D = diag (µ1, µ2,..., µr ), (10.10) µ2 T причем = i, где i собственные числа матрицы A A.

i 2. Для псевдообратной матрицы A+ справедливо выражение D1 + + QT, + A = Q2 =.

Определение 10.7. Числа µi называются сингулярными числами матрицы A, и разложение (10.10) называется сингулярным разложением матрицы A.

Доказательство.

1. Рассмотрим матрицу AT A. Она симметрическая или эрмитова (в вещественная, то AT A комплексном случае). Если A симметри ческая, то есть она совпадает со своей транспонированной матрицей:

комплексная, то AA (AT A)T = AT A. Если A эрмитова, то есть она совпадает со своей сопряженно-транспонированной: (AA) = AA.

10 Теоретические основы Фундаментальное свойство таких матриц заключается в следующем.

Только эрмитовы матрицы обладают одновременно (подробнее см. ниже стр. 233):

вещественными неотрицательными собственными значениями, • ортонормированными собственными векторами.

• Имеем: матрица AT A (n n) эрмитова.

набор собственных векторов в Rn, Обозначим: {x1, x2,..., xn} {1, 2,..., n } соответствующие собственные значения.

Запишем AT Axi = i xi, xT xj = 1, i = j i, где i, j = 1, 2,..., n.

xT xj = 0, i = j i Умножим скалярно на xi:

xT (AT A)xi = i xT xi = i xi = i, i i i 0.

Axi = i = Пронумеруем i так, чтобы 1 2... r 0, а остальные i = 0, i = r + 1, r + 2,.., n. Это возможно, так как rank(AT A) =. rank A = r.

Вычислим µi = i для i = 1, 2,..., r. Заметим, что µi = i = 0 для i = r + 1, r + 2,..., n. Для µi, i = 1, 2,..., r снова запишем:

AT Axi = i xi xT (AT A)xi = i = µ2, = i i xT AT Axi xT AT Axi i i · = 1, = 1, Axi = 0.

µ2 µi µi i Обозначим yi = Axi/µi, i = 1, 2,..., r. Тогда xT AT Axj xT AT Axj xT j xj 1, i = j = 1, 2,..., r, i i =i T · yi yj = = = 0, i = j.

µi µj µi µj µi µj ортонормированы в Rm, так как yi Следовательно, {y1, y2,..., yr } Rm. Все yi линейные комбинации столбцов матрицы A: yi R(A).

Они могут быть дополнены в Rm до полного ортонормированного базиса:

{y1, y2,..., yr, yr+1,..., ym }.

Таким образом, имеем:

в Rm ортонормированный базис из векторов {y1, y2,..., ym }, • 10.5 Отыскание псевдообратной матрицы в Rn ортонормированную систему векторов {x1, x2,..., xn}.

• Соберем эти векторы в две матрицы:

Q1 = [y1, y2,..., ym ], Q2 = [x1, x2,..., xn].

a) Имеем для i = 1, 2,..., r:

yi µi = Axi, µi 0, Axi = 0. (10.11) б) Имеем для i = r + 1, r + 2,..., m:

Axi = i = 0 = Axi = 0.

Поэтому в записи yi µi = Axi следует считать µi = 0, i = r + 1, r + 2,..., m. (10.12) Это означает, что (10.11) и (10.12) равносильны записи:

D [y1, y2,..., ym ] = A [x1, x2,..., xn] Q1 Q где D = diag (µ1, µ2,..., µr ), то есть или Q1 QT = A, или = QT AQ2.

Q1 = AQ2, 2 Утверждение 1 теоремы доказано.

2. Умножение на ортогональную матрицу не изменяет евклидовой нормы вектора, поэтому имеем цепочку равенств:

= Q1QT xb = QT xQT b = yQT b = yc 2.

Axb 2 2 1 Введем новый вектор y = QT x = Q1x.

2 Для него y = x, так как QT ортогональная матрица.

Из приведенной цепочки равенств получаем следующий вывод: отыска ние нормального псевдорешения системы Ax = b эквивалентно отыска нию нормального псевдорешения системы y = c, где c = QT b. Имеем эти нормальные псевдорешения: y0 и x0. Они равны:

y0 = + c, x0 = A+b.

10 Теоретические основы В силу связи x и y имеем y0 = QT x 2 = x0 = Q2 y0.

Поэтому x 0 = Q2 + c = Q2 + QT b = A+ b.

любой вектор в Rm. Отсюда Но b A+ = Q2 + QT.

Пример 10.4. Дана матрица [13] A =.

Тогда AT A = 34 = 25. Поэтому единственный собственный вектор матрицы AT A есть: x1 = [1]. Это и есть матрица Q2, Q2 = [1].

Найдем 1 :

(AT A)x1 = 1 x1 = [25] [1] = 1 [1] = 1 = 25.

Найдем µ1 : µ1 = 1 = 25 = 5.

Найдем вектор y1 :

Ax1 1 3 3/ y1 = = 1 =.

4 4/ µ1 y1 есть первый столбец матрицы Q1 = [y1, y2]. Второй столбец y2 матрицы Q1 должен быть выбран так, чтобы быть в R2 ортогональным вектору y1 = 3/ =.

4/ y12 T В общем виде y2 =. Из условия ортогональности y1 y2 = 0 имеем y 3 y12 + y22 = 0.

5 T Кроме того, y2 должен быть ортонормирован, то есть y2 y2 = 1. Отсюда следует 2 y12 + y22 = 1.

10.5 Отыскание псевдообратной матрицы Из первого условия имеем y12 = y224/3. Подставляя значение y12 во второе условие, выводим y22:

y22(4/3)2 + y22 = 1 = y22[1 + (4/3)2] = 1 = 2 2 1 1 = y22 = = =.

1 + (4/3)2 1 + 16/9 Можно выбрать одно из двух значений:

(a) y22 = 3/5 либо (б) y22 = 3/5.

Отсюда, соответственно, (a) y12 = (3/5)(4/3) = 4/5, либо (б) y12 = (3/5)(4/3) = 4/5.

Следовательно, возможны два варианта:

Вариант 1 Вариант 3/5 4/5 3/5 4/ Q1 =, Q1 =.

4/5 3/ 4/5 3/ В варианте 1 имеем 3/5 4/5 3 9/5 + 16/5 = QT AQ2 = 1 = =.

4/5 3/5 12/5 + 12/ 4 В варианте 2 имеем 3/5 4/5 3 9/5 + 16/5 = QT AQ2 = 1 = =.



Pages:     | 1 |   ...   | 2 | 3 || 5 | 6 |   ...   | 8 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.