Таблица А.7. Остаток при знаковом коротком делении (строка + столбец)

Таблица А.8. Остаток при беззнаковом коротком делении (строка »- столбец)

ПРИЛОЖЕНИЕ Б МЕТОД НЬЮТОНА

Для краткого рассмотрения метода Ньютона предположим, что у нас имеется дифференцируемая функция/от действительной переменной х и нам требуется решить уравнение /(дг) = 0 относительно х. Метод Ньютона по данному приближению д:„ корня/дает

нам при определенных условиях улучшенное приближение дг,,, по формуле

Здесь /(дг,) означает производную/в точке х = х,. Вывод этой формулы можно пояснить приведенным ниже рисунком (решая показанное уравнение относительно x,).

Накяон=

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

\x..,-r\<{x,-rf.

Таким образом, количество точных цифр решения удваивается при каждой итерации (например, если дг,-гй 0.001, то дг,,-гй 0.000001).

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

Приведенное рассмотрение метода достаточно туманно из-за наличия фраз типа "определенные условия", "доброкачественная функция" и "достаточно близко". Для того чтобы познакомиться с методом Ньютона более строго, обратитесь практически к любому учебнику по вычислительным методам.

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

В табл. Б. 1 приведены некоторые итеративные формулы, выведенные из метода Ньютона. В первом столбце приведены искомые значения, во втором - функции, для которых эти значения являются корнями, и в третьем - правые части формул Ньютона, соответствующие этим функциям.

Таблица Б.1. Метод Ньютона для вычисления некоторых значений

Вычисляемое значение

4 Га 1

logs в

Функция

Итеративная формула

Х.+-

2х.+

ir- )

Х.+-

К сожалению, не всегда просто найти подходящую функцию. Разумеется, существует множество функций, корнем которых является интересующее нас значение, но только немногие из них приводят к практичным итеративным формулам. Обычно функция представляет собой некоторый тип обратных вычислений по отнощению к вычислению искомого значения. Например, для поиска -Ja используется f{x) = x-a, для поиска

loga - f{x) = 2-a ит.д}

Итеративная формула для loga сходится (к log,о ) даже если заменить множитель 1/1п2 некоторым другим значением (например, 1 или 2). Однако скорость сходимости при этом упадет. Для ряда приложений вместо множителя 1/1п 2 можно использовать величины 3/2 или 23/16 (1/1п2 = 1.4427).

Метод Ньютона для частного случая квадратного корня был известен еще в древнем Вавилоне около 4000 лет назад.

ПРИЛОЖЕНИЕ Б. МЕТОД НЬЮТОНА