Метод золотого сечения в excel
Базовая структура алгоритма оптимизации основана на итерационной формулеПродолжайте создавать следующую точку итерации, пока не будут выполнены определенные условия завершения. Определение итерационной формулы включает направление поискаИ шаг поискаХорошо, гдеПроцесс определения - это процесс так называемого линейного поиска. Технология поиска по строкам является основой многомерной оптимизации функций, которая включает в себя технологию точного поиска по строкам и технологию поиска по неточным строкам. Точный поиск строки такСоответствует минимальному значениюДругими словами: точный линейный поиск стремится сделать целевую функцию вдоль направления поискаШаг поиска, который упал больше всего. Неточный линейный поиск - заставить целевую функцию по направлению поискаЕсть некий убывающий шаг поиска.
Обычные методы точного линейного поиска можно разделить на две категории: методы сегментации и методы интерполяции: методы сегментации включают дихотомию, золотое сечение, Фибоначчи и т.д .; методы интерполяции включают одноточечную квадратичную интерполяцию (метод Ньютона), два Точечная квадратичная интерполяция (включая метод секущих), трехточечная квадратичная интерполяция, двухточечная кубическая интерполяция и т. Д. Технология поиска по неточной строке основана на критериях поиска по неточной строке. Обычно используются критерии Армийо-Гольдштейна, критерий Вульфа-Пауэлла, строгий критерий Вульфа-Пауэлла и простой критерий.
Точный поиск строки:
Метод деления: дихотомия, метод золотого сечения, метод рядов Фибоначчи
Метод интерполяции: метод одноточечной квадратичной интерполяции (метод Ньютона), метод двухточечной квадратичной интерполяции (включая метод секущей и метод несекущей) и т. Д.
Неточный поиск в Интернете:
Критерий Армихо-Гольдштейна, критерий Вульфа-Пауэлла, строгий критерий Вульфа-Пауэлла
В реальных расчетах обычно используется технология поиска по неточной линии.Это связано с тем, что технология поиска по точной линии требует больших вычислительных ресурсов, а для оптимизации многомерных функций скорость сходимости многих алгоритмов не зависит от того, используется ли технология точного поиска по линии.
2. Технология точного линейного поиска
Технология точного линейного поиска включает две категории методов: методы сегментации и методы интерполяции. Метод сегментации непрерывно сжимает интервал в соответствии с определенными правилами и останавливается до тех пор, пока ширина интервала не станет очень малой, и использует среднюю точку интервала как крайнюю точку целевой функции. Метод интерполяции заключается в непрерывной аппроксимации целевой функции новыми квадратичными или кубическими интерполяционными полиномами до тех пор, пока не будет выполнено условие остановки, а крайние точки интерполяционного полинома будут рассматриваться как крайние точки целевой функции.
2.1 Метод сегментации
Общие методы разделения включают дихотомию, золотое сечение и Фибоначчи. Мы определяем степень сжатия каждого шага как отношение длины сжатого интервала к исходной длине интервала, а общая степень сжатия - это отношение конечной длины интервала к начальной длине интервала. Когда общее количество итераций равно Когда степень сжатия каждого шага дихотомии равна, Общая степень сжатия составляет; Степень сжатия каждого шага метода золотого сечения равна, Общая степень сжатия составляет Степень сжатия каждого шага метода Фибоначчи варьируется, но когда количество шагов достаточно велико, степень сжатия близка к, Общая степень сжатия составляет,Последовательность Фибоначчи вещь. Принципиальное введение и реализация этих методов в Python приведены ниже.
2.1.1 Дихотомия
Найдите функцию одной долиныВ интервалеВерхняя крайняя точкаОсновной принцип: рассчитать,в случае, ПотомА именноМинимальная точка, если, Описание вПо-прежнему монотонно снижается, не достигнув минимального значения, то есть, В этот раз, Начальный интервалСжат до. в случае , Описание вУже находится в монотонном восходящем состоянии и меньше чемДостигли минимума в какой-то момент, В этот раз, Начальный интервалСжат до. Используя этот принцип или напрямую найдите точку минимума, Или вы можете сравнитьВ середине интервалаСвязь между производной от и 0 для непрерывного сужения интервала, в котором находится точка минимумаДлина интервала каждый раз уменьшается до 1/2 от исходной длины. Когда длина интервала достаточно мала или точка минимума найдена напрямую, итерация может быть остановлена. В это время средняя точка интервала или найденная точка минимума является дихотомией. Последняя функцияМинимальная точка.
2.1.2 Метод золотого сечения
Найдите функцию одной долиныВ интервалеВерхняя крайняя точкаОсновной принцип: выбирайДве точки золотого сечения на
Если, Должно быть , В этот разЕсли , Должно быть , На этот раз заказ, Итак, начальный интервалСжат в, Его длина примерно в 0,618 раза больше начального интервала. По интервалу сравненияДве точки золотого сечения Отношение размеров продолжает сужать интервалКогда длина достаточно мала, середина интервала получается методом золотого сечения.Минимальная точка. Особо следует отметить: каждый шаг метода золотого сеченияДве точки золотого сечения наКогда есть точка золотого сечения, это точка золотого сечения на предыдущей итерации, и ее не нужно вычислять. Время,, когда Время,.
2.1.3 Метод рядов Фибоначчи
Найдите функцию одной долиныВ интервалеВерхняя крайняя точкаОсновной принцип: выбирайДве точки разделения на
Если, Должно быть , В этот разЕсли , Должно быть , На этот раз заказ, Итак, начальный интервалСжат в, Его длина порядка начального интервалаРаз. По интервалу сравненияДве точки золотого сечения Отношение размеров продолжает сужать интервалКогда длина достаточно мала, середина интервала получается методом золотого сечения.Минимальная точка. Как и метод золотого сечения, Фибоначчи требует каждого шагаДве точки вставки наЕсли есть точка вставки, которая является точкой вставки на предыдущей итерации, ее не нужно вычислять. Время,, когда Время,. Отличие от метода золотого сечения:
1) Степень сжатия каждого шага метода ФибоначчиНеопределено, и степень сжатия каждого шага метода золотого сеченияВсегда равно ;
2) Во-вторых, метод Фибоначчи можно повторять не более n раз, а длина последовательности Фибоначчи равна n + 1. Правило золотого сечения не требует этого.
Кроме того, необходимо подчеркнуть еще один момент: степень сжатия n-го шага метода Фибоначчи.Потому что, еслиПриведет кПоявляется, где ϵ - небольшое положительное действительное число
2.2 Метод интерполяции
Общие методы интерполяции включают одноточечную квадратичную интерполяцию, двухточечную квадратичную интерполяцию, трехточечную квадратичную интерполяцию и двухточечную кубическую интерполяцию. Одним из методов одноточечной квадратичной интерполяции является метод Ньютона, а одним из методов двухточечной квадратичной интерполяции является метод секущей. Принципиальное введение и реализация этих методов в Python приведены ниже.
Метод квадратичной интерполяции заключается в непрерывном построении полинома квадратичной интерполяцииДля аппроксимации целевой функцииТочка минимума полинома квадратичной интерполяции, построенного на последнем шаге, используется в качестве точки минимума целевой функции.Разница между различными методами квадратичной интерполяции состоит в том, что информация, используемая при построении полинома квадратичной интерполяции, отличается.
2.2.1 Метод одноточечной квадратичной интерполяции
Метод одноточечной квадратичной интерполяции (метод Ньютона) использует информацию о 1 функции, 1 первой производной и 1 второй производной при построении полинома квадратичной интерполяции на этапе (k + 1):
Отсюда итерационная формула метода одноточечной квадратичной интерполяции (метод Ньютона) выводится как:
Ниже приводится реализация Python метода одноточечной квадратичной интерполяции (метод Ньютона):
2.2.2 Метод двухточечной квадратичной интерполяции
Метод двухточечной квадратичной интерполяции (метод секущей, метод секущей) использует информацию о 1 функции и 2 первых производных при построении полинома квадратичной интерполяции на этапе (k + 1)
Итерационная формула метода двухточечной квадратичной интерполяции (метод секущей) выводится из этого:
Метод двухточечной квадратичной интерполяции (метод без секущей, метод квадратичной интерполяции с двумя точками) использует 2 функции и 1 информацию о производной первого порядка
Отсюда итерационная формула метода двухточечной квадратичной интерполяции (метод несекущей) выводится как:
3. Неточный поиск
Интернет-поиск сначала найдетПо убыванию, А затем рассчитать размер шага, Размер шага определяетРазмер изменения.
Направление поискаНужно встретить это нисходящее направление, то есть встретить , Позволять ,Является симметричной невырожденной матрицей, согласноНа выбор будут произведены следующие направления:
- Когда направление поиска является направлением с отрицательным градиентом, этот метод является направлением наискорейшего спуска.
- Когда, это метод Ньютона.
- Удовлетворяет симметричной положительно определенной матрице, метод является квазиньютоновским. .
Общие критерии поиска по неточным строкам включают критерии Армийо-Голдштейна, критерии Вульфа-Пауэлла, строгие критерии Вульфа-Пауэлла и простые критерии. Их отправной точкой является обеспечение того, чтобы размер шага поиска не был слишком большим или не слишком маленьким. Метод поиска по неточной строке заключается в том, чтобы найти шаг поиска, который удовлетворяет определенному критерию, так что
3.1 Критерий (условие) Армиджо, критерий (условие) кривизны, критерий (условие) Вульфа, сильный критерий (условие) Вульфа
Правила Armijo (условия):,В настоящее время, В реальном приложении выбор
Критерии (условия) кривизны:, В настоящее время, Для рекомендаций Armijo (условия)
Критерий Вульфа (условие): критерий Армиджо и комбинация критерия кривизны
Сильное условие Вульфа: ограничения как на положительный, так и на отрицательный наклон
3.2 Критерий Армихо-Гольдштейна, критерий Вульфа-Пауэлла, строгий критерий Вульфа-Пауэлла (,)
Есть две основные идеи:
Условие 1. Убедитесь, что целевая функция уменьшается в направлении вниз, а длина шага поиска не слишком велика;
Второе условие гарантирует, что размер шага поиска не будет слишком маленьким. ▫ ▫
Есть две основные идеи:
Первое условие гарантирует, что целевая функция убывает в нисходящем направлении и длина шага поиска не слишком велика;
Условие два гарантирует, что минимальное значение целевой функции может стать размером шага поиска, а размер шага поиска не будет слишком маленьким. ,
Есть две основные идеи:
Первое условие гарантирует, что целевая функция убывает в нисходящем направлении и длина шага поиска не слишком велика;
Условие 2 гарантирует, что точка минимума целевой функции может стать шагом поиска, а в крайнем случае это может привести к возможности точного линейного поиска, а шаг поиска не слишком мал.
VBA Excel. Нахождение экстремума функции Методом Золотого Сечения.
О методе Золотого Сечения:
Безусловно, простой и быстрый метод. И как водится, скорость не способствует аккуратности. Это я о том, что если на заданном интервале поиска будут находиться несколько минимумов (максимумов), то данный алгоритм легко может вернуть локальный (не самый большой, не абсолютный) экстремум.
Задание:
Составить программу позволяющую протестировать алгоритм поиска экстремума методом Золотого Сечения на примере пяти произвольных функций. Исходными данными для поиска должны являться границы интервала, точность и тип экстремума (MAX или MIN). Программа должна отображать график функции на заданном интервале и координаты точки экстремума.
- Модуль листа Excel (SheetGoldCutting), на котором как на форме будут располагаться необходимые органы управления ходом тестирования;
- Форма для ввода данных FormDann;
- Класс ExtremGC, вычисляющий координаты точки экстремума с заданной точностью, а также массив точек графика функции на заданном интервале (для отображения на диаграмме);
- Стандартный модуль GoldCutting для описания глобальных констант, переменных и функций.
Например, так.
Рис.1 Рабочий лист Excel с диаграммой, двумя командными кнопками и кнопками выбора функции
Рис.2 Форма для ввода исходных данных
Данная форма вызывается явно при щелчке по первой командной кнопке (расположенной на листе Excel) или косвенно, если в момент нажатия на вторую командную кнопку (расположенную на листе Excel), исходные данные не обеспечивают необходимых условий начала выполнения алгоритма.
Для удобства пользователя, все элементы TextBox допускают ввод только числовых значений.
При щелчке по кнопке «Отмена» все переменные получат значения, которые существовали на момент открытия формы.
При открытии файла (если макросы включены) или включении макросов (если они были отключены на момент открытия файла) выполняется обработчик события с целью задать (определить) одну из заготовленных функций, как функцию для тестирования по умолчанию. Для этого достаточно отметить одну (например, первую) OptionButton (или как часто называют - радиокнопку) и вызвать макрос назначенный этой кнопке.
Private Sub Workbook_Open()
' радиокнопки нумеруются в этой книге от 5 до 9.
' Поэтому по умолчанию выделяю первую кнопку.
Sheets(1).Shapes("Option Button 5").ControlFormat.Value = 1
SheetGoldCutting.OptBut1_Click
End Sub
Метод theAlgoritm класса ExtremGC, который, собственно, и выполняет определение координат точки экстремума выглядит приблизительно так:
'Нахождение экстремума функции на отрезке. Метод золотого сечения
Public Sub theAlgoritm(v1 As Double, v2 As Double, v3 As Double, v4 As Double, findMax As Boolean)
Dim x1 As Double, x2 As Double, y1 As Double, y2 As Double, sme As Double
FullArrayOnly v1, v2, v3, v4 'для проверки допустимости аргумента
If Not BadDann Then
zc = (1 + Sqr(5)) / 2
n = 0 'количество разбиений (переменная модуля класса)
Do While b - a > ep
sme = (b - a) / zc
x1 = b - sme: x2 = a + sme
y1 = theFunc(x1): y2 = theFunc(x2)
If findMax Then
'поиск максимума
If y1 = y2 Then
a = x1
Else
b = x2
End If
End If
n = n + 1 'количество разбиений (переменная модуля класса)
Loop
dxk = Abs(b - a) ' конечное значение шага
xe = (a + b) / 2: ye = theFunc(xe) ' результат: координаты точки экстремума
Где
FullArrayOnly - закрытый метод класса для проверки допустимости аргумента и заполнения массива точек графика;
BadDann – флаг допустимости аргумента;
zc – константа золотого сечения;
a, b – границы интервала;
ep – заданная точность поиска ε;
findMax – параметр, характеризующий режим поиска (при true ищется максимум, при false – минимум);
theFunc(x As Double) As Double – метод класса, возвращающий значение тестируемой функции в зависимости от значение аргумента.
Кому интересен остальной код – обращайтесь…
Если нужно что-то изменить в проекте под Ваши требования (например, заменить функции) – пожалуйста, проблем не будет!
исходный код уже открыт. Используйте !
Если у Вас не появляется форма ввода данных, значит вы забыли включить макросы…
Хочу обратить внимание, что для первой функции значения аргумента не могут быть меньше или равны нулю.
Чтобы увидеть, как ошибается алгоритм и находит локальный экстремум вместо абсолютного, задайте достаточно большой интервал (например: от 0 до 25) для 4 или 5 функций, имеющих явную периодичность…
Нахождение экстремума функции Методом Золотого Сечения.
Условие:
Вычислить экстремум функции y(x)=x+lg(1/x); с заданной точностью ε,
т.е. найти координаты (xe, ye).
Значение границ интервала, начальное значение шага и точность ввести с клавиатуры в главной программе. Координаты экстремума, конечное значение шага и количество разбиений вывести на экран в главной программе.
Решение:
function dannFunc (x: real): real;
begin
if x
while (b-a>eps) do
begin
x1:=b-((b-a)/zc); x2:=a+((b-a)/zc);
y1:= dannFunc(x1); y2:= dannFunc(x2);
if y1>=y2 then a:=x1 else b:=x2;
Данная процедура получает семь параметров. Первые три параметра передаются по значению, а следующие четыре - по ссылке.
Рассчитываем переменную zc:=(1+sqrt(5))/2; .
По идее – это константа, так как все данные в формуле известны и не зависят от параметров, но оформить ее как константу нельзя, потому что используется функция извлечения квадратного корня.
Цикл while(b-a>eps) do сознательно не оптимизирован… Конечно, метод золотого сечения позволяет (т.е. достаточно) считать функцию только в одной новой точке, а не в двух (при каждой итерации как сделано в моем примере), но для учебной задачи, где заданная функция достаточно проста и машинное время на ее выполнение не критично, это вполне допустимо (если, конечно, Ваш преподаватель не акцентировал на этом моменте особое внимание).
По окончанию цикла, остается инициализировать три параметра (переменные) по ссылке (т.к. параметр nn уже инициализирован в ходе цикла).
- Приглашение (типа… write('Ведите a, b, eps ->');)
- Инициализация переменных с клавиатуры ( readln(a, b, eps); )
- Вызов процедуры ExtrеmGC(a, b, eps, xe, ye, dx1, n);
- Вывод на экран переменных xe, ye, dx1, n (в удовлетворяющем Ваш вкус виде), которые получили инициализацию в ExtrеmGC.
Заданная функция в моем примере y(x)=x+lg(1/x); имеет два максимума в точках +0 и +∞ и один минимум в точке ~0,4343. Значение функции в точке экстремума y(0,4343)= ~0,7965
При изучении дисциплины “Математика” в средних специальных учебных заведениях предполагается рассмотрение темы: “Элементы численных методов”. Использование MathCAD 2000 и Microsoft Excel для реализации численных методов позволяет сформировать понимание математического содержания конкретного метода и умение использовать современные программные средства. При использовании MathCAD 2000 и Microsoft Excel в ходе выполнения лабораторных работ студенты получают возможность использовать знания, полученные при изучении дисциплины “Информатика”.
Возможности MathCAD 2000 позволяют строить графики зависимостей, графически отделять корни уравнений, решать уравнения и системы уравнений, преобразовывать полученные выражения, проверять правильность полученного приближённого решения.
Возможности Microsoft Excel позволяют не тратить время на проведение однотипных расчетов, быстро исправлять возникающие ошибки в вычислениях.
Использование MathCAD 2000 и Microsoft Excel для приближённого решения систем линейных алгебраических уравнений методом итераций.
На первом этапе приближённого решения СЛАУ методом простой итерации необходимо привести систему к нормальному виду. Для этого нужно выразить х из первого уравнения, y из второго уравнения и т.д. Это можно сделать с помощью Math CAD 2000. При этом можно использовать один из способов решения уравнений: набирается уравнение, причём равно ставится жирное (+) и даётся команда solve из панели “Символика”, после указания переменной, относительно которой необходимо разрешить уравнение, получим результат.
На втором этапе решения необходимо проверить для полученной системы, приведённой к нормальному виду условие сходимости итерационного процесса, т. е. сравнить нормы матрицы с единицей. Например, проверить условие, что наибольшая из сумм модулей элементов столбцов меньше 1. Это также можно сделать с помощью Math CAD 2000. При этом используется функция norm1(А) из стандартного набора функций.
Итерационный процесс удобнее осуществить в Microsoft Excel. В столбец А заносится номер итерационного шага, в столбцы В, С, D – значения хk, yk, zk в столбцы E,F,G – значения хk+1, yk+1, zk+1, в столбце Н можно вычислять значение погрешности вычислений на данном шаге итерации, чтобы выполнить вычисления с заданной степенью точности.
При заполнении ячеек В3, С3, D3 лучше ссылаться на ячейки E2, F2, G2, а не вводить данные вручную, это позволит рациональнее использовать время, лучше использовать автозаполнение и проще исправлять ошибки.
В правильности полученных результатов можно убедиться, если решить систему с помощью MathCAD 2000. Это можно сделать с помощью команд given и find.
Для решения данной системы методом Зейделя достаточно будет лишь изменить формулы для вычисления , yk, zk.
Пример использование MathCAD 2000 и Microsoft Excel для приближённого решения системы линейных алгебраических уравнений методом простых итераций и методом Зейделя можно увидеть на рис.1.
Использование MathCAD 2000 и Microsoft Excel для интерполирования кубическими сплайнами
Сейчас широкое распространение для интерполяции получило использование кубических сплайн–функций – специальным образом построенных многочленов третьей степени.
Проверить правильность выполнения сплайн–интерполирования можно, построив график данной функции и полученного сплайна в MathCAD 2000. Для этого задаются: матрицы Х и У исходных данных, три отрезка на которых строится сплайн–функция. Потом задаются все три функции, определяющие сплайн–функцию (аргумент у каждой должен быть разный, соответствующий отрезку на котором эта функция построена). Последний этап – построение графика. Чтобы задать несколько аргументов и функций используется запятая. Если щёлкнуть по полю графика 2 раза, то появится окно форматирования графиков, в закладке Х–У Axec можно задать линию сетки, а в закладке Traces задать вид линии графика и построить график исходных данных точками, а график полученной сплайн–функции сплошной линией.
Пример использование Math CAD 2000 для интерполирования кубическими сплайнами можно увидеть на рис.2.
Использование MathCAD 2000 и Microsoft Excel для поиска экстремума функции методом золотого сечения
При решении задачи на поиск экстремума функции методом золотого сечения необходимо сначала определить отрезок, которому принадлежит минимум или максимум. Это можно сделать, построив график данной функции в MathCAD 2000. Выполнив форматирование графика, можно указать достаточно малый отрезок, которому принадлежит экстремум функции.
Уточнять значение экстремума с заданной степенью точности лучше в Microsoft Excel. В столбцы A и D удобно занести значение концов отрезка на данном шаге, а в столбцы B и C – формулы для нахождения точек, которые осуществляют золотое сечение данного отрезка. В столбцах E и F вычисляются значения функции в этих точках, а в столбце G – вычисляется длина рассматриваемого отрезка, т. е. точность вычисления на данном шаге. Для наглядности выбора следующего рассматриваемого отрезка можно выделять ячейки цветом. Последующие строки заполняются с использованием автозаполнения.
Правильность решения можно проверить в MathCAD 2000. Для этого необходимо воспользоваться правилами нахождения экстремума функции средствами математического анализа. Найти производную функции и решить полученное уравнение помогут панели “Калькулус” и “Символика”.
Пример использование MathCAD 2000 и Microsoft Excel для нахождения экстремума функции методом золотого сечения можно увидеть на рис.4.
Использование MathCAD 2000 и Microsoft Excel для поиска экстремума функции методом Ньютона
При нахождении экстремума функции методом Ньютона MathCAD 2000 поможет не только определить отрезок, которому принадлежит экстремум, но и вычислить необходимые для выбора начального приближения первую, вторую, третью производные и значения их на концах рассматриваемого отрезка.
Найти экстремум с заданной степенью точности можно в Microsoft Excel. В столбец А заносится начальное значение экстремума, в столбцах В и С вычисляются значения первой и второй производных в этой точке. В столбце D вычисляется по формуле Ньютона уточнённое значение экстремума, а в столбце Е – точность вычисления на данном шаге.
Пример использование Math CAD 2000 и Microsoft Excel для нахождения экстремума функции методом Ньютона можно увидеть на рис.5
Использование MathCAD 2000 и Microsoft Excel для аппроксимации функций методом наименьших квадратов
При осуществлении линейной аппроксимации функций методом наименьших квадратов для составления уравнения регрессии сначала необходимо вычислить числа Мх, Мху, Му, Мх 2 , это удобно сделать в Microsoft Excel, используя автосуммирование.
По полученным значениям Мх, Мху, Му, Мх 2 составляется система, после решения которой можно будет записать уравнение регрессии. Решить систему можно с помощью MathCAD 2000.
Правильность вычислений можно проверить в MathCAD 2000. Функции interсept(Х,У) и slope(Х,У) вычисляют по заданным векторам экспериментальных данных Х, У значения а0 и а1 для записи уравнения линейной регрессии в виде j (х)=а0+а1х.
Затем с помощью MathCAD 2000 можно убедиться в том, что полученное уравнение регрессии аппроксимирует таблично заданную функцию, построив в одной системе координат график данной функции и полученного уравнения регрессии. Возможности
Пример использование MathCAD 2000 и Microsoft Excel для составления уравнения линейной регрессии можно увидеть на рис.6.
Аналогично используются MathCAD 2000 и Microsoft Excel для выполнения аппроксимации функций многочленами второй степени и составления уравнений регрессии, преобразуемых в линейную. Примеры этого представлены на рис.7 и рис.8.
Использование MathCAD 2000 для численного решения дифференциальных уравнений методом Рунге–Кутта
Осуществление численного решения дифференциального уравнения методом Рунге–Кутта даже в Microsoft Excel весьма трудоёмкий процесс. MathCAD 2000 позволяет облегчить эту задачу.
Решить дифференциальное уравнение методом Рунге–Кутта в MathCAD 2000 можно двумя способами: с помощью встроенной функции и непосредственно по формулам.
При непосредственном осуществлении метода Рунге–Кутта задаются формулы для вычисления необходимых коэффициентов, а затем создаётся цикл для вычисления с помощью их искомых значений у.
Встроенная функция rkfixed позволяет осуществить метод Рунге–Кутта, не производя никаких вычислений. С помощью этой функции можно предложить студентам проверить вычисления, выполненные ими по формулам, а преподавателю быстро просчитать различные варианты.
Пример использование MathCAD 2000 для реализации метода Рунге–Кутта численного решения дифференциального уравнения можно увидеть на рис.9.
Применение MathCAD 2000 и Microsoft Excel для реализации численных методов и для решения других математических задач поможет студентам не только лучше понять приёмы решения задач, не теряя время на рутинные вычисления, но и создаст возможности для использования этих программ при дальнейшем обучении и в профессиональной деятельности.
Метод основан на делении текущего отрезка [а, b], где содержится искомый экстремум, на две неравные части, подчиняющиеся правилу золотого сечения, для определения следующего отрезка, содержащего максимум.
Золотое сечение определяется по правилу: отношение отрезка к большей его части равно отношению большей части отрезка к меньшей. Ему удовлетворяют две точки с и d, расположенные симметрично относительно середины отрезка.
Рис. 3.3. Иллюстрация метода золотого сечения:
1 — интервал, включающий в себя искомый максимум функции после
первого этапа (первого золотого сечения в точках c и d);
2 — то же, после второго этапа (новая точка еи старая точка d
Путем сравнения R(с)и R(e)определяют следующий отрезок, где содержится максимум. Если R(e) > R(с), то в качестве следующего отрезка выбирается отрезок [с, b], в противном случае — отрезок [a, e].
Поэтому на каждой следующей итерации (кроме "запуска" метода на исходном отрезке) нужно вычислять только одно значение критерия оптимальности.
Новый отрезок снова делится на неравные части по правилу золотого сечения. Следует отметить, что точка d является и точкой золотого сечения отрезка [с, b], т.е.
Обозначим коэффициент золотого сечения k=db/cd, тогда можно получить квадратное уравнение для его нахождения
k=0,618
Решение уравнения применительно к первой итерации имеет вид
Условие окончания поиска — величина отрезка, содержащего максимум, меньше заданной погрешности.
Метод обеспечивает более быструю сходимость к решению, чем многие другие методы, и применим, очевидно, только для одноэкстремальных функций.
R(x)=sin(x+1),
Найти максимум на интервале: [-1,2]. Ошибка задается по х: e =0,05.
Результаты расчетов. Для "запуска" метода найдем две симметричные точки золотого сечения для отрезка [-1, 2]:
х1 = 0,145898, х2 = 0,85410197.
Значения критериев в этих точках соответственно R(x1) = 0,911080, R(x2)= 0,960136. Следовательно, новым отрезком является [0,145898,2], внутри которого находится максимальное из найденных значений R. Точка золотого сечения для нового отрезка будет х3= 0,58359214, a R(x3) = 0,99991813.
Далее приведены только координаты лучших точек при очередном шаге, номер шага и значения критерия в этих точках.
x3 = 0,584 R3 = 0,9999 x4 = 0,584 R4 = 0,9999
С точностью до четырёх значащих цифр задача решена на третьей итерации
d)
Читайте также: