Лекции по методам оптимизации - файл n1.doc

Лекции по методам оптимизации
скачать (1278 kb.)
Доступные файлы (1):

n1.doc

1278kb.

29.05.2012 23:54

скачать

---

Смотрите также:
• Громницкий В.С. Лекции по методам оптимизации (Документ)
• Лекции по методам оптимизации (Лекция)
• Лекции по методам оптимизации (Лекция)
• Ответы по методам оптимизации (Шпаргалка)
• Григорьев В.А. Лекции по экспериментальным методам ядерной физики (Документ)
• Лекции - Методы оптимизации (Лекция)
• Лутманов С.В. Курс лекций по методам оптимизации (Документ)
• Измаилов А.Ф., Солодов М.В. Численные методы оптимизации (Документ)
• Ахназарова С.Л., Кафаров В.В. Методы оптимизации эксперимента в химической технологии (Документ)
• КП по методам оптимизации (Документ)
• Хворова Л.А., Жариков А.В. Сборник задач по методам оптимизации и вариационному исчислению (Документ)
• Ларин Р.М., Пяткин А.В., Плясунов А.В. Методы оптимизации примеры и задачи (Документ)

n1.doc

1. 
   Элементы теории погрешностей.
   

1.1.Определение абсолютной и относительной погрешности численного результата.

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

а = А - а .

Абсолютной погрешностью  приближенного числа а называется абсолютная величина разности между соответствующим точным числом А и числом а, т.е.

 = А - а .

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

Под предельной абсолютной погрешностью приближенного числа понимается всякое число, не меньшее абсолютной погрешности этого числа. Таким образом, если а - предельная абсолютная погрешность, то

 = А - а  а .

Относительной погрешностью  приближенного числа а называется отношение абсолютной погрешности  этого числа к модулю соответствующего точного числа А (А0) т.е.

.

Так же как и для абсолютной погрешности вводят понятие предельной относительной погрешности. Под предельной относительной погрешностью _а понимают всякое число, не меньшее относительной погрешности этого числа. В качестве предельной относительной погрешности числа а можно принять число

.
1.2.Основные составляющие абсолютной погрешности.

1.3.Формулы для оценки абсолютной и относительной погрешности для значения функции и переменных.

При сложении или вычитании чисел их абсолютные погрешности складываются. Относительная погрешность суммы заключена между наибольшим и наименьшим значениями относительных погрешностей слагаемых; на практике принимается наибольшее значение.

(a  b) = a + b .

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

;

При возведении в степень приближенного числа его относительная погрешность умножается на показатель степени.



Погрешность разности: предельная абсолютная погрешность разности (u = x₁ - x₂) равна сумме предельных абсолютных погрешностей уменьшаемого и вычитаемого:

_u = _x1 + _x2

Отсюда предельная относительная погрешность разности



где А - точное значение абсолютной величины разности чисел х₁ и х₂ .

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

  ₁ + ₂ + ... + _{n .}

Поэтому при вычислении произведения нескольких приближенных чисел применяют следующие правила:

- округляют эти числа так, чтобы каждое из них содержало на одну (или две) значащие цифры больше, чем число верных значащих цифр в наименее точном из сомножителей;

- в результате умножения сохраняют столько значащих цифр, сколько верных цифр имеется в наименее точном из сомножителей.

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

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

Пусть задана дифференцируемая функция u=(x₁,x₂, ... , x_n) и пусть x_i - абсолютные погрешности аргументов функции.
Тогда предельная абсолютная погрешность функции может быть вычислена по формуле:



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

2. 
   Решение уравнений с одной неизвестной.
   

2.1.Отделение корней уравнения и отделение корней алгебраического уравнения.

Всякое уравнение с одним неизвестным можно представить в виде

(x) = g(x) ,

где (x) и g(x) - данные функции, определенные на некотором числовом множестве Х, называемом областью допустимых значений уравнения. Уравнение с одним неизвестным можно записать в виде

f(x) = 0 .

Совокупность значений переменной х, при котором уравнение превращается в тождество, называется решением этого уравнения, а каждое значение х из этой совокупности, называется корнем уравнения. Решить уравнение - это значит найти множество всех корней этого уравнения. Оно может быть конечным или бесконечным.

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

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

.

Процесс нахождения приближенных значений корней уравнения разбивается на два этапа:

1) отделение корней;

2) уточнение корней до заданной точности.

Корень  уравнения f(x) = 0 считается отделенным на отрезке [a,b], если на этом отрезке уравнение f(x) = 0 не имеет других корней.

Отделить корни - это значит разбить всю область допустимых значений на отрезки, в каждом из которых содержится один корень.

Графический метод отделения корней - в этом случае поступают также, как и при графическом методе решения уравнений.

Если кривая касается оси абсцисс, то в этой точке уравнение имеет двукратный корень (например, уравнение x³ - 3x + 2 = 0 имеет три корня: x₁ = -2 ; x₂ = x₃ = 1).

Если же уравнение имеет трехкратный действительный корень, то в месте касания с осью х кривая y = f(x) имеет точку перегиба (например, уравнение x³ - 3x² + 3x - 1 = 0 имеет корень x₁ = x₂ = x₃ = 1).

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

Теорема 1. Если функция f(x) непрерывна на отрезке [a,b] и принимает на концах этого отрезка значения разных знаков, то внутри отрезка [a,b] существует по крайней мере один корень уравнения f(x) = 0.

Теорема 2. Если функция f(x) непрерывна и монотонна на отрезке [a,b] и принимает на концах отрезка значения разных знаков, то внутри отрезка [a,b] содержится корень уравнения f(x) = 0, и этот корень единственный.

Теорема 3. Если функция f(x) непрерывна на отрезке [a,b] и принимает на концах этого отрезка значения разных знаков, а производная f '(x) сохраняет постоянный знак внутри отрезка, то внутри отрезка [a,b] существует корень уравнения f(x) = 0 и притом единственный.

Порядок действий для отделения корней аналитическим методом:

1) Найти f '(x) - первую производную.

2) Составить таблицу знаков функции f(x), полагая х равным:

а) критическим значениям (корням) производной или ближайшим к ним;

б) граничным значениям (исходя из области допустимых значений неизвестного).


2.2.Понятие кратного корня.

Если кривая касается оси абсцисс, то в этой точке уравнение имеет двукратный корень (например, уравнение x³ - 3x + 2 = 0 имеет три корня: x₁ = -2 ; x₂ = x₃ = 1).

Если же уравнение имеет трехкратный действительный корень, то в месте касания с осью х кривая y = f(x) имеет точку перегиба (например, уравнение x³ - 3x² + 3x - 1 = 0 имеет корень x₁ = x₂ = x₃ = 1).

2.3.Методы уточнения корней простой итерации.

Сущность этого метода заключается в следующем. Пусть дано уравнение f(x) = 0, где f(x) - непрерывная функция, и требуется определить ее вещественные корни. Для этого заменяют исходное уравнение равносильным:

x = (x).

Выбрав приближенное значение корня x₀ подставляют его в правую часть этого уравнения. Тогда получают:

x₁ = (x₀).

После этого процесс продолжают:

x₂ = (x₁) … x_n = (x_n-1).

Если эта последовательность - сходящаяся, т.е. существует предел , то, переходя к пределу в выражении x_n = (x_n-1) и предполагая функцию (x) непрерывной, можно найти:



или

 = ().

Таким образом, предел  является корнем уравнения и может быть вычислен по приведенной формуле с любой степенью точности.

₀

Y=x

Y=(x)

Y=x

Y=(x)

y

y











X₀

X₁

X₂

X₀

X₁

X₂

X₃


На приведенных рисунках процесс итерации сходится (кривая y = (x) в окрестности корня  - пологая, т.е.  '(x) < 1).



X₀

X₁

X₂

y

X

Y=x


(x)=f(x)+x,где :

если f '(x)>0, то –1/r<<0; если f '(x)<0, то –1/r>>0, где r=max(| f '(a)|, |f '(b)|).

Однако, если рассмотреть случай, где '(x) > 1, то процесс итерации может быть рас­ходящимся.

Поэтому для практического применения ме­тода итерации нужно выяснить достаточные условия сходимости итерационного процесса.
(см. вопрос№2.6.)

2.4.Метод Ньютона.

Пусть корень  уравнения f(x) = 0 отделен на отрезке [a,b], причем f '(x) и f "(x) непрерывны и сохраняют определенные знаки при a  x  b. Найдя какое-нибудь n-е приближение корня x_n   (a  x_n  b), можно уточнить его по методу Ньютона следующим образом. Положим  = x_n + h_n , где h_n считают малой величиной. Отсюда, применяя формулу Тейлора, получим

0 = f(x_n + h_n)  f(x_n) + h_n f '(x_n) .

Следовательно,



Отсюда можно найти следующее (по порядку) приближение корня:



X₀

X₁

y

F(x₀)

B

B=x₀

a

0




, (n = 0, 1, 2, …)

Как видно из этого рисунка правильный выбор начального приближения обеспечивает удачу в по­иске корня. Общее правило - "хорошим" начальным приближением является то, для которого выполня­ется неравенство:

f(x₀) f "(x₀) > 0 .

Из общей формулы метода вытекает, что чем больше численное значение первой производной в окрестности данного корня, тем меньше поправка, которую нужно прибавить к n-му приближению, чтобы получить n+1 приближение. Поэтому метод Ньютона удобно применять тогда, когда в окрестности данного корня график функции имеет большую крутизну. Но если численное значение первой производной близ корня мало, то поправки будут велики, и вычисление корня по этому методу может оказаться очень долгим, а иногда и вовсе невозможным.

2.5.Метод хорд.

Пусть для определенности f(a) < 0 и f(b) > 0. Тогда, вместо того, чтобы делить отрезок [a,b] пополам, более естественно разделить его в соотношении f(a)/f(b) . Это дает приближенное значение корня x₁ = a + h .

Для вычисления значения h можно составить пропорцию (см.рисунок)



Откуда



b

B

f(b)

a

A


x



x

y

0




Далее, применяя этот прием к тому из отрезков [a,x] или [b,x], на концах которого функция f(x) имеет противоположные знаки, получим второе приближение корня и т.д.

Геометрически способ пропорциональ­ных частей эквивалентен замене кривой y = f(x) хордой, проходящей через точки A [a, f(a)] и B [b, f(b)]. Отсюда можно получить еще одну формулу этого метода. Из подобия треугольников вытекает, что

. Отсюда .
2.6.Достаточное условие сходимости метода простой итерации.

Пусть функция (x) определена и диффе­ренцируема на отрезке [a,b], причем все ее зна­чения (x)  [a,b].

Тогда, если выполняется условие

 '(x) < 1

при a < x < b, то:

1) процесс итерации x_n = (x_n-1) (n=1,2,…) сходится независимо от начального значения x₀  [a,b];

2) предельное значение является единственным корнем уравнения x = (x) на отрезке [a,b] .

Если это условие выполняется не на всем интервале, то метод может как сходиться, так и расходиться.

Вывод условия сходимости:

Так как  = () и x_n = (x_n-1), то можно записать



По теореме о среднем (она утверждает, что если производная функции f(x) непрерывна на некотором интервале [a,b], то тангенс угла наклона хорды, проведенной между точками a и b (т.е. {f(b)-f(a)/(b-a)} равен производной функции в некоторой промежуточной точке, лежащей между a и b) частное в последнем выражении будет равно '(C), где С - некоторая промежуточная точка в интервале поиска корня.

Следовательно

x_n -  =  ' (C)  (x_n-1 - )

Если ввести обозначение M = max ' (x) для всего интервала поиска, то предыдущее равенство может быть переписано в виде:

x_n -   M  x_n-1 - 

Аналогично

x_n-1 -   M  x_n-2 - 

Тогда для x_n -  будет справедливо неравенство:

x_n -   M ²  x_n-2 - 

и т.д.

Продолжая эти выкладки дальше, в результате получаем

x_n -   M ⁿ  x₀ - 

где n - натуральное число.

Чтобы метод сходился, необходимо выполнение неравенства:

x_n -  < M ⁿ  x₀ - 

Отсюда следует, что M = max ' (x) должно быть меньше единицы.

В свою очередь, для всех остальных значений  ' (x) меньших М, можно записать:

 ' (x) < 1

2.7.Оценка погрешности n-приближения.

Метод хорд: |x*- x_n | (M₁-m1)|x_n - x_n-1|/ m₁,где M1,m₁-наибольшее и наименьшее значение |f’(x)| на [a,b].

Метод Ньютона:|x*- x_n | M₂(x_n - x_n-1) ²/2 m₁,где M2-наибольшее значение |f’’(x)|, m1- наименьшее значение |f’(x)| на [a,b].

Метод итераций: Пусть  - точное значение корня уравнения х = (x), а число q определяется из соотношения '(x)  q < 1. Тогда справедливо соотношение (вывод см. ниже):

.

Если поставить условие, что истинное значение корня  должно отличаться от приближенного значения на величину , т.е.  - x_n, то приближения x₀, x₁, … , x_n надо вычислять до тех пор, пока не будет выполнено неравенство

или

и тогда  = x_n  

3. 
   Решение систем линейных уравнений.
   

Линейная система n уравнений может быть записана в виде:

a₁₁x₁ + a₁₂x₂ + … + a_1nx_n = b₁

a₂₁x₁ + a₂₂x₂ + … + a_2nx_n = b₂

. . . . . . . . . . .

a_n1x₁ + a_n2x₂ + … + a_nnx_n = b_n

Эту систему линейных уравнений можно также записать в матричном виде:

,

где A - матрица коэффициентов системы, а и - вектор-столбец неизвестных и вектор-столбец правых частей соответственно.

.

---