|
| |
|
Слаботочка Книги 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 [106] 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 нальных матриц Qi и правых треугольных матриц Ri по рекуррентным формулам A-vxE = QiRi, Ai= RiQi + щЕ, Ai i - щЕ = QiRi, Ai = RiQi + viE. Матрицы Ai подобны матрице A\ за счет введения сдвигов щ удается добиться ускорения сходимости. Вопрос о наиболее целесообразном выборе параметров щ мы рассматривать пе будем. В этой главе было, в частности, приведено большое количество методов решения линейных систем уравнений. Какой же из этих методов все-таки стоит выбрать, решая задачу? Если порядок системы небольшой и по затратам машинного времени число арифметических операций порядка /п, где т -порядок системы, является приемлемым, то прош,е всего обратиться к стандартным программам метода отражений (число арифметических действий N w 2m/3) или метода вращений (число арифметических действий N 4т/3, но меньше накопление вычислительной погрешности). Конечно, при этом надо иметь в виду, ito точные методы типа методов отражений или вращений для матрицы общего вида требуют одновременного хранения в памяти ЭВМ порядка т? чисел. Если такое количество чисел не помещается в оперативной памяти ЭВМ, а обмен информацией между оперативной и внешней памятью происходит недостаточно быстро или из-за структуры nporpainMbi, или из-за возможностей ЭВМ, то применение этих программ может оказаться нецелесообразным. В случае, когда применение этих методов нецелесообразно, имеет смысл проанализировать возможности применения простейших по своей структуре итерационных методов: простой итерации, Зейделя, сверхрелаксации, наискорейшего спуска. Если решается отдельная задача, то вследствие простоты соответствующих программ применение этих методов может быть вполне целесообразным. Если применение этих методов требует больших затрат машинного времени, то следует проанализировать возможности применения более сложных по своей структуре методов: оптимального линейного итерационного процесса, метода с использованием корней многочлена Чебышева, метода сопряженных градиентов, итерационных методов, используюпщх спектрально эквивалентные операторы. Если размерность задачи столь велика, что само решение задачи, т.е. вектор X, не помещается в оперативной памяти ЭВМ, то иногда применяются вероятностные методы решения систем линейных уравнений, которые остались вне нашего рассмотрения. Литература 1. Абрамов А.А. О численном решении некоторых алгебраических задач, возникающих в теории устойчивости. ЖВМиМФ -1984. 24, N 3. С. 339-347. 2. Бахвалов Н.С. Численные методы. - М.: Наука, 1975. 3. Воеводин В.В. Численные методы алгебры. Теория и алгоритмы. - М.: Наука, 1966. 4. Воеводин В.В. Вычислительные основы линейной алгебры.- М.: Наука, 1977. 5. Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. - М.: Наука, 1984. 6. Годунов С.К. Решение систем линейных уравнений. - Новосибирск: Наука, 1980. 7. Годунов С.К. Современные аспекты линейной алгебры. - Новосибирск: Научная книга, 1997. 8. Джордж А., Лю Д. Численное решенпе больших разреженных систем уравнений.-М.: Мир, 1984. 9. Дьяконов Е.Г. О построении итерационных методов на основе использования операторов, эквивалентных по спектру ЖВМ и МФ. - 1966. - 6, N 1. - С. 12-34. 10. Икрамов Х.Д. Численное решение матричных уравнений. ~ М.: Наука, 1984. 11. Канторович Л.В. Функциональный анализ и прикладная математика. УМН -1948. 3 N 6 (28). С. 89-185. 12. Крылов В.И., Бобков В.В., Монастырный П.И. Начала теории вычислительных методов. Линейная алгебра и нелинейные уравнения. - Минск: Наука и техника, 1982. 13. Марчук Г.И., Лебедев В.И. Численные методы в теории переноса нейтронов. -- М.: Атомиздат, 1981. 14. Ортега Д. Введение в параллельные и векторные методы решения линейных систем. - М.: Мир, 1991. 15. Парлетт Б. Симметричная проблема собственных значений. - М.: Мир, 1983. 16. Поспелов В.В. Метод оптимального спуска по базису для решения вырожденных систем линейных алгебраических уравнений. ЖВМиМФ - 1991. 31, N 7. С. 961-969. 17. Фаддеев Л.К., Фадцеева В.Н. Вычислительные методы линейной алгебры. - М.: Физматгиз, 1963. 18. Форсайт Дж. и др. Машинные методы математических вычислений. - М.: Мир, 1980. - Глава/ ..... Решение систем нелинейных уравнений и задач оптимизации Решение задач оптимизации, будь то оптимизация производственных или экономических процессов, оптимизация конструкций или оптимизация численных алгоритмов, сводится в математической формулировке исследуемой задачи к отысканию экстремума функционалов. В наиболее типичных случаях возникает задача мш1имизации функции большого числа переменных в области Q, задаваемой большим числом ограничений типа неравенств или равенств: ищется при условиях inf Ф(Ж], . . . , Хт) Xl,...,Xr,i ipi{xu ..., Хт) о, г = 1,...,/; ф1{х1,..., Хт) =0, i = l,...,q. Задача минимизации функций большого числа переменных возникает также в случае применения вариационных методов к решению задач математической физики и в других разделах прикладной математики. Системы уравнений fi{xi,..., Хт) =0, г = 1, ...,т, которые мы будем также обозначать F(x) = О, возникают в случае многих задач указанных выше типов; например, в гл. 10 будет идти речь о подобных системах, возникающих при решении краевых задач. Задачи минимизации функции и решения системы уравнений сводятся друг к другу. Если {уи...,Ут) > о при {Уъ..-,Ут)Ф{0,...,0), Ф(0,...,0)=0, то решение системы F(x) = О равносильно минимизации функции Хт),..., /т(ж1,..., Хт)У 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 [106] 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 |