Далее: Описание этапов проведения лабораторной Вверх: Лабораторная работа №1 Назад: Лабораторная работа №1

Теоретический аспект

Число $A$ называется пределом числовой последовательности $\left\{ {x_n } \right\}$, если для любого $\varepsilon > 0$ существует такое натуральное число $n_\varepsilon$, что для любого $n > n_\varepsilon$ верно неравенство: $\left\vert {x_n - A} \right\vert < \varepsilon$.

Рассмотрим числовые последовательности вида:

$$x_n = \frac{a_2 n^2 + a_1 n + a_0 }{b_2 n^2 + b_1 n + b_0 },$$

где $a_0$, $a_1$, $a_2$, $b_0$, $b_1$, $b_2$ - целые числа, причем $a_2 \ne 0$ и $b_2 \ne 0$.

Пределом числовых последовательностей является отношение:

$$A = \mathop {\lim }\limits_{n \to \infty } x_n = \frac{a_2 }{b_2 }.$$

Необходимо осуществить приближенные вычисления значений минимальных номеров $n_\varepsilon$ числовых последовательностей $\left\{ {x_n } \right\}$ по заданным $\varepsilon > 0$, таких, что для всех членов числовых последовательностей со значениями номеров $n > n_\varepsilon$ выполняется неравенство $\left\vert {x_n - A} \right\vert < \varepsilon$ в соответствии с различными условиями варьирования значений исходных данных.

Рассмотрим функцию $\left\vert {f\left( n \right)} \right\vert = \left\vert {x_n - A} \right\vert$:

$$\left\vert {f(n)} \right\vert = \left\vert {\frac{a_2 n^2 + ... ...0 }{b_2 \left( {b_2 n^2 + b_1 n + b_0 } \right)}} \right\vert.$$

От рассмотрения функции $\left\vert {f\left( n \right)} \right\vert$ перейдем к рассмотрению функции $f\left( n \right)$ (экстраполируя $f\left( n \right)$ на положительную $R^{ + })$, так как график функции $\left\vert {f\left( n \right)} \right\vert$ отличается от графика функции $f\left( n \right)$ (в смысле выяснения особенностей, т.е. действительных точек разрыва и экстремума) только появлением дополнительной действительной угловой точки графика на оси абсцисс:

$$f(n) = \frac{a_2 n^2 + a_1 n + a_0 }{b_2 n^2 + b_1 n + b_0 }... ... b_2 - a_2 b_0 }{b_2 \left( {b_2 n^2 + b_1 n + b_0 } \right)}.$$

Для определения действительных точек разрыва функции $f\left( n \right)$, то есть действительных точек несуществования функции $f\left( n \right)$, необходимо решить уравнение $b_2 n^2 + b_1 n + b_0 = 0$ ($b_2 \ne 0$ в силу существования предела последовательности).

В силу решения квадратного уравнения возможны следующие варианты наличия у функции $f\left( n \right)$ действительных точек разрыва ( $D_{BP} = b_1^2 - 4b_0 b_2 )$:

Если $D_{BP} < 0$, то функция $f\left( n \right)$ не имеет действительных точек разрыва и непрерывна на всей числовой оси.

Если $D_{BP} = 0$, то функция $f\left( n \right)$ имеет одну действительную точку разрыва со следующим значением абсциссы: $n_{BP} = \frac{ - b_1 }{2b_2 }$.

Если $D_{BP} > 0$, то функция $f\left( n \right)$ имеет две действительные точки разрыва со следующими значениями абсцисс:

$$n_{BP1,BP2} = \frac{ - b_1 \pm \sqrt {D_{BP} } }{2b_2 } = \frac{ - b_1 \pm \sqrt {b_1^2 - 4b_0 b_2 } }{2b_2 }.$$

Для определения действительных точек экстремума функции $f\left( n \right)$, то есть действительных точек, в которых данная функция имеет максимум или минимум, необходимо решить уравнение ${f}'\left( n \right) = 0$ и выявить характер действительных критических точек.

$$\begin{array}{l} {f}'\left( n \right) = \frac{1}{b_2 }\left... ... - a_0 b_1 } \right)}{b_2 n^2 + b_1 n + b_0 }. \\ \end{array}$$

В силу решения квадратного уравнения, левая часть которого представлена в числителе, а именно, $\left( {a_2 b_1 - a_1 b_2 } \right)n^2 + 2\left( {a_2 b_0 - a_0 b_2 } \right)n + \left( {a_1 b_0 - a_0 b_1 } \right) = 0$и влияния знаменателя возможны следующие варианты наличия у функции $f\left( n \right)$ действительных критических точек $\left( {D_{EP} = 4\left( {a_2 b_0 - a_0 b_2 } \right)^2 - 4\left( {a_2 b_1 - a_1 b_2 } \right)\left( {a_1 b_0 - a_0 b_1 } \right)} \right)$, причем $b_2 \ne 0$ в силу существования предела последовательности:

Если $D_{EP} < 0$, то функция $f\left( n \right)$ не имеет действительных критических точек.

Если $D_{EP} = 0$, то функция $f\left( n \right)$ должна иметь одну действительную критическую точку со следующим значением абсциссы: $n_{EP} = \frac{a_0 b_2 - a_2 b_0 }{a_2 b_1 - a_1 b_2 }$.

Действительно, если $D_{EP} = 0$, то есть $\left( {a_2 b_0 - a_0 b_2 } \right)^2 = \left( {a_2 b_1 - a_1 b_2 } \right)\left( {a_1 b_0 - a_0 b_1 } \right)$, и $n_{EP} = \frac{a_0 b_2 - a_2 b_0 }{a_2 b_1 - a_1 b_2 }$, то получим:

$$\begin{array}{l} \left( {a_2 b_1 - a_1 b_2 } \right)n_{EP}^... ...ht) + \left( {a_1 b_0 - a_0 b_1 } \right) = 0. \\ \end{array}$$

Однако при соблюдении предлагаемых договоренностей имеем:

$$\begin{array}{l} b_2 n_{EP}^2 + b_1 n_{EP} + b_0 = b_2 \lef... ...0 b_1 - a_1 b_0 b_2 }{a_2 b_1 - a_1 b_2 } = 0. \\ \end{array}$$

Таким образом, если $D_{EP} = 0$, то $b_2 n_{EP}^2 + b_1 n_{EP} + b_0 = 0$, что противоречит условию существования производной функции ${f}'\left( n \right)$, то есть при данных условиях функция $f\left( n \right)$ не имеет действительных критических точек.

Если $D_{EP} > 0$, то функция $f\left( n \right)$ должна иметь две действительные критические точки со следующими значениями абсцисс:

$$\begin{array}{l} n_{EP1,EP2} = \frac{2\left( {a_0 b_2 - a_2... ..._0 - a_0 b_1 } \right)} }{a_2 b_1 - a_1 b_2 }. \\ \end{array}$$

Если при $n_{EP1} = \frac{2\left( {a_0 b_2 - a_2 b_0 } \right) + \sqrt {D_{EP} } }{2\left( {a_2 b_1 - a_1 b_2 } \right)}$ получим, что $b_2 n_{EP1}^2 + b_1 n_{EP1} + b_0 = 0$, то функция $f\left( n \right)$ имеет только одну действительную критическую точку со следующим значением абсциссы:

$$n_{EP} = n_{EP2} = \frac{a_0 b_2 - a_2 b_0 - \sqrt {\left( {... ...ht)\left( {a_1 b_0 - a_0 b_1 } \right)} }{a_2 b_1 - a_1 b_2 }.$$

Если при $n_{EP2} = \frac{2\left( {a_0 b_2 - a_2 b_0 } \right) - \sqrt {D_{EP} } }{2\left( {a_2 b_1 - a_1 b_2 } \right)}$ получим, что $b_2 n_{EP2}^2 + b_1 n_{EP2} + b_0 = 0$, то функция $f\left( n \right)$ имеет только одну действительную критическую точку со следующим значением абсциссы:

$$n_{EP} = n_{EP1} = \frac{a_0 b_2 - a_2 b_0 + \sqrt {\left( {... ...ht)\left( {a_1 b_0 - a_0 b_1 } \right)} }{a_2 b_1 - a_1 b_2 }.$$

Если при $n_{EP1} ,n_{EP2} = \frac{2\left( {a_0 b_2 - a_2 b_0 } \right)\pm \sqrt {D_{EP} } }{2\left( {a_2 b_1 - a_1 b_2 } \right)}$ получим, что $b_2 n_{EP1,EP2}^2 + b_1 n_{EP1,EP2} + b_0 \ne 0$, то функция $f\left( n \right)$ имеет две действительные критические точки со следующими значениями абсцисс:

$$n_{EP1,EP2} = \frac{a_0 b_2 - a_2 b_0 \pm \sqrt {\left( {a_2... ...t)\left( {a_1 b_0 - a_0 b_1 } \right)} }{a_2 b_1 - a_1 b_2 }..$$

Нахождение действительной угловой точки осуществляется в результате анализа функции $\left\vert {f\left( n \right)} \right\vert$:

$$\left\vert {f(n)} \right\vert = \left\vert {\frac{a_2 n^2 + ... ..._2 - a_2 b_0 }{b_2^2 n^2 + b_1 b_2 n + b_0 b_2 }} \right\vert.$$

Действительная угловая точка означает пересечение графика функции $\left\vert {f\left( n \right)} \right\vert$ с осью абсцисс, то есть точку, в которой график функции резко меняет направление в силу зеркального отображения отрицательных областей графика функции $f\left( n \right)$ относительно оси абсцисс.

Для определения действительной угловой точки функции $\left\vert {f\left( n \right)} \right\vert$, то есть точки, в которой функции $\left\vert {f\left( n \right)} \right\vert$ и $f\left( n \right)$ пересекают ось абсцисс, необходимо решить уравнение $f\left( n \right) = 0$:

$$f(n) = \frac{\left( {a_1 b_2 - a_2 b_1 } \right)n + a_0 b_2 - a_2 b_0 }{b_2 \left( {b_2 n^2 + b_1 n + b_0 } \right)}.$$

В силу решения линейного уравнения, левая часть которого представлена в числителе, а именно, $\left( {a_1 b_2 - a_2 b_1 } \right)n + a_0 b_2 - a_2 b_0 = 0$ и влияния знаменателя возможны следующие варианты наличия у функции $\left\vert {f\left( n \right)} \right\vert$ действительных угловых точек, причем $b_2 \ne 0$ в силу существования предела последовательности:

Если $a_1 b_2 - a_2 b_1 = 0$, то функция $\left\vert {f\left( n \right)} \right\vert$ не имеет действительной угловой точки.

Если $a_1 b_2 - a_2 b_1 \ne 0$, то функция $\left\vert {f\left( n \right)} \right\vert$ должна иметь одну действительную угловую точку со следующим значением абсциссы: $n_{AP} = \frac{a_2 b_0 - a_0 b_2 }{a_1 b_2 - a_2 b_1 }$.

Если при $n_{AP} = \frac{a_2 b_0 - a_0 b_2 }{a_1 b_2 - a_2 b_1 }$ получим, что $b_2 n_{AP}^2 + b_1 n_{AP} + b_0 = 0$, то функция $\left\vert {f\left( n \right)} \right\vert$ не имеет действительной угловой точки;

Если при $n_{AP} = \frac{a_2 b_0 - a_0 b_2 }{a_1 b_2 - a_2 b_1 }$ получим, что $b_2 n_{AP}^2 + b_1 n_{AP} + b_0 \ne 0$, то функция $\left\vert {f\left( n \right)} \right\vert$ имеет одну действительную угловую точку со следующим значением абсциссы: $n_{AP} = \frac{a_2 b_0 - a_0 b_2 }{a_1 b_2 - a_2 b_1 }$.

После нахождения действительных точек разрыва ($n_{BP1}$,$n_{BP2}$ или $n_{BP} )$, точек экстремума ($n_{EP1}$,$n_{EP2}$ или $n_{EP} )$ и угловой точки ($n_{AP} )$ для функции $\left\vert {f\left( n \right)} \right\vert$ определим отрезок $\left[ {n_{A0} ,n_{B0} } \right]$ с условием $n_{A0} < n_{B0}$, на котором следует осуществлять нахождение значения минимального номера $n_\varepsilon$, где $n_{B0}$ - минимальный номер, теоретически найденный аналитическим методом, а значение $n_{A0}$ определяется из выражения $n_{A0} = \max \{n_{BP1} \left( {n_{BP} } \right),n_{BP2} ,n_{EP1} \left( {n_{EP} } \right),n_{EP2} ,n_{AP} \}$, при этом для дальнейших расчетов в случаях наличия дробных частей значения граничных номеров следует округлять до больших ближайших целых чисел.

Порядок нахождения значения $n_{A0}$ в силу особенностей функции $\left\vert {f\left( n \right)} \right\vert$ состоит из следующих этапов:

При отсутствии у функции $\left\vert {f\left( n \right)} \right\vert$ действительных точек разрыва $n_{A01} = - \infty$;

При наличии у функции $\left\vert {f\left( n \right)} \right\vert$ одной действительной точки разрыва $n_{A01} = n_{BP}$;

При наличии у функции $\left\vert {f\left( n \right)} \right\vert$ двух действительных точек разрыва если $n_{BP1} > n_{BP2}$, то $n_{A01} = n_{BP1}$, если $n_{BP1} < n_{BP2}$, то $n_{A01} = n_{BP2}$;

При отсутствии у функции $\left\vert {f\left( n \right)} \right\vert$ действительных точек экстремума $n_{A02} = - \infty$;

При наличии у функции $\left\vert {f\left( n \right)} \right\vert$ одной действительной точки экстремума если $\left\vert {f\left( {n_{EP} } \right)} \right\vert < \varepsilon$, то $n_{A02} = - \infty$, если $\left\vert {f\left( n \right)_{EP} } \right\vert > \varepsilon$, то $n_{A02} = n_{EP}$;

При наличии у функции $\left\vert {f\left( n \right)} \right\vert$ двух действительных точек экстремума если $\left\vert {f\left( {n_{EP1} } \right)} \right\vert < \varepsilon$, то $n_{A021} = - \infty$, если $\left\vert {f\left( {n_{EP1} } \right)} \right\vert > \varepsilon$, то $n_{A021} = n_{EP1}$;

При наличии у функции $\left\vert {f\left( n \right)} \right\vert$ двух действительных точек экстремума если $\left\vert {f\left( {n_{EP2} } \right)} \right\vert < \varepsilon$, то $n_{A022} = - \infty$, если $\left\vert {f\left( {n_{EP2} } \right)} \right\vert > \varepsilon$, то $n_{A022} = n_{EP2}$;

При наличии у функции $\left\vert {f\left( n \right)} \right\vert$ двух действительных точек экстремума если $n_{A021} > n_{A022}$, то $n_{A02} = n_{A021}$, если $n_{A021} < n_{A022}$, то $n_{A02} = n_{A022}$;

При отсутствии у функции $\left\vert {f\left( n \right)} \right\vert$ действительной угловой точки $n_{A03} = - \infty$;

При наличии у функции $\left\vert {f\left( n \right)} \right\vert$ одной действительной угловой точки $n_{A03} = n_{AP}$;

В качестве $n_{A0}$ выбирается округленное до большего ближайшего целого числа максимальное из значений $n_{A01}$, $n_{A02}$ и $n_{A03}$.

Рассмотрим логические основы реализации методов золотой пропорции, Фибоначчи, дихотомии для выполнения приближенных вычислений значений пределов числовых последовательностей вида $x_n = \frac{a_2 n^2 + a_1 n + a_0 }{b_2 n^2 + b_1 n + b_0 }$ (для $\varepsilon > 0$, $a_2 \ne 0$, $b_2 \ne 0$, $\left\vert {x_n - \frac{a_2 }{b_2 }} \right\vert < \varepsilon )$ на основе расчетов значений минимальных номеров $n_\varepsilon$ в зависимости от различных значений $\varepsilon$, $n_{A0}$ и $n_{B0}$, заложенных в программу "MINNESQS".

Метод золотой пропорции

Суть золотой пропорции, изображенной на рис. 1, состоит в следующем: если разделить отрезок С на отрезки А и В таким образом, что это будет отражать золотую пропорцию, то А, деленное на В, будет равно С, деленному на А.

Символьная запись: $\frac{C}{A} = \frac{A}{B} = \varphi = \frac{1 + \sqrt 5 }{2} \approx 1,618033989$.

Рис. 1. Золотая пропорция

Действительно, пусть $\frac{C}{A} = \frac{A}{B} = X$.

Так как $A + B = C$ или $\frac{A}{A} + \frac{B}{A} = \frac{C}{A}$, то получим квадратное уравнение:

$$1 + \frac{1}{X} = X \Rightarrow X^2 - X - 1 = 0.$$

Положительный действительный корень квадратного уравнения:

$$X = \varphi = \frac{1 + \sqrt 5 }{2} \approx 1,618033989.$$

По аналогии с пропорцией назовем число $\varphi$ золотым.

Одно из общеизвестных алгебраических свойств золотого числа заключается в следующем: золотое число, возведенное в степень с натуральным показателем, равно сумме двух золотых чисел, возведенных в две предшествующие степени: $\varphi ^N = \varphi ^{N - 1} + \varphi ^{N - 2}$.

Действительно, так как $\varphi ^2 - \varphi - 1 = 0$, то $\varphi ^2 = \varphi + 1$ или $\varphi ^{N - 2} \cdot \varphi ^2 = \varphi ^{N - 2} \cdot \varphi + \varphi ^{N - 2}$, откуда $\varphi ^N = \varphi ^{N - 1} + \varphi ^{N - 2}$.

Поскольку $\varphi ^N = \varphi ^{N - 1} + \varphi ^{N - 2}$, то $\varphi ^N = \varphi ^{N + 2} - \varphi ^{N + 1}$, откуда можно получить следующие соотношения:

$$\frac{1}{\varphi } = \varphi - 1, \quad \frac{1}{\varphi ^2}... ... \frac{2}{\varphi ^2} = \frac{2}{\varphi } - 1 = 2\varphi - 3.$$

В данной лабораторной работе метод золотой пропорции ("METHOD OF GOLD PROPORTION") имеет следующую реализацию:

Итерация с индексом $''0''$:

На искомом отрезке $\left[ {n_{A0} ,n_{B0} } \right]$ при соблюдении условий $n_{A0} < n_{B0}$ и $\left\vert {f\left( {n_{A0} } \right)} \right\vert \ge \varepsilon > \left\vert {f\left( {n_{B0} } \right)} \right\vert$ (по умолчанию значения $n_{A0}$ и $n_{B0}$ являются целыми числами) выбираются точки с абсциссами $n_{C0}^{GP}$ и $n_{D0}^{GP}$, исходя из неравенств $n_{A0} < n_{C0}^{GP} < n_{D0}^{GP} < n_{B0}$ и $\left\vert {f\left( {n_{A0} } \right)} \right\vert > \left\vert {f\left( {n_{C0... ...GP} } \right)} \right\vert > \left\vert {f\left( {n_{B0} } \right)} \right\vert$, в соответствии с принципами золотой пропорции согласно следующим соотношениям:

$$n_{C0}^{GP} = n_{A0} + \frac{n_{B0} - n_{A0} }{\varphi ^2} =... ...0} }{\varphi } = n_{B0} - \frac{n_{B0} - n_{A0} }{\varphi ^2}.$$

При наличии положительных дробных частей значения $n_{C0}^{GP}$ и $n_{D0}^{GP}$ округляются до ближайших больших целых чисел.

Если достигнута истинность выражения $n_{B0} - n_{A0} = 1$, то итерации прекращаются, количество шагов итераций $s_\varepsilon ^{GP} = 0$, и в качестве минимального номера $n_\varepsilon ^{GP}$ выбирается $n_\varepsilon ^{GP} = n_{A0}$ в силу неравенства $\left\vert {f\left( {n_{A0} } \right)} \right\vert \ge \varepsilon > \left\vert {f\left( {n_{B0} } \right)} \right\vert$.

Если $n_{B0} - n_{A0} \ne 1$, то осуществляется переход к следующей итерации.

Итерация с индексом $''N'' \left( {N \ge 1} \right)$:

Если $\left\vert {f\left( {n_{C\left( {N - 1} \right)}^{GP} } \right)} \right\vert < \varepsilon$, то $n_{AN}^{GP} = n_{A\left( {N - 1} \right)}^{GP}$, $n_{BN}^{GP} = n_{C\left( {N - 1} \right)}^{GP}$, $n_{BN}^{GP} - n_{AN}^{GP} = n_{C\left( {N - 1} \right)}^{GP} - n_{A\left( {N - ... ...{B\left( {N - 1} \right)}^{GP} - n_{A\left( {N - 1} \right)}^{GP} }{\varphi ^2}$, и получаем отрезок $\left[ {n_{AN}^{GP} ,n_{BN}^{GP} } \right] = \left[ {n_{A\left( {N - 1} \right)}^{GP} ,n_{C\left( {N - 1} \right)}^{GP} } \right]$.

Если $\left\vert {f\left( {n_{C\left( {N - 1} \right)}^{GP} } \right)} \right\vert \ge \varepsilon$ и $\left\vert {f\left( {n_{D\left( {N - 1} \right)}^{GP} } \right)} \right\vert < \varepsilon$, то $n_{AN}^{GP} = n_{C\left( {N - 1} \right)}^{GP}$, $n_{BN}^{GP} = n_{D\left( {N - 1} \right)}^{GP}$, $n_{BN}^{GP} - n_{AN}^{GP} = n_{D\left( {N - 1} \right)}^{GP} - n_{C\left( {N - ... ...{B\left( {N - 1} \right)}^{GP} - n_{A\left( {N - 1} \right)}^{GP} }{\varphi ^3}$, и получаем отрезок $\left[ {n_{AN}^{GP} ,n_{BN}^{GP} } \right] = \left[ {n_{C\left( {N - 1} \right)}^{GP} ,n_{D\left( {N - 1} \right)}^{GP} } \right]$.

Если $\left\vert {f\left( {n_{D\left( {N - 1} \right)}^{GP} } \right)} \right\vert \ge \varepsilon$, то $n_{AN}^{GP} = n_{D\left( {N - 1} \right)}^{GP}$, $n_{BN}^{GP} = n_{B\left( {N - 1} \right)}^{GP}$, $n_{BN}^{GP} - n_{AN}^{GP} = n_{B\left( {N - 1} \right)}^{GP} - n_{D\left( {N - ... ...{B\left( {N - 1} \right)}^{GP} - n_{A\left( {N - 1} \right)}^{GP} }{\varphi ^2}$, и получаем отрезок $\left[ {n_{AN}^{GP} ,n_{BN}^{GP} } \right] = \left[ {n_{D\left( {N - 1} \right)}^{GP} ,n_{B\left( {N - 1} \right)}^{GP} } \right]$.

На отрезке $\left[ {n_{AN}^{GP} ,n_{BN}^{GP} } \right]$ при соблюдении условий $n_{AN}^{GP} < n_{BN}^{GP}$ и $\left\vert {f\left( {n_{AN}^{GP} } \right)} \right\vert \ge \varepsilon > \left\vert {f\left( {n_{BN}^{GP} } \right)} \right\vert$ выбираются точки с абсциссами $n_{CN}^{GP}$ и $n_{DN}^{GP}$, исходя из неравенств $n_{AN}^{GP} < n_{CN}^{GP} < n_{DN}^{GP} < n_{BN}^{GP}$ и $\left\vert {f\left( {n_{AN}^{GP} } \right)} \right\vert > \left\vert {f\left( {... ... \right)} \right\vert > \left\vert {f\left( {n_{BN}^{GP} } \right)} \right\vert$, в соответствии с принципами золотой пропорции согласно следующим соотношениям:

$$n_{CN}^{GP} = n_{AN}^{GP} + \frac{n_{BN}^{GP} - n_{AN}^{GP} ... ...} = n_{BN}^{GP} - \frac{n_{BN}^{GP} - n_{AN}^{GP} }{\varphi },$$

$$n_{DN}^{GP} = n_{AN}^{GP} + \frac{n_{BN}^{GP} - n_{AN}^{GP} ... ...= n_{BN}^{GP} - \frac{n_{BN}^{GP} - n_{AN}^{GP} }{\varphi ^2}.$$

При наличии положительных дробных частей значения $n_{CN}^{GP}$ и $n_{DN}^{GP}$ округляются до ближайших больших целых чисел.

Если достигнута истинность выражения $n_{BN}^{GP} - n_{AN}^{GP} = 1$, то итерации прекращаются, количество шагов итераций $s_\varepsilon ^{GP} = N$, и в качестве минимального номера $n_\varepsilon ^{GP}$ выбирается $n_\varepsilon ^{GP} = n_{AN}^{GP}$ в силу неравенства $\left\vert {f\left( {n_{AN}^{GP} } \right)} \right\vert \ge \varepsilon > \left\vert {f\left( {n_{BN}^{GP} } \right)} \right\vert$.

Если $n_{BN}^{GP} - n_{AN}^{GP} \ne 1$, то осуществляется переход к следующей итерации.

Метод Фибоначчи

Последовательность чисел Фибоначчи (открыта Леонардо Фибоначчи) отличается от других последовательностей чисел тем, что каждый ее член, начиная со второго по индексу, равен сумме двух предыдущих (с добавлением нулевого члена последовательности): 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233 и так далее.

Действительно: $0 + 1 = 1$, $1 + 1 = 2$, $2 + 1 = 3$, $3 + 2 = 5$, то есть $F_K = F_{K - 1} + F_{K - 2}$, где $F_K$, $F_{K - 1}$ и $F_{K - 2} \quad _{ } -$ члены последовательности Фибоначчи с индексами $''K''$, $''K - 1''$ и $''K - 2''$ соответственно.

Интересно отметить, что отношение значений соседних членов данной последовательности, начиная с больших номеров (при $K \to \infty )$, приближается к золотому числу, то есть $\varphi$:

$$\frac{F_K }{F_{K - 1} } \approx \varphi = \frac{1 + \sqrt 5 }{2} \approx 1,618033989,$$

где $F_K$ и $F_{K - 1} -$ члены последовательности Фибоначчи с индексами $''K''$ и $''K - 1''$ соответственно.

Для золотых чисел, возведенных в определенных степенях (геометрическая прогрессия со значениями начального члена и знаменателя, равными $\varphi$), как и для последовательности чисел Фибоначчи, справедливо общее правило о том, что значение каждого члена любой из этих последовательностей равно сумме значений двух предыдущих членов:

Формула для геометрической прогрессии золотых чисел: $\varphi ^K = \varphi ^{K - 1} + \varphi ^{K - 2}$, где $''K''$, $''K - 1''$ и $''K - 2''$ - показатели степеней для золотого числа $\varphi$;

Формула для последовательности чисел Фибоначчи: $F_K = F_{K - 1} + F_{K - 2}$, где $F_K$, $F_{K - 1}$ и $F_{K - 2} \quad _{ } -$ члены последовательности Фибоначчи с индексами $''K''$, $''K - 1''$ и $''K - 2''$ соответственно.

Поскольку $F_K = F_{K - 1} + F_{K - 2}$, то $F_{K - 2} = F_K - F_{K - 1}$, откуда можно получить следующие соотношения:

$$F_{K - 3} = F_{K - 1} - F_{K - 2} = 2F_{K - 1} - F_K = F_K - 2F_{K - 2} ,$$

$$\frac{F_{K - 3} }{F_K } = \frac{F_{K - 1} }{F_K } - \frac{F_... ...= 2\frac{F_{K - 1} }{F_K } - 1 = 1 - 2\frac{F_{K - 2} }{F_K }.$$

Взаимосвязь между золотым числом и числами Фибоначчи выражается следующим соотношением: $\varphi ^K = F_{K - 1} + F_K \cdot \varphi$.

Докажем утверждение методом последовательного перебора:

$$\varphi ^1 = \varphi ^0 + \varphi ^{ - 1} = 0 + 1 \cdot \varphi = F_0 + F_1 \cdot \varphi ,$$

$$\varphi ^2 = \varphi ^1 + \varphi ^0 = \varphi + 1 = 1 + 1 \cdot \varphi = F_1 + F_2 \cdot \varphi ,$$

$$\varphi ^3 = \varphi ^2 + \varphi ^1 = (F_1 + F_2 \cdot \var... ...{F_1 + F_2 } \right) \cdot \varphi = F_2 + F_3 \cdot \varphi ,$$

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

$$\begin{array}{l} \varphi ^K = \varphi ^{K - 1} + \varphi ^{... ...cdot \varphi = F_{K - 1} + F_K \cdot \varphi . \\ \end{array}$$

В данной лабораторной работе метод Фибоначчи ("METHOD OF FIBONACHCHI") имеет следующую реализацию:

Итерация с индексом $''0''$:

Осуществляется ввод значения индекса последнего члена ряда Фибоначчи для его построения, то есть $''K''$.

Осуществляется построение заданного ряда Фибоначчи, начиная с нулевого индекса и заканчивая индексом $''K''$.

На искомом отрезке $\left[ {n_{A0} ,n_{B0} } \right]$ при соблюдении условий $n_{A0} < n_{B0}$ и $\left\vert {f\left( {n_{A0} } \right)} \right\vert \ge \varepsilon > \left\vert {f\left( {n_{B0} } \right)} \right\vert$ (по умолчанию значения $n_{A0}$ и $n_{B0}$ являются целыми числами) выбираются точки с абсциссами $n_{C0}^F$ и $n_{D0}^F$, исходя из неравенств $n_{A0} < n_{C0}^F < n_{D0}^F < n_{B0}$ и $\left\vert {f\left( {n_{A0} } \right)} \right\vert > \left\vert {f\left( {n_{C0... ...}^F } \right)} \right\vert > \left\vert {f\left( {n_{B0} } \right)} \right\vert$, в соответствии с принципами последовательности Фибоначчи согласно следующим соотношениям:

$$n_{C0}^F = n_{A0} + \frac{F_{K - 2} }{F_K }\left( {n_{B0} - ... ...0} - \frac{F_{K - 2} }{F_K }\left( {n_{B0} - n_{A0} } \right).$$

При наличии положительных дробных частей значения $n_{C0}^F$ и $n_{D0}^F$ округляются до ближайших больших целых чисел.

Если достигнута истинность выражения $n_{B0} - n_{A0} = 1$, то итерации прекращаются, количество шагов итераций $s_\varepsilon ^F = 0$, и в качестве минимального номера $n_\varepsilon ^F$ выбирается $n_\varepsilon ^F = n_{A0}$ в силу неравенства $\left\vert {f\left( {n_{A0} } \right)} \right\vert \ge \varepsilon > \left\vert {f\left( {n_{B0} } \right)} \right\vert$.

Если $n_{B0} - n_{A0} \ne 1$, то осуществляется переход к следующей итерации.

Итерация с индексом $''N'' \left( {N \ge 1} \right)$:

Если $\left\vert {f\left( {n_{C\left( {N - 1} \right)}^F } \right)} \right\vert < \varepsilon$, то $n_{AN}^F = n_{A\left( {N - 1} \right)}^F$, $n_{BN}^F = n_{C\left( {N - 1} \right)}^F$, $n_{BN} - n_{AN} = n_{C\left( {N - 1} \right)} - n_{A\left( {N - 1} \right)} = \... ...N} }\left( {n_{B\left( {N - 1} \right)} - n_{A\left( {N - 1} \right)} } \right)$, и получаем отрезок $\left[ {n_{AN}^F ,n_{BN}^F } \right] = \left[ {n_{A\left( {N - 1} \right)}^F ,n_{C\left( {N - 1} \right)}^F } \right]$.

Если $\left\vert {f\left( {n_{C\left( {N - 1} \right)}^F } \right)} \right\vert \ge \varepsilon$ и $\left\vert {f\left( {n_{D\left( {N - 1} \right)}^F } \right)} \right\vert < \varepsilon$, то $n_{AN}^F = n_{C\left( {N - 1} \right)}^F$, $n_{BN}^F = n_{D\left( {N - 1} \right)}^F$, $n_{BN}^F - n_{AN}^F = n_{D\left( {N - 1} \right)}^F - n_{C\left( {N - 1} \right... ...\left( {n_{B\left( {N - 1} \right)}^F - n_{A\left( {N - 1} \right)}^F } \right)$, и получаем отрезок $\left[ {n_{AN}^F ,n_{BN}^F } \right] = \left[ {n_{C\left( {N - 1} \right)}^F ,n_{D\left( {N - 1} \right)}^F } \right]$.

Если $\left\vert {f\left( {n_{D\left( {N - 1} \right)}^F } \right)} \right\vert \ge \varepsilon$, то $n_{AN}^F = n_{D\left( {N - 1} \right)}^F$, $n_{BN}^F = n_{B\left( {N - 1} \right)}^F$, $n_{BN}^F - n_{AN}^F = n_{B\left( {N - 1} \right)}^F - n_{D\left( {N - 1} \right... ...\left( {n_{B\left( {N - 1} \right)}^F - n_{A\left( {N - 1} \right)}^F } \right)$, и получаем отрезок $\left[ {n_{AN}^F ,n_{BN}^F } \right] = \left[ {n_{D\left( {N - 1} \right)}^F ,n_{B\left( {N - 1} \right)}^F } \right]$.

На отрезке $\left[ {n_{AN}^F ,n_{BN}^F } \right]$ при соблюдении условий $n_{AN}^F < n_{BN}^F$ и $\left\vert {f\left( {n_{AN}^F } \right)} \right\vert \ge \varepsilon > \left\vert {f\left( {n_{BN}^F } \right)} \right\vert$ выбираются точки с абсциссами $n_{CN}^F$ и $n_{DN}^F$, исходя из неравенств $n_{AN}^F < n_{CN}^F < n_{DN}^F < n_{BN}^F$ и $\left\vert {f\left( {n_{AN}^F } \right)} \right\vert > \left\vert {f\left( {n_{... ...F } \right)} \right\vert > \left\vert {f\left( {n_{BN}^F } \right)} \right\vert$, в соответствии с принципами последовательности Фибоначчи согласно следующим соотношениям:

$$n_{CN}^F = n_{AN}^F + \frac{F_{K - 2 - N} }{F_{K - N} }\left... ...K - 1 - N} }{F_{K - N} }\left( {n_{BN}^F - n_{AN}^F } \right),$$

$$n_{DN}^F = n_{AN}^F + \frac{F_{K - 1 - N} }{F_{K - N} }\left... ...K - 2 - N} }{F_{K - N} }\left( {n_{BN}^F - n_{AN}^F } \right).$$

При наличии положительных дробных частей значения $n_{CN}^F$ и $n_{DN}^F$ округляются до ближайших больших целых чисел.

Если достигнута истинность выражения $n_{BN}^F - n_{AN}^F = 1$, то итерации прекращаются, количество шагов итераций $s_\varepsilon ^F = N$, и в качестве минимального номера $n_\varepsilon ^F$ выбирается $n_\varepsilon ^F = n_{AN}^F$ в силу неравенства $\left\vert {f\left( {n_{AN}^F } \right)} \right\vert \ge \varepsilon > \left\vert {f\left( {n_{BN}^F } \right)} \right\vert$.

Если $n_{BN}^F - n_{AN}^F \ne 1$, то осуществляется переход к следующей итерации.

Стоит отметить, что при достаточно большом значении начального индекса $''K''$ соответствующие отрезки, полученные методами золотой пропорции и Фибоначчи, будут иметь незначительные отличия, что влечет за собой приблизительно равную эффективность обоих методов.

Метод дихотомии

Суть дихотомии или половинного деления состоит в следующем: если разделить отрезок C на отрезки A и B таким образом, что это будет отражать дихотомию, то C, деленное на A, будет равно C, деленному на B, то есть A равно B: $\frac{C}{A} = \frac{С}{B} = 2$ или $A = B$.

Таким образом, при наличии исходного отрезка $\left[ {a_0 ,b_0 } \right]$ полученный в результате $''N''$-го деления отрезок $\left[ {a_N ,b_N } \right]$ связан с исходным соотношением $b_N - a_N = \frac{b_0 - a_0 }{2^N}$.

В данной лабораторной работе метод дихотомии ("METHOD OF DICHOTOMY") имеет следующую реализацию:

Итерация с индексом $''0''$:

Осуществляется ввод значения расстояния, откладываемого симметрично относительно середины отрезка, для установки точек, то есть $n_M^D$.

Если $n_{B0} - n_{A0} \le 2$, то на искомом отрезке $\left[ {n_{A0} ,n_{B0} } \right]$ при соблюдении условий $n_{A0} < n_{B0}$ и $\left\vert {f\left( {n_{A0} } \right)} \right\vert \ge \varepsilon > \left\vert {f\left( {n_{B0} } \right)} \right\vert$ (по умолчанию значения $n_{A0}$ и $n_{B0}$ являются целыми числами) выбирается точка с абсциссой $n_{C0}^D = n_{D0}^D$, исходя из неравенств $n_{A0} < n_{C0}^D = n_{D0}^D < n_{B0}$ и $\left\vert {f\left( {n_{A0} } \right)} \right\vert > \left\vert {f\left( {n_{C0... ...}^D } \right)} \right\vert > \left\vert {f\left( {n_{B0} } \right)} \right\vert$, в соответствии с принципами дихотомии согласно следующему соотношению:

$$n_{C0}^D = n_{D0}^D = n_{A0} + \frac{n_{B0} - n_{A0} }{2} = n_{B0} - \frac{n_{B0} - n_{A0} }{2}.$$

Если $2 < n_{B0}^D - n_{A0}^D \le 2n_M^D$, то на искомом отрезке $\left[ {n_{A0} ,n_{B0} } \right]$ при соблюдении условий $n_{A0} < n_{B0}$ и $\left\vert {f\left( {n_{A0} } \right)} \right\vert \ge \varepsilon > \left\vert {f\left( {n_{B0} } \right)} \right\vert$(по умолчанию значения $n_{A0}$ и $n_{B0}$ являются целыми числами) выбираются точки с абсциссами $n_{C0}^D$ и $n_{D0}^D$, исходя из неравенств $n_{A0} < n_{C0}^D < n_{D0}^D < n_{B0}$ и $\left\vert {f\left( {n_{A0} } \right)} \right\vert > \left\vert {f\left( {n_{C0... ...}^D } \right)} \right\vert > \left\vert {f\left( {n_{B0} } \right)} \right\vert$, в соответствии с принципами дихотомии согласно следующим соотношениям:

$$n_{C0}^D = n_{A0} + \frac{n_{B0} - n_{A0} }{2} - 1 = n_{B0} ... ...} - n_{A0} }{2} + 1 = n_{B0} - \frac{n_{B0} - n_{A0} }{2} + 1.$$

Если $n_{B0} - n_{A0} > 2n_M^D$, то на искомом отрезке $\left[ {n_{A0} ,n_{B0} } \right]$ при соблюдении условий $n_{A0} < n_{B0}$ и $\left\vert {f\left( {n_{A0} } \right)} \right\vert \ge \varepsilon > \left\vert {f\left( {n_{B0} } \right)} \right\vert$ (по умолчанию значения $n_{A0}$ и $n_{B0}$ являются целыми числами) выбираются точки с абсциссами $n_{C0}^D$ и $n_{D0}^D$, исходя из неравенств $n_{A0} < n_{C0}^D < n_{D0}^D < n_{B0}$ и $\left\vert {f\left( {n_{A0} } \right)} \right\vert > \left\vert {f\left( {n_{C0... ...}^D } \right)} \right\vert > \left\vert {f\left( {n_{B0} } \right)} \right\vert$, в соответствии с принципами дихотомии согласно следующим соотношениям:

$$n_{C0}^D = n_{A0} + \frac{n_{B0} - n_{A0} }{2} - n_M^D = n_{B0} - \frac{n_{B0} - n_{A0} }{2} - n_M^D ,$$

$$n_{D0}^D = n_{A0} + \frac{n_{B0} - n_{A0} }{2} + n_M^D = n_{B0} - \frac{n_{B0} - n_{A0} }{2} + n_M^D .$$

При наличии положительных дробных частей значения $n_{C0}^D$ и $n_{D0}^D$ округляются до ближайших больших целых чисел.

Если достигнута истинность выражения $n_{B0} - n_{A0} = 1$, то итерации прекращаются, количество шагов итераций $s_\varepsilon ^D = 0$, и в качестве минимального номера $n_\varepsilon ^D$ выбирается $n_\varepsilon ^D = n_{A0}$ в силу неравенства $\left\vert {f\left( {n_{A0} } \right)} \right\vert \ge \varepsilon > \left\vert {f\left( {n_{B0} } \right)} \right\vert$.

Если $n_{B0} - n_{A0} \ne 1$, то осуществляется переход к следующей итерации.

Итерация с индексом "N" $\left( {N \ge 1} \right)$:

Если $\left\vert {f\left( {n_{C\left( {N - 1} \right)}^D } \right)} \right\vert < \varepsilon$, то $n_{AN}^D = n_{A\left( {N - 1} \right)}^D$, $n_B^D = n_{C\left( {N - 1} \right)}^D$, $n_{BN}^D - n_{AN}^D = n_{C\left( {N - 1} \right)}^D - n_{A\left( {N - 1} \right... ...rac{n_{B\left( {N - 1} \right)}^D - n_{A\left( {N - 1} \right)}^D }{2} - n_M^D$, и получаем отрезок $\left[ {n_{AN}^D ,n_{BN}^D } \right] = \left[ {n_{A\left( {N - 1} \right)}^D ,n_{C\left( {N - 1} \right)}^D } \right]$.

Если $\left\vert {f\left( {n_{C\left( {N - 1} \right)}^D } \right)} \right\vert \ge \varepsilon$ и $\left\vert {f\left( {n_{D\left( {N - 1} \right)}^D } \right)} \right\vert < \varepsilon$, то $n_{AN}^D = n_{C\left( {N - 1} \right)}^D$, $n_{B1}^D = n_{D\left( {N - 1} \right)}^D$, $n_{BN}^D - n_{AN}^D = n_{D\left( {N - 1} \right)}^D - n_{C\left( {N - 1} \right)}^D = 2n_M^D$, и получаем отрезок $\left[ {n_{AN}^D ,n_{BN}^D } \right] = \left[ {n_{C\left( {N - 1} \right)}^D ,n_{D\left( {N - 1} \right)}^D } \right]$.

Если $\left\vert {f\left( {n_{D\left( {N - 1} \right)}^D } \right)} \right\vert \ge \varepsilon$, то $n_{AN}^D = n_{D\left( {N - 1} \right)}^D$, $n_{B1}^D = n_{B0}^D$, $n_{BN}^D - n_{AN}^D = n_{B\left( {N - 1} \right)}^D - n_{D\left( {N - 1} \right... ...rac{n_{B\left( {N - 1} \right)}^D - n_{A\left( {N - 1} \right)}^D }{2} - n_M^D$, и получаем отрезок $\left[ {n_{AN}^D ,n_{BN}^D } \right] = \left[ {n_{D\left( {N - 1} \right)}^D ,n_{B\left( {N - 1} \right)}^D } \right]$.

Если $n_{BN}^D - n_{AN}^D \le 2$, то на отрезке $\left[ {n_{AN}^D ,n_{BN}^D } \right]$ при соблюдении условий $n_{AN}^D < n_{BN}^D$ и $\left\vert {f\left( {n_{AN}^D } \right)} \right\vert \ge \varepsilon > \left\vert {f\left( {n_{BN}^D } \right)} \right\vert$ выбирается точка с абсциссой $n_{CN}^D = n_{DN}^D$, исходя из неравенств $n_{AN}^D < n_{CN}^D = n_{DN}^D < n_{BN}^D$ и $\left\vert {f\left( {n_{AN}^D } \right)} \right\vert > \left\vert {f\left( {n_{... ...D } \right)} \right\vert > \left\vert {f\left( {n_{BN}^D } \right)} \right\vert$, в соответствии с принципами дихотомии согласно следующему соотношению:

$$n_{CN}^D = n_{DN}^D = n_{AN}^D + \frac{n_{BN}^D - n_{AN}^D }{2} = n_{BN}^D - \frac{n_{BN}^D - n_{AN}^D }{2}.$$

Если $2 < n_{BN}^D - n_{AN}^D \le 2n_M^D$, то на отрезке $\left[ {n_{AN}^D ,n_{BN}^D } \right]$ при соблюдении условий $n_{AN}^D < n_{BN}^D$ и $\left\vert {f\left( {n_{AN}^D } \right)} \right\vert \ge \varepsilon > \left\vert {f\left( {n_{BN}^D } \right)} \right\vert$ выбираются точки с абсциссами $n_{CN}^D$ и $n_{DN}^D$, исходя из неравенств $n_{AN}^D < n_{CN}^D < n_{DN}^D < n_{BN}^D$ и $\left\vert {f\left( {n_{AN}^D } \right)} \right\vert > \left\vert {f\left( {n_{... ...D } \right)} \right\vert > \left\vert {f\left( {n_{BN}^D } \right)} \right\vert$, в соответствии с принципами дихотомии согласно следующим соотношениям:

$$n_{CN}^D = n_{AN}^D + \frac{n_{BN}^D - n_{AN}^D }{2} - 1 = n... ...N}^D }{2} + 1 = n_{BN}^D - \frac{n_{BN}^D - n_{AN}^D }{2} + 1.$$

Если $n_{BN}^D - n_{AN}^D > 2n_M^D$, то на отрезке $\left[ {n_{AN}^D ,n_{BN}^D } \right]$ при соблюдении условий $n_{AN}^D < n_{BN}^D$ и $\left\vert {f\left( {n_{AN}^D } \right)} \right\vert \ge \varepsilon > \left\vert {f\left( {n_{BN}^D } \right)} \right\vert$ выбираются точки с абсциссами $n_{CN}^D$ и $n_{DN}^D$, исходя из неравенств $n_{AN}^D < n_{CN}^D < n_{DN}^D < n_{BN}^D$ и $\left\vert {f\left( {n_{AN}^D } \right)} \right\vert > \left\vert {f\left( {n_{... ...D } \right)} \right\vert > \left\vert {f\left( {n_{BN}^D } \right)} \right\vert$, в соответствии с принципами дихотомии согласно следующим соотношениям:

$$n_{CN}^D = n_{AN}^D + \frac{n_{BN}^D - n_{AN}^D }{2} - n_M^D... ... + n_M^D = n_{BN}^D - \frac{n_{BN}^D - n_{AN}^D }{2} + n_M^D .$$

При наличии положительных дробных частей значения $n_{CN}^D$ и $n_{DN}^D$ округляются до ближайших больших целых чисел.

Если достигнута истинность выражения $n_{BN}^D - n_{AN}^D = 1$, то итерации прекращаются, количество шагов итераций $s_\varepsilon ^D = N$, и в качестве минимального номера $n_\varepsilon ^D$ выбирается $n_\varepsilon ^D = n_{AN}^D$ в силу неравенства $\left\vert {f\left( {n_{AN}^D } \right)} \right\vert \ge \varepsilon > \left\vert {f\left( {n_{BN}^D } \right)} \right\vert$.

Если $n_{BN}^D - n_{AN}^D \ne 1$, то осуществляется переход к следующей итерации.

Далее: Описание этапов проведения лабораторной Вверх: Лабораторная работа №1 Назад: Лабораторная работа №1