|
| |
|
Слаботочка Книги Поэтому при любой норме имеем х - XII (Xllxill) llilloo \\D- IU Q x° - XU 0. (9) Соотношения (8), (9) означают также, что любые нормы погрешности убывают быстрее любой геометрической прогрессии со знаменателем, большим max Л.;. Необходимость. Пусть Л] > 1 и ei - соответствующий собственный вектор матрицы В. Тогда при начальном приближении х = Х + се\ сф О, имеем г = cei и г = Xfcei -фг О при п -> оо. Задача 1. Пусть все собственные значения матрицы В, за исключением простого Ai = 1, лежат внутри единичного круга и система (2) имеет решение X. Решением системы будут также все х = X + cei. Доказать, что итерационный процесс (3) сходится к одному из таких решений. § 4. Особенности реализации метода простой итерации на ЭВМ Если все собственные значения матрицы В лежат внутри единичного круга, то может показаться, что не возникает никаких проблем относительно поведения метода в реальных условиях ограниченности порядков чисел в ЭВМ и присутствия округлений. В обоснование этого иногда приводят следующий довод: возмущения приближений в результате округлений равносильны возмущениям начальных условий итерационного процесса. Поскольку процесс сходящийся, самоисправляющийся , эти возмущения в конце концов затухнут, и будет получено хорошее приближение к решению исходной задачи. Однако при решении некоторых систем возникала следующая ситуация. Все собственные значения матрицы В лежали в круге А 1/2, а итерационный процесс останавливался после некоторого чида итераций из-за переполнения порядков чисел в ЭВМ. В других случаях такого переполнения не происходило, но векторы х , получаемые при вычислениях, не сходились к решению. Последний случай особенно опасен по следующей причине. Можно необоснованно решить, что при условии maxAj < 1/2 какое-то определенное число итераций, например 100, заведомо достаточно для получения решения с требуемой точностью. Затем производим эти 100 итераций и рассматриваем полученный результат как требуемый. Поэтому наличие подобных явлений послужило толчком к более детальному исследованию итерационных процессов и формированию новых понятий в теории операторов. Чтобы понять сущность явления, полезно построить пример, где это явление прослеживается в явном виде. В качестве модели выберем итерационный процесс, соответствующий двухдиагональной матрице In /3 О О \ О а /3 О При возведении матрицы Bp в степень п, получается треугольная матрица с элементами bf = СГ*а /3 Если = (О,..., О, 1), то При п < т последнее выражение упрощается: г=1 т-1 Рассмотрим случай \а\ < 1, а-Ь > 1, -а) < 1. Пусть с = с = (О,..., О, 1)-. Непосредственно проверяется, что при таком с решением рассматриваемой системы будет Справедлива оценка где 1 - а \1 - а 1 -а 1 -а При начальном приближении = -f с имеем г = с и, согласно проводившимся выше построениям, 1к 1 = (И + ;бГ для П<Ш. Выберем m таким, чтобы число о= [(а + уб) ~ - /т превосходило пределы, допустимые в ЭВМ. Из полученных ранее соотношений следует, что х-Mloo > х-iii/m (г--11 - x ii)/m а. Поэтому построенный пример обладает следуюш,ими свойствами: норма начального приближения невелика, итерационный процесс сходится при отсутствии округлеиий и ограничения на порядки чисел в ЭВМ, но останавливается не позднее чем при п = тп - 1 из-за недопустимо больших значений компонент приближений. Обратимся к реальной ситуации, когда на каждом шаге вьгшслений происходят округления. Рассмотрим подробнее случай, когда переполнение не происходит. Вместо х получаются векторы х* , связанные соотношениями х* +1 = j5x* + с -Ь р , где р -суммарное округление на шаге итерации. Отсюда и из (3.2) получается уравнение относительно погрешности г* = X* - X: г* +1 = p + i?r* . (1) Выражая каждое г* через предыдущее, получаем г* = р -1 -f i?r* -i = р - Л- В{р - + Вг* -) = = р -1 + Вр - -Ь -Ь Я -° + J5 r°. Как мы видели, норма i?o II при а < 1, а-Ь)0 > 1 имеет следующий характер поведения: при малых п она имеет тенденцию к возрастанию, при больших п стремится к нулю. (Можно показать, что максимальное значение (р{Во) = maxi? достигается при значении п = по порядка т.) При таком характере поведения норм i? может возникнуть следующая ситуация. Величина шахх* не настолько велика, чтобы происходило переполнение и остановка ЭВМ; в то же время ip{B)2~* 3> R, где R - максимально допустимая погрешность решения. Поэтому, как правило, при 71 > По среди слагаемых в правой части (2) присутствует слагаемое jnopn-1-по нормой, много большей, чем R. В результате установление приближений х с приемлемой точностью не происходит. Подведем некоторый итог проведенных построений. Матрицы высокой размерности обладают свойствами, существенно отличными от свойств матриц малой размерности. Кроме собственных значений у таких матриц есть почти собственные значения, т. е. Л такие, что Лх - Лх ех при х 7 О и очень малом е. Например, в случае матрицы Во при любом Л , лежащем в круге о: - А < можно построить вектор хд такой, что ЦВоХд - АхдПоо < еаЦхаНоо, где ед = 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 |