Общие комментарии о методах удаления

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

является то, что можно использовать все время одну и ту же точность вычислений.

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

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

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

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