Влияние ошибок округления

46. Нет особого смысла продолжать анализ предыдущего параграфа, так как в действительности ошибки округления — основной фактор при практическом решении задачи. На практике возможная достижимая точность вычислений ограничивается областью неопределенности корня, и, вообще говоря, у нас нет а priori информации о размере этой области. Если мы в критерии (45.3) выберем слишком малое значение то он может не быть удовлетворенным, как бы долго ни продолжали мы итерации. С другой стороны, если 8 будет слишком велико, то достигнутая точность будет значительно меньше точности, которую можно было бы получить. Это будет верно, например, в случае хорошо определенных кратных корней, так как для них сходимость к пределу медленная, но неуклонная.

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

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

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

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

то предлагается считать значение приемлемым.

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

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