Фаддеев, Фаддеева - Вычислительные методы линейной алгебры

ДК. Фаддеев, В.Н.Фаддеева ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ ЛИНЕЙНОЙ АЛГЕБРЫ ОГЛАВЛЕНИЕ Предисловие Глава 1. Основные сведения из линейной алгебры 8 1. Матрицы 8 2. Матрицы специального вида 8 3. Аксиомы линейного пространства 8 4. Базис и координаты 8 5. Подпространства 8 6. Линейные операторы 8 7. Каноническая форма Жордана 8 8. Строение инвариантных подпространств 8 9. Ортогональность векторов и подпространств 8 10. Линейные операторы в унитарном пространстве и эвклидовом пространстве 8 11.

Самосопряженный оператор 8 12. Квадратичные формы 8 13. Понятие предела в линейной алгебре 8 14. Градиент функционала Глава П. Точные методы решения систем линейных уравнеивй 8 15. Обусловленность матриц 8 16. Метод Гаусса 8 17. Вычисление определителей 8 18. Компактные схемы для решения неоднородной линейной системы 8 19. Связь метода Гаусса с разложением матрицы на множители 8 20. Метод квадратных корней 9 21. Обращение матрицы 8 22.

Задача исключения 8 23. Исправление элементов обратной матрицы 8 24, Обращение матрицы при помощи разбиения на клетки 8 25. Метод окаймления 8 26. Эскалаторный метод 8 27. Метод Перселла 8 28. Метод пополнения для обращения матрицы Глава ПЬ Итерационные методы решения Систем линейных уравнений 8 29. Принципы построения итерационных процессов 8 ЗО.Метод последовательных приближений 8 31. Подготовка системы линейных уравнений к виду, удобному для применения метода последовательных приближений.

Метод простой итерации 8 32. Одношаговый циклический процесс б 7 7 33 41 45 50 58 71 85 87 94 99 111 117 134 137 138 147 157 160 162 165 168 172 182 184 187 192 195 198 204 204 207 214 220 8 33. Метод П. А. Некрасова 8 34. Методы полной релаксации з 35. Неполная релаксация 8 36. Исследование итерационных методов для систем с квазитрехдиагональными матрицами 8 37. Теорема сходимости 8 38. Управление релаксацией 8 39. Релаксация по длине вектора невязки 8 40. Групповая релаксация Глава 1У.

Полная проблема собственных значений 8 41. Устойчивость проблемы собственных значений 8 42. Метод А. Н. Крылова з 43. Определение собственных векторов по методу А. Н. Крылова 8 44. Метод Хессенберга З 45. Метод Самуэльсона 8 46. Метод А.

М. Данилевского 8 47. Метод Леверье и видоизменение Д. К. Фаддеева 8 48. Эскалаторный метод 8 49. Метод интерполяции 8 50. Метод ортогонализации последовательных итераций з 51. Преобразование симметричной матрицы к трехдиагональному виду посредством вращений 8 52. Уточнение полной проблемы собственных значений Глава У.

Частичная проблема собственных значений 8 53. Определение наибольшего по модулю собственного значения матрицы при помощи последовательных итераций 8 54. Ускорение сходимости степенного метода 9 55. Модификации степенного метода 9 56. Применение степенного методак отысканию нескольких собственных значений 8 57. Ступенчатый степенной метод 8 58.Метод 2.-разности 8 59. Метод исчерпывання 8 60. Метод понижения 8 61.

Координатная релаксация з 62. Уточнение отдельного собственного значения н принадлежащего ему собственного вектора Глава 'Л. Метод минимальных итераций и другие методы, основаннь на идее ортогопализации з 63. Метод минимальных итераций 8 64. Биоргогональный алгорифм 8 65.

Метод А-минимальных итераций 8 66. А-бнортогональный алгорифм 226 230 232 237 244 248 253 254 257 259 263 271 273 280 285 295 300 308 314 317 324 328 329 346 352 355 358 367 370 375 378 386 392 392 404 416 425 ора ем 9 67. Двучленные формулы метода минимальных итераций и биортогонального алгорифма 9 68. Методы сопряженных направлений и их общие свойства 8 69. Некоторые методы сопряженных направлений Глава УП.

Градиентные итерационные методы 8 70. Метод наискорейшего спуска для решения линейных систем 8 71. Градиентный метод с минимальными невязками 8 72. Градиентные методы с неполной релаксацией 8 73. х-шаговые градиентные методы наискорейшего спуска 8 74. Определение алгебраически наибольшего собственного значения симметричной матрицы и принадлежащего ему собственного вект градиентными методами ~ 75. Решение частичной проблемы собственных значений с помощью полиномов Ланцоша з 76. к-шаговый метод наискорейшего спуска Глава У1П. Итерационные методы дли решения полной проблемы собственных значений 8 77.

Алгорифм деления и вычитания 8 78. Треугольный степенной метод 8 79. 1.К-алгорифм 8 80. АР-алгорифм 8 81. Итерационные процессы, основанные на применении вращений 8 82. Решение полной проблемы собственных значений при помощи спектрального анализа последовательных итераций Глава 1Х. Универсальные алгорифмы 8 83. Общая идея подавления компонент 8 84. Прием Л. А.

Люстерника для ускорения сходимости метода последовательных приближений при решении системы линейных уравнений 8 85. Подавление компонент при помощи полиномов низших степеней 8 86. Различные формы проведения универсальных алгорифмов 8 87. Универсальный алгорифм, наилучший в смысле первого критерия 8 88. Универсальный алгорифм, наилучший в смысле второго критерия 8 89. Прием А. А. Абрамова для ускорения сходимости метода последовательных приближений при реп|енин систем линейных уравнений 8 90.

ВТ-процессы 8 91. Общие трехчленные итерационные процессы в 92. Универсальный ангорифм Ланцоша 8 93. Универсальные алгорифмы, наилучшие в среднем 8 94. Метод подавления компонент в комплексной области 8 95. Применение конформного отображения к решению линейных сист 8 96. Примеры з-универсальных алгорифмов 427 433 437 455 456 465 466 472 480 494 498 508 508 524 530 533 536 547 553 554 557 559 563 567 570 572 574 577 582 586 589 591 599 8 97. Метод конформного отображения в применении к неподготовленной системе 8 98. Применение идеи подавления компонент к решению частичной проблемы собственных значений ~ 99. Применение конформного отображения к решению частичной проблемы собственных значений Заключение Дополнение Литература Дополнительная литература 603 609 610 612 615 617 654 ПРЕДИСЛОВИЕ Настоящая книга посвящена изложению вычислительных методов для решения основных задач линейной алгебры.

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

ортогональность понимается в линейно-алгебраическом смысле. В книге почти не затрагивается важный вопрос о влиянии ошибок округления на результат вычислений. Первая глава книги носит вводный характер. Остальные восемь глав посвящены изложению вычислительных методов. Материал этих глав частично был освещен в книге В. Н. Фаддеевой, вышедшей в 1950 г. под тем же названием.

В конце книги приложены библиография по вычислительным методам линейной алгебры и вопросам оценки и распределения собственных вцачений матрицы. При ее составлении существенную помощь оказали авторам И. А. Лифшиц и Р. С. Александрозэ. Авторы приносят им свою благодарность. Рукопись книги была прочитана В. Н. Кублановской, сделавшей ряд ценных замечаний. Авторы приносят ей глубокую благодарность. Авторы благодарят также редактора книги Г. П. Акилова 'и всех своих товарищей, проявивших интерес к их работе.

ГЛАВА 1 ОСНОВНЫЕ СВЕДЕНИЯ ИЗ ЛИНЕЙНОЙ АЛГЕБРЫ $ 1. Матрицы 1. Определения. Прямоугольной матри цен называешься совокупность чисел, вообще говоря, комплексных, расположенных в виде прямоугольной таблицы, содержащей и строк и ги столбцов. Такая матрица записывается в виде: ан аы ... аьи ам ам .. аз~ а„, аьг,. а„~ или, сокращенно, в виде: А=(ао), 1=-1, 2, ..., и; у=-1, 2, ..., иг. Две матрицы назывзются р а в н ы м и, если равны нх соответствующие элементы. Матрица, состоящая из одной строки, называется просто ст р ок о й; матрица, состоящая из одного столбца, — с т о л б ц о м; матрица А.=(а), состоящая из одного числа, отождествляется с этим числом.

Если число и строк матрицы равно числу ее столбцов„то матрица называется к в а д р а т н о й, В этом случае число и называется п о р я дк о м матрицы. Среди квадратных матриц важную роль играют так называемые диагональные матрицы, т. е. матрицы, у которых отличны от нуля лишь элементы, стоящие вдоль диагонали. Диагональные матрицы обозначаются [а,, а, ..., а„], так что а, О ... О О а,...О (2) [ао а, ..., а„[ = О О ...а„ основныв сведения из линейной алгвзвы (гл.

! Если зсе числа а; при этом равны между собой, матрица называется скалярной: а 6... О О а...О (3) О О ... а и в случае, если в= 1,— единичной: 1 О ... О . О 1 ... О (4) = (еы), О О ... 1 где 3О так называемый символ Кронекера, т. е. о~ = О при 1 +у, Наконец, матрица, все элементы которой равны нулю, называется нулевой. Мы будем обозначать ее символом О. Переставив в матрице ап а„... а, ам аю ., лая а„, а,з...аи строки со столбцами, мы получим так называемую транспонирова иную матрицу ац а„...

аю А'= а„„а„„, ... а„„, Квадратная матрица А равна транспонирозанной А' в том и только в том случае, когда она снимет рич на, т. е. если а~~= — ауь Очевидно, что матрица, транспонированная со строкой, есть столбец, составленный из тех же элементов. Это обстоятельство мы часто будем использовать для удобства записи столбцов. Так, вместо столбца мы будем писать (4, 2, 3, 5)'. б 11 МАТРИЦЫ Посредством замены элементов матрицы на комплексно-сопряженные числа мы приходим к комплексно-сопряженной матрице А. Если элементы матрицы 'А вещественны, то А=А. Матрица А*=А', комплексно-сопряженная с транспонированной, называется матрицей с опря же иной с матрицей А. Очевидно, что (А')* = А.