LINEAR ALGEBRA and its applications Gilbert Strong • Massachusetts Institute of Technology ACADEMIC PRESS NEW YORK SAN FRANCISCO LONDON 1976 Г. Стренг ЛИНЕЙНАЯ АЛГЕБРА И ЕЕ ПРИМЕНЕНИЯ Перевод с английского Ю. А. КУЗНЕЦОВА и Д. М. ФАГЕ под редакцией Г. И. МАРЧУКА ИЗДАТЕЛЬСТВО «МИР» МОСКВА 1980 УДК 512.8+518.5 Книга отличается от традиционных руководств по линейной алгебре тем, что материал излагается в тесной связи с много- численными приложениями. В виде отдельных глав представлены метод исключения Гаусса, ортогональные проекции, положительно определенные матрицы, линейное программирование и теория игр. Автор знаком советским читателям по переводу его (в соавторстве сДж. Фиксом) «Теории метода конечных элементов» (М.: Мир, 1977)- Книга, несомненно, окажется полезной математикам-приклад- никам различных специальностей; она заинтересует также и пре- подавателей, аспирантов и студентов университетов и втузов, пре- подающих или изучающих линейную алгебру и ее приложения. Редакция литературы по математическим наукам 1702030000 20203-031 041 (01)-80 31-1980 1976, by Academic Press, Inc. Перевод на русский язык, «Мир», 1980 От редактора перевода Традиционные курсы линейной алгебры, читаемые в высших учебных заведениях, и соответствующие учебные пособия, как правило, мало затрагивают прикладную сторону предмета. Но в то же время линейная алгебра служит основой всех методов вычислительной математики, являясь в этом смысле чисто при- кладной наукой. Предлагаемая вашему вниманию книга написана известным американским математиком Гильбертом Стренгом на основе кур- са лекций для студентов Массачусетского технологического института, который читался им с учетом именно этих обстоя- тельств, и это оказало существенное влияние как на стиль изложения материала, так и на его выбор. Например, в виде отдельных глав здесь представлены метод исключения Гаусса, положительно определенные матрицы и даже линейное програм- мирование, и в то же время жорданова форма матрицы и ли- нейные преобразования рассматриваются в виде кратких прило- жений. В книге рассматриваются также вопросы об ортогональ- ном проектировании векторов на подпространства и дается представление о методе конечных элементов, который в настоя- щее время становится основным средством приближенного реше- ния уравнений математической физики. Отдельная глава посвя- щена вычислениям с матрицами и, в частности, итерационным методам решения систем линейных алгебраических уравнений, играющим важную роль в вычислительной математике. Каждая глава еодержит большое число примеров и упражне- ний, которые также призваны способствовать развитию у чита- теля навыков в решении прикладных задач. От редактора перевода Написанная доступным языком, эта книга, несомненно, ока- жется полезной для широкого круга читателей: математиков^- прикладников, аспирантов и студентов многих специальностей университетов и втузов. Она заинтересует также преподавателей курсов линейной алгебры-как с точки зрения методологии, так и с точки зрения максимальной приближенности теории к при- ложениям. о Перевод глав 1, 2, 6, 7 выполнен Ю. А. Кузнецовым, глав 3, 4 5, 8 и приложений—Д. М. Фаге. Г. И. Марчук Предисловие Я считаю, что линейная алгебра преподается сейчас слиш- ком абстрактно. Конечно, это утверждение спорно и, быть мо- жет, слишком спорно, чтобы быть верным. Но я убежден, что настоящее руководство должно объяснять существо линейной алгебры и развивать математическое мышление читателей — ведь этот предмет столь же фундаментален, как математический анализ, столь же полезен и имеет такие же богатые приложе- ния. Кроме того, линейная алгебра доступнее анализа, и это обстоятельство слишком важно, чтобы им пренебрегать. Разумеется, нынешнее состояние дел с линейной алгеброй вполне объяснимо. Ее преподавание дает прекрасную возмож- ность иллюстрировать точность математических рассуждении и построения доказательств. Это достоинство я сознаю, ценю и надеюсь сохранить, и мне всегда было приятно читать лекции именно в таком стиле. Однако, когда я начал экспериментиро- вать в Массачусетском технологическом институте с различными вариантами курса, я обнаружил еще одно его достоинство: пре- подавание линейной алгебры не только позволяет иллюстриро- вать единство двух важнейших черт математики — абстрактности и приложимости, но и постоянно побуждает подчеркивать это единство. Так повелось, что большинство изучающих линейную алгебру вязнет в абстракциях и не доходит до приложений. И очень многие студенты, особенно нематематических отделений, вовсе не выбирают этот курс. Даже самые способные наши студенты при- обретают тенденцию к постижению абстракций, но остаются бес- помощными в вычислениях — например, они решают системы линейных уравнений по правилу Крамера, а собственные зна- чения понимают только как корни характеристических уравне- ний. В силу всего этого возникает сильное желание сделать преподавание нашего предмета более полезным и более доступным. 8 Предисловие ____________ Мы надеемся изложить курс линейной алгебры так, что- бы его изучение приобрело смысл для широких кругов студен- тов самых разных уровней. Это, конечно, не означает, что мы задумали написать своего рода поваренную книгу по алгебре — предмет заслуживает большего. Мы просто концентрируем вни- мание не на строгости изложения ради ее самой, а на сути понятий, всюду стараясь скорее объяснить, нежели доказать. Некоторые определения вводятся формально, но многие появ- ляются в процессе обсуждения. Точно так же строги и точны лишь некоторые, а не все доказательства. Разумеется, в каж- дом случае имеется строгая теория, которая лежит в основе изложения; она должна быть разъяснена и подкреплена при- мерами. При построении любого курса имеется специфическая труд- ность, которую нельзя отложить на более поздний срок: с че- го начать курс? Большинство студентов начинают его слушать, уже имея некоторые представления о линейных уравнениях. Тем не менее мы убеждены, что изучение линейной алгебры должно начинаться с основной задачи о решении системы п уравнений с п неизвестными, причем решаться эта система дол- жна простейшим и наиболее употребительным способом—мето- дом исключения Гаусса (а не по правилу Крамера!). К счас- тью, несмотря на простоту этого метода, имеется ряд момен- тов, которые являются центральными для его понимания и но- выми почти для каждого студента. Наиболее важно то, что ме- тод исключения эквивалентен матричному разложению: матрица коэффициентов разлагается в произведение треугольных матриц. Это является прекрасным введением к матричным обозначе- ниям и к правилу умножения матриц. Другая трудность состоит в правильном выборе темпа изло- жения. Если предполагать, что операции с матрицами уже зна- комы студенту, то материал первой главы нужно излагать не слишком медленно, поскольку следующая глава потребует от читателя значительных усилий. Ее цель состоит в том, чтобы объяснить смысл уравнения Ах=Ь глубже, чем позволяет метод исключения. Я считаю, что введение четырех основных подпро- странств—пространства столбцов матрицы А, пространства ее строк и их ортогональных дополнений (двух нуль-пространств)— дает эффективный способ построения примеров линейной зави- симости и независимости, а также хорошо иллюстрирует идеи базиса, размерности и ранга. Кроме того, с помощью понятия ортогональности обычная геометрия трехмерного пространства естественным образом распространяется на п-мерный случай. И, разумеется, эти четыре основных подпространства служат клю- чом к пониманию уравнения АУ.=Ь. Главы 1—5 являются сердцевиной курса линейной алгебры. Предисловие В них содержится большое число примеров из физики, техники, теории вероятностей и статистики, экономики и биологии. (Здесь рассматривается, в частности, геометрия молекулы метана и даже намечается способ применения факторного анализа в психологии, который мои коллеги по МТИ отказываются излагать студентам!) В то же время ясно, что наша книга не претендует на описа- ние всех возможных применений матриц. Это—всего лишь на- чальный курс линейной алгебры, и наша цель состоит не в из- ложении таких применений, а в подготовке к ним. И такая под- готовка может быть успешной лишь в том случае, если удастся добиться хорошего понимания теории. Теория в книге представлена достаточно подробно. После изу- чения в гл. 2 векторных пространств в гл. 3 мы изучаем проекции и скалярные произведения, в гл. 4—определители и в гл. 5—собст- венные значения. Я считаю, что инженеры и другие лица, интересу- ющиеся приложениями, должны обратить особое внимание на гл.5, где делается упор на использование диагонализации (включая спектральную теорему); жорданову форму матриц мы отнесли в приложение. Каждая глава оканчивается набором обзорных упраж- нений и построена таким образом, что последний параграф является дополнительным; это относится также и к § 3.4 о псевдообратных матрицах. Для семестровых или полусеместровых курсов преподава- тель должен сделать выбор между положительно определенными матрицами (из гл. 6) или линейными программами (из гл. 8) в зависимости от интересов слушателей; я надеюсь, что § 8.1 и 8.5 дают краткое, но полезное введение в линейное программирова- ние и теорию игр. Заметим, что книга может послужить основой для трех раз- личных курсов. Первый из них—вычислительная линейная алгеб- ра—должен включать материал всей гл. 1, наиболее существенные факты из гл. 2—6 и, наконец, гл. 7 о вычислениях и §8.2 о симп- лекс-методе, Второй курс—линейная алгебра для статистиков; в нем должны быть полнее изучены гл. 3 и 6. Третья возможность — рассматривать, как это делают экономисты, неравенства наряду с уравнениями, и тогда нужно возможно скорее перейти от уравне- ния Ах=Ь к линейному программированию и двойственности. Мы надеемся на благосклонное внимание математиков, которые просто обучают основам линейной алгебры. Это—истинная цель нашей книги и хочется думать, что математиков не отпугнут мно- гочисленные «подсчеты числа операций» и другие замечания вычис- лительного характера, особенно в гл. 1. С практической точки зрения важность таких замечаний очевидна. Но они имеют и серьезную теоретическую цель—способствовать более детальному изучению процесса исключения посредством фактического под- счета числа шагов. Обычно я прошу аудиторию на первой или второй лекции проделать такой подсчет, и результаты оказывают- 10 Предисловие ся совершенно непредсказуемыми. Однако нет нужды обсуждать этот или другие вычислительно-ориентированные вопросы в ауди- тории; любой учебник должен и дополнять, и суммировать мате- риал лекций. Итак, необходима книга, которая позволит читателям успешно овладеть приложениями и в то же время научит их математике, лежащей в основе этих приложений. Именно такую книгу я и попытался написать. За помощь в ее написании мне хочется особенно поблагода- рить Тома Слобко, который постоянно подбадривал меня, Урсулу, которая с такой милой добротой перепечатывала весь материал, и самое для меня драгоценное—мою семью. Есть еще и более ранний долг, которого я никогда не смогу оплатить,—это долг перед моими родителями. Я посвящаю им свою книгу в надежде, что они поймут, как много они сделали для меня. Спасибо им обоим. Гильберт Стренг Глава 1 МЕТОД ИСКЛЮЧЕНИЯ ГАУССА § 1.1. ВВЕДЕНИЕ Решение систем линейных уравнений—это центральная зада- ча линейной алгебры. Наиболее важным и в то же время наиболее простым является случай, когда число неизвестных равно числу уравнений. Поэтому мы начнем с задачи, когда задано п уравнений с п неизвестными. В курсе высшей алгебры рассматриваются два в каком-то смысле конкурирующих способа решения систем уравнений. Первым является метод исключения- Сначала некоторые кратные первого уравнения системы вычитаются из других уравнений, с тем чтобы устранить из этих уравнений первое неизвестное. В результате возникает меньшая система, состоящая из п—1 уравнений с п—1 неизвестными. Процесс повторяется, пока не останется только одно уравнение с одним неизвестным, которое можно решить непосредственно. Теперь нетрудно произвести обратный ход и определить все другие неизвестные в обратном порядке. Соответствующий пример мы скоро приведем. Второй, более сложный, путь дает идея определителя. Существует точная формула, называемая правилом Крамера, которая позволяет вычислить решение (значения неизвестных) как отношение двух определителей порядка п. Из примеров, приводимых в учебниках (человеческого терпения хватает, как правило, на случаи п==3 или п==4, но не более), не всегда видно, который путь лучше. На практике более сложные формулы, содержащие определите- ли, оказываются для вычислителя бедствием, и потому для реше- ния больших систем уравнений постоянно используются алго- ритмы исключения. Таким образом, наша первая цель—понять алгоритм, который обычно называется методом исключения Гаусса. Этот алгоритм обманчиво прост и, вероятно, в некоторых частных случаях уже хорошо знаком читателю. Однако имеют- ся четыре аспекта, которые значительно глубже, чем простая техника исключения, и которые (вместе с самим алгоритмом) мы хотим обсудить в этой главе. Перечислим эти аспекты. 446 Указатель Алгебраическая кратность 223 Алгебраическое дополнение 196, 197 Алгоритм Кроута 37 Альтернатива Фредгольма 111 Альтернативная теорема 384, 386 Анализ основных компонент 261, 292 Базис 82 Базисное решение 364 Базисные переменные 71, 364 Бесконечномерное пространство 159, 408 Блочное умножение матриц 205 Блочный степенной метод 333 Бридж 404 Булева алгебра 186 Буняковский 130 Вандермонд 99, 191 Ведущий элемент 13, 34, 50, 56, 184, 289 — — в симплекс-методе 366 — — формула 204, 205 Вектор 18 — невязки 136 Векторное пространство 62—64 Вес 63, 139, 175 Вещественное пространство 65 Взаимно однозначное преобразова- ние 97, 409 Взвешенная длина 176, 178 Взвешенное скалярное произведение 178 — среднее значение 175 Взвешенные наименьшие квадраты 175 Волновое уравнение 250 Выбор портфеля ценных бумаг 359 Вырожденный угол 366 Галуа 218 Гармоники (гармонические составляю- щие) 216, 230, 243, 249 Гаусс 11, 13, 31, 43, 48, 74, 206 Гейзенберг 269 Гейл 386, 403 Гены 235 Геометрическая кратность 223 Гершгорин 351 Гессе 285 Гивенс 301 Гильберт 51, 56, 159, 161, 269, 408, 409 Гильбертово пространство 159, 269, 408, 409 Главная подматрица 296 Голуб 350 Грузовые перевозки 234 Гурвиц 246 Данциг 361 Двойственная задача 357, 375 Двухдиагональная матрица 57 Двухточечная краевая задача 53 Дефект 89, 120 Дефектная матрица 216, 223, 275 Диагонализация 221, 258, 272, 303, 314, 415 Диагональная матрица 37, 170 Диагональное преобладание 352 Дилемма заключенного 405 Динамическое программирование 394 Дисперсия 146 Указатель 447 Дифференциальное уравнение 52, 211, 239, 421 Диффузия 242, 244, 245 Длина 101, 159, 254, 265 — взвешенная 76, 178 Допустимое множество 355, 360, 376, Допустимый вектор 355, 377, 379 Достижимый вектор 384 Дуги сети 388 Единичная матрица 29 Единичный вектор 103 — — в направлении оси координат 78 Единственность решения 95 Жордан 45, 75, 275, 416, 419 Жорданова форма 275, 416, 419 Задача об оптимальном назначении 394 — о бракосочетании 394 — — диете 357, 376 • — — коммивояжере 394 — — максимальном потоке 388 — — перевозках 359, 395 — — простом назначении 392 Закон ассоциативности 27 — дистрибутивности 28 — инерции 298 — Кирхгофа 111 — Ньютона 247, 301 — Ома 112 — Сильвестра 298 Замена базиса 414 — переменных 244, 268 Зацикливание 366 Зейдель 345 Значение программы 355 Идемпотентная матрица 140 Изоморфизм 117 Исключение с частичным выбором ве- дущего элемента 51 Исправленный симплекс-метод 372 Исходная задача 357, 374 Итеративное уточнение 352 Итерационные методы 322, 343 Калифорния 22, 232, 333 Квадратичная форма 281, 283, 285 Квадратный корень 227, 291 Квантовая механика 225, 269 Кирхгоф 111 Коммутирование матриц 29, 133, 225 — — контрпример 28 Комплексное число 216, 251 Комплексно-сопряженное число 252 Комплексный вектор 253, 267 Конечно-разностная матрица 59, 191, 198, 319 Консервативная система 246 Контур 111 Конус 384, 387 Корреляционная матрица 261 Косинус 128, 130, 161 Кососимметрическая матрица 190, 401 Косоэрмитова матрица 263, 264 Коши 130 Коэффициент корреляции 177 — регрессии 175 Коэффициенты влияния 184 Краевая задача 53 Крамер 185, 201 Критерий останова 368, 381 Кроут 37 Кун 379, 403 Лагранж 378 Левая обратная матрица 44, 94, 138< 411 Левое нуль-пространство 92 Левый нуль-вектор 92 Лежандр 162, 164 Лемма Шура 270 Ленбергер 373 Ленточная матрица 52, 58 Леонтьев 238, 239 Линейная зависимость 77 — комбинация 22, 63, 77 — независимость 77, 90, 224 — оболочка 81 Линейное преобразование 97, 407, 410 — программирование 353 Линейность 23, 185, 407 Линейные неравенства 353 Ляпунов 246 Максимум 283 Марковский процесс 232, 235, 244, . 245 Массы 249, 301, 315 Масштабирование 51 Матрица 19 — Вандермонда 99 — весов 178 Указатель - вырожденная 40, 187 - Гессе 285 - Гильберта 51, 56, 161 - дефектная 216, 223, 275 - единичная 29 - Жордана 275, 417 - «затраты — выпуск» Леонтьева 238 - идемпотентная 140 - инцидентности 112, 389 - квадратный корень 227, 291 - ковариацин 177, 179 - конечных разностей 59, 191, 198, 319 - корреляционная 251 - кососимметрическая 190, 401 - косоэрмитова 263, 264 - коэффициентов 19 - ленточная 52, 58 - Мура — Пенроуза 165 - невырожденная 41, 98 - неопределенная 295 - неотрицательная 232, 237, 238 - нижняя треугольная 31 - нормальная 32, 44, 94 - обратимая 44, 188 ~ обратная 32, 44, 94 - ортогональная 151, 258, 329 - ортонормированная 151 - отражения 141 - отрицательно определенная 236 - перестановки 40, 43, 70, 152 - плохо обусловленная 48, 324 - положительно определенная 178, 285, 287, 331 - полуопределенная 295 - потребление .237 - присоединенная 201 - проектирования 139, 415 - псевдообратная 110, 165 - ранга один 93 - симметрическая 54, 132 - с кратными собственными значени- ями 260, 268, 272, 417 - — различными собственными зна- чениями 222, 224, 260, 272 - ступенчатая форма 69, 76 - транспонированная 55, 131 - трапецеидальная 65 - треугольная 31, 187, 270 - трехдиагональная 54, 336, 341 - унитарная 258, 264, 265 - Хессенберга 118, 336, 341 - хорошо обусловленная 48, 324 - элементарная 31 - эрмитова 256, 272 - эрмитовая к А 255 — эрмитово сопряженная 255 Метан 134 Метод взвешенных наименьших квад- ратов 176, 178 — Гаусса — Зейделя 345, 351 — Гивенса 301 — исключения Гаусса 11, 13, 31, 43, 74, 206 — — — с полным выбором ведущего элемента 50 — — — — частичным выбором ве- дущего элемента 50, 51, 324 — — Гаусса — Жордана 45, 75 — конечных разностей 53 — — элементов 309, 315, 316 — наименьших квадратов 126, 135, 137, 166, 174, 306 — переменных направлений 350 — последовательной верхней релак- сации 346 — сопряженных градиентов 351 — Якоби 336, 344, 351 Минимум 279, 282 Минор 196 Мнимое число 226, 251, 263 Многомерный анализ 280 Многочлены 98, 407 — Лежандра 162, 164 Множители 33 — Лагранжа 378 Множитель, характеризующий схо- димость 333, 334 Модуль 253 Молер 48 Мур 165, 182 Начальная задача 211 Невырожденность 68, 98, 122 Недоопределенная система 68 Нейман 48, 236, 269, 402, 403 Нейтральная устойчивость 211, 235, 245 Нелинейная задача о наименьших квадратах 145 Нелинейное убывание 236 Ненулевое решение 72 Необратимость во времени 244 Неопределенная квадратичная форма 283 — матрица 295 Неотрицательная матрица 232, 237, 238 Неотрицательное решение 384 Неравенство Коши—Шварца—Буня- ковского 130 — треугольника 133 Указатель 449 — Шварца 130, 133, 159 Несовместная система 68, 126, loo Нетривиальная комбинация 77 Неустойчивость 211, 235, 245 Нижняя треугольная матрица 31 Нобл 48 Норма 324, 328, 330 Нормальная матрица 274, 2" Нормальные уравнения 137, 330 Нулевая длина 178 — строка 186 Нулевой ведущий элемент 14, 39, 9й, 206 — вектор 64, 65 — определитель 182 Нуль-пространство bb, t^, ов, luo, 419 Ортонормированные векторы 103, 147, 155 — собственные векторы 258, 274 Оси эллипсоида 293, 311 Основная теорема линейной алгебры 92, 108 Основные подпространства 86, 119, Отношение Релея 307, 309, 312, 320, 330, 334 Отображение «на» 97, 409 Отрицательно определенная квадра- тичная форма 283 — — матрица 236 — полуопределенная квадратичная форма 283 Ошибка 134, 324, 325 • - округления 12, 47, 162, 227, 229 Обобщенная задача на собственные значения 301, 304 — обратная матрица 165 Обобщенный собственный вектор 241, 417 Образ 89 Обратимая матрица 44, 188 Обратимое отображение 97 Обратная матрица 32, 44, 94 — — к произведению 44 — — — транспонированной 133 — — Мура — Пенроуза 165 — — формула 20 — подстановка 14, 35 Обратный степенной метод 333, 334 Обусловленность 48 Общее решение 74 Объединение 115 Ограничения 360, 363, 379 Однородная система 72 Определитель 182 — Вандермонда 191 — матрицы перестановки 189, 191, 194, 206 — свойства 185 — формула 191, 194, 197, 218 — Якоби 183, 207 Оптимальный вектор 355, 377, 379 Ортогонализация Грамма — Шмидта 127, 154, 162, 203, 309, 338 Ортогональная матрица 151, 258, 329 Ортогональное дополнение 107 Ортогональные векторы 101, 102 — подпространства 104 — собственные векторы 257, 263, 265, 274 Ортогональный базис 146 Ортонормированная матрица 151 Параболоид 305 Пенроуз 165, 174 Переменная невязки 357, 363 Переопределенная система 126, 143 Пересечение 114 Перестановка 193, 209 — строк 26, 36, 56, 186 Пифагор 100, 153 Плавающая точка 32 Планирование производства 359 Плохо обусловленная матрица 48, 324 Площадь 207 Погрешность (ошибка) 324, 325 Подгонка данных 143, 163 Подматрица 121 Подобные матрицы 268 Подпространство 64 Подсчет числа действий 15, 36, 46, 58, 341 Покер 405 Полный выбор ведущего элемента 50 — квадрат 282, 289 Положительно определенная квадра- тичная форма 281, 285 — — матрица 178, 285, 287, 331 — полуопределеиная квадратичная форма 283 Полу определенна я матрица 295 Полупространство 353 Последовательность Фибоначчи 128, 135 Почти периодическое движение 249 Правая обратная матрица 44, 94 Правило Крамера 185, 201 Предельная стоимость 382 Представление в виде матрицы 410 Преобразование конгруэнтности 298 450 Указатель — подобия 268, 277, 414, 420 — Хаусхолдера 153, 336, 339 Принцип максимина 311 — минимума 304 — неопределенности Гейзенберга 269 — Релея 307 — Релея — Ритца 315 Присоединенная матрица 201 Присоединенный вектор 418 Проекция 109, 126, 136, 137, 148, 273 Произведение ведущих элементов 57, 184, 191 — матриц 25, 119, 413 — определителей 188 — псевдообратных матриц 176 Пропускная способность разреза 390 Пространство 64 — столбцов 64, 89 — строк 81, 87, 105 Псевдообратная матрица 110, 165 — — произведения 176 — — формула 170, 173 Разбиение на блоки 205 Разделяющая гиперплоскость 385, 386 Разложение определителя на алгеб- раические дополнения 196 — Холецкого 291, 331 — LDU 37, 38, 55 — UJ_ 12, 34, 70 — LU 120, 172 — QR 157, 338 — QiSQ? 170, 339 Размерность 84 — основных подпространств 92 Разностное уравнение 53, 227 Разрез сети 390 Разрешимость системы 63 Райнш 323 Ранг 75, 77 — подматрицы 121 — произведения 120 Расстояние 129 Раус 246 Ребро 361, 362 Регрессионный анализ 126, 260 Релаксационный множитель 346 Релей 307, 315 Ритц 315 Ряды Фурье 160, 164 Сверхубывание 243 Свободные переменные 71, 88, 364 — члены 18 Свойства определителя 185 Сдвиг 334, 340 Седловая точка 283, 309, 397 Сетевые задачи 388 — модели 388 Сильвестр 298 Симметрическая матрица 54, 132 Симметрическое исключение 297 Симплекс-метод 360, 361, 372, 379 Сингулярное разложение 170, 330, 339 Сингулярные числа 170, 330 Скалярное произведение 20, 25, 102 — — взвешенное 178 — — в комплексном случае 254, 265 — — функций 160 Слабая двойственность 377 След 218, Смешанная стратегия 396, 399 Собственное подпространство 214 Собственные значения 182, 213, 263, 267, 268 — — кратные 260, 272, 417 — — различные 222, 224, 260, 272 — функции 243 Собственный вектор 213, 230, 257 — — обобщенный 241, 417 Сопрягающий член 149 Сопряженно транспонированная мат- рица 255 Спектральная теорема 258, 271 Спектральный радиус 344 Среднее арифметическое 133, 150 — геометрическое 133 — значение 146 Средняя ошибка 134, 142, 143 Стандартный базис 147 Стационарная точка 280 Стационарное состояние 233, 244 Степенные методы 323, 332, 334 Ступенчатая форма матрицы 63, 76 Стюарт 342 Сумма подпространств 115, 118 Существование решения 95 Таблица для симплекс-метода 367 Такер 379 Теневые цены 382 Теорема двойственности 376 — Кэли — Гамильтона 271 — о кругах Гершгорина 351 — — максимальной точке и минималь- ном разрезе 390 — — минимаксе 402 — — равновесии 379 — — разделяющей гиперплоскости 386 Теория игр 395 Указатель 451 Торп 404 Транспонированная матрица 55, 131 — — определитель 189 — — к обратной 133 — — — произведению 131 Трапецеидальная матрица 69 Треугольная матрица 31, 187, 270 Трехдиагональная матрица 54, 336, 341 Угол 127, 265, 356, 361 Узлы сети 388 Уилкинсон 48, 323, 329, 342 Умножение вектора на матрицу 19, 20 — матриц 25 Унитарная матрица 258, 264, 265 Уравнение теплопроводности 243, 244 Условие оптимальности 368 Условия Куна — Такера 379 — совместности невязок 379, 382, 398 Устойчивость 212, 235, 245, 271 Факторный анализ 260, 261 Фибоначчи 228, 235 Фикс 320 Филиппов 276, 418 Формула для ведущего элемента 204, 205 — — обратной матрицы 20 — — определителя 191, 194, 197, 218 — — псевдообратной матрицы 170, 173 Форсайт 48 Фредгольм 111 Функциональное пространство 158, 159 Функция стоимости 355, 360, 368 Фурье 160, 164 Характеристический многочлен 213, 217, 269 Характеристическое уравнение 213, 217 Хаусхолдер 153, 336, 339 Хессенберг 118, 336, 341 Хокней 350 Холецкий 291, 300, 331 Хорошо обусловленная матрица 48, 324 Целевая функция 355 Цена игры 397, 402 Цепочка векторов 418 Частичный выбор ведущего элемента 50, 324 Частное решение 74 Частота 215, 248 Четная перестановка 206 Численное интегрирование 99 Число обусловленности 323, 325, 328 Шахматы 404, 406 Шварц 130, 133, 159 Ширина ленты 58 Шур 270 Экономика 236, 238, 263, 376 Экспонента от матрицы 239, 240, 244, 422 Экспоненциальное решение 215, 239, 240, 244 Элементарное преобразование 186 Элементарные матрицы 31 Эллипс 293 Эллипсоид 294, 304, 311 Эпидемия 234 Эрмитова матрица 256, 272 Эрмитово сопряженная матрица 255 Ядро 89 Якоби 336, 344, 351 Якобиан 183, 207 Янг 348 «Ящичные» ограничения 389 ШУ-разложение 37, 38, 55 L [/-разложение 12, 34, 70 1,[7-разложение 120, 172 Ой-алгоритм (метод) 323, 332, 340, 341 Q^-разложение 157, 338 <Э120?-разложение 170, 339 Оглавление От редактора перевода ....................... 5 Предисловие ............................ 7 Глава 1. МЕТОД ИСКЛЮЧЕНИЯ ГАУССА ............. 11 § 1.1. Введение ......................... 11 § 1.2. Пример применения метода исключения Гаусса ....... 13 § 1.3. Матричные обозначения и умножение матриц ........ 17 § 1.4. Эквивалентность метода исключения Гаусса и разложения на треугольные матрицы ................... 30 § 1.5. Перестановки строк, обращения и ошибки округления ... 39 § 1.6. Ленточные матрицы, симметрические матрицы и их применения 52 Обзорные упражнения ................... 60 Глава 2. ТЕОРИЯ СИСТЕМ ЛИНЕЙНЫХ УРАВНЕНИЙ ....... 62 § 2.1. Векторные пространства и подпространства ......... 62 § 2.2. Решение т уравнений с п неизвестными .......... 68 § 2.3. Линейная независимость, базис и размерность ....... 77 § 2.4. Четыре основных подпространства ............. 86 § 2.5, Ортогональность векторов и подпространств ......... 100 § 2.6. Пары подпространств и произведения матриц ........ 113 Обзорные упражнения ................... 123 Глава 3. ОРТОГОНАЛЬНЫЕ ПРОЕКЦИИ И МЕТОД НАИМЕНЬШИХ КВАДРАТОВ ....................... 125 § 3,1. Скалярные произведения и транспонирование ........ 125 § 3.2. Проекции на подпространства и аппроксимации по методу на- именьших квадратов .................... 134 Оглавление 453 <; 3.3. Ортогональные базисы, ортогональные матрицы и ортогонали- зация Грама—Шмидта ................... 146 § 3.4. Псевдообращение и сингулярное разложение ........ 164 § 3.5. Взвешенные наименьшие квадраты ............. 174 Обзорные упражнения ................... 180 Глава 4. ОПРЕДЕЛИТЕЛИ ..................... 182 § 4.1. Введение ......................... 182 § 4.2. Свойства определителя ................... 185 § 4.3. Формулы для определителя ................ 191 § 4.4. Применения определителей ................. 200 Обзорные упражнения ................... 208 Глава 5. СОБСТВЕННЫЕ ЗНАЧЕНИЯ И СОБСТВЕННЫЕ ВЕКТОРЫ 210 § 5.1. Введение ......................... 210 § 5.2. Диагональная форма матрицы ................ 221 § 5.3. Разностные уравнения и степени Л* ............ 227 § 5.4. Дифференциальные уравнения и экспонента е^ ....... 239 § 5.5. Комплексный случай: эрмитовы и унитарные матрицы ... 251 § 5,6. Преобразования подобия и треугольные формы ....... 267 Обзорные упражнения ................... 277 Глава 6. ПОЛОЖИТЕЛЬНО ОПРЕДЕЛЕННЫЕ МАТРИЦЫ ..... 279 § 6.1. Максимумы, минимумы и седловые точки .......... 279 § 6.2. Критерии положительной определенности .......... 286 § 6.3. Полуопределенные и неопределенные магрицы. Обобщенная задача на собственные значения Ах=\Вх ......... 295 § 6.4. Принципы минимума и отношение Релея .......... 304 § 6.5. Принцип Релея—Ритца и метод конечных элементов .... 315 Глава 7. ВЫЧИСЛЕНИЯ С МАТРИЦАМИ ............. 322 § 7.1. Введение ......................... 322 § 7.2. Норма и число обусловленности матрицы ......... 324 § 7.3. Вычисление собственных значений ............. 332 § 7.4. Итерационные методы решения системы Ах=Ь ....... 343 Глава 8. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ И ТЕОРИЯ ИГР . . 353 § 8.1. Линейные неравенства ................... 35S § 8.2. Симплекс-метод ...........,..,,.,.,-. ЭТО 454 Оглавление § 8.3. Теория двойственности ................... 374 § 8.4. Сетевые модели ...................... 388 § 8.5. Теория игр и георема о минимаксе ............ 395 Приложение А. ЛИНЕЙНЫЕ ПРЕОБРАЗОВАНИЯ, МАТРИЦЫ И ЗАМЕНЫ БАЗИСОВ ................ 407 Приложение В. ЖОРДАНОВА ФОРМА МАТРИЦЫ ......... 416 Список литературы ......................... 423 Решения .............................. 424 Указатель ............................. 446