Теория цепных дробей - (реферат)
p>2. 1. Оценка погрешности при замене действительного числа его подходящей дробью. Теорема 1: Для любых двух соседних подходящих дробей и к действительному числу имеет место неравенство , и если , то . Доказательство: Если , подходящие дроби и , из которых одна четная, а другая – нечетная, лежат по разные стороны от (так как точное значение непрерывной дроби находится между двумя соседними подходящими дробями), и поэтому расстояние от до любой из них меньше длины интервала, образованного этими двумя подходящими дробями, то есть .Если =, то .
Теорема 2: Для любой подходящей дроби к действительному числу справедливо неравенство:
Доказательство: Если =, то получаем, что левая часть неравенства равна нулю, в то время как правая часть всегда больше нуля. Поэтому при = неравенство выполняется. Пусть , то есть существует подходящая дробь . При k>0 и согласно предыдущей теореме имеем:
.
Отдельно рассмотрим случай k=0. Если , то
.
Теорема 3: Если , то .
Из теорем 1-3 получаем следующие оценки погрешности:
, ,
из которых первая является наиболее точной, а последняя – наиболее грубой.
2. 2. Приближение действительного числа подходящими дробями. Решение поставленной задачи начнем с рассмотрения нескольких примеров. Пример 1: Рассмотрим задачу, аналогичную той, с которой встретился голландский математик Христиан Гюйгенс (1629-1695) при построении модели солнечной системы с помощью набора зубчатых колес и которая привела его к открытию ряда важных свойств непрерывных дробей. Пусть требуется, чтобы отношение угловых скоростей двух зацепляющихся зубчатых колес II и I было равно . Так как угловые скорости колес обратно пропорциональны числам зубцов, то отношение чисел зубцов колес I и II должно быть равно . Если – несократимая дробь с большим числителем и знаменателем, например, , то для точного решения задачи возникает техническая трудность изготовления колес с большим количеством зубцов. Задачу можно технически упростить при помощи колес с меньшим количеством зубцов. При этом важно, чтобы отношение этих чисел было, по возможности, ближе к заданному отношению. Хорошего удовлетворения поставленных требований можно добиться, если воспользоваться непрерывными дробями. Пусть, например, поставлено требование заменить N и n меньшими числами и так, чтобы и чтобы отношение было, по возможности, ближе к . Применяя аппарат цепных дробей, можем дать следующее решение этой задачи: разлагаем в непрерывную дробь и берем ее подходящую дробь с наибольшим знаменателем, не превышающим 100. Получаем, =(1, 2, 3, 7, 8, 2)
Составляя схему, находим:
1
2
3
7
8
2
1
3
10
73
594
1261
1
2
7
51
415
881
Поставленному условию удовлетворяет подходящая дробь . При этом допущенная погрешность , то есть весьма незначительна. Ответ: .
Для иррационального по существу возможно лишь приближенное решение задачи. Пример 2: Как мы уже определили ранее . Вычислим с точностью до 0, 001. Для решения придется найти такую подходящую дробь разложения , чтобы . Сделаем это, используя схему:
3
3
6
3
3
10
63
199
1
3
19
60
Очевидно, нам достаточно взять , так как 19·60>1000. Это значение будет равно с точностью до 0, 001, причем с недостатком, так как – подходящая дробь нечетного порядка. Мы можем представить в виде десятичной дроби, причем имеем право взять 3 знака после запятой, так как является приближенным значением для с точностью до 0, 001. Получаем (мы округляем по избытку, так как является приближенным значением с недостатком, однако, не можем теперь сказать, будет ли 3, 316 приближенным значением с недостатком или избытком). Решенные задачи в более общем виде формулируются так:
Найти рациональное приближение к действительному со знаменателем в виде наиболее близкой к подходящей дроби. Для этого надо взять подходящую дробь для с наибольшим знаменателем, не превышающим n. Найти рациональное приближение к действительному числу с возможно меньшим знаменателем так, чтобы погрешность не превосходила (то есть с точностью до ). Для этого, пользуясь аппаратом цепных дробей, находим подходящую дробь с наименьшим знаменателем так, чтобы .
2. 3. Теорема Дирихле.
Выше мы нашли оценку погрешности, возникающей при замене любого действительного числа рациональными дробями определенного типа, а именно: подходящими дробями. А сейчас рассмотрим некоторые сравнительно простые результаты, показывающие как обстоит дело с приближением действительных чисел рациональными числами, не предрешая заранее, что эти рациональные числа будут подходящими дробями. Пусть – произвольное действительное число. Из теории десятичных дробей следует существование рационального числа такого, что . поставим вопрос о возможности таких приближений рациональными числами , при которых точность приближения будет оценена не величиной , а величиной, в раз меньшей, то есть вопрос о нахождении рациональных чисел таких, что , где – любое заранее положительное число. Например, можно поставить задачу нахождения такого рационального приближения к , чтобы точность приближения была в 1000 или в 1000000 раз лучшей, чем величина, обратная знаменателю. Это соответствует выбору =1000 или =1000000. оказывается, что как бы велико ни было , можно найти рациональную дробь , приближающую с точностью до , причем и это является самым интересным, дробь мы можем выбрать так, что . Теорема Дирихле: Пусть и – действительные числа; существует несократимая дробь , для которой , (или: существует такая пара взаимно простых целых чисел a и b, что , ). Доказательство: Теорему легко доказать с помощью аппарата цепных дробей. Пусть подходящая дробь числа ; выберем наибольший из знаменателей , не превышающий , то есть наибольшее k, чтобы и положим =. Рассмотрим два случая: не является последним знаменателем, то есть существует такое, что
2) – знаменатель последней подходящей дроби разложения , то есть =. Тогда при a=, b=, имеем: .
Теорема доказана.
Сам Дирихле дал другое доказательство, использовав в нем принцип, который носит теперь имя Дирихле: при распределении N объектов между N-1 ящиками хотя бы в одном ящике должно находиться 2 объекта. Приведем это доказательство. Пусть , рассмотрим совокупность t+2 чисел, состоящую из 1 и значений дробных частей для x=0, 1, …, t (причем =-, ). Очевидно, каждое из чисел этой совокупности принадлежит точно одному из t+1 промежутков , , …, , из которых первые t являются полусегментами, а последний сегментом.
————————————————————————————————
0 1
Так как чисел у нас t+2, то (согласно принципу Дирихле) обязательно найдется такой промежуток, который содержит 2 числа из совокупности и 1. Разность этих двух чисел не превосходит длину содержащего их промежутка, то есть . Если такими числами являются и , то . Пусть и , . Так как , то , ). Если и 1 принадлежат одному промежутку, то
Пусть в таком случае , . Очевидно, и здесь , так что , ).
Теорема доказана.
Рассмотрим пример применения теоремы Дирихле.
Найти рациональное приближение к с точностью до .
Решение: Разложим в цепную дробь.
=2 -2 …
=(2, 4, 4, 4, …)=(2, (4)).
Находим подходящие дроби:
2
4
4
4
4
4
…
2
9
38
161
682
…
…
1
4
17
72
305
1929
…
Наибольший знаменатель, меньший чем 100, при =305. Искомая дробь равна ; .
Подходящие дроби как наилучшие приближения.
Приближение подходящей дробью дает большую точность при значительно меньшем знаменателе, чем приближение десятичной дробью. Покажем это. Округляя десятичное выражение действительного до n–го знака после запятой, мы тем самым представляем приближенно дробью со знаменателем , причем погрешность , если же подходящая дробь к , то , так что при сколько-нибудь значительном q величина во много раз меньше, чем . Пример: Десятичное выражение числа в виде рациональной дроби со знаменателем имеет вид . Если же разложить в цепную дробь, получается =(3, 7, 15, …); Наибольшей подходящей дробью для со знаменателем является число , известное уже Архимеду, причем . Итак, мы получили, что приближение подходящей дробью дает большую точность, чем приближение десятичной дробью. Это объясняется тем, что знаменатели подходящих дробей определяются арифметической природой изображаемого числа, а знаменатели же приближающих десятичных дробей не могут быть иными, как только . Теорема: Если рациональное число ближе к действительному числу , чем его подходящая дробь , где k>1, то , то есть если , то . Доказательство: Рассмотрим случай, когда (иначе теряет смысл). Тогда всегда лежит между любыми двумя последующими подходящими дробями так, что для k>1 всегда лежит между и , причем ближе к , чем к . Поэтому, если ближе к , чем , то оно находится между и . В случае четного можно записать 1, имеет знаменатель . Для k=1 теорема неверна: может оказаться ближе к , чем его подходящая дробь , хотя . Доказанная теорема приводит нас к следующему определению:
