Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Шпоры по численным методам анализа - файл 1.doc


Шпоры по численным методам анализа
скачать (790.8 kb.)

Доступные файлы (1):

1.doc906kb.25.05.2009 16:44скачать

содержание
Загрузка...

1.doc

Реклама MarketGid:
Загрузка...
Численные методы анализа.

1.Аппроксимация функций с помощью алгебраических и тригонометрических многочленов.

Экспериментально в точках х1, х2…хn определены значения функции у12…уn неизвестной функции. Надо подобрать замену этой функции в виде другой известной. Т.е. надо найти полином степени “n” : . Для этого полинома выполняется , j = 1,2…N, n=N-1

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


Найти полином (РN-1(х)), который в N точках совпадает со значением функции f(х)

или , где ,

При увеличении N максимальное отклонение может возрастать. Интерполяционный полином Лагранжа эффективен при интерполяции гладкой кривой и при небольшом N.

Если выбрать в качестве узлов интерполяции например нули полинома Чебышева 1-ого рода можно уменьшить абсолютную погрешность интерполирования. , если считать f(x) на [-1:1] из ТN(x)=0 следует , тогда полином Лагранжа:

Для отрезка [a:b]: ,



Точность аппроксимации значительно увеличивается.
^

Интерполяционная формула Ньютона


В ней используются разделенные разности.

  • 1-ого порядка:

  • 2-ого порядка:

Если все узлы интерполяции равноотстоящие, то можно использовать таблицу разностей, каждый элемент которой

Интерполяционную формулу Ньютона можно представить в виде



Это формула интерполирования вперед, дающая наибольшую точность в начале кривой.






^
2.Аппроксимация функции с помощью кубического сплайна

Сплайны – многочлены 3-ей степени, построенные специальным образом.

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

Для определения коэффициентов а, b, c, d на всех (N-1) отрезках необходимо получить 4*(N-1) уравнений.

Часть уравнений составляется из условия прохождения функцией (х) через заданные точки эксперимента

, j=2,3…N

Так получаем 2*(N-1) уравнений.

Для получения недостающих уравнений используем условие непрерывности 1-ых и 2-ых производных в узлах интерполяции. Приравнивая в каждом внутреннем узле значение этих производных, вычисленных в правом и левом от узла интерполяции интервалах, получим еще 2*(N-1)-2 уравнения:

Ещё 2 уравнения получим из условия закрепления концов сплайна. При свободном закреплении концов можно приравнять к нулю кривизну линий в этих точках (эта функция – свободный кубический сплайн) 2-ые производные в этих точках равны нулю.



С целью экономии машинного времени:

Сначала находят аj-1= yj-1, затем

Далее подстановкой и

В окончательном виде получим с1=0, сN-1=0,

По найденным сj находят b и d.

На каждом интервале своя сплайн функция.

При интерполяции сплайнами следует чаще выбирать узлы интерполяции на нелинейных участках изменения функции.

^ 3,4.Явные и неявные методы численного решения систем диф. уравнений. Одношаговые и многошаговые методы.

Общий вид разностного уравнения:

Если в правой части уравнения нет yj+1, то оно вычисляется явно по R- предыдущим значениям. При этом и метод называется явным (R-шаговым).

Если в правой части есть искомое значение yj+1, то решение усложняется. В таких методах называемых неявными уравнение решается с помощью итерационных методов.

Одношаговые методы:

^ Метод Эйлера (явный):

Блок-схема



Имеет первый порядок точности



В одношаговых методах для нахождения yj+1 используется только ранее найденное значение на предыдущем шаге yj.

^ Метод Эйлера с пересчетом (неявный)





Для вычисления предварительно находится первое приближение
по формуле

И новое значение подставляется вместо yj+1, т.е.

Увеличивается время расчета, но метод имеет второй порядок точности.

^ Метод Рунге-Кутта (явный)

- четвёртого порядка.

R0 – значение производной в точке (xj;yj)

R1 – значение производной в точке

R2 – значение производной в точке

R3 – значение производной в точке

Методы Эйлера можно рассматривать как метод Рунге-Кутта 1-ого и 2-ого порядка. Наиболее широко используемый.

Многошаговые методы:

Для вычисления yj+1 используются результаты R-предыдущих шагов. Генерируются так: перепишем , интегрируем на отрезке [хjj+1]

Интеграл левой части

Интеграл правой части

Приравняв получим

Методы Адамса (явные)

При R=1 совпадает с методом Эйлера 1-ого порядка точности. Чаще используется метод при R=4:

Метод не позволяет начать счет по известному (х00). Значения у1, у2, у3 необходимо рассчитать каким-либо другим способом.
Неявные R-шаговые методы Адамса



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

Используя неявный метод в результате итерации находится приближение ,s – номер итерации.

Явные разностные методы являются условно устойчивыми, а среди неявных существуют абсолютно устойчивые

Или h>0 (всегда)


^ 5.Методы одномерной и многомерной оптимизации

Процесс выбора наилучшего варианта из всех возможных называется оптимизацией.

Целевая функция – глобальный критерий оптимальности.
^ Одномерная оптимизация.

Постановка задачи: определить наибольшее или наименьшее значение целевой функции у=f(х) на отрезке [a,b].

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

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

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

На каждом шаге, кроме 1-ого, вычисление значений f(х) происходит лишь в одной точке – точке Золотого сечения. Она выбирается так, чтобы отношение большей части отрезка к длине всего отрезка равнялось отношению длины меньшей части к длине большей части отрезка.



Ещё существует метод деления отрезка пополам.
^ Многомерная оптимизация.

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

При решении задачи оптимизации с числом параметров 3 и более применяются следующие методы:

^ Метод покоординатного спуска.

Надо найти наименьшее значение целевой функции

Предварительно выбираем в n-мерном пространстве начальную точку К0 с координатами . Далее фиксируют все координаты функции кроме 1-ой, получая

Функция одной переменной (х1). Решая одномерную задачу оптимизации находят координату , в которой значение целевой функции минимально. От точки К0 переходим к точке К1 с координатами

. Это спуск по координате х1. Далее то же для других координат.

Метод градиентного спуска

Направление наибольшего возрастания функции характеризуется её градиентом , - единичные векторы.

  1. Предварительно выбирают некоторую начальную точку и вычисляют в ней градиент целевой функции.

  2. Делают шаг в направлении, обратном градиентному, получая точку, значение функции в которой меньше первоначального.

  3. В новой точке снова вычисляют градиент и делают шаг в обратном направлении и тд - До равенства нулю градиента.

^ Метод наискорейшего спуска

Модификация метода градиентного спуска.

В направлении противоположном градиентному двигаются до тех пор пока целевая функция убывает. В этой точке снова определяют направление спуска и тд.


^ 6. Задачи оптимизации с ограничениями

Метод штрафных функций. Решение задач математического программирования значительно более трудоемко по сравнению с задачами безусловной оптимизации. Ограничения типа равенств или неравенств требуют их учета на каждом шаге оптимизации. Одним из направлений в методах решения задач математического программирования является сведение их к последовательности задач безусловной оптимизации. К этому направлению относится, в частности, метод штрафных функций.
Сущность метода состоит в следующем. Пусть f(x1,x2,…,xn) - целевая функция, для которой нужно найти минимум т в ограниченной области D (). Данную задачу заменяем задачей о безусловной минимизации однопараметрического семейства функций
(2)
При этом дополнительную (штрафную) функцию j (x) выберем таким образом, чтобы при решение вспомогательной задачи стремилось к решению исходной или, по крайней мере, чтобы их минимумы совпадали: при .
Штрафная функция j (x) должна учитывать ограничения, которые задаются при постановке задачи оптимизации. В частности, если имеются ограничения-неравенства вида (j = 1,2,…, J), то в качестве штрафной функции можно взять функцию, которая:

1) равна нулю во всех точках пространства проектирования, удовлетворяющих заданным ограничениям-неравенствам;

2) стремится к бесконечности в тех точках, в которых эти неравенства не выполняются. Таким образом, при выполнении ограничений-неравенств функции f(x) и F(x,b ) имеют один и тот же минимум. Если хотя бы одно неравенство не выполнится, то вспомогательная целевая функция F(x,b ) получает бесконечно большие добавки. И ее значения далеки от минимума функции f(x). Другими словами, при несоблюдении ограничений-неравенств налагается “штраф”. Отсюда и термин “метод штрафных функций”.
Теперь рассмотрим случай, когда в задаче оптимизации заданы ограничения двух типов - равенства и неравенства:

(3)

В этом случае в качестве вспомогательной целевой функции, для которой формулируется задача безусловной оптимизации во всем n-мерном пространстве, принимают функцию

. (4)

Здесь взята такая штрафная функция, что при выполнении условий (3) она обращается в нуль. Если же эти условия нарушены (т. е. , hj(x) < 0 и sign hj(x) = -1), то штрафная функция положительна. Она увеличивает целевую функцию f(x) тем больше, чем больше нарушаются условия (3).
При малых значениях параметра b вне области D функция F(x,b ) сильно возрастает. Поэтому ее минимум может быть либо внутри D, либо снаружи вблизи границ этой области. В первом случае минимумы функций F(x,b ) и f(x) совпадают, поскольку дополнительные члены в (4) равны нулю. Если минимум функции F(x,b ) находится вне D, то минимум целевой функции f(x) лежит на границе D. Можно при этом построить последовательность такую, что соответствующая последовательность минимумов функции F(x,b ) будет стремиться к минимуму функции f(x).
Таким образом, задача оптимизации для целевой функции f(x) с ограничениями (3) свелась к последовательности задач безусловной оптимизации для вспомогательной функции (4), решение которых может быть проведено с помощью методов спуска. При этом строится итерационный процесс при .


Скачать файл (790.8 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации