Выбор и обоснование используемых методов

Решение данной задачи требует использование трех численных методов:

1. Численный метод одномерной оптимизации

2. Численный метод вычисления определенного интеграла

3. Метод интерполирования функции

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

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

Для интерполирования полученных значений функции f(y) будет использована формула Лагранжа с автоматической перенумерацией узлов. Хоть у нас и равноотстоящие узлы, для которых интерполяционные формулы Ньютона удобней при расчете, формула Лагранжа даст больший порядок точности, потому что при ее использовании возможно задействовать большее количество узлов, чем в формулах Ньютона, которыми можно интерполировать либо только влево, либо только вправо.

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

В основу метода положено разбиение отрезка неопределенности [a; b] в соотношении золотого сечения, такого, что отношение длины его большей части ко всей длине отрезка равно отношению длины его меньшей части к длине большей части.

В методе золотого сечения каждая точка () осуществляет золотое сечение отрезка.

Точка осуществляет золотое сечение не только отрезка [a; b], но и отрезка [a; ]. Аналогично с точкой . Это приводит к тому, что значение целевой функции на каждой итерации (кроме первой) вычисляется один раз.

Сокращение отрезка неопределенности идет следующим образом:

1) Если

2) Если

После каждой итерации длина отрезка неопределенности сокращается в 1.618 раза. Длина конечного отрезка неопределенности , где .

Условие окончания процесса итераций . Отсюда находим количество итераций, необходимых для достижения точки минимума:

Методом золотого сечения можно найти минимум функции только при условии, что отрезок содержит единственный минимум, то есть, целевая функция на данном отрезке – унимодальная.

3.1.1 Проверка унимодальности

Методом золотого сечения можно найти минимум только при условии, если отрезок содержит единственный минимум, то есть целевая функция на данном отрезке – унимодальна.

Проверим условие унимодальности для заданного в курсовой работе отрезка [m, n].

Как видно из графика и значений функции, ее первой и второй производных, функция P(x) на отрезке [0, 1] унимодальна, так как выполняются необходимые условия:

1) Для дифференцируемой функции f(x), ее производная f′ (х) - неубывающая.

2) Для дважды дифференцируемой функции f(x) выполняется неравенство f``(х) ≥ 0

3.2 Метод Симпсона

Суть метода заключается в приближении подынтегральной функции на отрезке [a, b] интерполяционным многочленом второй степени P₂(x), то есть приближение графика функции на отрезке параболой. Метод Симпсона имеет порядок погрешности 4 и алгебраический порядок точности 3.

Формулой Симпсона называется интеграл от интерполяционного многочлена второй степени на отрезке :

где , и — значения функции в соответствующих точках (на концах отрезка и в его середине).

Общая погрешность при интегрировании по отрезку с шагом (при этом, в частности, , ) определяется по формуле:

.

Однако на практике использование этой формулы ограничено в связи с трудоемкостью ее вычисления, поэтому для реализации метода Симпсон а на ПК мы будем использовать прием, имеющий название правило Рунге (или метод двойного просчета). Этот прием основан на двукратном вычислении значения интеграла вначале с шагом h (где ), а затем с шагом . Полученные значения и могут быть применены для оценки погрешности интегрирования по формуле:

где k = 4 – для формулы Симпсона.

3.3 Интерполяционная формула Лагранжа

Пусть функция f(x) задана в (n+1) узлах, произвольно или равномерно расположенных на отрезке [a; b]:

Требуется найти интерполирующий алгебраический многочлен , степени не выше n, удовлетворяющий условию интерполяции , такой, что:

Будем искать вида:

где – коэффициенты, зависящие только от узлов , i = 0, 1, … n и текущего значения x.

Для выполнения условий интерполяции нужно, чтобы

Этому требованию отвечает коэффициент вида:

Для интерполяционного многочлена Лагранжа выражение будет иметь вид:

\

Несмотря на громоздкость, одним из преимуществ формулы Лагранжа является возможность ее записи непосредственно по заданной таблице значений функции. Для этого следует учесть следующее правило: формула содержит столько слагаемых, сколько узлов в таблице; каждое слагаемое – это произведение дробного коэффициента на соответствующее значение ; числитель коэффициента при содержит произведение разностей х со всеми узлами кроме , а знаменатель полностью повторяет числитель при

Оценка погрешности формулы Лагранжа:

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

В данной курсовой работе перенумерация узлов будет осуществляться с помощью сортировки «методом пузырьков».