На языке векторов v_n=(p_n, q_n) это соответствует линейному соотношению —
v_{n+1}=a_{n+1}v_n + v_{n-1}.
Потому что мы смотрим на образ вектора (1, a_{n+1}) под действием всей предыдущей матрицы.
v_{n+1}=a_{n+1}v_n + v_{n-1}.
Потому что мы смотрим на образ вектора (1, a_{n+1}) под действием всей предыдущей матрицы.
И я помню, как в своё время меня удивили рекуррентные соотношения на подходящие дроби — почему-то одинаковые для числителей и знаменателей:
Так вот — потому что это на самом деле соотношения на вектора v_n, у которых числители p_n и знаменатели q_n это координаты.
Я тут пользуюсь случаем порекламировать замечательную брошюру В.И. Арнольда, "Цепные дроби" (https://www.mccme.ru/free-books/mmmf-lectures/book.14-full.pdf ) — с соответствующей картинкой на с. 7:
Так вот — после такой линейной интерпретации, например, становится очень понятно, почему разница соседних подходящих дробей это плюс-минус единица, делённая на произведение знаменателей:
Потому что в числителе разности дробей
a/b-c/d = (ad-bc)/bd
стоит определитель ad-bc — он же ориентированная площадь параллелограмма, натянутого на вектора (a,b) и (c,d):
a/b-c/d = (ad-bc)/bd
стоит определитель ad-bc — он же ориентированная площадь параллелограмма, натянутого на вектора (a,b) и (c,d):
Когда мы прибавляем к одному из векторов другой, умноженный на константу, площадь не меняется; когда меняем их местами — меняет знак.
Математические байки
Photo
Нет, конечно, из рекуррентных соотношений это тоже немедленно следует, но это объяснение, мне кажется, более правильное.
Математические байки
Когда мы прибавляем к одному из векторов другой, умноженный на константу, площадь не меняется; когда меняем их местами — меняет знак.
Конечно же, ещё лучше сказать, что числитель
p_{n-1} q_n -p_n q_{n-1}
это определитель нашей матрицы A_n, который тем самым равен произведению определителей R_n — каждый из которых равен (-1).
p_{n-1} q_n -p_n q_{n-1}
это определитель нашей матрицы A_n, который тем самым равен произведению определителей R_n — каждый из которых равен (-1).
Так вот — а давайте теперь посмотрим на наши модифицированные цепные дроби, у которых каждый раз не "+1/что-то там", а "-a^2/что-то там".
Если смотреть с точки зрения "модифицированного алгоритма Евклида", то после j-го вычитания мы не просто меняем местами координаты, а умножаем одну из них на c_j.
Если смотреть с точки зрения произведения матриц — то мы будем перемножать матрицы вида
Первая матрица отвечает операции a_n+(...), а вторая — переходу x->c_{n+1}/x.
И определитель у такой матрицы равен (-c_{n+1}) — соответственно, мы получаем в качестве числителя разности "подходящих дробей" (получающихся обрубанием на a_n)
P_{n-1}/Q_{n-1} - P_n/Q_n
произведение (-c_j).
P_{n-1}/Q_{n-1} - P_n/Q_n
произведение (-c_j).