Главная > Методы обработки сигналов > Численные методы
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

§ 4. Особенности реализации метода простой итерации на ЭВМ

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

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

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

При возведении матрицы в степень , получается треугольная матрица

с элементами . Если , то

При последнее выражение упрощается:

Рассмотрим случай . Пусть . Непосредственно проверяется, что при таком с решением рассматриваемой системы будет

Справедлива оценка

где

При начальном приближении имеем и, согласно проводившимся выше построениям,

Выберем таким, чтобы число превосходило пределы, допустимые в ЭВМ. Из полученных ранее соотношений следует, что

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

Обратимся к реальной ситуации, когда на каждом шаге вычислений происходят округления. Рассмотрим подробнее случай, когда переполнение не происходит. Вместо получаются векторы , связанные соотношениями

где — суммарное округление на шаге итерации.

Отсюда и из (3.2) получается уравнение относительно погрешности :

Выражая каждое через предыдущее, получаем

Как мы видели, норма при имеет следующий характер поведения: при малых она имеет тенденцию к возрастанию, при больших стремится к нулю. (Можно показать, что максимальное значение достигается при значении порядка .)

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

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

Например, в случае матрицы при любом , лежащем в круге , можно построить вектор такой, что , где .

Поведение степеней матрицы при порядка определяется во многом такими «почти собственными векторами» и «почти собственными значениями» .

Задача 2. Построить «почти собственный вектор» , соответствующий значению , приведенному выше.

Суммарная вычислительная погрешность может оказаться большой не только из-за большой величины отдельных слагаемых, но и из-за того, что их много.

Пусть В симметричная матрица и — соответствующий нормированный собственный вектор. Предположим, что на каждом шаге происходит округление , где порядка . Имеем равенство

Поскольку число итераций берется таким, что , а , то можно считать, что . Таким образом, если близко к 1, то суммарное влияние округлений на шагах интегрирования может оказаться довольно большим.

Покажем, что вычислительная погрешность такого порядка является неизбежной. Предположим, что вместо системы (3.2) решается система . Разность X — X решений этих систем удовлетворяет соотношению , отсюда . Поэтому погрешность порядка является неустранимой; возмущение приближений, создаваемое в ходе итераций, сравнимо с неустранимой погрешностью.

<< Предыдущий параграф Следующий параграф >>
Оглавление