Определение минимального номера N(ε) по заданным коэффициентам последовательности a0, a1, a2, b0, b1, b2 и ε

1. Определение минимального номера N(ε) по заданным коэффициентам последовательности a0, a1, a2, b0, b1, b2 и ε.

Исходя из постановки задачи определения минимального номера N()ε по

заданному ε, начиная с которого выполняется неравенство:

рассмотрим функцию f (n ):

(экстраполируя f на положительную полуось R+)

От рассмотрения функции f(n)

перейдем к рассмотрению функции f (n ), так как график функции f()n отличается от графика функции f()n (в смысле выявления точек экстремума, точек несуществования производной) только появлением дополнительных угловых точек графика на оси абсцисс.

Как же ведет себя функция f(n)?

Во-первых, она может иметь точки раз-

* * рыва n1* и n*2:

Если же D < 0, то f непрерывна на

R+

Во-вторых, она имеет точки экстремума, для определения которых необходимо решить уравнение: f(nj = 0 и выявить характер критических точек.

От рассмотрения уравнения f (n ) = 0 перейдем к рассмотрению уравнения:

Вычислим критические точки n1 и n2 функции f(n): Если a1b2 − a2b1 ≠ 0, то, учитывая

получим: Если D≥0,то

Если D < 0, то действительных критических точек нет. Если же a2b1 − a1b2 = 0, то

Нахождение угловых точек осуществляется в результате анализа функции

Угловые точки означают пересечение графика данной функции с осью абсцисс, то есть точки, где график функции резко меняет направление, поскольку данная функция является зеркальным отображением функции f ()n j (то есть отрицательные области графика зеркально отображаются относительно оси абсцисс).

Исходя из числителя функции, которая является линейной, очевидно нали-

чие либо одной такой точки, либо вовсе ее отсутствие.

Откуда

Итак, когда найдены B1 и B2 - точки разрыва, и E1, E2 - точки экстремума f()n и угловая точка G для функции

f ()n, определим интервал [nx;n0], на котором следует искать минимальный N()ε:

nx =max{B1,B2,E1,E2,G},

n0 - теоретически найденный номер аналитическим методом.

Теперь непосредственно рассмотрим вычислительные процедуры для нахождения N()ε, то есть три численных метода, которые применялись для вычисления минимального номера N(ε) при разработке программы "NUMBERS".

Метод золотого сечения

Золотое сечение, открытое Евклидом, состоит в разбиении интервала [а; b] точкой x на две части таким образом, чтобы отношение длины всего интервала к большей части было равно отношению большей части к меньшей:

Золотое сечение производят две точки:

где

(в качестве точки x будем

брать точку х1).

Алгоритм метода золотого сечения для интервала []nx;n0 J следующий:

1. Вычислить значение x.

2. Вычислить значение f()x.

3. Если f(x)< ε, то для дальнейшего деления оставляют интервал [nx;x].

4. Если f(x)≥ ε, то для дальнейшего деления оставляют интервал [x;n0].

Процесс деления продолжают до тех пор, пока длина интервала неопределенности не станет равной 1, то есть точки nx и n0 станут соседними. Искомым N(ε) будет номер n0.

При написании программы использованы стандартные функции: int - получение целой части числа, frac - получение дробной части числа.

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

Как известно, числа Фибоначчи определяются соотношениями:

Используя числа Fn, строим n-точечный последовательный метод, который принято называть методом Фибоначчи. Как и метод золотого сечения, метод Фибоначчи состоит в задании на интервале [a;b] точки х1 или симметричной ей точки х2:

В качестве x - точки разбиения интервала будем брать точку хь Алгоритм метода Фибоначчи совпадает с алгоритмом метода золотого сечения. Единственный недостаток метода Фибоначчи в том, что нужно заранее задать количество проходов.

Интересно заметить, что

то есть при достаточно больших n (больше 10) точки разбиения методом Фибоначчи и золотого сечения практически совпадают. Это означает, что в данном случае метод Фибоначчи и метод золотого сечения по своей эффективности одинаковы, что и было подтверждено практическими испытаниями.

Метод дихотомии (бисекции)

Метод дихотомии состоит в разбиении интервала [a;b] точкой x пополам. Алгоритм метода дихотомии аналогичен алгоритму метода золотого сечения. Метод дихотомии является менее эффективным в данном случае, чем методы золотого сечения и Фибоначчи.

Описание лабораторной работы

Лабораторная работа по нахождению минимального номера N()ε может быть разделена на три этапа: I этап "Творческий поиск"

Студентам индивидуально-аналитическим методом оценок предлагается найти номер n0, начиная с которого выполняется xn − A < ε (например, ε = 0,05). Ввиду индивидуальности задания и различия способов оценки неравенства пути поиска решения проблемы могут быть весьма различными. IIэтап "Соревнование"

Данный этап подразумевает отыскание более точного значения номера n0 с аналогичными условиями выполнения. Студенты разделяются на m групп по 3 -4 человека, находят оптимальный общий метод оценки, благодаря чему вносится элемент соревнования, основанный на нахождении каждой из групп более точной оценки.

Преподаватель фиксирует найденные в группах номера nk (k = 1, 2, ….. , m) и оценивает правильность и эффективность оценочных процедур. /// этап "Нахождение минимального номера N()ε"

Данный этап является заключительным, поскольку именно здесь студенты получают возможность вычислить минимальный номер N(ε), начиная с которого выполняется неравенство

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

< ε (что является трудоемким процессом и неэффективным);

- Использование одного из численных методов (золотого сечения, Фибоначчи или метод дихотомии (бисекции));

- Использование метода случайного поиска.

Ниже представлено описание соответствующей программы для нахождения N(ε) при ε = 0,05 и n0 =10000 для последовательности

Описание программы

Итак, перейдем непосредственно к программе "NUMBERS", реализующей следующие задачи: