Богачев - Практикум на ЭВМ. Методы решения линейных систем и нахождения собственных значений (Богачев - Практикум на ЭВМ)

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М.В. ЛОМОНОСОВА Механико-математический факультет Кафедра вычислительной математики К.Ю. Богачев Практикум на ЭВМ. Методы решения линейных систем и нахождения собственных значений Москва 1998 год СОДЕРЖАНИЕ Содержание ПРЕДИСЛОВИЕ 34.4 34.5 310.МЕТОД ХОЛЕЦКОГО (КВАДРАТНОГО КОРНЯ) ......... 35 ~10.1. Разложение Холецкого 35 310.2. Алгоритм построения разложения Холецкого ........ 36 310.3.

Оценка количества арифметических операций в алгоритме построения разложения Холецкого .............. 39 Глава Р. 32. ~3. Я 35. 36. 37. 38. 39. 1. ТОЧНЫБ МЕТОДЫ РЕШЕНИЯ ЛИНЕИНЫХ СИСТЕМ 7 МАТРИЧНЫЕ НОРМЫ 7 ОБРАТИМОСТЬ МАТРИЦЫ, БЛИЗКОЙ К ОБРАТИМОЙ МАТРИЦЕ . 12 ОШИБКИ В РЕШЕНИЯХ ЛИНЕЙНЫХ СИСТЕМ......... 12 МЕТОД ГАУССА.............................

15 34.1. Алгоритм метода Гаусса 15 34.2. Оценка количества арифметических операций в методе Гаусса 17 34.3. Представление метода Гаусса в виде последовательности элементарных преобразований 18 Алгоритм построения ИУ-разложения............ 19 Оценка количества арифметических операций в алгоритме построения И7-разложения 21 34.6. Осуществимость метода Гаусса 21 МЕТОДЫ ПОСЛЕДОВАТЕЛЬНОГО ИСКЛ1ОЧЕНИЯ НЕИЗВЕСТНЫХ ДЛЯ ЛЕНТОЧНЫХ МАТРИЦ 22 35.1. Метод Гаусса для ленточных матриц............. 22 35.2. Алгоритм ИУ-разложения для трехдиагональных матриц .

23 $э.3. Метод прогонки для трехдиагональных матриц....... 24 ЗАДАЧА ОБРАЩЕНИЯ МАТРИЦЫ 26 МЕТОД ГАУССА С ВЫБОРОМ ГЛАВНОГО ЭЛЕМЕНТА..... 27 МЕТОД ЖОРДАНА (ГАУССА-ЖОРДАНА)............. 31 ПОЛОЖИТЕЛЬНО ОПРЕДЕЛЕННЫЕ МАТРИЦЫ........ 33 СОДЕРЖАНИЕ 311. МЕТОД ОРТОГОНАЛИЗАЦИИ 312.

МЕТОД ВРАЩЕНИЙ 312.1. Матрица элементарного вращения и ее свойства 312.2. Алгоритм метода вращений 312.3. Оценка количества арифметических операций в методе врагцений 312.4. Построение ЯЛ-разложения методом вращений....... 312.5.

Оценка количества арифметических операций в алгоритме построения Ягг-разложения методом вращений ....... 313. МЕТОД ОТРАЖЕНИЙ ~13.1. Матрица отражения и ее свойства . 313.2. Алгоритм метода отражений 313.3. Оценка количества арифметических операций в методе отражений . 313.4. Построение ЯВ-разложения методом отражений...... 313.5. Оценка количества арифметических операций в алгоритме построения ЯЛ-разложения методом отражений 314. ПРИВЕДЕНИЕ МАТРИЦЫ К ПОЧТИ ТРЕУГОЛЬНОМУ ВИДУ УНИТАРНЫМ ПОДОБИЕМ МЕТОДОМ ВРАЩЕНИЙ....... 314.1.

Случай произвольной матрицы 314.2. Случай симметричной матрицы 315. ПРИВЕДЕНИЕ МАТРИЦЫ К ПОЧТИ ТРЕУГОЛЬНОМУ ВИДУ УНИТАРНЫМ ПОДОБИЕМ МЕТОДОМ ОТ1'АЖЕНИЙ...... 315.1. Случай произвольной матрицы 315.2. Случай самосопряженной матрицы Глава 11. МЕТОДЫ НАХО.гКДЕНИЯ СОБСТВЕННЫХ ЗНАЧЕНИЙ 31. ТОЧНЫЕ И ИТЕРАЦИОННЫЕ МЕТОДЫ.............. 32.

ЛОКАЛИЗАЦИЯ СОБСТВЕННЫХ ЗНАЧЕНИЙ 33. ОШИБКИ ПРИ НАХОЖДЕНИИ СОБСТВЕННЫХ ЗНАЧЕНИЙ . 34. СТЕПЕННОЙ МЕТОД .. 34.1. Описание алгоритма . 34.2. Оценка количества арифметических операций на один шаг алгоритма .. 35. МЕТОД ВРАЩЕНИЙ ЯКОБИ 35.1. Описание алгоритма . 35.2. Выбор угла вращения 35.3. Стратегии выбора обнуляемого элемента...........

39 43 43 46 48 50 51 52 53 эо 58 59 62 62 67 71 79 79 80 82 85 85 85 87 89 СОДЕРЖАНИЯ 35.3.1. Метод вращений с выбором максимального элемента 90 35.3.2. Метод вращений с циклическим выбором обнуляемого элемента 91 Алгоритм вычисления й-го по величине собственного значения методом бисекции Алгоритм вычисления всех собственных значений на заданном интервале методом бисекции 36.2.1. Рекурсивный алгоритм 36.2.2. Алгоритм последовательного поиска собственных значений 95 Алгоритм вычисления всех собственных значений методом бисекции 95 Вычисление числа перемен знака в последовательности главных миноров .

95 36.4.1. Вычисление числа перемен знака в последовательности главных миноров с помощью Асг-разложения 96 Я.4.2. Вычисление числа перемен знака в последовательности главных миноров с помощью реккурентных формул . 96 98 98 37. 511 АЛГОРИТМ 37.1 ЬЛ-разложение, используемое в 1.В алгоритме....... 37.1.1. Алгоритм построения Ь1г-разложения для произвольной матрицы Алгоритм построения ЬВ-разложения для почти треугольной матрицы Алгоритм построения Ь1г-разложения для трех- диагональной матрицы ьгг алгоритм нахождения собственных значений......

37.2.1. Ьг1 алгоритм нахождения собственных значений для почти треугольной матрицы АВ алгоритм нахождения собственных значений для трехдиагональной матрицы........... 37.1.2 100 37.1.3 101 101 37.2 102 37.2.2 103 104 105 106 37.3 Ускорение сходимости алгоритма 37.3.1. Исчерпывание матрицы .. ~7.3.2. Сдвиги 37.3.3. Практическая организация вычислений в ЬЛ алгоритме . 106 35.3.3. Метод вращений с выбором оптимального элемента 92 ~6. МЕТОД БИСЕКЦИИ 93 СОДЕРЖАНИЕ 38. МЕТОД ХОЛЕЦКОГО .. 38.1. Разложение Холецкого,используемое в методе Холецкого .

38.1.1. Алгоритм построения разложения Холецкого для произвольной самосопряженной матрицы 38.1.2. Алгоритм построения разложения Холецкого для трехдиагональной матрицы 38.2. Метод Холецкого нахождения собственных значений.... 38.2.1. Метод Холецкого нахождения собственных значений для трехдиагональной матрицы 38.3. Ускорение сходимости алгоритма 38.3.1. Исчерпывание матрицы .. Я.3.2. Сдвиги '38.3.3. Практическая организация вычислений в методе Холецкого ~9. ЯВ АЛГОРИТМ 39.1. ЯЯ-разложение, используемое в ЯЛ алгоритме 39.1.1.

Алгоритм построения ЯВ-разложения для произвольной матрицы 39.1.2. Алгоритм построения ЯН-разложения для почти треугольной матрицы 39.1.3. Алгоритм построения (~1т-разложения для трех- диагональной матрицы 39.2. ЯВ алгоритм нахождения собственных значений...... 39.2.1. ЯЛ алгоритм нахождения собственных значений для почти треугольной матрицы 39.2.2. ЧЛ алгоритм нахождения собственных значений для самосопряженной трехдиагональной матрицы 39.3.

Ускорение сходимости алгоритма 39.3.1. Исчерпывание матрицы .. ~9.3.2. Сдвиги 39.3.3. Практическая организация вычислений в ЯВ алгоритме . 310. МЕТОД ОБРАТНОЙ ИТЕРАЦИИ НАХОЖДЕНИЯ СОБСТВЕННЫХ ВЕКТОРОВ .. ПРОГРАММА КУРСА ЛИТЕРАТУРА .. 107 107 107 109 110 111 112 112 113 113 114 114 114 114 120 124 125 126 129 129 129 130 130 133 137 ПРЕДИСЛОВИЕ Настоящее пособие содержит описания алгоритмов, предлагаемых к реализации на ЭВМ студентам механико-математического факультета МГУ на занятиях по "Практикуму на ЭВМ".

Для всех алгоритмов приводится необходимое теоретическое обоснование, соответствующие расчетные соотношения и рекомендации по их практическому осуществлению на ЭВМ (организация процесса вычислений, хранения данных и результатов в памяти ЭВМ и т.п.). Многообразие алгоритмов объясняется, с одной стороны, необходимостью обеспечить преподавателей достаточным набором задач для проведения занятий, а с другой стороны, желанием продемонстрировать различные подходы к решению задачи решения линейных систем и нахождения собственных значений матриц. Алгоритмы требуют разных вычислительных затрат, имеют разную чувствительность к погрешностям во входных данных, их свойства по-разному зависят от числа обусловленности матрицы. "Самого лучшего" метода решения поставленной задачи не существует, и выбор алгоритма зависит от конкретной задачи.

Этот выбор будет различным, например, для симметричных и несимметричных матриц, для трехдиагональных и заполненных матриц, и т.д. Подбор алгоритмов для Практикума диктовался, в основном, возможностью реализации их студентами при существующих ресурсах времени на ЭВМ, что привело к отказу от рассмотрения усложненных подходов. Часть описанных алгоритмов вытеснена из широкой вычислительной практики более эффективными (и более сложными) алгоритмами, рассмотреть которые в курсе "Практикум на ЭВМ" не представляется возможным.

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

Поэтому в рамках Практикума студентам предлагается как разработать программу на ЭВМ, реализующую заданный алгоритм, так и письменно ответить хотя бы на половину вопросов из предложенного варианта, составленного из вопросов, приведенных в конце пособия. В основе настоящего пособия лежат материалы лекций, читавшихся автором в течении 4-х лет в рамках факультативного курса "Практикум на ЭВМ". В электронном варианте оно уже более 5-ти лет используется при проведении занятий со студентами в дисплейном классе. Предложения, замечания и отмеченные опечатки просьба сообщать автору на кафедру вычислительной математики. Глава 1.

ТО~ХНЫЕ МЕТОДЫ РЕШЕНИЯ ЛИНЕЙНЫХ СИСТЕМ 2 1. МАТРИЧНЫЕ НОРМЫ Обозначим через М„пространство 1кольцо) матриц размера и х и над полем С. Определение. Нормой на кольце М„называется неотрицательный функционал ~~ ~): ̄— ~ К', удовлетворяющий следующим условиям для всех А,ВеМ„: 1) ()А)(=о ~ А=о, 2) (! ЛА )) = )Л( )/ А !) для всех Л ~ С, З) ()А+В)( < !)А()+()В(), 4) (/АВ(/ < !)А!)(!В!). Простейшие свойства нормы: 1) )(1 )) > 1 1где Т означает единичную матрицу).

Действительно, Щ = !)Т Т(! < )(Т)( )(А"О = 'ОА'()2. ~й 2) оА 1)( > и, в частности, !)А 1!) ()А)! > 1. И! Доказательство: (Щ = ()АА ')( < !)А() )(А 1)( . Поскольку М„можно рассматривать как векторное пространство размерности п2, то на нем можно вести векторные нормы, некоторые из которых оказываются матричными. Для таких норм в проверке нуждается только свойство 4) 1поскольку первые три свойства составляют определение векторной нормы). 1,12 Пример.

оА~~н — — ~)(а;1); 1 „'он — — ( ) ~а1 ~2 ~ является матричной нор- 1 1,1=1 мой. Проверим свойство 4): 1АВ))' = с )с 1 11 )' < с (с ) и)) (с ( Х; (а;ь)2)( ~и )Ь )2) = !)А()н)/В(/и. К.Ю.Богачев Точные методы решения линейных систем ~1. МАТРИЧНЫЕ НОРМЫ Упражнение. Проверить, что выражение ~)А~~с = шах ~а;,~ не является !<!д<н матричной нормой.

Указание: рассмотреть матрину Упражнение. Проверить, что выражение !)А)( = и ()А)(~ является матричной нормой. Определение. Пусть ~~ ~~ есть векторная норма на пространсте С". Опере- делим матричную норму ~! ~( на М„формулой (/А!) = шах (!Ах)!. Такая норма называется подчиненной, или от!ераторной, или индуцированной по отношению к векторной норме ~~ ~!. Проверим вначале, что !)А(! = и!ах )(Ах() = шах !)Ах)) ~И=! *Фо )(х!) Действительно, шах = !пах)(А !) < !пах ()Ау() = !)А)(, ()Ах)( х иФо )(х!) лФо ()х!) Ь~(=! ()А!) = !пах ()Ах!) = шах < !пах !)Ах!) !)Ах)( ~И=! ~И=! ()х)! *Фо )(х!) Теорема 1. Так определенный функционал на М„действигпельно лвллетсл матричной нормой, которая обладает следующими свойствами: )(Ах(! < !)А() 'Ох)) для всех А Е М„, х Е С", Н =1.