Метод итераций

16

Метод интерации

Член-корреспондент АПН СССР
В. Г. БОЛТЯНСКИЙ

I

Несколько тысячлетий назад в Древнем Вавилоне был изобретен простой способ приближенного вычисления квадратных корней.

Пусть мы хотим вычислить $\sqrt{a}$ (где $a > 0$), то есть найти положительный корень уравнения $x^2 = a$.

Это уравнение равносильно следующему:

$$x = \frac{a}{x}.$$

(1)

Предположим теперь, что мы имеем некоторое приближение $x_0$

числа $\sqrt{a}$. Согласно (1), $x_0$ надо сравнить с числом $\frac{a}{x_0}$: ведь если $x_0$ и $\frac{a}{x_0}$ совпадают, то $x_0$ — точное значение $\sqrt{a}$. Если, однако, $x_0 \neq \sqrt{a}$, то одно из чисел $x_0$, $\frac{a}{x_0}$ меньше, а другие больше, чем $\sqrt{a}$ (поскольку произведение этих чисел равно $a$), то есть $\sqrt{a}$ лежит между $x_0$ и $\frac{a}{x_0}$. Можно предложить, что среднее арифметическое этих чисел

$$x_1 = \frac{1}{2} \left( x_0 + \frac{a}{x_0} \right)$$

является лучшим приближением числа $\sqrt{a}$, чем исходное приближение $x_0$.

Это приближение $x_1$ можно улучшить таким же способом, то есть взять среднее арифметическое чисел $x_1$ и $\frac{a}{x_1}$

$$x_2 = \frac{1}{2} \left( x_1 + \frac{a}{x_1} \right),$$

затем можно взять среднее приближение

$$x_3 = \frac{1}{2} \left( x_2 + \frac{a}{x_2} \right)$$

и так далее.

Какова точность вывилонского способа? Для ответа на этот вопрос проведем следующие вычисления:

$$x_n - \sqrt{a} = \frac{1}{2} \left( x_{n-1} + \frac{a}{x_{n-1}} \right) - \sqrt{a} =$$

17

$$\frac{1}{2} \left( \sqrt{x_{n-1}} - \sqrt{\frac{a}{x_{n-1}}} \right)^2 = \frac{1}{2x_{n-1}} \left( x_{n-1} - a \right)^2. \quad (2)$$

Равенство (2) дает возможность выразить ошибку приближения $x_n$ (то есть число $|x_n - \sqrt{a}|$) через ошибку предыдущего приближения $x_{n-1}$.

Задание

1. Докажите, что все приближения числа $\sqrt{a}$, найденные по вавилонскому способу, кроме, быть может, начального приближения $x_0 > 0$, является приближением с избытком.
2. Докажите, что при любом $x_0 > 0$ последовательность $(x_n)$ приближений, найденных по вавилонскому способу, стремится к $\sqrt{a}$.
3. К какому предely будет стремиться эта последовательность, если в качестве $x_0$ взять некоторое отрицательное число?

Чтобы оценить, насколько быстро числа $x_0, x_1, x_2, \dots$ приближются к $\sqrt{a}$, вычислим $\sqrt{19}$, взяв начальное приближение $x_0 = 4$. Вооружившись микрокалькулятором$^*$), находим

$$x_0 = 4,0000000; \quad x_1 = 4,3750000; \quad x_2 = 4,3589285; \quad x_3 = 4,3588989; \quad x_4 = 4,3588989.$$

Как видим, уже четвертое приближение не отличается (при вычислениях с семью знаками после запятой) от третьего. Естественно приять, что $\sqrt{19} \approx 4,3588989$.

Читатель может возразить, что незачем было «огород городить»: имея в руках микрокалькулятор, можно было набрать число 19 и затем, нажав всего одну кнопку $\sqrt{19}$, сразу получить тот же результат $\sqrt{19} \approx 4,3588989$. Однако согласитесь, что нас интересало не столько значение $\sqrt{19}$, сколько достоинства вавилонского способа. Они оказывались весмя значительными: уже после третьего повторения одотипной операции (или, как говоря, после третьей utepaши) мы получили значение $\sqrt{19}$ с семью верными знаками (см. задачу 4).

$^*$ Тем, у кого микрокалькулятор под рукой нет, придетя либо считать вручную, либо поверить написанному.

3 задачи
4. Пусть, применяя вавилонский способ, мы вычисляем последовательные приближения $x_0 > 0, x_1, x_2, \dots$ числа $\sqrt{a}$ с $k$ знаками после запятой, то есть okругляем каждый раз $(k+1)$-ю цифру. Докажите, что если приближения стабилизируются в точке $x_n$ (то есть $x_{n+1} = x_n$ с точностью до $10^{-k}$, но $x_n \geq x_{n-1} + 10^{-k}$), то ошибка приближения $\sqrt{a} \approx x_n$ меньше 0,75 $\cdot 10^{-k}$.
5. Сколько интересный нужно сделать, чтобы провода вычисления по вавилонскому способу с $k$ знаками после запятой, получить число $\sqrt{a}$ с $k$ верными знаками после запятой?

Что бы показать читателю превосходство человекаского интеллекта над любой машиной (в частности, над микрокалькулятором, который лишь выполняет волю человека, является его помощью), мы проведем вычисления с пятнадцатью знаками после запятой. С этой целью применяют найденное приближение числа $\sqrt{19}$ за новое исходное приближение $x_0$ (то есть положим $x_0 = 4,3588989$) и вычислим по вавилонскому способу следующее приближение $x_1 = \frac{1}{2} \left( x_0 + \frac{19}{x_0} \right)$. Положим $\frac{19}{x_0} = x_0 + h$, то есть

$$19 = (x_0)^2 + x_0 h. \quad (3)$$

Мы имеем

$$(x_0)^2 = (4,3588989)^2 = (4,358 + 8,989 \cdot 10^{-4})^2 = 4,358^2 + 2 \cdot 4,358 \cdot 8,989 \cdot 10^{-4} + 8,989^2 \cdot 10^{-8}.$$

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

$$18,992164 \quad 0,0078348124 \quad 0,00000080802121$$

мы можем (вручную, что совсем несложно) найти их сумму.

$$(x_0)^2 = 19 - 37,957879 \cdot 10^{-8}$$

и потому, подставляя в (3), имеем

$$4,3588989 h = 37,957879 \cdot 10^{-8},$$

откуда (с помощью микрокалькуля-

21

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

Задача и

14. Примените метод интераций к управлению (6), где $f(x)=0,9999x+0,0004$. Докажите, что если интерационный процесс решения, проводимый с четырьмя знаками после запятой, останавливается в точке $x_n$, то ошибка приближения $x^* \approx x_n$ применено равна единице, то есть комнительны не только знаки после запятой, но и целая часть приближения $x_n$. (Эти сообщения и использованы при построении примера 1; в этом примере $0,9999<f'(x)<1$ при $x>0,12$.)

15. Пусть функция $f$ удовлетворяет условиям $f(a)>a$, $f(b)<b$ и $|f'(x)|<q<1$ при $x \in [a; b]$. Тогда уравнение (6) имеет на отрезке $[a; b]$ единственный корень $x^*$. Докажите, что при решении уравнения (6) метод интераций

$$|x_{n+1}-x_n| \leq |x_1-x_0| \cdot q^n$$

$$|x^*-x_n| \leq |x_1-x_0| \cdot \frac{q^n}{1-q}.$$

16. Примените эти оценки к функция (5).

17. Решите метод интераций уравнения $0,6095+0,274 \sin x=x$ (пользовясь микрокалькулятором). После скольких интераций процесс останавливается? Сколько верных знаков имеет полученное приближение?

18. Решите метод интераций уравнения $\sqrt{1+x}=x$, взяв $x_0=0$. Сравните полученный результат с корнем, получаемым при «обчислом» решения этого irrationalного уравнения. Докажите, что $n$-е приближение имеет вид

$$x_n = \sqrt{1 + \sqrt{1 + \ldots + \sqrt{1}}} \quad (n \text{ единиц}).$$

IV

В задачах 8, 10 и 15 указаны условия, при выполнении которых метод интераций завершено приводит к цели. А как бы, если эти условия не выполнены?

Пусть рассматривается уравнение $g(x)=0$, где $g(a)<0$, $g(b)>0$, функция $g$ имеет на отрезке $[a; b]$ непрерывную производную и $g'(x)>0$ при $x \in [a; b]$. Таким образом, функция $g$ возвращает на отрезке $[a; b]$, и уравнение $g(x)=0$ имеет на этом отрезке единственный корень $x^*$. Что бы сделать применим метод интераций, обозначим через $p_1$ и $p_2$ такие положительные числа, что $p_1 \leq g'(x) \leq p_2$ на отрезке $[a; b]$. Затем темп теперь уравнение $g(x)=0$ равносильным ему уравнением $x+a \cdot g(x)=x$, где $a$ подберем так, чтобы функция

$$f(x)=x+a \cdot g(x)$$

удовлетворяла условиям задачи 15. (Проверьте, что это будет, например, при $a=-\frac{2}{p_1+p_2}$, $q=\frac{p_2-p_1}{p_2+p_1}$.) Таким образом, мы заменили уравнение $g(x)=0$ на равносильное уравнение $f(x)=x$, к которым метод интераций уже применим.

Если $g'(x)<0$ при $x \in [a; b]$ применим тот же прием. (В этом случае $p_1$ и $p_2$ отрицательны и $a=-\frac{2}{p_1+p_2} > 0$.)

Пример 2. Решим метод интераций уравнения

$$x^2-x=\cos x.$$

При $0 \leq x \leq 1$ левая часть неположителя, а правая положителя; поэтому на отрезке $[0; 1]$ корней нет. Переписав уравнение в виде

$$x^2-x-\cos x=0,$$

замечаем, что функция $g$, стояшая влевой части, имеет производную $g'(x)=2x-1+\sin x$, которая при $x \geq 1$ положительная, то есть $g$ возвращает на $[1; +\infty]$. Поскольку $g(1)<0$ и $g(2)>0$, на луче $[1; +\infty]$ имеетровно один корень расматриемого уравнения, причем он расположен на отрезке $[1, 2]$. С помощью микрокалькутора на отрезке $[1, 2; 1, 3]$. Функция $g'$ возвращает на $[1; +\infty]$ (поскольку ее производная $g''(x)=2+cos x$ положительная). Следовательно, $p_1 \leq g'(x) \leq p_2$ на отрезке $[1, 2; 1, 3]$, где $p_1=g'(1,2) \approx 2,332$, $p_2=g'(1,3) \approx 2,564$. Таким образом, $a=-\frac{2}{p_1+p_2} \approx -0,401$. Взяв для простоты $a=-0,4$, получаем уравнение (Окончание см. на с. 37)