§ 4. Особенности реализации метода простой итерации на ЭВМ
Если все собственные значения матрицы В лежат внутри единичного круга, то может показаться, что не возникает никаких проблем относительно поведения метода в реальных условиях ограниченности порядков чисел в ЭВМ и присутствия округлений. В обоснование этого иногда приводят следующий довод: возмущения приближений в результате округлений равносильны возмущениям начальных условий итерационного процесса. Поскольку процесс сходящийся, «самоисправляющийся», эти возмущения в конце концов затухнут, и будет получено хорошее приближение к решению исходной задачи.
Однако при решении некоторых систем возникала следующая ситуация. Все собственные значения матрицы В лежали в круге
, а итерационный процесс останавливался после некоторого
итераций из-за переполнения порядков чисел в ЭВМ. В других случаях такого переполнения не происходило, но векторы
, получаемые при вычислениях, не сходились к решению. Последний случай особенно опасен по следующей причине. Можно необоснованно решить, что при условии
какое-то определенное число итераций, например 100, заведомо достаточно для получения решения с требуемой точностью. Затем производим эти 100 итераций и рассматриваем полученный результат как требуемый. Поэтому наличие подобных явлений послужило толчком к более детальному исследованию итерационных процессов и формированию новых понятий в теории операторов.
Чтобы понять сущность явления, полезно построить пример, где это явление прослеживается в явном виде. В качестве модели выберем итерационный процесс, соответствующий двухдиагональной матрице
При возведении матрицы
в степень
, получается треугольная матрица
с элементами
. Если
, то
При
последнее выражение упрощается:
Рассмотрим случай
. Пусть
. Непосредственно проверяется, что при таком с решением рассматриваемой системы будет
Справедлива оценка
где
При начальном приближении
имеем
и, согласно проводившимся выше построениям,
Выберем
таким, чтобы число
превосходило пределы, допустимые в ЭВМ. Из полученных ранее соотношений следует, что
Поэтому построенный пример обладает следующими свойствами: норма начального приближения невелика, итерационный процесс сходится при отсутствии округлений и ограничения на порядки чисел в ЭВМ, но останавливается не позднее чем при
из-за недопустимо больших значений компонент приближений.
Обратимся к реальной ситуации, когда на каждом шаге вычислений происходят округления. Рассмотрим подробнее случай, когда переполнение не происходит. Вместо
получаются векторы
, связанные соотношениями
где
— суммарное округление на шаге итерации.
Отсюда и из (3.2) получается уравнение относительно погрешности
:
Выражая каждое
через предыдущее, получаем
Как мы видели, норма
при
имеет следующий характер поведения: при малых
она имеет тенденцию к возрастанию, при больших
стремится к нулю. (Можно показать, что максимальное значение
достигается при значении
порядка
.)
При таком характере поведения норм
может возникнуть следующая ситуация. Величина
не настолько велика, чтобы происходило переполнение и остановка ЭВМ; в то же время
, где R - максимально допустимая погрешность решения. Поэтому, как правило, при
среди слагаемых в правой части (2) присутствует слагаемое
с нормой, много большей, чем R. В результате установление приближений
с приемлемой точностью не происходит.
Подведем некоторый итог проведенных построений. Матрицы высокой размерности обладают свойствами, существенно отличными от свойств матриц малой размерности. Кроме собственных значений у таких матриц есть почти собственные значения, т. е.
такие, что
при
и очень малом
.
Например, в случае матрицы
при любом
, лежащем в круге
, можно построить вектор
такой, что
, где
.
Поведение степеней матрицы
при
порядка
определяется во многом такими «почти собственными векторами»
и «почти собственными значениями»
.
Задача 2. Построить «почти собственный вектор»
, соответствующий значению
, приведенному выше.
Суммарная вычислительная погрешность
может оказаться большой не только из-за большой величины отдельных слагаемых, но и из-за того, что их много.
Пусть В симметричная матрица и
— соответствующий
нормированный собственный вектор. Предположим, что на каждом
шаге происходит округление
, где
порядка
. Имеем равенство
Поскольку число итераций берется таким, что
, а
, то можно считать, что
. Таким образом, если
близко к 1, то суммарное влияние округлений на шагах интегрирования может оказаться довольно большим.
Покажем, что вычислительная погрешность такого порядка является неизбежной. Предположим, что вместо системы (3.2) решается система
. Разность X — X решений этих систем удовлетворяет соотношению
, отсюда
. Поэтому погрешность порядка
является неустранимой; возмущение приближений, создаваемое в ходе итераций, сравнимо с неустранимой погрешностью.