|
| |
|
Слаботочка Книги Пусть для определенности (х, gfc) > (у, gi). Тогда справедлива цепочка неравенств I gfc) I - I {У, I I 1(х, gfc)l I - I 1(У, gfc)l I (х - У, gfc) шцх (х - у, откуда и следует непрерывность рассматриваемого функционала. Предположим, что утверждение леммы неверно. Тогда существует последовательность {xj} такая, что ЦхЦ = 1 и 0(х) > 1-е,:, где О при г -> оо. Так как в конечномерном пространстве сфера S - {х. : ЦхЦ = 1} компактна, то существует сходящаяся подпоследовательность. Для простоты изложения предположим, что сходится сама последовательность X* = Иш x-i- г->оо В силу непрерывности функционала ф имеем ф{х*) - 1 и Цх*Ц = 1. Следовательно, при А; = argmax (х*, g,) имеем ф{х*) = \\х* - (х*, gk)gkf = Цх*Ц2 - 2(Х*, gk? + (х*, gk)4gkf = = \\x*f - (X*, g,f = 1. Отсюда следует, что (х*, g) = 0. Так как (х*, gfc) > (х*, gj) для любого j = 1,(/, то (х*, gj) = О при всех j = 1,..., (/. Так как х* принадлежит линейной оболочке векторов gi,..-, gb то последнее равенство может выполняться лишь при X* = О, что противоречит условию Цх*Ц = 1. Лемма доказана. Теорема. Последовательность приближений х*, получаемая в ходе итерационного метода (14), (15), является фундаментальной и сходится к некоторому вектору, минимизирующему функционал невязки ф(х) на подпространстве W, со скоростью геометрической прогрессии. А именно, существует q < 1 такое, что Цх= - х°°Ц Cq, х° = Иш х к-оо Постоянная q при этом зависит от выбора базиса {wj} и оператюра А. Доказательство. Так как Awj ф О, то существует постоянная J > О такая, что ЦЛгЛ>< VA;. (16) Из (14), (15) следует, что невязки = Ак - Ъ удовлетворяют соотношению tk+l tk (Awj,*) xii iix+i xii 5]7+ Vp е N. Таким образом, последовательность {х*} является фундаментальной и имеет предел х°°. В силу построения, х°° минимизирует функционал Ф(у) на подпространстве W. Теорема доказана. Описанный выше метод решения систем уравнений с плохо обусловленными матрицами особенно эффективен в случае, когда априорная информация представлена в виде каких-либо сведтий о структурных особенностях искомого решения; например, когда известны базисные функции Wj, и решение представимо в виде разложения по небольшому числу этих функций. Такая ситуация часто имеет место в задачах цифровой обработки сигналов. Особенно эффективен данный метод в случае, когда q достаточно мало. Другими словами, для эффективного применения данного метода надо иметь разумную параметризацию исходной задачи. Довольно часто это можно сделать на основе априорной информации о решении. Например, если известно, что решение представляет собой некоторый колебательный процесс с небольшим числом гармоник, номера которых, вообще говоря, неизвестны. Положим gj = Awi/Awi. Тогда (17) примет вид Поскольку Cfc выбиралось из условия минимума Ц* !!, то jk = arg max (*, gj) и мы находимся в условиях предыдущей леммы. Тогда из условий леммы следует оценка ие+ЧКтГи, 7<1- (18) Из (14) и (15) имеем Aw,J2 откуда, учитывая (16), получаем оценку 11х-+-хк iiWi/iiAwjjK (1е11/<. Применяя к полученному неравенству оценку (18), имеем (х=+-х=К7ьА откуда следует цепочка соотношений р+к р (1-)6 § 12. Проблема собственных значений в различных случаях возникают разные требования к информации о собственных значениях и собственных векторах матриц, и это порождает многообразие проблем и приемов решения этой задачи. 1. Для решения ряда задач механики, физики, химии требуется получение всех собственных значений, а иногда и всех собственных векторов некоторых матриц. Эту задачу называют полной проблемой собственных значений. 2. В ряде случаев требуется найти лишь максимальное или минимальное но модулю собственное значение матрицы. Проблемы подобного сорта возникают, в частности, при решении некоторьгх задач ядерной физики. Здесь приходится решать задачи, эквивалентные задачам отыскания собственных значений матриц размерности порядка Ю-Ю** или даже существенно большей. При малых размерностях матриц для решения этих задач чаще применяют итерационные методы, при больших - вероятностные. 3. При исследовании колебательных процессов иногда требуется найти два максимальных но модулю собственных значения матрицы, причем меньшее из них обычно достаточно определить с меньшей точностью. 4. Там же возникает задача отыскания собственного значения матрицы, наиболее близкого к заданному числу А , или отыскания расстояния от заданного числа А до спектра матрицы. Формально рассуждая, можно было бы сказать, что эти задачи, называемые частичными проблемами собственных значений, являются частным случаем общей проблемы собственных значений и достаточно ограничиться рассмотрением методов решения общей проблемы. Однако такой подход приведет к неоправданно большому объему вычислений. При обсуждении постановок конкретных задач, связанных с отысканием собственных значений матриц, зачастую значительные усилия тратятся именно на установление минимального объема информации о спектре матрицы, которым можно ограничиться. Решение задач 2-4 обычно сводят к отысканию максимального по модулю собственного значения некоторой матрицы В = д{А) такой, что это Изложенный выше метод может быть обоснован также и в случае, когда спуск осугцествляется не по одномерным подпространствам, соответствуюнщм координатным осям в базисе {wj}, а но гиперплоскостям. При этом, естественно, скорость сходимости обычно бывает вьппе, однако число арифметических операций на шаге процесса возрастает. 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 |