demsp 7 авг 2018 в 22:33

Решение задачи о приближении иррациональных

24 мин

18K

Занимательные задачкиПрограммирование*Математика*

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

В сборнике Арнольда есть следующая задача

38. Вычислить сумму:

$\frac{ 1 }{ 1\cdot2 } + \frac{ 1 }{ 2\cdot3 } + \frac{ 1 }{ 3\cdot4 } + ... + \frac{ 1 }{ 99\cdot100 }$

(с ошибкой не более 1% от ответа)

Ниже представлен алгоритм для вычисления частичных сумм этого ряда на языке Scheme (Lisp), который позволяет производить вычисления в обыкновенных дробях

#lang racket
(define series_sum
 ( lambda (n)
  (if (= n 0) 0 
    (+ (/ 1 (* n (+ n 1))) (series_sum(- n 1)))
  ) ) )
(series_sum 10)
(series_sum 100)
(series_sum 1000)
(series_sum 10000)
(series_sum 100000)
(series_sum 1000000)

(define series_sum_1
 ( lambda (n)
  (if (= n 0) 0 
    (+ (/ 1.0 (* n (+ n 1.0))) (series_sum_1(- n 1.0)))
  ) ) )
(series_sum_1 10)
(series_sum_1 100)
(series_sum_1 1000)
(series_sum_1 10000)
(series_sum_1 100000)
(series_sum_1 1000000)

Два последних примера drRacket вычислил с ошибкой

Этот же алгоритм на Python

def series_sum(n):
	if n==0:
		return 0
	else:
		return 1.0/(n*(n+1.0))+series_sum(n-1.0)
 
print(series_sum(10))
print(series_sum(100))

Переведём периодическую десятичную дробь $inline$ в обыкновенную
$inline$
Домножим обе части на $10^{n}$ , где $inline$ равняется периоду десятичной дроби
$inline$
вычтем из данного равенства предыдущее
$99x=90 \rightarrow\ x=\frac{90}{99}=\frac{10}{11}$

Если последовательность частичных сумм имеет предел $inline$ , то говорят, что сумма ряда равна этому пределу $inline$

Если рассмотреть частичные суммы в обыкновенных дробях, то можно заметить, что сумма ряда равна

$\frac{ n }{ n + 1 }$

Доказательство из книги «Метод математической индукции»:
1. При $inline$ гипотеза верна, так как $S_{1}= \frac{ 1 }{ 2 }$
2. Предположим, что гипотеза верна и для $inline$ , т.е. что

$S_{k}= \frac{ 1 }{ 1\cdot2 } + \frac{1}{2\cdot3}+...+\frac{1}{k(k+1)}=\frac{k}{k+1}$

где $inline$ — некоторое натуральное число.
Установим справедливость и при $inline$

$S_{k+1}= \frac{ k+1 }{ k+2 }$

$S_{k+1}=S_{k} + \frac{ 1 }{ (k+1)(k+2) } = \frac{k}{k+1} + \frac{1}{(k+1)(k+2)} =\frac{k^{2}+2k+1}{(k+1)(k+2)}=\frac{k+1}{k+2}$

Последовательность частичных сумм имеет предел, который равен
$\lim \frac{n}{n+1}=\lim\frac{1}{1+\frac{1}{n}}=\frac{1}{1}=1$ при $n\to\infty$

Числа Фибоначчи

В следующей задаче требуется найти НОД двух соседних чисел Фибоначчи
43.Числа кроликов («Фибоначчи»), образуют последовательность $(a_{1}=1, 1, 2, 3, 5, 8, 13, 21, 34, ...,$ в которой $a_{n+2} = a_{n+1} + a_{n}$ для всякого $inline$ . Найти наибольший общий делитель чисел $a_{100}$ и $a_{99}$ .

Для решения данной задачи необходимо доказать, что два соседних числа Фибоначчи взаимно просты, то есть $НОД(a_{n+1},a_{n}) = 1$
иными словами $a_{n+1}$ и $a_{n}$ не имеют общих делителей (кроме единицы)

Доказательство из книги «За страницами учебника математики» [10-11]

Из равенства $u_{n+2} = u_{n+1} + u_{n}$ следует, что $НОД(u_{n+2},u_{n+1}) = НОД(u_{n+1},u_{n})$ . Пятясь таким образом назад, придём к $НОД(u_{2},u_{1}) = НОД(1,1) = 1$ , а потому два соседних числа Фибоначчи взаимно просты.

Пояснение

$НОД(u_{n+2},u_{n+1}) = НОД(u_{n+1},u_{n})$ по алгоритму Евклида
$НОД(u_{n+2},u_{n+1}) = НОД(u_{n+1},r)$
где $inline$ — остаток от деления $u_{n+2}$ на $u_{n+1}$
и в данном конкретном случае $r = u_{n}$ поскольку $u_{n+2} = u_{n+1} + u_{n}$

Доказательство, не использующее алгоритм Евклида

Пусть некоторое число $inline$ является делителем чисел $u_{n}$ и $u_{n+1}$ . Тогда и их разность $u_{n+1}-u_{n} = u_{n-1}$ будет делиться на $inline$ .
Пятясь таким образом назад, придём к тому, что на $inline$ будут делиться и $u_{n-2}$ и $u_{n-3}$ и так далее, а значит и $u_{1}=1$ должно делиться на $inline$ , а значит два соседних числа Фибоначчи взаимно просты

Похожий метод, метод перебора последовательности $F_{n}$ используется для доказательства тождества Кассини (ссылка на Wiki), которое выражается соотношением:
$F_{n-1}F_{n+1}-F_{n}^2= (-1)^n$

После перехода от $F_{n} \rightarrow F_{n-1}$ в тождестве
$F_{n+1}F_{n-1}-F_{n}^2=F_{n-1}^2-F_{n}F_{n-2}$
получим
$F_{n}^2-F_{n-1}F_{n+1} \rightarrow F_{n-1}^2-F_{n}F_{n-2}$
а значит единица в правой части исходного тождества меняет свой знак на противоположный

Для доказательства тождества
$F_{n+1}F_{n-1}-F_{n}^2=F_{n-1}^2-F_{n}F_{n-2}$
домножим левую и правую части уравнения $F_{n+1}=F_{n}+F_{n-1}$ на $F_{n-1}$ :
$F_{n+1}F_{n-1} = F_{n}F_{n-1}+F_{n-1}^2$

Вычтем из левой и правой части $F_{n}^2$ :
$F_{n+1}F_{n-1}-F_{n}^2=F_{n }F_{n-1}+F_{n-1}^2-F_{n}^2$
$F_{n+1}F_{n-1}-F_{n}^2=F_{n-1}^2-F_{n}^2+F_{n}F_{n-1}$
$F_{n+1}F_{n-1}-F_{n}^2=F_{n-1}^2-F_{n}(F_{n}-F_{n-1})$
а поскольку $F_{n}=F_{n-1}+F_{n-2} \rightarrow F_{n}-F_{n-1}=F_{n-2}$
произведя замену получим требуемое тождество

Поэтому $F_{n+1}F_{n-1}-F_{n}^2=F_{n-1}^2-F_{n}F_{n-2} |(-1)$
равносильно $F_{n}^2-F_{n+1}F_{n-1}=F_{n}F_{n-2}-F_{n-1}^2$

Иллюстрация перехода от младших членов последовательности Фибоначчи к старшим представлена ниже

$F_{1} \rightarrow F_{2}:$
$1 - 0 = 1 \rightarrow 1 - 2= -1$

$F_{2} \rightarrow F_{3}:$
$1 - 2 = -1 \rightarrow 4 - 3 = 1$

$F_{3} \rightarrow F_{4}:$
$4 - 3 = 1 \rightarrow 9 - 10 = -1$
и т.д.

Приближения к золотому сечению

В следующей задаче необходимо вычислить золотое сечение, $\frac {\sqrt{5} + 1}{2} \approx 1,618$ . [Это соотношение сторон открытки, остающейся себе подобной при отрезании квадрата, стороной которого является меньшая сторона открытки.]

53. Для последовательности чисел Фибоначчи $a_{n}$ задачи 43 найти предел отношения $\frac { a_{n+1} }{ a_{n} }$ при стремлении $inline$ к бесконечности:

$\frac { a_{n+1} }{ a_{n} } = 2, \frac {3}{2}, \frac {5}{3}, \frac {8}{5}, \frac {13}{8},\frac {21}{13}, \frac {34}{21}.$

Рассмотрим отрезки, представляющие собой разности двух соседних членов ряда $\frac { a_{n+1} }{ a_{n} }$

Четные члены ряда $\frac { a_{n+1} }{ a_{n} }$ представляют растущую последовательность $x_{n}$

$\frac{ 3 }{ 2 }, \frac{ 8 }{ 5 }, \frac{ 21 }{ 13 }, ...,$

Нечетные члены ряда $\frac { a_{n+1} }{ a_{n} }$ представляют убывающую последовательность $y_{n}$

$2 , \frac{ 5 }{ 3 }, \frac{ 13 }{ 8 }, ...,$

По лемме о вложенных промежутках (Курс дифференциального и интегрального исчисления, 38)

$c = \lim x_{n} = \lim y_{n}$

Для нашего ряда в точке $inline$ справедливо равенство $\frac { a_{n+2} }{ a_{n+1} } = \frac { a_{n+1} }{ a_{n} }$

Разделив $a_{n+2} = a_{n+1} + a_{n}$ на $a_{n+1}$ , получим уравнение $\frac{a_{n+2}}{a_{n+1}} = 1 + \frac{a_{n}}{a_{n+1}}$ .
Произведя замену $\frac{a_{n+2}}{a_{n+1}}=x , \frac{a_{n}}{a_{n+1}} = \frac{1}{x}$ , получим квадратное уравнение $x = 1 + \frac{1}{x}$ , положительным решением которого является золотое сечение.
Решение этого уравнения рассматривается в конце данной статьи

Если в программе geogebra соединить дугами окружности точки 2 и $\frac{3}{2}$ , $\frac{3}{2}$ и $\frac{5}{3}$ , $\frac{5}{3}$ и $\frac{8}{5}$ и т.д. — получим самоподобную фигуру

Для сравнения

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

В самом деле, так как треугольники ACD и ABE подобны, то AC:AB=AD:AE. Но AD=BC, а AE=AC, и поэтому AC:AB=BC:AC — уже известная нам пропорция золотого сечения.

А в правильном пятиугольнике отношение диагонали к стороне равно $\varphi$
ссылка

Вообще, существует стандартный алгоритм вычисления чисел Фибоначчи на Python
Этот алгоритм представлен на сайте Python.org

def fib(n):
	    a, b = 0, 1
	    while a < n:
		print(a)
		a, b = b, a+b
fib(100)

Приближения к $\varphi$ являются отношением суммы двух соседних чисел $inline$ и $inline$ к числу $inline$

def fib(n):
	    a, b = 0.0 , 1.0
	    while a < n:
		print((a+b)/b)
		a, b = b, a+b
fib(12)

На двенадцатом шаге получим приближение, равное 1.61805

Формула Бине использует $\varphi$ для вычисления $inline$ -ого числа Фибоначчи
$F_{n}=\frac{(\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n}{\sqrt {5}}$

Можно заметить, что второе слагаемое всегда меньше единицы при любом целом неотрицательном $inline$
Поэтому, зная, что формула Бине даёт целые числа, можно утверждать справедливость тождества, в котором данная дробь округляется до ближайшаго целого
$F_{n}=\frac{(\frac{1+\sqrt{5}}{2})^n}{\sqrt{5}}$

Кстати, $\varphi$ упоминается в учебнике SICP
Упражнение 1.35.
Покажите, что золотое сечение $\varphi$ (раздел 1.2.2) есть неподвижная точка трансформации $x \to 1 + 1/x$ , и используйте этот факт для вычисления $\varphi$ с помощью процедуры fixed-point.

Используя алгоритм вычисления факториала

(define ! 
 (lambda (n) 
  (if (= n 0) 
    1 
    (* n (! (- n 1))))))
(display (! 5))

задачу 1.35 можно решить так

(define fixed-point 
 (lambda (n) 
  (if (> n 10) 
    1 
    (+ 1 (/ 1.0 (fixed-point (+ n 1)))))))
(display (fixed-point 1) )

Эту задачу можно решить без использования рекурсии
Следующая программа выводит значения счётчика $inline$ в цикле

(do ((i 1 (+ 1 i)))
    ((> i 10))
  (display i)(newline))

Оператор set! позволяет переопределить значение глобальной переменной
Определим глобальную переменную fixed-point и будем переопределять значение данной переменной в цикле do c помощью оператора set!

(define fixed-point 1)
(do ((i 1 (+ 1 i)))
    ((> i 10))
   (set! fixed-point (+ 1 (/ 1.0 fixed-point)))   
  (display fixed-point)
  (newline))

Цепные дроби

Если в уравнении $x = 1 + \frac{1}{x}$ в правой части заменить x на $1 + \frac{1}{x}$ получим $x = 1 + \frac{1}{1 + \frac{1}{x}}$ . Продолжая производить замены, придём к представлению золотого сечения в виде цепной дроби

$1+ \frac{1}{1 + \frac{1}{1+ \frac{1}{1+ \frac{1}{1+ \frac{1}{1+...}}}}}$

Ниже представлен алгоритм (Python) для вычисления приближений к золотому сечению, использующий формулу $x \to 1 + \frac{1}{1 + \frac{1}{x}}$

arr=[1.0]
def foo(a):
	b=1.0+1.0/(1.0+1.0/a[len(a)-1])
	return b
arr.append(foo(arr)) #первый шаг
arr.append(foo(arr)) #второй шаг
arr.append(foo(arr)) #третий шаг
print (arr)

На десятом шаге получим приближение, равное 1.618033985

В книге «Задачи для детей от 5 до 15 лет» есть похожий пример
54. Вычислить бесконечную цепную дробь

$1+ \frac{1}{2 + \frac{1}{1+ \frac{1}{2+ \frac{1}{1+ \frac{1}{2+...}}}}}$

Решение

Рассмотрим уравнение

$\alpha = 1+ \frac{1}{2 + \frac{1}{ \alpha}}$

Согласно теоремам 236 и 235 из книги «Теория чисел»:

$\alpha = \frac{ P_{1}\alpha+ P_{0}}{Q_{1}\alpha+ Q_{0} }$

Составляем таблицу значений $P_{n}$ и $Q_{n}$ при $inline$

	1	2
P	1	3
Q	1	2

так что $\alpha = \frac{ 3\alpha + 1 }{ 2\alpha + 1}, 2\alpha^{2} - 2\alpha -1 = 0$

и поскольку $\alpha > 0 ,$ то

$\alpha = \frac{ 1 + \sqrt{3} }{ 2 }$

Золотое сечение может быть представлено в виде бесконечно вложенных радикалов, которые в некоторых случаях могут быть тождественны некоторому рациональному числу, например выражение
$x=\sqrt{2+ \sqrt{2 +\sqrt{2 + ...} } }$ тождественно двойке

Для того чтобы это увидеть, возведем обе части выражения в квадрат и отнимем число два:
$x^{2}-2=\sqrt{2+ \sqrt{2 +\sqrt{2 + ...} } }=x$
$x^{2}-x-2=0$
$x_{1}=2,x_{2}=-1$
Очевидно, что $inline$ не может являться значением исходного радикала.

Вообще, $a=\sqrt{a \sqrt{a\sqrt{a ...} } }$

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

$x^{2}=a\sqrt{a \sqrt{a\sqrt{a ...} } }$

$x^{2}=ax$

$display$

Пусть $inline$
Здесь показатели степеней предстваляют геометрическую прогрессию, то есть
$2^\frac{1}{2} \cdot 2^\frac{1}{4} \cdot 2^\frac{1}{8} ...$
При перемножении степеней с одинаковыми основаниями показатели степеней складываются

$2^{\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+... }$

Сумма геометрической прогрессии $S_{n} = \frac{1}{2}+\frac{1}{4}+\frac{1}{8}+...=1$

Легко понять, что $S_{n}$ отличается от $inline$ на
$(\frac{1}{2})^n$ и что эта разность становится сколь угодно малой или «стремится к нулю» при неограниченном возрастании $inline$

Python:

>>> def foo(n,a):
... 	temp=a
... 	while(n>0):
... 		a=temp*(a**0.5)
... 		n=n-1
... 	return a**0.5
... 
>>> print(foo(50,2))
#1.9999999999999993

Кстати, Сриниваса Рамануджан Айенгор установил некоторые зависимости между бесконечно вложенными радикалами и рациональными числами
Например, он установил, что
$\sqrt{1+2\sqrt{1+3\sqrt{1+ 4\sqrt{1+... } } } } = 3$
Вывод формулы:
$3 = \sqrt{9} = \sqrt{1+2\cdot4} = \sqrt{1+2\sqrt{16}}$
$16 = 1+15=1+3\cdot5=1+3\sqrt{25} = 1+3\sqrt{1+24}=1+3\sqrt{1+4\cdot6}=1+3\sqrt{1+4\sqrt{36}}$
$36 = 1+35=1+5\cdot7=1+5\sqrt{49} = 1+5\sqrt{1+48}=1+5\sqrt{1+6\cdot8}=1+5\sqrt{1+6\sqrt{64}}$
$64 = 1+63=1+7\cdot9=...$

А золотое сечение можно представить в виде бесконечно вложенных радикалов таким образом:
$\varphi=\sqrt{1+ \sqrt{1 +\sqrt{1 + ...} } }$
Попробуйте самостоятельно установить справедливость данного тождества
Данное выражение является частным случаем варианты $x_{n} = \sqrt{c+ \sqrt{c +... + \sqrt{c } } }$
Курс дифференциального и интегрального исчисления, 35 (2)

Таким образом $x_{n+1}$ получается из $x_{n}$ по формуле

$x_{n+1} = \sqrt{c + x_{n} }$

… По основной теореме, варианта $x_{n}$ имеет некий конечный предел $inline$ . Для определения его перейдём к пределу в равенстве

$x_{n+1}^{2} = c + x_{n};$

Мы получим, таким образом, что $inline$ удовлетворяет квадратному уравнению

$a^{2} = c + a$

Уравнение это имеет корни разных знаков; но интересующий нас предел $inline$ не может быть отрицательным, следовательно, равен именно положительному корню:

$a = \frac{ \sqrt{4c + 1} + 1}{2}$

То есть золотое сечение является одним из бесконечного множества пределов, являющихся решениями уравнения $a^{2} = c + a$
при различных $inline$

Далее в «Курсе дифференциального и интегрального исчисления», 35(3) рассматривается алгоритм вычисления обратного числа (такого числа 1/с, произведение которого на данное число с равно единице)

Пусть $inline$ — любое положительное число, и положим $x_{n} = cy_{n}$ . Написанное выше рекуррентное соотношение заменится таким:

$y_{n+1} = y_{n}(2 - cy_{n})$

Взяв начальное значение $y_{0}$ под условием: $0< y_{0}<\frac{1}{c}$ , получим, что $y_{n}$ , монотонно возрастая, будет стремиться к $\frac{1}{c}$ . По этой схеме на счётных машинах и вычисляется число, обратное $inline$ .

Алгоритм вычисления числа, обратного числу $inline$ на языке Python:

def reciprocal(c,y0,n):
	arr=[]
	for i in range(n):
		arr.append(y0)
		y0=y0*(2-c*y0)
        return arr

Функция reciprocal принимает на вход число $inline$ , начальное значение $y_{0}$ , количество итераций $inline$ и возвращает массив «приближений» к числу $\frac{1}{c}$ .
$y_{0} = 0.1$ при $inline$
$y_{0} = 0.01$ при $inline$
$y_{0} = 0.001$ при $inline$
и т.д.
Примеры работы функции reciprocal при $inline$ , равном 3

>>> reciprocal(3,0.1,5)
#[0.1,   0.17,   0.2533,   0.31411733000000003,   0.3322255689810133]

при $inline$ , равном 5

>>> reciprocal(5,0.1,5)
#[0.1,0.15000000000000002,0.18750000000000003,0.19921875000000003,0.19999694824218753]

при $inline$ , равном 8

>>> reciprocal(8,0.1,5)
#[0.1,0.12,0.1248,0.12499968,0.1249999999991808]

Геометрическая интерпретация

Вывод уравнения касательной

Уравнение прямой

$y=kx+b \; (I)$

Уравнение прямой, проходящей через точку $(x_{0},y_{0})$

$y_{0}=kx_{0}+b \; (II)$

Вычтем из уравнения (I) уравнение (II)

$y-y_{0}=kx- kx_{0} \leftrightarrow\ y=k(x-x_{0})+f(x_0)$

Так как угловой коэффициент касательной к графику дифференцируемой функции в точке с абсциссой $x_{0}$ равен $f'(x_{0})$ , то уравнение касательной имеет вид

$y=f'(x_{0})(x-x_{0})+f(x_0)$

Производная функции $inline$ в точке $x_{0}$ определяется формулой:

$\lim_{\Delta x\to 0} \frac{ \Delta y }{ \Delta x } =\lim_{\Delta x\to 0} \frac{ f(x_{0}+\Delta x)-f(x_{0}) }{ \Delta x }$

Для гиперболы

$f(x+ \Delta x) = \frac{1}{x+ \Delta x}$

$\Delta y = \frac{1}{x + \Delta x} - \frac{1}{x} = \frac{- \Delta x}{x(x+ \Delta x)}$

$\frac{ \Delta y }{ \Delta x } = \frac{- \Delta x}{x(x+\Delta x)\Delta x}= \frac{-1}{x(x+ \Delta x)}$

Знаменатель состоит из двух слагаемых, второе при малых значениях $\Delta x$ пренебрежимо мало по сравнению первым, значит

$\lim_{\Delta x\to 0}\frac{-1}{x^2+x\Delta x}=-\frac{1}{x^2}$

Для приближенного вычисления обратного числа здесь используется метод касательных (метод Ньютона), который приводится в книге «Digital Arithmetic»

Касательными $y=f'(x_{0})(x-x_{0})+ f(x_{0})$ к гиперболе $y=\frac{1}{x}$ являются функции
$y=-\frac{x-x_{0}}{x_{0}^2}+\frac{1}{x_{0}} \rightarrow y=\frac{2x_{0}-x}{x_{0}^2}$ , т.е.
$y = \frac{2}{x_{0}} - \frac{x}{x_{0}^{2}}$

Подставляя числа $inline$ вместо $x_{0}$ получим уравнения касательных

$display$

$y=1-\frac{x}{4}$

$y=\frac{2}{3}-\frac{x}{9}$

$y=\frac{1}{2}-\frac{x}{16}$

Если сдвинуть гиперболу вниз на $\alpha$ , то она пересечёт ось абсцисс в точке $\frac{1}{\alpha}$
Уравнение касательных преобразуется в $y = \frac{2}{x_{0}} - \frac{x}{x_{0}^{2}} - \alpha$
Далее, приравняв уравнение касательной к нулю и выразив $inline$ , получим уравнение $x= x_{0} - \frac{f(x_{0})}{f'(x_{0})}$

Вместо $f(x_{0})$ подставим $\frac{1}{x_{0}} - \alpha$
Вместо $f'(x_{0})$ подставим $-\frac{1}{x_{0}^{2}}$

Получим выражение $x= x_{0} + (\frac{1}{x_{0}}-\alpha) x_{0}^{2}$
Раскрыв скобки, получим $x= x_{0} + x_{0}-\alpha x_{0}^{2}$

Подставим $inline$ в уравнение $x=x_{0}(2-\alpha x_{0})$ и посмотрим, какие значения будет «пробегать» $inline$ .
При $\alpha=2$ получим приблизительные значения $inline$

Подставив эти значение в уравнение $y=\frac{2}{x_{0}}-\frac{x}{x_{0}^{2}}-2$ , получим касательные, которые с каждой новой итерацией всё ближе приближаются к искомой величине $inline$

$y= 0.111 - \frac{x}{0.897}$

$y= 0.222 - \frac{x}{0.81}$

$y= 0.816 - \frac{x}{0.504}$

$y= 0.857 - \frac{x}{0.49}$

$y= 1.5 - \frac{x}{0.326}$

$y= 2 - \frac{x}{0.25}$

Заголовок спойлера

Модифицированный метод касательных

Преобразуем $\frac{1}{x}-\alpha =0 \rightarrow \frac{1}{x}=\alpha \rightarrow 1=\alpha\cdot x$
$\alpha\cdot x -1 =0$
и возведём это уравнение в квадрат, чтобы получить квадратную параболу
$\alpha^2 x^2 - 2\alpha x + 1 =0$
Все параболы данного вида будут иметь с осью абсцисс одну общую точку (точку касания), равную $\frac{1}{\alpha}$
Для того, чтобы найти приближения к точке касания, необходимо взять производную этой функции. Она будет равна $2\alpha^2 x - 2 \alpha$
Тогда касательными к параболе будут функции вида

$y = (2\alpha^2 x_{0} - 2 \alpha)(x-x_{0})+(\alpha^2 x_{0}^2-2\alpha x_{0} + 1)$

$y = (2\alpha^2 x_{0} - 2 \alpha)x - \alpha^2 x_{0}^2 + 1$

Пусть требуется найти приближения к $\frac{1}{3}$
Тогда параболой будет функция $9x^{2}-6x+1$

Касательными будут функции
$y= (18 x_{0}-6)x-9x_{0}^2+1$
В точке $x_{0}=0$ касательной будет $inline$
Первым приближением будет $\frac{1}{6} \approx 0.17$
Подставив это значение в уравнение касательной, получим
$y=-3x+ \frac{3}{4}$
Касательная пересечёт ось абсцисс в точке $-3x+ \frac{3}{4}= 0 \rightarrow x=\frac{1}{4}=0.25$
Приравняв $inline$ к нулю и выразив $inline$ в уравнении касательной, получим уравнение, позволяющее получать новые приближения

$x=\frac{9x_{0}^2-1}{18x_{0}-6}$

Напишем функцию, которая вычисляет данное значение при различных $x_{0}$
Python:

def foo(x_null):
    x=(9.0*x_null**2.0-1.0)/(18.0*x_null-6.0)
    return x 
print (foo(foo(foo(foo(foo(foo(foo(0))))))))

Scheme

(define (foo x)( /(-(* 9 (* x x))1)(- (* 18 x)  6) ))
(display (foo(foo(foo(foo(foo(foo(foo 0))))))))

Добавим в функцию переменную, равную количеству рекурсивных вызовов функции

def foo(x_null,i):
    i=i-1
    x=(9.0*x_null**2.0-1.0)/(18.0*x_null-6.0)
    print(x)
    if i>=0:
        foo(x,i)
foo(0,7)

получим приближение, равное $inline$
Далее этот алгоритм используется для подсчёта приближений в обыкновенных дробях на Scheme

Обработка переменных в цикле производится следующим образом

(define (do_cycle n)
  (do ((i 1 (+ i 1))) ((> i n)  )
   (display i)(display " ")   ))
(do_cycle 10)

Далее do_cycle используется для вычисления приближений в цикле

(define (foo x)( /(-(* 9 (* x x))1)(- (* 18 x)  6) ))
(define x0 0)
(define (do_cycle n)
  (do ((i 1 (+ i 1))) ((> i n)  )
   (foo x0)(set! x0 (foo x0))   ))
(do_cycle 7)
(display x0)

Если ограничиться однократным вычислением производной в точке начального приближения, то пересечения прямых, параллельных касательной $inline$ с осью абсцисс дадут новые приближения
Подставив значение $-6x+1=0 \rightarrow x= \frac{1}{6}$ в уравнение параболы $9x^{2}-6x+1$ получим значение, на которое требуется сдвинуть касательную

Новой касательной будет $inline$

а следующим приближением будет точка пересечения этой касательной с осью абсцисс
$inline$

Подставив это значение в уравнение параболы $9x^{2}-6x+1$ получим значение, на которое необходимо сдвинуть касательную по оси ординат

Напишем программу, реализующую данный метод
Пусть proxima — это последовательные приближения
b_coef — это коэффициент, на который сдвигается касательная по оси абсцисс
parabola() — это параболическая функция

proxima=0.17
b_coef=1.0
def parabola(x):
    return 9.0*x*x-6.0*x+1.0 
i=0
while i<=100000:
    b_coef = b_coef+parabola(proxima)
    proxima = b_coef/6.0
    i=i+1
print(proxima)

Output
Результат $\approx 0.3333$

Число $inline$ в уравнении линейной функции $inline$ называется свободным коэффициентом.
Предположим, что свободные коэффициенты касательных являются рациональными числами, то есть $b \in \mathbb {Q}$ . Тогда $proxima \in \mathbb {Q}$ , поскольку является результатом деления коэффициента $inline$ на натуральное число. При подстановке proxima в $inline$ получим число рациональное. Тогда $b \in \mathbb {Q}$ по предположению.

Следовательно, вычисления можно выполнять в обыкновенных дробях

(define proxima 1/6)
(define b_coef 1)
(define (parabola x)(  +( -(* 9 (* x x))(* 6 x))1  ) )

(define (do_cycle n)
  (do ((i 1 (+ i 1))) ((> i n)  )
  (set! b_coef (+ b_coef (parabola x0)))
  (set! proxima (/ b_coef 6)) 
     ))
(do_cycle 5)
(display proxima)

Здесь для подсчёта приближений в обыкновенных дробях, по видимому, используется механизм длинной арифметики

Извлечение квадратного корня

Существует несколько методов для приближенного вычисления (вычисления приближений) квадратного корня из натурального числа

Следующий алгоритм использует итерационный метод Герона

$x_{n+1} = \frac{1}{2}(x_{n}+\frac{a}{x_{n}})$

def square_root(a,n):        # a - подкоренное значение, n - количество циклов
        x0=1                      # первое приближение равно 1 
	arr=[]
	for i in range(n):
		arr.append(x0)       # добавляем к массиву новые приближения
		x0=0.5*(x0+a/x0)  # вычисляем приближения по формуле Герона
        return arr
print square_root(2,10)

Output:
1.4142135623730949

Вычисление квадратного корня с помощью цепных дробей использовал Рафаэль Бомбелли

Чтобы найти значение $\sqrt{n}$ , сначала определим его целое приближение: $\sqrt {n}=a\pm r$ , где $inline$ . Тогда $n=(a\pm r)^{2}=a^{2}\pm 2ar+r^{2}$ . Отсюда несложно вывести, что $r={\frac {|n-a^{2}|}{2a\pm r}}$ . Повторно подставляя полученное выражение в формулу $\sqrt {n}=a\pm r$ , мы получаем разложение в цепную дробь:

$a\pm {\frac {|n-a^{2}|}{2a\pm {\frac {|n-a^{2}|}{2a\pm {\frac {|n-a^{2}|}{2a\pm \cdots }}}}}}$

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

arr=[]
def square_root(n,a,n_count): # n-подкоренное значение, a - целая часть корня 
    x0=a                               # первое приближение равно a
    global arr
    for i in range(n_count): # результат будет больше искомой величины на a
        arr.append(x0-a)  # вычитаем a
        x0=2*a+(n-a*a)/x0
    
square_root(2.0,1.0,10) 
print(arr[9])

Output:
1.4142139267767408

Способ выделения целой части позволяет представить иррациональное число в виде бесконечной цепной дроби с единицами в числителях (частыми числителями, равными единице)
Вот пример разложения в цепную дробь числа $\sqrt{5}$ из книги «Алгебра»

$\sqrt{5}-2= \frac{(\sqrt{5}-2)(\sqrt{5}+2)}{\sqrt{5}+2}=\frac{1}{\sqrt{5}+2}$

Таким образом, $\sqrt{5} = 2+\frac{1}{\sqrt{5}+2}$

Выделим целую часть числа $\sqrt{5}+2:E(\sqrt{5}+2)=4$ . Значит, $\sqrt{5}+2$ можно представить в виде $4 + \alpha$ . Ясно, что $\alpha = \sqrt{5}+2-4=\sqrt{5}-2$ , поэтому $\sqrt{5}+2=4+\sqrt{5}+2$ . Снова уничтожим иррациональность в числителе второго слагаемого:

$\sqrt{5}-2 = \frac{1}{\sqrt{5}+2}$

В итоге получилось:

$\sqrt{5} = 2 + \frac{1}{4+\frac{1}{\sqrt{5}+2}}$

Проделаем еще один аналогичный шаг:

$\sqrt{5} = 2 + \frac{1}{4+\frac{1}{4+\frac{1}{\sqrt{5}+2}}}$

Нетрудно заметить, что процесс выделения целой части и образования цепной дроби в данном примере не имеет конца. В каждом новом знаменателе будет появляться $inline$ и слагаемое $\sqrt{5}-2$ . Поэтому ясно, что $\sqrt{5}$ представляется в виде бесконечной цепной дроби:

$\sqrt{5} = [2, 4, 4, 4, ...]$

Гипотеза

Если $d \in \mathbb{N}, \sqrt{d} \notin \mathbb{N}$ , то цепная дробь числа $\sqrt{d} + [\sqrt{d}]$ чисто периодическая.
Эту гипотезу доказал Эварист Галуа

Т.е. если к непериодической части дроби $[1;2,2,2,...] = \sqrt{2}$ прибавить целую часть $[\sqrt{2}] =1$ , то получится чисто периодическая дробь $inline$ .

$\sqrt{3} = [1;1,2,...];$
$\sqrt{3}+1 = [2,1,...]$

$\sqrt{5} = [2;4,4,4,...];$
$\sqrt{5}+2 = [4,4,4,...]$

$\sqrt{6} = [2;2,4,...];$
$\sqrt{6}+2 = [4,2,...]$

$\sqrt{13} = [3;1,1,1,1,6,...];$
$\sqrt{13}+3 = [6,1,1,1,1,...]$

Вычисление в облаке WolframAlpfa

WolframAlpfa производит вычисление цепных дробей с помощью операции continued fraction
Вычислим значение $\sqrt{3}$
ссылка
Вычислим значение $\sqrt{3}+1$
ссылка

Если в разложении корня по методу Бомбелли

$\sqrt{n} =a\pm {\frac {|n-a^{2}|}{2a\pm {\frac {|n-a^{2}|}{2a\pm {\frac {|n-a^{2}|}{2a\pm \cdots }}}}}}$

к первому слагаемому прибавить $inline$ , получим чисто периодическую дробь

$\sqrt{n}+a =2a\pm {\frac {|n-a^{2}|}{2a\pm {\frac {|n-a^{2}|}{2a\pm {\frac {|n-a^{2}|}{2a\pm \cdots }}}}}}$

Остаётся привести дробь к виду, в котором числителями дробей являются единицы

Разделим числитель и знаменатель дроби на $|n-a^{2}|$ , получим выражение

$\sqrt{n}+a =2 a\pm {\frac {1}{\frac{2a}{|n-a^{2}|} \pm {\frac {1}{2a \pm {\frac {1}{\frac{2a}{|n-a^{2}|}\pm \cdots }}}}}}$

Таким образом

$\sqrt{2}+1 = 2+ \frac{1}{\frac{2}{1} + \frac{1}{2 + \frac{1}{\frac{2}{1}+...} } } =[2,2,2,...]$

$\sqrt{3}+1 = 2+ \frac{1}{\frac{2}{2} + \frac{1}{2 + \frac{1}{\frac{2}{2}+...} } } =[2,1,...]$

$\sqrt{5}+2 = 4+ \frac{1}{\frac{4}{1} + \frac{1}{4 + \frac{1}{\frac{4}{1}+...} } } =[4,4,4,...]$

$\sqrt{6}+2 = 4+ \frac{1}{\frac{4}{2} + \frac{1}{4 + \frac{1}{\frac{4}{2}+...} } } =[4,2,...]$

$\sqrt{13}+3 = 6+ \frac{1}{\frac{6}{4} + \frac{1}{6 + \frac{1}{\frac{6}{4}+...} } } =[6,\frac{3}{2},...]$

Напишем программу, вычисляющую приближение цепной дроби $[6,\frac{3}{2},...]$

#lang racket
(define continued_fraction
 ( lambda (n)
  (if (= n 0) 1 
    (+ 6 (/ 1  (+ 3/2 (/ 1 (continued_fraction(- n 1)))))) 
  )))
(continued_fraction 4)

codepad.org
На четвёртом шаге получаем $6\frac{3818}{6305}$ , что равно $inline$ в то время как $\sqrt{13}+3 \approx 6.6055512...$ .

Для поиска приближений к квадратному корню можно использовать метод касательных
Для вычисления $\sqrt{2}$ рассмотрим уравнение
$x^{2}-2=0$
$x^{2}=2$
$x=\pm\sqrt{2}$
Эта парабола пересекает ось абсцисс в точках $\pm\sqrt{2}$

Проведём касательную к параболе в точке с координатами (1,-1)
Производная функции $y=x^{2}-2$ равна $inline$
Значение функции в точке $x_{0} = 1^2-2=-1$
Т.о. касательной к параболе $x^{2}-2=0$ в точке (1,-1) будет прямая $inline$ , которая пересечёт ось абсцисс в точке $inline$

Проведем касательную в точке $x_{0} = 1.5$
Такой касательной будет прямая $y = 3x-\frac{17}{4}$
Эта касательная пересечёт ось абсцисс в точке $\frac{17}{12}$ , что равняется корню из двух с точностью до второго знака после запятой

Следующая касательная пересечёт ось абсцисс в точке $\frac{3462}{2448}$ , что равняется корню из двух с точностью до пятого знака после запятой

Рассмотрим ещё один метод — метод половинного деления или метод бисекции

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

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

Если произведение значений функции на концах отрезка меньше нуля, то эти значения имеют разные знаки
Определим сперва функцию $inline$

def foo(x):
    return x*x-2

и саму функцию бисекции bisection(a,b,i), где a,b — это границы отрезков, i — это количество итераций

def bisection(a, b, i):
    i=i-1 # уменьшаем количество итераций
    middle=(a+b)/2.0 # делим отрезок пополам
    print(middle)
    if i>0: 
        if(foo(a)*foo(middle)<0): # определяем нужный отрезок
            bisection(a,middle,i)
        if(foo(middle)*foo(b)<0):
            bisection(middle,b,i) #загружаем в функцию новые значения 
bisection(1.0, 2.0, 15)

Output:
1.414215087890625

Уравнения Пелля

Приближения к квадратному корню можно искать с помощью уравнений Пелля.

Пусть натуральное число $inline$ не является квадратом. Легко видеть, что $\sqrt{a}$ не выражается отношением натуральных чисел, т.е. не существует такой обыкновенной дроби $\frac{x}{y}$ , что $(\frac{x}{y})^2=a$ . Другими словами, если натуральное число $inline$ не является точным квадратом, то уравнение $inline$ не имеет решения в натуральных числах.
Попытаемся в этом случае выразить $\sqrt{a}$ отношением натуральных чисел приближённо. Если $\sqrt{a} \approx \frac{x}{y}$ , то $x^2-ay^2 \approx 0$ . Самое близкое к нулю натуральное число — это единица. Поэтому дело сводится к решению в натуральных числах диофантова уравнения

$display$

которое носит название… уравнения Пелля

При подстановке $inline$ в уравнение
$x^{2}=2y^{2} \pm 1$
получим тождества
$1^2=2 \cdot 1^2-1$
$3^{2}=2 \cdot 2^{2} + 1$
$7^{2}=2 \cdot 5^{2} - 1$
Здесь каждая новая пара выражается через предыдущую подстановкой в рекуррентную формулу
$y_{n+1} = x_{n}+y_{n}$
$x_{n+1} = y_{n+1}+y_{n}=x_{n}+y_{n}+y_{n}=x_{n}+2 \cdot y_{n}$
Следующая программа использует данные соотношения для вычисления приближений к корню из двух

x0=1
y0=1
x=0 
y=0 
i=0
while i<=6:
    y=x0+y0
    x=2*y0+x0
    x0=x
    y0=y
    i=i+1 
print(x)
print(y)

Получившиеся приближение $\frac{577}{408}$ было известно ещё математикам древней Индии

Указания к решению квадратного уравнения

Полином $inline$ ой степени от переменной $inline$ есть сумма вида $P(x)=c_{0}+c_{1}x^{1}+...+c_{n}x^{n}$
Из теоремы Безу:

остаток от деления полинома $inline$ на полином первой степени $inline$ равен $inline$

следует, что если остаток равен нулю, то число $inline$ является решением уравнения $inline$ , поскольку $inline$ , где $inline$ — это полином степени $inline$ от переменной $inline$

Квадратное уравнение $inline$ можно представить как $(x-x_{1})(x-x_{2})=0$ , где $x_{1}$ и $x_{2}$ являются корнями квадратного уравнения

По теореме Виета

сумма корней приведённого квадратного уравнения равна второму коэффициенту с противоположным знаком, а их произведение равно свободному коэффициенту

$x_{1}+x_{2} = -p$
$x_{1} \cdot x_{2} = q$
поскольку
$(x-x_{1})(x-x_{2}) = x^2-xx_{2}-xx_{1}+x_{1}x_{2}=x^2-(x_{1}+x_{2})x+x_{1}x_{2}$
Значит сумма и произведение корней уравнения $inline$ равны
$x_{1}+x_{2}=1$
$x_{1}x_{2}=-1$

По формуле сокращенного умножения квадрат разности корней
$(x_{1}-x_{2})^2=x_{1}^2-2x_{1}x_{2}+x_{2}^2=$
$=x_{1}^2+2x_{1}x_{2}+x_{2}^2-4x_{1}x_{2}= (x_{1}+x_{2})^2-4x_{1}x_{2}$
Подставив числовые значения в уравнение, получим
$(x_{1}+x_{2})^2-4x_{1}x_{2}= 1-4(-1)=5$
Значит
$(x_{1}-x_{2})^2=5$
$x_{1}-x_{2}= \sqrt{5}$
Решив систему уравнений
$x_{1}-x_{2}= \sqrt{5}$
$x_{1}+x_{2}=1$
в ответе получим золотое сечение
$2x_{1}= \sqrt{5}+1 \rightarrow x_{1}=\frac{\sqrt{5}+1}{2}$

Подробнее об этом методе решения можно прочитать в статье, посвященной резольвеньте алгебраического уравнения

Вершина параболы $inline$ лежит в точке с координатой $\frac{-b}{2a}= 0.5$
Точки пересечения параболы с осью абсцисс симметричны относительно вершины
Пускай начальные значения $x_{1}=0$ и $x_{2}=1$
Поскольку произведение корней является отрицательным числом, значит $x_{1}<0$ и $x_{2}>1$
Пускай расстояние между корнями увеличивается на $inline$ до тех пор, пока произведение не превысит единицу (по модулю)

def foo(x1,x2,step):
    x1=x1+step
    x2=x2+step
    if x1*x2<1:
        foo(x1,x2,step)
    else:
        print(x1-step)               
foo(0,1,0.1)

Получим приближение $\phi \approx 1.6$
При уменьшении длины шага $inline$ получим $\phi \approx 1.61$
При $inline$ получим $\phi \approx 1.618$

P.S.
Следующая задача из сборника Арнольда рассматривается в статье журнала «Квант» Удивительные приключения периодических дробей

27. Доказать, что остаток от деления числа $2^{p-1}$ на простое нечетное число
$inline$ равен $inline$
(примеры: $2^{2} = 3a+1, 2^{4}=5b+1, 2^{6}=7c+1, 2^{10} -1 = 1023 = 10 \cdot 93)$ .

P.P.S. Статья, в которой содержится информация о цепных дробях «Об одной задаче, которую больше не предлагают на собеседовании» ссылка

Книги

Задачи для детей от 5 до 15 лет В. И. Арнольд
Курс дифференциального и интегрального исчисления Г. М. Фихтенгольц
Теория чисел А. А. Бухштаб
За страницами учебника математики Н. Я. Виленкин, Л. П. Шибасов, З. Ф. Шибасова
Алгебра Н. Я. Виленкин, Р. С. Гутер, С. И. Шварцбурд
Что такое производная Виленкин Н., Мордкович А., журнал «Квант»
Метод математической индукции И.С. Соминский
Числа Фибоначчи Н. Н. Воробьёв
Уравнения Пелля Сендеров В., Спивак А., журнал «Квант»
Золотое сечение Бендукидзе А. Д., журнал «Квант»
Что такое математика? Курант Р., Роббинс Г.
Digital Arithmetic Ercegovac Milos D., Lang Tomas
Cайты
math.stackexchange.com
mathhelpplanet.com

Теги:

Хабы: